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

У математици, транзитивни завршетак бинарних релација R у скупу X је транзитивна релација R⁺ у скупу X тако да је R⁺ који садржи R и R⁺ минималан (Lidl i Pilc 1998:337). Ако је сама бинарна релација транзитивна, онда је транзитивни завршетак та иста бинарна релација; у супротном, транзитивни завршетак је различита релација. На пример, ако је X скуп аеродрома а x R y значи: постоји директан лет од аеродрома x до аеродрома y, онда је транзитивни завршетак R на X релација R⁺: могуће је летети од x до y једним или више летова.

Транзитивни односи и примери

Релација R у скупу X је транзитивна ако је за свако x,y,z из X, кад год је x R y и y R z, онда је y R z. Примери транзитивних релација обухватају релацију једнакост у сваком скупу, „мање од или једнако” релације у било ком линерано уређеном скупу, и релација „x је рођен пре y” у скупу свих људи. Симболично, ово се може означити као: ако је x < y и y < z онда је x < z.

Један од примера непрелазне релације је „у град x може се стићи директним летом из града y”, у скупу свих градова. Једноставно, зато што постоји директан лет од једног до другог града, директан лет од другог до трећег града, не значи да постоји директан лет од првог до трећег града. Транзитивни завршетак ове релације је другачија релација, односно „постоји секвенца директних летова који почињу у граду x а завршавају у гради y”. Свака релација се може продужити на сличан начин у транзитивну релацију.

Постојање и опис

За било коју релацију R, транзитивни завршетак R увек постоји. Да бисте видели ово, запазите да је пресек сваке породице транзитивних релација, поново транзитивна. Осим тога, постоји најмање једна транзитивна релација која садржи R, наиме једана тривијална: X &тимес; X. Транзитивни завршетак R је тада дат као пресек свих транзитивних завршетака садржајног R.

За завршне скупове, можемо конструисати прелазни завршетак корак по корак од R и додајући транзитивне гране. Ово пружа сазнање за општу конструкцију. За неки скуп X, можемо доказати да је транзитивни завршетак дат помоћу следећег израза

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

где је $R^{i}$ i-ти степен R, дефинисан индуктивно

R^{1}=R\,\!

и, за $i>0$ ,

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

где $\circ$ означава композицију релација.

Да би показали да је горња дефиниција R⁺ најмања транзитивна релација садржајног R, показујемо да она садржи R, да је транзитивна, и да је најмањи скуп са обе ове карактеристике.

$R\subseteq R^{+}$ : $\displaystyle R^{+}$ садржи све из $\displaystyle R^{i}$ , тако да $\displaystyle R^{+}$ садржи $\displaystyle R$ .
$\displaystyle R^{+}$ је транзитивно: сваки елемент из $\displaystyle R^{+}$ је у једном од $\displaystyle R^{i}$ , тако да $\displaystyle R^{+}$ мора бити транзитивно због следећег закључка: ако је $(s_{1},s_{2})\in R^{j}$ и $(s_{2},s_{3})\in R^{k}$ , онда из композиција асоцијативности, $(s_{1},s_{3})\in R^{j+k}$ (и на тај начин у $\displaystyle R^{+}$ ) због дефиниције $\displaystyle R^{i}$ .
$\displaystyle R^{+}$ је минималан: Нека $\displaystyle G$ буде било која транзитивна релација која садржи $\displaystyle R$ , желимо да покажемо да $R^{+}\subseteq G$ . Довољно је да показемо да за свако $i>0$ , $R^{i}\subseteq G$ . Дакле, пошто $\displaystyle G$ садржи $\displaystyle R$ , $R^{1}\subseteq G$ . И општо је $\displaystyle G$ транзитивно, кадгод је $R^{i}\subseteq G$ , $R^{i+1}\subseteq G$ према конструкцији $R^{i}\,\!$ што значи да је транзитивно. Дакле, по индукцији, $\displaystyle G$ sadrži svaki $R^{i}\,\!$ , и такође $\displaystyle R^{+}$ .

Доказ да је Т најмања транзитивна релација која садржи R

Нека је А произвољан скуп елемената.

Претпоставка: G_A транзитивна релација R_AG_A T_AG_A. Следи (a,b)G_A(a,b)T_A. Следи посебно (a,b)R_A .

Сада, према дефиницији релације Т, знамо да n (a,b) $R^{n}$ _A. Затим, i ,i < n e_i А. Дакле, постоји пут од a до b, то је: aR_Ae₁R_A...R_Ae_(n-1)R_Ab.

