AIwiki

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: ===== 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.