Dziennik danych - Datalog

Datalog jest deklaratywnym językiem programowania logicznym , który syntaktycznie jest podzbiorem Prologa . Jest często używany jako język zapytań dla dedukcyjnych baz danych . W ostatnich latach Datalog znalazł nowe zastosowanie w integracji danych , ekstrakcji informacji , sieciach , analizie programów , bezpieczeństwie , przetwarzaniu w chmurze i uczeniu maszynowym .

Jego początki sięgają początków programowania logicznego , ale stało się widoczne jako osobny obszar około 1977 roku, kiedy Hervé Gallaire i Jack Minker zorganizowali warsztaty na temat logiki i baz danych . David Maier jest uznawany za twórcę terminu Datalog.

Funkcje, ograniczenia i rozszerzenia

Inaczej niż w Prologu, instrukcje programu Datalog mogą być podawane w dowolnej kolejności. Co więcej, zapytania Datalog dotyczące zbiorów skończonych mają gwarancję zakończenia , więc Datalog nie ma operatora cięcia w Prologu . To sprawia, że ​​Datalog jest językiem w pełni deklaratywnym .

W przeciwieństwie do Prologu, Datalog

1. nie zezwala na wyrażenia złożone jako argumenty predykatów , np. p (1, 2) jest dopuszczalne, ale nie p (f (1), 2),
2. nakłada pewne ograniczenia stratyfikacji na stosowanie negacji i rekurencji ,
3. wymaga, by każdy zmienną która pojawia się w głowie klauzuli pojawia się również w nonarithmetic dodatni (czyli nie negujące) dosłownego w treści klauzuli,
4. wymaga, aby każda zmienna występująca w literale ujemnym w treści klauzuli występowała również w literale dodatnim w treści klauzuli

Ocena zapytań za pomocą Datalog opiera się na logice pierwszego rzędu , dzięki czemu jest solidna i kompletna . Jednak Datalog nie jest kompletnym językiem Turinga i dlatego jest używany jako język specyficzny dla domeny, który może korzystać z wydajnych algorytmów opracowanych do rozwiązywania zapytań. Rzeczywiście, zaproponowano różne metody wydajnego wykonywania zapytań, np. algorytm Magic Sets, programowanie w logice tabelarycznej lub rozdzielczość SLG.

Niektóre powszechnie używane systemy baz danych zawierają pomysły i algorytmy opracowane dla Datalog. Na przykład standard SQL:1999 obejmuje zapytania rekurencyjne , a algorytm Magic Sets (początkowo opracowany w celu szybszej oceny zapytań Datalog) jest zaimplementowany w DB2 firmy IBM . Ponadto silniki Datalog stoją za wyspecjalizowanymi systemami baz danych, takimi jak baza danych Intellidimension dla sieci semantycznej .

W Datalogu wprowadzono kilka rozszerzeń, np. w celu obsługi funkcji agregujących , umożliwienia programowania obiektowego lub umożliwienia rozłączeń jako nagłówków klauzul . Rozszerzenia te mają znaczący wpływ na definicję semantyki Datalog oraz na implementację odpowiedniego interpretera Datalog.

Paprochy

Programy Datalog mogą, ale nie muszą używać negacji w ciałach reguł: Programy Datalog z negacją często muszą używać jej jako negacji warstwowej, aby zapewnić, że semantyka jest dobrze zdefiniowana. Programy Datalog mogą, ale nie muszą wykorzystywać nierówności między zmiennymi w ciałach reguł.

Zdefiniowano niektóre fragmenty składniowe Datalog, takie jak następujące (od najbardziej do najmniej ograniczonego):

• liniowy Datalog , gdzie ciała reguł muszą składać się z jednego atomu
• strzeżony Datalog , gdzie dla każdej reguły wszystkie zmienne występujące w ciałach reguł muszą występować razem w co najmniej jednym atomie zwanym atomem ochronnym
• Frontier-guarded Datalog , gdzie dla każdej reguły wszystkie zmienne, które są współdzielone między treścią reguły a jej nagłówkiem (nazywane zmiennymi granicy ) muszą występować razem w atomie ochronnym

Inne ograniczenie dotyczy użycia rekurencji: nierekurencyjny Datalog jest definiowany przez zakazanie rekurencji w definicji programów Datalog. Ten fragment Datalogu jest tak samo wyrazisty jak sumy zapytań spójnych , ale pisanie zapytań jako nierekurencyjnego Datalogu może być bardziej zwięzłe.

Wyrazistość