Али, због транзитивности G_A на R_A, i, i < n (a,e_i)G_A, па је (a,e_(n-1))G_A (e_(n-1),b)G_A, па због транзитивности G_A, добијамо (a,b)G_A. Ово је контрадикција са (a,b)G_A.

Због тога, (a,b)AA, (a,b)T_A (a,b)G_A. Ово значи да је TG, за било коју транзитивну G која садржи R. Дакле, Т је најмања транзитивна релација која садржи R.

Последица

Ako je R транзитивна, онда R = T.

Карактеристике

Унија две транзитивне релације не мора да буде транзитивна. Да би се сачувала транзитивност, један мора преузети транзитивни завршетак. Ово се дешава, на пример, када се узме унија две исте релације или два „преордера”. За добијање нове релације еквиваленције или „преордера”, један мора преузети транзитиван завршетак (рефлексивност и симетрија - у случају релације еквиваленције - су аутоматски).

У теорији графова

Транзитивни завршеци конструису излазни граф од улазног графа.

У рачунарству, концепт транзитивног завршетка може се сматрати као конструисање структура података које омогућавају да се одговори на питања досежности. То је, може ли се добити од чвора a до чвора d један или више путева? Бинарна релација говори само да је чвор a повезан са чвором b, и да је чвор b повезан са чвором c, и тако даље. Након што је транзитивни завршетак образован, као што је представљено на слици, у O(1) операцији може се одредити да је чвор d доступан из чвора a. Структуре података се обично чувају као матрице, тако да ако је матрица[1][4] = 1 онда је то случај када се из чвора 1 може доћи до чвора 4 једним или помоћу више путева.

Транзитивни завршетак директних ацикличних графова (DAG) је достижана релација DAG-а и строго парцијалних уређења.

У логичкој и рачунарској сложености

U теорији коначних модела, логика првог реда (FO) проширена операцијом транзитивног завршетка обично се зове логика транзитивног завршетка, и скраћује се FO (TC) или само TC. TC је подтип логичке фикспоинт логике. Чињеница да је FO (TC) строго много израженији него FO, открио је Роналд Фагин 1974; резултате су преиспитали Алфред Ахо и Џефри Улман 1979, који су предложили да се фикспоинт логика употребљава као језичка база упита. (Libkin 2004:vii) Са новијим концептима теорија коначних модела, доказује се да је FO (TC) строго израженији него FO који следи непосредно из чињенице да FO (TC) није Gaifman-лоцал (Libkin 2004:49).

У сложеној рачунарској теорији, комплексност класе NL одговара тачно скупу логичких израза изражених у TC. То је зато што својство транзитивног завршетка има близак однос са NL-комплетним проблемом STCON за налажење усмерених путања у графу. Слично класа L је логика првог реда са комутативним, транзитивним завршецима. Кад се транзитивни завршетак дода уместо логике другог реда, добијамо PSPACE.

У базама језика упита

Додатне информације: Хијерархијски и рекурзивни упити у SQL-у.

Још од 1980—их године Оракл база података је увела приватни SQL проширен са CONNECT BY... START WITH, који омогућава рачунање транзитивних завршетака као делова декларативних упита. SQL 3 (1999) стандард је више општији стандард, са РЕКУРЗИВНИМ спојем који омогућава транзитивним завршецима да буду израчунати унутар упита процесора; од 2011, овај последњи се имплементира у IBM DB2, Microsoft SQL Server, и PostgreSQL, али не у MySQL (Benedikt and Senellart 2011:189).

Алгоритми

Ефикасни алгоритми за израчунавање транзитивног завршетка графа може се наћи у Nuutila (1995). Најједноставнија техника је вероватно Флојд–Варшалов алгоритам. Најбржи, метод најгорег случаја, која није практичан, смањује проблем на множења матрица. Скорија истраживања су показала ефикасне начине израчунавања транзитивних завршетка на подељеним системима заснованим на MapReduce парадигмама (Afrati et al. 2011).

Види још

Дедуктивно затворење
Транзитивна редукција (најмања релација која има транзитиван завршетак у R као свој транзитиван завршетак)
Симетрично затворење
Рефлексивно затворење
Анцестрални однос

Литература

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. стр. 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 изд.). Springer. стр. 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. стр. 110—119. S2CID 3242505. doi:10.1145/567752.567763.
Benedikt, Michael; Senellart, Pierre (2011). „Databases”. Computer Science. стр. 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. Недостаје или је празан параметар |title= (помоћ) ISSN 1237-2404, UDC 681.3.
Silberschatz, Abraham; Korth, Henry; 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. Ailamaki, Anastasia (2011). Proceedings of the 14th International Conference on Extending Database Technology. Association for Computing Machinery. ISBN 978-1-4503-0528-0.

Спољашње везе

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