Baze de date de cunostinte

Baze de date de cunostinte

Bazele de cunostinte mai sunt numite baze de date logice, baze de date interferentiale, baze de date inteligente, etc. Prin aceste sisteme se incearca o cat mai apropiata functionare a bazelor de date de sistemul obisnuit de operare cu date. Diferitele tupluri ale bazelor de date sunt interpretate ca axiome, cererile sunt interpretate ca teoreme, raspunsul la cerere fiind considerat ca o demonstratie in aceste baze de date. Acesta interpretare permite o uniformitate de reprezentare, uniformitate de operare, modelare semantica, aplicatii extinse si altele.

Bazele de cunostinte permit interpretarea unor cereri din limbaje naturale. Ele contin copii ale unor tabele din catalogul bazei de date, tabele ce contin valorile datelor utilizate frecvent, reguli de transformare a frazelor, unele permitand substituirea automata a unor subexpresii, un lexicon continand un tabel care defineste cuvinte din limba naturala ce pot fi utilizate in cereri, cuvinte generale.

Baza de cunostinte este initiata prin construirea lexiconului si a altor parti componente, ea completandu-se in timp cu noi componente sau elemente, de catre utilizatori sau automat, pe baza informatiilor obtinute prin exploatare.

In bazele de cunostinte sunt aplicate rezultatele din calculul propozitiilor si calculul predicatelor. Pe baza transformarilor logice se incearca demonstrarea unor asertiuni tinand seama de axiomele din logica matematica si de informatiile continute de sistem.

Prin axioma deductiva sau regula de interferenta se intelege o regula care permite deducerea unor fapte plecand de la o multime de fapte date. Axiomele deductiv pot fi reprezentate in baza de date prin vederi.

Pentru a demonstra o asertiune de forma:

f₁,f₂,,f_n -g

unde f₁,f₂,,f_n sunt premisele si g este concluzia, se foloseste de obicei metoda reducerii la absurd. Aceasta se realizeaza demonstrand ca formula:

f₁&f₂&&f_n& non geste falsa.

Aceasta se face transformand formula precedenta, cu ajutorul proprietatilor din algebra logica, intr-o formula echivalenta, normal conjunctiva, de forma:

u₁&u₂&&u_m

in care fiecare u_i (i=1,,m) este o disjunctie de atomi care pot fi uneori precedati de „non”. Se listeaza termenii formulei precedente u₁,u₂,,u_m si se deriveaza in continuare alti termeni aplicand legea rezolutiei, de forma:

=((f g)&(non g h)) T (f h)

Daca printre termenii derivati apare multimea vida (termenul „fals”), atunci asertiunea initiala este adevarata, altfel asertiunea este falsa.

Exempu: pentru a demonstra asertiunea urmatoare:

A T (B T C), NOT D OR A, B -D TC

ANALIZA: Filtre numerice iir - lucrarea de laborator ANALIZA: Recursivitate - proiect de tehnologie didactica

unde A,B,C  si D sunt formule, se pleaca de la:

A T (B T C)

NOT D OR A

B

NOT (D T C)

care, aduse la forma normal conjunctiva, dau formulele:

(1) NOT A OR NOT B OR C

(2) NOT D OR A

(3) B

(4) D

(5) NOT C

Aplicand rezolutia pentru formulele (1) si (2) in raport cu A se obtine:

(6) NOT D OR NOT B OR C

apoi, pentru formulele (3) si (6) in raport cu B se obtine:

(7) NOT D OR C

pentru formulele (4) si (7) in raport cu D se obtine:

(8) C

iar pentru formulele (5) si (8) in raport cu C se obtine formula vida notata [], ceea ce demonstreaza ca asertiunea facuta este adevarata.

Cererile pentru bazele de date de cuostinte pot fi exprimate sub forma generala:

A₁ AND A₂ ANDAND A_mTB₁OR B₂ORORB_n

Unde A₁,,A_m si B₁,,B_n sunt de forma r(x₁,x₂,,x_t), cu r predicat si x₁,x₂,,x_t argumente.

Pentru m=0 si n=1, expresia se reduce la un singur predicat:

r(x₁,x₂,,x_t)

Daca toate argumentele sunt constante, predicatul reprezinta o axioma de baza si este o propozitie adevarata. In termeni de baze de date, tuplul (x₁,x₂,,x_t) este unul din tuplurile existente intr-o relatie R din baza de date. In acest caz, predicatul r afirma ceva in concordanta cu intelesul pe care il are relatia R.

Pentru m>0 si n=1 se obtine clauza :

A₁AND A₂ ANDAND A_mTB

care poate fi privita ca o axioma deductiva. Aceasta da o definitie (partiala) a predicatului din partea dreapta a implicatiei in functie de predicatele din partea stanga. Poate fi privita si ca o constrangere de integritate.

Vederile unei baze de date pot fi privite ca modele teoretice. In aceste modele, domeniile de baza contin valori sau constante ce pot sa descrie anumite obiecte ale lumii reale, acestea formand universul contextului. Relatiile de baza reprezinta o multime de predicate sau formule deschise ce urmeaza sa fie interpretate in acel univerrs. Fiecare tuplu al unei relatii reprezinta o particularizare a universului corespunzator (formula inchisa  - fara variabile) care are valoarea adevarat pentru universul respectiv. Constrangerile de integritate sunt tot formule inchise interpretabile pe acelasi univers. Tuplurile si constrangerile de integritate pot fi privite ca formand multimea axiomelor ce definesc o anumita „ teorie logica”. Baza de date poate fi privita ca multimea tuturor teoremelor ce se pot demonstra pornind de la axiome. Evaluarea cererilor se face analog cu demonstrarea teoremelor.

Ca axiome ale unei baze de date pot fi considerate urmatoarele:

1.     Axiomele de baza corespund tuplurilor relatiilor de baza, ele definind asanumita baza de date extinsa (extensional database  - EDB)

2.     O axioma de completitudine pentru fiecare relatie prin care se afirma ca nu exista alte tupluri decat cele ce apar efectiv in relatia respectiva. Aceasta se mai numeste presupunrerea de inchidere (closed world assumption - CWA)

3.     Axioma numelui unic, prin care se afirma ca fiecare constanta se distinge de toate celelalte constante.

4.     Axioma inchiderii domeniului, prin care se afirma ca nu exista alte constante in afara de cele existente in domeniile bazei de date.

5.     O multime de axiome (standard) prin care se defineste predicatul „=”.

Un sistem deductiv de baze de date este un SGBD care permite construirea vederilor cu demonstrare teoretica si care este capabil, in particular, fapte suplimentare din baza de date existenta aplicand axiome deductive sau reguli de inferenta la aceste fapte. Axiomele deductive impreuna cu constrangerile de integritate formeaza ceea ce se numeste continutul intern al bazei de date (intensional database - IDB) si acesta, impreuna cu extinderea bazei de date (partea de informatii), formeaza baza de date deductiva (deductive database).

Un limbaj in care se pot exprima asertiuni si cererei pentru baza de date este Datalog (analog Prolog), an care instructiunile sunt de forma urmatoare:

B A₁ AND A₂ ANDAND A_n

unde B este concluzia si A₁A_n sunt premisele, ele fiind predicate nenegate ce contin numai constante si variabile. Daca in loc de B se pune „?” are loc afisarea rezultatului obtinut prin evaluarea facuta pentru expresia indicata in partea dreapta dupa ce sunt inlocuite valorile curente ale variabilelor.

In acest limbaj pot sa apara si definiri recursive. Acestea pot fi tratate prin tehnici de unificare si de rezolutie. O alta metoda, evaluarea naiva, pleaca de la baza de date extinsa si aplica in mod repetat premisele definitiei pana se obtine rezultatul concluziei. O imbunatatire a acestei metode, metoda seminaiva de evaluare, evita recalcularea tuplurilor rezultate in pasii anteriori. Filtrarea statistica sau reducerea multimii factorilor relevanti, foloseste informatia de cerere pentru a modifica premisele, putand astfel sa elimine tuplurile nefolositoare din extensia bazei de date.