Datalog

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Datalog – język zapytań wzorowany na języku Prolog stosowany dla dedukcyjnych baz danych. Oparty jest o metody wnioskowania znane 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 [1].

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[edytuj | edytuj kod]

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:

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ą[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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 Javy [2]
  • ConceptBase - obiektowo - dedukcyjna baza danych używająca Datalogu jako języka zapytań. W zamierzeniach platforma do tworzenia modeli koncepcyjnych [3]
  • 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” [4]
  • DES - implementacja języka Datalog w Prologu na licencji Open-source [5]
  • pyDatalog - implementacja Datalogu w Pythonie


Bibliografia[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]