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

Из Википедије, слободне енциклопедије

У математици, транзитивни завршетак бинарних релација 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, можемо доказати да је транзитивни завршетак дат помоћу следећег израза

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

и, за ,

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

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

  • : садржи све из , тако да садржи .
  • је транзитивно: сваки елемент из је у једном од , тако да мора бити транзитивно због следећег закључка: ако је и , онда из композиција асоцијативности, (и на тај начин у ) због дефиниције .
  • је минималан: Нека буде било која транзитивна релација која садржи , желимо да покажемо да . Довољно је да показемо да за свако , . Дакле, пошто садржи , . И општо је транзитивно, кадгод је , према конструкцији што значи да је транзитивно. Дакле, по индукцији, sadrži svaki , и такође .

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

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

Претпоставка: GA транзитивна релација RAGA TAGA. Следи (a,b)GA(a,b)TA. Следи посебно (a,b)RA .

Сада, према дефиницији релације Т, знамо да n (a,b)A. Затим, i ,i < n ei А. Дакле, постоји пут од a до b, то је: aRAe1RA...RAe(n-1)RAb.

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

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

Последица[уреди]

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

Карактеристике[уреди]

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

У теорији графова[уреди]

Transitive closure constructs the output graph from the input graph.
Транзитивни завршеци конструису излазни граф од улазног графа.

У рачунарству, концепт транзитивног завршетка може се сматрати као конструисање структура података које омогућавају да се одговори на питања досежности. То је, може ли се добити од чвора 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).

Види још[уреди]

Литература[уреди]

Спољашње везе[уреди]