Problemem ograniczoność dla Datalogu pyta, biorąc pod uwagę program DATALOG, czy jest on ograniczony , czyli maksymalna głębokość rekurencji osiągnięta podczas oceny programu na bazie danych wejściowych może być ograniczona przez pewien stały. Innymi słowy, to pytanie dotyczy tego, czy program Datalog można przepisać na nierekurencyjny program Datalog. Rozwiązanie problemu ograniczeń w dowolnych programach Datalog jest nierozstrzygnięte , ale można je rozstrzygnąć, ograniczając się do niektórych fragmentów Datalogu.

Przykład

Te dwie linie definiują dwa fakty , czyli rzeczy, które zawsze obowiązują:

parent(xerces, brooke).
parent(brooke, damocles).

Oto, co mają na myśli: xerces jest rodzicem brooke, a brooke jest rodzicem damokles . Nazwy są pisane małymi literami, ponieważ łańcuchy zaczynające się od dużej litery oznaczają zmienne.

Te dwie linie definiują reguły , które określają, w jaki sposób nowe fakty można wywnioskować ze znanych faktów.

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

oznaczający:

• X jest przodkiem Y, jeśli X jest rodzicem Y.
• X jest przodkiem Y, jeśli X jest rodzicem niektórych Z, a Z jest przodkiem Y.

Ten wiersz to zapytanie:

?- ancestor(xerces, X).

Zadaje następujące pytanie: Kim są wszyscy X, których Xerces jest przodkiem? To powrót Brooke i DAMOCLES gdy postawione przed systemem DATALOG zawierającej fakty i zasady opisane powyżej.

Więcej o regułach: reguła ma pośrodku symbol :- : część po lewej stronie tego symbolu to głowa reguły, część po prawej to korpus . Reguła brzmi następująco: <head> jest wiadome, że jest prawdziwe, jeśli wiadomo, że <body> jest prawdziwe . Wielkie litery w regułach oznaczają zmienne: w przykładzie nie wiemy, kim są X lub Y , ale niektóre X są przodkami niektórych Y, jeśli ten X jest rodzicem tego Y . Kolejność klauzul w Datalogu nie ma znaczenia, w przeciwieństwie do Prologu, który zależy od kolejności klauzul obliczających wynik wywołania zapytania.

Datalog rozróżnia ekstensjonalne symbole predykatów (zdefiniowane przez fakty) i intensjonalne symbole predykatów (zdefiniowane przez reguły). W powyższym przykładzie ancestorjest to symbol predykatu intensjonalnego i parentjest ekstensjonalny. Predykaty mogą być również definiowane przez fakty i reguły, a zatem nie mogą być czysto ekstensjonalne ani intensjonalne, ale każdy program Datalog może zostać przepisany na równoważny program bez takich symboli predykatów ze zduplikowanymi rolami.

Składnia

Program Datalog składa się z listy faktów i reguł ( klauzule Horn ). Jeśli stała i zmienna są odpowiednio dwoma policzalnymi zestawami stałych i zmiennych, a relacja jest policzalnym zbiorem symboli predykatów , to następująca gramatyka wyraża strukturę programu Datalog:

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

W literaturze atomy są również określane jako literały .

Semantyka

Istnieją trzy powszechnie stosowane podejścia do semantyki programów Datalog: teorie modeli , stałoprzecinkowe i dowodowe .

Teoria modeli

Fakt lub regułę nazywamy podstawą, jeśli wszystkie jej podwarunki są stałymi. Podstawowa reguła R ₁ jest podstawową instancją innej reguły R _{2 ,} jeśli R ₁ jest wynikiem podstawienia stałych dla wszystkich zmiennych w R ₂ .

Baza Herbranda (patrz Herbrand Universe ) programu Datalog to zbiór wszystkich atomów naziemnych, które można utworzyć za pomocą stałych występujących w programie. Interpretacji (znany również jako przykład bazy danych ) jest podzbiorem podstawy Herbrand. Atom ziemi jest prawdziwy w interpretacji I, jeśli jest elementem I . Reguła jest prawdziwa w interpretacji I, jeśli dla każdego podstawowego wystąpienia tej reguły, jeśli wszystkie zdania w ciele są prawdziwe w I , to nagłówek reguły jest również prawdziwy w I .

Modelu programu Datalog P jest interpretacją I z P , który zawiera wszystkie fakty zmielone P , i sprawia, że wszystkie reguły P prawdziwych w I . Semantyka teorii modeli mówi, że znaczeniem programu Datalog jest jego minimalny model (odpowiednik przecięcie wszystkich jego modeli).

Semantyka punktów stałych

