{{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
: '''fakta''' - ''tvrzení'', atomické fle obsahující pouze konstanty (statická data, základní informace) - tj. '''základní literály'''
:* termy - proměnné nebo konstanty
: '''pravidla''' - jsou Hornovy klausule <math>L_0:- L_1,…,L_n</math> (návod jak odvodit data, která nejsou explicitně uložena)
:* kde <math>L_i</math> jsou atomické fle nebo negace atomických flí - tj. ''positivní a negativní literály''
:* <math>L_0</math> hlava pravidla, <math>L_1,…,L_n</math> tělo pravidla
:* tvrzení i literály jsou Hornovy klauzule
: '''dotazy''' - výraz jehož výsledkem jsou nalezená a odvozená data
* 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
'''Deduktivní db''' se skládá z:
* '''Extenzionální db (EDB)''' (základní data)
* '''Intenzionální db (IDB)''' (virtuální relace dané odvoz pravidly, "pohledy" z SQL)
** mžina Hornových klauzulí (pravidel): hlava:-tělo (např: Sourozenec(y,w) :- Otec(x,y), Otec(x,w), y != w )
* '''Integritní omezení (IO)'''
** tvrzení vymezující korektní DB (na konceptuální a db úrovni)
** př: název_k jednoznačně identifikuje řádky tabulky Kina
{{Zdroje|
* [http://www.ksi.mff.cuni.cz/~pokorny/vyuka/dj2-vyjadrovaci-sila/img83.html DJ II]
* ''viz [[wcs:Deduktivní databáze]]''
}}
=== Datalog, 3 sémantiky a jejich ekvivalence. ===
{{TODO|projit a doformatovat}}
''viz také otázka v DMJ: [[Databázové_modely_a_jazyky#Algoritmy_vyhodnocen.C3.AD_dotaz.C5.AF_v_Datalogu_a_Datalogu_s_negac.C3.AD|Algoritmy vyhodnocení dotazů v Datalogu a Datalogu s negací]]''
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.C4.8Dn.C3.A9_pravidla_v_Datalogu|bezpečná pravidla v Datalogu]]====
'''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ř.: 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)
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 programu P.
* Nechť: R(1) Q(1) P(1) M2
Pak relace P*, Q*, R* tvoří model M2 logického programu P.
* Nechť EDB: R(1), tj. relační DB je dána jako R* ={(1)}.
Pak M1 i M2 jsou s danou databází konzistentní.
* M2 tvoří dokonce minimální model, tj. změníme-li v něm cokoliv, porušíme konzistenci.
* M1 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.
==== pomocí pevného bodu zobrazení (Fixpoint Semantics) ====
*Metoda: vyhodnocovací algoritmus + relační db stroj
Definice: '''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:
*Kdyz existuje '''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 [http://webdam.inria.fr/Alice/ link Datalog]
**Kopie z [http://www.ksi.mff.cuni.cz/~pokorny/vyuka/pokorny.dj/]:
}}
=== Datalog s negací, stratifikace. ===
[[Soubor:Dalalog.jpg|right|thumb|800px|'''vyjadřovací síla relačních dotazovacích jazyků''']]
{{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 <math>A(x) \& B(x) \Rightarrow P(x)</math> 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.
}}
<math>A_{RP} \{(), [ ], \cup, \times, rename \}</math> (pozitivní RA)
{{TODO|doplnit ozrázky grafu atd...}}
==== Datalog¬ ====
* Datalog je silnější než <math>A_{RP}</math>, ale existují dotazy v <math>A_R</math>, které v Datalogu nelze vytvořit,
: např. 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|right|thumb|274px|'''závislostní graf''' logického programu P: ''uzly'' - predikáty z <math>R</math> a IDB, ''hrany'' - <math>(U,V)</math> je hrana, existuje-li pravidlo <math>V :- … U ...</math>]]
* 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 = P1 \union P2 .... \union Pn 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 Pi, pak je jeho definice obsažena v sjednocení Pk pro 1 <= k <= i
** 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 Pi, pak je jeho definice obsažena v sjednocení Pk pro 1 <= k < i
* 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 (negativní, pozitivní), '''jestliže se v grafu vyskytuje cyklus s negativní hranou, není program stratifikovatelný'''
* Př.: Program
P(x) :- ¬ Q(x) (1)
R(1) (2)
Q(x) :- Q(x), ¬ R(x) (3)
: je stratifikovatelný. Stratifikace: {(2)} ∪ {(3)} ∪ {(1)}
: Program
P(x) :- ¬ Q(x)
Q(x) :- ¬ P(x)
: není stratifikovatelný.
*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 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ší minimální bod tohoto programu, ačkoliv není výsledkem stratifikovaného vyhodnocení.
*vyhodnocení stratifikovaného programu pak probíhá obdobně jako u Datalogu bez negace, s tím, že pokud se literál Q vyskytuje v pravidle negativně, použije se místo Q: adom^n – Q (adom je aktuální doména programu, tj. sjednocení všech konstant z EDB a IDB, n je počet atributů v Q)
* Stratifikovaný DATALOG¬ Předpoklady: pravidla jsou bezpečná, rektifikovaná.
'''Tvrzení:''' Nerekurzivní programy DATALOG¬u vyjadřují právě ty dotazy, které jsou vyjádřitelné v <math>A_R</math>.
===== předpoklad uzavřeného světa=====
{{Collapse|(možná už není ve státnicích)|2=
* 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
}}
{{Zdroje|1=
* http://forum.matfyz.info/viewtopic.php?p=25929#p25929
}}
