Транзитивно затворење

Za druge potrebe, pogledati Closure(disambiguation).

Ovaj članak govori o tranzitivnim završecima binarnih relacija. Za tranzitivne završetke skupa, pogledaj transitive set#Transitive closure.

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: ако је 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}\,\!$ sto znači da je tranzitivno. Dakle, po indukciji, $\displaystyle G$ sadrži svaki $R^{i}\,\!$, i takođe $\displaystyle R^{+}$.

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žnostii. 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 Fagin1974; rezultate su preispitali Alfred Aho i Jeffrey Ullman 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 Oracle Database je uveo 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, and 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 Floyd–Warshall-ov 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).

Pogledajte takođe

• Deductive closure
• Transitive reduction (najmanja relacija koja ima tranzitivan završetak u R kao svoj tranzitivan završetak)
• Symmetric closure
• Reflexive closure
• Ancestral relation

Reference

• Lidl, R. and Pilz, G., 1998, Applied abstract algebra, 2nd edition, Undergraduate Texts in Mathematics, Springer, ISBN 0-387-98290-6
• Keller, U., 2004, Some Remarks on the Definability of Transitive Closure in First-order Logic and Datalog (unpublished manuscript)
• Erich Grädel; Phokion G. Kolaitis; Leonid Libkin (2007). Finite Model Theory and Its Applications. Springer. стр. 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 (2nd изд.). Springer. стр. 123—124, 151—161, 220—235. ISBN 978-3-540-28787-2. 
• 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 951-666-451-2, ISSN 1237-2404, UDC 681.3.
• Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Database System Concepts (6th изд.). 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, ISBN 978-1-4503-0528-0

External links

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