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

okruhy 14/15: Relacní kalkuly, relacní algebry, deduktivní databáze. Relacní úplnost. Bezpecné výrazy, ekvivalence relacních dotazovacích jazyku. Veta o tranzitivním uzáveru relace. Sémantika SQL. Datalog, 3 sémantiky a jejich ekvivalence. Datalog s negací, stratifikace. Deduktivní databáze. Rekurze v SQL. Tablo dotazy - statická analýza a optimalizace relacních dotazovacích jazyku. Modelování preferencí, dotazování s preferencemi.

Podle Majklových zápisků: [1] čepičky (🎓) udávají pravděpodobnou důležitost okruhu u státnic.

Relacní kalkuly, relacní algebry. Relacní úplnost. Bezpecné výrazy, ekvivalence relacních dotazovacích jazyku. (12×🎓)

Koncepty v relačním modelu

Zážitky ze zkoušek

Relačí algebra + kalkuly + SQL (Mlýnková) - Stačilo vědět nástřel definice a hlavně, jak to přirovnat k SQL (prvky jsou tabulky/řádky/atributy ... algebra/n-ticový/doménový). U popisu algebry a kalkulu ukázat nějaké příklady. Vědět že je to ekvivalentní (kalkuly a algebra), ale že SQL je silnější protože má navíc agregačí funkce. Relacni kalkuly a algebry (Knap) - Kalkuly jsou zalozene na predikatove logice 1. radu, mohou obsahovat nebezpecna pravidla atd. Algebra muze byt pozitivni (bez mnozinoveho rozdilu), nema nebezpecna pravidla. Pak jsem byl dotazan na to, jak se v relacni algebre zapise prunik - pomoci sjednoceni a selekce.

Relační kalkul a relační algebra jsou prostředky relačního modelu dat pro manipulaci s daty

Relační kalkuly (7×🎓)

Zážitky ze zkoušek

DRK (Riha) - kde sa vyuziva prakticky - QBE, Oracle - dake formulare ci co Relační kalkuly (?) - Popsal jsem NRK, DRK, jak se v nich dotazuje (na příkladu), dále jsem zmínil doménově závislé dotazy, neomezené, problémy a jak je řešit a bezpečné formule (eliminace všeobecného kvantifikátoru, omezení volných proměnných atd.). To stačilo. Doménový kalkul (Říha) - Na papier som napísal väčšinu informácii z Pokorného skrípt, definícia, bezpečné výrazy, 1-2 príklady, použitie - to som našiel na inej diskusii - a to Říhu potešilo, že som tam mal. Bohužiaľ otázky Říhu smerovali k logike, ktorú som si už nepamätal a neopakoval. Takže najprv som z dvoch možností skúšal uhádnuť správnu, ale trafil stále špatne. Naviac som sa do toho začínal zamotávať a akosi som už nedokázal racionálne premýšľať. Červenal som sa i za ušami, ale nakoniec to Říha zhodnotil tak, že všetko podstatné bolo na papieri a tie otázky boli nad požadovaný rámec a prepustil ma. Odporúčam ujasniť si základy a spoľahlivo vedieť, čo znamená PRL 1.řádu, 2.řádu, čo je term, funkč. symbol, formula, pred. symbol, voľná premenná atp. Relacne kalkuly (Skopal) - Toto uz islo lepsie. Chcel odo mna pocut ako by som naivne implmementoval relacny kalkul v nej, programovacom jazyku - odpoved: dosadzujem prvky z domeny a skusam kedy bude podmienka true. Este chcel rozirenie kalkulu o agreg. operacie - ako by som implemetoval trebars AVG - odpoved: mam predikat AVGZAM(x) a hadam priemerny plat a ten predikat mi niekedy povie true. N-ticovy kalkul (Riha) - (priklad relacie, dotaz, realne pouzitie) Napisal som zakladne veci, ze je to rozsirenie jazyka logiky 1. radu. A uviedol som priklad na filmoch a hercoch. Realne pouzitie som nevedel. Zacali sme to rozoberat, presli sme ake veci su v jazyku logiky a ako si odpovedaju s NDK. Ked chcel to pouzitie a ja som to nevedel, tak mi napomohol poznamkou, aby som si ukazany dotaz napisal v SQL. Realne pouzitie je SQL :) Aj ked som sa dost tazko nechytal na niektore otazky, tak to uzavrel tym, ze som vlastne vsetko podstatne napisal. Celkovo velmi prijemne skusanie.

• neprocedurální jazyky
• relačně úplné, mohou obsahovat nebezpečná pravidla (⇒ silnější než RA)
• vychází z predikátové logiky 1. řádu (při dotazování) relační algebra ne

n-ticový relační kalkul (NRK)

př(NRK): spojení (představení * kina):
{ x.NÁZEV_K, k.ADRESA, x.JMÉNO_F $ | $ PŘEDSTAVENÍ(x) & KINA(k) & k.NÁZEV_K $ = $ x.NÁZEV_K }

př(NRK): film, který dávají ve všech kinech, kde něco dávají (P $ = $ PŘEDSTAVENÍ)
{p.JMÉNO_F $ | $ P(p) & ∀x ( P(x) ⇒ ∃y ( P(y) & y.NÁZEV_K $ = $ x.NÁZEV_K & p.JMÉNO_F $ = $ x.JMÉNO_F) ) }

• pracuje s daty na úrovni n-tic (prvků relace/řádků)
• Termy - n-ticové proměnné, jejich komponenty a konstanty
• Predikáty - jména relací a binární porovnávací predikáty θ (>, <, >=, <=, <>, =)
• Atomické formule R(x), x.A θ y.B, x.C θ 'konstanta', (θ je bin. porov. Predikát), R(t1,....tn) (R predikát, ti je term)
  • Atomické formule NRK jsou formule NRK a formule složené z formuli pomocí &, ∨, ¬, ⇒, ⇔ jsou také NRK fle
• Kvantifikátory: ∃, ∀

doménový relační kalkul (DRK)

př(DRK): spojení (P$ = $představení * k$ = $kina)
{f $ | $ ∀k(P(Název_kina:k) & P(Jméno_Filmu:f, Název_kina:k))}

• Místo n-tic používá doménové proměnné (tj. atributy = sloupce), místo R.u se používá R(A:x, B:y,...), atribut:typ
• Termy - jednoduché proměnné, konstanty
• Atomické formule R(A1:T1, A2:T2, ...) - stejné jako u NRK

