=== 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
* Datalog je jazyk typicky používaný pro specifikaci faktů, pravidel a dotazů v deduktivních db
* 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]]''
}}
=== 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) M1
P(3)
Relace P*, Q*, R* tvoří model M1 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
}}
