![]() |
![]() | ||||||||||||||||||||||||||||||||||||||||||
Deduktivní databáze
Kdo byl někdy v Paříži, jistě obdivoval množství stanic a linek tamějšího metra. Jezdit metrem v Paříží je jisté dobrodružství, protože v řadě případů je možné se z jedné stanice do druhé dostat více způsoby, po různých trasách. Navíc, spočítáme-li se počet stanic jednou linkou a počet stanic druhou, nemusí být pravda, že přes méně stanic trvá cesta kratší čas. Relačního databázistu by jistě napadlo vytvořit relaci METRO(LINKA, Z, DO) a pro každou linku uložit všechny dvojice stanic Z a DO, kde DO je bezprostřední následník stanice Z. Mít po ruce vhodný relační jazyk, bylo by hezké klást dotazy jako např.: (1) Které stanice jsou dosažitelné ze stanice Chatelet? (2) Lze se dostat ze stanice Chatelet do stanice Gallieni ne více než se dvěma přestupy? (3) S jakým nejmenším počtem zastávek se lze dostat ze stanice Chatelet do stanice Gallieni? Bohužel, relační jazyky jako je relační algebra či kalkul, ale i SQL, neumožňují formulovat ani dotazy typu (1). Zkusme např. dotaz zapsaný jako SELECT DO FROM METRO WHERE Z = ¢ Chatelet¢ Zřejmě obdržíme všechny stanice, do kterých se lze ze Chatelet dostat bezprostředně. Složitější dotaz SELECT X.DO FROM METRO X WHERE X.Z IN (SELECT Y.DO FROM METRO Y WHERE Y.Z = ¢ Chatelet¢ ) vede k množině stanic, do kterých se lze dostat ze Chatelet “přes” jednu mezistanici. Kdybychom takto chtěli pokračovat, museli bychom stále zvětšovat výraz dotazu, a nejen to, museli bychom znát nejvzdálenější stanici dosažitelnou ze stanice Chatelet. Navíc, pro jinou stanici než Chatelet by byl výraz dotazu obecně jiný, protože cesta k nejvzdálenější stanici by byla obecně jiné délky. Matematický důkaz, že v relační algebře nelze zkonstruovat výraz, který by řešil původní dotaz, je dost obtížný. Jeho význam je však hluboký. Znamená vlastně, že ve světě relačních jazyků neexistuje rekurze nebo cyklus, tak jak je známe z univerzálních programovacích jazyků. Při hlubším pohledu na daný problém zjistíme, že relace METRO vlastně reprezentuje orientovaný graf, jehož uzly jsou stanice a hrana (A,B) znamená, že z A se dostaneme do B bezprostředně. Další atributy relace (např. LINKA) mohou být přiřazeny buď hraně nebo jednomu z jejich uzlů. Daný problém je ekvivalentní nalezení všech následníků uzlu v daném grafu. Rekurzivní dotazy Z praxe jsou známé další podobné úlohy založené na grafech, jako je třeba problém kusovníku, kdy se podobné dotazy řeší nad relací JE_ČÁSTÍ, jiný příklad poskytují genealogické databáze (předci, potomci), v tezaurech se hledají všechny pojmy podřízené danému pojmu atd. Charakteristický pro výpočet těchto úloh je mechanismus rekurze (nebo zásobníku). Dotazy spojené s těmito problémy se nazývají rekurzivní. Abychom byli přesní, některé verze SQL mají speciální, nestandardní konstrukty, které umožňují částečně řešit uvedené dotazy (např. SŘBD ORACLE). Dotaz (1) se v syntaxi ORACLE zapíše jako SELECT DO FROM METRO CONNECT BY PRIOR DO = Z START WITH Z = ¢ Chatelet¢ Zdůrazněme však, že v připravovaném standardu SQL3 je syntaxe pro rekurzivní dotazy zcela odlišná. Zmíněný dotaz se v syntaxi navržené v SQL3 zapíše takto: WITH RECURSIVE DOSAŽITELNÉ(Z, KAM) (SELECT Z, KAM FROM METRO UNION SELECT in.Z, out.KAM FROM FROM DOSAŽITELNÉ in, METRO out WHERE in.KAM = out.Z) SELECT * DOSAŽITELNÉ WHERE Z = ¢ Chatelet¢ Poněkud jiné a zřejmě obecnější řešení poskytují až deduktivní databáze, které zavedly rekurzi do dotazovaní velmi elegantním způsobem. Deduktivní a aktivní databáze Deduktivní databáze jsou často formálně popisovány jako kombinace běžných (relačních) databází obsahujících fakta (řádky tabulek) a bází znalostí, které obsahují pravidla a odvozovací stroj, který dovoluje odvozování informací z faktů a daných pravidel. Báze znalostí je často vyjádřena podmnožinou pravidel logiky 1. řádu. Z hlediska uživatele jde o prostředky, které jsou deklarativní, a které zvyšují sílu běžných relačních dotazovacích jazyků. Pravidla mají obecně tvar [ Aktivátor Þ ] předpoklady Þ důsledky tj., jestliže nastane aktivace, pak jsou-li splněny předpoklady, platí důsledky. Některé systémy nemají explicitní aktivátory. V příkladě dotazu (1) by pravidlo mohlo mít tvar: Je-li Y přímo bezprostředně dosažitelné z X a Z je dosažitelné z Y, pak Z je dosažitelné z X. Historicky je třeba odlišit deduktivní databáze od aktivních databází, které představují poněkud jiný styl spouštění odvozovacích pravidel. V aktivních databázích se pravidla automaticky vyvolávají (jsou aktivována) na základě vzniku jistých událostí a splnění jistých podmínek. Speciálním případem takového pravidla může být trigger známý ze současných relačních SQL serverů. Jeniffer Widom uvedla na 1. mezinárodním workshopu o pravidlech v databázových systémech (1993) spektrum 6 jazyků používajících pravidla (obr. 1). Deduktivní DB Aktivní DB
DATALOG RDL A-RDL Ariel Starburst Postgres Obr. 1 Spektrum jazyků používajících pravidla Nejznámějším představitelem deduktivních databází je DATALOG, který si podrobněji ukážeme v příštím dílu Databázové abecedy. Pravidla v systémech jako je Starburst a Postgres jsou složitější týkají se nejenom dotazů, ale i přechodu z jednoho stavu databáze do jiného, v důsledku pravidla se objevují složitější operace. Také aktivátory jsou složitější. Připomeňme ovšem i fakt, že vesměs nejde o komerční systémy, nýbrž o dlouhodobé výzkumné projekty s implementovány prototypy, jejichž rysy se objevují v současných a očekávaných verzích známých databázových produktů. Rekurze pomocí pravidel Uvažujme další příklad. Schéma relace JE_ČÁSTÍ(OBJEKT,NADOBJEKT) popisuje vztahy mezi objekty a jejich přímými nadobjekty. Příkladem relace JE_ČÁSTÍ je tabulka 1 nebo její ekvivalentní vyjádření pomocí grafu (zde stromu) na obrázku 2.
Tab. 1 Tabulka základních vztahů objektů
IS
RDBS
DATABÁZE IO SCHÉMATA
RELACE REFERENČNÍ INTEGRITA Obr. 1 Hierarchie objektů Vyhodnocení dotazu na všechny části RDBMS vlastně znamená projít jistý podstrom od uzlu RDBMS do jednotlivých listů. Každý programátor zareaguje na takovou úlohu použitím prohledávání stromu pomocí cyklu nebo pomocí rekurzivního volání jisté procedury. V řeči relačního jazyka bychom však raději dali přednost nějakému úspornějšímu, neprocedurálnímu vyjádření, tak jako se např. vytvářejí pohledy v SQL. Protože definice pohledů v SQL používá příkaz SELECT, z předchozích úvah plyne, že tudy cesta nevede. V jazyku DATALOG, který je zřejmě nejznámějším jazykem deduktivních databází, budeme konstruovat virtuální relaci POD_NAD(OBJEKT,NADOBJEKT), která obsahuje dokonce všechny vztahy nadřazenosti a podřazenosti mezi známými relačními pojmy vyskytujícími se v relaci JE_ČÁSTÍ, tj. i všechny podobjekty RDBMS. Relace bude zadána jistými pravidly, která mají logickou interpretaci, což ospravedlňuje název deduktivní databáze, jak se zadané množině pravidel také říká. Řešení vyžaduje dvě pravidla: POD_NAD(x,y):- JE_ČÁSTÍ(x,y) POD_NAD(x,y):- JE_ČÁSTÍ(x,z), POD_NAD(z,y) Význam pravidel bychom mohli objasnit např. takto: (i) Je-li X částí Y, pak X je podobjektem Y. (ii) Je-li X částí Z a Z je podobjektem Y, pak X je podobjektem Y. Pravidla se tedy čtou zprava doleva, pravá strana pravidla je konjunkcí podmínek. Rekurze je patrná z pravidla (ii), kdy relace POD_NAD je definována pomoci sebe samé. Relaci POD_NAD* získáme z nějaké relace JE_ČÁSTÍ* (např. té, která je v tabulce 1) odvozováním, tj. aplikací pravidel (i) a (ii). Tato aplikace je vlastně založena na dosazování objektů (konstant) za proměnné x, y, z do pravé strany pravidel a získávání nových faktů z levých stran pravidel. Jednoduše řečeno, pravidla se aplikují tak dlouho, dokud získáváme nové řádky relace POD_NAD* . Intuitivně, odvozování musí jednou skončit, protože z konečného množství hodnot obsažených v relaci JE_ČÁSTÍ* nelze získat (v daném případě) nic nekonečného. Virtuální relace POD_NAD* vyhodnocená vzhledem k relaci JE_ČÁSTÍ* dané tabulkou 1 obsahuje, data daná tabulkou 2.
Tab. 2 Tabulka odvozených vztahů objektů z relace JE_ČÁSTI Závěrem si povšimněme jednoho významného jevu. Není zcela dobře řečeno, že pomocí uvedeného odvozování získáváme něco nového. Co je odvoditelné, je vlastně skryto v datech základních relací dané databáze. Podstatná jsou základní fakta. To, co jsme odvodili, jsou vlastně logické důsledky plynoucí z daných dat. Podobný princip je dán i mechanismem pohledů. Pohledy jsou také virtuální relace. Nejsou tedy materializovány v databázi. To, že je materializace někdy nutná (viz např. statistické databáze), je pouze proto, abychom se zbavili opětovného výpočtu odvozených dat. <seznam dílů seriálu> <COMPUTERWORLD> |