Transitive Schließung

Im Mathematik, das Transitive Schließung von a binäre Beziehung R auf einen einstellen X ist der kleinste Beziehung an X das beinhaltet R und ist transitiv. Für endliche Sets kann "kleinste" in seinem üblichen Sinne von den wenigsten verwandten Paaren aufgenommen werden. Für unendliche Sets ist es das einzigartige minimal transitiv Superset von R.

Zum Beispiel wenn X ist eine Reihe von Flughäfen und x r y bedeutet "Es gibt einen Direktflug vom Flughafen x zum Flughafen y" (zum x und y in X), dann der transitive Verschluss von R an X ist die Beziehung R⁺ so dass x R⁺ y bedeutet "es ist möglich, von zu fliegen x zu y in einem oder mehreren Flügen ". informell die Transitive Schließung Gibt Ihnen das Set aller Orte, an die Sie von jedem Startplatz aus erreicht werden können.

Formell die transitive Schließung einer binären Beziehung R auf einem Set X ist die transitive Beziehung R⁺ am Set X so dass R⁺ enthält R und R⁺ ist minimal; sehen Lidl & Pilz (1998, p. 337). Wenn die binäre Beziehung selbst transitiv ist, ist der transitive Verschluss dieselbe binäre Beziehung; Andernfalls ist der transitive Verschluss eine andere Beziehung.

Umgekehrt, Transitive Reduktion ergibt eine minimale Beziehung S aus einer bestimmten Beziehung R so dass sie die gleiche Schließung haben, das heißt, S⁺ = R⁺; Allerdings viele verschiedene S mit dieser Eigenschaft kann existieren.

Sowohl Transitivverschlüsse als auch transitive Reduktion werden ebenfalls im eng verwandten Bereich von verwendet Graphentheorie.

Transitive Beziehungen und Beispiele

Eine Relation R auf einem Set X ist transitiv, wenn für alle x, y, z in X, wann immer x r y und y r z dann x r z. Beispiele für transitive Beziehungen umfassen die Gleichstellungsbeziehung an jedem Satz, die "weniger oder gleiche" Beziehung zu einem linear geordneten Satz und der Beziehung "x wurde vorher geboren y"Am Set aller Menschen. Symbolisch kann dies als bezeichnet werden als: wenn x < y und y < z dann x < z.

Ein Beispiel für eine nicht-transitive Beziehung ist "Stadt x kann über einen Direktflug aus der Stadt erreicht werden y"Am Set aller Städte. Einfach weil es einen Direktflug von einer Stadt in eine zweite Stadt gibt und ein Direktflug von der zweiten Stadt in die dritte nicht impliziert, dass es einen Direktflug von der ersten Stadt in die dritte gibt Die transitive Schließung dieser Beziehung ist eine andere Beziehung, nämlich "Es gibt eine Abfolge von Direktflügen, die in der Stadt beginnen x und endet in der Stadt y"Jede Beziehung kann auf ähnliche Weise wie eine transitive Beziehung erweitert werden.

Ein Beispiel für eine nicht-transitive Beziehung zu einem weniger bedeutungsvollen transitiven Verschluss ist "x ist der Wochentag nach y". Die transitive Schließung dieser Beziehung ist" eines Tages " x Kommt nach einem Tag y im Kalender ", was für alle Tage der Woche trivial zutrifft x und y (und damit äquivalent dem Kartesischer Platz, welches ist "x und y sind beide Wochentage ").

Existenz und Beschreibung

Für jede Beziehung R, die transitive Schließung von R Es existiert immer. Um dies zu sehen, beachten Sie, dass die Überschneidung von jedem Familie von transitiven Beziehungen ist wieder transitiv. Außerdem, Es gibt es mindestens eine transitive Beziehung, die enthält R, nämlich das triviale: X × X. Die transitive Schließung von R wird dann durch den Schnittpunkt aller transitiven Beziehungen angegeben, die enthalten R.

Bei endlichen Sätzen können wir die transitive Verschlussschritte Schritt für Schritt aus konstruieren R und Hinzufügen von transitiven Kanten. Dies gibt die Intuition für eine allgemeine Konstruktion. Für jeden Satz XWir können beweisen, dass der transsitive Verschluss durch den folgenden Ausdruck gegeben wird

