Deduktīvās datubāzes

Kārlis Podnieks, LU

2009.gada 24.aprīlī

 This work is licensed under a Creative Commons License and is copyrighted © 2007-2009 by  me, Karlis Podnieks.

C. J. Date. An Introduction to Database Systems. Eighth Edition. Pearson-Addison-Wesley, 2004, 24.nodaļa.

"Parastās" datubāzes

Piemērs. Relāciju datubāze CILVEKI, tikai viena tabula:
CILVEKS(vards, dzimums, teva-vards. mates-vards).
Vārdus uzskatīsim par atslēgām (t.i. identifikatoriem).

Šajā datubāzē tiešā veidā ir reģistrēti tikai cilvēku tiešie senči, t.i. vecāki. Bet no šiem datiem, ja tie ir pietiekami pilnīgi, var izsecināt arī citu informāciju: kas ir dotā cilvēka vecvecāki (un vēl tālāki senči), cik cilvēkam ir bērnu (un mazbērnu), vai diviem dotajiem cilvēkiem ir kopīgs sencis, citi kopīgi radinieki, iespējamie interešu konflikti utt.

Bet kā šo "izsecināmo" informāciju no mūsu datubāzes var iegūt?

Uzdevums. Uzrakstiet SQL vaicājumus, kas cilvēkam vārdā John atrod: 1) abus vectēvus (visas māsas, visus brālēnus utt.); 2) bērnu skaitu (mazbērnu skaitu utt.).

Relāciju datubāzēs tātad atvasinātās informācijas iegūšanas līdzeklis ir SQL vaicājumi.

Šeit visus izmantotos jēdzienus (vectēvs, māsa, brālēns utt.) nākas "definēt" tieši pašās meklēšanas programmās. Nav pārliecības, ka visas šīs "definīcijas" uzreiz (bez ilgāka skaņošanas procesa) būs korektas, un ka tās visos gadījumos (dažādu autoru programmās) būs vienādas.

Deduktīvās datubāzes / Zināšanu bāzes

Kas tad ir "atvasināta informācija"? Visvispārīgākajā veidā tā ir informācija, kas seko no tiem datiem, kas glabājas datubāzē. Tātad atvasinātas informācijas iegūšana (visvispārīgākajā gadījumā) ir secināšana (reasoning).

Bet ja tā, tad būtu dabiski datubāzē visu informāciju attēlot ar loģikas formulu palīdzību un secināšanai izmantot loģikas aksiomas un izveduma likumus.

Tieši tā tiek būvētas t.s. deduktīvās datubāzes, vai zināšanu bāzes. Šajās bāzēs līdz ar faktiem (parastu datubāzu informāciju, ground axioms) var reģistrēt arī likumus (deductive axioms), kurus izmantojot, no vieniem faktiem izvest citus faktus, t.sk. tādus, kuri tiešā veidā bāzē nav reģistrēti.

Piemērs. Tos pašus datus, kas glabājas datubāzē CILVEKI, var attēlot formālā valodā (predikātu valodā), kurā:

1) cilvēku vārdi ir objektu konstantes, kas šos cilvēkus apzīmē (piemēram, John, Paris), tāda konstante ir ievesta katram cilvēkam, kura informācija glabājas datubāzē;

2) ir mainīgie x, y, z, ..., kuru vērtību apgabals ir "visi cilvēki, kura informācija glabājas datubāzē";

3) cilvēka x dzimumu uzdod divas predikātu konstantes: S(x) - "x ir sieviete", V(x) - "x ir vīrietis";

4) tēva un mātes informāciju uzdod predikātu konstantes: M(x, y) - "x ir y-a māte", T(x, y) - "x ir y-a tēvs".

Mūsu bāzē tad glabātos fakti:

V(John), S(Paris), M(Paris, Peter), T(Peter, John), ...

Šī informācija, protams, ir līdzvērtīga datubāzes CILVEKI informācijai.

Bet līdz ar faktiem mēs savā bāzē varam reģistrēt arī likumus un jēdzienu definīcijas, piemēram (implikāciju šai nozarē pieņemts rakstīt no labās puses uz kreiso - kā valodā Prolog):

