 |
 |
|
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> | |