\documentstyle[cprog,a4,czech,11pt,boxit]{article}
\title{Experiment�ln� deduktivn� datab�ze: \\
Popis jazyka EDD-Datalog
}
\author{Vladim�r Toncar\\
Katedra informatiky a v�po�etn� techniky\\
Z�pado�esk� univerzita, Plze�}
\date{}
\parskip 1mm
\cprogpairsfalse
\begin{document}
\maketitle

\section{�vod}
Experiment�ln� deduktivn� datab�ze (zkr�cen� EDD) je projekt 
zpracov�van� na Kated�e informatiky a v�po�etn� techniky 
Z�pado�esk� univerzity v Plzni.
C�lem projektu je vytvo�it deduktivn� datab�zi
jako nadstavbu nad rela�n�m datab�zov�m syst�mem.

V�raznou v�hodou vyu�it� ji� existuj�c� rela�n� datab�ze
je mo�nost soust�edit se pouze na �e�en� deduktivn� ��sti cel�ho syst�mu. 
Dal��m d�vodem pro v�b�r tohoto p��stupu je roz���enost rela�n�ch datab�z�.
Objemy dat shrom��d�n� v t�chto syst�mech jsou velmi velk�.
Mo�nost vyhodnocovat deduktivn� programy 
i nad t�mito daty je velmi zaj�mav�.

Logick� jazyk, kter� na�e Experiment�ln� deduktivn� datab�ze pou��v�,
je odvozen od Datalogu. Ozna�ujeme jej n�zvem EDD-Datalog. Roz���en� oproti
Datalogu spo��vaj� v za�azen� negace a agrega�n�ch funkc� a v mo�nosti 
pracovat s extern�mi relacemi. V budoucnu bude EDD-Datalog d�le roz�i�ov�n.

Propojen� EDD-Datalogu s rela�n�m datab�zov�m syst�mem je prozat�m vy�e�eno
jen velmi voln�, prost�ednictv�m p�eklada�e EDD-Datalogu.
Rela�n�m datab�zov�m syst�mem, kter� pou��v�me, je Oracle 7.
V�stupem p�eklada�e EDD-Datalogu 
je soubor s programem v datab�zov�m jazyce SQL.
Tento program je t�eba spustit v rela�n� datab�zi. Program obsahuje
akce pot�ebn� pro vyhodnocen� logick�ho programu ve sm�ru zdola nahoru.

\section{Definice a terminologie}

Programy v EDD-Datalogu sest�vaj� z prom�nn�ch, konstant, funk�n�ch
a predik�tov�ch symbol� a logick�ch spojek pro konjunkci, negaci
a implikaci. Prom�nn� jsou reprezentov�ny identifik�tory za��naj�c�mi
velk�m p�smenem. Konstanty jsou ��sla a �et�zce znak�. �et�zce znak�
se uzav�raj� do apostrof�. Lze pou��vat i �et�zce znak� bez apostrof�,
takov� �et�zec v�ak mus� za��nat mal�m p�smenem a nesm� obsahovat mezeru.

Funk�n� a predik�tov� symboly jsou p�edstavov�ny indentifik�tory, kter�
za��naj� mal�mi p�smeny. S funk�n�mi a predik�tov�mi symboly je spojena
arita, kter� ud�v� po�et jejich argument�. Konjunkce je p�edstavov�na
��rkou \csprimesoff ``,'', negace slovem ``not''. Implikace je
reprezentov�na symbolem ``:-''. \csprimeson

{\bf Term} je definov�n takto:
\begin{itemize}
\item prom�nn� je term;
\item konstanta je term;
\item jsou-li $t_{1}, t_{2}$ termy, kter� nejsou �et�zce
znak� nebo prom�nn� reprezentuj�c� �et�zce znak�, 
pak i $t_{1} + t_{2}$, $t_{1} - t_{2}$, $t_{1} * t_{2}$,
$t_{1} / t_{2}$ a $(t_{1})$
jsou termy. 
\end{itemize}

