Formální základy databázové technologie/TransitiveClosure

Zážitky ze zkoušek

Věta o tranzitivním uzávěru relace (2012) - Napsal jsem definici tranzitivního uzávěru, znění věty a důkaz podle slidů prof. Pokorného. Až na drobnou chybu v definici tranzitivního úzávěru, kterou jsem opravil, to stačilo. Veta o tranzitivnim uzaveru relace (2009, Galambos) - jeste ze jsem si tu otazku nechal az na konec, jinak bych tam sedel asi az do vecera. Nebyl jsem jedinej, koho otazka tohoto zkousejiciho dost zdrzela, spis to bylo pravidlo. Styl zkouseni podobny tomu pana Skopala s tim rozdilem, ze "se teda hezky snazte, vas necham chvili uzrat" a takhle se to opakuje nekolikrat..si osobne myslim, ze tenhle styl zkouseni je pro matfyz potrebnej, ale nikoliv u statnic, kde ma clovek dalsi ctyri otazky. Uz takhle tam nektery lidi sedeli a "zrali" u tech statnic celkem pres pet hodin (nebo i dyl-vyhlaseni melo bejt ve tri, ale ve trictvrte prisla pani Dejmkova, at prej mame strpeni, ze dva lidi jsou jeste zkouseny. Zacinali vsichni v devet..) Vubec si neumim predstavit, ze by v jedny komisi bylo takovejchhle zkousejicich vic. Navic nutit lidi na fleku (navic u statnic pod takovym tlakem) vymejslet veci, ktery treba nikdy neslyseli, protoze v doporucenejch kurzech ke statnicim se neberou, ale podle nazoru zkousejiciho se "do toho tematu daj zahrnout" (abych nekrivdil - to nebyl zrovna muj pripad, ale u nekterejch kolegu jo) podle me neni uplne stastnej pristup..

Binární relace R je tranzitivní, jestliže ∀abc: (a,b)∈R ∧ (b,c)∈R ⇒ (a,c)∈R.

Tranzitivní uzávěr Rₛ⁺ relace R, je nejmenší tranzitivní relace obsahující R.

• v praxi užitečný – např. hledání spojení s přestupy v dopravě, nebo hledání nejkratší cesty v grafu, apod.

Věta (TC nemůže být vyjádřen v RA ): Pro schéma binární relace R v A_R neexistuje výraz, který ∀ relaci R počítá její tranzitivní uzávěr R⁺.

Pozn: 💡 Nestačí ani rozšíření o aritmetické výrazy, agregační fce a ano/ne dotazy, částečné řešení poskytuje Datalog

Rₛ = {a₁a₂, a₂a₃,...,aₛ₋₁aₛ}

Lemma E(Rₛ):
lze se na to dívat tak, že: E(Rₛ) = {(aᵢ,aⱼ): (aᵢ,aⱼ) ∈ Rₛ ∨ (aᵢ,x) ∈ Rₛ ∧ (x, aⱼ) ∈ Rₛ ∨ (aᵢ,x) ∈ Rₛ ∧ (x, y) ∈ Rₛ ∧ (y, aⱼ) ∈ Rₛ ∨ ...}

Dk (sporem, nechť takové E existuje (je konečné), pak dokážu zvýšit d natolik, že aₘaₘ₊_d ∉ E(Rₛ) nebo aₘ₊_daₘ ∈ E(Rₛ) a nemělo by být)

• uvažujme binární relaci Rₛ = { aᵢaⱼ | 1 ≤ i < s } ⇒ jejím tranzitivním uzávěrem je Rₛ⁺ = {aᵢaⱼ: i < j}
• ukážeme, že ∄ výraz E(Rₛ) = Rₛ⁺, ∀s
• Lemma: každý RA výraz E můžeme pro dost.velké s vyjádřit jako: E(Rₛ) ≅ { b₁,...,bₖ | Γ(b₁,...,bₖ) }, kde Γ je v DNF
  • bᵢ = aⱼ , bᵢ ≠ aⱼ ,
  • bᵢ = bⱼ + c nebo bᵢ ≠ bⱼ + c, kde c je (ne nutně kladná) konstanta,
  • Dk: indukcí dle počtu operátorů v E