další zdroje
Relační model - dotazování - relační kalkuly (Skopal)

Relační algebry (3×🎓)

Zážitky ze zkoušek
Relační algebra a její použití (?) - popsal jsem základní operace, odvozené operace, relační úplnost, základ k tomu, jak se díky ní optimalizuje v SQL a Datalogu (ten jsem spíš jen zmínil).

př.: herci z filmů v kině Mír
(Hrají(Název_k $ = $ Mír)[Jméno_f, Čas] * Film)[Herec]

př.: kdy je v RA mozne: $ \small(E_1 \times E_2)(selekce) = $ $ \small E_1(selekce) \times E_2 $ ?
Jestliže všechny atributy ve selekci jsou současně v E1

je neprocedurální jazyk vysoké úrovně pro práci s relacemi v relačním datovém modelu

💡 neprocedurální, nicméně struktura výrazu navádí na pořadí a způsob vyhodnocení

💡 nemá nebezpečné výrazy

• Relace - má schema (atributy + domény, na pořadí atributů nezáleží ), obsahuje množinu n-tic (duplicity jsou eliminovány)
• Operace - vytvoří z vstupní relace/í výsledek jako novou relaci
• Minimálni množina 6 operací (tvoří rel.algebru A_R):
  • výběr () (select): - vrací relaci jejíž hodnoty atributů splňují danou podmínku, která může obsahovat jména atributů, konstanty, operátory prorovnávání a logické spojky
  • projekce [] (project) - vrací relaci obsahující vybrané sloupce (duplicity jsou eliminovány)
  • sjednocení $ \cup $ (union) - vstupní relace musí mít shodnou aritu (stejný počet atributů) a domény atributů musí být stejného typu (duplicity jsou eliminovány)
  • množinový rozdíl $ \setminus $ (set difference) - musí platit stejné předpoklady jako u sjednocení
  • kartézský součin $ \times $ (Cartesian product) - předpokládá se, že atributy vstupních relací jsou disjunktní (v opačném případě musí být provedeno přejmenování), v praxi mnohdy neproveditelné kvůli vysoké režii
  • přejmenování $ ρ $ (rename)
• další odvozené operace
  • Průnik $ \cup $ - dá se vyjádřit: $ R_1 \cap R_2 = (R_1 \cup R_2 \setminus (R_1 \setminus R_2))\setminus (R_2 \setminus R_1) $
  • Přirozené spojení $ * $ (Natural join) - lze cca vyjádřit pomocí kartézského součinu, selekce a projekce: $ R * S = \left(\left(R \times S\right)\left(Rx = Sx\right)\right)[A \cup B] $
    • Spojení přes výraz (normální je přes atributy) = inner join (zobecnění vnitřního spojení)
    • Polospojení R <* S. Spojení s projekcí na schema relace, které je menší tj. R
    • Levé/Pravé vnější spojení - ve spojení jsou zachovány všechny n-tice z levé/pravé/obou relací, pokud řádky vyhovují podmínkám spojení (v SQL jsou doplněné null, RA toto neumožňuje, jelikož je relačně úplná)
    • 💡 Rozdíly mezi Joiny
  • Dělení (÷) : Dělíme všechny představení Filmy(režisér=čáp).[jmeno_f]. Vrátí to ntici odpovídajícím všechem kinům, kde všechny filmy režíroval čáp (defakto to vydělí všechny stejný kina čápem a pokud je to jedna tak to vypíše)
    • lze vyjádřit pomocí projekce, rozdílu a kartézského součinu: $ R \div S = R[A\setminus B] \setminus ((R[A\setminus B] \times S)\setminus R)[A\setminus B] $

• Dotazovací jazyk Relační algebry - jeden dotaz lze zapsat mnoha způsoby, toho se vyžívá v alg. optimalizaci dotazu
  • Jednoduchý dotaz - lze vyjádřit pouze pomocí selekce, projekce a spojení (až 80%) - nejvíc optimalizovány
• Relační úplnost - pokud lze prostředky jazyka lze vyjádřit min.množinou operací $ A_{R} \{(), [ ], \cup, \setminus, \times, rename \} $
• Pozitivní relační algebra $ A_{RP} \{(), [ ], \cup, \times, rename \} $ - je fragment RA vzniklý odstraněním množinového rozdílu
  • 💡odpovídá nerekurzivnímu DATALOGu (bez negace)

• Konstantní relace (relace co se nemění po dobu života DB) - např Číselník

Příklad(srovnání RA, DRK, NRK)

definujeme rel.schémata: FILM(JMENO_FILMU, JMENO_HERCE) HEREC(JMENO_HERCE, ROK_NAROZENI) Dotaz: Ve kterých filmech hráli všichni herci? RA: $ \small FILM \div HEREC[JMENO\_HERCE] $ NRK:$ ~ \small\{f.JMENO\_FILMU \;|\; \forall herec(HEREC(herec) \Rightarrow f(FILM(f) \wedge\; f.JMENO\_HERCE = herec.JMENO\_HERCE \;\wedge f.JMENO\_FILMU = film.JMENO\_FILMU))\} $ DRK: $ \small\{(f) | FILM(f)\wedge \forall h (HEREC(h) \Rightarrow FILM(f, h))\} $

další zdroje
Pokorného slajdy Relační model - dotazování - relační algebra (Skopal)

Bezpečné výrazy (2×🎓)

Zážitky ze zkoušek
Bezpečné výrazy (Skopal) - problémem u relačních kalkulů jsou nekonečné domény, takže je potřeba výrazy nějak omezit (aktuální doménou), kromě toho je dobré znát (resp. umět pohotově vymyslet) výrazy, na kterých jsou ty problémy relačních kalkulů vidět

bezpečné fle
každá bezpečná fle je doménově nezávislá dá se rychle zjistit zda ze daná fle bezpečná N/DRK fle vyjádřitelné realnými DJ jsou bezpečné

volne proměnné - nejsou v zadnem kvantif. (např R(x)), vázané - jsou v nejakem kvantifikátoru (např: ∃xR(x))

