Datalog

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:^[1]

1. Teorie modelů
2. Teorie důkazů
3. 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