Celem tego dokumentu jest omówienie implementacji dedukcyjnego systemu bazodanowego DES, opierającego się na języku Datalog. Największa część uwagi zostanie skupiona na praktycznych cechach narzędzia, jakkolwiek zawarte zostaną także uwagi o charakterze bardziej teoretycznym.
Instalacja narzędzia DES jest wyjątkowo prosta – dla poszczególnych systemów operacyjnych, w przypadku ściągnięcia wersji wykonywalnej, polega po prostu na uruchomieniu pliku wykonywalnego EXE (Windows) bądź głównego skryptu (Linux).
W przypadku systemu operacyjnego MS Windows mamy do wyboru dwie możliwości:
- plik des.exe – uruchomienie DES w standardowej konsoli:
- plik deswin.exe – konsola dedykowana dla Windows:
DES ma postać konsoli, w której wprowadza się poszczególne polecenia. Chociaż przewodnim językiem komunikacji jest Datalog, to jednak istnieje także możliwość używania innych języków – Prologu i SQL. Komendy pozwalające na przełączanie się pomiędzy tymi trzeba językami to:
/datalog
/prolog
/sql
Tego typu komendy pozwalają na permanentne (do czasu kolejnego wpisania kolejnej tego typu komendy) przełączenie się na dany język.
Jeśli natomiast chcemy wpisać tylko jedne polecenie w danym języku, odmiennym od aktualnie używanego, należy wykonać następujące komendy:
/datalog polecenie
/prolog polecenie
/sql polecenie
Taki sposób operowania na trzech językach jednocześnie jest bardzo wygodny i pozwala na wykonywanie różnych czynności w sposób wyjątkowo szybki i wydajny, pozwalając na maksymalną elastyczność w osiągnięciu zamierzonego celu bądź rozwiązaniu jakiegoś problemu, jako że języki SQL oraz Datalog / Prolog cechują się większą elastycznością w trochę innych obszarach, uzupełniając się wzajemnie.
Co więcej, dzięki łatwości w przełączaniu się można bardzo szybko poznać wszystkie trzy języki używane w DES.
Poniższe komendy służą do uzyskania różnego rodzaju przydatnych informacji:
/help – wypisuje listę dostępnych w danej chwili komend
/builtins – wypisuje listę wbudowanych komend i poleceń
Jest to najważniejszy język DES, z którego to narzędzie wywodzi swoją nazwę. Składnia Datalogu jest bardzo podobna do odpowiednika w Prologu, jedyna różnica jest związana z pewnymi niuansami, o których szerzej za chwilę.
Poniżej punktuję ważne elementy składni języka Datalog:
t(t1, t2, …, tn), gdzie: t – symbol funkcyjny (funktor) t1 … tn - termy a(t1, t2, …, tn), gdzie: a – predykat (relacja) t1 … tn – termy f(a1, … an),gdzie: a1 … an – argumenty Jak widać, język Datalog oferuje maksymalny wachlarz możliwości programowania logicznego, od najprostszych i najpopularniejszych elementów do znacznie bardziej wyrafinowanych i rzadziej stosowanych. Nie ustępuje tutaj znacznie takim implementacjom jak chociażby SWI.
Składnia jest zgodna ze standardem SQL.
W obecnej wersji (1.7) systemu DES, istnieją jednakże liczne ograniczenia. Poniżej wypunktowałem ważniejsze z nich:
W odniesieniu do języka Datalog, w SQL'u podjęto dwie decyzje związane z rozróżnianiem wielkości liter:
Implementacja języka SQL w systemie DES jest ukierunkowana na wykorzystanie edukacyjne oraz porównawcze w odniesieniu do języków Datalog / Prolog. W żadnym razie nie powinno być stosowane w celu zarządzania danymi i operowania na jakiejkolwiek bazie danych.
Składnia oraz zasady związane z językiem Prolog są w systemie DES takie same jak dla języka Datalog.
Wspólnym, współdzielonym na identycznych zasadach aspektem każdego z trzech języków systemu DES, są elementy wbudowane. Poniżej opisuję każdy z rodzajów pod kątem składni oraz sposobu bycia wykorzystanym.
Jedynym elementem wbudowanym, który jest różni się w zależności od języka, jest operator porównania „mniejszy lub równy”. W zależności od języka, jego postać jest następująca:
Różnica wynika z faktu, iż w językach Datalog i Prolog operator ten należy odróżnić od operatora implikacji (⇐), a skoro w SQL nie istnieje taki operator, to bardziej naturalne wydaje się zapisanie operatora „mniejszy lub równy” dla tego języka w sposób zgodny z nazwą (⇐).
Operatory dostarczane przez system DES są standardowym zestawem spotykanym w każdym z języków programowania. Należą do nich:
X = Y - testuje równość pomiędzy X i Y. Jeśli chociaż jeden z argumentów X, Y jest zmienną, operator ten staje się odpowiedzialny za operację unifikacji.X \= Y - testuje czy X jest różny od YX > Y - testuje czy X jest większy od YX >= Y - testuje czy X jest większy lub równy YX < Y - testuje czy X jest mniejszy od YX ⇐ Y - testuje czy X jest mniejszy lub równy YNależą do nich:
sin(X) - sinus z Xcos(X) - cosinus z Xtan(X) - tangens z Xcot(X) - cotangens z Xasin(X) - arcus sinus z Xacos(X) - arcus cosinus z Xatan(X) - arcus tangens z Xacot(X) - arcus cotangens z X sqrt(X) - pierwiastek kwadratowy z xlog(X) - logarytm naturalny z Xln(X) - logarytm natuaralny z X. Synonim dla powyższegoabs(X) - wartość bezwzględna z Xsign(X) - funkcja signum z Xgcd(X,Y) - największy wspólny dzielnik X i Ymin(X,Y) - mniejsza z wartości X i Ymax(X,Y) - większa z wartości X i Y float(X) - konwersja wartości X na liczbę zmiennopozycyjnąinteger(X) - konwersja X na wartość całkowitą poprzez obcięcie części po przecinku.truncate(X) - działa jak powyższeround(X) - zaokrąglenie X do najbliższej wartości całkowitej. Jeśli X leży dokładnie pomiędzy dwiema wartościami całkowitymi, jest zaokrąglana w górę.floor(X) - zwraca największą wartość całkowitą mniejszą lub równą Xceiling(X) - zwraca najmniejszą wartość całkowitą większą lub równą XRównież tutaj, podobnie jak w przypadku operatorów porównania, mamy do czynienia ze standardowym zestawem. Jakkolwiek, niektóre z operatorów są oznaczone dość niestandardowymi symbolami, dlatego dla porządku wypunktujmy je wszystkie:
\X - negacja bitowa-X - wartość przeciwna do XX ^ Y - operator potęgowaniaX * Y - mnożenieX / Y - dzielenieX + Y - dodawanieX - Y - odejmowanieX Y - dzielenie całkowite X przez Y
* X rem Y - reszta z dzielenie X przez Y
* X \/ Y - operacja OR w sensie bitowym
* X /\ Y - operacja AND w sensie bitowym
* X # Y - operacja XOR w sensie bitowym
* X « Y - przesunięcie bitowe w lewo X o Y bitów
* X » Y - przesunięcie bitowe w prawo X o Y bitów
== 3.4.4. Stałe arytmetyczne ==
* pi
* e
== 3.4.5. Wykonywanie operacji arytmetycznych ==
Po wypunktowaniu poszczególnych elementów arytmetycznych (funkcji, operatorów i stałych) nadszedł czas na praktyczne omówienie ich stosowania. W języku Datalog używamy zapożyczonego z Prologu wyrażenia is, postaci:
<code>X is expression</code>
Istotne są trzy ograniczenia - zasady:
* X musi być zmienną lub wartością liczbową
* expression musi być wyrażeniem arytmetycznym zbudowanym z liczb, zmiennych, stałych arytmetycznych, funkcji bądź operatorów arytmetycznych
* zmienne używane w expression muszą być zunifikowane z jakimś wartościami na etapie wyliczania wartości expression.
Poniżej podajmy prawidłowe i błędne przykłady stosowania omawianego wyrażenia:
Najpierw dla języka Datalog. Jak widać poniżej, poza oczywistymi wnioskami dotyczącymi używania obliczeń arytmetycznych, w Datalogu wyniki zapytań przetwarzane są jako krotki. Jest to jedna z tych subtelnych różnic pomiędzy Datalogiem i Prologiem.
Następnie prezentujemy analogiczne zapytania dla interpretera Prologu
=== 3.5. Różnice między Datalogiem i Prologiem ===
Jest tylko jedna różnica - dotyczy sposobu traktowania wyników zapytań w każdym z tych języków.
W Datalogu informacja wyjściowa jest traktowana, podobnie jak w SQL, jako zbiór krotek.
W Prologu podejście jest zupełnie inne, podobnego do tego, które znamy z innych implementacji tego języka (np. SWI-Prolog).
=== 3.6. Wnioski ===
Elementy wspólne w naturalny sposób unifikują używanie trzech języków w systemie DES, pozwalając na szybkie i intuicyjne korzystanie z systemu.
===== 4. Porównanie na przykładach =====
Po teoretycznych rozważaniach prezentuję kilka praktycznych przykładów programów dla każdego z 3 opisanych języków.
=== 4.1. Rodzina ===
Rozpoczynamy od klasycznego dla programowania deklaratywnego, przykładu rodziny. W tym przykładzie, wykonamy analogiczne zadanie najpierw w języku Datalog, a następnie w SQL.
== Przykład w języku Datalog / Prolog ==
<code>father(tom,amy).
father(jack,fred).
father(tony,carolII).
father(fred,carolIII).
mother(graceI,amy).
mother(amy,fred).
mother(carolI,carolII).
mother(carolII,carolIII).
parent(X,Y) :-
father(X,Y)
;
mother(X,Y).
% Powyzsze jest rownowazne z zapisem:
% parent(X,Y) :-
% father(X,Y).
% parent(X,Y) :-
% mother(X,Y).
ancestor(X,Y) :-
parent(X,Y).
ancestor(X,Y) :-
parent(X,Z),
ancestor(Z,Y). </code>
Jak widzimy w tym przypadku, składnia jest identyczna zarówno dla Prologu, jak i Datalogu.
DES pozwala na zapis alternatywy w jednej regule – jest to równoważne z klasycznym zapisem za pomocą dwóch reguł.
Wykorzystajmy jakoś nasz powyższy kod. Zapiszmy go w pliku family.dl:
Najpierw wczytajmy plik z kodem:
<code> /c family</code>
Następnie znajdźmy wszystkie osoby, których przodkiem jest tom:
<code>ancestor(tom,X)</code>
Widzimy po raz kolejny, że Datalog operuje na krotkach.
== Przykład w języku Prolog ==
Jako że składnia Prologu jest taka sama jak Datalogu, podajmy od razu rozwiązanie problemu:
Widać wyraźnie, że Prolog różni się od Datalogu sposobem operowania na rezultatach działania.
== Przykład w języku SQL: ==
<code>/sql
create table father(father,child);
insert into father values('tom','amy');
insert into father values('jack','fred');
insert into father values('tony','carolII');
insert into father values('fred','carolIII');
create table mother(mother,child);
insert into mother values('graceI','amy');
insert into mother values('amy','fred');
insert into mother values('carolI','carolII');
insert into mother values('carolII','carolIII');
create view parent(parent,child) as select * from father union select * from mother;
create or replace view ancestor(ancestor,descendant) as select parent,child from parent union select parent,descendant from parent,ancestor where parent.child=ancestor.ancestor;
select * from ancestor where ancestor='tom';
select child,father,mother from father,mother where father.child=mother.child;</code>
Także i tutaj sprawdźmy działanie kodu w praktyce. Najpierw załadujmy plik z kodem sql:
<code>/process family.sql</code>
A potem:
=== 4.2. Gramatyki ===
Kolejny problem będzie bardzo odmienny od poprzedniego - spróbujemy zapisać w Datalogu, z użyciem systemu DES, prosty parser działający od lewej do prawej rekursywnie wedle formuły:
A → a
A → Ab
A → Aa
Pierwszym zagadnieniem do rozwiązania jest sposób zapisu łańcucha wejściowego tak, by móc odczytać z niego każdy token z osobna razem z jego pozycją początkową i końcową. Pod pojęciem token rozumiemy tutaj dowolny podłańcuch łańcucha wejściowego.
Rozwiązaniem jest relacja
t(F,T,L)''
gdzie:
F - pozycja początkowa tokenu,
T - token
L - pozycja końcowa tokenu
Ustalmy, że łańcuch wejściowy ma postać „ababa”. Zakodujmy go z użyciem powyższego:
<code>t(1,a,2).
t(2,b,3).
t(3,a,4).
t(4,b,5).
t(5,a,6).</code>
Następnie zapiszmy formułę parsera dla powyższego łańcucha:
<code>a(F,L) :- t(F,a,L).
a(F,L) :- a(F,M), t(M,b,L).
a(F,L) :- a(F,M), t(M,a,L).</code>
=== 4.3. Ciąg Fibonacciego ===
W następnym przykładzie przyjrzymy się sposobowi rozwiązania ciągu Fibonacciego.
Najpierw zdefiniowanie początkowych wartości ciągu:
<code>fib(0,1).
fib(1,1).</code>
Następnie formuła wyznaczająca kolejne:
<code>fib(N,F) :-
N > 1,
N2 is N - 2,
fib(N2, F2),
N1 is N - 1,
fib(N1, F1),
F is F2 + F1.</code>
Na sam koniec przykład działania:
=== 4.4. Wieże Hanoi oraz tablice rozszerzeń DES===
Rozwiążmy problem wież hanoi. Będzie to jednocześnie pokazanie działania tablicy rozszerzeń systemu DES, przechowującej poszczególne etapy rozwiązywania danego zagadnienia.
Najpierw kod w Datalogu:
<code>hanoi(1,A,B,C).
hanoi(N,A,B,C) :-
N > 1,
N1 is N - 1,
hanoi(N1,A,C,B),
hanoi(N1,C,B,A).</code>
Przykład działania dla 10 dysków:
Okazuje się, że wynik nie odzwierciedla ilości przełożeń. Aby zobaczyć faktyczną drogę do wyniku końcowego, należy wywołać DES'ową tablicę rozszerzeń:
część pierwsza, dotycząca odpowiedzi z systemu DES:
część druga, dotycząca wywołań systemu DES:
=== 4.5. Relacje ===
Zanalizujmy bardziej złożony przykład, pokazujący jak imitować polecenia SQL za pomocą Datalogu. Będzie to
przyklad testujący możliwości DES pod kątem współdziałania różnego rodzaju języków, oraz tego, czy faktycznie
można je stosować mniej więcej wymiennie.
Przedstawmy polecenia SQL razem z analogami w Datalogu:
== Tworzenie tabel i wstawianie wartości ==
<code>% Najpierw tworzymy tabele
create or replace table a(a);
create or replace table b(b);
create or replace table c(a,b);
% Listujemy powyższe zależności
/dbschema
% Dodajemy rekordy do tabeli
insert into a values ('a1');
insert into a values ('a2');
insert into a values ('a3');
insert into b values ('b1');
insert into b values ('b2');
insert into b values ('a1');
insert into c values ('a1','b2');
insert into c values ('a1','a1');
insert into c values ('a2','b2');</code>
Odpowiednik w Datalogu, łączący tworzenie tabel oraz wstawianie rekordów:
<code>a(a1).
a(a2).
a(a3).
b(b1).
b(b2).
b(a1).
c(a1,b2).
c(a1,a1).
c(a2,b2).</code>
== Projekcja ==
Kod SQL:
<code>
% Testujemy operację projekcji
select a from c;</code>
Kod Datalog:
<code>projection(X) :- c(X,Y).</code>
== Selekcja z kryterium ==
Kod SQL:
<code>% Selekcja z pewnym kryterium
select a from a where a='a2';</code>
Kod Datalog:
<code>selection(X) :- a(X), X=a2.</code>
== Iloczyn kartezjański ==
Kod SQL:
<code>% Iloczyn kartezjański
select * from a,b;</code>
Kod Datalog:
<code>cartesian(X,Y) :- a(X), b(Y).</code>
== Inner Join ==
Kod SQL:
<code>% złączenie typu inner join
select a from a inner join b on a.a=b.b;</code>
Kod Datalog:
<code>inner_join(X) :- a(X), b(X).</code>
== Left Join ==
Kod SQL:
<code>% złączenie typu left join
select * from a left join b on a.a=b.b;</code>
Kod Datalog:
<code>left_join(X,Y) :- lj(a(X), b(Y), X=Y).</code>
== Right Join==
Kod SQL:
<code>% złączenie typu right join
select * from a right join b on a.a=b.b;</code>
Kod Datalog:
<code>right_join(X,Y) :- rj(a(X), b(Y), X=Y).</code>
== Full join ==
Kod SQL:
<code>% złączenie typu full foin
select * from a full join b on a.a=b.b;</code>
Kod Datalog:
<code>full_join(X,Y) :- fj(a(X), b(Y), X=Y).</code>
== Union ==
Kod SQL:
<code>% złączenie typu unia
select * from a union select * from b;</code>
Kod Datalog:
<code>union(X) :- a(X) ; b(X).</code>
== Różnica ==
Kod SQL:
<code>% Testujemy operację select z kryterium różnicy
select * from a except select * from b;</code>
Kod Datalog:
<code>difference(X) :- a(X), not(b(X)).</code>
== Relacje w Datalog i SQL ==
Ważnym aspektem systemu DES jest fakt, iż mimo że polecenia w SQL i Datalog można stosowac wymiennie i przeplatać
je ze sobą, to jednak relacji utworzonych w Datalog nie można używać od razu jako tabeli w SQL.
Przyjrzyjm się powyższemu kodowi. Załóżmy, że utworzyliśmy w Datalogu relacje:
<code>a(a1).
a(a2).
a(a3)</code>
Nie możemy po prostu użyć jej w SQL za pomocą, np., polecenia:
<code>/sql select * from a;</code>
Musimy WPIERW utworzyć analogiczną tabelę w SQL:
<code>/sql
create table a(a)</code>
I dopiero teraz spróbować powyższej operacji. Całość obrazuje poniższy przykład.
Zakładamy, że wczytaliśmy już całość powyższego kodu do systemu DES.
===== 5. Wnioski końcowe =====
System DES jest bardzo skutecznym systemem edukacyjnym, posiadającym liczne walory. Zaliczamy do nich:
* Efektywny sposób poznania trzech języków: Datalogu, Prologu i SQL, poprzez możliwość rozwiązywania problemów niemal natychmiast w każdym z trzech języków
* Prostota użytkowania
* Szeroki wachlarz możliwości w przypadku języka Datalog / Prolog
Nawet limitowana implementacja SQL ma swoje zalety - DES ma służyć jako system edukacyjny, a nie typowy transakcyjny DBMS, czyli przede wszystkim powinien być mały i szybki, co byłoby niemożliwe w przypadku pełnej implementacji całego standardu SQL.