Definujeme: výrazy dotazu $ \{x_1,...,x_k | A(x_1,...,x_k )\} $, $ A $ je formule DRK, databáze $ R* $, dom je doména pro $ R $, aktuální doména formule $ A $ $ adom(A) $ je množina hodnot z relací v $ A $ a konstant v $ A $.

Problém RK jsou nekonečné domény, které je potřeba omezit (aktuální doménou - adom), aby nedocházelo k nežádoucím jevům:

• Nekonečná odpověď v případě nekonečné $ dom $ (např. $ \{ x,y | x=y \} $ )
• situace, kdy TRUE ohodnocení volných proměnných není v DB (např. $ \{ x | ¬Employee(Name: x)\} $ )
• nekonečný výpočet (impl. vyhodnoceni kvantifikace na nekonečné $ dom $) (např. $ \{ x | ∀y R(x,...,y) \} $ kde y má nekon.doménu )

řešením jsou doménově nezávislé (definitní, určité) dotazy $ DRK^{ind} $

• tj.: nejsou definitní pokud pod ruznymi $ dom $ davaji ruzne vysledky
• bezpečná formule ⇒ je také doménově nezávislá (opačně to neplatí, dom.nezávislé jsou nadmnožinou bezpečných)

další info

další sémantiky (stejně silné), které uvedené problémy řeší: neomezená interpretace s omezeným výstupem $ DRK^{out} $ (výsledek je definová jako průnik s $ adom^k $) omezená interpretace $ DRK^{lim} $ (vyhodnocení dotazu probíhá pouze přes hodnoty z $ adom $) každou proměnnou (volné i vázanou) omezíme doménu - přidáme $ R(x) $ a tím omezíme doménu $ x $ na $ adom(R) $ vzhledem k relaci $ R* $ konkrétněji: Omezené kvantifikátory: místo $ ∃x(φ(x)) $ se používá $ ∃x(R(x) \and φ(x)) $ - tedy $ (∃x ∈ R) φ(x) $ místo $ ∀x(φ(x)) $ se používá $ ∀x(R(x) ⇒ φ(x)) $ - tedy $ (∀x ∈ R) φ(x) $ volné proměnné ve φ(x) můžeme také omezit – konjunkcí $ R(x) \and φ(x) $ $ DRK^{out}≅DRK^{lim}≅DRK^{ind} $

zjistit, zda je DRK výraz dom.nezávislý je nerozhodnutelný problém (∄program co zjisti jestli je dom.nezávislý) a tedy $ DRK^{ind} $ není rek.spočetný jazyk

máme ale jednoduchá syntaktická pravidla (třídu) která nám určují bezpečné formule (jsou podmnožinou dom.nezávislých):

Bezpečné formule DRK

př: bezpečná pravidla DRK:
¬R(x,y) NENÍ bezpečný (dle 3.a) x = y NENÍ bezpečný (3.a) x = y ∨ R(x,y) NENÍ bezpečný (2,3.a) x = y ∧ R(x,y) JE bezpečný

př: nebezpečná pravidla NRK
pomoci ¬: {S $ | $ ¬(S ∈ Sailors)} pozn.: RA neobsahuje nebezpecna pravidla (nema ¬) a je doménově nezávislá

1. nemají ∀
   • ( $ ∀x~ φ(x) $ můžeme nahradit $ ¬∃x (¬φ(x)) $ )
2. každá disjunkce $ \varphi_1 \or \varphi_2 \or ... $obsahuje stejné volné proměnné
   • ( $ \varphi_1 \Rightarrow \varphi_2 $ tranformujeme na $ ¬\varphi_1\or\varphi_2 $ )
3. každá konjunkce (maximální), $ φ \equiv φ_1∧...∧φ_r $má všechny volné proměnné omezené, tj. platí pro ni alespoň 1 z podmínek:

   (a) proměnná je volná v $ \varphi_i $co není negace ani binární porovnání

   (b) ∃$ \varphi_i\equiv x=a $, kde $ a $ je konstanta nebo omezená proměnná

4. ¬ smí být pouze v konjunkcích z bodu 3

další zdroje
Principles of Database and Knowledge-base Systems (Jeffrey D. Ullman) - zdarma ke stažení na google books

Bezpečné (safe) formule NRK

syntaktická pravidla pro bezpečné výrazy v NRK (nebylo na přednášce)

nemají ∀ každá disjunkce $ \varphi_1 \or \varphi_2 $obsahuje pouze 1 stejnou volnou proměnnou každá konjunkce (maximální), $ φ \equiv φ_1∧...∧φ_r $má všechny volné proměnné omezené, tj. platí pro ni alespoň 1 z podmínek: (a) $ \varphi_i $ není negace ani binární porovnání ( $ \varphi_i $ obsahuje $ x $v ni volnou ⇒ každá komponenta $ x $ je omezená) (b) $ \varphi_i\equiv x.A=a $, kde $ a $ je konstanta nebo komponenta omezené proměnné ¬ smí být pouze v konjunkcích z bodu 3

př: nebezpečná pravidla Datalog
z přednášky: GREATER(x,y) :- x > y (není bezpečné) FRIEND(x,y) :- M(x) (není bezpečné) S1(y,w) :- F(x,y), F(x,w), y ≠ w (je bezpečné, ≠ se bere jako =) z media:Datalog-unsafe_rules.PNG: s(X) :- r(Y) (není bezpečné) s(X) :- r(Y) AND NOT r(X) (není bezpečné) s(X) :- r(Y) AND X < Y (není bezpečné) (ve všech připadech nekonečnost X splni pravidlo i když je R konečná relace)

Bezpečné pravidla v Datalogu

• Omezená proměnná x v Datalogu je taková, která se vyskytuje v těle literálu L a pro jehož tělo platí:
  • L je dán pravým predikátem, nebo
    • pravý predikát - jméno zákl.db relace nebo jméno virtuální relace (prakticky EDB nebo levá strana IDB pravidla)
  • L je x = a nebo a = x , kde a je konstanta nebo omezená proměnná

Pravidlo je bezpečné pokud jsou ∀proměnné omezené.

Datalog má povolená pouze bezpečná pravidla a dále platí, že v hlavách jsou pouze jména virtuálních relací

💡 (ktere nejsou v EDB), tzn odvozováním nevytvářím další základní data

Ekvivalence dotazovacích jazyků

vyjadřovací síla relačních dotazovacích jazyků

