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 i intuicyjna – 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

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

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.

Po teoretycznych rozważaniach prezentuję kilka praktycznych przykładów programów dla każdego z 3 opisanych językow.

Rozpoczynamy od klasycznego dla programowania deklaratywnego, przykładu rodziny.

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ł.

/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;