Tranzitivno zatvorenje

Ukoliko ste tražili tranzitivno zatvorenje skupa, pogledajte članak tranzitivni skup.

U matematici, tranzitivni završetak binarnih relacija R u skupu X je tranzitivna relacija R⁺ u skupu X tako da je R⁺ koji sadrži R i R⁺ minimalan (Lidl i Pilc 1998:337). Ako je sama binarna relacija tranzitivna, onda je tranzitivni završetak ta ista binarna relacija; u suprotnom, tranzitivni završetak je različita relacija. Na primer, ako je X skup aerodroma a x R y znači: postoji direktan let od aerodroma x do aerodroma y, onda je tranzitivni završetak R na X relacija R⁺: moguće je leteti od x do y jednim ili više letova.

Tranzitivni odnosi i primeri

Relacija R u skupu X je tranzitivna ako je za svako x,y,z iz X, kad god je x R y i y R z, onda je y R z. Primeri tranzitivnih relacija obuhvataju relaciju jednakost u svakom skupu, „manje od ili jednako” relacije u bilo kom linerano uređenom skupu, i relacija „x je rođen pre y” u skupu svih ljudi. Simbolično, ovo se može označiti kao: ako je x < y i y < z onda je x < z.

Jedan od primera neprelazne relacije je „u grad x može se stići direktnim letom iz grada y”, u skupu svih gradova. Jednostavno, zato što postoji direktan let od jednog do drugog grada, direktan let od drugog do trećeg grada, ne znači da postoji direktan let od prvog do trećeg grada. Tranzitivni završetak ove relacije je drugačija relacija, odnosno „postoji sekvenca direktnih letova koji počinju u gradu x a završavaju u gradi y”. Svaka relacija se može produžiti na sličan način u tranzitivnu relaciju.

Postojanje i opis

Za bilo koju relaciju R, tranzitivni završetak R uvek postoji. Da biste videli ovo, zapazite da je presek svake porodice tranzitivnih relacija, ponovo tranzitivna. Osim toga, postoji najmanje jedna tranzitivna relacija koja sadrži R, naime jedana trivijalna: X × X. Tranzitivni završetak R je tada dat kao presek svih tranzitivnih završetaka sadržajnog R.

Za završne skupove, možemo konstruisati prelazni završetak korak po korak od R i dodajući tranzitivne grane. Ovo pruža saznanje za opštu konstrukciju. Za neki skup X, možemo dokazati da je tranzitivni završetak dat pomoću sledećeg izraza

$R^{+}=\bigcup _{i\in \{1,2,3,\ldots \}}R^{i}.$

gde je $R^{i}$ i-ti stepen R, definisan induktivno

$R^{1}=R\,\!$

i, za $i>0$,

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

gde $\circ$ označava kompoziciju relacija.

Da bi pokazali da je gornja definicija R⁺ najmanja tranzitivna relacija sadržajnog R, pokazujemo da ona sadrži R, da je tranzitivna, i da je najmanji skup sa obe ove karakteristike.

• $R\subseteq R^{+}$: $\displaystyle R^{+}$ sadrži sve iz $\displaystyle R^{i}$, tako da $\displaystyle R^{+}$ sadrži $\displaystyle R$.
• $\displaystyle R^{+}$ je tranzitivno: svaki element iz $\displaystyle R^{+}$ je u jednom od $\displaystyle R^{i}$, tako da $\displaystyle R^{+}$ mora biti tranzitivno zbog sledećeg zaključka: ako je $(s_{1},s_{2})\in R^{j}$ i $(s_{2},s_{3})\in R^{k}$, onda iz kompozicija asocijativnosti, $(s_{1},s_{3})\in R^{j+k}$ (i na taj način u $\displaystyle R^{+}$) zbog definicije $\displaystyle R^{i}$.
• $\displaystyle R^{+}$ je minimalan: Neka $\displaystyle G$ bude bilo koja tranzitivna relacija koja sadrži $\displaystyle R$, želimo da pokažemo da $R^{+}\subseteq G$. Dovoljno je da pokazemo da za svako $i>0$, $R^{i}\subseteq G$. Dakle, pošto $\displaystyle G$ sadrži $\displaystyle R$, $R^{1}\subseteq G$. I opšto je $\displaystyle G$ tranzitivno, kadgod je $R^{i}\subseteq G$, $R^{i+1}\subseteq G$ prema konstrukciji $R^{i}\,\!$ što znači da je tranzitivno. Dakle, po indukciji, $\displaystyle G$ sadrži svaki $R^{i}\,\!$, i takođe $\displaystyle R^{+}$.

