Forme Normale In Baze de Date Orientate Obiect

Introducere

Modelele de baze de date orientate obiect oferă construcții bogate pentru realizarea unor obiecte complexe și posibilitatea refolosirii prin moștenire. Lucrarea noastră prezintă problema modelării schemelor bazelor de date orientate obiect.

Problema modelării unei scheme relaționale se referă la îmbunătățirea unei scheme inițiale cu una echivalentă, mai bună. Noțiunea de echivalență include proprietățile de join fără pierdere (asigură identitatea datelor în schema inițială/finală) și păstrarea dependenței (asigură identitatea dependențelor în cele două scheme). Conceptul de mai bun se referă la o schemă cu o redundanță mai mică și cu mai puține probleme la actualizare. Scopul rezolvării problemei redundanței este de a minimiza spațiul de stocare necesar unei baze de date prin limitarea duplicării infomației din relații.

Redundanța și anomaliile legate de actualizare au fost rezolvate într-o anumită măsură printr-o serie de forme normale pentru baze de date. Trei forme normale (notate 1NF, 2NF, 3NF) au fost propuse de Codd (1972), pentru ca în 1974 cea de a treia formă să fie prelucrată, rezultând forma mai puternică Boyce-Codd. Aceste forme normale se bazează pe corelarea dintre atributele unei relații și cheia sa primară, folosind dependențele funcționale. Formele 4NF, 5NF propuse mai târziu se bazează pe conceptele de dependențe multivaluate, respectiv dependențe join.

Proprietatea de join fără pierdere și cea de păstrare a dependenței au fost studiate în diferite moduri, conducând la două abordări ale schemelor de baze de date. Abordarea pură subliniază strict proprietățile de join fără pierdere și păstrarea dependenței, pe când abordarea top-down accentuează mai ales redundanța și problemele de anomalii la actualizare.

Abordarea pură pentru modelarea schemelor se bazează pe așa numita relație universală, unde toate relațiile vor fi definite prin proiecții ale acestei relații universale, iar toate regulile privind universul în discuție vor fi specificate relativ la această relație prin dependențe funcționale și/sau multivaluate (Beeri et al. 1978).

Abordarea top-down preia un set de relații date în forma normală și folosește metode adecvate de descompunere pentru a genera relații mai eficiente. Procesul de normalizare poate fi privit ca un proces de „rupere” a atributelor unei relații în relații mai mici cu scopul de a limita problemele de redundanță sau de anomalii la actualizare.

Extensii ale modelului relațional „plat” care, după cum am arătat, a fost intens studiat, au dus la modelele de baze de date Non-First Normal Form (). A fost propusă o nouă formă normală, Nested Normal Form (NNF) pentru relații nested, relații ce limitează problemele de redundanță sau anomalii la actualizare. NNF se bazează pe conceptul de arbore pentru o schemă normală care e o relație (nested) fără redundanțe (Özsoyoglu&Yuan, 1987). Caracteristica relației nested în NNF este aceea că nodurile arborelui corespondent induc restricții de tip dependență multivaluate. Din punctul de vedere al proprietăților de join fără pierdere și păstrarea dependenței, acest model poate fi văzut ca o extindere a abordării pure la scheme conținând structuri complexe. Lucrări în același sens au fost propuse de Roth&Korth (1987) sau Ling și Yan (1994).

În anii ’80 design-ul bazelor de date s-a ridicat de la nivelul logic la unul conceptual, în care sunt des folosite modele de baze de date semantice (Hull și King 1987). Aceste modele conceptuale (Hammer și McLeod 1981; Elmasri et al. 1985) integrează abilități structurale mai bogate decât în modelul relațional plat, permițând moștenirea, atribute multivaluate și atribute complexe (compuse din alte atribute). În contextul modelării conceptuale, formele normale reflectă o schemă relațională normalizată atunci când sunt traduse într-un model relațional plat.

Paradigma orientată obiect (Atkinson et al. 1989) oferă o soluție în tratarea complexității în modelarea universului în discuție. Modelele de baze de date orientate obiect suportă mecanisme complexe ce permit refolosirea datelor și a proceselor prin moștenire, construirea unor obiecte complexe (folosind constructorii ortogonali tuplu și set), identificarea obiectelor independent de valoarea lor (folosind mecanismul de identitate a obiectelor); toate aceste avantaje nu sunt suportate de modelele de scheme tradiționale prezentate anterior.

Lucrarea de față urmărește teoria de normalizare a bazelor de date orientate obiect propusă de Z. Tari et al. în 1997 și are următoarea structură:

▪ Capitolul 1. Utilizăm modele conceptuale mai bogate (orientate obiect) ce încorporează noțiunile de identitate a obiectului, obiect complex, moștenire. O extensie a restricțiilor de tip dependență funcționale și multivaluate va lua în considerare complexitatea schemei: dependențe de cale, dependențe locale și dependențe globale. Ele exprimă legăturile obiectului în funcție de diferitele tipuri de drumuri existente. La nivel schemă, restricțiile de dependență sunt multitip (dependențe de cale) și exprimă legăturile inter-obiect. La nivel obiect, restricțiile de dependență exprimă legăturile intra-obiect, și anume legăturile dintre obiect și componentele sale (dependențe locale și globale). În finalul capitolului vom prezenta axiome de inferență pentru diferitele tipuri de restricții de dependență.

▪ Capitolul 2. Normalizarea se bazează pe un proces ce compară interpretarea dată de utilizator universului discutat cu interpretările reflectate de obiecte în schemă. O interpretare este de fapt o mulțime de restricții de dependență ce furnizează o anumită „înțelegere” a semanticilor aplicației date; vom face distincție între interpretarea utilizator (implică un set de restricții de dependență specificate de utilizator) și interpretarea obiect (mulțime de restricții de tip dependență reflectate de structurile complexe ale obiectelor din schemă). Spre deosebire de design-ul bazelor de date tradițional în care o relație are o interpretare unică, un obiect poate avea mai multe interpretări obiect (reflectând posibilele interpretări multiple ale drumurilor sale). Mulțimea tuturor interpretărilor unui obiect se numește modelul obiectului, iar un obiect se află în formă normală dacă interpretarea utilizator este exprimată (tehnic, derivabilă din) prin modelul obiectului.

▪ Capitolul 3. În final vom propune doi algoritmi de normalizare a unei baze de date. Primul, bazat pe o abordare top-down, transformă o schemă dată în una normalizată, folosind regulile pentru normalizarea obiectului date în capitolul 2. Al doilea algoritm, cu câteva elemente de abordare pură, construiește o schemă normalizată din „nimic”, folosind dependențele utilizator. Algoritmul necesar într-o situație dată depinde de complexitatea structurii obiectului.

Capitolul 1

Noțiuni de bază

Capitolul descrie un model de baze de date orientate obiect ce va fi utilizat la dezvoltarea teoriei de normalizare. Modelul suportă cele mai multe concepte ale paradigmei obiect, inclusiv obiecte complexe, identitatea obiectului, moștenire și clasă. Unele concepte, ca suprascrierea sau încapsularea nu sunt aplicabile în această abordare, deoarece ele se referă la comportamentul schemelor orientate obiect, pe când teoria noastră de normalizare se referă la aspectele structurale.

Pe lângă descrierea modelului de baze de date orientate obiect vom include și definiții clare pentru restricțiile de tip dependență, acestea specificând semanticile obiectelor și legăturile lor. Restricțiile de tip dependență sunt extensii la arhicunoscutele dependențe funcționale și multivaluate și descriu diferite legături ale obiectelor, inclusiv legături intra-obiect sau inter-obiect.

Restricțiile de tip dependență pentru scheme orientate obiect sunt definite prin proiectarea operațiilor. În acest scop vom dezvolta o algebră de proiecție pentru modelele orientate obiect ce suportă accesul la diferite obiecte folosind o operație de proiecție simplă (permite accesul la componentele directe ale unui obiect), o operație de proiecție complexă (permite accesul la toate obiectele date printr-un drum) și o operație de proiecție condiționată ce va permite accesul la obiectele selectate într-o instanță a unei căi date.

1.1 Modelul bazelor de date. Algebra de proiecție

Un obiect în contextul bazelor de date este o colecție de atribute ce reprezintă cunoștințele de structură (atribute enumerate) și comportament (atribute procedurale) ale unui domeniu. Un obiect O va fi reprezentat ca O(Do),unde Do este tipul obiectului (instanța unui obiect se construiește prin instanțierea tipului obiectului). Atributul va fi privit ca o funcție definită pe o mulțime de obiecte, luând valori pe o mulțime de obiecte. Vom numi un atribut care returnează întotdeauna o mulțime cu un singur element atribut singleton-valued; altfel, vom vorbi despre atribute multivaluate.

Schema prezentată în continuare suportă noțiunea de obiect cu proprietățile sale (atribute în obiecte). Legăturile dintre obiecte pot fi unidirecționale (agregarea: de exemplu, între Proiect și Laborator) sau bidirecționale (asocierea: de exemplu, Persoană-Mașină). Moștenirea asigură reutilizarea informației într-o schemă orientată obiect.

In exemplele următoare ident va desemna domeniul tuturor identificatorilor, iar {nume: tip} reprezintă un atribut multivaluat.

În particular, vom defini obiectul Personal ca: Personal ([IDpers: ident; prenume: string; {nume: string}; salariu: integer; {Conduce: Mașină}; {Copil: Persoană}; {Laborator: lab}]), unde obiectul lab este definit ca lab([IDlab:integer; numeLab:string; {Proiect: Proj}; {adresa:string}]). În acest exemplu atributul Conduce modelează parțial semantica asocierii dintre Persoană și Mașină, aceasta fiind completată de atributul Proprietar al obiectului Mașină.

(Fig.1: diagrama unui exemplu de schemă orientată obiect)

