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:

# 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)

::= | | ɛ ::= "(" ")." ::= ":-" "." ::= "(" ")" ::= | "," ::= | ::= | "," ::= | ","

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