Baze de Date Aciclice

Concluzionând cele descrise în secţiunile precedente, o schemă “bună” a bazei de date trebuie să posede mai multe calităţi dezirabile. Printre aceste calităţi putem menţiona, în primul rând, formele normale, proprietatea joncţiunii fără pierderi şi conservarea dependenţelor.

Însă, asupra schemei bazei de date mai pot fi definite nişte constrângeri sintactice cum ar fi, spre exemplu, aciclicitatea. Se cunosc diferite tipuri de aciclicitate. Similar unei ierarhii de forme normale ale schemelor, fiecare formă fiind mai restrictivă decât predecesoarea, există şi o ierarhie de tipuri de aciclicităţi. După cum se ştie, proiectantul bazei de date trebuie să ţină cont că, dacă schema relaţională nu se găseşte în forma normală corespunzătoare, atunci pot apărea diverse probleme de actualizare a bazei de date. De asemenea, de competenţa proiectantului ţine şi selectarea gradului de aciclicitate în care doreşte ca schema să fie proiectată.

Schemele aciclice se bucură de o serie de proprietăţi. Cu cât gradul de aciclicitate este mai înalt, cu atât mai “bună” este schema. Mai mult decât atât, unii algoritmi, ce au o complexitate exponenţială asupra schemelor ciclice, asupra schemelor aciclice, sunt polinomiali.

Schemele aciclice ale bazelor de date pot fi caracterizate în diferite moduri. În primul rând, definiţia de aciclicitate poate fi formulată prin forme echivalente. Toate aceste forme se bazează pe reprezentarea schemelor bazelor de date cu ajutorul hipergrafurilor. Unele definiţii de aciclicităţi se aduc, utilizând componentele hipergrafurilor în timp ce altele sunt bazate pe grafuri ordinare construite din hipergrafuri.

Multe din proprietăţile schemelor aciclice pot fi concepute în calitate de caracteristici, în sens că schema are o proprietate particulară, dacă şi numai dacă schema este aciclică. O parte din proprietăţi sunt strâns legate de procesarea interpretărilor la baza de date.

6.1. Scheme hipergrafuri

Întrucât schema bazei de date este o mulţime de scheme relaţionale, e foarte comod de a asocia schemei bazei de date un hipergraf.

Vom aduce noţiunea de hipergraf. Hipergraful este analogic grafului ordinar neorientat, cu excepţia că o muchie a lui nu uneşte numai două noduri, ci o mulţime arbitrară de noduri.

FURNIZOR CONTRACT DATĂ

FURNIZOR ARTICOL PREŢ

FURNIZOR ARTICOL CONTRACT

Fig.6.1. Schema bazei de date Db={FURNIZOR CONTRACT DATĂ, FURNIZOR ARTICOL PREŢ, FURNIZOR ARTICOL CONTRACT}

Definiţia 6.1. Hipergraful H este o pereche (N, E), unde N este o mulţime finită de noduri şi E o mulţime de muchii (sau hipermuchii), care sunt submulţimi nevide ale mulţimii de noduri N.

Mai departe vom identifica un hipergraf numai prin menţionarea muchiilor sale şi implicit vom presupune că mulţimea de noduri este exact mulţimea nodurilor ce aparţin tuturor muchiilor.

Schemei bazei de date îi vom pune în corespondenţă un hipergraf în felul următor. Mulţimea de atribute U ce formează mulţimea universală este mulţimea de noduri, iar fiecare schemă relaţională din schema bazei de date reprezintă o muchie ce include nodurile notate cu atributele din schema relaţională. Hipergraful din fig.6.2 corespunde schemei bazei de date din fig.6.1.

Considerăm două scheme ale bazelor de date din fig.6.3 şi fig.6.4, fiecare conţinând trei scheme relaţionale. Unica diferenţă dintre aceste scheme este că a doua schemă a bazei de date are atributul D în ultima schemă relaţională, în timp ce prima schemă a bazei de date conţine atributul E. Cu toate că această diferenţă la prima vedere pare neesenţială, în realitate, schema din figura 6.3 este aciclică, iar cea din fig.6.4 e ciclică. Mai departe vom vedea că prima schemă posedă o serie de priorităţi dezirabile, dar a doua - nu. Pentru o vizualizare a faptului că a doua schemă este ciclică considerăm hipergrafurile corespunzătoare din fig.6.5.