Транзитивно затворење
У математици, транзитивни завршетак бинарних релација -{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}- 
Нека је А произвољан скуп елемената.

Претпоставка: -{G}-A транзитивна релација -{R}-AGA TAGA. Следи (-{a}-,-{b}-)-{G}-A(-{a}-,-{b}-)TA. Следи посебно (-{a}-,-{b}-)-{R}-A .

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

Али, због транзитивности -{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}-)TA (-{a}-,-{b}-)-{G}-A. Ово значи да је T-{G}-, за било коју транзитивну -{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. 
 Keller, U., 2004,  (unpublished manuscript)
 
 
 
 
 
 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.  , UDC 681.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.

Спољашње везе 
 "Transitive closure and reduction", The Stony Brook Algorithm Repository, Steven Skiena .

Математичке релације
У математици , транзитивни завршетак бинарних релација -{ R }- у скупу X је транзитивна релација -{ R } -+ у скупу X тако да је -{ R } -+ који садржи -{ R }- и -{ R } -+ минималан ( -{ Lidl i Pilc337 }- ) . Ако је сама бинарна релација транзитивна , онда је транзитивни завршетак та иста бинарна релација ; у супротном , транзитивни завршетак је различита релација . На пример , ако је 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 }- Нека је А произвољан скуп елемената . Претпоставка : -{ G } -A транзитивна релација -{ R } -AGA TAGA . Следи ( -{ a } -,-{ b }- ) -{ G} -A( -{ a } -,-{ b }- ) TA . Следи посебно ( -{ a } -,-{ b }- ) -{ R } -A \ . Сада , према дефиницији релације Т , знамо да -{ n }- ( -{ a } -,-{ b }- )A . Затим , -{ i } -,-{ i }- < -{ n }- e-{ i }- А . Дакле , постоји пут од -{ a }- до -{ b }- , то је : -{ a } --{ R } -Ae1RA...-{ R } -Ae( -{ n } --1 ) RAb . Али , због транзитивности -{ 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 }- ) TA ( -{ a } -,-{ b }- ) -{ G } -A . Ово значи да је T-{ G }- , за било коју транзитивну -{ G }- која садржи -{ R }- . Дакле , Т је најмања транзитивна релација која садржи -{ R }- . Последица Ako je -{ R }- транзитивна , онда -{ R }- = T . Карактеристике Унија две транзитивне релације не мора да буде транзитивна . Да би се сачувала транзитивност , један мора преузети транзитивни завршетак . Ово се дешава , на пример , када се узме унија две исте релације или два „ преордера ” . За добијање нове релације еквиваленције или „ преордера ” , један мора преузети транзитиван завршетак ( рефлексивност и симетрија - у случају релације еквиваленције - су аутоматски ) . У теорији графова У рачунарству , концепт транзитивног завршетка може се сматрати као конструисање структура података које омогућавају да се одговори на питања досежности . То је , може ли се добити од чвора -{ a }- до чвора -{ d }- један или више путева ? Бинарна релација говори само да је чвор -{ a }- повезан са чвором -{ b }- , и да је чвор -{ b }- повезан са чвором -{ c }- , и тако даље . Након што је транзитивни завршетак образован , као што је представљено на слици , у -{ O( 1 ) }- операцији може се одредити да је чвор -{ d }- доступан из чвора -{ a }- . Структуре података се обично чувају као матрице , тако да ако је матрица[ 1][ 4 ] =онда је то случај када се из чвораможе доћи до чвораједним или помоћу више путева . Транзитивни завршетак директних ацикличних графова ( -{ DAG }- ) је достижана релација -{ DAG } --а и строго парцијалних уређења . У логичкој и рачунарској сложености U теорији коначних модела , логика првог реда ( -{ FO }- ) проширена операцијом транзитивног завршетка обично се зове логика транзитивног завршетка , и скраћује се -{ FO ( TC ) }- или само -{ TC } -. -{ TC }- је подтип логичке фикспоинт логике . Чињеница да је -{ FO ( TC ) }- строго много израженији него -{ FO }- , открио је Роналд Фагин резултате су преиспитали Алфред Ахо и Џефри Улман који су предложили да се фикспоинт логика употребљава као језичка база упита. ( -{ Libkinvii }- ) Са новијим концептима теорија коначних модела , доказује се да је -{ FO ( TC ) }- строго израженији него -{ FO }- који следи непосредно из чињенице да -{ FO ( TC ) }- није -{ Gaifman } --лоцал ( -{ Libkin49 }- ) . У сложеној рачунарској теорији , комплексност класе -{ NL }- одговара тачно скупу логичких израза изражених у -{ TC }- . То је зато што својство транзитивног завршетка има близак однос са -{ NL } --комплетним проблемом -{ STCON }- за налажење усмерених путања у графу . Слично класа -{ L }- је логика првог реда са комутативним , транзитивним завршецима . Кад се транзитивни завршетак дода уместо логике другог реда , добијамо -{ PSPACE }- . У базама језика упита Додатне информације : Хијерархијски и рекурзивни упити у -{ SQL } --у . Још одих године Оракл база података је увела приватни -{ SQL }- проширен са -{ CONNECT BY ... START WITH }- , који омогућава рачунање транзитивних завршетака као делова декларативних упита. -{ SQL-стандард је више општији стандард , са РЕКУРЗИВНИМ спојем који омогућава транзитивним завршецима да буду израчунати унутар упита процесора ; од овај последњи се имплементира у -{ IBM DB2 }- , -{ Microsoft SQL Server }- , и -{ PostgreSQL }- , али не у -{ MySQL }- ( -{ Benedikt and Senellart189 }- ) . Алгоритми Ефикасни алгоритми за израчунавање транзитивног завршетка графа може се наћи у -{ Nuutila }- Најједноставнија техника је вероватно Флојд–Варшалов алгоритам . Најбржи , метод најгорег случаја , која није практичан , смањује проблем на множења матрица . Скорија истраживања су показала ефикасне начине израчунавања транзитивних завршетка на подељеним системима заснованим на -{ MapReduce }- парадигмама ( -{ Afrati et al. }- Види још Дедуктивно затворење Транзитивна редукција ( најмања релација која има транзитиван завршетак у -{ R }- као свој транзитиван завршетак ) Симетрично затворење Рефлексивно затворење Анцестрални однос Литература Lidl , R. and Pilz , G . , Applied abstract algebra ,d edition , Undergraduate Texts in Mathematics . Keller , U . , ( unpublished manuscript ) Nuutila , E . , Efficient Transitive Closure Computation in Large Digraphs . Acta Polytechnica Scandinavica , Mathematics and Computing in Engineering Series No . Helsinkipages . Published by the Finnish Academy of Technology . , UDC3. Appendix C ( online only ) Foto N . Afrati , Vinayak Borkar , Michael Carey , Neoklis Polyzotis , Jeffrey D . Ullman , Map-Reduce Extensions and Recursive Queries , EDBT March24 , Uppsala , Sweden . Спољашње везе " Transitive closure and reduction " , The Stony Brook Algorithm Repository , Steven Skiena \ . Математичке релације