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

editovat

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í

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

editovat

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

editovat

Datalog má tři velmi rozlišné, ale přesto ekvivalentní přístupy, jak definovat vlastní sémantiku:[1]

  1. Teorie modelů
  2. Teorie důkazů
  3. Fitpoint (sémantika fixpointů)

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

editovat
  1. KARVOUNARAKIS, Grigoris. Datalog. Příprava vydání LING LIU, M. TAMER ÖZSU. Boston, MA: Springer US Dostupné online. ISBN 978-0-387-39940-9. DOI 10.1007/978-0-387-39940-9_968. S. 751–754. (anglicky) DOI: 10.1007/978-0-387-39940-9_968.