![]() |
![]() |
DATALOG
Na jazyk DATALOG se lze dívat různými způsoby. Těm, kteří znají jazyk PROLOG, lze sdělit, že jde o syntaktickou podmnožinu PROLOGu s poněkud odlišnou interpretací pravidel. Databázistům znajícím PROLOG lze nabídnout, že jde o PROLOG pro databáze či o logický aparát tvořící nadstavbu relační databáze. Jazyk DATALOG nemá ani jednoznačného tvůrce, vznikl spíše vývojem. U zrodu pojmu DATALOG se uvádí D. Maier, rozvoji DATALOGu se hodně věnoval význačný expert na teorii (ale i praxi) databází - J. Ullman. Z předchozího dílu Databázové abecedy víme, že DATALOG je jazykem deduktivních databází. Budeme pro něj předpokládat existenci základních relací daných klasickou relační databází. Abychom mohli použít data z relační databáze k odvozování pomocí pravidel, je nutné vyjádřit prvky relací jako logické formule. To je formálně jednoduché. Např. fakt, že n-tice (relace,IS) je prvkem relace JE_ČÁSTÍ* , lze vyjádřit pomocí atomické formule JE_ČÁSTÍ(relace,IS) Takové formule se nazývají v terminologii DATALOGu (a i PROLOGu) tvrzení. Skutečně, zmíněná formule označuje tvrzení "relace je částí informačního systému". V DATALOGu se zapisují pravidla. Zapisují ve tvaru L0 :- L1,...,Ln kde Li jsou atomické formule. Mají tvar P(t1,...,tk), kde P je predikátový symbol a ti je buď proměnná nebo konstanta. Tvrzení jsou vlastně pravidla s n=0 a ti, které jsou konstanty. Symbol P je buď jméno základní databázové relace nebo jméno virtuální relace. Pro aplikace je vhodné, aby mezi predikáty byly i binární porovnávací predikáty >,<,=,... apod.Levá strana pravidla se nazývá hlava, pravá tělo. Virtuální relace se definuje pomocí jednoho nebo více pravidel (se stejnou hlavou), a to tak, že v pravidlu lze použít i odkazy na jiné virtuální relace, dokonce, a to je velmi důležité, i na sebe samu. Tímto způsobem získáme rekurzivní pravidla a obdržíme tak možnost vyjádřit rekurzi, která schází v relačních jazycích. Tvrzení tvoří tzv. extenzionální databázi (EDB) fyzicky uloženou v relační databázi. Program v DATALOGu je dán množinou pravidel a případně tvrzeními z virtuálních relací. Říká se mu také intenzionální databáze (IDB). Program v DATALOGu můžeme také chápat jako dotaz, ve kterém požadujeme na základě EDB (a eventuálně dalších virtuálních relací) zkonstruovat virtuální relace vyskytující se v hlavách pravidel. Terminologie dotazování známá z relačních databází ale musí poněkud modifikovat. Relace v EDB není totiž množina prvků (či řádků tabulky), nýbrž množina tvrzení tvaru P(t1,...,tk). Jde ovšem o rozdíl teoretický. Z hlediska uživatele jsou virtuální relace zobrazovány opět pomocí tabulek. Příkladem rekurzivního dotazu v DATALOGu je (1) POD_NAD(x,y):- JE_ČÁSTÍ(x,y) (2) POD_NAD(x,y):- JE_ČÁSTÍ(x,z), POD_NAD(z,y) Tato dvě pravidla tedy definují virtuální relací POD_NAD. Vyhodnocením programu bychom získali všechny dvojice (X,Y), pro které plazí, že X je podobjektem Y. DATALOG není užitečný pouze pro rekurzivní dotazy. Je možné pomocí něj popsat dotazy, které jsou vyjádřitelné pozitivní relační algebrou, tj. jazykem zahrnujícím operace spojení, selekce, projekce, sjednocení. Uvažujme relace KVALIFIKACE(JMÉNO,JAZYK,POČET_PŘEKLADŮ), PŘEKLÁDÁ(JMÉNO,NÁZEV), INDEXACE(NÁZEV,TÉMA) V IDB definujeme(kromě jiného) specialisty (podle témat) překládající z angličtiny: SPECIALISTA(jméno,téma):-ZABÝVÁ_SE(jméno,téma),ZKUŠENÝ_ANGL(jméno) ZABÝVÁ_SE(jméno,téma):-PŘEKLÁDÁ(jméno,název),INDEXACE(název,téma) ZKUŠENÝ_ANGL(jméno):-KVALIFIKACE(jméno,jazyk,kolik), kolik > 10, jazyk = ANGL Tedy SPECIALISTA vzniká pomocí relací ZABÝVÁ_SE a ZKUŠENÝ_ANGL, které vzniknou z relací v EDB. Efektivní vyhodnocení programu v DATALOGu Vyhodnocování zdola-nahoru ze známých dat má přímou vazbu na relační algebru. Virtuální relaci ZKUŠENÝ_ANGL lze vypočítat jako ZKUŠENÝ_ANGL=def KVALIFIKACE(POČET_PŘEKLADŮ>10 AND JAZYK=ANGL)[JMÉNO] Relaci ZABÝVÁ_SE definujeme jako ZABÝVÁ_SE =def PŘEKLÁDÁ * INDEXACE Nejsou-li pravidla rekurzivní, vždy lze nalézt takové uspořádání ve vyhodnocovaných pravidlech, že relace v těle zrovna vyhodnocovaného pravidla jsou k dispozici. I rekurzivní pravidla programu v DATALOGu se dají transformovat do rovnic relační algebry. V případě pravidel (1) a (2) obdržíme POD_NAD = (JE_ČÁSTÍ[NADOBJEKT=OBJEKT]JE_ČÁSTÍ)[1,3] È JE_ČÁSTÍ Zkušenější čtenář v rovnici rozezná podobnost s rekurzivním UNION navrženým v SQL3 (viz zmínka v minulém dílu Databázové abecedy). Relace POD_NAD je však vyjádřena opět pomocí POD_NAD. Způsob vyhodnocení takové rovnice vyžaduje iterace. 80. léta věnovali protagonisté DATALOGu mnoho sil studiu rekurze a vývoji efektivních algoritmů jejího vyhodnocení. Snahou samozřejmě je, aby se co nejvíce využil relační databázový stroj, což je v případě DATALOGu bez rekurze přímočaré. Vyjadřovací síla DATALOGu, možnosti rozšíření Každý dotaz pozitivní relační algebry lze transformovat do nerekurzivního programu v DATALOGu s vestavěnými binárními porovnávacími predikáty ³ , £ , >, ....Opak ovšem neplatí. Díky rekurzivním dotazům je DATALOG silnější než pozitivní relační algebra. Ne každý dotaz v relační algebře lze vyjádřit v DATALOGu. Dotaz používající rozdíl dvou relací vyžaduje použití negace na pravé straně pravidla. Např. dotaz "Kteří překladatelé nejsou zkušení angličtináři" lze zapsat v relační algebře jako KVALIFIKACE[JMÉNO] - ZKUŠENÝ_ANGL Zavedeme-li virtuální relaci ODPOVĚĎ, bude odpovídající pravidlo mít tvar ODPOVĚĎ(j):- KVALIFIKACE(j,z,p), ù ZKUŠENÝ_ANGL(j) kde symbol é značí negaci. DATALOG připouštějící taková pravidla bývá označován jako DATALOGù . Předchozí způsoby vyhodnocení programů v tomto jazyku ale obecně nevedou k jednoznačně definovaným virtuálním relacím. Existují ovšem podmnožiny jazyka DATALOGù takové, kde sémantika programů je jednoznačná a odpovídá přirozenému řešení problému. V praxi se vystačí s tzv. stratifikovaným DATALOGem s negací. V principu jde o omezení použití negace. Pravidla programu se rozdělí do skupin tak, že rekurzivně definované relace jsou definovány bez negace a teprve tyto jsou použity ve výrazech s negací. Ne ke každému programu v jazyku DATALOGù však existuje jeho stratifikovaná verze. Shrneme-li předchozí, vyjadřovací síla deduktivních databází ve srovnání s relačně úplnými jazyky je naznačena na obrázku 1.
relační algebra DATALOG
(rekurzivní positivní relační algebra (dotazy s rozdílem) dotazy) = nerekurzivní DATALOG
stratifikovaný DATALOG
Obr. 1 Vyjadřovací síla relačních dotazovacích jazyků
Shrnutí Deduktivní databáze reprezentují přístup, který vznikl ze dvou požadavků:
Opodstatnění deduktivních databází ukazuje hezký příklad, který použil na jedné panelové diskusi F. Bry. Šlo o systém veřejné dopravy, kde databáze byla redukována 600´ nahrazením velkého množství dat několika deduktivními pravidly (např. pravidlo "je-li státní svátek, platí jízdní řád jako v neděli" nahradí mnoho konkrétních denních jízdních řádů). Vedle relační databáze zadané relačním schématem je tedy možné zadat databázi pomocí pravidel, a to dokonce rekurzivních. Tento způsob zacházení s daty je možné nalézt v 80. letech také v disciplíně informatiky zvané - logické programování, speciálně v jazyku PROLOG vyvinutém již v 70. letech Colmerauerem a Kowalskim. Na přelomu 70. a 80. let se v Toulouse uskutečnilo několik pracovních setkání věnovaných deduktivním databázím, která naznačila problém: spojit vhodně PROLOG s relační databází uloženou na vnějším médiu. Výzkumné úsilí a následné softwarové realizace se zkoncentrovaly na syntaktickou podmnožinu PROLOGu zvanou DATALOG, která se navíc liší od PROLOGu tím, že programy v DATALOGu používají vyhodnocovací algoritmy, umožňující efektivnější implementaci než obecnější PROLOG. DATALOG tedy představuje význačný krok v budování deduktivních databází. Ramakrishnan a Ullman uvádějí ve svém přehledu z r. 1993 14 prototypů deduktivních SŘBD. Nejznámějšími projekty, vycházejícími z DATALOGu, jsou systém LDL vyvinutý v MCC a Standfordský NAIL!. Deduktivní složku má i následník INGRESu - POSTGRES.
<seznam dílů seriálu> <COMPUTERWORLD> |