\documentstyle[cprog,a4,czech,11pt,boxit]{article}
\title{Princip p�ekladu EDD-Datalogu do SQL}
\author{Karel Je�ek\\
Katedra informatiky a v�po�etn� techniky\\
Z�pado�esk� univerzita, Plze�}
\date{}
\parskip 1mm
\cprogpairsfalse
\begin{document}
\maketitle

\section{�vod}

Aktualni popis naleznete na http://proteus.fav.zcu.cz/groups/db/
Hlavn�m d�vodem, pro� byl vybr�n SQL jako mezijazyk pro 
implementaci deduktivn�ho datab�zov�ho syst�mu, 
je mo�nost pou��t v takov�m p��pad� jako back-end v�konn� 
komer�n� datab�zov� syst�m, a realizovat v podob� preprocesoru 
pouze p�edn� ��st syst�mu.
 
P�eklad fakt� je vzhledem k jejich  p��m� souvislosti s relacemi 
bezprobl�mov�. Na v��n�j�� probl�my nenar���me ani  
v p��pad� p�ekladu nerekurzivn�ch pravidel. 
Posta�uje, uv�dom�me-li si v�znam, kter� m� mno�ina pravidel 
se stejnojmenn�m levostrann�m predik�tem. 
P�edstavuje relaci, jej�� atributy koresponduj� s argumenty 
tohoto predik�tu, a kter� je vyhodnotiteln� z relac� 
determinovan�ch predik�ty prav� strany pravidla.

Pon�kud obt��n�j�� je p�eklad rekurzivn�ch predik�t�. 
Ne�plnost SQL nedovoluje vyjad�ovat itera�n� algoritmy, 
kter� jsou pot�ebn� k v�po�tu relac� koresponduj�c�ch 
rekurzivn�m predik�t�m, tzv. {\bf pevn�ho bodu}. 
Proto�e pr�v� rekurzivn� predik�ty p�edstavuj� 
podstatn� zv�t�en� vyjad�ovac�ch schopnost� oproti 
rela�n�m jazyk�m, je pro u�ite�nost popisovan�ho syst�mu 
realizace jejich p�ekladu nutn�. V tomto p��pad� v�ak mus� 
b�t p�eklad proveden do procedur�ln�ho 
roz���en� SQL (PL SQL v na�em p��pad�).

V dal��m textu je pops�na pouze z�kladn� 
filosofie p�ekladu, bez uveden� detail� implementace. 
P��pustn� tvary p��kaz� EDD-Datalogu a p��klady jeho pou�it� 
jsou uvedeny v dokumentu ``Popis jazyka EDD-Datalog''. 

\section{P�eklad fakt�}

V�echna fakta s predik�tem   {\bf p}  jsou ukl�d�na jako ��dky 
stejn� pojmenovan� datab�zov� tabulky. 
Prv� pr�chod p�ekl�dan�m textem zjist� jm�na predik�t�, 
typy jejich argument� a generuje SQL p��kazy pro vytv��en� tabulek:

\begin{cprog}
	CREATE TABLE jm�no_faktu (	
		ARG1	typ1,
		ARG2	typ2,
		...	...
		);

\end{cprog}

Proto�e jm�na argument�, jejich� prost�ednictv�m budou 
prov�d�ny dotazy na ulo�en� fakta nejsou ze zdrojov�m textu zn�ma, 
p�eklada� odvod� pro n� jm�na z jejich po�ad�:

\begin{quote} 
		ARG1,  ARG2, \ldots
\end{quote}

Napln�n� tabulek  zajist� p��kazy, kter� jsou generovan� pro ka�d� z fakt�:

\begin{quote}
		INSERT INTO jm�no\_faktu VALUES ( \ldots  );
\end{quote}

\section{P�eklad pravidel}

Predik�ty, kter� jsou definov�ny prost�ednictv�m 
rekurzivn�ch pravidel, jsou v c�lov�m tvaru reprezentov�ny tabulkami. 
Zp�sob jejich vytv��en� je uveden ve druh� polovin� t�to ��sti textu. 
Rovn�� pozd�ji bude uveden zp�sob p�ekladu pravidel 
s negovan�mi predik�ty. Pokud predik�ty nejsou rekurzivn�, 
mohou b�t  reprezentov�ny prost�ednictv�m pohled�. 
Pro pravidlo s levou stranou  $t(\ldots{})$  
je generov�n p��kaz vytvo�en� pohledu  $t$,  
jeho� sloupce odpov�daj� argument�m  predik�tu $t$. 
K ur�en� typ� sloupc� vytv��� p�eklada� intern� 
datovou strukturu --- graf z�vislosti predik�t�. 
Jeho uzly reprezentuj� jednotliv� predik�ty. V�tev z uzlu  $q$
vede do uzlu  $p$, obsahuje-li b�ze znalost� pravidlo

