Dedukcinių ir reliacinių duomenų bazių sistemų lyginamoji analizė

Naudoti terminai anglų kalba plečiamoji extensional išplečianti intensional termų rinkinys tuple išvedimo taisyklė deductive rule vientisumo reikalavimai integrity constraint použklausis subquery kylantis bottom-up besileidžiantis top-down mišrusis magic set sprendimo rėmimo sistema decision support system ekspertinės sistema expert system planavimo sistema planning system uždaro pasaulio prielaida closed world assumption (CWA) Įvadas Duomenų bazių technologijos sparčiai vystėsi nuo tada, kai 1960 metais atsirado pirmoji duomenų bazių valdymo sistema. Šiomis dienomis jos atlieka svarbų vaidmenį tiek bankininkystėje, tiek gamyboje tiek kitose sferose. Svarbiausia duomenų bazių sistemų savybė – gebėjimas valdyti didelius duomenų kiekius, taip pat jos teikia galimybę paprastomis operacijomis valdyti duomenis. Didėjant poreikiui, nenumaldomai didėja ir pasiūla, t.y. duomenų bazių įvairovė. Dabar galime rinktis tarp reliacinių, tinklinių, dedukcinių ir kitokių duomenų bazių. Šio darbo tikslas: detaliau panagrinėti dedukcines ir reliacines duomenų bazes, išskirti pranašesnę, patogesnę vartoti duomenų bazių sistemą, atsižvelgiant į tam tikras charakteristikas. Siekiant tikslo buvo iškelti tokie uždaviniai: • detaliau susipažinti su dedukcinėmis duomenų bazėmis, • išsiaiškinti apie jų taikymo galimybes, • palyginti jas su reliacinėmis duomenų bazėmis įvairiais aspektais. Manau šis darbas turės ir praktinę naudą: suteiks ojektyvios informacijos apie kiekvienos sistemos privalumus bei trūkumus. 1. Dedukcinės duomenų bazių sistemos Per paskutinius 15 metų duomenų bazių ir loginio programavimo simbiozė labai intensyviai tyrinėjama, siekiant geresnio panaudojimo tiek tradicinių, tiek naujų duomenų bazių sistemų. Tai vedė prie įprastinių, reliacinių duomenų bazių praplėtimo. Buvo įvesta taisyklėmis paremta kalba žinių pateikimui. Ši kalba buvo naudojama tiek kaip modeliavimo, tiek kaip užklausų formavimo kalba. Taip pat buvo įvesti dedukcijos metodai informacijos apdorojimui. Dedukcinė duomenų bazių sistema, tai sistema, kuri remdamasi duomenų bazėje jau esamais faktais ir taisyklėmis gali išvesti naujus faktus ar taisykles ([BS96]). 1.1. Dedukcinė duomenų bazė Dedukcinę duomenų bazę sudaro faktai (baziniai faktai), išvedimo taisyklės ir vientisumo užtikrinimo reikalavimai. Faktais užrašoma pagrindinė duomenų bazės informacija, kuri visada teisinga. Išvedimo taisyklėmis iš jau turimų duomenų bazėje faktų galima išvesti naujus. Vientisumo užtikrinimo reikalavimai – tai sąlygos, kurias duomenų bazė turi visada (po kiekvieno atnaujinimo) tenkinti ([Pia00]). Norint tiksliau apibrėžti šias sąvokas, reikalingos šios terminologijos: • Termas – tai kintamasis arba konstanta. • Jei P – predikatas, ir t1, ... , tn – termai, tai P(t1, ... , tn) – atomas. • Litera – atomas arba atomo neigimas. Bendru atveju, faktai, išvedimo taisyklės ir vientisumo reikalavimai išreiškiami tokia forma: A0:– L1 & ... & Ln, kur n – teigiamas skaičius A0 – atomas, kuris apibrėžiamas kaip šios formos galva, o L1 & ... & Ln – literų konjunkcija, apibrėžiama kaips formos kūnas. Faktai užrašomi sakiniais su tuščiais kūnais, t.y. atomais. Pavyzdžiui, faktas „Rasa yra Jono mama“ gali būti užrašomas taip: mama(rasa, jonas). Išvedimo taisyklės apibrėžia išvestinę informaciją, t.y. informaciją, kurios realiai duomenų bazėje nėra, bet ją galima gauti logiškai susiejus turimus faktus. Pavyzdžiui, turime tokius faktus ir taisyklę: didesnis(3, 1). didesnis(5, 3). didesnis(X, Y):– didesnis(X, Z) & didesnis(Z, Y). Užklausai ?– didesnis(5, 1). bus grąžintas atsakymas true, nors ir nėra tokio fakto didesnis(5,1), tačiau pritaikius taisyklę, randama, kad 5>3, o 3>1, tad ir 5>1. Vientisumo reikalavimai dažniausiai užrašomi sakiniais, neturinčiais galvos. Šie sakiniai taip pat vadinami neigimais. Norėdami nurodyti, kad vienas asmuo negali būti tuo pačiu metu ir mama ir tėtis, galėtume užrašyti taip: :–tėtis(X, Y) & mama(X, Z). Visgi dėl bendrumo, neigimuose taip pat naudojama galva – prieštaringas predikatas ICn, kuris naudojamas dar ir dėl patogumo, nes jei ICi reikšmė yra true, reiškia suveikė būtent tas reikalavimas. Vientisumo reikalavimus galima išreikšti ir išvedimo taisyklėmis, kurių išvada yra klaidinga. Taigi, pabaigai apibendrinsime: dedukcinė duomenų bazė, tai trejetas D=(F, DR, IC), kur F – baigtinė faktų aibė, DR – baigtinė išvedimo taisyklių aibė ir IC – baigtinė vientisumo reikalavimų aibė. Faktų aibė – plečiamoji (ją galima pralėsti) duomenų bazės dalis (EDB), o DR ir IC aibės – išplečianti (jos pagalba galima praplėsti) duomenų bazės dalis (IDB). Duomenų bazės predikatai skirstomi į bazinius ir išvestinius predikatus. Baziniai predikatai sutinkami EDB, taip pat išvedimo taisyklių ir vientisumo reikalavimuose. Išvestiniai predikatai apibrėžiami kokia nors išvedimo taisykle. Jie kitaip dar vadinami rodiniais, kurie atlieka tas pačias funkcijas, kaip ir rodiniai reliacinėje duomenų bazėje ([Pia00]). 1.2. DATALOG Datalog – užklausų ir taisyklių kalba, skirta dedukcinėms duomenų bazėms. Ši kalba yra sintaksinis loginio programavimo kalbos Prolog poaibis. Datalog – pilna ir išbaigta kalba, todėl gali būti efektyviai panaudota net didelėse duomenų bazėse. Ji gana populiari teoriniuose taikymuose, tačiau komercinėse duomenų bazių sistemose vis dar neįsitvirtino ([Mar03]). Datalog kalboje neleistini sudėtiniai termai kaip predikatų argumentai (išraiška P(f(1), 2) neleistina). Predikatų argumentais gali būti tik kintamieji arba konstantos. Tai garantuoja užklausos analizės saugumą. Datalog kalboje, priešingai nei Prolog, sakinių eilės tvarka programoje visiškai nesvarbi. 1.3. Užklausų apdorojimas dedukcinėse duomenų bazėse Dedukcinė duomenų bazių valdymo sistema turi pateikti užklausų apdorojimo sistemą, kuri gebėtų atsakyti į užklausas tiek rodiniais, tiek baziniais predikatais. Datalog sintaksėje užklausos duomenų bazei pateikiamos forma ?–w(x), kur x – kintamųjų ir konstantų vektorius, o w(x) – literų konjunkcija. Atsakymas į užklausą – tai aibė tokių x reikšmių, su kuriomis w(x) įgyja reikšmę true, atsižvelgiant į EDB ir IDB ([Pia00]). Pavyzdžiui, užklausa ?– protėvis(stasys, X), užduota pirmame priede pateiktai duomenų bazei grąžina sąrašą asmenų, kuriems Stasys yra protėvis, o užklausa ?– protėvis(jonas, marytė) grąžins reikšmę true, jei duomenų bazėje yra faktas, arba galima jį išvesti, pasinaudoję išvedimo taisyklėmis, kad Jonas yra Marytės protėvis. Užklausoms apdoroti pateikiami trys būdai: kylantis atsakymo ieškojimas (Bottom-up), besileidžiantis atsakymo ieškojimas (Top-down), mišrusis būdas (Magic Set) ([Pia00], [Bau94]). 1.3.1. Kylantis metodas Ši procedūra susideda iš dviejų žingsnių. Pirmajame siekiama rasti visus įmanomus faktus, pritaikant išvedimo taisykles ir prijungiant bazinius. Taip randamas minimalus dedukcinės duomenų bazės Herbrando modelis. Jis randamas, taikant kiekvieną taisyklę tol, kol nebegaunama jokių naujų rezultatų. Antrame žingsnyje užklausa užduodama pirmame žingsnyje rastiems faktams, nes šie apima visą dedukcinės duomenų bazės informaciją. Vėl vadovausimės pirmame priede pateikta duomenų baze ir bandysime sužinoti apie visus Saulės anūkus tokia užklausa: ?-močiutė(saulė, X). Pirmas žingsnis: Visa įmanoma informacija iš pateiktos duomenų bazės išvedama per tokias iteracijas: 1 iter.: išvedami baziniai faktai; 2 iter.: pritaikoma taisyklė T1 pirmos iteracijos rezultatams ir gaunama: vienas_iš_tėvų(stasys, antanas), vienas_iš_tėvų(stasys, rūta), vienas_iš_tėvų(antanas, jonas), vienas_iš_tėvų(antanas, ramunė); 3 iter.: pritaikoma taisyklė T2 pirmos ir antros iteracijos rezultatams: vienas_iš_tėvų(saulė, antanas), vienas_iš_tėvų(saulė, rūta), vienas_iš_tėvų(rūta, jolanta), vienas_iš_tėvų(jolanta, marytė); 4 iter.: pritaikoma taisyklė T3 jau turimiems rezultatams : močiutė(saulė, jonas), močiutė(saulė, ramunė), močiutė(saulė, jolanta), močiutė(rūta, marytė); 5 iter.: pirmas žingsnis baigiamas, jei daugiau nebeišvedama jokių naujų faktų. Antras žingsnis: Užklausa ?– močiutė(saulė, X) pritaikoma aibei, apimančiai 20 pirmu žingsniu gautų faktų. Kadangi tarp šių faktų yra ir močiutė(saulė, jonas), močiutė(saulė, ramunė) ir močiutė(saulė, jolanta), tai šios užklausos rezultatas bus X=jonas, ramunė, jolanta. Užklausų analizė kylančiu būdu turi keletą trūkumų: • Išvedami ir tie rezultatai, kurie norimai užklausai nereikalingi. Pavyzdžiui, mūsų nagrinėtu atveju, bereikalingai išvesta informacija apie Rūtos anūkę Marytę bei kiti. • Taisyklių parinkimo tvarka tiesiogiai susijusi su užklausos analizės efektyvumu. Ieškant atsakymo į tam tikrą užklausą, reikia tai vykdyti kiek įmanoma efektyviau. Todėl siekiant efektyvumo reikia atsižvelgti ir į tai, kokia tvarka taikyti išvedimo taisykles. Pavyzdžiui, jei antroje iteracijoje būtume taikę taisyklę T3, o tik paskui T1, nebūtų išvesta jokios naujos informacijos ir ciklą būtų reikėję kartoti dar kartą. • Skaičiuojant neigiamą informaciją taikomas „susluoksniavimas“. Neigiama informacija traktuojama uždaro pasulio prielaidos (CWA) pagalba, kuri informaciją laiko klaidinga, jei negali būti parodyta kaip teisinga. Todėl, jei išvestinės taisyklės kūne pasirodo neigiamas išvestinis predikatas, pirmiausia turime pritaikyti taisykles, kurios apibrėžia tą predikatą, kad įsitikintume, jog CWA buvo pritaikyta sėkmingai, t.y. skaičiavimas vykdomas sluoksnis po sluoksnio. 1.3.2. Besileidžiantis metodas Duota tam tikra užklausa Q. Paprasta procedūra, analizuojanti užklausą Q besileidžiančiu metodu, remiasi atskirų použklausių (užklausos poaibių) Qi, tokių, kad atsakymas į Q yra atsakymų iš kiekvieno tokio poaibio sąjunga. Norint gauti tuos poaibius, kiekvienas išvestinis predikatas P užklausoje Q turi būti pakeistas tą predikatą apibrėžiančios taisyklės kūnu. Kadangi predikatus keičiam tik jų apibrėžimais, tai naujai gautų užklausų gavimas ekvivalentus Q gavimui. Gauti použklausiai yra kažkuria prasme „paprastesni“, nes jie jau yra predikatai, „artimesni“ baziniams. Užklausų keitimas použklausiais tęsiamas tol, kol gauname užklausas, sudarytas vien iš bazinių predikatų. Kai pasiekiam tokias užklausas, pagal pateikiamus rezultatus jos ekvivalenčios EDB. Pradinės užklausos Q konstantos naudojamos per visą šį procesą, kadangi jos padeda nustatyti bazinius faktus, kurie reikalingi skaičiavimui. Užklausos ?– močiutė(saulė, X). vykdymas šuo atveju vyksta taip: Pirmas žingsnis: Užklausa, pasinaudojant T3 taisykle, redukuojama į Q1: ?– mama(saulė, Y) & vienas_iš_tėvų(Y, X). Antras žingsnis: Q1, naudojant T1 arba T2, redukuojama į: Q2a: ?– mama(saulė, Y) & tėvas(Y, X) Q2a: ?– mama(saulė, Y) & mama(Y, X). Trečias žingsnis: Q2a pakeičiama užklausa Q3a: ?– tėvas(antanas, X), nes duomenų bazėje yra faktas mama(saulė, antanas). Q2b pakeičiama užklausa Q3b: ?– mama(rūta, X), nes taip pat yra faktas mama(saulė, rūta). Ketvirtas žingsnis: Užklausa Q3a, remdamasi EDB, grąžina X=jonas, ramunė; analogiškai Q3b prideda, kad X=jolanta. Užklausų analizė besileidžiančiu būdu turi keletą trūkumų: • Besileidžiančio metodo greitis dažniausiai vienas termų rinkinys per laiko vienetą. Besileidžiantis metodas bazinius predikatus peržiūri vieną po kito, kaip tik jie pasirodo tam tikrame použklausyje. Tokiu būdu šio metodo efektyvumas mažesnis. • Besileidžiantis metodas gali nebaigti darbo. Esant rekursyvioms taisyklėms, šis metodas gali įeiti į begalinį ciklą ir taip niekada nebaigti vykdymo. Taip gali nutikti, jei mes nagrinėsime kažkokią užklausą, kurioje panaudojamas predikatas protėvis (T4 ir T5 taisyklės pirmame priede), nes besileidžiantis metodas visada pradės redukuoti užklausą apie protėvį į kitą užklausą vėl apie protėvį. • Nevisada įmanoma nustatyti, ar besileidžiantis algoritmas darbą baigs. T. y., jei algoritmas dirba per ilgai, neįmanoma nustatyti, ar jis jau darbo nebaigs niekada, ir jis tik per ilgai dirba. • Pasikartojantys použklausiai. Redukuojant tikrąją užklausą į paprastesnius použklausius, tam tikras použklausis gali būti iškviestas keletą kartų. 1.3.3. Mišrusis metodas Mišrusis metodas – dviejų prieš tai aptartų algoritmų mišinys. Jis panaudoja besileidžiančio metodo pliusus analizuojant užklausą kylančiu metodu. Tarkim turime dedukcinę duomenų bazę D, užklausą Q. Šis metodas siekia perrašyti D taisykles į ekvivalnečią duomenų bazei D bazę D', atsižvelgiant į užklausą Q. Toks taisylkių perrašymas sukuria besileidžiančio metodo panaudojimo iliuziją duomenų bazėje D'. Tokiu atveju apdorojant užklausą kylančiu metodu, D' duomenų bazėje jau nebus išvedinėjama tai užklausai nereikalinga informacija. Be to, rezultatas gautas vykdant užklausą Q duomenų bazėje D' bus ekvivalentus rezultatui, vykdant tą pačią užklausą duomenų bazėje D. Tai pasiekiama Q informaciją išrieškiant kaip praplečiamą informaciją ir perrašant tas D taisykles, kurios panaudojamos užklausos Q vykdymo metu. Taisyklių perrašymas vykdomas perkeliant informaciją, esančią užklausoje Q, į perrašytų taisyklių kūną. Vėl nagrinėsime pavyzdį, pateiktą pirmame priede, tik dabar jau apimsime T1, T2, ..., T5 taisykles. Tarkime turime užklausą ?– protėvis(rūta, X). Šiai užklausai perrašytos taisyklės atrodys taip: m_protėvis(rūta). T1: protėvis(X, Y):– m_protėvis(X) & vienas_iš_tėvų(X, Y). T2: m_protėvis(Z):– m_protėvis(X) & vienas_iš_tėvų(X, Z). T3: protėvis(X, Y):– m_protėvis(X) & vienas_iš_tėvų(X, Z) & protėvis(Z, Y). Tariant, kad faktai vienas_iš_tėvų jau rasti (vienas_iš_tėvų(rūta, jolanta), vienas_iš_tėvų(jolanta, marytė)), kylantis metodas perrašytoms taisyklėms bus vykdomas taip: Pirmasis žingsnis apima septynias iteracijas: 1 iter.: protėvis(rūta, jolanta) gaunamas panaudojant T1 2 iter.: m_protėvis(jolanta) gaunamas panaudojant T2 3 iter.: nieko naujo negaunama taikant T3 4 iter.: protėvis(Jolanta, marytė) gaunamas taikant T1 5 iter.: m_protėvis(marytė) gaunamas taikant T2 6 iter.: protėvis(rūta, marytė) gaunamas T3 7 iter.: nebeišvedama nieko naujo taikant T1, T2, T3 Antras žingsnis: Gaunamas rezultatas yra {protėvis(rūta, jolanta), protėvis(rūta, marytė)} Kaip jau buvo minėta, mišrusis metodas išveda tik atitinkamai užklausai reikalngą informaciją. Tai pasiekiama įvedant predikatą m_protėvis, kuris įtrauktas į visų taisyklių kūną, ir faktą m_protėvis(rūta), kuris ir nurodo, kad mums reikia informacijos tik apie Rūtos palikuonis. 2. Reliacinės duomenų bazių sistemos 2.1. Reliacinė duomenų bazė Reliacinės duomenų bazės pagrindas – lentelė. Kiekviena lentelė skirta vienai esybei, pavyzdžiui, Darbuotojas, Studentas, Knyga, Šeima ir pan. Lentelė – dvimatis masyvas, sudarytas iš horizontalių eilučių ir vertikalių stulpelių. Kiekviena lentelės eilutė aprašo vieną objektą – žmogų, knygą, šeimą ar pan. Kiekvienas stulpelis apibūdina vieną objekto savybę, charakteristiką – žmogaus pavardė, knygos leidimo metai, vaikų skaičius šeimoje ar pan ([Bar02]). Kiekviena lentelė turi pirminį raktą, pagal kurį galima vienareikšmiškai rasti norimą įrašą. Reliacinėje duomenų bazėje įeinančios lentelės tarpusavyje susijusios. Šią sąsają išreiškia išorinis raktas. Išorinis raktas – vienos lentelės atributų rinkinys, kuris kitoje lentelėje yra pirminis raktas. Vientisumo sąlygos suteikia loginį pagrindą teisingoms duomenų reikšmėms duomenų bazėje nustatymui, perspėja apie klaidas, pasitaikančias atnaujinant ir apdorojant duomenis. Tokios galimybės labai vertingos, kadangi pagrindinis duomenų bazės tikslas- teikti tikslią informaciją. Reliacinėje teorijoje suformuluota keletas reikalavimų, kuriuos turi tenkinti duomenų bazės duomenys. Svarbiausi iš jų: • kategorijų vientisumas • nuorodų vientisumas • funkcinės priklausomybės Reliacinėje teorijoje realaus pasaulio objektai arba lentelės eilutės vadinami kategorijomis. Kadangi pirminis lentelės raktas vienareikšmiškai nurodo duomenis apie norimą kategoriją, tai pagal kategorijų vientisumo reikalavimą, lentelės rakto atributas negali turėti reikšmės NULL. Nuorodų vientisumo reikalavimas iškelia būtinybę, kad kiekvieno išorinio rakto reikšmė duomenų bazėje sutaptų su viena pirminio rakto reikšme lentelėje, į kurią tas išorinis raktas nukreiptas, arba ta reikšmė turi būti tuščia. Funkcinių priklausomybių esmė – vienų atributų reikšmės eilutėje gali vienareikšmiškai apibrėžti kitų atributų reikšmes. 2.2. SQL SQL (Struktūrizuota užklausų kalba, Structured Query Language) - populiariausia iš šiuo metu naudojamų kalbų, skirtų aprašyti duomenis ir manipuliuoti jais reliacinių duomenų bazių valdymo sistemose. SQL kalboje išskiriamos trys sakinių grupės: • Duomenų apibrėžimo sakiniai (DDL, Data Definition Language). Šiais sakiniais kuriamos duomenų bazės ir lentelės, atliekami kiti veiksmai. • Duomenų apdorojimo sakiniai (DML, Data Manipulation Language), kuriais formuojamos užklausos duomenims išrinkti, atnaujinti, šalinti ar įterpti. • Duomenų valdymo sakiniai (DCL, Data Control Language). Šiais sakiniais koordinuojamas vartotojų darbas su duomenų baze. SQL kalbos ypatybė – SQL sakiniai gali būti įterpti į programas, sudaromas kita programavimo kalba (C, C++, COBOL ir kt.) arba vykdomi interaktyviai. Šiuo metu žinomi trys SQL standartai. Pirmąjį – SQL1 standartą, priimtą 1989 metais, visiškai atitinka dauguma šiuolaikinių reliacinių duomenų bazių valdymo sistemų. 1992 metais pasirodė SQL2 – tai reikalavimai, kurių laikosi dauguma platinamų RDBVS. SQL3, priimtas 1999 metais, turbūt ryškiausiai skiriasi nuo prieš tai buvusių standartų. Šiuo metu RDBVS plėtojamos stengiantis atitikti SQL3 standarto reikalavimus. SQL sakinių sintaksė skirtingose DBVS skiriasi, taip pat skiriasi ir nuo standarto. Praktiškai SQL dialektų yra tiek, kiek Platinamų RDBVS. 3. Dedukcinių ir reliacinių duomenų bazių sistemų skirtumai ir panašumai Dedukcinės duomenų bazės atsirado kaip reliacinių praplėtimas, kai padidėjo informacijos, galimos išreikšti rodiniais ir vientisumo apribojimais naudojimas. Tačiau šiuolaikinės reliacinės duomenų bazės taip pat leidžia apibrėžti rodinius ir apribojimus (trigerius). Tai gal tarp reliacinių ir dedukcinių duomenų bazių jokių skirtumų ir nėra? 3.1. Kalbų galimybių palyginimas Svarbiausio skirtumo priežastis – skirtingos duomenų apibrėžimo kalbos (DDL): dedukcinėse duomenų bazėse naudojama Datalog, o daugelyje reliacinių – SQL ([Pia00]). Bandysime išsiaiškinti, kuri kalba – Datalog ar SQL – gali apibrėžti principus, kurių negali apibrėžti kita kalba iš šių dviejų. Čia palyginsime išraiškingas Datalog galimybes su SQL kalbos 1992 metais priimtu standartu SQL2. Paprasčiausios užklausos reliacinėje duomenų bazėje, tiek vienai lentelei, tiek kelioms, gana nesunkiai išreiškiamos ir dedukcinėmis užklausomis. Pavyzdžiui, norėdami sužinoti apie Saulės vaikus, reliacinės duomenų bazės atveju rašytume: SELECT vaiko_vardas FROM Mamos WHERE mamos_vardas=‘Saulė‘ Ta pati užklausa dedukcinėje duomenų bazėje atrodytų taip: ?– mama(saule, X) Neigiamos literos, sutinkamos išvedimo taisyklėse, SQL2 gali būti apibrėžtos operatoriumi NOT EXISTS. Tarkime norime sužinoti apie mamas, kurios dar nėra močiutės. Užklausa dedukcinės duomenų bazės atveju atrodys taip: ?– mama(X, _) & ¬močiutė(X, _) Simboliu ‚_‘ žymime, kad ši informacija mums nesvarbi, t. y. mums nesvarbu, kas yra tų mamų, vaikai. SQL kalba tai būtų užrašyta taip: SELECT mamos_vardas FROM Mamos WHERE NOT EXISTS ( SELECT močiutės_vardas FROM Močiutė WHERE mamos_vardas=močiutės_vardas) Močiutė šiame SELECT sakinyje yra virtuali lentelė, arba kitaip rodinys, kurį apibrėšime netrukus. Dedukcinės duomenų bazės baziniai faktai atitinka sąryšius. Taigi, baziniai faktai atitinka reliacinės duomenų bazės lenteles. Galime sakyti, kad plečiamoji dedukcinės duomenų bazės dalis atitinka reliacinės duomenų bazės duomenis. Dedukcinės duomenų bazės leidžia išvestinius predikatus, bet ir SQL2 leidžia apibrėžti rodinius. Pavyzdžiui, predikatas močiutė(X, Y):– mama(X, Z) & vienas_iš_tėvų(Z, Y). SQL2 gali būti užrašytas taip: CREATE VIEW Močiutė AS SELECT mamos_varas, tėvų_vardas FROM Mamos, Vienas_iš_tėvų WHERE Mamos.vaiko_vardas=tėvų_vardas Reikia pastebėti, kad Vienas_iš_tėvų čia taip pat virtuali lentelė (rodinys). Rodiniai, išreikšti daugiau nei viena taisykle SQL2 standarte gali būti apjungti operatoriumi UNION. Nors SQL2 gali apibrėžti rodinius, jis neteikia rekursyvaus rodinio mechanizmo. Taigi, predikatas protėvis(X, Y):– vienas_iš_tėvų(X, Y). protėvis(X, Y):– vienas_iš_tėvų(X, Z) & protėvis(Z, Y). negali būti užrašytas SQL2 standarte, Datalog, priešingai, geba tai padaryti. tiesą sakant, tai yra pagrindinis skirtumas tarp Datalog ir SQL2, kuris būtų panaikintas perėjus prie SQL3 standarto, kuris jau leidžia apibrėžti rekursyvius rodinius į Datalog panašia kalba su tam tikrais papildomais apribojimais (šalia panaudojimo apribojimų ir susluoksniavimo). Ciklas priklausomybių grafe (kuris vaizduoja predikatų tarpusavio sąryšius) gali apimti tik vieną predikatą, todėl rekursija turi būti „tiesiška“. Iš esmės tai reiškia, kad predikatas rekursyviojoje užklausos dalyje FROM gali būti sutiktas tik vieną kartą ([Mar03]). SQL3 standarte aukščiau minėtas rekursyvus rodinys gali būti suformuluotas taip: CREATE RECURSIVE VIEW Protėvis (protėvio_vardas, palikuonio_vardas)AS SELECT tėvų_vardas, vaiko_vardas FROM vienas_iš_tėvų UNION ALL SELECT tėvų_vardas, palikuonio_vardas FROM Vienas_iš_tėvų, Protėvis WHERE vaiko_vardas=protėvio_vardas Nerekursyvi dalis šioje užklausoje yra pirmasis FROM, rekursyvi – antrasis. Komercinės reliacinės duomenų bazės dar ir dabar nepilnai tenkina SQL2 standarto reikalavimus, išnaudoja jo teikiamas galimybes. Tai turėtų išsispręsti per artimiausius keletą metų, ir galbūt tada komerciniai produktai jau bus linkę lygiuotis į SQL3 standartą. Jei tai bus pasiekta, tarp dedukcinių ir komercinių reliacinių duomenų bazių nebeliks jokio skirtumo. 3.2. Vientisumo reikalavimų užtikrinimas Vientisumo reikalavimų pagalba galima užtikrinti norimą duomenų bazės būseną, arba norimą būsenų seką. Pirmu atveju kalbama apie statinius vientisumo reikalavimus, antru – apie dinaminius. Vientisumo reikalavimas – tai uždara formulė C, kuri gali įgyti reikšmę true arba false. Duomenų bazės būsena tenkina vientisumo reikalavimą C, jei jis įgyja reikšmę true. Jei vientisumo reikalavimas C įgyja reikšmę false, tai ši duomenų bazės būsena yra neleistina (C netenkinamas). Tarkime turime dedukcinė duomenų bazę, kurioje yra apibrėžti tokios formos predikatai: skyrius(Nr, Pavadinimas) darbuotojas(Nr, Vardas, SkyriausNr) amžius(DarbuotojoNr, Metai) Pagal juos labai nesunku sudaryti reliacinės duomenų bazės modelį. Predikato darbuotojas termas Nr turi būti unikalus kiekvienam darbuotojui. Tai galima nurodyti taip ([Mar03]): E, N1, D1, N2, D2(darbuotojas(E, N1, D1) & darbuotojas(E, N2, D2)  (N1= N2 & D1= D2)) Suvedę į normalinę formą, gauname: E, N1, D1, N2, D2(¬darbuotojas(E, N1, D1)  ¬darbuotojas(E, N2, D2)  (N1= N2 & D1= D2)) Šios formos paneigimas atrodo taip: E, N1, D1, N2, D2(darbuotojas(E, N1, D1) & darbuotojas(E, N2, D2) & (N1 N2  D1 D2)) Dabar galime užrašyti vientisumo reikalavimą: IC1:– darbuotojas(E, N1, D1) & darbuotojas(E, N2, D2) & (N1 N2  D1 D2) Štai taip apibrėžiame pirminį raktą ir kitas reikšmes, kurios turi būti unikalios. Reliacinėje duomenų bazėje pirminiai raktai gali būti apibrėžti kuriant lentelę, arba jau sukurtoje raktiniais žodžiais PRIMARY KEY. Reikšmių unikalumui užtikrinti reliacinėje duomenų bazėje naudojame indeksus. Tarkime, kad negali būti dviejų skyrių su vienodais pavadinimais. Šią sąlygą reliacinėje duomenų bazėje užrašytume taip ([Bar02]): CREATE UNIQUE INDEX Unikalus_Pavadinimas ON Skyrius(Pavadinimas) Mūsų nagrinėjamoje dedukcinėje duomenų bazėje, predikato darbuotojas termas SkyriausNr turi sutapti su bent viena predikato skyrius termo Nr reikšme, nes SkyriausNr yra išorinis raktas, kreipiantis į predikatą (lentelę) skyrius. Be didesnių samprotavimų šį reikalavimą galime užrašyti taip: IC2:– darbuotojas(E, N, D) & ¬skyrius(D, P) Reliacinėje duomenų bazėje išorinis raktas vėlgi gali būti apibrėžtas kuriant lentelę ir vėliau. Kuriant išorinį raktą, čia dar nurodomos atnaujinimo ir šalinimo taisyklės: ALTER TABLE Darbuotojas ADD FOREIGN KEY Į_Skyrių (SkyriausNr) REFERENCES Skyrius ON DELETE CASCADE ON UPDATE RESTRICT CASCADE čia nurodo, kad šalinant, pašalinti ir priklausomas eilutes, o RESTRICT – drausti atnaujinimą, jei yra priklausomų eilučių. Dalykinės taisyklės reikalingos konkrečioms situacijoms nurodyti. Pavyzdžiui, turimoje duomenų bazėje galime nurodyti, kad darbuotojų amžius gali būti nuo 18 iki 63 metų: IC3:– amžius(E, A) & (A63) Reliacinių duomenų bazių atveju dalykinėms taisyklėms išreikšti naudojami trigeriai. Ši sąvoka atsirado jau gana seniai, 1990-aisiais trigeriai jau buvo naudojami daugelyje DBVS, bet SQL2 standarte jo nėra, tad skirtingos DBVS jį apibrėžia skirtingai. Čia trigeris bus apibrėžtas prisilaikant DB2 SQL sintaksės. Trigeriai kuriami sakiniu CREATE TRIGGER, kuriame nurodoma: • duomenų keitimo įvykis (INSERT, UPDATE, DELETE); • trigerio kvietimo momentas: prieš duomenų vykdymą, ar po; • trigerio kvietimo dažnis: kviesti jį tik vieną kartą, vykdant SQL duomenų keitimo sakinį, ar kiekvienai keičiamai eilutei; • trigerio kamienas – vienas ar keli SQL sakiniai, kuriuos reikia įvykdyti, kai trigeris kviečiamas; • trigerio kamieno vykdymo sąlyga: vykdyti besąlygiškai, ar tik tuomet, kai patenkinta konkreti sąlyga ([Bar02]); Taigi, sukurkime trigerį, kuris prieš įterpdamas į lentelę Amžius naują įrašą patikrina, ar tenkinama leistina amžiaus reikšmė. Jei ji netenkinama, išvedamas klaidos pranešimas apie tai. CREATE TRIGGER Leistinas_Amžius NO CASCADE BEFORE INSERT ON Amžius REFERENCING NEW AS NaujasAmžius FOR EACH ROW MODE DB2SQL WHEN (NaujasAmžius63) SIGNAL SQLSTATE '99999' ('Nedarbingas amžius') 3.3. Bazių sandaros palyginimas Reliacinėje duomenų bazėje visa informacija vartotojui pateikiama lentelėmis. Tai gana įprasta, lengvai suprantama ir priimtina duomenų pateikimo forma. Norint sužinoti tam tikro įrašo kažkokią savybę, randama šio įrašo eilutės ir tą savybę atitinkančio stulpelio sankirta. Dedukcinėje duomenų bazėje duomenys patiekiami faktais. Baziniai faktai gali būti atvaizduoti ir reliacine lentele. Pavyzdžiui, turime kažkiek faktų pavidalu didesnis(2, 1), ..., didesnis(6, 5), tai jiems galima sukurti lentelę pavadinimu Didesnis su dviem stulpeliais. Tuo pačiu principu galime atvaizduoti ir užklausų rezultatus ([Bau94]). 3.4. Taikymo galimybių palyginimas Reliacinės duomenų bazės išpopuliarėjo vos tik atsiradusios, šiuo metu jos paplitusios daug labiau, nei kartu paimtos visų kitų rūšių duomenų bazės. Grėsmę tokiam viešpatavimui pastaraisiais metais kelia nebent objektinės technologijos. Objektinių duomenų bazių valdymo sistemų kūrėjai prognozavo, kad jų produktas išpopuliarės taip pat, kaip ir objektinės programavimo kalbos (tokios kaip JAVA, C++), tačiau prognozės iki šiol dar nepasitvirtino. Prie to, kad RDBVS vis dar populiariausios, prisidėjo ir pačių jų raida. Komerciniai RDBVS kūrėjai pripažįsta objektinių technologijų pliusus, tad intensyviai jas diegia, taip praplėsdami sistemų galimybes. Dedukcinėms duomenų bazėms taip pat yra ne mažai taikymo sričių. Viena tokių sričių – sprendimo rėmimo sistemos. Ypač naudojant organizacijos resursus, kuriems reikia pateikti informaciją ne tik apie tų pačių resursų dabartinį ar būsimą statusą, bet ir teikti efektyvų ateities planavimo būdą. Šiai problemai dedukcinės duomenų bazės yra geriausias sprendimas. Kita dedukcinių duomenų bazių taikymo sritis – ekspertinės sistemos, kurios apdoroja didžiulius kiekius informacijos, iš kurios, supaprastinus analizę, gali būti išvesti labai svarbūs faktai. Pavyzdžiui, medicininiai tyrimai ir stebėjimai sukaupia didelius kiekius informacijos, o klaidos atveju pasėkmės gali būti siaubingos. Tuo pačiu klaidų gali pasitaikyti ir medicininio aparato, atsakingo už paciento priežiūrą, darbe. Šioms klaidoms išvengti taip pat gali būti panaudojamos dedukcinės duomenų bazės, kurios leidžia efektyviau vykdyti duomenų analizę taip sumažinant klaidų tikimybę. Dar viena gana tipinė sritis dedukcinių duomenų bazių taikymui – planavimo sistemos. Pavyzdžiui, norint susidaryti paskaitų tvarkaraštį, ar susiplanuoti kelionę aplink pasaulį reikia apsvarstyti didelį kiekį informacijos, nepamirštant galimų alternatyvų ir hipotezių. Taigi, čia taip pat gali pasitarnauti dedukcinės duomenų bazės ([RH94]). Nors buvo paminėta net keletas dedukcinių duomenų bazių taikymo sričių, jos labiau naudojamos teoriniuose taikymuose, komercinėje rinkoje dedukcinės DBVS visiškai nekonkuruoja. Viena iš priežasčių gali būti ta, kad nors daugelis dedukcinių prototipų leidžia efektyvias užklausų apdorojimo ir atnaujinimo technikas, jos nėra pilnai apgalvotos. Todėl daugelis išskirtinių dedukcinių duomenų bazių sistemų bruožų (išplečiančios informacijos atnaujinimas ir valdymas) nėra pilnai tiekiami egzistuojančiuose prototipuose. Išvados Palyginus galimybes tiek vienos tiek kitos duomenų bazės, galima teigti, kad dedukcinė duomenų bazė tinkamesnė kai: • Reikia rekursiško atvaizdavimo; • Norima užklausas ir vientisumo reikalavimus rašyti trumpais ir aiškiais (“logiškais”) sakiniais; • Turima didelė duomenų bazė, kurioje labai džnai vykdoma paieška, Reliacinė duomenų bazė tinkamesnė, kai: • Norima informaciją pateikti ir saugoti lentelėmis (kas daugeliui daug priimtiniau ir suprantamiau) ; • Turima duomenų bazė, kurioje dažni duomenų atnaujinimo veismai. Aišku, šiame darbe atlikta analizė daugiau teorinė. Ateityje norėtųsi pabandyti abi duomenų bazių sistemas praktiškai, tada gal būtų galima aiškiau išskirti kiekvienos teigiamas ir neigiamas savybes; tuo pačiu ir priežastis, kodėl vienos naudojamos taip plačiai, o kitos turi tenkintis tik palyginti siauromis panaudojimo galimybėmis. Literatūros sąrašas [Bar02] R. Baronas. Duomenų bazių sistemos. TEV, Vilnius, 2002. [Bau94] M. Baumeister. Ein Transaktionskonzept für die deduktive Objektbank ConceptBase. http://www-i5.informatik.rwth-aachen.de/mbp/dipl/node1.html. 1994. [BS96] F. Bry, D. Seipel. Deduktive Datenbanken. http://www.gi-ev.de/service/informatiklexikon/informatiklexikon-detailansicht/meldung/31/. 1996. [Mar03] R. Marti. Wissensbasierte Systeme. http://www.inf.ethz.ch/personal/plattner/education/wbs2004/. 2003. [Pia00] M. Piattini. Advanced Database Technology and Design. Artech House, Norwood, 2000. [RH94] K. Ramamohanarao, J. Harland. An Introduction to Deductive Database Languages and Systems. The VLDB Journal, volume 3, number 2, 1994, p. 107-122. Pirmas priedas 1. Dedukcinė duomenų bazė, vaizduojanti giminystės ryšius 1.1. Faktai tėvas(stasys, antanas). mama(saulė, antanas). tėvas(stasys, rūta). mama(saulė, rūta). tėvas(antanas, jonas). mama(rūta, jolanta). tėvas(antanas, ramunė). mama(jolanta, marytė). 1.2. Išvedimo taisyklės T1: vienas_iš_tėvų(X, Y):– tėvas(X, Y). T2: vienas_iš_tėvų(X, Y):– mama(X, Y). T3: močiutė(X, Y):– mama(X, Z) & vienas_iš_tėvų(Z, Y). T4: protėvis(X, Y):– vienas_iš_tėvų(X, Y). T5: protėvis(X, Y):– vienas_iš_tėvų(X, Z) & protėvis(Z, Y). T6: netiesioginis_protėvis(X, Y):– protėvis(X, Y) & ¬vienas_iš_tėvų(X, Y). 1.3. Vientisumo reikalavimai IC1 :– vienas_iš_tėvų (X, X). IC2 :– tėvas(X, Y) & mama(X, Z). 2. Reliacinė duomenų bazė, vaizduojanti giminystės ryšius Mamos Tėvai Nr. mamos_vardas vaiko_vardas Nr. tėvo_vardas vaiko_vardas 1 Saulė Antanas 1 Stasys Antanas 2 Saulė Rūta 2 Stasys Rūta 3 Rūta Jolanta 3 Antanas Jonas 4 Jolanta Marytė 4 Antanas Ramunė

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!