NRK omezený na bezpečné výrazy je ekvivalentní $ A_{R} $ (relační algebře)

• Z toho plyne, že kalkulové jazyky lze realizovat pomocí $ A_{R} $, která je relativně dost silná (ale nemá na logiku 1. řádu - Datalog)

DRK omezený na bezpečné výrazy je ekvivalentní $ A_{R} $

💡 DRK s doménově nezávislými výrazy je silnější než $ A_{R} $

NRK omezený na bezpečné výrazy je ekvivalentní DRK omezenému na bezpečné výrazy

Datalog je silnější než $ A_{RP} $ (pozitivní RA)

• Tranzitivní uzávěr (rekurze)
• V datalogu nelze vyjádřit rozdíl, proto není silnější než obyč RA

Stratifikovaný Datalog¬ je silnější než $ A_{R} $

• tranzitivní uzávěr (rekurze)
• rozdíl lze vyjádřit pomocí negace

💡 Stratifikovaný nerekurzivní Datalog¬ je ekvivaletní $ A_{R} $

Relační úplnost (2×🎓)

Zážitky ze zkoušek
Relační úplnost (?) - bylo 30.5.2012

relačně úplný jazyk - má prostředky přímo realizovat všechny operace $ A_R $ ( tj. "minimalne tak silny jako RA" )

Relačně úplný je:

• NRK, DRK (s bezpecnymi vyrazy jsou ekvivalentní $ A_{R} $)
• SQL (silnější, protože má navíc agregační fce, aritmetiku, null...)

💡 Datalog¬ (Stratifikovaný nerekurzivní Datalog¬ je ekvivaletní $ A_{R} $)

další zdroje
Anglicky relational completeness DJ2-2-vyjadrovaci-sila.pdf 10. slide zapisky

Věta o tranzitivním uzávěru relace (2×🎓)

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

Datalog (7×🎓)

Zážitky ze zkoušek

FZDT - Datalog s negací (Pokorný?) - Profesor si přípravu nepřečte pořádně, na škodu studentovi. Očekával jsem, že je hodný, nevyžaduje moc (např. kdybych si vytáhl větu o tr. uzávěru, nechtěl by důkaz), tak jsem se ani neobhajoval; nijak jsem se nechtěl hádat u státnic. Měl jsem popsané asi dvě stránky. Jednou z prvních otázek bylo: "A jak vypadá ten Datalog?" Zas a znovu, jako se stalo jiným, i já jsem spletl termíny term/proměnná/predikát. To, že má člověk praxi v prologu/datalogu, ještě nestačí k tomu, aby správně vysvětlil syntaxi. Dá se říct, že v Datalogu P(x) :- A(x), B(x) je něco jako A(x) & B(x) ⇒ P(x) v logice 1. řádu. Doporučuji psát obecně, ne hned příklady. Profesor si dá záležet na detailech (např. u stratifikace se jednotlivé vrstvy píší jako P1, P2, ..., Pn, tedy čárky místo sjednocení, protože sjednocení by znamenalo, že nám nezáleží na pořadí). Ale kvůli takovým detailům zas nevyhazuje. FZDT - Sémantika Datalogu pomocí NPB (Pokorný) - Posledná otázka, čas už tlačil - Pokorný musel za 45 min. odísť, tak sme sa dali do rozpracovanej otázky. V podstate príjemný rozhovor, na papieri som mal to, čo som si pamätal zo skrípt, akurát mi to veľmi nedávalo dokopy zmysel Skúšajúci bol ale vynikajúci, pýtal sa návodne, prípadne to doplnil. Nič detailné, ani nevyžadoval formalizmy. Ja som zodpovedal čo je to min. pevný bod, ako sa vyhodnocuje, ako sa vyhodnocujú datalog. programy, ako vyzerá EDB, IDB. FZDT - Sémantika Datalogu pomocí NPB (Pokorny) - Takhle by se podle me melo u statnic zkouset. S prihlednutim k tomu, ze je clovek zkousen nejen z ty jedny otazky, ale i ctyrech dalsich. Pritom docela proklepnout, zjistit, co clovek umi, neumi a pustit. Zadnej stres. DMJ - Stratifikovany Datalog s negaci (Pokorny) - Popsal jsem co je stratifikace. Program je stratifikovatelny, kdyz neexistuje v zavislostnim grafu cyklus s negativni hranou. Kdyz je program stratifikovatelny, tak ma MPB (minimalni pevny bod). Vyhodnoceni - pravidla se rozdeli do vrstev a postupne se od prvni vrstvy program vyhodnocuje algoritmem pro Datalog bez negace, tj. naivnim ci semi-naivnim pristupem.

Deduktivní databáze

př. EDB:
F(Oldřich, Pavel) F(Oldřich, Jaroslav) F(Jaroslav, Veronika)

př. IDB:
M(x):- F(x,y) S(y,w) :- F(x,y), F(x,w) B(x,y) :- S(x,y),M(x)

př. dotazy:
D1: Má Pavel bratra? D2: Najdi všechny (x,y), kde x je bratrem y D3: Najdi všechny (x,y), kde x je sourozencem y

je db systém, který dokáže provádět dedukce (např. odvodit další fakta) založené na faktech a pravidlech uložených v (deduktivní) db

Deduktivní db se skládá z:

• Extenzionální db (EDB) (uložené tabulky) - tvořené fakty
  • fakta - tvrzení, atomické fle obsahující pouze konstanty (statická data, základní informace) - tj. základní literály
    • termy - proměnné nebo konstanty
• Intenzionální db (IDB) (virtuální relace ≈ "pohledy" z SQL) - množina pravidel: hlava :- tělo
  • pravidla (v IDB) - jsou Hornovy klausule L₀ :- L₁,…,Lₙ (návod jak odvodit data, která nejsou explicitně uložena)
    • literály Lᵢ - jsou atomické formule (nebo negace a.f.) ve tvaru P(t₁,..,tₖ) , kde P je predikátový symbol a tᵢ je proměnná nebo konstanta
    • L₀ hlava pravidla, L₁,…,Lₙ tělo pravidla
    • 💡 tvrzení i literály jsou Hornovy klauzule
  • dotazy - výraz jehož výsledkem jsou nalezená a odvozená data
• Integritní omezení (IO)
  • tvrzení vymezující korektní DB (na konceptuální a db úrovni)
  • př: název_k jednoznačně identifikuje řádky tabulky Kina