\begin{quote}
		p    :-    \ldots{}, q ,\ldots{} .
\end{quote}

Neur�en� jm�na atribut� p�eklada� generuje ve stejn�m tvaru 
jako v p��pad� fakt�. Graf z�vislosti predik�t� je vyu��v�n 
i pro ur�en� po�ad� vyhodnotitelnosti predik�t�. 
Proto�e nov� fakta (koresponduj�c� hlav� pravidla) jsou 
vyhodnocov�na na z�klad� znalosti fakt�, kter� koresponduj� 
predik�t�m z prav� strany pravidla, ud�v� graf z�vislosti 
po�ad� vyhodnocov�n� predik�t� sm�rem od list� ke ko�enu. 

Vyhodnocen� predik�t� (napln�n� relac�) je prov�d�no 
prost�ednicv�m p��kaz� SELECT, kter� p�eklada� generuje 
podle t�chto z�sad:

\begin{itemize}

\item Seznam argument� SELECT je tvo�en jm�ny, 
kter� koresponduj� argument�m z hlavy pravidla.
\item ��st FROM je tvo�ena jm�ny u�ivatelem 
zaveden�ch (deklarovan�ch) predik�t�, kter� se vyskytuj� 
na prav� stran� pravidla.
\item Princip konstrukce WHERE ��sti vyjad�uje cyklus:

\begin{cprog}
FOR p IN prv�..posledn� predik�t prav� strany pravidla LOOP
   IF p je deklarovan� predik�t THEN
      FOR a IN prv�..posledn� argument predik�tu p LOOP
         IF a je prom�nn� THEN
            IF a se ji� d��ve vyskytl jako argument predik�tu q v t�to prav� stran� THEN
	    generuj do where ��sti podm�nku spojen�
		"p.jm�no sloupce = q.jm�no sloupce";
	END IF;
         ELSE generuj do where ��sti podm�nku spojen�
		"p.jm�no sloupce = a";
         END IF;
      END LOOP;
   ELSE  -- p je rela�n� oper�tor t.j. <, >, =, ...
      IF oba argumenty predik�tu p jsou prom�nn� THEN
	generuj do where ��sti podm�nku
		"jm�no sloupce1     oper�tor     jm�no sloupce2";
      ELSE  -- prom�nn� je porovn�v�na s konstantou
	          generuj       "jmeno sloupce      oper�tor    konstanta";
      END IF;
   END IF;
END LOOP;

\end{cprog}
\end{itemize}

Je-li n�kter� predik�t deklarov�n v�ce ne� jedn�m pravidlem, 
v�znam takov�ho z�pisu odpov�d� disjunkci ��ste�n�ch �e�en�. 
Jednotliv� p��kazy SELECT jsou v takov�m p��pad� spojeny 
do jedin�ho dotazu oper�torem  UNION.

V p��pad�, �e logick� program obsahuje rekursivn� pravidla, 
obsahuje graf z�vislosti cykly. K ur�en� po�ad� vyhodnocen� predik�t� 
je nutn� transformovat tento graf na tzv. redukovan� graf, 
ve kter�m je ka�d� siln� souvisl� komponenta p�vodn�ho grafu 
nahra�ena nov�m jedin�m uzlem. Redukovan� graf je acyklick� 
(je to strom), a ve sm�ru od list� ke ko�enu ur�uje 
po�ad� vyhodnocov�n� predik�t�.

\begin{figure}
P�.

\caption{Uk�zka programu a jeho stromu z�vislost�}
\end{figure}


Pokud uzel redukovan�ho grafu reprezentuje nerekurzivn� predik�t, 
je pro n�j generov�n p��kaz SELECT v��e popsan�m zp�sobem. 
Pokud uzel reprezentuje rekurzivn� predik�t, 
�i n�kolik vz�jemn� rekurzivn�ch predik�t�, bude pro 
ka�d� z t�chto predik�t� vytvo�ena tabulka. 
Pro jej� napln�n�  generuje p�eklada� smy�ku v jazyce PL SQL, 
kterou je implementov�n v�po�et pevn�ho bodu seminaivn� metodou. 
Princip v�po�tu je zalo�en na opakovan�ch spojen�ch a p�id�v�n� 
nov� vznikaj�c�ch n-tic.

