推移閉包

数学において、集合X上の同次二項関係Rの推移閉包 R ^{+ は}、 R を含み推移的なX上の最小の関係です。有限集合の場合、「最小」は通常の意味で、関連するペアが最も少ないという意味でとらえることができます。無限集合の場合、R ^+はRの唯一の最小推移スーパーセットです。

たとえば、X が空港の集合であり、x R yが「空港xから空港yへの直行便がある」という意味である場合 ( Xのxとyに対して)、 RのX上の推移閉包は、 x R ⁺ yが「1 回以上のフライトでxからyまで飛行することが可能」という意味になるような関係R ⁺です。

より正式には、集合X上の二項関係Rの推移閉包は、R ⊆ R ⁺となるようなX上の最小の (⊆ に関して) 推移関係R ⁺です。Lidl & Pilz (1998、p. 337) を参照してください。R自体が推移的である場合に限り、R ⁺ = Rとなります。

逆に、推移的簡約は、与えられた関係Rから、同じ閉包、つまりS ⁺ = R ^{+ を}持つような極小関係S を導出します。ただし、この特性を持つ異なるS が多数存在する可能性があります。

推移閉包と推移簡約は、グラフ理論という密接に関連する分野でも使用されます。

集合X上の関係Rが推移的であるとは、X内のすべてのx、y、zについて、 x R yかつy R z であればx R zであることを意味します。推移的な関係の例には、任意の集合上の等式関係、任意の線形順序集合上の「以下」関係、およびすべての人々の集合上の「x はyより前に生まれた」関係が含まれます。これは、記号的に次のように表すことができます。x < yかつy < zであればx < z。

非推移的関係の一例は、すべての都市の集合上で「都市xへは都市yからの直行便で行くことができる」というものです。ある都市から 2 番目の都市への直行便があり、2 番目の都市から 3 番目の都市への直行便があるからといって、最初の都市から 3 番目の都市への直行便があるというわけではありません。この関係の推移閉包は別の関係、つまり「都市xから始まり都市yで終わる直行便の列がある」という関係です。すべての関係は、同様の方法で推移的関係に拡張できます。

あまり意味のない推移閉包を持つ非推移的関係の例は、「xはyの次の曜日である」です。この関係の推移閉包は、「カレンダー上である日x がyの次の曜日になる」であり、これはすべての曜日xとyに対して自明に当てはまります(したがって、「xとyは両方とも曜日である」 というデカルト平方に相当します)。

任意の関係Rに対して、 Rの推移閉包は常に存在します。これを確認するには、推移関係の任意の族の交差が再び推移的であることに注目してください。さらに、 R を含む推移関係が少なくとも 1 つ存在します。つまり、自明な関係です: X × X。Rの推移閉包は、 R を含むすべての推移関係の交差によって与えられます。

有限集合の場合、 Rから始めて推移的な辺を追加することで、推移閉包を段階的に構築することができます。これにより、一般的な構築に対する直感が得られます。任意の集合Xに対して、推移閉包が次の式で与えられることを証明できます 。

${\displaystyle R^{+}=\bigcup _{i=1}^{\infty }R^{i}.}$

ここでRのi乗は、次のように帰納的に定義される。 ${\displaystyle R^{i}}$

${\displaystyle R^{1}=R}$

そして、 については、 ${\displaystyle i>0}$

${\displaystyle R^{i+1}=R\circ R^{i}}$

ここで は関係の合成を表します。 ${\displaystyle \circ}$

上記のR ^{+の定義が}R を含む最小の推移関係であることを示すために、それがR を含み、推移的であり、そして、これら両方の特性を備えた最小の集合であることを示します。

