Datalog
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
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ą edytuj
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
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
Przypisy edytuj
- ↑ Logic and Data Bases. H. Gallaire, J. Minker (red.). New York: Plemum Press, 1978. ISBN 0-306-40060-X.
- ↑ Strona główna projektu BDDBDDB
- ↑ Strona główna bazy ConceptBase
- ↑ Silnik automatycznego dowodzenia IRIS. [dostęp 2021-05-28]. [zarchiwizowane z tego adresu (2016-03-11)].
- ↑ Datalog Educational System
Bibliografia edytuj
- Serge Abiteboul, Richard W. Hull, Victor Vianu: Foundations of databases. Reading, Mass.: Addison-Wesley, 1995. ISBN 978-0-201-53771-0.
- Stefano Ceri, Georg Gottlob, Letizia Tanca. What You Always Wanted to Know About Datalog (And Never Dared to Ask). „IEEE Transactions on Knowledge and Data Engineering”. 1 (1), s. 146-166, 1989. Piscataway, NJ, USA: IEEE Educational Activities Department. DOI: 10.1109/69.43410. ISSN 1041-4347. (ang.).