${\ displayStyle r^{+} = \ bigcup _ {i = 1}^{\ infty} r^{i}.}$

wo ${\ displayStyle r^{i}}$ ist der i-Th Kraft von R, definiert induktiv durch

${\ displayStyle r^{1} = r}$

und für ${\displaystyle i>0}$Anwesend

${\ displayStyle r^{i+1} = r \ circ r^{i}}$

wo ${\ displayStyle \ circ}$ bezeichnet Zusammensetzung der Beziehungen.

Um zu zeigen, dass die obige Definition von R⁺ ist die am wenigsten transitive Beziehung, die enthält Rwir zeigen, dass es enthält R, dass es transitiv ist und dass es mit beiden Eigenschaften der kleinste Satz ist.

• ${\ displayStyle r \ subseteq r^{+}}$: ${\ displayStyle r^{+}}$ enthält alle alle ${\ displayStyle r^{i}}$so besonders ${\ displayStyle r^{+}}$ enthält ${\ displayStyle r}$.
• ${\ displayStyle r^{+}}$ ist transitiv: wenn ${\ displayStyle (s_ {1}, s_ {2}), (s_ {2}, s_ {3}) \ in r^{+}}$, dann ${\ displayStyle (s_ {1}, s_ {2}) \ in r^{j}}$ und ${\ displayStyle (s_ {2}, s_ {3}) \ in r^{k}}$ für einige ${\ displayStyle j, k}$ per Definition von ${\ displayStyle r^{+}}$. Da ist Komposition assoziativ, ${\ displaystyle r^{j+k} = r^{j} \ circ r^{k}}$; somit ${\ displayStyle (s_ {1}, s_ {3}) \ in r^{j+k} \ subseteq r^{+}}$ per Definition von ${\ displayStyle \ circ}$ und ${\ displayStyle r^{+}}$.
• ${\ displayStyle r^{+}}$ ist minimal, das heißt, wenn ${\ displayStyle t}$ ist eine transitive Beziehung, die enthält ${\ displayStyle r}$, dann ${\ displayStyle r^{+} \ subseteq t}$: Angesichts einer solchen ${\ displayStyle t}$, Induktion an ${\ displayStyle i}$ kann verwendet werden, um zu zeigen ${\ displayStyle r^{i} \ subseteq t}$ für alle ${\ displayStyle i}$ folgendermaßen: Base: ${\ displayStyle r^{1} = r \ subseteq t}$ durch Annahme. Schritt: Wenn ${\ displayStyle r^{i} \ subseteq t}$ hält und ${\ displayStyle (s_ {1}, s_ {3}) \ in r^{i+1} = r \ circ r^{i}}$, dann ${\ displayStyle (s_ {1}, s_ {2}) \ in r}$ und ${\ displayStyle (s_ {2}, s_ {3}) \ in r^{i}}$ für einige ${\ displayStyle s_ {2}}$per Definition von ${\ displayStyle \ circ}$. Somit, ${\ displayStyle (s_ {1}, s_ {2}), (s_ {2}, s_ {3}) \ in t}$ durch Annahme und durch Induktionshypothese. Somit ${\ displayStyle (s_ {1}, s_ {3}) \ in t}$ durch Transitivität von ${\ displayStyle t}$; Dies vervollständigt die Induktion. Endlich, ${\ displayStyle r^{i} \ subseteq t}$ für alle ${\ displayStyle i}$ impliziert ${\ displayStyle r^{+} \ subseteq t}$ per Definition von ${\ displayStyle r^{+}}$.

Eigenschaften

Das Überschneidung von zwei transitiven Beziehungen ist transitiv.

Das Union von zwei transitiven Beziehungen müssen nicht transitiv sein. Um die Transitivität zu bewahren, muss man den transitiven Verschluss einnehmen. Dies geschieht zum Beispiel bei der Einnahme der Vereinigung von zwei Äquivalenzbeziehungen oder zwei Vorbestellungen. Um eine neue Äquivalenzbeziehung oder eine neue Vorbestellung zu erhalten, muss man den transitiven Verschluss annehmen (Reflexivität und Symmetrie - im Fall von Äquivalenzbeziehungen - sind automatisch).

In der Graphentheorie

Transitiver Verschluss konstruiert den Ausgangsgraphen aus dem Eingangsgraphen.

