[[
✎ pl:miw:2009:piw09_des
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
===== 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.1252439407.txt.gz
· ostatnio zmienione: 2019/06/27 15:58 (edycja zewnętrzna)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry