Pagina documente » Informatica, Matematica » Forme normale in baze de date orientate obiect

Despre lucrare

lucrare-licenta-forme-normale-in-baze-de-date-orientate-obiect
Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.
lucrare-licenta-forme-normale-in-baze-de-date-orientate-obiect


Cuprins

Cuprins
Introducere..............2
Cap. 1. Notiuni de baza............6
1.1. Modelul bazelor de date.
Algebra de proiectie........7
1.1.1. Cai (drumuri).......10
1.1.2. Proiectii12
1.2. Restrictii de tip dependenta.........14
1.2.1. Restrictii de tip dependenta de cale......15
1.2.2. Restrictii de tip dependenta locala........16
1.2.3. Restrictii de tip dependenta globala......17
1.2.4. Restrictii de cheie.18
1.3. Axiome de inferenta......19
Cap. 2. Normalizarea obiectelor..............23
2.1. Exemplu........23
2.2. Modelul unui obiect..28
2.3. Forme normale obiect33
2.4. Reguli de normalizare..............36
2.5. Completitudine........41
Cap. 3. Algoritmi pentru derivarea formelor normale obiect.....43
3.1. Generarea formelor normale prin
restructurare..............44
3.2. Generarea formelor normale prin
reconstructie45
3.3. Algoritmi de descompunere si fuziune..........46
3.4. Completitudinea algoritmilor de descompunere si fuziune56
Concluzii60
Bibliografie............62
2

EXTRAS DIN DOCUMENT

?{p}

{p}

?Introducere

Modelele de baze de date orientate obiect ofera constructii bogate pentru realizarea unor obiecte complexe si posibilitatea refolosirii prin mostenire. Lucrarea noastra prezinta problema modelarii schemelor bazelor de date orientate obiect.

Problema modelarii unei scheme relationale se refera la imbunatatirea unei scheme initiale cu una echivalenta, mai buna. Notiunea de echivalenta include proprietatile de join fara pierdere (asigura identitatea datelor in schema initiala/finala) si pastrarea dependentei (asigura identitatea dependentelor in cele doua scheme). Conceptul de mai bun se refera la o schema cu o redundanta mai mica si cu mai putine probleme la actualizare. Scopul rezolvarii problemei redundantei este de a minimiza spatiul de stocare necesar unei baze de date prin limitarea duplicarii infomatiei din relatii.

Redundanta si anomaliile legate de actualizare au fost rezolvate intr-o anumita masura 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 in 1974 cea de a treia forma sa fie prelucrata, rezultand forma mai puternica Boyce-Codd. Aceste forme normale se bazeaza pe corelarea dintre atributele unei relatii si cheia sa primara, folosind dependentele functionale. Formele 4NF, 5NF propuse mai tarziu se bazeaza pe conceptele de dependente multivaluate, respectiv dependente join.

Proprietatea de join fara pierdere si cea de pastrare a dependentei au fost studiate in diferite moduri, conducand la doua abordari ale schemelor de baze de date. Abordarea pura subliniaza strict proprietatile de join fara pierdere si pastrarea dependentei, pe cand abordarea top-down accentueaza mai ales redundanta si problemele de anomalii la actualizare.

Abordarea pura pentru modelarea schemelor se bazeaza pe asa numita relatie universala, unde toate relatiile vor fi definite prin proiectii ale acestei relatii universale, iar toate regulile privind universul in discutie vor fi specificate relativ la aceasta relatie prin dependente functionale si/sau multivaluate (Beeri et al. 1978).

Abordarea top-down preia un set de relatii date in forma normala si foloseste metode adecvate de descompunere pentru a genera relatii mai eficiente. Procesul de normalizare poate fi privit ca un proces de „rupere” a atributelor unei relatii in relatii mai mici cu scopul de a limita problemele de redundanta sau de anomalii la actualizare.

