Revert to this revision
TransitiveClosure

Binární relace <math>R</math> je '''tranzitivní''', jestliže pro každé <math>(a,b)∈R</math> a <math>(b,c)∈R</math> také <math>(a,c)∈R</math>.

'''Tranzitivní uzávěr <math>R^+</math>''' relace <math>R</math>, je nejmenší tranzitivní relace obsahující <math>R</math>.

{{theorem 
  | Pro schéma binární relace <math>R</math> v <math>A_R</math> neexistuje výraz, který ∀ relaci <math>R</math> počítá její tranzitivní uzávěr <math>R^+</math>.
  | o tranzitivním uzávěru relace
}} 

{{TODO|důkaz}}

;Dk (sporem a indukcí přes počet operací v hypotetickém výrazu pro výpočet tranzitivního uzávěru RA)
# Nechť <math>\sum_s = \{a_1,a_2,...,a_s\}, s \geq 1</math>, je množina konstant, na které neexistuje uspořádání a
#: <math>R_s =\{a1a2, a2a3,...,as-1as\}</math>
#: Pz.: Rs grafu a1  a2 as, tj. transitivita je definovaná pomocí konektivity v orientovaném grafu.
#: Pz.: je-li na sdefinováno uspořádání , pak
#:: Rs+(Rs 1Rs )(1  2)
# Ukážeme, že pro libovolný výraz E(R) existuje s takové, že E(Rs) Rs+.
# Lemma: Je-li E výraz relační algebry, pak pro dostatečně velké s
#:: E(Rs) b1,...,bk |(b1,...,bk),
#: kde k 1 a  je formule v disjunktivní normální formě.
#: Atomické formule v mají speciální tvar:
#:: bi = aj, bi aj,
#:: bi = bj + c nebo bi bj + c, kde c je (ne nutně kladná) konstanta, přičemž
#:: bj + c je zkratka pro “takové am, pro které bj = am-c“
#: Doména interpretace pro ohodnocení proměnných bj je s.
#: Pz.: bi = bj + c bi je za bj ve vzdálenosti c uzlů.
# Důkaz sporem.
#* existuje E tak, že E(R) = R+ a jakoukoliv relaci R, tj. i E(Rs) =Rs+ pro dostatečně velká s
#* dle lemmatu, Rs+ b1,b2 |(b1,b2)
#: Nastávají dva případy:
## každá klauzule z obsahuje atom tvaru
##: b1=ai, b2=ai nebo b1=b2+ c (b=b1- c)
##: Nechť b1b2 =amam+d ,
##: kde m  libovolné i a d libovolné c
##: b1=am a b2 =am+d nevyhovuje žádné klauzuli z .
##: spor (amam+d Rs+ )
## v existuje klauzule s atomy obsahujícími jen 
##: Nechť b1b2 =am+dam , kde ani bi am ani bi  am+d
##: není obsaženo v  a d 0 je větší než libovolné c
##: v b1b2+ c nebo b2 b1+ c v (viz konstrukce )
##: am+d am E(Rs) pro postačující s, ale Rs+ spor
##: Tedy: Pro jakýkoliv výraz E vždy existuje s pro něž
##: E(Rs) Rs+
# Důkaz lemmatu - indukcí dle počtu operátorů v E
## operátorů E Rs nebo E je relační konstanta stupně 1
##: E b1,b2 | b2=b1 + 1,resp.
##: E b1 | b1 = c1 b1=c2b1 = cm,
## 
### E E1 E2, E1-E2, E1  E2
#:: E1b1,...,bk | 1(b1,...,bk)
#:: E2 b1,...,bm | 2(b1,...,bm)
#:: pro a - je k=m a tedy
#:: E b1,...,bk | 1(b1,...,bk) (b1,...,bk), resp. ,
#:: E b1,...,bk | 1(b1,...,bk)  2(b1,...,bk),
#:: pro
#:: E b1,...,bk bk+1,...,bk+m | 1(b1,...,bk) 2( bk+1,...,bk+m)
#:: !! pak následuje transformace do DNF.
### E E1() a obsahuje buď = nebo 
#:: E b1,...,bk |1(b1,...,bk) (b1,...,bk)
### E E1S
#:: Budeme uvažovat projekci odstraňující jeden atribut
#:: jde o posloupnost permutací proměnných a eliminaci poslední komponenty
#:: eliminace bk vede k
#:: b1,...,bk-1|  bk (b1,...,bk),kde  je v DNF
#:: podle a) ..
#:: i=1..mb1,...,bk-1 |bki(b1,...,bk)
#:: budeme eliminovat  z jednoho konjunktu
##* v i není bk=ai, bi =bk +c, bk=bi +c
##: b1,...,bk-1 i(b1,...,bk-1)
##: kde i neobsahuje bkai , bi bk +c, bk bi +c
##* v i je buď bk=ai, bi =bk +c, bk=bi +c
##: provedou se substituce za bk
##: výsledky se upraví na TRUE
##: nebo FALSE
##: nebo bt=bj +g
##: a přidají se: bi aj pro s-c  j s, resp.
##: bi aj pro 1  j c

{{Zdroje|
* Zdroj (znění a důkaz věty):
** Věta: For an arbitrary binary relation R, there is no expression E(R) in relational algebra equivalent to R+, the transitive closure of R.

** Článek: Alfred V. Aho and Jeffrey D. Ullman: Universality of data retrieval languages. In POPL '79: Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on  Principles of programming languages, San Antonio, Texas, 1979, strany 110--119
** [http://db.cs.berkeley.edu/cs286sp07/aho-ullman.pdf link]

V češtině u Prof. Pokorného na [http://ksi.ms.mff.cuni.cz/~pokorny/vyuka/pokorny.dj/ slajdech].

A pokud to někdo náhodou stále nechápe, tak jako já, tak doporučuji materiály z jedné nizozemské univerzity, kde je dopodrobna rozebrán jak důkaz lemmatu, tak hlavního teorému:
[http://wwwis.win.tue.nl/~tcalders/teaching/advancedDB08/ex/tc.pdf Lemma1]
[http://wwwis.win.tue.nl/~tcalders/teaching/advancedDB09/notes/lecture02.pdf MainTheorem]
}}