{{Zkazky|

  • 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

{{zarovka| :F(Oldřich, Pavel)

:F(Oldřich, Jaroslav) :F(Jaroslav, Veronika)

|př. EDB}} {{zarovka|

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

:B(x,y) :- S(x,y),M(x) |př. IDB}}

{{zarovka| :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

|př. dotazy}} 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. <u>základní literály</u>

      • 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{{Zdroje|

  • DJ II

  • viz wcs:Deduktivní%20databá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)

{{:Formální_základy_databázové_technologie/Bezpečné_výrazy_Datalog}}

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.

{{zarovka|1=

%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)

| 2= příklad MPB }}

<u>pomocí pevného bodu zobrazení (Fixpoint Semantics)</u>

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

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

  • R∗=f(R∗)R^* = f(R^*) (pevný bod)

  • S∗=f(S∗)⇒R∗⊆S∗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.

{{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 http://www.ksi.mff.cuni.cz/%7Epokorny/vyuka/pokorny.dj/:

}}

Datalog s negací, stratifikace.

Soubor:Dalalog.jpg

{{Zkazky|

  • 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)⇒P(x)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.

}}

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 14: A_{RP} \{(), \̲[̲ ], \cup, \time…

(pozitivní RA)

Datalog¬

  • Datalog je silnější než ARPA_{RP}, ale existují dotazy v ARA_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

[[Soubor:Zav_graf.jpg|thumb|274px|závislostní graf logického programu P: uzly - predikáty z RR a IDB, hrany - (U,V)(U,V) je hrana, existuje-li pravidlo V:−…U...V :- … U ...

||

|

předpoklad uzavřeného světa

::

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

::

Nerekurzivní program

Rekurzivní program

|

|

Datalog¬

Stratifikovaný DATALOG¬

  •   ::