Transitiv stängning

Den här artikeln handlar om den transitiva stängningen av en binär relation. För transitiv stängning av en uppsättning, se transitiv uppsättning § Transitiv stängning .

Inom matematiken är den transitiva stängningen av en binär relation R på en mängd X den minsta relationen på X som innehåller R och är transitiv . För ändliga mängder kan "minst" tas i sin vanliga betydelse, att ha minst relaterade par; för oändliga mängder är det den unika minimala transitiva supermängden av R .

Till exempel, om X är en uppsättning flygplatser och x R y betyder "det finns en direktflygning från flygplats x till flygplats y " (för x och y i X ), då är den transitiva stängningen av R på X relationen R ⁺ så att x R ⁺ y betyder "det är möjligt att flyga från x till y på en eller flera flygningar". Informellt ger den transitiva stängningen dig en uppsättning av alla platser du kan ta dig till från vilken startplats som helst.

Mer formellt är den transitiva stängningen av en binär relation R på en mängd X den transitiva relationen R ⁺ på mängden X så att R ⁺ innehåller R och R ⁺ är minimal; se Lidl & Pilz (1998 , s. 337). Om den binära relationen i sig är transitiv, så är den transitiva stängningen samma binära relation; annars är den transitiva stängningen ett annat förhållande.

Omvänt adderar transitiv reduktion en minimal relation S från en given relation R så att de har samma stängning, det vill säga S ⁺ = R ⁺ ; det kan dock finnas många olika S med denna egenskap.

Både transitiv stängning och transitiv reduktion används också inom det närbesläktade området grafteorin .

Transitiva relationer och exempel

En relation R på en mängd X är transitiv om, för alla x , y , z i X , närhelst x R y och y R z då x R z . Exempel på transitiva relationer inkluderar likhetsrelationen på vilken mängd som helst, relationen "mindre än eller lika" på vilken linjärt ordnad mängd som helst, och relationen " x föddes före y " på mängden av alla människor. Symboliskt kan detta betecknas som: om x < y och y < z då x < z .

Ett exempel på en icke-transitiv relation är "stad x kan nås via ett direktflyg från stad y " på uppsättningen av alla städer. Bara för att det finns ett direktflyg från en stad till en andra stad, och ett direktflyg från den andra staden till den tredje, betyder det inte att det finns ett direktflyg från den första staden till den tredje. Den transitiva stängningen av denna relation är en annan relation, nämligen "det finns en sekvens av direktflyg som börjar vid stad x och slutar vid stad y ". Varje relation kan utvidgas på liknande sätt till en transitiv relation.

Ett exempel på en icke-transitiv relation med en mindre meningsfull transitiv stängning är " x är veckodagen efter y ". Den transitiva stängningen av denna relation är "någon dag x kommer efter en dag y på kalendern", vilket är trivialt sant för alla dagar i veckan x och y (och därmed likvärdig med den kartesiska kvadraten , som är " x och y är båda dagarna i veckan").

Existens och beskrivning

För varje relation R existerar alltid den transitiva stängningen av R. För att se detta, notera att skärningspunkten mellan en familj av transitiva relationer återigen är transitiv. Vidare finns det åtminstone en transitiv relation som innehåller R , nämligen den triviala: X × X . Den transitiva stängningen av R ges då genom skärningspunkten mellan alla transitiva relationer som innehåller R .

För finita uppsättningar kan vi konstruera den transitiva stängningen steg för steg, med start från R och lägga till transitiva kanter. Detta ger intuitionen för en allmän konstruktion. För varje uppsättning X kan vi bevisa att transitiv stängning ges av följande uttryck

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

där $R^{i}$ är den i -te potensen av R , definierad induktivt av

$R^{1}=R$

och för $i>0$ ,

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

där $\circ$ anger sammansättning av relationer .

För att visa att ovanstående definition av R ⁺ är den minst transitiva relationen som innehåller R , visar vi att den innehåller R , att den är transitiv och att den är den minsta mängden med båda dessa egenskaper.