Term, kter� nen� prom�nnou nebo konstantou, se naz�v� {\bf slo�en�} term.
Term, kter� neobsahuje prom�nn�, se naz�v� {\bf z�kladn�} term.

Je-li $p$ predik�tov� symbol s aritou $n$ a $t_{1},\ldots , t_{n}$
jsou termy, pak $p(t_{1},\ldots , t_{n})$ je {\bf atom}.
Atom nebo negovan� atom se naz�v� {\bf liter�l}. 
Nenegovan� atom je {\bf pozitivn� liter�l}, negovan� atom je 
{\bf negativn� liter�l}.

{\bf Pravidlo} pro predik�t $p$ s aritou $n$ m� tvar:
\begin{displaymath}
p(t_{1},\ldots , t_{n}) \ :- \ L_{1},\ldots , L_{m}.
\end{displaymath}
kde ka�d� $L_{i}$ je liter�l. Jestli�e $m = 0$, pak se pravidlo zapisuje jako
\begin{displaymath}
p(t_{1},\ldots , t_{n}).
\end{displaymath}
a jestli�e neobsahuje ��dn� prom�nn�, naz�v� se {\bf fakt}.

Predik�t je v logick�m programu definov�n jedn�m nebo v�ce pravidly.
Predik�ty se rovn�� n�kdy naz�vaj� {\bf relace}.

Mno�ina fakt� se naz�v� {\bf extenzion�ln� datab�ze} (EDB). Mno�ina pravidel
v programu tvo�� {\bf intenzion�ln� datab�zi} (IDB).
Predik�ty definovan� v~extenzion�ln� datab�zi 
se n�kdy naz�vaj� {\bf z�kladn�}.
O predik�tech definovan�ch v datab�zi intenzion�ln� se hovo�� jako
o {\bf odvozen�ch}.

V rela�n�m datab�zov�m syst�mu jsou predik�ty reprezentov�ny
jako relace (datab�zov� tabulky) nebo jako pohledy ({\em views\/}).
Pohledy se pou��vaj� pro nerekurz�vn� predik�ty, datab�zov� relace
pro predik�ty rekurz�vn� (p��mo �i nep��mo) 
a pro predik�ty z extenzion�ln� datab�ze. 
Pro urychlen� v�po�tu m��e b�t n�kdy v�hodn�
reprezentovat i nerekurz�vn� predik�t jako datab�zovou tabulku.
Tuto mo�nost chceme za�adit do dal�� verze p�eklada�e EDD-Datalogu.

\section{Prvn� p��klad}

Abychom si uk�zali pou�it� p�eklada�e, vezmeme jednoduch� a �asto
pou��van� p��klad: program pro hled�n� cesty v neorientovan�m grafu.
Program je uveden na obr. \ref{path.d}.

\begin{figure}
\begin{boxit}
\begin{cprog}

	e(1,2).
	e(1,3).
	e(1,4).
	e(3,4).
	e(5,6).
	e(5,7).

	edge(A,B) :- e(A,B).
	edge(A,B) :- e(B,A).

	path(A,B) :- edge(A,B).

	path(A,B) :- edge(A,C), path(C,B).


\end{cprog}
\end{boxit}
\caption{Hled�n� cesty v neor. grafu (soubor path.d)} \label{path.d}
\end{figure}

Abychom pon�kud zkr�tili z�pis programu, predik�t $e$ 
p�edstavuje hrany {\em orientovan�ho\/} grafu.
Neorientovan� hrany jsou definov�ny odvozen�m predik�tem $edge$.
Predik�t pro nalezen� cesty ($path$) je definov�n b��n�m rekurz�vn�m
zp�sobem.

P�eklad tohoto programu (um�st�n�ho v souboru path.d) se provede p��kazem
\begin{quote}
{\tt > edd path.d}
\end{quote}

P�eklada� vytvo�� tri soubory. Prvn� z nich, soubor prog.sql,
obsahuje p��kazy SQL pro vyhodnocen� logick�ho programu v rela�n�
datab�zi. Druh� soubor se jmenuje drop.sql. S jeho pomoc� lze po
skon�en� pr�ce odstranit z datab�ze relace a pohledy vznikl� b�hem
v�po�tu. Treti se jmenuje goal.sql a spousti vypocet dotazu.

