--- pl:miw:2009:piw09_des [2009/09/08 21:50]
piw09
+++ pl:miw:2009:piw09_des [2019/06/27 15:50]
@@ Linia 1: / Linia 1: @@
-===== 1. Wstęp =====
-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.
-===== 2. Informacje wstępne =====
-=== 2.1. Uwagi odnośnie instalacji ===
-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).
-== 2.1.1. MS Windows ==
-W przypadku systemu operacyjnego MS Windows mamy do wyboru dwie możliwości:
-- plik des.exe – uruchomienie DES w standardowej konsoli:
-{{:pl:miw:2009:windows_konsola_zwykla.png|}}
-- plik deswin.exe – konsola dedykowana dla Windows:
-{{:pl:miw:2009:windows_konsola_dedykowana.png|}}
-=== 2.2. Uwagi o różnych językach ===
-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''
-== 2.2.1. Wnioski ==
-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.
-=== 2.3. Pomoc ===
-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ń
-===== 3. Opis działania poszczególnych języków =====
-=== 3.1. Datalog ===
-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: \\ \\ {{:pl:miw:2009:3_1_liczby_calkowite.png|}} \\ \\
-          * **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: \\ \\ {{:pl:miw:2009:3_1_liczby_zmiennopozycyjne.png|}} \\ \\
-      * **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
-== 3.1.1. Wnioski ==
-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.
-=== 3.2. SQL ===
-Składnia jest zgodna ze standardem SQL.
-== 3.2.1. Ograniczenia ==
-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
-== 3.2.2. Wielkość liter ==
-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.
-== 3.2.3. Wnioski ==
-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.
-=== 3.3. Prolog ===
-Składnia oraz zasady związane z językiem Prolog są w systemie DES takie same jak dla języka Datalog.
-=== 3.4. Elementy wspólne ===
-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ą (<=).
-== 3.4.1. Operatory porównania ==
-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
-== 3.4.2. Funkcje ==
-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
-== 3.4.3. Operatory arytmetyczne ==
-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.
-{{:pl:miw:2009:3_4_5_1.png|}}
-Następnie prezentujemy analogiczne zapytania dla interpretera Prologu
-{{:pl:miw:2009:3_4_5_2.png|}}
-=== 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>
-{{:pl:miw:2009:4_1_1.png|}}
-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:
-{{:pl:miw:2009:4_1_2.png|}}
-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:
-{{:pl:miw:2009:4_1_3.png|}}
-=== 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:
-{{:pl:miw:2009:4_3_1.png|}}
-=== 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:
-{{:pl:miw:2009:4_4_1.png|}}
-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:
-{{:pl:miw:2009:4_4_2.png|}}
-część druga, dotycząca wywołań systemu DES:
-{{:pl:miw:2009:4_4_3.png|}}
-===== 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.

pl/miw/2009/piw09_des.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)

Pokaż stronę Poprzednie wersje

Menadżer multimediów Do góry

AIwiki

Menu

Dla Studentów

Old specialized AI courses

SMaDA/SMaIDA/AIDA

Informatyka (EAIiIB)

Studia Dr

Inne materialy dydaktyczne

Archiwum

Dyplomanci

Geist Season of Code

HeKatE

Public

Różnice