În acest context, definim o schemă orientată obiect ca pe o structură , unde reprezintă mulțimea de obiecte a schemei, iar este mulțimea restricțiilor de dependență peste obiectele din . Structura definește o bază de date orientată obiect, unde prin am notat mulțimea instanțelor elementelor din .

Tabela1: Exemplu de instanță pentru schema din figura1

Instanțele obiectelor sunt construite prin instanțierea tipurilor obiectelor. Fiecare instanță a unui obiect are un identificator de obiect. Atributele au de asemenea identificatori, derivând după restricțiile specificate obiectului respectiv. De exemplu, Tabela1 prezintă instanțe pentru diferite obiecte din schema dată de Figura1. Prima instanță pentru obiectul Personal este identificată prin P1 și are forma {P1, Ionescu, {Mihai}, {M1, M2}, {P3}, 8000000, {[1, AAA, {[5, {r1, r2}], [9, {r4}]}], [2, BBB, {25, {r5}}]}, {București,Brașov}}.

1.1.1. Căi (drumuri)

Restricțiile de dependență necesită introducerea unor concepte adiționale; unul dintre acestea se referă la relațiile dintre obiecte. Secvența reprezintă drumul (sau calea) de la la prin obiectele ,…, dacă fiecare obiect ()se leagă de predecesorul și/sau succesorul său printr-o legătură atribut sau o legătură obiect. Recunoaștem 3 tipuri de drumuri:

Calea verticală pleacă de la un obiect la una din componentele sale directe; de exemplu Personal-Laborator-Proiect este o cale verticală, ce returnează toate proiectele din toate laboratoarele la care lucrează un membru al personalului; de asemenea, Personal-nume este cale verticală deoarece nume este parte componentă a tipului obiectului Personal.

Calea orizontală reprezintă o secvență în care alternează numai obiecte; de exemplu Persoană-Copil-Copil-Conduce (am folosit ciclul Peroană-Copil recursiv) sau Persoană-Conduce-Asigurare; prima cale returnează mulțimea de mașini conduse de nepotul unei persoane date. Drumurile orizontale includ și relațiile de agregare inversă (relația dintre Persoană și Asigurare). Agregarea este unidirecțională (navigare într-un singur sens); permițând relația dRestricțiile de dependență necesită introducerea unor concepte adiționale; unul dintre acestea se referă la relațiile dintre obiecte. Secvența reprezintă drumul (sau calea) de la la prin obiectele ,…, dacă fiecare obiect ()se leagă de predecesorul și/sau succesorul său printr-o legătură atribut sau o legătură obiect. Recunoaștem 3 tipuri de drumuri:

Calea verticală pleacă de la un obiect la una din componentele sale directe; de exemplu Personal-Laborator-Proiect este o cale verticală, ce returnează toate proiectele din toate laboratoarele la care lucrează un membru al personalului; de asemenea, Personal-nume este cale verticală deoarece nume este parte componentă a tipului obiectului Personal.

Calea orizontală reprezintă o secvență în care alternează numai obiecte; de exemplu Persoană-Copil-Copil-Conduce (am folosit ciclul Peroană-Copil recursiv) sau Persoană-Conduce-Asigurare; prima cale returnează mulțimea de mașini conduse de nepotul unei persoane date. Drumurile orizontale includ și relațiile de agregare inversă (relația dintre Persoană și Asigurare). Agregarea este unidirecțională (navigare într-un singur sens); permițând relația de agregare „inversă” schema își păstrează semantica. De exemplu, navigarea Persoană→Asigurare returnează de fapt toate contractele de asigurare semnate de o persoană la diferite companii. Astfel, chiar dacă există agregare Asigurare-Persoană, specificarea căii orizontale Persoană-Asigurare este validă.

Calea compusă este o combinație de căi verticale și orizontale; de exemplu, Persoană-Conduce-Asigurare-IDcontract este o cale compusă ce returnează contractele de asigurare ale tuturor mașinilor conduse de o persoană dată.

În exemplele date, drumurile încep prin instanțierea unui obiect (de exemplu, Personal-Laborator-Proiect va fi instanțiat de un IDpersonal dat). Vom cerceta instanțierea de obiecte de obiecte specificate printr-o cale dată. De exemplu, Personal-Laborator-Proiect poate fi instanțiat specificând un IDpersonal și un IDlab, în acest caz returnându-se toate proiectele la care lucrează membrul specificat în laboratorul dat de IDlab.

Din aceste motive s-a introdus noțiunea de instanță de cale: o instanță a căii este o secvență de instanțe , unde este o instanță a lui , (de exemplu, instanța P1-M2-CA2 a căii Persoană-Conduce-Asigurare-IDcompA înapoiază compania la care a apelat P1 pentru a-și asigura mașina M2 pe care o conduce). În aceste condiții, accesul la obiecte poate fi generic (folosesc căi) sau restrictiv (folosesc instanțe de căi).

1.1.2. Proiecții

O proiecție după o cale sau o instanță de cale poate fi definită ca o imbricare de proiecții multiple pe componentele obiectului. De exemplu, proiectarea instanței P1 a obiectului Personal pe Proiect după calea Personal-Laborator se execută prin proecții succesive pe atributele Laborator și respectiv Proiect. Într-un prim stadiu, P1 este proiectat pe atributul componentă directă {laborator: Laborator}, care va returna setul mulțimilor de laboratoare în care lucrează P1 (pentru aceasta vom nivela setul mulțimilor de laboratoare). Într-o a doua fază, fiecare element al mulțimii de laboratoare generat este proiectat după atributul {proiect: Proiect}. Deoarece fiecare element aparținând mulțimii de laboratoare include de asemenea un set de proiecte, va trebui să nivelăm și această set de mulțimi de proiecte din atributul Laborator. Procesul de nivelare repetată a proiecției continuă până când nu mai găsesc mulțimi imbricate (nested) în atribut.

Pentru următoarele definiții vom folosi următoarele notații: dată o instanță de obiect și o cale sau o instanță de cale , vom nota prin proiecția lui peste O și prin proiecția lui peste O după . În plus, vom prescurta notația pentru instanțele obiectelor, referindu-ne doar la identificatorii lor.

Tipuri de proiecții prin care poate fi accesat un obiect:

Proiecția simplă implică mereu o cale verticală sau orizontală uninivel (exemplu: proiecția lui P1 pe {Laborator} sau {Conduce}). Formal, proiecția simplă a instanței a obiectului pe una din componentele sale directe se definește ca . Mai mult, o proiecție simplă a unei instanțe poate implica și retragerea altor instanțe ce o conțin (pot accesa instanțele obiectului Asigurare ce conțin instanța P1 a obiectului Persoană). Acest tip de proiecție se definește astfel: date două obiecte O și , unde este cale dar nu este cale, proiecția unei instanțe a obiectului O peste obiectul este definită ca , unde ’ este o instanță a lui iar (exemplu: P1[Asigurare]={12290, 11049}).

Proiecția complexă implică căi de nivele multiple, cum ar fi proiecția lui P1 pe obiectul Companie de Asigurări după calea Persoană-Conduce-Asigurare (realizată prin proiecții multiple ale lui P1 pe obiectele Conduce și Asigurare). Formal, proiecția unei instanțe a unui obiect O pe un alt obiect după calea compusă se definește prin proiecții succesive pe obiectele (sau =). De exemplu, =(P1[Laborator])[Proiect]={[5, {r1, r2}], [9, {r4}], [25, {r5}]} returnează toate proiectele unui laborator la care lucrează P1.

Proiecția simplă condiționată este o proiecție simplă în care obiectul țintă este condiționat de o instanță dată (de exemplu, proiecția lui P1 pe Laborator după condiția IDlab=1). Formal, proiecția condiționată a unei instanțe a obiectului O pe o componentă directă după instanța de cale a căii este:

if then else if ( este obiect monovaluat) then

else {y/ y and y=}.

De exemplu, ={1, AAA, {[5, {r1, r2}], [9, {r4}]}, {București, Brașov}} returnează o instanță specificată a obiectului Laborator, identificată de IDlab=1.

Proiecția complexă condiționată implică drumuri de instanță multinivel, în care există cel puțin o condiție atașată unui obiect din drumul selectat (de exemplu, proiecția lui P1 pe obiectul CompanieDeAsigurări după instanța de cale P1-M2-11049). Vom defini proiecția unei instanțe a obiectului O pe obiectul după instanța de cale pentru calea compusă ca ). De exemplu, ={r1, r2} returnează rapoartele proiectului identificat de IDproiect=5 la care lucrează persoana P1 în laboratorul dat de IDlab=1.

Deoarece acest model include noțiunea de atribut multivaluat, vom defini un operator adițional de „nivelare” a mulțimilor de mulțimi: nivelarea unei instanțe a obiectului pe una din componentele sale directe se definește ca . Exemplu de nivelare: P1[Laborator]=(P1[{Laborator}])[Laborator]={[1, AAA, {[5, {r1, r2}], [9, {r4}]}], [2, BBB, {25, {r5}}], {București, Brașov}}.

1.2 Restricții de tip dependență

În modelul relațional restricțiile de tip dependență reflectă legături atribut-atribut; în modelele orientate obiect în aceste restricții sunt incluse conceptele de cale și identificator de obiect.

Dată o schemă orientată obiect , definește mulțimea de restricții de tip dependență pe elementele din . Aceste dependențe iau forme diferite, în funcție de tipul căilor dintre obiecte. Dependențele bazate pe căi orizontale se numesc dependențe de cale, și sunt dependențe multitip deoarece exprimă legătura dintre obiecte diferite. Dependențele bazate pe căi verticale pot fi locale sau globale. Dependențele locale sunt restricționate la o singură instanță a unui obiect, pe când cele globale cuprind toate instanțele respectivului obiect.

1.2.1. Restricții de tip dependență de cale

Dependențele de cale (Path Dependency) exprimă semantica legăturilor dintre obiecte multitip și se bazează pe căile orizontale.

Definiția 1.1. Există restricție de tip dependență de cale (restricții PD) între obiectele X și Y după calea (notat ) dacă și numai dacă pentru fiecare instanță a lui X și pentru orice instanță a lui ce pornește din X se obține același rezultat din Y. Putem formaliza după algebra de proiecție propusă anterior: astfel încât este cale între X și Y și este instanță a lui X, iar și instanțe ale lui ce conțin pe => .

Pe exemplul de mai sus observăm că este o restricție PD validă, care arată că toate mașinile conduse de o persoană sunt asigurate de aceeași companie. Pornind cu instanța P1 și urmând orice instanță de drum spre obiectul CompanieDeAsigurări prin diferiți identificatori de instanțe ale obiectului Mașină (după cum s-a specificat în dependența de cale) obținem instanța CA2 a obiectului CompanieDeAsigurări. Există doar două instanțe de cale ce pot fi folosite în verificarea dependențelor și . Proiecțiile corespunzătoare au forma [CompanieDeAsigurări]={CA2} și [CompanieDeAsigurări]={CA2}.

Restricțiile PD se ocupă doar de restricții multitip (pe obiecte diferite). Prin ele nu pot exprima alte tipuri de restricții de dependență, cum ar fi cele dintre obiecte și componentele lor. De exemplu restricția dintre Personal și {adresă} arată faptul că adresele specificate sunt legate de viața personală a membrilor echipei, deci nu sunt legate de alte tipuri de informații, cum ar fi Laborator sau Proiect. Această proprietate poate fi exprimată astfel: de fiecare dată când luăm o instanță de cale de la Personal la {adresă} vom obține aceeași instanță a obiectului {adresă}. Acest tip de restricție este o „rafinare” a restricțiilor PD în care există o cale unică între obiecte componente ale aceluiași predecesor (dependențe locale). Totuși, în unele situații, pot exista două obiecte O1 și O2 astfel încât O1 nu este componentă a lui O2 și nici O2 nu este componentă a lui O1, obiecte ce pot fi legate prin dependență locală. Această restricție de dependență semnifică faptul că prin orice instanță de cale de la O1 la O2 obțin același rezultat referitor la O2.

1.2.2. Restricții de tip dependență locală

Definiția 1.2. Obiectul Y se numește local dependent de X dacă și numai dacă pe orice cale de la X la Y se obține același rezultat în Y. Formal, avem restricție de tip dependență locală (LD), notat astfel încât este instanță a lui X, și sunt căi distincte între X și Y, și instanțe pentru , respectiv ce conțin pe => (restricțiile locale se ocupă de legăturile „intra” dintre obiect și componentele sale).

Pe tabela dată avem Personal{adresă} o restricție LD validă (orice membru al personalului are o mulțime de adrese). În acest caz observăm că există o infinitate de drumuri între Personal și {adresă}, construite folosind bucle cum ar fi Personal-Copil-Personal sau Personal-Conduce-Asigurare-Personal. Utilizând axioma de derivare PD5 (tranzitivitatea restricțiilor PD) pentru dependențe de cale (paragraful 1.3), avem că toate dependențele de cale ce folosesc bucle sunt derivate din dependențele de cale , și , dependențe valide în Tabela1.

1.2.3. Restricții de tip dependență globală

Cele două tipuri de restricții definite anterior sunt aplicabile doar câte unei instanțe. Atunci când dependențele locale sunt aplicate tuturor instanțelor ale aceluiași obiect cu același identificator vom vorbi despre restricții globale (GD).

Definiția 1.3. Obiectul Y se numește global dependent de X (pe scurt, Y dependent de X), notat X→Y X este local dependent de Y și oricare două instanțe egale în X sunt egale în Y. Formal, spunem că X→Y și cu , și sunt căi ce conțin pe X și Y, și instanțe pentru , respectiv conținând instanțele și respectiv , atunci .

Prin se înțeleg toate instanțele bazei de date. Proiecția acestei mulțimi pe un obiect X (notat ) reprezintă toate instanțele posibile ale acestui obiect. se mai numește populația de instanțe ale lui X, definită astfel:

if X este un obiect entitate then ={ instanță a lui X} else ={y/ este instanță a obiectului entitate E, E este predecesor pentru X, z}, unde reprezintă cel mai scurt drum între obiectele E și X.

Remarcăm că exemplul dat mai sus ca restricție LD este și restricție GD (Persoană→{adresă}).

1.2.4. Restricții de cheie

Modelele de baze de date orientate obiect includ noțiunea de identificator de obiect pentru obiect entitate, pentru care atributele complexe nu au un concept echivalent deoarece nu există independent de altă informație. Această noțiune va oferi identificarea instanțelor atributelor complexe folosite de instanțele de cale în navigarea în interiorul bazei de date. Această navigare activează verificarea diferitelor forme de restricții de dependență introduse.

Identificatorul unui atribut complex se bazează pe noțiunea de restricție de tip cheie. O restricție de cheie peste un atribut cmplex A descrie o partiționare a componentelor directe ale lui A în trei părți A1, A2, A3 unde A1 este cheie, A2 este complet dependent de A1 iar A3 este dependent de A1 și de unii din predecesorii săi. De exemplu, luarea unei instanțe a obiectului Laborator pe calea Personal-Laborator-Proiect se face după valoarea atributului IDlab, cheia atributului complex Laborator (atributul numeLab este complet dependent de IDlab, iar Proiect și adresă sunt dependente de combinația atributului IDlab și identificatorul de obiect al predecesorului său, IDpersonal).

Definiția 1.4. Vom spune că M poate fi cheie pentru obiectul O dacă și numai dacă:

M este o mulțime de componente ale lui O

astfel încât:

a) , , M formează o partiție a lui O

b) , , M→

c) , unde este cheie pentru și este predecesor pentru O (1≤i≤r) și

3. Nu există nici o submulțime M1 a lui M care să verifice condițiile de mai sus. Observăm că pentru un atribut complex pot exista mai multe chei care să-l caracterizeze. Din acestea se selectează una ca identificator al atributului.

Din informațiile date de Figura1 și Tabela1 reiese că IDproiect poate fi cheie pentru obiectul Proiect datorită dependenței {Personal, IDproiect, IDlab}→{raport}.

1.3 Axiome de inferență

Prezentăm în continuare axiome de inferență pentru diferite tipuri de restricții de dependență în modelele de baze de date orientate obiect, axiome bazate pe proprietățile căilor. Ele necesită introducerea a două noțiuni complementare: satisfiabilitate (╞) și derivabilitate (├): dată o mulțime de restricții F și o restricție w notăm:

(satisfiabilitate) F╞w : dacă w este satisfăcută, atunci și F trebuie să fie satisfăcută

(derivabilitate) F├ w : w este rezultatul aplicării uneia sau mai multor axiome de inferență prezentate mai jos pe restricțiile mulțimii F.

Dependențe de cale (folosirea mai multor căi într-o restricție PD reprezintă o concatenare de drumuri):

PD1 (reflexivitate)

PD2 (reuniune)

PD3 (extensie)

PD4 (simplificare)

PD5 (tranzitivitate)

PD6 (atribuire) A atribut al lui X:

PD7 (multiset)

Demonstrație (PD6 și PD7 sunt evidente):

PD1:

Fie Y=, și X=, unde k≤n și . drum între Y și X și instanțe pentru calea ce conțin pe :

PD2:

Ipoteza: instanță pentru X, instanțe pentru : = și instanță pentru X’, instanțe pentru : =. Se observă că și sunt instanțe pentru calea ce conțin pe și avem: ( nu poate fi proiectat pe , iar nu poate fi proiectat pe ). q.e.d.

PD3:

Ipoteza: instanță pentru X, instanțe pentru : =. instanță pentru Z, este instanță pentru XZ. Avem două cazuri:

1. : și (q.e.d.)

2. : Fie X-Z-Y (sau Z-X-Y)cea mai simplă formă a lui și fie două instanțe de cale pentru , instanțe ce conțin pe .

și ; dar din ipoteză avem că →q.e.d.

PD4:

instanță pentru X, instanțe pentru Z avem:

și ; dar , deci definiția restricției PD este satisfăcută.

PD5:

Ipoteză: instanță pentru X, instanțe pentru ce conțin pe , și pentru instanță a lui Y, instanțe pentru ce conțin pe , .

, iar (q.e.d.)

Dependențe locale

LD0 XY

LD1 (reflexivitate)

LD2 (atribuire)

LD3 (extensie) XY XZY

LD4 (pseudotranzitivitate) XY și YZ

LD5 (multiset) XY{X}{Y}

LD6 (generalizare) X este un sub-obiect al lui Y XY

Dependențe globale

GD0 X→Y XY

GD1 (atribuire)

GD2 (extensie)

GD3 (pseudotranzitivitate)

GD4 (descompunere) X{Y} și

GD5 (generalizare) X este un sub-obiect pentru Y

Capitolul II

Normalizarea obiectelor

Problema modelelor de baze de date orientate obiect este descrierea unei scheme conceptuale corecte care să reflecte interpretarea dată de utilizator universului de discuție (UD). Prin interpretare utilizator vom înțelege un set de restricții GD specificate de utilizator ca modul său propriu de înțelegere a semanticii UD (un obiect poate avea mai multe interpretări, rezultate din complexitatea structurii sale).

Normalizarea unui obiect poate fi văzută ca o proces de comparare a interpretării utilizator cu interpretarea obiect. Dacă interpretarea utilizator este derivabilă (prin axiome de inferență) din interpretarea obiect, putem spune că obiectul se află în formă normală; în acest caz avem consistență între interpretarea dată de utilizator universului pus în discuție și interpretările reflectate de structura obiectului. Dacă un obiect este nenormalizat, structura sa va trebui alterată pentru a reflecta căile induse de interpretarea utilizator.

2.1 Exemplu

Un obiect al unei scheme date poate avea multiple interpretări obiect datorită semanticilor multiple ale căilor sale verticale. De exemplu, calea verticală Personal-Laborator-Proiect-raport din figura 2 are șase interpretări obiect posibile:

I1 ={Personal→{Laborator}, Laborator→{Proiect}, Proiect→{raport}}; această interpretare obiect arată că proiectele sunt realizate într-un laborator și că unset de rapoarte este scris pentru fiecare proiect; de asemenea, rapoartele scrise pentru un proiect nu sunt legate automat de membrii personalului laboratorului.

I2={Personal→{Laborator}, Laborator→{Proiect}, (Laborator, Proiect)→{raport}}: un raport trebuie să fi fost scris pentru un proiect într-un laborator dat.

I3={Personal→{Laborator}, Laborator→{Proiect}, (Personal, Laborator, Proiect)→{raport}}: fiecare membru al personalului lucrează într-un laborator dat, dar nu neapărat la un proiect; de asemenea, rapoartele proiectelor sunt scrise de membri ai personalului din laborator.

I4={Personal→{Laborator}, Proiect→{raport}, (Personal, Laborator)→{Proiect}}: fiecare persoană lucrează la un proiect, rapoartele fiind scrise pentru fiecare proiect; în plus, rapoartele nu sunt scrise automat de personalul unui laborator și nu sunt neapărat legate de un anumit laborator.

I5={(Personal, Laborator)→{Proiect}, (Laborator, Proiect)→{raport}, Personal→{Laborator}}: toți membrii personalului lucrează într-un laborator, iar rapoartele proiectelor se referă la cercetarea din laborator.

I6={(Personal, Laborator, Proiect)→{raport}, (Personal, Laborator)→{Proiect}, Personal→{Laborator}}: toți lucrează la proiecte într-un laborator, iar rapoartele sunt scrise de membrii echipei laboratorului.

Interpretările mai sus menționate reflectă toate înțelesurile posibile sau interpretările drumului, incluzând interpretarea utilizatorului în cazul obiectului normalizat Personal. Deoarece obiectul Personal din Figura2 mai are o cale Personal-Laborator-dată, aceasta induce interpretări obiect adiționale: I={Personal→{Laborator}, Laborator→{dată}} și I= {(Personal, Laborator)→{dată}, Personal→{Laborator}}.

Mulțimea interpretărilor pentru obiectul Personal se definește prin diferitele interpretări posibile ale drumurilor conținute de Personal. Deoarece calea Personal-Laborator-Proiect-raport are șase interpretări, iar Personal-Laborator-dată are două interpretări, rezultă că obiectul Personal are 12 interpretări descrise prin diferite interpretări ale celor două drumuri. De exemplu, I1U I este o interpretare obiect pentru Personal.

În general, dat fiind un obiect O cu o cale verticală O-O1-…-On, aceasta are n! interpretări posibile, de forma sau (în funcție de cardinalitatea obiectului On), cu (). Presupunînd că P1,..,Pm sunt căile verticale ale lui O și că fiecare Pj conține |Pj| obiecte (), atunci numărul de interpretări obiect ale lui O este . Vom numi mulțimea tuturor acestor interpretări obiect modelul obiectului, model ce oferă semantica reflectată de structura complexă a obiectului respectiv. În cazul obiectului Personal, modelul său implică toate semanticile posibile ale celor două drumuri ale sale, Personal-Laborator-Proiect-raport și Personal-Laborator-dată (toate combinațiile posibile ale mulțimilor {I1, I2, I3, I4, I5, I6} și { I , I }).

Dacă interpretarea utilizator nu este derivabilă din modelul obiectului, vom spune că acesta este nenormalizat, iar dependențele din interpretarea utilizator incoerente; ele vor fi folosite la restructurarea obiectului. O dependență incoerentă induce o cale neexprimată în structura obiectului, structură ce va fi alterată pentru a reflecta calea indusă de respectiva dependență. Procesul de restructurare se termină atunci când structura obiectului devine coerentă cu toate restricțiile GD date de utilizator.

Ilustrăm procesul de normalizare descris mai sus în exemplul din Figura2. Presupunem că interpretarea utilizator pentru Personal conține restricțiile GD (Personal, Proiect)→{raport} și (Proiect, raport)→{dată}. Prima nu poate fi derivată din interpretările obiect ale lui Personal, deoarece toate dependențele obiectului raport ar trebui să conțină obiectul Laborator (Teorema 1 pentru demonstrare formală). Totuși, restricțiile GD utilizator specificăfaptul că rapoartele scrise de persoane penru proiecte sunt independente de obiectul Laborator, deci obiectul Personal nu este în formă normală. Pentru a exprima semantica restricției GD incoerentă (Personal, Proiect)→{raport} (normalizarea obiectului Personal), împărțim calea inițială Personal-Laborator-Proiect-raport în două drumuri Personal-Proiect-raport și Personal-Proiect-Laborator, după cum se vede în figura 2b.

Să considerăm cealaltă restricție GD pentru obiectul Personal, (Proiect, raport)→{dată}. Aceasta nu poate fi derivată din obiectul Personal (Figura 2b) deoarece Proiect, raport și dată nu induc nici o cale în acest obiect. În acest caz restructurarea drumului (analog celei anterioare) nu poate fi aplicată. Pentru a exprima o asemenea dependență, soluția este gruparea obiectelor Proiect, raport și dată într-un obiect complex O1. Acest obiect va avea cheia (Proiect, raport) și atributul dată. Deoarece dependența (Personal, Proiect)→{raport} este validă în schemă, raport va deveni un atribut al obiectului Proiect (=O1). În final, formalizarea obiectului Personal are forma din Figura 2c.

În exemplul anterior s-au folosit două operații de restructurare la normalizarea obiectului Personal, acestea acoperind toate transformările posibile ce pot fi folosite în normalizarea unui obiect. Prima operație se referă la obiecte „legate” (conectate printr-un drum) și va fi clasificată ca transformare bazată pe cale. A doua operație se referă la obiecte neconectate, oferind o transformare orientată-obiect a informațiilor nelegate.

Figura 2: Normalizarea obiectului Personal

2.2 Modelul unui obiect: caracterizare formală

Definiția 2.1. Numim dependența A→B coerentă dacă și numai dacă A-B este cale; altfel vom spune că dependența este incoerentă (de exemplu, {Personal, Proiect}→{raport} este o dependență incoerentă a obiectului Personal).

Definiția 2.2. Interpretarea unui obiect este o mulțime de restricții GD coerente. O interpretare se numește maximală dacă și numai dacă nu poate fi derivată din altă interpretare obiect. Exemplu: I1={Personal→{Laborator}, Laborator→{Proiect}, {Laborator, Proiect}→{raport}, {Personal, Laborator}→{data}} este maximală pentru obiectul Personal, spre deosebire de I2={Personal→{Laborator}, {Personal, Laborator}→ →{data}, {Personal, Laborator}→{Proiect}, {Laborator, Proiect}→{raport}} care derivă din I1.

Definiția 2.3. Fie toate interpretările maximale ale obiectului O. Interpretarea se numește modelul lui O. Formal, dat fiind un obiect O, vom nota prin interpretarea utilizator pentru O și cu modelul lui O.

Având la dispoziție aceste definiții, vom caracteriza în continuare restricțiile GD din modelul unui obiect.

Teorema 1. M este modelul obiectului E dacă și numai dacă M verifică următoarele condiții:

(1) este identificatorul lui E și

A este atribut direct monovaluat al lui E, atunci →A M

A este atribut direct multivaluat al lui E, atunci →{A} M

K este cheie pentru E și K≠, atunci K→ M și →K M;

(2) Dacă este o componentă directă complexă a lui E, este identificatorul lui și

B este atribut direct monovaluat al lui , atunci →BM și →BM

B este atribut direct multivaluat al lui , atunci →{B}M și →{B}M

este o cheie pentru și ≠, atunci →M și →M;

(3) Dacă sunt componentele lui E, unde este cale pentru E, este identificatorul lui (1≤i≤n), și dacă

B este un atribut direct monovaluat al lui , atunci pentru orice 1≤j≤n , unde

B este un atribut direct multivaluat al lui , atunci pentru orice 1≤j≤n , unde

este o cheie pentru și ≠, atunci →M și →M;

(4) Nu există alte dependențe în M.

Demonstrație:

(necesitatea) Fie E un obiect E; notăm cu M modelul său. Orice dependență coerentă a obiectului E (în forma A→B sau A→{B}) aparține lui M, altfel s-ar contrazice definiția modelului (mulțime de dependențe maximale). Dat un atribut al lui E:

▪ (Clauza 1) dacă este o componentă directă a lui E, atunci este dependentă de identificatorul (→ sau →), în funcție de cardinalitatea atributului ; astfel, restricția GD aparține modelului M

▪ (Clauzele 2 și 3) dacă este un atribut complex al lui E, obiectele de pe căile de la E ce folosesc determină potențialele restricții GD coerente. Să considerăm o cale pentru E ce conține pe . Orice restricție GD de forma este o interpretare posibilă pentru calea dată, deci restricția GD este coerentă. Astfel, ar trebui să fie în modelul M. Deoarece atributul , este complex, poate fi rescrisă ca . Se observă că dacă B este atribut multivaluat, demonstrația este aceeași. Totuși, când B este atribut mandatar (de ordine), el poate fi folosit ca și cheia atributului A: .

(suficiența) Considerăm o mulțime M ce conține restricții GD în forma prezentată de clauzele teoremei. Demonstrăm că M este un model conținând toate interpretările maximale ale obiectului E.

Fiecare restricție GD din mulțimea M este dependență coerentă. Referitor la clauzele teoremei, construcția mulțimii M se face luând în considerare doar acele dependențe care formează o cale (pentru atribute simple sau complexe). Astfel, M se referă numai la restricții GD coerente.

Vom partiționa mulțimea M într-un set de interpretări maximale ale obiectului E și vom demonstra că orice dependență maximală a obiectului E aparține de (sau este derivată din) unul din elementele partiției. Presupunem că E are k drumuri și că a j-a cale are forma , j≤k. Se observă rapid că E poate fi reprezentat ca o matrice de forma

………………..

………………..

……………………………

………………..

↑

atributul

Pentru fiecare atribut complex (coloana j), considerăm următoarele restricții GD:

▪atribut :

▪atribut : ; această mulțime conține toate restricțiile coerente posibile cu ținta

▪atribut : ; această mulțime conține toate restricțiile GD coerente cu ținta .

Mulțimile astfel definite (,,..,) conțin toate restricțiile GD ce folosesc ,.., și sunt consistente cu clauzele din teoremă. Astfel . Folosind interpretările diferitelor căi ale lui M, vom încerca să construim toate interpretările posibile pentru obiectul E, selectând toate restricțiile GD în diferite interpretări ale căilor lui E. Se găsește ușor că există n! interpretări posibile pentru fiecare cale E–..-, . Vom nota aceste interpretări de cale cu pentru calea E–..-, . Considerăm toate interpretările posibile ale obiectului E din interpretările căilor sale, construite prin selectarea unei interpretări posibile a fiecărui drum. În acest caz avem n!*n!*..*n!=k*n!. Notăm aceste interpretări prin cu două proprietăți importante: sunt maximale și maximal unice pentru interpretările lui E.

Considerăm inițial maximalitatea interpretărilor . O interpretare a fost construită prin alegerea a k-interpretări a k-drumuri pentru obiectul E. Mai mult, în diferite stadii ale construirii interpretărilor lui E nu folosesc două mulțimi identice de k-intepretări. Rezultă că este interpretare maximală deoarece diferă de alte interpretări ale lui E prin cel puțin o interpretare de cale (aleasă din mulțimile ).

Până acum am obținut interpretările maximale ale obiectului E. Trebuie să demonstrăm că mulțimile sunt singurele interpretări maximale ale acestui obiect. Acest lucru este simplu, deoarece modul de construcție a interpretărilor maximale ale lui E arată că s-au luat în considerare toate cazurile prin selectarea fiecărei interpretări pentru fiecare cale. Mai mult, conțin numai restricții GD din mulțimea M, deci M╞ și ╞M. Concluzionăm că M este un model al obiectului E deoarece este echivalent cu o mulțime de interpretări maximale. (q. e. d.)

2.3 Forme normale obiect

Am introdus conceptul de formă normală obiect, unde interpretarea utilizator este derivabilă din modelul obiectului. Am folosit simbolul ╞ pentru a specifica derivarea restricțiilor de dependență. Astfel, dată o dependență w și o mulțime de dependențe F, F╞w arată faptul că w este rezultatul aplicării uneia sau mai multor axiome de inferență pe elementele lui F. Dacă un obiect se află în formă normală, restricțiile sale de depndență sunt consistente cu structura și căile obiectului normalizat.

Definiția 2.4. Un obiect E este în formă normală dacă și numai dacă orice componentă complexă a lui E are un identificator și ╞ .

Teorema 2. Dacă un obiect E este în forma normală, atunci sunt adevărate următoarele afirmații:

(1) Dacă A→B , unde A și B sunt componente ale lui E, atunci A→B;

(2) Dacă B este o componentă directă monovaluată pentru un obiect din E, atunci există o mulțime de atribute cheie , unde este o cheie a lui în E și este o componentă directă a lui (), și ;

(3) Dacă B este o componentă directă multivaluată a lui , atunci există o mulțime de atribute cheie , unde este o cheie a obiectului în E și este o componentă directă a lui (), și ;

(4) Nu există dependențe printre atributele noncheie ale componentei O a lui E.

Demonstrație: Folosim Teorema 1 (de caracterizare a restricțiilor GD ale modelului unui obiect). Clauzele teoremei arată că (i) fiecare restricție GD utilizator este derivabilă din model și (ii) fiecare componentă a unui atribut complex este dependentă de o mulțime de atribute ce formează o cale în obiect; mai mult, această dependență aparține interpretării utilizator. (q. e. d.)

Următoarea teoremă oferă condițiile necesare pentru ca un obiect să fie în formă normală. Condițiile se referă la acele dependențe care sunt consistente cu structura obiectului complex (sunt derivabile din modelul obiectului). Dependențele care nu sunt consistente cu forma normală obiect sunt incoerente.

Teorema 3. Un obiect E este în forma normală dacă și numai dacă:

(1) Dacă A→B este dependență utilizator (), atunci este valabilă una din afirmațiile:

A-B este cale în E

A este o mulțime de chei pentru componente ale lui E, unde este componentă directă a lui (), iar B este componentă directă monovaluată a lui

A este componentă directă a unui obiect O de cardinalitate 1:n și B este componentă directă monovaluată a lui O

(2) Dacă A→{B} este dependență utilizator (), sunt valabile afirmațiile:

A-B este cale în E

A este o mulțime de chei pentru componente ale lui E, unde este un atribut direct al lui () și B este o componentă directă monovaluată a lui

A este o componentă directă a unui obiect O de cardinalitate 1:n și B este o componentă directă monovaluată a lui O.

Demonstrație:

Considerăm un obiect normalizat E; din teorema 1 și teorema 2 reiese ușor că fiecare restricție GD induce o cale în obiectul E

Presupunem că există un obiect nenormalizat E care satisface clauzele teoremei 3; deoarece E nu este normalizat, există o restricție GD ce nu poate fi derivată din modelul lui E. Formal, avem: . Presupunem că w are forma sau . Este evident că nu este cale în B, altfel ar fi dependență coerentă (și deci, conform teoremei 1, ar fi derivabilă din modelul lui E).

A doua clauză a teoremei arată că sunt chei pentru o mulțime de componente ale lui E (pe care le notăm cu ). Fiecare restricție din cu ținta B (fie X→B) ar trebui să conțină în partea stângă toate obiectele (altfel X ar fi o submulțime pentru , ceea ce înseamnă că restricția GD poate fi derivată din X→B folosind axioma GD2 pentru restricții de dependență). Notăm cu toate restricțiile GD din cu ținta B. Fiecare element din are forma . Aceste dependențe nu sunt coerente, deoarece conform ipotezei, nu este cale. Aceasta contrazice definiția lui , unde , iar este definit doar de definiții coerente (vezi teorema 1).

Analog se demonstrează al doilea caz al teoremei 3, în care în partea stângă a unei dependențe se află un atribut multivaluat. (q. e. d.)

2.4 Reguli de normalizare

Paragraful detaliază regulile necesare la producerea formei normale obiect dintr-o mulțime de restricții de dependență utilizator. Ideea de bază a regulilor de normalizare este identificarea acelor dependențe din specificația interpretării utilizator care nu sunt derivate din modelul obiectului; altfel spus, un utilizator specifică unele căi de acces care nu există în schemă. Pentru a normaliza obiecte, vom analiza dependențele incoerente și vom modifica structura obiectului pâne ce aceste dependențe devin coerente (reflectă căile de acces ale utilizatorului).

Vom folosi Teorema 3 ca bază în identificarea regulilor de normalizare. Aceste reguli restructurează cele mai mici căi implicând obiectele specificate în dependențele incoerente. Căile cele mai scurte sunt importante în normalizare deoarece restructurarea focalizează mulțimea minimală de obiecte legate de restricția GD incoerentă, iar cu cât operația de restructurare afectează mai puține obiecte, cu atât mai mult se păstrează semantica schemei.

Prima regulă de normalizare identifică restricțiile GD din interpretarea obiect care nu induc o cale în schema orientată obiect (Teorema 3, clauza 1). Acestea au în general forma A→B (sau A→{B}), unde A și B aparțin unei aceleiași căi, dar A-B nu formează o cale. A doua regulă se ocupă de restricțiile GD de forma A→B (sau A→{B}) în care A este o mulțime de obiecte nelegate (aparțin de căi diferite). Scopul acestor reguli este acela de a asigura faptul că toate obiectele din restricția GD incoerentă vor fi legate fie prin restructurarea unei căi (când A și B nu induc o cale, dar aparțin unui aceluiași drum), fie prin gruparea obiectelor (când A și B sunt pe aceeași cale).

Regula 1: Dat un obiect E, dacă există o dependență incoerentă A→B (sau A→{B}) și există o cale care conține pe A și B, atunci calea se împarte în două subdrumuri și : prima conține doar obiectele A și B iar a doua conține obiectele A și obiectele din

Intuitiv, dacă A→B nu este o restricție GD coerentă, din definiție A-B nu este cale pentru E. Pentru a exprima o asemenea dependență în obiectul E, A-B ar trebui să fie cale, iar celelalte obiecte din ar trebui să formeze o altă cale. În final A-B este restructurată în două căi echivalente, și -B.

Considerăm structura obiectului E prezentat în figura 3(a). Presupunem că E satisface următoarele restricții GD: {E→{A1}, A2→{A3}, A1→{A4}, A1A4→{A2}, A1A4→{A5}}=. Atributele A1 și A5 sunt independente de acces, deoarece A5 poate fi accesat prin calea A1-A4-A5 (A1-A4-{A5}). Aceasta înseamnă că A1A4→{A5} nu este o dependență coerentă. Considerând modelul obiectului E (conține numai dependențe coerente), din nu pot deriva A1A4→{A5}. Obiectul E este normalizat prin „ruperea” căii A1-A2-A3-A4 în A1-A2-A3 și A1-A4-A5 după cum se vede în figura 3(b). Obiectul E din figura 3(b) nu este normalizat deoarece A1A4→{A2} nu este restricție GD coerentă, adică A1-A4-A2 nu este cale pentru obiectul E. Aplicăm Regula 1 din nou, folosind această restricție GD în restructurarea obiectului E (punem pe A2 componentă pentru A4). Forma finală a lui E este cea din figura 3(c).

Figura 3. Normalizarea obiectelor (caz 1)