Extensii ale modelului relational „plat” care, dupa cum am aratat, a fost intens studiat, au dus la modelele de baze de date Non-First Normal Form (). A fost propusa o noua forma normala, Nested Normal Form (NNF) pentru relatii nested, relatii ce limiteaza problemele de redundanta sau anomalii la actualizare. NNF se bazeaza pe conceptul de arbore pentru o schema normala care e o relatie (nested) fara redundante (Özsoyoglu&Yuan, 1987). Caracteristica relatiei nested in NNF este aceea ca nodurile arborelui corespondent induc restrictii de tip dependenta multivaluate. Din punctul de vedere al proprietatilor de join fara pierdere si pastrarea dependentei, acest model poate fi vazut ca o extindere a abordarii pure la scheme continand structuri complexe. Lucrari in acelasi sens au fost propuse de Roth&Korth (1987) sau Ling si Yan (1994).

În anii ’80 design-ul bazelor de date s-a ridicat de la nivelul logic la unul conceptual, in care sunt des folosite modele de baze de date semantice (Hull si King 1987). Aceste modele conceptuale (Hammer si McLeod 1981; Elmasri et al. 1985) integreaza abilitati structurale mai bogate decat in modelul relational plat, permitand mostenirea, atribute multivaluate si atribute complexe (compuse din alte atribute). În contextul modelarii conceptuale, formele normale reflecta o schema relationala normalizata atunci cand sunt traduse intr-un model relational plat.

Paradigma orientata obiect (Atkinson et al. 1989) ofera o solutie in tratarea complexitatii in modelarea universului in discutie. Modelele de baze de date orientate obiect suporta mecanisme complexe ce permit refolosirea datelor si a proceselor prin mostenire, construirea unor obiecte complexe (folosind constructorii ortogonali tuplu si set), identificarea obiectelor independent de valoarea lor (folosind mecanismul de identitate a obiectelor); toate aceste avantaje nu sunt suportate de modelele de scheme traditionale prezentate anterior.

Lucrarea de fata urmareste teoria de normalizare a bazelor de date orientate obiect propusa de Z. Tari et al. in 1997 si are urmatoarea structura:

? Capitolul 1. Utilizam modele conceptuale mai bogate (orientate obiect) ce incorporeaza notiunile de identitate a obiectului, obiect complex, mostenire. O extensie a restrictiilor de tip dependenta functionale si multivaluate va lua in considerare complexitatea schemei: dependente de cale, dependente locale si dependente globale. Ele exprima legaturile obiectului in functie de diferitele tipuri de drumuri existente. La nivel schema, restrictiile de dependenta sunt multitip (dependente de cale) si exprima legaturile inter-obiect. La nivel obiect, restrictiile de dependenta exprima legaturile intra-obiect, si anume legaturile dintre obiect si componentele sale (dependente locale si globale). În finalul capitolului vom prezenta axiome de inferenta pentru diferitele tipuri de restrictii de dependenta.