Niech ja będę zbiorem interpretacji programu Datalog P (tj. I = P ( H ), gdzie H jest bazą Herbranda P, a P jest operatorem zbioru potęgowego . Zdefiniuj mapę od I do I w następujący sposób: każda reguła w P , jeśli każda klauzula w ciele jest w interpretacji wejściowej, dodaj nagłówek instancji podstawy do interpretacji wyjściowej.Wtedy punkt stały tej mapy jest minimalnym modelem programu. Semantyka punktu stałego sugeruje algorytm obliczania modelu minimalnego: Zacznij od zbioru podstawowych faktów w programie, a następnie wielokrotnie dodawaj konsekwencje reguł, aż do osiągnięcia punktu stałego.

Ocena

Istnieje wiele różnych sposobów oceny programu Datalog o różnych charakterystykach wydajności.

Strategie oceny oddolnej

Strategie ewaluacji oddolnej rozpoczynają się od faktów zawartych w programie i wielokrotnie stosują reguły, aż do ustalenia jakiegoś celu lub zapytania, lub do czasu, gdy zostanie stworzony kompletny minimalny model programu.

Ocena naiwna

Naiwna ocena odzwierciedla semantykę punktów stałych dla programów Datalog. Ocena naiwna wykorzystuje zestaw „znanych faktów”, który jest inicjowany do faktów w programie. Polega na wielokrotnym wyliczaniu wszystkich podstawowych wystąpień każdej reguły w programie. Jeśli każdy atom w ciele instancji podstawowej znajduje się w zbiorze znanych faktów, to główny atom jest dodawany do zbioru znanych faktów. Proces ten jest powtarzany aż do osiągnięcia ustalonego punktu i nie można już wydedukować faktów. Ewaluacja naiwna wytwarza cały minimalny model programu.

Systemy wdrażające Datalog

Oto krótka lista systemów, które są oparte na Datalogu lub udostępniają interpreter Dataloga:

Darmowe oprogramowanie/open source

Niewolne oprogramowanie

• Datomic to rozproszona baza danych zaprojektowana w celu umożliwienia skalowalnych, elastycznych i inteligentnych aplikacji działających w nowych architekturach chmurowych. Używa Datalog jako języka zapytań.
• FoundationDB zapewnia bezpłatne wiązanie bazy danych dla pyDatalog, wraz z samouczkiem na temat jego użycia.
• Leapsight Semantic Dataspace (LSD) to rozproszona dedukcyjna baza danych, która oferuje wysoką dostępność, odporność na błędy, prostotę działania i skalowalność. LSD używa Leaplog (implementacja Datalog) do zapytań i wnioskowania i zostało stworzone przez Leapsight.
• LogicBlox , komercyjna implementacja Datalog używana do internetowych aplikacji do planowania handlu detalicznego i ubezpieczeń.
• Profium Sense to natywna baza danych grafów zgodna z RDF napisana w Javie. Zapewnia obsługę oceny Datalog dla reguł zdefiniowanych przez użytkownika.
• .QL , komercyjny, obiektowy wariant Datalog stworzony przez Semmle do analizy kodu źródłowego w celu wykrycia luk w zabezpieczeniach.
• SecPAL to język polityki bezpieczeństwa opracowany przez Microsoft Research .
• Stardog to grafowa baza danych zaimplementowana w Javie . Zapewnia wsparcie dla RDF i wszystkich profili OWL 2 , zapewniając szerokie możliwości wnioskowania, w tym ocenę dziennika danych.
• StrixDB: komercyjny magazyn grafów RDF, zgodny z SPARQL z Lua API i możliwościami wnioskowania Datalog. Może być używany jako moduł httpd ( Apache HTTP Server ) lub samodzielny (chociaż wersje beta są objęte licencją Perl Artistic License 2.0).

Zobacz też

• Programowanie zestawu odpowiedzi
• Zapytanie łączące
• DLV
• Flix
• SWRL
• Zależność generowania krotek (TGD), język ograniczeń integralności w relacyjnych bazach danych o składni podobnej do Datalog

Bibliografia

Bibliografia

Dalsza lektura

• Gradel, Erich; Kolaitis, Phokion G.; Libkin, Leonid ; Maartena, Marksa; Spencera, Joela ; Vardi, Mosze Y .; Venema, Yde; Weinstein, Scott (2007), Teoria modeli skończonych i jej zastosowania , Teksty w informatyce teoretycznej. Seria EATCS, Berlin: Springer-Verlag , ISBN 978-3-540-00428-8, Zbl  1133.03001