Spu�t�n� souboru *.sql v datab�zi je velmi jednoduch�.
Vyvol�me oraclovsk� program {\tt sqlplus} a v n�m vyd�me p��kaz:
\begin{quote}
{\tt > @prog.sql}	
\end{quote}

V�sledek v�po�tu, tj. v�echny cesty v grafu, budou obsa�eny v datab�zov�
tabulce $path$.

\begin{figure}
\begin{boxit}
\begin{cprog}

	create table e(Attr_0 integer,Attr_1 integer);
	insert into e values(1,2);
	insert into e values(1,3);
	insert into e values(1,4);
	insert into e values(3,4);
	insert into e values(5,6);
	insert into e values(5,7);

	create view edge as
	select distinct e0.Attr_0 Attr_0,e0.Attr_1 Attr_1
		from e e0
	UNION
	select distinct e0.Attr_1 Attr_0,e0.Attr_0 Attr_1
		from e e0;

	create table path(Attr_0 integer,Attr_1 integer);

	insert into path
	select distinct edge0.Attr_0,edge0.Attr_1
		from edge edge0;

	DECLARE
	c number;
	BEGIN
	LOOP
	c := 0;
	insert into path
	select distinct edge0.Attr_0,path0.Attr_1
		from edge edge0,path path0
		where edge0.Attr_1=path0.Attr_0
		and (edge0.Attr_0,path0.Attr_1) 
		not in (select Attr_0,Attr_1 from path);
	c := c + SQL%ROWCOUNT;
	COMMIT;
	IF c = 0 THEN EXIT; END IF;
	END LOOP;

	EXCEPTION
	  WHEN OTHERS THEN ROLLBACK;
	END;
	/

\end{cprog}
\end{boxit}
\caption{P�elo�en� tvar programu} \label{prog.sql}
\end{figure}

Obsah souboru path.sql je uveden na obr. \ref{prog.sql}.
Logick� program je vyhodnocov�n ve sm�ru zdola nahoru.
Datab�zov� tabulky a pohledy jsou zav�d�ny v~po�ad� dan�m
grafem z�vislosti predik�t� v logick�m programu.

V na�em p��pad� je nejprve vytvo�ena a napln�na relace $e$ p�edstavuj�c�
orientovan� hrany. Pot� je vytvo�en datab�zov� pohled reprezentuj�c�
predik�t $edge$.

Predik�t $path$ je rekurz�vn� a proto pro n�j mus� b�t vypo�ten
pevn� bod. K tomu je pou�ita seminaivn� itera�n� metoda.



\section{Negace}

Zaveden� negace do Datalogu p�in��� probl�my s vyhodnotitelnost�
program�. V EDD-Datalogu garantujeme spr�vn� proveden� v�po�tu pouze
pro stratifikovan� programy. 

Nen�-li program s negac� stratifikov�n, mohou nastat tyto problematick�
situace:

\begin{itemize}
\item Nekone�n� smy�ka. Program nikdy nedokon�� v�po�et.
Kv�li negaci nelze u rekurz�vn�ho predik�tu
dos�hnout pevn�ho bodu, proto�e v itera�n� smy�ce jsou st�le generov�ny
nov� a nov� �daje.
\item Program v�po�et dokon��, ov�em v�sledky jsou chybn�.
\end{itemize}

Jednoduch� p��klad pou�it� negace je uveden v souboru pathcon.d.
Je to varianta hled�n� cesty v grafu, kter� se vyh�b� zablokovan�m
uzl�m grafu.

\section{Agrega�n� funkce}

EDD-Datalog nab�z� stejn� agrega�n� funkce jako datab�zov� jazyk SQL.
Jsou to funkce avg (pr�m�r), count (po�et prvk�), max, min a sum.
Tyto agrega�n� funkce mohou b�t pou�ity pouze v hlav� pravidla.