• jsou výsledkem snahy kombinovat logické programování s relačními db za účelem vytvořit systém, který podporuje mocný formalismus (s vyjadřovacími schopnostmi logických prog. jazyků) a je stále rychlý a schopný pracovat s velmi rozsáhlými objemy dat.
• mají větší vyjadřovací schopnosti než relační db, ale menší než logické programovací jazyky

další zdroje
DJ II viz wcs:Deduktivní databáze

Datalog, 3 sémantiky a jejich ekvivalence.

jazyk používaný v deduktivních db je Datalog - (data)logický program je množinou tvrzení a pravidel

💡 vychází z PROLOGu (Datalog je podmnožinou PROLOGu) a využívá vyhodnocovací algoritmy umožňující efektivnější implementaci (operace relační algebry)

př: nebezpečná pravidla Datalog
z přednášky: GREATER(x,y) :- x > y (není bezpečné) FRIEND(x,y) :- M(x) (není bezpečné) S1(y,w) :- F(x,y), F(x,w), y ≠ w (je bezpečné, ≠ se bere jako =) z media:Datalog-unsafe_rules.PNG: s(X) :- r(Y) (není bezpečné) s(X) :- r(Y) AND NOT r(X) (není bezpečné) s(X) :- r(Y) AND X < Y (není bezpečné) (ve všech připadech nekonečnost X splni pravidlo i když je R konečná relace)

Bezpečné pravidla v Datalogu

• Omezená proměnná x v Datalogu je taková, která se vyskytuje v těle literálu L a pro jehož tělo platí:
  • L je dán pravým predikátem, nebo
    • pravý predikát - jméno zákl.db relace nebo jméno virtuální relace (prakticky EDB nebo levá strana IDB pravidla)
  • L je x = a nebo a = x , kde a je konstanta nebo omezená proměnná

Pravidlo je bezpečné pokud jsou ∀proměnné omezené.

Datalog má povolená pouze bezpečná pravidla a dále platí, že v hlavách jsou pouze jména virtuálních relací

💡 (ktere nejsou v EDB), tzn odvozováním nevytvářím další základní data

Sémantiku logických programů je možné vybudovat minimálně třemi různými způsoby:

logicko-odvozovací přístup (Proof-Theoretic Approach)

• Metoda: interpretace pravidel jako axiomů použitelných k důkazu, tj. provádíme substituce v těle pravidel a odvozujeme nová tvrzení z hlavy pravidel. V případě DATALOGu tak lze získat právě všechna odvoditelná tvrzení.

logicko-modelový přístup (Model-Theoretic Semantics)

Predstavme si to jako model v logice (analogicke pro logicko-odvozovaci pristup, kde je to take stejne jako v logice - take se z "axiomu" odvozuji vsechna tvrzeni).

• Metoda: za predikátové symboly dosadíme relace tak, aby na nich byla splněna pravidla.

Příklady z přednášky:

Uvažujme logický program LP IDB: P(x) :- Q(x) Q(x) :- R(x) tj. Q a P označují virtuální relace. Nechť: R(1) Q(1) P(1) Q(2) P(2) M₁ P(3) Pak relace P*, Q*, R* tvoří model M₁ logického programu LP.

Nechť: R(1) (a ostatní tvrzení mají hodnotu FALSE). Pak relace P*, Q*, R* netvoří model pogického programu LP. Nechť: R(1) Q(1) P(1) M₂ Pak relace P*, Q*, R* tvoří model M₂ logického programu LP. Nechť EDB: R(1), tj. relační DB je dána jako R* ={(1)}. Pak M₁ i M₂ jsou s danou databází konzistentní. M₂ tvoří dokonce minimální model, tj. změníme-li v něm cokoliv, porušíme konzistenci. M₁ netvoří minimální model.

💡 při obou sémantikách obdržíme stejný výsledek.

Nevýhody obou přístupů: neefektivní algoritmy v případě, že EDB je dána databázovými relacemi.

příklad MPB:
%EDB: muž(Honza) %IDB: nudný(x)  :- ¬zábavný(x), muž(x) zábavný(x) :- ¬nudný(x), muž(x) pak instance databáze I1: {nudný = {Honza}, zábavný = Ø} I2: {nudný = Ø, zábavný = {Honza}} jsou dva MPB (💡 IDB obsahuje neg.cyklus)

pomocí pevného bodu zobrazení (Fixpoint Semantics)

• Metoda: vyhodnocovací algoritmus + relační db stroj

Nejmenší pevný bod (NPB) rovnice $ R = f(R) $(kde R je bin.schéma relace) je relace $ R^* $ taková, že platí:

• $ R^* = f(R^*) $ (pevný bod)
• $ S^* = f(S^*) ⇒R^*⊆ S^* $ (minimalita)

Minimální pevný bod (MPB) pro program je takový pevný bod R*, že neexistuje žádný další pevný bod, který je vlastní podmnožinou R*.

Z toho plyne:

• ∃ nejmensi pevny bod (NPB), pak je jediným MPB.
• Existuje-li více MPB, pak jsou navzájem neporovnatelné a NPB neexistuje.

další zdroje
http://www.cs.nott.ac.uk/~nza/G53RDB07/rdb14.pdf http://webdam.inria.fr/Alice/pdfs/Chapter-12.pdf Knížka v pdf formátu zabývající se problematikou Datalogu link Datalog Kopie z [2]:

Datalog s negací, stratifikace.

vyjadřovací síla relačních dotazovacích jazyků

Zážitky ze zkoušek