Dokaz da je T najmanja tranzitivna relacija koja sadrži R

Neka je A proizvoljan skup elemenata.

Pretpostavka: G_A tranzitivna relacija R_AG_A T_AG_A. Sledi (a,b)G_A(a,b)T_A. Sledi posebno (a,b)R_A .

Sada, prema definiciji relacije T, znamo da n (a,b)$R^{n}$_A. Zatim, i ,i < n e_i A. Dakle, postoji put od a do b, to je: aR_Ae₁R_A...R_Ae_(n-1)R_Ab.

Ali, zbog tranzitivnosti G_A na R_A, i, i < n (a,e_i)G_A, pa je (a,e_(n-1))G_A (e_(n-1),b)G_A, pa zbog tranzitivnosti G_A, dobijamo (a,b)G_A. Ovo je kontradikcija sa (a,b)G_A.

Zbog toga, (a,b)AA, (a,b)T_A (a,b)G_A. Ovo znači da je TG, za bilo koju tranzitivnu G koja sadrži R. Dakle, T je najmanja tranzitivna relacija koja sadrži R.

Posledica

Ako je R tranzitivna, onda R = T.

Karakteristike

Unija dve tranzitivne relacije ne mora da bude tranzitivna. Da bi se sačuvala tranzitivnost, jedan mora preuzeti tranzitivni završetak. Ovo se dešava, na primer, kada se uzme unija dve iste relacije ili dva „preordera”. Za dobijanje nove relacije ekvivalencije ili „preordera”, jedan mora preuzeti tranzitivan završetak (refleksivnost i simetrija - u slučaju relacije ekvivalencije - su automatski).

U teoriji grafova

Tranzitivni završeci konstruisu izlazni graf od ulaznog grafa.

U računarstvu, koncept tranzitivnog završetka može se smatrati kao konstruisanje struktura podataka koje omogućavaju da se odgovori na pitanja dosežnosti. To je, može li se dobiti od čvora a do čvora d jedan ili više puteva? Binarna relacija govori samo da je čvor a povezan sa čvorom b, i da je čvor b povezan sa čvorom c, i tako dalje. Nakon što je tranzitivni završetak obrazovan, kao što je predstavljeno na slici, u O(1) operaciji može se odrediti da je čvor d dostupan iz čvora a. Strukture podataka se obično čuvaju kao matrice, tako da ako je matrica[1][4] = 1 onda je to slučaj kada se iz čvora 1 može doći do čvora 4 jednim ili pomoću više puteva.

Tranzitivni završetak direktnih acikličnih grafova (DAG) je dostižana relacija DAG-a i strogo parcijalnih uređenja.

U logičkoj i računarskoj složenosti

U teoriji konačnih modela, logika prvog reda (FO) proširena operacijom tranzitivnog završetka obično se zove logika tranzitivnog završetka, i skraćuje se FO (TC) ili samo TC. TC je podtip logičke fikspoint logike. Činjenica da je FO (TC) strogo mnogo izraženiji nego FO, otkrio je Ronald Fagin 1974; rezultate su preispitali Alfred Aho i Džefri Ulman 1979, koji su predložili da se fikspoint logika upotrebljava kao jezička baza upita. (Libkin 2004:vii) Sa novijim konceptima teorija konačnih modela, dokazuje se da je FO (TC) strogo izraženiji nego FO koji sledi neposredno iz činjenice da FO (TC) nije Gaifman-local (Libkin 2004:49).