Regula 1 se referă la obiecte de pe aceeași cale, care nu respectă prima clauză din Teorema 3. Există însă situații în care dependențele incoerente implică obiecte care nu aparțin aceleiași căi („violează” celelalte condiții ale Teoremei 3). Regula 2 dată mai jos se referă la această situație, grupând obiecte cu asemenea restricții GD în cadrul aceluiași obiect predecesor. Să luăm ca exemplu o restricție incoerentă A2A3→A5 a obiectului E din figura 4(a). Deoarece A2, A3, A5 nu aparțin aceluiași drum, se va crea un nou obiect ca o componentă a lui E cu cheie A2A3 și A5 atribut. Deoarece A3 este un atribut al lui A2, este obiectul A2 (obiectul normalizat din firgura 4(b)).

Figura 4 (Normalizarea obiectelor)

Regula 2: Dat un obiect E, dacă toate dependențele din E care folosesc obiecte complexe sunt coerente și dacă există o restricție GD A→B astfel încât A→B, E se transformă prin crearea unui obiect O cu proprietățile:

▪ O este o componentă directă a lui E de cardinalitate (min(), min()), unde A=, iar () reprezintă cardinalitățile minime și maxime ale lui  ; atributul devine o componentă directă monovaluată a lui O ()

▪ B este componentă directă a lui O

▪ A este cheie pentru O.

Exemplu: Considerăm structura din figura 5(a), cu următoarele restricții ={A→{B}, AB→{C}, ABC→{D}, E→{F}}.

Figura 5. Normalizarea obiectelor (caz 2)

Aplicând regula 2 se creează un nou obiect O1 pentru exprimarea căii ABC-D (5b), ABC fiind identificatorul lui O1. Folosim regula 2 recursiv pe dependențele incoerente rămase. De exemplu, AB→{C} nu este restricție GD coerentă deoarece AB-C nu este cale. El va fi restructurat ca în figura 5(c) prin crearea unui nou obiect O2. AB→{C} devine O2→{C}, deoarece AB este cheie pentru O2. Obiectul O2 din figura 5(c) nu este normalizat deoarece A→{B} nu este coerentă (A nu este cheie pentru O2). Creăm un nou obiect O3 pentru exprimarea acestei restricții (5d); obiectul A devine o cheie în O3. Forma finală a obiectului din figura 5(d) este normală deoarece fiecare restricție GD este exprimată printr-o cale adecvată.

2.5 Completitudine

Vom demonstra intuitiv completitudinea regulilor de normalizare propuse mai sus, pentru a asigura acoperirea gamei complete de transformări pe obiecte.

Presupunem că mulțimea {Regula 1, Regula 2} nu este completă, adică există un obiect nenormalizat E în care nu pot aplica nici una din cele două reguli. Aceasta înseamnă că există o retsricție GD A→B (sau A→{B}) ce nu poate fi derivată din modelul lui E. Din Teorema 3, A-B nu este cale:

(1) A și B aparțin aceluiași drum, dar împreună nu formează o cale. Altfel spus, între A și B există alte obiecte pe calea . În această situație pot aplica Regula 1, rupând calea în două subcăi, unde A și B vor forma o cale, iar calea rămasă va conține obiectele dintre A și B pe

sau

(2) A și B nu aparțin aceleiași căi (obiecte nelegate). Pentru această situație folosim a doua regulă, ce creează un nou obiect complex pentru gruparea lui A și B. Acest nou obiect va fi identificat prin A datorită restricției GD dintre A și B

Cele două reguli sunt folosite de algoritmi pentru construcția obiectelor normalizate prin restructurarea lor. Deoarece mulțimea de reguli de normalizare este completă, în cazul în care folosirea lor pe un obiect nenormalizat duce la transformări infinite ale obiectului atunci trebuie să existe conflicte între restricțiile GD utilizator. De exemplu, dacă obiectul E din figura 4(a) ar avea restricțiile A1A2→A3 și A1A4→A5, precum și o restricție adițională A2A3→A5, vom avea un ciclu infinit de transformări datorită conflictului dintre dependențele A1A4→A5 și A2A3→A5.

Problema detectării conflictelor printre restricțiile GD este că folosirea regulilor duce la calcule infinite. Totuși, în următorul capitol vom propune doi algoritmi de producere a formelor normale obiect, ale căror complexități pot fi folosite ca bază în determinarea conflictelor între restricțiile GD utilizator.

Capitolul 3

Algoritmi pentru derivarea formelor normale obiect

Capitolul detaliază algoritmi de normalizare pentru producerea formelor normale obiect. Algoritmii propuși se bazează pe două principii:

▪ Primul algoritm pleacă de la ideea că o schemă orientată obiect deja existentă este doar un model inițial care trebuie restructurat pentru a reflecta restricțiile impuse de utilizator referitor la universul în discuție. Această abordare este iterativă: se execută rafinări succesive ale obiectelor până la obținerea schemei finale (corecte). Algoritmul folosește cele două reguli de normalizare pe diferite obiecte ale schemei, până când toate restricțiile GD utilizator devin coerente. De asemenea, vom da o soluție de detectare a conflictelor între restricțiile GD utilizator (în cazul în care există).

▪ Al doilea algoritm consideră că schema existentă nu este principala sursă de informație, dar poate fi folosită ca punct de plecare. Principiile se referă la folosirea restricțiilor GD utilizator pentru generarea unei scheme consistente cu interpretarea utilizator; schema inițială este folosită ca mulțime de obiecte universale, în care toate atributele se află pe același nivel fără nici o imbricare, reconstruindu-se structurile obiect adecvate. Algoritmul preia restricțiile GD utilizator și identifică posibilele imbricări (nesting) între atributele obiectelor universale. Imbricarea se execută derivând cheile posibile din restricțiile GD utilizator. Incluziunea între chei definește nesting-ul complex între obiecte.

3.1 Generarea formelor normale obiect prin restructurare

Dată o schemă S= (unde este mulțimea de obiecte, iar interpretarea utilizator ), algoritmul de transformare convertește pe S într-o schemă normalizată prin aplicarea regulilor 1 și 2 de normalizare pe elementele lui . La fiecare pas al algoritmului 1 se produce o versiune a mulțimii , deci vom genera o mulțime de versiuni , , .., , unde este mulțimea obiectelor normalizate.

Algoritm 1 (ALGORITM DE TRANFORMARE)

INPUT: Mulțimea de obiecte și interpretarea utilizator (toate restricțiile GD pentru schemă)

OUTPUT: Mulțimea de obiecte normalizate

Begin

Pentru fiecare obiect din execută:

Begin

Pentru fiecare A→B (sau A→{B}) do

dacă A-B nu este cale dar A și B aparțin aceleiași căi

atunci aplică Regula 1 obiectului pentru a exprima A-B

altfel aplică regula 2 obiectului pentru crearea obiectului AB

end

end

Complexitatea algoritmului de transformare depinde de următoarele statistici: numărul de obiecte din schemă (notat cu n), lungimea maximă a căilor din schemă (notat cu m) și numărul maxim de căi orizontale pe care le poate avea un obiect (notat cu p).

Un obiect normalizat este generat în cel mult (m-1)!*p pași, deoarece numărul de interpretări pentru o cale dată este (m-1)!*p. Deoarece am n obiecte, complexitatea acestui algoritm este O((m-1)!*np).

Analizând complexitatea algoritmului 1 se observă că atunci când obiectele conțin nesting de atribute în grad scăzut (m este mic), algoritmul este polinomial (O(n)). Totuși, când gradul de imbricare este ridicat, algoritmul devine costisitor. Din acest motiv adăugăm un algoritm mai eficient, numit de descompunere și fuziune ce evită folosirea regulilor de normalizare, reconstruind structura complexă a obiectului din interpretarea utilizator.

Complexitatea algoritmului 1 oferă un prim pas spre identificarea conflictelor în restricțiile GD utilizator. Este evident că, dacă algoritmul 1 nu se oprește după O((m-1)!*np) pași, atunci există un conflict între unele din restricțiile GD date de utilizator, pentru care acesta ar trebui să ofere o rezolvare.

3.2 Generarea formelor normale obiect prin reconstrucție

Algoritmul dat mai sus normalizează obiectele astfel încât ele să reflecte interpretarea utilizator. În continuare vom da trei algoritmi ce reconstruiesc structurile obiect din interpretarea obiect.

▪ Algoritmul 2 preia o mulțime de obiecte și o nivelează pentru a îndepărta orice imbricare de atribute complexe, producând obiecte numite universale. Din restricțiile GD utilizator asociate fiecărui obiect universal se identifică apoi posibilele clustere de atribute. Aceasta se realizează prin identificarea cheilor (relațiile dintre componentele obiectului universal). Fiecare cluster poate fi descompus dacă are mai mult de o cheie, iar dacă un cluster poate fi descompus atunci există subgrupări de obiecte ce trebuie identificate.

▪ Cînd procesul de descompunere a clusterelor s-a terminat (subgrupările generate nu mai pot fi descompuse), algoritmul 3 construiește structura arbore pentru fiecare arbore final folosind cheia identificată pentru acest cluster, precum și toate restricțiile GD asociate obiectelor respectivului cluster. Acest pas construiește structura complexă adecvată a obiectului prin identificarea relațiilor intercluster din incluziunea cheilor grupării. Altfel spus, dacă o cheie K1 este inclusă în altă cheie K2 atunci arborele clusterului identificat de K1 conține arborele grupării identificată de K2. Împreună, arborii și interrelațiile creează formele adecvate ale obiectelor, reflectând restricțiile GD date de utilizator.

▪ Algoritmul 4 adună arborii rezultați din algoritmul 3 în funcție de nodurile și muchiile lor comune; arborele final reprezintă structura complexă a obiectului normalizat.

3.3 Algoritmi de descompunere și fuziune

Dată S o mulțime de restricții GD, notăm prin închiderea lui S, definită ca cea mai mică mulțime de restricții GD derivabile din S prin axiomele de inferență. poate conține restricții GD redundante sau derivabile din restricțiile existente. Din acest motiv renunțăm la restricțiile GD redundante sau derivabile rezultând o nouă mulțime numită acoperirea minimală a lui S, notată . Reconstruirea structurii complexe a unui obiect se realizează prin identificarea poențialelor clustere ale componentelor obiectului folosind restricțiile GD conținute de acoperirea minimală. Analizând partea stângă a restricțiilor, obținem cheile clusterelor, orice intersecție între chei oferind interconexiunea dintre clustere.

Definiția 3.1. Dacă S este o mulțime de restricții GD , atunci X→Y în se numește:

▪ trivială dacă Y sau YX

▪ stânga-reductibilă dacă și X’→Y.

O dependență se numește redusă dacă nu este trivială sau stânga-reductibilă, unde identificarea restricțiilor GD reduse date de utilizator se realizează prin verificarea redundanței unei restricții.

Definiția 3.2. O mulțime S de restricții GD este acoperire minimală dacă:

▪ este redusă

▪ și , atunci S=S’.

Se observă că dacă S este acoperire minimală atunci S=. De asemenea, acoperirea unei acoperiri minimale este o acoperire: =, deoarece conține doar restricții GD neredundante din . Calculând acoperirea acoperirii minimale, restricțiile redundante din pot fi derivate din datorită proprietăților restricțiilor GD redundante. Din acoperirea minimală a mulțimii S, definim conceptele referitoare la clustere:

▪ Keys(S) este o mulțime ce conține partea stângă a restricțiilor GD din . Formal, Keys(S)=. Mulțimea Keys(S) identifică potențialele grupări de obiecte în S

▪ Dep(X, S) implică toate obiectele dependente de X prin restricțiile lui S. Formal Dep(X, S)=. Dată o cheie X dintr-un cluster, elementele sale sunt identificate ca obiecte dependente de X în S.

În continuare vom prezenta modul de prezentare a conceptelor date în procesul de normalizare. Primul pas spre normalizarea unei scheme S= este identificarea clusterelor; acest pas este realizat de procedura Decompose() care folosește cheile derivabile din . La identificarea unui cluster procesul de descompunere încearcă să găsească posibilele subclustere prin analizarea elementelor clusterului și a restricțiilor GD corespunzătoare.

După identificarea unui cluster se va trece la identificarea obiectelor sale și a restricțiilor GD aferente prin funcția Dep. Procesul de descompunere partiționează un cluster într-o serie de sublustere, încheindu-se atunci când nu mai este posibilă nici o partiționare a clusterului. Folosind algoritmul 3 vom construi apoi structuri arborescente ale clusterelor descompuse (procedura BuildTree). Arborii reflectă restricțiile GD ale clusterelor (muchiile unu arbore sunt restricții GD). În final se folosește algoritmul 4 pentru unirea acestor arbori, rezultând structura complexă a obiectului final.

În prezentarea algoritmilor s-au mai folosit unele notații referitoare la clustere: dacă E este un obiect iar T orice submulțime a componentelor sale, vom nota prin:

▪ -submulțimea lui ce implică doar elemente din T. Aceasta se definește ca =. Intersecția cu T se folosește ca bază la unirea arborelui generat pentru T cu arborele ce include pe X.

▪ Keys(T) include toate cheile lui . Formal, avem Keys(T)=, unde LHS este o funcție aplicabilă unei mulțimi de restricții GD ce returnează partea stângă a restricțiilor GD.

▪ Subtree(X, ) este o funcție ce returnează mulțimea tuturor elementelor dependente total/parțial de X referitor la mulțimea de restricții GD , unde X este o cheie pentru T. Evident, această funcție returnează toate elementele din subclusterul lui T ce sunt identificate prin cheia X. Formal, mulțimea Subtree(X,) se definește ca . Definirea recursivă evită preluarea unui element dintr-un cluster dependent de un atribut non-cheie (preluarea unui element Y dependent de Z cu ).

Dat un cluster T, el poate fi descompus în subclustere dacă și numai dacă mulțimea returnată de Keys(T) nu este vidă. Presupunând Keys(T)=, subclusterele corespondente sunt obținute prin funcția Subtree: , …, .

Algoritmul 2 (ALGORITM DE DESCOMPUNERE)

Procedure Decompose()

Inițializare. Se definesc variabilele:

T:= ; //mulțimea de obiecte inițiale

:=; restricții GD ce implică elemente din T

INPUT: O schemă orientată obiect cu mulțimea obiectelor complementată de interpretarea utilizator

OUTPUT: O mulțime T de clustere ce nu mai pot fi descompuse

Begin

repeat

for each do begin

calculează ; //restricțiile GD pentru clusterul

calculează Keys(); //cheile clusterului

scoate din Keys() cheia lui și clusterele predecesoare lui ;

șterge cheile non-maximale din keys();

if Keys() then begin

șterge din T;

repeat

for each XKeys() do begin

calculează Subtree(X, );

adaugă Subtree(X, ) la T;

șterge X din Keys(); end; //endfor

end; //endif

end; //endfor

until „nici un element din T nu mai poate fi descompus”;

end.

Să considerăm un exemplu: presupunem T=ABCDE și ={A→B, B→C, BC→D, C→E}. Nu avem nici o restricție GD redundantă în . În primul pas al algoritmului este T (ABCDE). Cheile lui se definesc prin prelucrarea grupurilor maximale din partea stângă a lui , deci BC și A sunt chei (B și C sunt incluse în BC la folosirea restricțiilor GD B→C și C→E). Rezultă că există două subclustere ale lui T, definind două grupări de elemente. Primul cluster implică elementele dependente de A (B). Al doilea conține acele obiecte dependente de B și/sau C (pot fi dependente și de A, chiar dacă A nu aparține acestei chei), deci obiectele BCDE. După algoritmul 2, T este {AB, BCDE}. Mulțimea de restricții GD pentru AB și BCDE este {A→B}, respectiv {BC→D, B→C, C→E}.Următorul pas analizează fiecare cluster astfel produs, pentru a vedea dacă mai poate fi descompus. Clusterul AB nu mai poate fi descompus, deoarece nu există nici o cheie (identificator de subclustere) în afara lui A, cheia clusterului AB. Clusterul BCDE poate fi însă descompus, deoarece Keys(BCDE)={B, C} (BC este deja folosit). Rezultă două noi subclustere pentru BCDE. Unul este identificat prin B și conține BC cu restricția GD B→C iar celălalt este identificat prin C, conținând CDF cu restricțiile GD BC→D și D→E. Rezultă că obiectul inițial are doar 3 clustere: AB, BC, CDF.

După generarea clusterelor unui obiect () vom construi structura arborelui astfel:

▪ primul pas reconstruiește stuctura arborescentă pentru fiecare cluster, prin analiza restricțiilor sale GD: () calculate de algoritmul 2. O muchie a unui arbore este o restricție GD pentru clusterul corespunzător. De exemplu, dacă ABC este cluster cu o restricție GD AB→C, atunci va exista muchie între AB și C. Mai mult, dacă există o dependență B→A se construiește muchie între A și B. Algoritmul 3 construiește asemenea arbori.

▪ După crearea arborilor pentru fiecare cluster, algoritmul 4 îi unește în conformitate cu nodurile și muchiile lor comune.

Algoritm 3 (CONSTRUIREA ARBORILOR PENTRU CLUSTERE CE NU MAI POT FI DESCOMPUSE)

Procedure BuildTree()

INPUT: Clusterul T cu obiectele și mulțimea de restricții =S conținând restricțiile

OUTPUT: Un arbore reprezentând clusterul T (mulțimea de muchii dintre )

INIȚIALIZARE: (pentru grupurile de restricții GD)

For i:=1 to m do

; /*conține toate restricțiile GD care au aceeași parte stângă ca și */

Begin

/*Pas1: Ordonarea restricțiilor GD în grupuri prin așezarea celor cu aceaași parte stângă în același grup */

for each GD din S, GD de forma X→Y do

/* toate restricțiile GD din vor avea pe X în partea stângă */

găsește grupul adecvat pentru GD () care conține numai restricțiile GD cu X în partea stângă;

adaugă pe GD la ;

endfor;

// Pas2: Ordonează grupurile după cum urmează:

If , unde și then i<j;

Presupunem că ordonarea finală este (grupurile duplicat sunt șterse)

// Pas3: Construirea arborelui

for i:=1 to m do

for each restricție GD D din do

creează nod intern ca LHS(D);

creează nod extern ca DEP(LHS(D), );

creează legătură între nodurile interne și externe;

end.

Ca exemplu, să presupunem clusterul T=ABCDEFG cu ={A→B, AB→C, B→D, A→E, A→F, A→G}. Clusterul nu mai poate fi descompus deoarece Keys(T)={AB}. Toate restricțiile GD ale lui T își au părțile drepte în T. În conformitate cu algoritmul de mai sus, pentru a crea arborele lui T trebuie să avem o partiție a lui . Aceasta se definește după cum urmează: , și . Identificarea muchiilor între elementele lui T va începe cu mulțimile și . Acestea vor construi muchiile A-B, A-E, A-F, A-G și B-C. Mulțimea va crea o muchie între AB și C (A-B-C).

După identificarea clusterelor și construirea arborilor corespunzători, ultimul pas interconectează arborii, respectând incluziunea dintre chei. Algoritmul 4 unește arborii, rezultând un nou arbore din subarbori nondisjoint, prin gruparea nodurilor comune și adăugând apoi nodurile rămase din subarbori în arborele final.

Algoritm 4 (ALGORITM DE FUZIUNE)

Procedura Merge()

INPUT: Mulțimea de arbori ;

OUTPUT: Arborele unit Tree;

INIȚIALIZARE: Tree:=; Set:={ };

Begin

repeat

For each in Set do

If ∩Tree≠ then

Tree:=MergeTree(, Tree);

// MergeTree unește doi arbori

șterge din Set;

until Set=.