\begin{figure}
\begin{boxit}
\begin{cprog}

	owns(a, b, 0.6).
	owns(a, c, 0.4).
	owns(b, c, 0.6).
	owns(b, d, 0.3).
	owns(c, d, 0.4).

	controlsvia(X, X, Y, N) :- owns(X, Y, N).
	controlsvia(X, Y, Z, N) :- controls(X, Y), owns(Y, Z, N).

	controlsum(X, Y, sum(N) ) :- controlsvia(X, _, Y, N).

	controls(X, Y) :- controlsum(X, Y, N), N > 0.5. 


\end{cprog}
\end{boxit}
\caption{Program pro zji�t�n� majetkov� prov�zanosti
(soubor controls.d)} \label{controls.d}
\end{figure}


Pou�it� agrega�n� funkce je demonstrov�no 
programem na obr. \ref{controls.d}.
Program vyhodnocuje majetkovou prov�zanost podnik�. Extenzion�ln� datab�ze
sest�v� z fakt� ve tvaru $owns(X,Y,N)$. To znamen�, �e podnik $X$ 
vlastn� ��st akci� velikosti $N$ podniku $Y$. 
N�jak� podnik $X$ ovl�d� podnik $Y$, jestli�e p��mo nebo nep��mo 
(prost�ednictv�m jin�ch ovl�dan�ch spole�nost�) kontroluje alespo�
polovinu akci� podniku $Y$.

\section{Extern� datab�zov� relace}

EDD-Datalog umo��uje pracovat v programu i s predik�ty, 
kter� reprezentuj� datab�zov� relace (tabulky), 
kter� ji� v rela�n�m datab�zov�m syst�mu existuj�.

V�zm�me si p��klad uveden� v p�edchoz� ��sti (viz obr. \ref{controls.d}).
Pokud je po�et sledovan�ch spole�nost� velk�, je ne��eln� uv�d�t
�daje o vlastnictv� pod�l� v jednotliv�ch podnic�ch (predik�t $owns$)
p��mo v programu.
Je v�hodn�j�� udr�ovat tato data v datab�zi. P�edpokl�dejme, �e
v datab�zi ji� existuje relace $owns$ vytvo�en� 
pomoc� n�sleduj�c�ho p��kazu SQL:

\begin{cprog}

	CREATE TABLE owns (
		owner_company   CHAR(20),
		owned_company   CHAR(20),
		fraction	NUMBER(12,10)
	 );

\end{cprog}

Program uprav�me tak, �e v n�m sma�eme
�vodn� �ast s fakty a nahrad�me ji informac� o struktu�e datab�zov� 
relace. Upraven� program je na obr. \ref{econtrol.d}.

Obecn� tvar popisu struktury extern� datab�zov� relace je n�sleduj�c�:

\begin{quote}
{\em Jm�no\_relace\/}({\em Atribut\_1 dat\_typ, \ldots , 
Atribut\_N dat\_typ\/}).
\end{quote}

Jm�na atribut� mus� za��nat velk�m po��te�n�m p�smenem.
Sou�asn� verze p�eklada�e EDD-Datalogu dok��e u atribut� extern�ch
relac� pracovat s datov�mi typy �et�zec (ozna�en� A({\em d�lka\/}) )
nebo ��slo (ozna�en� N({\em p�esnost\/}) ). Dal�� datov� typy ---
nap��klad typ datum --- budou podporov�ny v dal��ch verz�ch
p�eklada�e. 

\begin{figure}
\begin{boxit}
\begin{cprog}

owns(Owner_company A(20), Owned_company A(20), Fraction N(12,10)).

controlsvia(X, X, Y, N) :- owns(X, Y, N).
controlsvia(X, Y, Z, N) :- controls(X, Y), owns(Y, Z, N).

controlsum(X, Y, sum(N) ) :- controlsvia(X, _, Y, N).

controls(X, Y) :- controlsum(X, Y, N), N > 0.5. 


\end{cprog}
\end{boxit}
\caption{Program pou��vaj�c� extern� relaci} \label{econtrol.d}
\end{figure}

\end{document}