Transitiv stängning - Transitive closure

I matematik är den transitiva stängningen av en binär relation R på en uppsättning X den minsta relationen på X som innehåller R och är övergående . För ändliga uppsättningar kan "minsta" tas i sin vanliga bemärkelse, att ha minst par relaterade par; för oändliga mängder är det den unika minimal transitiv superset av R .

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

Mer formellt är den transitiva förslutningen av en binär relation R på en uppsättning X den transitiva relationen R ⁺ på uppsättning X så att R ⁺ innehåller R och R ⁺ är minimal Lidl & Pilz (1998 , s. 337). Om den binära relationen i sig är transitiv, är den transitiva förslutningen samma binära relation; annars är den transitiva stängningen en annan relation.

Omvänt åstadkommer transitiv reduktion en minimal relation S från en given relation R så att de har samma förslutning, det vill säga S ⁺ = R ⁺ ; dock kan många olika S med denna egenskap existera.

Både transitiv stängning och transitiv reduktion används också i det nära besläktade området grafteori .

Transitiva relationer och exempel

En relation R på en uppsättning X är övergående 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 jämställdhetsrelationen på vilken uppsättning som helst, "mindre än eller lika" förhållandet för alla linjärt ordnade uppsättningar och förhållandet " x föddes före y " på uppsättningen för 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 en direktflygning från stad y " på uppsättningen av alla städer. Helt enkelt för att det finns en direktflygning från en stad till en andra stad och en direktflygning från den andra staden till den tredje innebär det inte att det finns en direktflygning 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å ett 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 i kalendern", vilket är triviellt sant för alla dagar i veckan x och y (och därmed motsvarar det kartesiska torget , vilket är " x och y är båda veckodagarna ").

Existens och beskrivning

För alla förhållanden R existerar alltid den transitiva förslutningen av R. För att se detta, notera att skärningspunkten mellan alla familjer av transitiva relationer återigen är transitive. Vidare finns det åtminstone en transitiv relation innehållande R , nämligen den triviala ett: X × X . Den transitiva stängningen av R ges då av skärningen mellan alla transitiva relationer som innehåller R .

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

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

var är den i- kraften av R , definierad induktivt av ${\ displaystyle R ^ {i}}$

{\ displaystyle R ^ {1} = R}

och, för , ${\ displaystyle i> 0}$

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

där betecknar sammansättningen av relationer . ${\ displaystyle \ circ}$

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 uppsättningen med båda dessa egenskaper.

${\ displaystyle R \ subseteq R ^ {+}}$ : innehåller alla , så innehåller särskilt . ${\ displaystyle R ^ {+}}$ ${\ displaystyle R ^ {i}}$ ${\ displaystyle R ^ {+}}$ ${\ displaystyle R}$
${\ displaystyle R ^ {+}}$ är övergående: Om , då och för vissa per definition av . Eftersom kompositionen är associativt, ; därav per definition av och . ${\ displaystyle (s_ {1}, s_ {2}), (s_ {2}, s_ {3}) \ i R ^ {+}}$ ${\ displaystyle (s_ {1}, s_ {2}) \ i R ^ {j}}$ ${\ displaystyle (s_ {2}, s_ {3}) \ i R ^ {k}}$ ${\ displaystyle j, k}$ ${\ displaystyle R ^ {+}}$ ${\ displaystyle R ^ {j + k} = R ^ {j} \ circ R ^ {k}}$ ${\ displaystyle (s_ {1}, s_ {3}) \ i R ^ {j + k} \ subseteq R ^ {+}}$ ${\ displaystyle \ circ}$ ${\ displaystyle R ^ {+}}$
${\ displaystyle R ^ {+}}$ är minimal, det vill säga om någon övergångsrelation innehåller , då : Med tanke på något sådant kan induktion på användas för att visa för alla enligt följande: Bas: genom antagande. Steg: Om innehav, och , då och för vissa , per definition . Därför genom antagande och genom induktionshypotes. Därav genom transitivitet av ; detta fullbordar induktionen. Slutligen, för alla innebär per definition av . ${\ 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}) \ i R ^ {i + 1} = R \ circ R ^ {i}}$ ${\ displaystyle (s_ {1}, s_ {2}) \ i R}$ ${\ displaystyle (s_ {2}, s_ {3}) \ i R ^ {i}}$ ${\ displaystyle s_ {2}}$ ${\ displaystyle \ circ}$ ${\ displaystyle (s_ {1}, s_ {2}), (s_ {2}, s_ {3}) \ in T}$ ${\ displaystyle (s_ {1}, s_ {3}) \ i T}$ ${\ displaystyle T}$ ${\ displaystyle R ^ {i} \ subseteq T}$ ${\ displaystyle i}$ ${\ displaystyle R ^ {+} \ subseteq T}$ ${\ displaystyle R ^ {+}}$

Egenskaper

Den korsningen av två transitiva relationer är transitiv.