Datalog s negací (Pokorny) - Profesor si přípravu nepřečte pořádně, na škodu studentovi. Očekával jsem, že je hodný, nevyžaduje moc (např. kdybych si vytáhl větu o tr. uzávěru, nechtěl by důkaz), tak jsem se ani neobhajoval; nijak jsem se nechtěl hádat u státnic. Měl jsem popsané asi dvě stránky. Jednou z prvních otázek bylo: "A jak vypadá ten Datalog?" Zas a znovu, jako se stalo jiným, i já jsem spletl termíny term/proměnná/predikát. To, že má člověk praxi v prologu/datalogu, ještě nestačí k tomu, aby správně vysvětlil syntaxi. Dá se říct, že v Datalogu P(x) :- A(x), B(x) je něco jako $ A(x) \& B(x) \Rightarrow P(x) $ v logice 1. řádu. Doporučuji psát obecně, ne hned příklady. Profesor si dá záležet na detailech (např. u stratifikace se jednotlivé vrstvy píší jako P1, P2, ..., Pn, tedy čárky místo sjednocení, protože sjednocení by znamenalo, že nám nezáleží na pořadí). Ale kvůli takovým detailům zas nevyhazuje. Datalog s negaci (Pokorny) - Co to je ten datalog s negaci, kde se muze negace vyskytovat. (Otazka.. a co kdyby byla negace v hlave pravidla?) Vylozil jsem kde je problem (vic minimalnich modelu), zadefinoval stratifikaci, algoritmus na vypocet datalogickeho programu s negaci, porovnal (bez dk) s Ar. DMJ - Stratifikovany Datalog s negaci (Pokorny) - Popsal jsem co je stratifikace. Program je stratifikovatelny, kdyz neexistuje v zavislostnim grafu cyklus s negativni hranou. Kdyz je program stratifikovatelny, tak ma MPB (minimalni pevny bod). Vyhodnoceni - pravidla se rozdeli do vrstev a postupne se od prvni vrstvy program vyhodnocuje algoritmem pro Datalog bez negace, tj. naivnim ci semi-naivnim pristupem.

$ A_{RP} \{(), [ ], \cup, \times, rename \} $ (pozitivní RA)

Datalog¬

• Datalog je silnější než $ A_{RP} $, ale existují dotazy v $ A_R $, které v Datalogu nelze vytvořit,

např.:"kteří překladatelé nepřekládají do angličtiny": PŘEKLÁDÁ[JMÉNO] – (KVALIFIKACE(JAZYK=‘ANGL’)[JMÉNO])

• k vyjádření takovýchto dotazů (obsahujících v relační algebře rozdíl) potřebuje Datalog negaci – je označován Datalog s negací, ovšem způsoby vyhodnocení programů v tomto jazyce obecně nevedou k jednoznačně definovaným virtuálním relacím – proto je identifikována podmnožina Datalogu s negací, která tuto jednoznačnost zajišťuje – tzv. stratifikovaný Datalog (viz dále)

stratifikace

závislostní graf logického programu P: uzly - predikáty z $ R $ a IDB, hrany - $ (U,V) $ je hrana, existuje-li pravidlo $ V :- … U ... $
Graf na obrázku je pro IDB:

M(x):- F(x,y)
S(y,w) :- F(x,y), F(x,w)
B(x,y) :- S(x,y),M(x) 

• jedná se o rozvrstvení pravidel do vrstev tak, aby byla zajištěna jednoznačnost vyhodnocování programů
• definujeme pojem definice virtuální relace S, což je množina všech pravidel, kde se S vyskytuje v hlavě
• Program $ P $ je stratifikovatelný, jestliže existuje disjunktní dělení $ P = P_1 ∪ P_2 .... ∪ P_n $ takové, že plati:
  • vyskytuje-li se predikátový symbol $ S $ pozitivně (je-li obsažen v pozitivním literálu v těle pravidla) v nějakém pravidle $ P_i $, pak je jeho definice obsažena v $ \bigcup_{1 ≤ k ≤ i}P_k $
    • 💡 tj. jeho definice může být ve stejné nebo nižší vrstvě
  • vyskytuje-li se predikátový symbol $ S $ negativně (je-li obsažen v negativním literálu v těle pravidla) v nějakém pravidle $ P_i $, pak je jeho definice obsažena v $ \bigcup_{1 ≤ k < i}P_k $
    • 💡 tj. jeho definice musí být pouze v nižší vrstvě
• Dělění $ P_1,…, P_n $ se nazývá stratifikace $ P $, každé $ P_i $ je stratum (stratifikace se píše s čárkami pže záleží na pořadí).
• zjišťování, zda je program stratifikovatelný (a nalezení konkrétního dělení) se provádí pomocí závislostních grafů s ohodnocenými hranami (poz/neg podle výskytu pravidla), jestliže se v grafu vyskytuje cyklus s negativní hranou, není program stratifikovatelný
• když je program stratifikovatelný ⇒ má MPB

Příklady z přednášky:

Program P(x) :- ¬ Q(x) (1) R(1) (2) Q(x) :- Q(x), ¬ R(x) (3) je stratifikovatelný. Stratifikace: Stratum 0: (2) R Stratum 1: (3) Q = Ø Stratum 2: (1) P = { 1 } Program P(x) :- ¬ Q(x) Q(x) :- ¬ P(x) není stratifikovatelný. Program pro EDB: METRO(linka, stanice, nasledujici stanice) A(x,x):-METRO(u,x,y) (1) A(x,y):-A(x,z),METRO(u,z,y) (2) B(x,z):-A(x,y),A(z,y),x!=z (3) O1(y):-A(y,Skalka),y!=Krizikova (4) O2(z):-B(z,Krizikova) (5) je stratifikovatelný, stratifikace: {(1)} ∪ {(2)} ∪ {(3)} ∪ {(4)} ∪ {(5)}

Stratifikovatelný program má obecně více stratifikací. Ty jsou ekvivalentní, tj. vyhodnocení vede ke stejnému MPB takze at provedu jakoukoliv stratifikaci daneho programu, ziskam MPB, ale nemusi to byt NPB. Viz priklad, kde existuje vice MPB: %EDB dil(trojkolka, kolo, 3). dil(trojkolka, rám, 1). dil(rám, sedadlo, 1). dil(rám, pedál, 2). dil(kolo, ráfek, 1). dil(kolo, pneumatika, 1). dil(pneumatika, ventilek, 1). dil(pneumatika, duse, 1). %IDB velky(P) :- dil(P,S,Q), Q > 2. maly(P) :- dil(P,S,Q), not velky(P). Stratifikace, a pak výsledný MPB Stratum 0: Díl Stratum 1: Velký = {trojkolka} Stratum 2: Malý = {rám, kolo, pneumatika} Ale: Relace {Malý = {trojkolka, rám, kolo, duše}, Velký = Ø } tvoří další MPB tohoto programu, ačkoliv není výsledkem stratifikovaného vyhodnocení (💡 v Datalogu není zaručeno pořadí vykonávání operací).