Im InformatikDas Konzept des transitiven Verschlusss kann als Konstruktion einer Datenstruktur angesehen werden, die es ermöglicht, zu antworten Erreichbarkeit Fragen. Das heißt, kann man vom Knoten bekommen a zum Knoten d in einem oder mehreren Hopfen? Eine binäre Beziehung sagt Ihnen nur, dass der Knoten A mit dem Knoten verbunden ist bund dieser Knoten b ist mit dem Knoten verbunden cusw. nach dem transitiven Verschluss, wie in der folgenden Abbildung dargestellt, in einem O (1) Operation man kann diesen Knoten bestimmen d ist vom Knoten erreichbar a. Die Datenstruktur wird typischerweise als Matrix gespeichert. Wenn also Matrix [1] [4] = 1, dann ist es der Fall, dass Knoten 1 Knoten 4 durch einen oder mehrere Hopfen erreichen kann.

Die transitive Schließung der Adjazenzbeziehung von a Regie acyclische Graphen (DAG) ist die Erreichbarkeitsbeziehung der DAG und a strenge teilweise Ordnung.

A Cluster -Diagramm, die transitive Schließung eines ungerichteten Diagramms

Die transitive Schließung eines ungerichtete Grafik produziert a Cluster -Diagramm, a Union Union von Cliquen. Die Konstruktion des transitiven Verschlusses ist eine äquivalente Formulierung des Problems beim Auffinden der Komponenten der Grafik.^[1]

In logischer und rechnerischer Komplexität

Der transitive Verschluss einer binären Beziehung kann im Allgemeinen nicht in ausgedrückt werden in Logik erster Ordnung (Fo). Dies bedeutet, dass man eine Formel mit Prädikatsymbolen nicht schreiben kann R und T Das wird in einem Modell nur dann erfüllt, wenn und nur wenn T ist der transitive Verschluss von R. Im Finite -Modell -Theorie, Logik erster Ordnung (FO), die mit einem transitiven Verschlussbetreiber erweitert wurde, wird normalerweise aufgerufen Transitive Verschlusslogikund abgekürzt FO (TC) oder nur TC. TC ist ein Untertyp von Fixpoint -Logik. Die Tatsache, dass FO (TC) streng ausdrucksvoller ist als Fo Ronald Fagin 1974; Das Ergebnis wurde dann wieder entdeckt von Alfred Aho und Jeffrey Ullman 1979 schlug der vorschlug, Fixpoint -Logik als Datenbankabfragesprache.^[2] Mit neueren Konzepten der Finite-Model-Theorie beweist der Nachweis, dass FO (TC) streng ausdrucksstarker ist als FO unmittelbar der Tatsache, dass FO (TC) nicht Gaifman-Local ist.^[3]

Im Computerkomplexitätstheorie, das Komplexitätsklasse Nl entspricht genau dem Satz logischer Sätze, die in TC exprimierbar sind. Dies liegt daran NL-Complete Problem Stcon zur Findung gerichtete Wege in einer Grafik. Ebenso die Klasse L ist Logik erster Ordnung mit dem kommutativen transsitiven Verschluss. Wenn der transitive Abschluss hinzugefügt wird zu hinzugefügt zu Logik zweiter Ordnung Stattdessen erhalten wir PSPACE.

In Datenbank -Abfragesprachen

Seit den 1980er Jahren Oracle -Datenbank hat eine proprietäre Implementierung implementiert Sql Verlängerung Verbinden mit ... Beginnen Sie mit Dies ermöglicht die Berechnung eines transitiven Verschlusses als Teil einer deklarativen Abfrage. Das SQL 3 (1999) Standard fügte einen allgemeineren hinzu Mit rekursiv Das Konstrukt, das auch transsitive Verschluss in den Abfragsprozessor berechnet werden kann; Ab 2011 wird letzteres in umgesetzt IBM DB2, Microsoft SQL Server, Orakel, PostgreSQL, und Mysql (v8.0+).

Datenprotokoll Implementiert auch transitive Schließberechnungen.^[4]

Mariadb Implementiert rekursive gemeinsame Tabellenausdrücke, die zur Berechnung von transitiven Verschlüssen verwendet werden können. Diese Funktion wurde in Release 10.2.2 von April 2016 eingeführt.^[5]

Algorithmen