• $R\subseteq R^{+}$ : $R^{+}$ innehåller alla $R^{i}$ , så i synnerhet ${ \displaystyle R^{+}}$ innehåller $R$ .
• $R^{+}$ är transitiv: If $(s_{1},s_{2}),(s_ {2},s_{3})\in R^{+}$ , sedan $(s_{1},s_{2})\in R^{j}$ och $(s_{2},s_{3})\in R^{k}$ för vissa $j,k$ enligt definitionen av $R^{+}$ . Eftersom sammansättning är associativ, $R^{j+k}=R^{j}\circ R^{k}$ ; därav $(s_{1},s_{3})\in R^{j+k}\subseteq R^{+}$ enligt definition av $\circ$ och $R^{+}$ .
• $R^{+}$ är minimal, det vill säga om $T$ är någon transitiv relation som innehåller $R$ , då $R^{+}\ subseteq T$ : Givet någon sådan ${\displaystyle T} kan$ induktion på $i$ användas för att visa $subseteq T}$ \ för alla $i$ enligt följande: Bas: $R^{1}=R\subseteq T$ genom antagande. Steg: Om $R^{i}\subseteq T$ gäller, och ${\displaystyle (s_{1},s_{ 3})\in R^{i+1}=R\circ R^{i}} ,$ sedan $(s_{1},s_{2})\in R$ och $(s_{2},s_{3})\in R^{i}$ för vissa $s_{2}$ , per definition av $\circ$ . Därför, $(s_{1},s_{2}),(s_{2},s_{3})\in T$ av antagande och genom induktionshypotes. Därför $(s_{1},s_{3})\in T$ genom transitivitet av $T$ ; detta avslutar induktionen. Slutligen, $R^{i}\subseteq T$ för alla $i$ innebär $R^{+}\subseteq T$ per definition av ${\ displaystil R^{+}}$ .

Egenskaper

Skärningspunkten mellan två transitiva relationer är transitiv.

Föreningen av två transitiva relationer behöver inte vara transitiv . För att bevara transitiviteten måste man ta den transitiva stängningen. Detta inträffar till exempel när man tar föreningen av två ekvivalensrelationer eller två förbeställningar . För att erhålla en ny ekvivalensrelation eller förbeställning måste man ta den transitiva stängningen (reflexivitet och symmetri – i fallet med ekvivalensrelationer – är automatiska).

I grafteori

Transitiv stängning konstruerar utdatagrafen från ingångsgrafen.

Inom datavetenskap kan begreppet transitiv stängning ses som att konstruera en datastruktur som gör det möjligt att besvara nåbarhetsfrågor . Det vill säga kan man ta sig från nod a till nod d i ett eller flera hopp? En binär relation säger bara att nod a är ansluten till nod b och att nod b är ansluten till nod c etc. Efter att den transitiva stängningen är konstruerad, som visas i följande figur, kan man i en O(1) operation bestäm att nod d är nåbar från nod a . Datastrukturen lagras vanligtvis som en matris, så om matris[1][4] = 1, så är det så att nod 1 kan nå nod 4 genom ett eller flera hopp.

Den transitiva stängningen av närliggande relation till en riktad acyklisk graf (DAG) är nåbarhetsrelationen för DAG och en strikt partiell ordning .

En klustergraf , den transitiva stängningen av en oriktad graf

Den transitiva stängningen av en oriktad graf producerar en klustergraf , en osammanhängande förening av klickar . Att konstruera den transitiva stängningen är en likvärdig formulering av problemet med att hitta komponenterna i grafen.

I logik och beräkningskomplexitet

Den transitiva stängningen av en binär relation kan i allmänhet inte uttryckas i första ordningens logik (FO). Detta innebär att man inte kan skriva en formel med predikatsymbolerna R och T som kommer att uppfyllas i vilken modell som helst om och endast om T är den transitiva stängningen av R . I finita modellteori kallas första ordningens logik (FO) utökad med en transitiv stängningsoperator vanligtvis transitiv stängningslogik och förkortas FO(TC) eller bara TC. TC är en undertyp av fixpoint-logik . Det faktum att FO(TC) är strikt mer uttrycksfull än FO upptäcktes av Ronald Fagin 1974; resultatet återupptäcktes sedan av Alfred Aho och Jeffrey Ullman 1979, som föreslog att använda fixpoint-logik som ett databasfrågespråk . Med nyare begrepp inom finita modellteori följer bevis på att FO(TC) är strikt mer uttrycksfull än FO omedelbart av det faktum att FO(TC) inte är Gaifman-lokal.

I beräkningskomplexitetsteori motsvarar komplexitetsklassen NL exakt den uppsättning logiska meningar som kan uttryckas i TC . Detta beror på att den transitiva stängningsegenskapen har ett nära samband med det NL-kompletta problemet STCON för att hitta riktade vägar i en graf. På liknande sätt är klassen L första ordningens logik med den kommutativa, transitiva stängningen. När transitiv stängning läggs till i andra ordningens logik istället får vi PSPACE .

I databasfrågespråk

Ytterligare information: Hierarkiska och rekursiva frågor i SQL