%Pro ka�dou ze siln� souvisl�ch komponent mus� b�t proto 
%vygenerov�n program v PL-SQL, kter� pro v�echny 
%doty�n� predik�ty (jim p��slu�n� tabulky) prov�d�:
%
%inicializace tabulek s p��ponou   ..._old  po��te�n�mi hodnotami,
%opakovan� prov�d�n� v�po�tu tabulek s p��ponou   ..._new  
%a jejich z�m�na za tabulky 	..._old, 
%dokud doch�z� ke zm�n�m po�tu v nich obsa�en�ch n-tic.


\section{Propojen� s rela�n� datab�z�}

Zp�sob propojen� s ji� existuj�c� datab�z� nen� logicky n�ro�n�. 
Je realizov�n  p�ekladem predik�tu, jeho� jm�no je shodn� se 
jm�nem datab�zov� tabulky a jeho� argumenty ud�vaj� jm�na 
sloupc� a jejich typy. P�eklada� tuto informaci vyu�ije 
pro vytv��en� intern�ch struktur, ve kter�ch uchov�v� jm�na fakt� 
a typ� jejich argument�. Nav�c mus� pouze respektovat p�vodn� 
pojmenov�n� jednotliv�ch sloupc�, kter� se p�en��� 
do v�ech generovan�ch konstrukc�, v nich� se s t�mito tabulkami pracuje.

\section{P�eklad dotazu}

P�eklad dotazu je provediteln� stejn�m zp�sobem 
jako p�eklad pravidla. Jeho tvar je obdobn� 
prav� stran� pravidla a i jeho s�mantika odpov�d� 
s�mantice pravidel, pokud si p�edstav�me dotaz jako pravidlo 
dodate�n� zaveden�ho predik�tu {\em dotaz\/}.

\begin{quote}
	dotaz	 :-     p�vodn� tvar dotazu.
\end{quote}

Zp�sob vytvo�en� jemu odpov�daj�c�ho p��kazu SELECT je pak z�ejm�.

Po�ad� vytv��en� relac�, kter� jsou pot�ebn� k vyhodnocen� 
dotazu je ur�eno grafem z�vislosti predik�t�, 
p��p. jeho redukovanou podobou. Ko�en tohoto stromu 
koresponduje dotazu a jeho listy koresponduj� fakt�m.

\section{P�eklad negovan�ch predik�t�}

Logick� program s negovan�mi predik�ty mus� b�t 
stratifikov�n. Rozum� se t�m, �e nen� p��pustn� pou��t 
v negovan�m tvaru rekursivn� predik�t (negovan� predik�t  
nesm� b�t sou��st� cyklu v grafu z�vislosti predik�t�). 
Pokud by tato podm�nka nebyla spln�na, m��e doj�t k nekone�n�mu 
v�po�tu p�i vyhodnocov�n� pevn�ho bodu.

V�skyt negace ve stratifikovan�m programu m� za 
n�sledek modifikaci generov�n� WHERE ��sti p��kazu SELECT:

\begin{itemize}

\item je-li  sou��st� prav� strany pravidla negovan� predik�t 
$p$ s argumentem  ve tvaru prom�nn� $X$  ($X$ mus� b�t 
argumentem vyskytuj�c�m se i v jin�m, positivn�m predik�tu 
$q$ t�to prav� strany),  generovan� konstrukce bude obsahovat
\begin{quote}
WHERE  NOT EXISTS (SELECT  *  FROM  p  WHERE  p.arg = q.arg)
\end{quote}

\item je-li sou��st� prav� strany negovan� predik�t $p$, 
jeho� argumentem je konstanta $c$, bude ve WHERE ��sti 
generov�na konstrukce:
\begin{quote}
WHERE  NOT  EXISTS  (SELECT *  FROM  p WHERE p.arg = c)
\end{quote}

\item je-li negov�n bin�rn� srovn�vac� predik�t, je generov�n 
do WHERE ��sti s p�edponou NOT.

\end{itemize}

\begin{thebibliography}{99}

\bibitem{ceri}
Ceri S., Gottlob G., Tanca L.:  Logic Programming and Databases.
Springer - Verlag, 1990.

\bibitem{jezek96}
Je�ek K.: Integrace rela�n� datab�ze s b�z� znalost�. 
{\em Proc. Datab�zy96--COFAX\/}, Bratislava, June 1996 (in czech).

\bibitem{jezek96a}
Je�ek K.,  Toncar V.:  Deductive Database Implementation using RDBMS.
{\em Proc. 3-th Int. Workshop AIT 96}, Brno, Sept. 1996.

\bibitem{marti91}
Marti R.:  Research in Deductive Databases at ETH: The LogiQuel Project.
{\em SI-DBTA Proc. Database Research in Switzerland\/}, 
S. Spaccapietra (Ed), 1991.

\end{thebibliography}

\end{document}