VECTEVS(x, y) <- T(x, z) & (M(z, y) v T(z,y)) - likums

VECTEVS(x, y) <-> Ez(T(x, z) & (M(z, y) v T(z,y))) - jēdziena definīcija

Arī datubāzes integritātes nosacījumus mēs varam glabāt kā formulas, piemēram:

AxAy[M(x, y) -> S(x)];

AxAy[T(x, y) -> V(x)];

Ax[S(x) v V(x)];

Ax[~(S(x) & V(x))];

Ax₁Ax₂Az[T(x₁, z) &T(x₂, z) -> x₁=x₂ & ~(x₁=z)];

Ax₁Ax₂Az[M(x₁, z) &M(x₂, z) -> x₁=x₂ & ~(x₁=z)];

utt.

Šādi likumi ir atklāti jānoformulē un jāievada zināšanu bāzē, jo no bāzes programmatūras viedokļa T, M, S, V ir patvaļīgas attiecīgi 2-vietīgas un patvaļīgas 1-vietīgas predikātu kontantes., bet jebkādām citām "noklusētām" īpašībām.

Reiz nodefinējuši, mēs šo jauno jēdzienu varam izmantot vaicājumos, piemēram, valodas Prolog stilā:

?VECTEVS(x, John) - - sameklēt visus John-a vectēvus.

Mūsu jaunajai bāzei, izmantojot loģikas aksiomas un izveduma likumus, būtu jāprot tikt galā ar šādiem vaicājumiem.

Uzdevums. a) Kā definēt bērna, mazbērna, brāļa, māsas, brālēna utt. jēdzienus?
b) Kā definēt jēdzienu SENCIS(x, y) - "x ir y-a sencis"? Vaicājums: ?SENCIS(x, John) - sameklēt visus John-a senčus.

Uzdevums. Pārdomājiet, kā šīs lietas varētu realizēt SQL un citās programmēšanas valodās? Vai tas sanāktu tikpat dabiski?

Ontoloģijas, UML un predikātu valodas

Loģikas formulu izmantošana datubāzēs pirmajā brīdī liekas neparasta. Daudz pierastāka ir ER-diagrammu vai UML klašu diagrammu izmantošana datubāzes struktūras uzdošanai.

Piemērs: kursi, studenti un pasniedzēji.

Piemērs: cilvēki, tēvi, mātes, vīrieši un sievietes.

Bet katras šādas diagrammas precīzu jēgu var nodefinēt, izmantojot loģikas formulas. Diagramma būtībā ir ekvivalenta formulu kopai atbilstošā predikatu valodā.

Daļa no formulām tiek attēlotas ar noteiktiem grafiskiem līdzekļiem (kastītes, līnijas, kardinalitātes, apakšklases, complete, disjoint utt.). Bet ne katru vajadzīgu formulu varēsim uzskatāmi attēlot grafiski. Formulas ir universālāks līdzeklis, salīdzinot ar diagrammām!

Tāpēc diagrammas nevajadzētu mistificēt. Tās cilvēkiem ir ļoti ērtas un ļauj ātri aptvert lietas būtību, jo cilvēka smadzenēs visjaudīgākais procesors ir t.s. redzes centrs. Vizuālu informāciju cilvēks apstrādā visefektīvāk. Toties datoram diagrammas neko nedod - to saturu nākas tulkot, piemēram, ar loģikas formulu palīdzību (vai kā savādāk, tikai formulas arī šeit izrādās visuniversālākais līdzeklis).

Uzdevums. Uzzīmējiet nelielu UML klašu diagrammas piemēru un tad ievediet speciālu predikātu valodu un uzrakstiet šajā valodā formulu kopu, kas būtu ekvivalenta šai diagrammai. Sevišķi uzmanīgi reģistrējiet visus integritātes nosacījumus.

 Atkārtojums

par predikātu (pirmās pakāpes) valodām, interpretācijām, modeļiem, loģiski vispārderīgām un izpildāmām formulām. Spēja ātri lasīt un saprast predikātu valodas formulas, ātri formulēt savas zināšanas predikātu valodā būs ļoti vēlama šī kursa sekmīgai apguvei.

Senči un rekursija

