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.

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φ 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∙.

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.