Sedan 1980-talet har Oracle Database implementerat en egenutvecklad SQL- tillägg CONNECT BY... START WITH som tillåter beräkning av en transitiv stängning som en del av en deklarativ fråga. SQL 3 (1999)-standarden lade till en mer allmän WITH RECURSIVE- konstruktion som också tillåter att transitiva stängningar kan beräknas inuti frågeprocessorn; från och med 2011 är det senare implementerat i IBM Db2 , Microsoft SQL Server , Oracle , PostgreSQL och MySQL (v8.0+). SQLite släppte stöd för detta 2014.

Datalog implementerar också transitiva stängningsberäkningar.

MariaDB implementerar Rekursiva Common Table Expressions, som kan användas för att beräkna transitiva stängningar. Den här funktionen introducerades i version 10.2.2 från april 2016.

Algoritmer

Effektiva algoritmer för att beräkna den transitiva stängningen av närliggande relation till en graf kan hittas i Nuutila (1995) . Att reducera problemet till multiplikationer av närliggande matriser uppnår den minsta tidskomplexiteten, dvs. det för matrismultiplikation ( Munro 1971 , Fischer & Meyer 1971 ), som är $O(n^{2.3728596})$ per 202 december. detta tillvägagångssätt är inte praktiskt eftersom både de konstanta faktorerna och minnesförbrukningen för glesa grafer är hög ( Nutila 1995 , s. 22–23, avsnitt 2.3.3). Problemet kan också lösas med Floyd–Warshall-algoritmen i ${\displaystyle O(n^{3})} ,$ eller genom upprepad sökning med bredd-först eller djup-först sökning med början från varje nod i grafen .

För riktade grafer löser Purdoms algoritm problemet genom att först beräkna dess kondensations-DAG och dess transitiva stängning, och sedan lyfta den till den ursprungliga grafen. Dess körtid är $O(m+\mu n)$ , där $\mu$ är antalet kanter mellan dess starkt anslutna komponenter .

Nyare forskning har utforskat effektiva sätt att beräkna transitiv stängning på distribuerade system baserat på MapReduce- paradigmet.

Se även

• Anfäders relation
• Deduktiv stängning
• Reflexstängning
• Symmetrisk stängning
• Transitiv reduktion (en minsta relation som har den transitiva stängningen av R som sin transitiva stängning)

•   Foto N. Afrati, Vinayak Borkar, Michael Carey, Neoklis Polyzotis, Jeffrey D. Ullman, Map-Reduce Extensions and Recursive Queries , EDBT 2011, 22–24 mars 2011, Uppsala, Sverige, ISBN 978-1-4503-0528 0
• Aho, AV; Ullman, JD (1979). "Universalitet av dataåtervinningsspråk". Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of programmeing languages ​​- POPL '79 . s. 110–119. doi : 10.1145/567752.567763 .
•   Benedikt, M.; Senellart, P. (2011). "Databaser". I Blum, Edward K.; Aho, Alfred V. (red.). Datavetenskap. Hårdvaran, programvaran och hjärtat av det . 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 Model Theory (2:a upplagan). Springer. s. 123 –124, 151–161, 220–235. ISBN 978-3-540-28787-2 .
• MJ Fischer och AR Meyer (okt 1971). "Boolesk matrismultiplikation och transitiv stängning" (PDF) . I Raymond E. Miller och John E. Hopcroft (red.). Proc. 12:e Ann. Symp. om växlings- och automatteori (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). Finita modellteori och dess tillämpningar . Springer. s. 151–152. ISBN 978-3-540-68804-4 .
• Keller, U., 2004, Några anmärkningar om definierbarheten av transitiv stängning i första ordningens logik och datalog (opublicerat manuskript)*   Libkin, Leonid (2004), Elements of Finite Model Theory , Springer, ISBN 978-3-540-21202 -7
•   Lidl, R.; Pilz, G. (1998), Tillämpad abstrakt algebra , Grundutbildningstexter i matematik (2:a upplagan), Springer, ISBN 0-387-98290-6
• Munro, Ian (januari 1971). "Effektiv bestämning av den transitiva stängningen av en riktad graf". Informationsbehandlingsbrev . 1 (2): 56–58. doi : 10.1016/0020-0190(71)90006-8 .
•    Nuutila, Esko (1995). Effektiv transitiv stängningsberäkning i stora digrafer . Finlands Tekniska Akademi. ISBN 951-666-451-2 . OCLC 912471702 .
•   Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Databassystemkoncept (6:e upplagan). McGraw-Hill. ISBN 978-0-07-352332-3 . Bilaga C (endast online)

externa länkar

• " Transitiv stängning och minskning ", The Stony Brook Algorithm Repository, Steven Skiena.