Jēdzienu SENCIS mūsu deduktīvajā datubāzē var ievest ar likumu palīdzību:

SENCIS(x, y) <- M(x, y) v T(x, y);
SENCIS(x, y) <- (M(x, z) v T(x, z)) & SENCIS(z, y);

Otro likumu varētu formulēt arī šādi:

SENCIS(x, y) <- SENCIS(x, z) & SENCIS(z, y);

(t.i. atklāti pasakot, ka SENCIS ir "vecāku predikāta"
M(x, y) v T(x, y) tranzitīvais slēgums).

Valodas SQL standartā, sākot ar 1999.gada versiju, jau tiek atbalstīti rekursīvi vaicajumi (recursive queries). Ar to palīdzību var realizēt vaicājumus, kas saistīti ar senča jēdzienu. [Vai Oracle. MS SQL Server, MySQL tas ir realizēts?]

Pirmās pakāpes valodas ir pārāk vājas, lai definētu senča jēdzienu ar vienas formulas palīdzību! Precīzu definīciju, ko tas nozīmē, un elegantu šīs teorēmas pierādījumu sk. Carlos Areces disertācijā, 2000.

[Ko tad tas precīzi nozīmē? T.i. ko nozīmētu izteikt senča jēdzienu ar vienu formulu? Tas nozīmē, ka, izmantojot kā atomus tikai predikātu konstantes T(x, y), M(x, y), konjunkcijas, disjunkcijas, negācijas, implikācijas un kvantorus, mums vajadzētu uzrakstīt (varbūt, sarežģītu, bet vienu) formulu F(x, y), kurai būtu šāda īpašība: jebkurā valodas interpretācijā jebkuriem objektiem c, d, formula F(c, d) ir patiesa tad un tikai tad, ja šajā interpretācijā c ir d sencis (šī vārda parastajā nozīmē). Tā to formulē Carlos Areces, jo viņš interesējas par abstraktāku problēmu - par patvaļīgas relācijas R tranzitīvā slēguma definējamību. Mūsu gadījumā interepretācijām būtu jāuzliek papildus prasība: tājās nedrīkst būt ciklu - "pats neesmu sev sencis". Vai Areces aprakstītais elegantais pierādījums ir pielāgojams arī šai situācijai? Droši vien, ir...]

Zināšanu bāze vispārīgajā gadījumā

Ja mēs savu zināšanu bāzi B veidosim, izmantojot predikātu valodu ("predikātu loģiku"), tad vispārīgā gadījumā situācija būs šāda:

a) Bāzē ir reģistrētas noteiktas objektu konstantes: c₁, c₂, ..., c_k, un predikātu konstantes: p₁, p₂, ..., p_m (katrai uzdots savs argumentu skaits). [Slēgtās pasaules pieņēmums: pasaulē nav citu objektu kā tie, kas ir apzīmēti ar kontantēm c₁, c₂, ..., c_k. Būtībā tā ir speciāla aksioma jeb likums, kas var būt vairākkārt jāpapildina: Ax (x=c₁ v x=c₂ v ... v x=c_k). Atvērtās pasaules pieņēmums: pasaulē var eksistēt arī citi objekti.]

b) Bāzē glabājas fakti, likumi un jēdzienu definīcijas, t.i. noteiktas formulas F₁, F₂, ..., F_n. Fakti ir atomāras formulas, ar vai bez negācijas, kas nesatur mainīgos: p_i(c_j1, c_j2, ..., c_js), vai ~p_i(c_j1, c_j2, ..., c_js). Būtībā fakti veido datubāzes tabulas. [Slēgtās pasaules pieņēmums: predikāts p_i(c_j1, c_j2, ..., c_js) tiek uzskatīts par patiesu tad un tikai tad, "ja tas ir fakts". Ja datubāzē tāda "fakta" nav, predikāts skaitās aplams - nevis nezināms. Atvērtās pasaules pieņēmums: predikāts p_i(c_j1, c_j2, ..., c_js) tiek uzskatīts par patiesu vai aplamu tad un tikai tad, ja datubāzē ir attiecīgais pozitīvais vai negatīvais fakts. Piemērs: John nav bērnu.] Daļa no likumiem ir integritātes nosacījumi.

