結合アルゴリズムの特性を示す図。2つ以上の属性で2つ以上のリレーションを結合する場合、ハッシュ結合などのバイナリ結合アルゴリズムは一度に2つのリレーションを処理し、結合条件のすべての属性でそれらを結合します。ジェネリック結合などの最悪ケース最適アルゴリズムは一度に1つの属性を処理しますが、この属性ですべてのリレーションを結合します。[ 1 ]最悪ケース最適結合アルゴリズムとは、結合の最悪ケース出力サイズによって実行時間が制限される、関係結合を計算するアルゴリズムのことです。ハッシュ結合などの従来の二項結合アルゴリズムは、一度に2つの関係を処理します。3つ以上の関係間の結合は、二項結合を繰り返し適用することで実現されます。最悪ケース最適結合アルゴリズムは、このような反復二項結合に基づくどの結合アルゴリズムよりも、最悪ケースにおいて漸近的に高速です。
最初の最悪ケース最適結合アルゴリズムであるgeneric joinは2012年に発表されました。[ 2 ]最悪ケース最適結合アルゴリズムは、 LogicBloxシステムを含む商用データベースシステムに実装されています。[ 3 ] [ 4 ]最悪ケース最適結合は、e-matchingの最悪ケース最適アルゴリズムを構築するために適用されています。[ 5 ]
参考文献
注記
- ↑ Wang, Yisu Remy; Willsey, Max; Suciu, Dan (2023-01-27). "Free Join: Unifying Worst-Case Optimal and Traditional Joins". arXiv : 2301.10841 [ cs.DB ].
- ↑ Ngo, Hung Q.; Porat, Ely; Ré, Christopher; Rudra, Atri (2012-03-08). "Worst-case Optimal Join Algorithms". arXiv : 1203.1952 [ cs.DB ].
- ↑ Veldhuizen, Todd L. (2013-12-20). "Leapfrog Triejoin: 最悪の場合に最適な結合アルゴリズム". arXiv : 1210.0481 [ cs.DB ].
- ↑ Freitag, Michael; Bandle, Maximilian; Schmidt, Tobias; Kemper, Alfons; Neumann, Thomas (2020-07-01). "リレーショナルデータベースシステムにおける最悪ケース最適結合の採用" (PDF) . Proceedings of the VLDB Endowment . 13 (12): 1891– 1904. doi : 10.14778/3407790.3407797 . ISSN 2150-8097 . S2CID 221115321 . 2024-02-01 のオリジナルからアーカイブ済み。
- ↑ Zhang, Yihong; Wang, Yisu Remy; Willsey, Max; Tatlock, Zachary (2022-01-12). "関係的電子マッチング" . ACM プログラミング言語に関する論文集. 6 (POPL): 35:1–35:22. arXiv : 2108.02290 . doi : 10.1145/3498696 . S2CID 236924583 .
情報源
- Ngo, Hung Q.; Porat, Ely; Ré, Christopher; Rudra, Atri (2018-03-13). "最悪ケース最適結合アルゴリズム" . Journal of the ACM . 65 (3): 16:1–16:40. arXiv : 1203.1952 . doi : 10.1145/3180143 . ISSN 0004-5411 .
- Ngo, Hung Q; Ré, Christopher; Rudra, Atri (2014-02-28). "Skew strikes back: new developments in the theory of join algorithms" . ACM SIGMOD Record . 42 (4): 5–16 . doi : 10.1145/2590989.2590991 . ISSN 0163-5808 . S2CID 6384477 .