• ${\displaystyle R\subseteq R^{+}}$:には がすべて含まれているため、特に にはが含まれます。${\displaystyle R^{+}}$${\displaystyle R^{i}}$${\displaystyle R^{+}}$${\displaystyle R}$
• ${\displaystyle R^{+}}$は推移的です: の場合、 の定義により、に対して およびが成り立ちます。合成は結合的であるため、であり、したがって の定義によりおよび が成り立ちます。${\displaystyle (s_{1},s_{2}),(s_{2},s_{3})\in R^{+}}$${\displaystyle (s_{1},s_{2})\in R^{j}}$${\displaystyle (s_{2},s_{3})\in R^{k}}$${\displaystyle j,k}$${\displaystyle R^{+}}$${\displaystyle R^{j+k}=R^{j}\circ R^{k}}$${\displaystyle (s_{1},s_{3})\in R^{j+k}\subseteq R^{+}}$${\displaystyle \circ}$${\displaystyle R^{+}}$
• ${\displaystyle R^{+}}$は最小、つまり がを含む任意の推移関係である場合、であることを意味します。 このような が与えられている場合、に関する帰納法を使用して、すべて について次のように示すことができます。基底:仮定により。ステップ:が成り立ち、 である場合、の定義により、およびいくつかの について が成り立ちます。したがって、仮定により、帰納法の仮説により が成り立ちます。したがっての推移性により、により; これで帰納法が完了します。最後に、すべて について は、の定義により を意味します。${\displaystyle T}$${\displaystyle R}$${\displaystyle R^{+}\subseteq T}$${\displaystyle T}$${\displaystyle i}$${\displaystyle R^{i}\subseteq T}$${\displaystyle i}$ ${\displaystyle R^{1}=R\subseteq T}$${\displaystyle R^{i}\subseteq T}$${\displaystyle (s_{1},s_{3})\in R^{i+1}=R\circ R^{i}}$${\displaystyle (s_{1},s_{2})\in R}$${\displaystyle (s_{2},s_{3})\in R^{i}}$${\displaystyle s_{2}}$${\displaystyle \circ}$${\displaystyle (s_{1},s_{2}),(s_{2},s_{3})\in T}$${\displaystyle (s_{1},s_{3})\in T}$${\displaystyle T}$${\displaystyle R^{i}\subseteq T}$${\displaystyle i}$${\displaystyle R^{+}\subseteq T}$${\displaystyle R^{+}}$

2 つの推移的関係の交差は推移的です。

2 つの推移関係の和集合は推移的である必要はありません。推移性を保つには、推移閉包をとらなければなりません。これは、たとえば、2 つの同値関係または 2 つの前順序の和集合を取るときに発生します。新しい同値関係または前順序を得るには、推移閉包をとらなければなりません (同値関係の場合、反射性と対称性は自動的に行われます)。

コンピュータサイエンスにおいて、推移閉包の概念は、到達可能性の質問に答えることを可能にするデータ構造を構築することと考えることができます。つまり、ノードaからノードdまで1 回以上のホップで到達できるかどうかです。2 項関係は、ノード a がノードbに接続され、ノードbがノードcに接続されていることなどのみを示します。次の図に示すように、推移閉包が構築された後、O(1)操作で、ノードdがノードaから到達可能であることを決定できます。データ構造は通常、ブール行列として格納されるため、matrix[1][4] = true の場合、ノード 1 は 1 回以上のホップでノード 4 に到達できます。

有向非巡回グラフ(DAG)の隣接関係の推移閉包は、DAG と厳密な半順序の到達可能性関係です。

無向グラフの推移閉包は、クリークの互いに素な和集合であるクラスターグラフを生成する。推移閉包を構築することは、グラフの構成要素を見つける問題と同等の定式化である。 ^[1]

二項関係の推移閉包は、一般に一階述語論理(FO) では表現できない。つまり、述語記号RとT を使用して、 T がRの推移閉包である場合に限り、どのモデルでも満たされる式を書くことはできない。有限モデル理論では、推移閉包演算子で拡張された一階述語論理 (FO) は通常、推移閉包論理と呼ばれ、FO(TC) または単に TC と略される。TC は不動点論理のサブタイプである。FO(TC) が FO よりも厳密に表現力が高いという事実は、 1974 年にRonald Faginによって発見され、その結果は1979 年にAlfred AhoとJeffrey Ullmanによって再発見され、彼らは不動点論理をデータベース クエリ言語として使用することを提案した。^[2]有限モデル理論のより最近の概念では、FO(TC) が FO よりも厳密に表現力が高いことの証明は、FO(TC) が Gaifman 局所的でないという事実から直ちに導かれる。^[3]

計算複雑性理論では、計算複雑性クラス NL はTC で表現可能な論理文の集合に正確に対応します。これは、推移閉包特性がグラフ内の有向パスを見つけるNL 完全問題STCONと密接な関係があるためです。同様に、クラスL は可換推移閉包を持つ一階述語論理です。代わりに二階述語論理に推移閉包を追加すると、PSPACEが得られます。

1980 年代以降、Oracle Database は、宣言型クエリの一部として推移閉包を計算できる独自のSQL拡張機能を実装してきました。SQL 3 (1999) 標準では、より一般的な構造が追加され、推移閉包をクエリ プロセッサ内で計算できるようになりました。2011 年現在、後者はIBM Db2、Microsoft SQL Server、Oracle、PostgreSQL、およびMySQL (v8.0+) に実装されています。SQLiteは2014 年にこれをサポートしました。 CONNECT BY... START WITHWITH RECURSIVE