Den union av två transitiva relationer behöver inte vara transitive. För att bevara transitiviteten måste man ta övergångsstängningen. Detta inträffar till exempel när man tar samman två likvärdighetsrelationer 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 utgångsdiagrammet från inmatningsdiagrammet.

Inom datavetenskap kan begreppet transitiv stängning ses som att konstruera en datastruktur som gör det möjligt att svara på frågor om tillgänglighet . Det vill säga kan man komma från nod a till nod d i en eller flera humle? 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 förslutningen har konstruerats, som avbildad i följande figur, kan man i en O (1) -operation bestäm att nod d kan nås från nod a . Datastrukturen lagras vanligtvis som en matris, så om matris [1] [4] = 1 är det så att nod 1 kan nå nod 4 genom en eller flera humle.

Den transitiva stängningen av angränsningsförhållandet för en riktad acyklisk graf (DAG) är DAGs tillgänglighetsförhållande och en strikt partiell ordning .

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 användning av predikat symbolerna R och T som kommer att uppfyllas av någon modell om och endast om T är den transitiva stängningen av R . I en ändlig modellteori kallas första ordningslogiken (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 fixpoint-logik skulle användas som databasfrågespråk . Med nyare begrepp för ändlig modellteori följer beviset på att FO (TC) är strikt mer uttrycksfull än FO omedelbart från det faktum att FO (TC) inte är Gaifman-lokal .

I beräkningskomplexitet teori , den komplexitetsklassen NL motsvarar exakt den uppsättning logiska meningar som kan uttryckas i TC. Detta beror på att den transitiva stängningsegenskapen har en nära relation med NL-komplett problem STCON för att hitta riktade banor i en graf. På samma sätt är klass L första ordningslogik med den kommutativa, transitiva stängningen. När transitiv stängning läggs till andra ordningens logik istället får vi PSPACE .

I databasfrågespråk

Sedan 1980-talet har Oracle Database implementerat en egen SQL- förlängning CONNECT BY... START WITHsom möjliggör beräkning av en transitiv stängning som en del av en deklarativ fråga. Den SQL 3 (1999) standard sattes en mer allmän WITH RECURSIVEkonstruktion som den tillåter transitiva förslutningar som skall beräknas inuti frågeprocessor; Från och med 2011 implementeras den senare i IBM DB2 , Microsoft SQL Server , Oracle och PostgreSQL , men inte i MySQL .

Datalog implementerar också beräkningar för transitiv stängning.

MariaDB implementerar rekursiva gemensamma tabelluttryck, som kan användas för att beräkna transitiva stängningar. Denna funktion introducerades i release 10.2.2 från april 2016.

Algoritmer

Effektiva algoritmer för att beräkna den transitiva stängningen av angränsningsförhållandet för en graf finns i Nuutila (1995). De snabbaste värsta fallmetoderna, som inte är praktiska, reducerar problemet till matrixmultiplikation . Problemet kan också lösas med Floyd-Warshall-algoritmen eller genom upprepad bredd-första-sökning eller djup-första-sökning som börjar från varje nod i diagrammet.

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

Se även

Släktskapsförhållande
Deduktiv stängning
Reflexiv förslutning
Symmetrisk stängning
Transitiv reduktion (en minsta relation med den transitiva tillslutningen av R som dess transitive tillslutning)

Referenser

Lidl, R .; Pilz, G. (1998),Tillämpad abstrakt algebra, Undergraduate Texts in Mathematics (2nd ed.), Springer, ISBN 0-387-98290-6
Keller, U., 2004, Några anmärkningar om definitionen av transitiv stängning i första ordningens logik och datalog (opublicerat manuskript)
Erich Grädel; Phokion G. Kolaitis; Leonid Libkin; Maarten Marx; Joel Spencer; Moshe Y. Vardi; Yde Venema; Scott Weinstein (2007). Ändlig modellteori och dess tillämpningar . Springer. s. 151–152. ISBN 978-3-540-68804-4.
Libkin, Leonid (2004), Elements of Finite Model Theory , Springer, ISBN 978-3-540-21202-7
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.
Aho, AV; Ullman, JD (1979). Msgstr "Universitet för datainsamlingsspråk". Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of programming 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.
Nuutila, E., Effektiv transitiv stängningsberäkning i stora grafer. Acta Polytechnica Scandinavica, Matematik och databehandling i ingenjörsserie nr 74, Helsingfors 1995, 124 sidor. Publicerad av Finlands tekniska akademi. ISBN 951-666-451-2 , ISSN 1237-2404 , UDC 681.3.
Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Database System Concepts (6: e upplagan). McGraw-Hill. ISBN 978-0-07-352332-3. Bilaga C (endast online)
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

externa länkar

" Transitive closure and reduction ", The Stony Brook Algorithm Repository, Steven Skiena.
" Apti Algoritmi ", ett exempel och några C ++ - implementeringar av algoritmer som beräknar den transitiva stängningen av en given binär relation, Vreda Pieterse.

Languages

In other projects