Datalog je deklarativní logický programovací jazyk, který vychází z Prologu. Často se používá jako dotazovací jazyk pro deduktivní databáze.
Začal se používat už v počátcích logického programování, ale samostatně se proslavil kolem roku 1977, díky Hervému Gallaire a Jacku Minkerovi, kteří uspořádali seminář o logice a databázích. Termín datalog zavedl profesor David Maier.
Rozdíly oproti Prologu Datalog na rozdíl od Prologu:
nelze psát složité výrazy dovnitř predikátů. Například proměnné v predikátu jsou v pořádku, složené výrazy nelze funkční symboly nejsou vůbec povoleny nemá operátor řezu (cut) – ukončení dotazů je automatické nezáleží na pořadí uvedení příkazů pro použití rekurze se zde vyskytují určitá omezení vyžaduje, aby se každá proměnná, vyskytující se v hlavě (head) klauzule (věta zakončená tečkou), nebo v záporném – negovaném – literálu v těle (tail) klauzule, objevila i v nenegovaném literálu v těle klauzule umožňuje disjunkci jako hlavu klauzulí umožňuje objektově orientované programování
Funkce Vyhodnocení dotazu je založeno na logice prvního řádu, ale není turingovsky úplný. Na základě toho může využívat výhod efektivních algoritmů.
Skládá se z množiny pravidel, z nichž je každé spojovacím dotazem.
Fragmenty Programy Datalogu mohou mít použitelný fragment s/bez negace v tělech pravidel a s/bez nerovnosti mezi proměnnými v tělech pravidel.
Některé syntaktické fragmenty Datalogu jsou:
lineární Datalog – nejvíce omezený, těla pravidel musí obsahovat právě jeden atom, strážený Datalog – pro každé pravidlo se musí všechny proměnné, vyskytující se v tělech pravidel, vyskytovat ještě společně alespoň v jednom atomu – ochranný atom, nerekurzivní Datalog – jak název napovídá, v definici programu Datalog je rekurze zakázána.
Sémantika Datalog má tři velmi rozlišné, ale přesto ekvivalentní přístupy, jak definovat vlastní sémantiku:
Teorie modelů Teorie důkazů Fitpoint (sémantika fixpointů)
Syntax Datalog se skládá ze seznamu faktů a pravidel (Hornova klauzule). Predikáty také mohou být definovány fakty a pravidly.
Příklad pravidlo: hlava :- tělo – tělo -> hlava (klasická implikace) <program> ::= <fact> <program> | <rule> <program> | ɛ <fact> ::= <relation> "(" <constant-list> ")." <rule> ::= <atom> ":-" <atom-list> "." <atom> ::= <relation> "(" <term-list> ")" <atom-list> ::= <atom> | <atom> "," <atom-list> <term> ::= <constant> | <variable> <term-list> ::= <term> | <term> "," <term-list> <constant-list> ::= <constant> | <constant> "," <constant-list>
Datalog rozlišuje mezi extenzivními predikáty (definované fakty) a intenzivními predikáty (definovaná pravidla).
Řetězce začínající velkým písmenem představují proměnné. Řetězce začínající malým písmenem představují názvy.
Reference
Kategorie:Dotazovací jazyky Kategorie:Deklarativní programovací jazyky