Tvrzení: Nerekurzivní programy DATALOG¬u vyjadřují právě ty dotazy, které jsou vyjádřitelné v $ A_R $.

předpoklad uzavřeného světa

(možná už není ve státnicích)

* předpoklad uzavřeného světa (CWA) je metapravidlo k odvozování negativní informace jestliže tvrzení R(a1,...,an) není odvoditelné z pravidel (bez použití negace), pak platí not R(a1,...,an) (neboli co není známo, není pravda) předpoklady pro použití CWA různé konstanty neoznačují tentýž objekt doména je uzavřená (konstanty z EDB+IDB) – neexistují relevantní konstanty mimo EDB a IDB Datalog s negací nelze vybudovat na základě CWA program s jediným pravidlem: NUDNÝ(EMIL) :- NOT ZAJÍMAVÝ(EMIL) bylo by odvozeno NOT ZAJÍMAVÝ(EMIL) a NOT NUDNÝ(EMIL), což je ale v rozporu s uvedeným pravidlem – na druhou stranu stratifikace to řeší přirozeně (vezme se prázdná EDB, ZAJÍMAVÝ pak bude mít prázdnou množinu – jelikož nelze odvodit žádný prvek jako ZAJÍMAVÝ a následně se odvozuje NUDNÝ a tam bude {EMIL}) příklad z SQL (které používá CWA): SELECT count(*) FROM employees WHERE secondname != „Iljič“ spočítej, kolik zaměstnanců má druhé jméno jiné než Iljič – problém nastává u zaměstnanců, kteří mají secondname = NULL, v takovém případě je podmínka ve WHERE vyhodnocena jako UNKNOWN a dle CWA následně jako FALSE, tedy zaměstnanci bez uvedeného druhého jména se do výsledku nezapočtou

další zdroje
http://forum.matfyz.info/viewtopic.php?p=25929#p25929

př. rektifikace:
P(a,x,y) :- R(x,y) P(x,y,x) :- R(y,x) zavedeme u,v,w , substituce: P(u,v,w) :- R(x,y), u = a, v = x, w = y P(u,v,w) :- R(y,x), u = x, v = y, w = x ⇒ P(u,v,w) :- R(v,w), u = a, P(u,v,w) :- R(v,u), w = u

Algoritmy vyhodnocení dotazů v Datalogu a Datalogu s negací

Obecne pred vyhodnocenim programu se provadi rektifikace - hlavy se stejnym predikatem maji po řadě stejne pojmenovane promenne.

💡 Lemma: rektifikace zachovává bezpečnost a je ekvivaletní původnímu výrazu

Nerekurzivní program

př. algoritmu pro nerekurzivní program:
C(x,y) :- F(x1,x), F(x2,y), S’(x1,x2) POM(X1,X,X2,Y) = F(X1,X) * F(X2,Y) * S’(X1,X2) C(X,Y) = POM[X,Y] S’(Y,W) = (F(X,Y) * F(X,W)) (Y ≠ W)[Y,W]

Jedna se o nerekurzivní program, tedy graf je acyklický. Z toho plyne existence topologického uspořádání. Podle tohoto uspořádání zpracovávám virtuální relace.

1. pravou stranu převeď na spojení a selekci
2. proveď na výsledek projekci
3. předchozí dvě pravidla proveď pro všechna pravidla se stejnou hlavou a výsledek sjednoť

💡 tj. v grafu začnu od uzlu ve kterém končí cesty a znej postupuji zpet k dalsim uzlum a je podle nej vyhodnocuji

Rekurzivní program

Naivní algoritmus v kazdem kroku algoritmu pracujeme s CELOU vyslednou mnozinou (v kazdem kroku se zbytecne znovu generuji jiz vygenerovane hodnoty). Cyklus konci, kdyz uz nove vysledky nepribyly zdroj

Polonaivní algoritumus vylepseni o to, ze se v kazdem kroku pracuje jen s nove vygenerovanou mnozinou Metoda: 1-krát se použije funkce eval a na diference increval (analogie s top down dyn.programováním?)

Datalog¬

Mejme priklad:

zajimavy(X) :- ¬nudny(X), muz(X).
nudny(X) :- ¬zajimavy(X), muz(X).

Extenzionalni tabulka muz obsahuje jeden zaznam 'Honza'. Pak dostavame dva minimalni pevne body (v Datalogu neni zaruceno poradi vykonavani pravidel):

1. {zajimavy={Honza}, nudny=Ø}
2. {nudny={Honza}, zajimavy=Ø}

Tento problem neexistence nejmensiho pevneho bodu (i neexistence nejmensiho modelu pro logicko-modelovy přístup + neexistence odvozeni pro logicko-odvozovaci přístup) resi stratifikace (viz definice).

Stratifikovaný DATALOG¬

• Předpoklady: pravidla jsou bezpečná, rektifikovaná.
• použije se alg. vyhodnocení Datalogu bez negace, akorát místo případné ¬Q se použije: $ adom^n – Q $

💡 $ adom $ - aktuální doména programu, tj. sjednocení všech konstant z EDB a IDB, $ n $ je počet atributů v Q

další zdroje
Slajdy Dotazovací jazyky 2 Starsi texty

kořeny SQL zdroj

Sémantika SQL

viz to samé v jiném okruhu

Rekurze v SQL. (🎓)

viz přesunuto vedle do SQL

Tableau dotazy - statická analýza a optimalizace relačních dotazovacích jazyků.

Statická analýza (relačních dotazovacích jazyků) chápeme ve smyslu statické analýzy programovacích jazyků (viz Static code analysis) - analýza (kódu) dotazů bez vykonávání programů z nich vytvořených (bez dynamické analýzy). Lze ji vykonat automatizovaným nástrojem ale také formálními metodami které dokazují vlastnosti dotazů.

• Obvyklé cíle statické analýzy programovacích jazyků (a tedy i relačních dotazovacích jazyků):
  • odhalení chyb
  • Optimalizace jako součást kompilace
  • Odhad složitosti úloh
  • Bezpečnost, …

Tableau dotazy (konjunktivní dotazy)

umí jen selekci, projekci a kartezsky součin (tedy i join) - používají se k ilustraci principů statické analýzy (na matfyzu :P)

tableau query = tabulkové dotazy ≈ konjunktivní dotazy DRK ≈ QBE - query by example