Datalogは推移閉包計算も実装している。^[4]

MariaDBは、推移閉包を計算するために使用できる再帰共通テーブル式を実装しています。この機能は、2016年4月のリリース10.2.2で導入されました。^[5]

グラフの隣接関係の推移閉包を計算するための効率的なアルゴリズムは、Nuutila (1995) に示されています。問題を隣接行列の乗算に簡約すると、行列乗算の時間計算量 を達成できます( ^[6] )。ただし、このアプローチは、疎なグラフの定数係数とメモリ消費量が大きいため、実用的ではありません (Nuutila 1995、pp. 22–23、sect.2.3.3)。この問題は、のFloyd–Warshall アルゴリズム、またはグラフの各ノードから開始する 幅優先探索または深さ優先探索を繰り返すことによっても解決できます。${\displaystyle O(n^{2.3728596})}$${\displaystyle O(n^{3})}$

有向グラフの場合、パードムのアルゴリズムは、まずその凝縮DAGとその推移閉包を計算し、次にそれを元のグラフに持ち上げることで問題を解決します。その実行時間はで、 は強く連結されたコンポーネント間の辺の数です。^{[7] [8] [9] [10]}${\displaystyle O(m+\mu n)}$${\displaystyle \mu}$

最近の研究では、 MapReduceパラダイムに基づく分散システム上で推移閉包を計算する効率的な方法が研究されている。^[11]

• 祖先関係
• 演繹的閉鎖
• 反射的閉鎖
• 対称閉鎖
• 推移的縮約（ Rの推移閉包を推移閉包として持つ最小の関係）

• Foto N. Afrati、Vinayak Borkar、Michael Carey、Neoklis Polyzotis、Jeffrey D. Ullman、「Map-Reduce Extensions and Recursive Queries」、EDBT 2011、2011 年 3 月 22 ～ 24 日、ウプサラ、スウェーデン、ISBN 978-1-4503-0528-0 
• Aho, AV ; Ullman, JD (1979)。「データ検索言語の普遍性」。プログラミング言語の原理に関する第 6 回 ACM SIGACT-SIGPLAN シンポジウム議事録 - POPL '79 。pp . 110–119。doi :10.1145/567752.567763。
• Benedikt, M.; Senellart, P. (2011)。「データベース」。Blum, Edward K.、Aho, Alfred V. (編)。コンピュータサイエンス。ハードウェア、ソフトウェア、そしてその中心。pp. 169–229。doi :10.1007 / 978-1-4614-1168-0_10。ISBN 978-1-4614-1167-3。
• ハインツ・ディーター・エビングハウス。ヨルク・フルム (1999)。有限モデル理論(第 2 版)。スプリンガー。 123–124、151–161、220–235ページ。ISBN 978-3-540-28787-2。
• Fischer, MJ; Meyer, AR (1971 年 10 月)。「ブール行列乗算と推移閉包」(PDF) 。Raymond E. Miller および John E. Hopcroft (編)。Proc . 12th Ann. Symp. on Switching and Automata Theory (SWAT)。IEEE Computer Society。pp. 129–131。doi :10.1109/SWAT.1971.4。
• Erich Grädel、Phokion G. Kolaitis、Leonid Libkin、Maarten Marx、Joel Spencer、Moshe Y. Vardi、Yde Venema、Scott Weinstein (2007)。有限モデル理論とその応用。Springer。pp. 151–152。ISBN 978-3-540-68804-4。
• Keller, U., 2004, Some Remarks on the Definitive Closure of Transitive Closure in First-order Logic and Datalog (未発表原稿)* Libkin, Leonid (2004), Elements of Finite Model Theory , Springer, ISBN 978-3-540-21202-7
• リドル、R.; ピルツ、G. (1998)、応用抽象代数、学部生向け数学テキスト（第2版）、Springer、ISBN 0-387-98290-6
• Munro, Ian (1971年1月). 「有向グラフの推移閉包の効率的な判定」. Information Processing Letters . 1 (2): 56–58. doi :10.1016/0020-0190(71)90006-8.
• Nuutila, Esko (1995)。大規模有向グラフにおける効率的な推移閉包計算。フィンランド技術アカデミー。ISBN 951-666-451-2. OCLC  912471702.
• Abraham Silberschatz、Henry Korth、S. Sudarshan (2010)。データベース システムの概念 (第 6 版)。McGraw- Hill。ISBN 978-0-07-352332-3。付録 C (オンラインのみ)

• 「推移的閉包と縮約」、ストーニーブルック アルゴリズム リポジトリ、Steven Skiena。