Pentru studierea complexității ultimilor trei algoritmi vom presupune s numărul maxim de atribute ale unui obiect și r numărul de restricții GD pentru o schemă. Algoritmul 2 calculează toate clusterele ce nu mai pot fi descompuse în cel mult s pași deoarece un obiect poate avea cel mult s arbori (fiecare arbore conține câte un atribut), deci complexitatea procedurii Decompose este O(s). În algoritmul 3, crearea arborelui unui cluster este O(s*r), deoarece pot fi cel mult s obiecte (noduri) și r muchii ce descriu restricțiile GD. Algoritmul 4 unește arborii în cel mult s pași deoarece fiecare obiect are cel mult s arbori. Din complexitățile celor trei algoritmi reiese complexitatea algoritmului de descompunere și fuziune ca fiind O(s*r). Complexitatea polinomială a acestui algoritm poate fi de asemenea folosită ca bază în detectarea conflictelor dintre restricțiile GD utilizator (mai eficient decât algoritmul 1 pentru un grad de nesting al obiectelor ridicat).

Exemplu: Să considerăm obiectul O=ABCDEFG, cu ={A→B, AB→C, B→D, BC→E, C→F, C→G, D→H}. Prin aplicarea algoritmului 2 vom avea clusterele

=AB, cu ={A→B} muchia A-B;

=BCD, cu ={AB→C, B→D} muchiile A-B-C, B-D;

=BDE, cu ={B→D, BC→E} muchiile B-D, B-C-E;

=CEFG, cu ={BC→E, C→E, C→F} muchiile B-C-E, C-E, C-F;

=DH, cu ={D→H} muchia D-H.

Algoritmul 3 produce următorii subarbori:

Prin aplicarea algoritmului 4 vom avea următoarea structură finală:

3.4 Corectitudinea algoritmilor de descompunere și fuziune

Scopul acestui paragraf este demonstrarea corectitudinii algoritmilor de descompunere și fuziune, în sensul că aceștia construiesc efectiv forme normale obiect. Corectitudinea primului algoritm este evidentă, deorece el se bazează pe cele două reguli derivate din Teorema 3. Restul acestei secțiuni prezintă corectitudinea algoritmilor 2, 3 și 4 prin demonstrarea faptului că interpretarea utilizator este derivabilă din modelul obiectului normalizat construit. Considerăm un obiect O cu o mulțime de restricții GD . Presupunem că folosind cei trei algoritmi pe obiectul O s-a generat obiectul . Aplicarea algoritmului 2 pe obiectul O va identifica un set de clustere ce nu mai pot fi descompuse: , iar pentru simplificarea demonstrației vom presupune k=3. Aceste clustere conțin următoarele:

– are un set de obiecte determinate de funcția Subtree(). Presupunem că elementele acestui cluster sunt (Subtree(,)=()) și că are o mulțime de restricții GD derivate din ce implică doar elementele din . Din definiția funcției Subtree, mulțimea va conține doar acele restricții GD ale căror parte dreaptă implică numai elemente din , iar partea stângă conține intersecții nevide cu ;

– și vor avea câte un set de obiecte, completate de restricțiile GD legate de respectivele obiecte (pot fi descrise ca mai sus).

Din modul de construire a clusterelor, fiecare din ele conține câte o cheie maximală. Fiecare obiect din cluster se află în una din situațiile următoare:

Este dependent de cheia maximală (sau este parte din cheia maximală)

Are o intersecție nevidă cu cheia maximală și este de asemenea dependent de elementele clusterului părinte.

Altfel spus, dacă presupunem că este cheia pentru , atunci va exista o partiționare a obiectelor acestui cluster după cum urmează:

(1) (k≤n)- partiție în care fiecare element este dependent doar de (total sau parițial) folosind restricțiile GD din

(2) – partiție conținând restul elementelor; fiecare element este dependent nu doar de elementele cheii, dar și de elemente ce nu aparțin de , dar aparțin clusterului predecesor.

Să considerăm o restricție GD, notată D; vom demonstra că ea este derivabilă din modelul lui O. D poate fi în mai multe clustere; să presupunem că D implică elemente din . În aceste caz D aparține uneia din cele două partiții de obiecte din . În prima partiție D va avea forma , sau , unde 3≤t≤k. Aplicarea algoritmului 3 pe dependența D duce la un arbore ce exprimă calea dintre și . În funcție de dependența dintre și , vom avea drumul – ( dependent de ) sau – ( dependent de ). Obiectul normalizat final va conține calea adecvată ce ne va permite să derivăm restricția GD D. Evident, restricția utilizator D este derivabilă din modelul obiectului . Considerăm a doua partiție de elemente din și demonstrăm în mod analog primei partiții că D este derivabilă din modelul obiectului . Din definiția partiției, D va depinde nu doar de elemente din , dar și de elemente ce nu aparțin lui , pe care le vom nota . D va avea forma →, →, sau →, unde k+1≤t≤n. Să analizăm cele trei tipuri de restricții GD:

(a) → nu este validă în , altfel ea ar genera o cheie în cluster, ce ar conține obiectul . Atfel spus, nu ar fi maximală, deci nu ar fi cheie (contrazice presupunerea că este cheie pentru );

(b) → (sau →) poate fi validă în ca element al lui . În acest caz, vor aparține unui cluster predecesor lui ( a fost identificat din acest cluster predecesor). În ipoteza noastră nu are cluster nu are predecesor, dar în cazul în care acest lucru s-ar întâmpla, ar fi dependent de în contextul acestui cluster predecesor. Aceasta înseamnă că va fi legat de printr-o cale după algoritmul 3. În același mod, și vor forma o cale. Folosind algoritmul 4, cele două drumuri generate de algoritmul 3 vor fi unite, deoarece au un nod comun . În consecință, obiectele , și vor forma o cale în obiectul normalizat final . Evident, dependența D (→) este derivabilă din modelul obiectului normalizat.

Până acum am văzut că în poate exista un singur tip de restricții GD și anume cele de tip (b). Mai observăm că restricțiile GD utilizator sunt exprimate de obiectul normalizat final. Pentru completitudine, orice restricție GD utilizator trebuie să fi fost folosită în cel puțin un cluster identificat de algoritmul 3, creând o cale în obiectul normalizat, după cum s-a arătat mai sus.

Concluzii

Am prezentat o teorie de normalizare pentru modele de baze de date orientate obiect ce implică restricții de tip dependență, forme normale și reguli de normalizare. Restricțiile de dependență pentru o schemă orientată obiect au două nivele de granularitate: nivel schemă și nivel obiect. La nivel schemă restricțiile exprimă relații inter-obiect prin drumuri orizontale, pe când la nivel obiect restricțiile specifică relații intra-obiect legate de căile verticale. Folosind aceste restricții am definit formele normale obiect pe baza unui pattern-matching între interpretarea dată de utilizator universului pus în discuție și interpretările reflectate de obiectele schemei. Utilizând algoritmii potriviți, obiectul poate fi restructurat pentru a fi consistent cu interpretarea utilizator sau poate fi construit direct din interpretarea utlizator.

Modelele de baze de date prezentate iau în considerare caracteristicile unice ale paradigmei obiect. Cele trei tipuri de restricții contribuie la creșterea semanticilor modelelor de baze de date orientate obiect. Formele normale oferă o bună metodă de măsurare a corectitudinii specificărilor cu privire la restricțiile date.

Această teorie diferă de modelele tradiționale (cum ar fi modelul relațional plat sau modelele relaționale nested) prin două aspecte. În primul rând se urmărește modul utilizatorului de a înțelege universul discutat în defavoarea problemelor de implementare a bazelor de date; aplicată unui obiect această abordare produce un obiect normalizat ce reflectă interpretarea utilizator, permițând coexistența mai multor interpretări într-un obiect. În plus, această abordare folosește modele de baze de date mai bogate, ce implică obiecte complexe, moștenire și identitatea obictului, oferind deci o arie de restricții ce acoperă multiple tipuri de relații inexistente în modelele convenționale (modelare mai eficientă).

Lucrarea pune la dispoziție designerului de baze de date concepte și metode de evaluare a calității unei scheme orientată obiect în conformitate cu restricțiile GD utilizator (facilități de verificare a gradului de echivalență între o schemă existentă și restricțiile utilizator sau de construire a unei scheme noi direct din restricțiile specificate). Designerul poate folosi una din cele două tehnici propuse, în funcție de cerințe. Prima tehnică (restructurarea obiectului) implică iterații, dând designerului mai mult control și permițându-i să evalueze fiecare rafinare succesivă a schemei. A doua tehnică este mai adecvată în cazul schemelor orientate obiect mari, fiind mai eficientă în producerea obiectelor normalizate.

Bibliografie

1. ATKINSON, M., BANCILHON, F., ZDONIK, S., DeWITT, D., DITRICH, D. 1989: The object-oriented database system manifesto;

2. BEERI, C., BERNSTEIN, P. 1979: Computational problems regarding the design of normal forms;

3. CODD, E. 1970: A relational model for large shared databases;

4. CODD, E. 1974: Recent investigations into relational database systems;

5. COLBY, L. 1989: A recursive algebra and query for nested relations;

6. ROTH, M. A., KORTH, H. F., SILBERSCHATZ, A. 1988: Extended algebra and calculus for 1NF relational databases;

7. LING, T. W., YAN, L. L. 1994: NF-NR: A practical normal form for nested relations;

8. MARKOWITZ, M., SHOSHANI, V.M. 1989: On the correctness of representing extended entity-relationship structures in the relational model;

9. ROTH, M., KORTH, H. 1987: The design of 1NF relational databases into nested normal form;

10. RUMBAUGH, J., BLAHA, M., PREMERLANI, W., EDDY, F., LORENSEN, W. 1991: Object-Oriented Modeling and Design;

11. TARI, Z., STOKES, J., SPACCAPIETRA, S. 1997: Object normal forms and dependency constraints for object-oriented schemata.