• sporem, nechť takové E existuje, pak můžeme d zvýšit natolik že:
  • díky konečnému počtu atomických formulí v Γ: aₘaₘ₊_d ∉ E(Rₛ) nebo
  • pomocí ≠: aₘ₊_daₘ ∈ E(Rₛ) (💡 obojí je spor se definicí TC)
• Tedy: Pro jakýkoliv výraz E vždy existuje s pro něž E(Rₛ) ≠ Rₛ⁺

Dk (detailně z přednášky s poznámkami - NEvyžaduje se ke zkoušce)

Nechť ∑ₛ = {a₁,a₂,...,aₛ}, s ≥ 1, je množina konstant, na které neexistuje uspořádání a Rₛ = {a₁a₂, a₂a₃,...,aₛ₋₁aₛ} = { aᵢaⱼ $ | $ 1 ≤ i < s } Pozn.: Rₛ odpovídá grafu a₁ → a₂ → ... → aₛ , tj. transitivita je definovaná pomocí konektivity v orientovaném grafu. Pozn.: je-li na ∑ₛ definováno uspořádání <, pak Rₛ⁺ ≅ (Rₛ [1] × Rₛ [2])(1 < 2) Ukážeme, že pro libovolný výraz E(R) existuje s takové, že E(Rₛ) ≠ Rₛ⁺. Lemma: Je-li E výraz relační algebry, pak pro dostatečně velké s E(Rₛ) ≅ { b₁,...,bₖ $ | $ Γ(b₁,...,bₖ) } (💡 tedy výsledek je množina k-tic) kde k ≥ 1 a Γ je formule v DNF (disjunktivní normální formě). Atomické formule v Γ mají speciální tvar: bᵢ = aⱼ , bᵢ ≠ aⱼ , bᵢ = bⱼ + c nebo bᵢ ≠ bⱼ + c, kde c je (ne nutně kladná) konstanta, přičemž bⱼ + c je zkratka pro “takové aₘ , pro které bⱼ = aₘ₋c“ bⱼ ∈ ∑ₛ (💡 tedy doména interpretace pro ohodnocení proměnných bⱼ je ∑ₛ ) 💡 Lemma říká že počet atomických formulí v Γ závisí na E a ne na s. Pozn.: bᵢ = bⱼ + c znamená: bᵢ je za bⱼ ve vzdálenosti c uzlů. Dk( sporem, nechť takové E existuje (je konečné), pak dokážu zvýšit d natolik, že aₘaₘ₊d ∉ E(Rₛ) nebo aₘ₊daₘ ∈ E(Rₛ) a nemělo by být ): existuje E tak, že E(R) = R⁺ a jakoukoliv relaci R, tj. i E(Rₛ) = Rₛ⁺ pro dostatečně velká s dle lemmatu, Rₛ⁺ ≅ { b₁,b₂ $ | $ Γ(b₁,b₂)} Nastávají dva (disjunktní) případy: každá klauzule z Γ obsahuje atom tvaru b₁ = aᵢ , b₂ = aᵢ nebo b₁ = b₂ + c (💡 tedy b₂ = b₁ - c) Nechť b₁b₂ = aₘaₘ₊d , kde m > libovolné i a d > libovolné c ⇒ b₁ = aₘ a b₂ = aₘ₊d nevyhovuje žádné klauzuli z Γ. ⇒ aₘaₘ₊d ∉ E(Rₛ) ⇒ aₘaₘ₊d ∉ Rₛ⁺ (💡 což je špatně, aₘaₘ₊d by z definice TC mělo být v Rₛ⁺ ) ⇒ spor v Γ existuje klauzule s atomy obsahujícími jen ≠ . Nechť b₁b₂ = aₘ₊daₘ , kde ani bᵢ ≠ aₘ ani bᵢ ≠ aₘ₊d není obsaženo v Γ a d > 0 je větší než libovolné c v b₁ ≠ b₂ + c nebo b₂ ≠ b₁ + c v Γ (viz konstrukce Γ) ⇒ aₘ₊daₘ ∈ E(Rₛ) pro postačující s, a tedy by mělo být i v Rₛ⁺ což ale je v rozporu s definicí TC ⇒ spor Tedy: Pro jakýkoliv výraz E vždy existuje s pro něž E(Rₛ) ≠ Rₛ⁺ Dk lemmatu (indukcí přes počet operátorů v E): krok: ∅ operátorů ⇒ E ≡ Rₛ nebo E je relační konstanta stupně 1 ⇒ E ≡ { b₁ , b₂ $ | $ b₂ = b₁ + 1 }, resp. ⇒ E ≡ { b₁ $ | $ b₁ = c₁ ∨ b₁ = c₂ ∨ ... ∨ b₁ = cₘ }, indukční krok (vše mimo projekce je jednoduché): a)  E ≡ E₁ ∪ E₂ , E₁ - E₂ , E₁ × E₂ , definujme: E₁ ≅ {b₁,...,bₖ $ | $ Γ₁(b₁,...,bₖ) } E₂ ≅ {b₁,...,bₘ $ | $ Γ₂(b₁,...,bₘ) } ⇒ pro ∪ k = m a tedy E ≅ {b₁,...,bₖ $ | $ Γ₁(b₁,...,bₖ) ∨ Γ₂(b₁,...,bₖ)} , ⇒ pro mínus (je také k = m) E ≅ {b₁,...,bₖ $ | $ Γ₁(b₁,...,bₖ) ∧¬Γ₂(b₁,...,bₖ)}, ⇒ pro × E ≅ {b₁,...,bₖ bₖ₊₁,...,bₖ₊ₘ $ | $ Γ₁(b₁,...,bₖ) ∧ Γ₂(bₖ₊₁,...,bₖ₊ₘ)} 💡! pro ∧ pak následuje transformace do DNF. b)  E ≡ E₁(φ) a φ obsahuje buď = nebo ≠ ⇒ E ≅ {b₁,...,bₖ $ | $ Γ₁(b₁,...,bₖ) ∧ φ(b₁,...,bₖ)} c)  E ≡ E₁[S] budeme uvažovat projekci odstraňující jeden atribut ⇒ jde o posloupnost permutací proměnných a eliminaci poslední komponenty eliminace bₖ vede k {b₁,...,bₖ₋₁ $ | $ ∃bₖ Γ(b₁,...,bₖ)} , kde Γ je v DNF ⇒ podle a) : ∪ᵢ₌₁..ₘ{b₁,...,bₖ₋₁ $ | $ ∃bₖ Γᵢ(b₁,...,bₖ)} ⇒ budeme eliminovat ∃ z jednoho konjunktu v Γᵢ není bₖ = aᵢ, bᵢ = bₖ + c, bₖ = bᵢ + c ⇒ {b₁,...,bₖ₋₁ $ | $ Γᵢ(b₁,...,bₖ₋₁)} kde Γᵢ neobsahuje bₖ ≠ aᵢ , bᵢ ≠ bₖ + c, bₖ ≠ bᵢ + c v Γᵢ je buď bₖ = aᵢ, bᵢ = bₖ + c, bₖ = bᵢ + c ⇒ provedou se substituce za bₖ výsledky se upraví na TRUE nebo FALSE nebo bₜ = bⱼ + g a přidají se: bᵢ ≠ aⱼ pro s-c < j ≤ s, resp. bᵢ ≠ aⱼ pro 1 < j ≤ c

další 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 link V češtině u Prof. Pokorného na 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: Lemma1 MainTheorem