Datalog

Datalog – język zapytań wzorowany na języku Prolog stosowany dla dedukcyjnych baz danych. Oparty jest na metodach wnioskowania znanych z logik formalnych. Składa się z aksjomatów oraz reguł wnioskowania. Początki Datalogu związane są z początkami programowania logicznego. Za twórcę terminu Datalog uznawany jest David Maier. Rozwinięciem tego terminu jest określenie database logic – z ang. „logika baz danych“.

Nie jest możliwe wskazanie konkretnej grupy twórców samego języka, gdyż w różnych publikacjach pojawiał się jako okrojenie bądź rozszerzenie innych języków i modeli obliczeniowych. Historia Datalogu jako niezależnej dziedziny badań naukowych związana jest z warsztatami poświęconymi logice i bazom danych, które zostały zorganizowane w 1977 roku przez Hervé’a Gallaire i Jacka Minkera.

Datalog cieszył się największą popularnością od połowy lat 80. do połowy 90., ale nawet współcześnie jest używany jako język zapytań w projektach badawczych i implementacjach dedukcyjnych baz danych.

Konstrukcja języka

Datalog jest postrzegany często jako język zbudowany z klauzul Horna, w których nie występują symbole funkcyjne. Program w Datalogu (podobnie jak w Prologu) składa się z reguł typu „jeżeli-to”, w skład których wchodzą predykaty (nazwy funkcji logicznych), atomy relacyjne (predykat i jego argumenty) oraz atomy arytmetyczne (wyrażenia arytmetyczne wraz z argumentami).

Każda reguła składa się z: nagłówka – atomu relacyjnego symbolu ← – zwykle czytanego jako słowo „jeżeli" treści – jednego lub więcej atomów relacyjnych bądź arytmetycznych zwanych podzdaniami połączonych spójnikami logicznymi AND („i”) oraz OR („lub”)

Przykładami reguł w Datalogu są: JestSynem(X,Y) ← JestMężczyzną(X) AND JestRodzicem(Y,X) DroższyProdukt(X,Y) ← ProduktNaStanie(X,Cena1) AND ProduktNaStanie(Y,Cena2) AND Cena1 > Cena2

Jedną z częściej podkreślanych właściwości Datalogu jest istnienie trzech równoważnych (choć znacząco różniących się) podejść do definiowania semantyki programu. Te trzy podejścia to: semantyka teoriomodelowa semantyka stałopunktowa semantyka dowodowa

W podejściu teoriomodelowym reguły postrzegane są jako zdania logiczne pierwszego rzędu określające właściwości docelowej zależności. W tym podejściu bazując na wejściowym zbiorze predykatów (zwanych predykatami ekstensjonalnymi) dedukujemy zbiór predykatów wynikających z zadanych reguł Datalogu (predykaty intensjonalne) – zbiór ten określany jest mianem modelu. Ponieważ takich modeli jest wiele, wynikowy model musi być modelem minimalnym.

W podejściu stałopunktowym idea polega na rozpoczęciu od jednej lub kilku znanych odgórnie relacji (predykatów ekstensjonalnych). Pozostałe predykaty definiowane są w nagłówkach reguł. Predykaty te obliczane są rekurencyjnie rozpoczynając od przypisania im wartości pustych, a następnie w kolejnych krokach dołączając do nich nowe wartości wyliczane przez stosowanie reguł do predykatów ekstensjonalnych i wartości wyliczonych w poprzednich krokach. Postępowanie kończymy wówczas, gdy nie powstają już nowe elementy.

W podejściu dowodowym zakładamy, że na wejściu dostajemy bazę faktów, zaś odpowiedzią na zadany program Datalogu jest zbiór faktów, które można udowodnić bazując na tych faktach i regułach tego programu. Wśród metod „dowodzenia” nowego faktu są m.in. metoda tworzenia tzw. drzewa dowodowego oraz metoda SLD rezolucji.

Przykładowym programem w Datalogu jest; I={Film(„Seksmisja”,1983,"Juliusz Machulski”,120), Film(„Anioły i Demony”,2009,"Ron Howard”,138), Film(„Ronin”,1998,"John Frankenheimer”,121), Film(„Kod da Vinci”,2006,"Ron Howard”,149), GrałW(„Kod da Vinci”, „Tom Hanks”), GrałW(„Kod da Vinci”, „Jean Reno”), GrałW(„Anioły i Demony”, „Tom Hanks”), GrałW(„Ronin”,"Jean Reno”), GrałW(„Seksmisja”,"Jerzy Stuhr”)} gdzie I to zbiór predykatów intensjonalnych (instancja początkowej bazy danych)

Datalog z negacją

Ponieważ podstawowa struktura Datalogu nie uwzględnia negacji, przydatnej w rzeczywistych aplikacjach, z punktu widzenia teoretycznego powstało wiele rozszerzeń początkowej teorii. W większości z nich przewijają się dwie ugruntowane terminologie: Program semi-pozytywny – program Datalogu, w którym dopuszczamy negację tylko przed predykatami ekstensjonalnymi (definiowanymi poprzez reguły) Stratyfikacja (warstwowanie) – podział programu na warstwy/podprogramy, które są programami semi-pozytywnymi albo z nich wynikają

Popularne implementacje Większość implementacji Datalogu wywodzi się ze środowisk akademickich i zawiera rozszerzenia Datalogu o pewną formę negacji.

BDDBDDB – implementacja Datalogu rozwijana na Stanford University używana do tworzenia zapytań dotyczących kodu bajtowego JavyStrona główna projektu BDDBDDB ConceptBase – obiektowo – dedukcyjna baza danych używająca Datalogu jako języka zapytań. W zamierzeniach platforma do tworzenia modeli koncepcyjnychStrona główna bazy ConceptBase IRIS – silnik systemu automatycznego dowodzenia na licencji Open-source wyposażony w mechanizm kontroli typów. Język zapytań jest wersją Datalogu rozszerzoną m.in. o symbole funkcyjne, wbudowane predykaty oraz możliwość obejścia „warunku bezpieczeństwa” DES – implementacja języka Datalog w Prologu na licencji Open-sourceDatalog Educational System pyDatalog – implementacja Datalogu w Pythonie

Przypisy

Bibliografia

Kategoria:Języki zapytań