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:

• Termy
  
  Podstawowe i najbardziej ogólne obiekty występujące w Datalogu. Dzielą się na dwie grupy:
  
  
  • Termy proste
    
    Podgrupa, dzieląca się na kolejne dwa rodzaje:
    
    
    • Stałe:
      
      
      • Stałe znakowe
        
        Mogą być dwojakiego rodzaju:
        • dowolny ciąg znaków alfanumerycznych (znaki alfabetu, liczby, znak podkreślenia _), rozpoczynający się od małej litery.
        • dowolny ciąg znaków alfanumerycznych oraz znaków białych, ograniczonony pojedynczymi cudzysłowami.
          
          
      • Liczby
        
        Wyróżniamy dwa rodzaje liczb w Datalogu:
        
        
        • Liczby całkowite
          
          Nie mogą występować w notacji wykładniczej, wartości ujemne zaczynają się minusem, wartości dodatnie NIE mogą zaczynać się od plusa, co ilustruję poniższym przykładem:
          
          
          
          
        • Liczby zmiennopozycyjne
          
          Mogą występować w notacji naukowej, w postaci aEb
          
          a jest ZAWSZE liczbą zmiennopozycyjną, natomiast b to liczba całkowita, która tylko w tym wypadku (jako wykładnik w notacji naukowej) może rozpoczynać się plusem.
          
          Pokazuje to poniższy przykład:
          
          
          
          
    • Zmienne
      
      Oznaczamy je ciągiem znaków alfanumerycznych, rozpoczynającym się od:
      • dużej litery,
      • znaku podkreślenia
        
        Sam znak podkreślenia oznacza zmienną anonimową. Należy zwrócić uwagę, że wystąpienie zmiennej anonimowej w jakiejś formule jest uznawane za różne od jakiegokolwiek innego wystąpienia zmiennej anonimowej.
        
        
  • Termy złożone
    
    W Datalogu mają postać:
    t(t1, t2, …, tn), gdzie:
    
    t – symbol funkcyjny (funktor)
    t1 … tn - termy
    
    

• Atomy
  
  Są to wyrażenia postaci:
  a(t1, t2, …, tn), gdzie:
  
  a – predykat (relacja)
  t1 … tn – termy
  
  
• Wyrażenie warunkowe
  
  Jest to wyrażenie logiczne zawierające:
  • conjunctions (/2)
  • disjunctions (; /2)
  • wbudowane operatory porównania
  • stałe
  • zmienne
    
    
• Funkcje
  
  f(a1, … an),gdzie:
  
  a1 … an – argumenty
  
  Dostępny jest tylko ograniczony zbiór funkcji wbudowanych

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:

• brak funkcji agregujących (min, max, avg)
• brak grupowania (group by)
• brak klauzuli order by
• brak więzów bazodanowych, takich jak klucze podstawowe w tabeli
• brak podstawowych operacji na widokach (insert / update / delete)
• brak informowania o występujących błędach w składni polecenia
• brak możliwości wpisywania wielolinijkowych komend

W odniesieniu do języka Datalog, w SQL'u podjęto dwie decyzje związane z rozróżnianiem wielkości liter:

• podobnie jak w języku Datalog, w identyfikatorach zdefiniowanych przez użytkownika wielkość liter ma znaczenie. Jest to niezgodne z tendencją występującą w klasycznych systemach DBMS.
• w odróżnieniu do języka Datalog, we wbudowanych identyfikatorach wielkość liter nie ma znaczenia. Jest to w zgodzie z obecną tendencją występującą w klasycznych systemach DBMS.

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:

• SQL - postać ⇐
• Datalog / Prolog - postać =<

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 Y
• X > Y - testuje czy X jest większy od Y
• X >= Y - testuje czy X jest większy lub równy Y
• X < Y - testuje czy X jest mniejszy od Y
• X ⇐ Y - testuje czy X jest mniejszy lub równy Y

Należą do nich:

• Funkcje trygonometryczne
  
  
  • sin(X) - sinus z X
  • cos(X) - cosinus z X
  • tan(X) - tangens z X
  • cot(X) - cotangens z X
  • asin(X) - arcus sinus z X
  • acos(X) - arcus cosinus z X
  • atan(X) - arcus tangens z X
  • acot(X) - arcus cotangens z X
    
    
• Różne funkcje arytmetyczne
  
  
  • sqrt(X) - pierwiastek kwadratowy z x
  • log(X) - logarytm naturalny z X
  • ln(X) - logarytm natuaralny z X. Synonim dla powyższego
  • abs(X) - wartość bezwzględna z X
  • sign(X) - funkcja signum z X
  • gcd(X,Y) - największy wspólny dzielnik X i Y
  • min(X,Y) - mniejsza z wartości X i Y
  • max(X,Y) - większa z wartości X i Y
    
    
• Funkcje konwersji i zaokrąglania
  
  
  • 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ższe
  • round(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ą X
  • ceiling(X) - zwraca najmniejszą wartość całkowitą większą lub równą X

Ró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 X
• X ^ Y - operator potęgowania
• X * Y - mnożenie
• X / Y - dzielenie
• X + Y - dodawanie
• X - Y - odejmowanie
• X 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.