Věta: Pro každý omezený relační výraz E (selekce, projekce, přirozené spojení s disjunktními proměnnými) existuje T-dotaz q = (T; u) tak, že pro každou instanci I platí E(I) = q(I).

Příklad

Relace: R(A,B,C), S(C,D,E) RA dotaz: (R*S)(C=4)[A,B]

Tablo dotaz:

• q = (T,u)
  • T = R(x_A,x_B,4), S(4,x_D,x_E)
  • u = <A:x_A, B:x_B>
  • zápist T tabulkou:

R	A	B	C
	xA	xB	4

S	C	D	E
	4	xD	xE

Glogální optimalizace - Homomorfismus tableau dotazů

Lokální optimalizace - klasická optimalizace třeba SQL přeuspořádáním stromu dotazu.

Globální optimalizace - vymaže vícero zbytečných spojení.

q₁ = (T₁, u₁) a q₂ = (T₂, u₂) jsou tablo dotazy, homomorfismus q₂ → q₁ je substituce θ taková, že θ(T₂) ⊆ T₁ a θ(u₂) ⊆ u₁.

Věta: q₁ ⊆ q₂ ⇔ existuje homomorfismus q₂ → q₁.

Řekneme, že tablo dotaz (T, u) je minimální, když neexistuje dotaz (S, v) ekvivalentní s (T, u) a |S|<|T| (tedy ostře méně spojení).

Příklad:

Substituce (homomorfismus) z (b) na (a):

x₁ v (b) je to samé jako x v (a). Stejne tak y₁ v (b) je to samé jako y v (a).

x,y zůstává.

Je vidět, že (a) má v sobě všechny podmínky co upravene (b), takže výsledny homomorfismus je podmnožinou (a).

Tudiz (a) je podmnozinou (b)

Substituce z (c) na (b):

x₂ v (c) je to samé jako x₁ v (b). Stejne tak y₂ v (c) je to samé jako y₁ v (b).

x,x₁,y,y₁ zůstává.

Je vidět, že (b) má v sobě všechny podmínky co upravene (c), takže výsledny homomorfismus je podmnožinou (b).

Tudiz (a) je podmnozinou (c)

Substituce z (d) na (c):

x₁ v (d) je to samé jako x₂ v (c).

x,y,y₁ zůstává.

Je vidět, že (c) má v sobě všechny podmínky co má (d), takže výsledek bude podmnožinou výsledku (d)

Statická analýza - Složitosti

co-r.e. ... co-rekursivne spocetne

¬r. ... neni rekurzivni

	inkluze	splnitelnost
T-dotazy	NP úplné	ano
DRK	co-r.e. a ¬r.	r.e. a ¬r.
Datalog	¬r.	r.

Veta: Necht q a q' jsou T-dotazy. Pak nasledujici jsou NP-uplne problemy:

(a) q ⊆ q' (problém existence homomorfismu)

(b) q ≡ q'

Veta (Datalog): Splnitelnost IDB relace r programem P je rozhodnutelna.

Modelování preferencí, dotazování s preferencemi. (nové od 2011)

Hledání optimalizované na preference uživatele ( pomáháme uživateli najít to co opravdu chce, nebo co si myslíme že by se mu mohlo líbit )

• Vyjádření preference - preferenční relace (porovnání x je lepší než y) vs. hodnotící funkce (x je dobrý na 5 hvězdiček, palec nahoru...).
• Explicitní vyjádření (vědomá akce) vs Implicitní vyjádření (chování se např. v eshopu - otevření detailů, prohlížení fotek, ...)

Modely preferencí a jejich učení

Model založený na atributech, kolaborativní filtrování, preferenční relace, hybridní modely

• Model preferencí umožňuje zjistit, jak je některý objekt preferovaný. Vytváří se z chování uživatele
• Model založený na atributech
  • Využívá atributů hodnocených položek
  • Učení se sestává ze dvou kroků - lokální preference (normalizace hodnot atributů), globální preference (agregace ohodnocení a projekce vektorů do [0, 1])
• Kolaborativní filtrování
  • Najdu si množinu V uživatelů podobných uživateli U, kterým se líbí stejné věci
  • „Zákazníci, kteří si koupili x si také koupili y“
  • K výpočtu vzdáleností se používáji váhy sousedů, počítá se kosinova míra, pearsonova korelace ....
  • Implementace - inmemory, bayesovy sítě, predikční modely...
• Preferenční relace
  • Užívané v ekonomii
  • Porovnání objektů – x je lepší než y
  • Neumožňuje jednoduché setřídění objektů podle aktuální vhodnosti
  • Vytvořeno podle lidského uvažování - Přirozené pro uživatele, ale možná moc složité
  • P(x,y) - mám radši y než x, R(x,y) - y je alespoň tak dobrá jako x, I(x,y) - mezi x a y nedokážu rozlišit, jsou stejně dobré
  • CP-sítě Conditional probability networks

další zdroje
Inductive Models of User Preferences for Semantic Web Dotazování s preferencemi, zápisky z přednášek a cvičení

Státnice -- Softwarové systémy
Složitost a vyčíslitelnost -- Tvorba algoritmů (10🎓), NP-úplnost (15🎓), Aproximační algoritmy (6🎓), Vyčíslitelné funkce a rekurzivní množiny (8🎓), Nerozhodnutelné problémy (9🎓), Věty o rekurzi (6🎓)
Datové struktury -- Stromy (32🎓), Hašování (13🎓), Třídění (10🎓)
Databázové systémy -- Formální základy: Relace (12🎓), Datalog (9🎓), Ostatní (0🎓)   Modely a jazyky: SQL (7🎓), DIS (7🎓), Odborné (3)   Implementace: Transakce (5🎓), Indexace (10🎓), Komprese (3)
Softwarové inženýrství -- Programovací jazyky a překladače, Objektově orientované a komponentové systémy, Analýza a návrh softwarových systémů
Systémové architektury -- Operační systémy, Distribuované systémy, Architektura počítačů a sítí
Počítačová grafika -- Geometrické modelování a výpočetní geometrie, Analýza a zpracování obrazu, počítačové vidění a robotika, 2D počítačová grafika, komprese obrazu a videa, Realistická syntéza obrazu, virtuální realita

🎓 - znamená kolikrát byla otázka u státnic