? Capitolul 2. Normalizarea se bazeaza pe un proces ce compara interpretarea data de utilizator universului discutat cu interpretarile reflectate de obiecte in schema. O interpretare este de fapt o multime de restrictii de dependenta ce furnizeaza o anumita „intelegere” a semanticilor aplicatiei date; vom face distinctie intre interpretarea utilizator (implica un set de restrictii de dependenta specificate de utilizator) si interpretarea obiect (multime de restrictii de tip dependenta reflectate de structurile complexe ale obiectelor din schema). Spre deosebire de design-ul bazelor de date traditional in care o relatie are o interpretare unica, un obiect poate avea mai multe interpretari obiect (reflectand posibilele interpretari multiple ale drumurilor sale). Multimea tuturor interpretarilor unui obiect se numeste modelul obiectului, iar un obiect se afla in forma normala daca interpretarea utilizator este exprimata (tehnic, derivabila 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, transforma o schema data in una normalizata, folosind regulile pentru normalizarea obiectului date in capitolul 2. Al doilea algoritm, cu cateva elemente de abordare pura, construieste o schema normalizata din „nimic”, folosind dependentele utilizator. Algoritmul necesar intr-o situatie data depinde de complexitatea structurii obiectului.

Capitolul 1

Notiuni de baza

Capitolul descrie un model de baze de date orientate obiect ce va fi utilizat la dezvoltarea teoriei de normalizare. Modelul suporta cele mai multe concepte ale paradigmei obiect, inclusiv obiecte complexe, identitatea obiectului, mostenire si clasa. Unele concepte, ca suprascrierea sau incapsularea nu sunt aplicabile in aceasta abordare, deoarece ele se refera la comportamentul schemelor orientate obiect, pe cand teoria noastra de normalizare se refera la aspectele structurale.

Pe langa descrierea modelului de baze de date orientate obiect vom include si definitii clare pentru restrictiile de tip dependenta, acestea specificand semanticile obiectelor si legaturile lor. Restrictiile de tip dependenta sunt extensii la arhicunoscutele dependente functionale si multivaluate si descriu diferite legaturi ale obiectelor, inclusiv legaturi intra-obiect sau inter-obiect.

Restrictiile de tip dependenta pentru scheme orientate obiect sunt definite prin proiectarea operatiilor. În acest scop vom dezvolta o algebra de proiectie pentru modelele orientate obiect ce suporta accesul la diferite obiecte folosind o operatie de proiectie simpla (permite accesul la componentele directe ale unui obiect), o operatie de proiectie complexa (permite accesul la toate obiectele date printr-un drum) si o operatie de proiectie conditionata ce va permite accesul la obiectele selectate intr-o instanta a unei cai date.

1.1 Modelul bazelor de date. Algebra de proiectie

Un obiect in contextul bazelor de date este o colectie de atribute ce reprezinta cunostintele de structura (atribute enumerate) si comportament (atribute procedurale) ale unui domeniu. Un obiect O va fi reprezentat ca O(Do),unde Do este tipul obiectului (instanta unui obiect se construieste prin instantierea tipului obiectului). Atributul va fi privit ca o functie definita pe o multime de obiecte, luand valori pe o multime de obiecte. Vom numi un atribut care returneaza intotdeauna o multime cu un singur element atribut singleton-valued; altfel, vom vorbi despre atribute multivaluate.

Schema prezentata in continuare suporta notiunea de obiect cu proprietatile sale (atribute in obiecte). Legaturile dintre obiecte pot fi unidirectionale (agregarea: de exemplu, intre Proiect si Laborator) sau bidirectionale (asocierea: de exemplu, Persoana-Masina). Mostenirea asigura reutilizarea informatiei intr-o schema orientata obiect.

In exemplele urmatoare ident va desemna domeniul tuturor identificatorilor, iar {nume: tip} reprezinta un atribut multivaluat.

În particular, vom defini obiectul Personal ca: Personal ([IDpers: ident; prenume: string; {nume: string}; salariu: integer; {Conduce: Masina}; {Copil: Persoana}; {Laborator: lab}]), unde obiectul lab este definit ca lab([IDlab:integer; numeLab:string; {Proiect: Proj}; {adresa:string}]). În acest exemplu atributul Conduce modeleaza partial semantica asocierii dintre Persoana si Masina, aceasta fiind completata de atributul Proprietar al obiectului Masina.

(Fig.1: diagrama unui exemplu de schema orientata obiect)

În acest context, definim o schema orientata obiect ca pe o structura , unde reprezinta multimea de obiecte a schemei, iar este multimea restrictiilor de dependenta peste obiectele din . Structura defineste o baza de date orientata obiect, unde prin am notat multimea instantelor elementelor din .

Tabela1: Exemplu de instanta pentru schema din figura1

Persoana

IDpersoana

prenume

{nume}

{Conduce}

{ Copil}

P1

Ionescu

Mihai

M1, M2