c) Vaicājums ir kāda cita formula G. Atbildēt uz šādu vaicājumu nozīmē noskaidrot, vai formula G (vai, varbūt, ~G?) seko formulām F₁, F₂, ..., F_n, t.i. no zināšanu bāzes faktiem un likumiem.

Ja formulai G ir brīvs mainīgais x, tad vaicājumu G(x) mēs saprotam šādi: atrast visas tās konstantes c_i, kam formula G(c_i) seko no F₁, F₂, ..., F_n.

Ko šeit nozīmē "seko"? Ja domā "semantiski", tad tad "formula G seko no formulām F₁, F₂, ..., F_n" nozīmē, ka "jebkurā valodas interpretācijā, kurā patiesas ir formulas F₁, F₂, ..., F_n, ir patiesa arī formula G". Bet tā kā mēs zinām Gēdela teorēmu par pilnību, tad zinām arī, ka šis formulējums ir ekvivalents ar šādu: "formula G ir izvedama no formulām F₁, F₂, ..., F_n, izmantojot predikātu loģikas aksiomas un izveduma likumus".

Tātad, veidojot savas zināšanu bāzes programmatūru, mums būs jāizmanto algoritms, kas, ja dotas formulas F₁, F₂, ..., F_n, G, var (vēlams, ātri) pateikt, vai G seko no F₁, F₂, ..., F_n, vai neseko. Sauksim to par formulu secināšanas uzdevumu.

Diemžēl, jau no 1936.gada ir zināma:

Čērča-Kalmāra teorēma. Ja kādā predikātu valodā ir vismaz viena vismaz divvietīga predikātu konstante, tad formulu secināšanas uzdevums šai valodai nav algoritmiski atrisināms.

Alonzo Church, Laszlo Kalmar

Elegantu šīs teorēmas (gan mazliet vājākā formā) pierādījumu sk. Carlos Areces disertācijā, 2000.

Uzdevums (matemātiska izklaide). Parādiet, ka ja kādā predikātu valodā ir tikai vienvietīgas predikātu konstantes (galīgā skaitā), tad formulu secināšanas uzdevums šai valodai ir algoritmiski atrisināms. [Reducējiet uzdevumu uz izteikumu rēķinu formulu patiesuma noteikšanas uzdevumu.]

Secinājums. Ja zināšanu bāzes būvēšanai mēs pilnā apjomā izmantosim kādu predikātu valodu (ar vismaz vienu vismaz divvietīgu predikātu konstanti), tad mēs šai bāzei nevarēsim izveidot universālu vaicājumu procesoru.

Tātad mūsu zināšanu bāzē pieļaujamie predikātu valodu līdzekļi ir jāierobežo tā, lai secināšanas uzdevums būtu algoritmiski atrisināms. Tikai tad varam cerēt izveidot universālu vaicājumu procesoru.

No dzīves...

Kursa grāmatas autors 792.lpp. atzīmē, ka deduktīvās datubāzes ir ļoti elegants izgudrojums, jo tajās vienotā veidā tiek attēlotas gan bāzes tabulas, gan skati, gan integritātes nosacījumi un vaicājumi. Tāpēc deduktīvās DBPS var piedāvāt unificētākas lietotāja saskarnes.

805.lpp. autors aplūko dažādos terminus, kas literatūrā tiek izmantoti deduktīvo datubāzu (deduktīvo DBPS) apzīmēšanai: zināšanu bāzes, ekspertsistēmas, logic-based systems, logic databases.

Ontoloģijas un semantiskais tīmeklis

Komerciālas tradicionālā stila ("lokālās") deduktīvās DBPS tirgū netiek piedāvātas, tas paliek universitāšu eksperimentālo sistēmu līmenī.

Par perspektīvu šai virzienā šobrīd tiek uzskatīta tikai semantiskā tīmekļa ideja. Sk. Semantic Web^Wikipedia.

Par to, kā darbojas semantiskā tīmekļa datubāzu secināšanas mehānisms, var uzzināt manā kursā
DatZ5033 "Aprakstošās loģikas un secinātāji",
kas jau 3.reizi tiks piedāvāts rudens semestrī.