U složenoj računarskoj teoriji, kompleksnost klase NL odgovara tačno skupu logičkih izraza izraženih u TC. To je zato što svojstvo tranzitivnog završetka ima blizak odnos sa NL-kompletnim problemom STCON za nalaženje usmerenih putanja u grafu. Slično klasa L je logika prvog reda sa komutativnim, tranzitivnim završecima. Kad se tranzitivni završetak doda umesto logike drugog reda, dobijamo PSPACE.

U bazama jezika upita

Dodatne informacije: Hijerarhijski i rekurzivni upiti u SQL-u.

Još od 1980—ih godine Orakl baza podataka je uvela privatni SQL proširen sa CONNECT BY... START WITH, koji omogućava računanje tranzitivnih završetaka kao delova deklarativnih upita. SQL 3 (1999) standard je više opštiji standard, sa REKURZIVNIM spojem koji omogućava tranzitivnim završecima da budu izračunati unutar upita procesora; od 2011, ovaj poslednji se implementira u IBM DB2, Microsoft SQL Server, i PostgreSQL, ali ne u MySQL (Benedikt and Senellart 2011:189).

Algoritmi

Efikasni algoritmi za izračunavanje tranzitivnog završetka grafa može se naći u Nuutila (1995). Najjednostavnija tehnika je verovatno Flojd–Varšalov algoritam. Najbrži, metod najgoreg slučaja, koja nije praktičan, smanjuje problem na množenja matrica. Skorija istraživanja su pokazala efikasne načine izračunavanja tranzitivnih završetka na podeljenim sistemima zasnovanim na MapReduce paradigmama (Afrati et al. 2011).

Vidi još

• Deduktivno zatvorenje
• Tranzitivna redukcija (najmanja relacija koja ima tranzitivan završetak u R kao svoj tranzitivan završetak)
• Simetrično zatvorenje
• Refleksivno zatvorenje
• Ancestralni odnos

Literatura

• Lidl, R. and Pilz, G., 1998. Applied abstract algebra, 2nd edition, Undergraduate Texts in Mathematics. . Springer. ISBN 978-0-387-98290-8. 
• Keller, U., 2004, „Some Remarks on the Definability of Transitive Closure in First-order Logic and Datalog”. CiteSeerX 10.1.1.127.8266 .  (unpublished manuscript)
• Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid (2007). Finite Model Theory and Its Applications. Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, Scott Weinstein. Springer. str. 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; Flum, Jörg (1999). Finite Model Theory (2nd izd.). Springer. str. 123-124,151-161,220–235. ISBN 978-3-540-28787-2. 
• Aho, Alfred V.; Ullman, Jeffrey D. (1979). „Universality of data retrieval languages”. Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '79. str. 110—119. S2CID 3242505. doi:10.1145/567752.567763. 
• Benedikt, Michael; Senellart, Pierre (2011). „Databases”. Computer Science. str. 169—229. ISBN 978-1-4614-1167-3. doi:10.1007/978-1-4614-1168-0_10. 
• Nuutila, E., Efficient Transitive Closure Computation in Large Digraphs. Acta Polytechnica Scandinavica, Mathematics and Computing in Engineering Series No. 74, Helsinki 1995, 124 pages. Published by the Finnish Academy of Technology. . ISBN 978-951-666-451-7.  ISSN 1237-2404, UDC 681.3.
• Silberschatz, Abraham; Korth, Henry; S. Sudarshan (2010). Database System Concepts (6th izd.). McGraw-Hill. ISBN 978-0-07-352332-3.  Appendix C (online only)
• Foto N. Afrati, Vinayak Borkar, Michael Carey, Neoklis Polyzotis, Jeffrey D. Ullman, Map-Reduce Extensions and Recursive Queries, EDBT 2011, March 22–24, 2011, Uppsala, Sweden. Ailamaki, Anastasia (2011). Proceedings of the 14th International Conference on Extending Database Technology. Association for Computing Machinery. ISBN 978-1-4503-0528-0. 

Spoljašnje veze

• "Transitive closure and reduction", The Stony Brook Algorithm Repository, Steven Skiena .