| Datalog | |
|---|---|
| Jazyková třída | Boolean , deklarativní |
| Objevil se v | 1986 |
| Typový systém | Slabý |
| Dialekty | Datomic , pyDatalog , Dyna atd. |
Datalog je deklarativní logický programovací jazyk. Ačkoli syntakticky vypadá jako podmnožina Prologu , Datalog obecně používá model rozlišení výrazů zdola nahoru, nikoli shora dolů. Tento rozdíl vede k výraznému rozdílu v chování a vlastnostech oproti Prologu. Často se používá jako dotazovací jazyk pro deduktivní databáze. V posledních letech našel Datalog nové využití v integraci dat, extrakci informací, vytváření sítí, programové analýze, bezpečnosti, cloud computingu a strojovém učení [1] [2] .
Jeho počátky sahají do počátků logického programování, ale jako samostatné téma se začalo prosazovat kolem roku 1977, kdy Herve Galler a Jack Minker uspořádali seminář o logice a databázích [3] . Davidu Mayerovi se připisuje vytvoření termínu Datalog [4] .
Na rozdíl od Prologu lze příkazy programu Datalog zadat v libovolném pořadí. Navíc je zaručeno dokončení dotazů Datalogu na konečné množiny, což je důvod, proč Datalog nemá v Prologu příkaz cut. Díky tomu je Datalog zcela deklarativní jazyk.
Na rozdíl od Prologu, Datalog:
Postup řešení dotazu pomocí Datalogu je založen na logice prvního řádu a z tohoto důvodu je správný a úplný. Datalog však není Turing kompletní, a proto se používá jako doménově specifický jazyk, který může využít efektivních algoritmů navržených pro řešení dotazů. Pro efektivní provádění dotazů byly skutečně navrženy různé metody, jako je algoritmus Magic Sets [6] , programování tabulkové logiky [7] nebo rozlišení SLG [8] .
Některé široce používané databázové systémy zahrnují nápady a algoritmy vyvinuté pro Datalog. Například standard SQL:1999 zahrnuje rekurzivní dotazy a algoritmus Magic Sets (původně navržený pro rychlejší vyhodnocování dotazů Datalog) je implementován v IBM DB2 . Datalog engine navíc stojí za specializovanými databázovými systémy, jako je databáze Intellidimension pro sémantický web [9] . Pro Datalog bylo vytvořeno několik rozšíření, jako je podpora agregačních funkcí, umožnění objektově orientovaného programování nebo umožnění disjunkcí jako záhlaví vět. Tato rozšíření mají významný dopad na definici sémantiky Datalogu a na implementace konkrétních verzí interpretu Datalog.
Datalogové programy mohou nebo nemusí používat negaci v tělech pravidel: Datalogové programy s negací ji často potřebují použít jako stratifikovanou negaci, aby zajistily, že sémantika je dobře definována. Datalogové programy mohou, ale nemusí používat nerovnosti mezi proměnnými v tělech pravidel.
Jsou definovány některé fragmenty syntaxe Datalogu, například následující (nejvíce omezené až nejméně omezené):
Další omezení se týká použití rekurze: nerekurzivní Datalog je definován zakázáním rekurze v definici programů Datalog. Tento fragment Datalogu je stejně výrazný jako zřetězení dotazů, ale psaní dotazů jako nerekurzivního Datalogu může být stručnější.
Problém omezení pro Datalog se scvrkává na to, zda je program Datalog omezen, tedy zda maximální hloubka rekurze dosažená při vyhodnocování programu ve vstupní databázi může být omezena nějakou konstantou. Jinými slovy, problém se scvrkává na to, zda lze program Datalog přepsat jako nerekurzivní program Datalog. Řešení omezení libovolných programů Datalog je nerozhodnutelné, ale lze jej učinit rozhodným tím, že se omezíme na některé fragmenty Datalogu [10] .
Tyto dva řádky definují dvě skutečnosti, tedy věci, které vždy platí:
rodič ( xerces , brooke ). rodič ( brooke , damocles ).Zde je to, co znamenají: xerces je rodič brooke a brooke je rodič damocles. Názvy jsou psány malými písmeny, protože řetězce začínající velkým písmenem představují proměnné.