GYOアルゴリズム

GYOアルゴリズム^{[ 1 ]}はハイパーグラフに適用されるアルゴリズムです。このアルゴリズムはハイパーグラフを入力として受け取り、ハイパーグラフがα-非巡回であるかどうかを判定します。そうであれば、ハイパーグラフの分解を計算します。

このアルゴリズムは1979年にグラハムによって提案され、その後、ユーとオズソヨグルによっても独立に提案されたため、その名が付けられた。

ハイパーグラフはグラフの一般化である。正式には、ハイパーグラフは${\displaystyle H=(V,E)}$ハイパーグラフは、頂点 の集合Vと、頂点Vの部分集合であるハイパーエッジの集合Eから構成されます。ハイパーグラフが与えられた場合、同じ頂点の集合上で定義される無向グラフとして、その原始グラフを定義できます。この無向グラフでは、何らかのハイパーエッジで一緒に現れる任意の 2 つの頂点の間にエッジを配置します。

ハイパーグラフHがα-非巡回であるとは、弦グラフであることと等角グラフであることの 2 つの条件を満たす場合をいう。より正確には、Hの原始グラフが弦グラフである場合、H は弦グラフであると言う。また、原始グラフの任意のクリークに対して、そのクリークのすべての頂点を含むHのハイパーエッジが存在する場合、 Hは等角グラフであると言う。

GYOアルゴリズムは、ハイパーグラフを入力として受け取り、それがこの意味でα-非巡回グラフであるかどうかを判定します。

このアルゴリズムは、ハイパーグラフが完全に分解されるまで、ハイパーグラフのいわゆる「耳」を繰り返し除去していく。

正式には、ハイパーグラフのハイパーエッジeは${\displaystyle H}$以下の2つの条件のうちいずれかが満たされる場合、それは耳である。

• ${\displaystyle e}$は孤立している、つまり、他のすべてのハイパーエッジに対して${\displaystyle e'}$、 我々は持っています${\displaystyle e\cap e'=\emptyset }$;
• ${\displaystyle e}$別のハイパーエッジによってほぼ覆われている、つまり、別のハイパーエッジが存在する${\displaystyle f}$すべての頂点が${\displaystyle e\setminus f}$のみ発生する${\displaystyle e}$。

特に、他のエッジの部分集合であるすべてのエッジは耳である。

GYOアルゴリズムは、その後以下のように進行します。

• Hの中にear e を見つけます。
• eを削除し、 eにのみ含まれるHのすべての頂点を削除します。

アルゴリズムがすべての頂点を正常に除去できた場合、ハイパーグラフはα-非巡回グラフである。そうでない場合、つまりアルゴリズムが耳を持たない空でないハイパーグラフに到達した場合、元のハイパーグラフはα-非巡回グラフではなかった。

GYOアルゴリズムは、Hが空ハイパーグラフである場合に限り、空のハイパーグラフで終了します。${\displaystyle \alpha }$-非環状

まず、GYOアルゴリズムが空のハイパーグラフで終了すると仮定します。${\displaystyle e_{1},\ldots ,e_{m}}$は、それが発見した耳のシーケンスとし、${\displaystyle H_{0},\ldots ,H_{m}}$得られたハイパーグラフのシーケンス（特に${\displaystyle H_{0}=H}$そして${\displaystyle H_{m}}$は空のハイパーグラフです。${\displaystyle H_{m}}$空のハイパーグラフは、${\displaystyle \alpha }$非巡回。次に、次のことを確認できます。${\displaystyle H_{n}}$は${\displaystyle \alpha }$-非巡回${\displaystyle H_{n-1}}$また${\displaystyle \alpha }$-非巡回。これは、${\displaystyle H_{0}}$確かに${\displaystyle \alpha }$非環状。

反対方向については、${\displaystyle H}$は${\displaystyle \alpha }$-非巡回では、${\displaystyle H}$耳がある${\displaystyle e}$[ ^{2 ]}この耳を取り除いてもハイパーグラフは依然として非巡回的であるため、ハイパーグラフが空になるまでこのプロセスを続けることができます^。

• アビテブール、セルジュ；ハル、リチャード；ヴィアヌ、ヴィクター（1994年12月2日）。データベースの基礎：論理レベル（PDF）。マサチューセッツ州レディング：ピアソン。ISBN 978-0-201-53771-0。アルゴリズム6.4.4を参照してください。
• Koutris、パリ。「講義4：非巡回結合クエリ」（PDF）。
• アレナス、マルセロ。バルセロ、パブロ。リブキン、レオニード。マルテンス、ウィム。ピエリス、アンドレアス（2022年8月19日）。 「第18章」。データベース理論 (暫定版)。
• Tziavelis, Giorgos; Gatterbauer, Wolfgang; Riedewald, Mirek (2022). "応答性の高いDBMSに向けて：最適な結合アルゴリズム、列挙、因数分解、ランキング、および動的計画法" . ICDE 2022 チュートリアル.パート 3: 非巡回クエリと列挙。スライド、20 分のビデオ、チュートリアル ページ。

• ヤナカキスアルゴリズム