AIwiki

Celem tego dokumentu jest omówienie implementacji dedukcyjnego systemu bazodanowego DES, bazującego 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ć nastepują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.

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.

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> ===== 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ęzykow. === 4.1. Rodzina === Rozpoczynamy od klasycznego dla programowania deklaratywnego, przykładu rodziny. == Przykład w języku Datalog / Prolog == 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).

% The above clause for parent is equivalent to:
% 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). 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ł. == Przykład w języku SQL: == /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;''