Effiziente Algorithmen zur Berechnung des transitiven Verschlusses der Adjazenzbeziehung eines Diagramms finden Sie in Nuutila (1995). Die Reduzierung des Problems mit Multiplikationen von Adjazenzmatrizen erreicht die geringste Zeitkomplexität, nämlich. das von Matrix-Multiplikation (Munro 1971, Fischer & Meyer 1971 Harvnb -Fehler: Kein Ziel: citereffischermeyer1971 (Hilfe)), welches ist ${\ displayStyle o (n^{2.3728596})}$ Ab Dezember 2020^{[aktualisieren]}. Dieser Ansatz ist jedoch nicht praktisch, da sowohl die konstanten Faktoren als auch der Gedächtnisverbrauch für spärliche Graphen hoch sind (hoch (Nuutila 1995, S. 22–23, Abschnitt.2.3.3). Das Problem kann auch von der gelöst werden Floyd -Warshall -Algorithmus, oder durch wiederholte Breite-First-Suche oder Tiefe-First-Suche Ausgehend von jedem Knoten des Diagramms.

Neuere Forschungen haben effiziente Möglichkeiten zur Berechnung des transsitiven Verschlusses auf verteilten Systemen basierend auf dem untersucht Karte verkleinern Paradigma.^[6]

Siehe auch

• Ahnenbeziehung
• Deduktiver Schließung
• Reflexive Abschluss
• Symmetrische Schließung
• Transitive Reduktion (eine kleinste Beziehung mit dem transitiven Verschluss von R als transsitiven Schließung)

Verweise

• Foto N. Afrati, Vinayak Borkar, Michael Carey, Neoklis Polyzotis, Jeffrey D. Ullman, Map-Reduce-Erweiterungen und rekursive Abfragen, EDBT 2011, 22. bis 24. März 2011, Uppsala, Schweden, ISBN978-1-4503-0528-0
• Aho, A. V.; Ullman, J. D. (1979). "Universalität der Datenabrufsprachen". Verfahren des 6. ACM Sigact -Sigplan -Symposiums über Prinzipien der Programmiersprachen - POPL '79. S. 110–119. doi:10.1145/567752.567763.
• Benedikt, M.; Senellart, P. (2011). "Datenbanken". In Blum, Edward K.; Aho, Alfred V. (Hrsg.). Informatik. Die Hardware, die Software und das Herz davon. S. 169–229. doi:10.1007/978-1-4614-1168-0_10. ISBN 978-1-4614-1167-3.
• Heinz-Dieter Ebbinghaus; Jörg Flum (1999). Finite -Modell -Theorie (2. Aufl.). Springer. pp.123–124, 151–161, 220–235. ISBN 978-3-540-28787-2.
• M. J. Fischer und A.R. Meyer (Oktober 1971). "Boolesche Matrix -Multiplikation und transitiver Verschluss" (PDF). In Raymond E. Miller und John E. Hopcroft (Hrsg.). Proc. 12. Ann. Symp. Zum Schalten und Automatentheorie (SWAT). IEEE Computer Society. S. 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). Finite -Modell -Theorie und ihre Anwendungen. Springer. S. 151–152. ISBN 978-3-540-68804-4.
• Keller, U., 2004, Einige Bemerkungen zur definierbaren Transitivverschluss in Logik erster Ordnung und Datalog (unveröffentlichtes Manuskript)* Libkin, Leonid (2004), Elemente der endlichen Modelltheorie, Springer, ISBN 978-3-540-21202-7
• Lidl, R.; Pilz, G. (1998), Angewandte abstrakte Algebra, Bachelortexte in Mathematik (2. Aufl.), Springer, ISBN 0-387-98290-6
• Munro, Ian (Januar 1971). "Effiziente Bestimmung des transitiven Verschlusses eines gerichteten Diagramms". Informationsverarbeitungsbriefe. 1 (2): 56–58. doi:10.1016/0020-0190 (71) 90006-8.
• Nuutila, Esko (1995). Effiziente Transitive -Schließberechnung in großen Digraphen. Finnische Akademie für Technologie. ISBN 951-666-451-2. OCLC 912471702.
• Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Datenbanksystemkonzepte (6. Aufl.). McGraw-Hill. ISBN 978-0-07-352332-3. Anhang C (nur online)

Externe Links

• "Transitivverschluss und Reduzierung", The Stony Brook Algorithmus Repository, Steven Skiena.