NORMALIZAREA BAZELOR DE DATE ORIENTATE-OBIECT

I.Structura lucrarii

II.Modelul orientat-obiect

II.1.Descriere

II.2.Algebra de proiectie

II.3.Path-uri

II.4.Proiectii

III.Restrictii de integritate

III.1.P-dependente

III.2.L-dependente

III.3.G-dependente

III.4.Constrangeri cheie

IV.Axiome de inferenta

V.Normalizarea obiectelor

V.1.Forme normale ale unui obiect

V.2.Reguli de normalizare

VI.Algoritmi de normalizare

VI.1.Generarea de forme normale prin restructurare.Algoritmul de

transformare.

VI.2.Generare de forme normale prin reconstructie.Algoritmul de

descompunere si fuziune

VII.Concluzii

I. Structura lucrarii

Paradigma orientarii-obiect este o solutie in modelarea universului pentru ca modelul de date orientat-obiect suporta mecanisme complexe, care permit reutilizarea datelor, construirea obiectelor complexe prin mostenire (folosind tuplurile si multimea de constructori ortogonali) si identificarea obiectelor independent de valoarea lor (prin mecanismul de identitatea obiectului). Modelele traditionale au urmatoarele dezavantaje:

1).Modelele nu sunt suficient de puternice pentru a face fata mecanismelor complexe de

modelare, precum identificatorul obiectului, obiecte complexe si mostenire .

2).Restricttiile de integritate (F-dependente, MV-dependente) sunt date de o multime

restransa de constrangeri, care pot fi impuse unor atribute dintr-o relatie. Modelul

obiectual include restrictii mult mai complexe, vizand nu numai legaturile dintre

obiecte si componentele lor, ci si restrictiile dintre obiectele insele (legaturi inter-

obiectuale). in modelele relationale, restrictiile de integritate reflectau

dependentele dintre datele unei relatii. in modelul obiectual, dependentele includ

conceptul de identitate a unui obiect prin legaturile dintre obiecte exprimate nu prin

valoarea lor, ci prin identitatea lor.

3). Nu este potrivita considerarea redundantelor si a problemelor de actualizare la

inceputul proiectarii schemei orientate-obiect, deoarece acestea tin de implementare.

Modelarea obiectuala ar trebui sa se bazeze pe ipoteza ca detaliile de implementare

nu sunt scopul activitatilor de modelare. Normalizarea obiectelor vizeaza descrierea

schemei care refecta interpretarea universului a utilizatorului (o schema corecta). in

modelul obiectual, un obiect va reflecta mai multe interpretari, datorita multiplelor

interpretari ale cailor sale (path-urilor), iar obiectul va fi intr-o forma corecta daca

interpretarea utilizatorului este exprimata de interpretarile obiectului. Din acest punct

de vedere, normalizarea orientata- obiect produce scheme corecte prin prisma

utilizatorului.

Lucrarea de fata propune descrierea unei teorii de normalizare orientata-obiect, care sa rezolve problemele mentionate mai sus si este organizata astfel:

II. Descrierea modelului orientat-obiect si a algebrei de proiectie pentru definire P-dependentelor, L-dependentelor, G-dependentelor si a tipurilor de proiectii.

III. Descrierea tipurilor de dependente folosind operatorii algebrei de proiectie.

IV. Axiomele de inferenta pentru tipurile de dependente.

V. Normalizarea obiectelor pornind de la descrierea formelor normale ale unui obiect, prezentarea regulilor de normalizare.

VI. Descrierea algoritmilor de generare a formelor normale ale unui obiect: algoritmul de transformare si algoritmul de descompunere si fuziune.

VII. Utilizarea de date obiectuale mai bogate decat modelele de date conceptuale care incorporeaza conceptele de identitatea unui obiect, obiecte complexe, mostenire .

II.Modelul orientat-obiect

Modelul orientat-obiect, utilizat in dezvoltarea teoriei de normalizare, suporta majoritatea conceptelor orientarii-obiect: obiecte complexe, identitatea unui obiect, mostenire, clase/ tipuri.

Restrictiile de integritate specifica semantica obiectelor si a legaturilor lor, devenind o exensie a dependentelor functionale si multivoce, care lucreaza cu legaturi variate, incluzand legaturile intra si inter obiectuale.

Algebra de proiectie se afla la baza definirii restrictiilor de integritate si suporta accesul la diferite obiecte legate prin proiectie simpla (permite accesul la componentele directe ale unui obiect), proiectie complexa (permite accesul la toate obiectele legate printr-un drum), proiectie conditionata (permite accesul la obiectele selectate de o instanta a unui drum dat).

II.1 Descriere

Modelul orientat-obiect descris aici suporta notiunea de obiect care inglobeaza proprietatile comune unei multimi de instante cu aceleasi caracteristici precum si universul. Aceste caracteristici sunt reprezentate ca atribute in obiecte. Relatiile reprezinta legaturi intre obiecte si pot fi unidirectionale (precum agregarea) sau bidirectionale (precum asocierea).

Mostenire a este un tip de legatura care asigura reutilizarea informatiilor unui obiect intr-o schema orientata-obiect.

Fiecare obiect are o multime de atribute. Un atribut poate fi simplu sau complex. Un atribut simplu are un domeniu simplu (de exemplu char, integer), pe cand un atribut complex este un atribut format din constructori tuplu si/sau multime de atribute existente (domenii).

Obiectele sunt legate prin legaturi de tipul: agregare, asociere si mostenire.

Mostenirea dintre doua obiecte semnifica faptul ca orice instanta a unui obiect (numit sub-obiect) este instanta a celuilalt obiect (numit super-obiect).

Agregarea dintre doua obiecte desemneaza faptul ca unul dintre obiecte refera celalat obiect (ca atribut).

Asocierea poate fi privita ca un acces in ambele sensuri de la obiectul vizat.

Conceptul principal in modelul obiectual este acela de obiect. Un obiect denota un element al schemei, facand abstractie ca este o entitate sau un atribut. Un obiect O este reprezentat ca O(D₀), unde D₀ este tipul obiectului. Instantele obiectelor sunt construite instantiind tipul obiectelor. Fiecare instanta a unui obiect are un identificator de obiect si atributele au identificatori, derivati conform constrangerilor specificate in obiectul corespunzator.

O schema orientata-obiect este definita ca o multime de obiecte complementata de restrictiile de integritate. Formal, schema este reprezentata astfel: < >, unde este o multime a obiectelor de schema si este multimea restrictiilor peste . Populand o schema orientata-obiect cu instante ale obiectului, se defineste o baza de date orientata-obiect, exprimata formal prin < < >, >, unde reprezinta instanta a lui

II.2.Algebra de proiectie

Restrictiile de integritate sunt extensii ale dependentelor functionale si multivoce, care lucreaza cu conceptele orientarii-obiect: obiecte complexe, identitatea unui obiect, mostenire a. Restrictiile de integritate se refera la dependentele semantice dintre diferite tipuri de obiecte legate prin diverse tipuri de legaturi. Pentru dezvoltarea acestora este necesara o algebra de proiectie ca sa se navigheze printre obiecte, utilizand legaturile. Algebrele au fost dezvoltate si in contextul modelelor relationale, dar aceasta lucreaza cu proiectiile atributelor si nu incorporeaza operatii algebrice pentru manevrarea, manipularea obiectelor de pe o cale (path) sau o instanta a unui drum. Caile includ nu numai atribute, dar si alte obiecte.

II.3. Path-uri (Cai)

#n mod obisnuit, o cale este o secventa ordonata de obiecte dintr-o schema, astfel incat fiecare obiect din secventa este legat de predecesorul si de succesorul sau fie printr-un atribut, fie printr-o legatura.

Formal, calea de la obiectul O₁ la un obiect O_n (n>2) prin obiectele O₂, ,O_n-1 este notat :

O₁-O₂- -O_n.

Tipuri de cai:

drum vertical: Este o secventa care genereaza dintr-un obiect una din componentele sale.

drum orizontal: Este o secventa in care alterneaza numai obiecte. Aceasta include agregarea inversa. De obicei, o relatie de agregare este unidirectionala (intr-un singur sens). Permitand relatia de agregare inversa, o schema este conservata semantic.

drum compus : Este o secventa care foloseste o combinatie de drumuri verticale si orizontale.

O instanta a unei cai O₁-O₂- -O_n este o secventa de forma _n, unde _i simbolizeaza o instanta a obiectului O_i , iЄ

II Proiectii

Algebra de proiectie ne da operatorii algebrici care permit accesul diferit la obiecte. Accesul poate fi generic (prin cai) sau restrictiv (prin instantele cailor). Prin cel generic este accesat intreaga multime de instante conectate la un obiect dat folosind o cale obisnuita, pe cand cel restrictiv imbunatateste accesul generic prin gasirea anumitor instante.

Fie instanta unui obiect, , si un drum sau o instanta a unui drum. Notam:

τa0s : proiectia lui in obiectul O.

τ_ρa0s : proiectia lui in O conform lui

Tipuri de proiectie:

• Proiectie simpla

O proiectie simpla realizeaza la un nivel doar un drum vertical sau orizontal.

Formal, proiectia simpla a instantei τ=aτ₁, τ₂,.,τ_j,.τ_ns a obiectului O(aO₁,.O_j,.O_ns) la una din componentele sale O_j este definita ca : τaO_js=.

Proiectia simpla a unei instante poate implica regasirea altor instante care o contin.

• Proiectia complexa

O proiectie complexa implica drumuri de nivele multiple. Formal, proiectia complexa a unei instante , ale unui obiect O intr-un alt obiect O_q, conform cu un drum compus O-O₁- -O_q-1, este definita prin proiectii succesive in obiectele O₁, O₂, ,O_q-1.Avem:

τaO_qs=(τaO_q-1s)aO_qs=(.(.((τaO₁s)aO₂s).)aO_q-1s)aO_qs.

• Proiectia simpla conditionata.

O proiectie simpla conditionata este o proiectie simpla in care obiectul-tinta este conditionat de o instanta data.

Formal, proiectia simpla conditionata a unei instante a unui obiect O in componenta directa O_i, conform instantei unui drum a drumului O-O_i este :

IF

THEN

ELSE

IF O_i este obiect univoc

THEN

ELSE

• Proiectie complexa conditionata

O proiectie complexa conditionata implica drumuri instantiate la nivele multiple, unde este cel putin o conditie atasata obiectului de-a lungul drumului selectat.

Formal, proiectia complexa conditionata a unei instante a unui obiect O_p , conform unei instante a drumului _{p-1 p} a unui drum compus O₁-O₂- -O_p-1-O_p este :

τ_{τ1-τ2-.-τp-1-τp}aO_ps=(((τ_τ1-τ2aO_ps).)_{τp-2 -τp-1}aO_p-1s)_τp-1-τpaO_ps

Operatorii acestei proiectii asigura tipuri diverse de acces la obiecte, inclusiv generic si restrictiv, folosind drumurile verticale si orizontale.Cum de modelul obiectual este legata notiunea de atribute multivoce, trebuie definit un operator care va aduce la acelasi nivel structurile multiseturilor.Aceasta operatie se numeste flatten si este definita astfel: Flattern-ul unei instante =a _{j n}s a obiectului O(aO₁, O_j, O_ns) intr-o componenta multivoca O_j este : raO_js=U_kt_k , t_k as.

III Restrictii de integritate

Spre deosebire de modelul relational, in care restrictiile de integritate se limitau la legaturi atribut-atribut, modelul obiectual a imbunatatit aceste dependente prin includerea conceptelor de identificatorul unui obiect si cai.

Fie o schema orientata-obiect < >, defineste multimea restrictiilor asupra lui . Aceste dependente iau forme diferite, in functie de tipul drumului dintre obiecte. Restrictiile care se bazeaza pe drumuri orizontale se numesc P-dependente si sunt restrictii multitip, deoarece exprima legaturile dintre obiecte. Dependentele bazate pe drumuri verticale se numesc fie dependente locale (L-dependente), fie dependente globale (G-dependente). L-dependentele sunt limitate la o singura instanta a unui obiect, pe cand cele globale sunt valabile pentru toate instantele acelui obiect.

III.1.P-dependente

P-dependentele reprezinta legaturile semantice dintre obiect multitip si se bazeaza pe notiunea de drumuri orizontale.

Definitie (P-dependente)

Intre doua obiecte X si Y avem P-dependenta, in raport cu un drum , notata X/ àY, daca si numai daca pentru orice instanta a lui , care porneste din X, este obtinut acelasi rezultat pentru obiectul Y.

Folosind algebra de proiectie propusa anterior, o P-dependenta se formalizeaza astfel:

X/ àY V X₀ si V ₁, V a..i. este singurul drum dintre X si Y si:

X₀ este o instanta a lui X

sunt instante ale lui care il contin pe X₀

Atunci:

X_0ρ1ays=X_0ρ2ays

III.2.L-dependente

Definitie (L-dependente)

Un obiect Y este local dependent (L-dependent) de X, notat X|->Y, daca si numai daca alegand orice drum de la X la Y, se obtine acelasi rezultat pentru Y.

Utilizand algebra de proiectie, L-dependentele se formalizeaza astfel:

X|->Y V X₀ si V ρ₁, V ρ₂ si V τ₁, Vτ₂ a.i

-X₀ este instanta a lui X

si sunt drumuri distincte, care leaga X si Y

si sunt instante ale lui , respectiv si contin X₀.

Atunci :

X_0τ1ays=X_0τ2ays

III.3.G-dependente

P-dependentele exprima legaturile inter-obiectuale, pe cand L-dependentele pe cele intra-obiectuale. in schema orientata -obiect, acestea se aplica doar unei singure instante a obiectului.Cand L-dependentele vizeaza toate instantele ale aceluiasi obiect cu acelasi identificator, acestea se numesc G-dependente (dependente globale).

Definitie (G-dependente)

Un obiect Y este G-dependent de X, notat X->Y, daca si numai daca Y este local dependent de X si oricare doua instante ale egale in X sunt egale si in Y.

Cu algebra de proiectie, G-dependentele se definesc astfel:

X->Y X|->Y si V X₀ ,X₁ , V ₁, V si V , V a.i.:

-X₀ aXs, X₁ aXs (X₀=X₁)²;

si sunt drumuri distincte, care leaga X si Y

si sunt instante ale lui , respectiv si contin X₀,X₁.

Atunci :

X₀ ays=X₁ ays

Toate instantele clasei sunt cuprinse in . Proiectia acestei multimi in X, notata aXs, reprezinta toate instantele posibile ale acelui obiect. aXs se numeste instanta globala a lui X si se defineste astfel:

IF X este obiect THEN aXs=C

ELSE

aXs=

Unde path_X(E) reprezinta cel mai drum care leaga E si X.

Formal, functia path() poate fi definita astfel:

Fie un obiect O. Notam path_{O1, On}(O) cel mai mic drum care porneste din O si ncontine toate obiectele O₁, O_n. path_{O1, On}(O) verifica proprietatile:

path_{O1, On}(O) contine O₁, O_n

V _{O1 On O1 On} este un drum care porneste din O si contine toate obiectele O₁, O_n, deci

length(path_{O1, On}(O) )<length( _{O1 On}

Functia length(p) returneaza numarul de obiecte continute de drumul p.

III.4.Constrangeri cheie

Modelul obiectual include notiunea de identificatorul unui obiect.Atributele complexe nu au corespondent in modelul obiectual deoarece acestea nu exista independent de alte informatii, deci se introduce notiunea de identificator pentru atribute complexe. Acest identificator asigura identificarea instantelor atributelor complexe care sunt folosite de un drum pentru a permite navigarea in baza de date. Navigarea ofera posibilitatea verificarii restrictiilor de integritate.

Identificatorul unui atribut complex se bazeaza pe constrangerile de tip cheie.O constrangere de tip cheie peste un atribut complex, de exemplu A, descrie o partitie a componentelor lui A in 3 parti: A₁, A₂, A₃, unde A₁ este cheie, A₂ este total dependent de A₁ si A₃ este dependent de A₁ prin mostenire .

Definitie (Constrangeri cheie)

K este cheie candidata a obiectului O daca si numai daca:

1).K este o multime din componentele lui O

S₁, S₂ a.i.:

a).S₁, S₂ si K formeaza o partitie a lui O

b).V O_i, O_i S₁, K->O_i

c).V O_j , O_j S₂, K_A1, K_Ar, unde K_Ai este cheie pentru A_i si A_i este un stramos al lui O (1<i<r) si KUK_A, .K_Ar->O_j.

3).Nu exista o submultime Ka a lui K a.i. Ka sa verifice 1) si 2).

Dintre cheile candidate ,ce caracterizeaza un atribut complex, una singura este aleasa sa fie identificator.

IV.Axiome de inferenta

Proprietatile axiomelor de inferenta se bazeaza pe doua notiuni complementare:

-satisfacere

-deducere : |-

Fie F o multime de dependente si w o dependenta. Notam:

-satisfacere :F|=w daca w este satisfacuta, atunci F trebuie sa fie satisfacuta;

-deducere :F|-w w rezulta din una din inferente.

P-dependente(PD)

PD1: XCY => V ρ, Y/ρàX

PD2: X/ρ₁à si Xa/ρ₂ => XXa/ρ₁ ρ₂ày

PD3: X/ρàY => XZ/ρày

PD4: X/Z_ρ2àY => XZ/ρ₂àY

PD5: X/ρ₁à, Y/ρ₂àZ => X/ρ₁ ρ₂àZ

PD6: V A, A atribut al lui X => X/ΦàA

PD7: X/ρàY =>/ρà

L-dependente(LD):

LD1 :X|->Y =>V ρ, X/ρàY

LD2 : XCY => Y|->X

LD3 : X/ àY => X|->Y

LD4 : X|->Y si Y|->X => X/YàZ

LD5 : X|->Y =>|->

LD6 : X este un sub-obiect al lui Y => X|->Y

G-dependente(GD)

GD0 : X|->y => X|->Y

GD1 : X/ΦàY =>X|->Y

GD2 : X|->Y =>XXa->Y

GD3 : X|->Y si Y->Z =>X/YàZ

GD4 : X|-> si Y->Z => XY->Z

GD5 : X este un sub-obiect al lui Y => Y->Z

V NORMALIZAREA OBIECTELOR

Modelul obiectual este conceput sa descrie o schema conceptuala corecta, care sa reflecte interpretarea utilizatorului a universului mai mult decat detaliile de implementare. Prin interpretarea utilizatorului se subintelege o multime de restrictii de G-dependente, care sunt specificate de un utilizator ca o intelegere a sa , a semanticii universului. Aceasta interpretare este exprimata ca o multime de G-dependente numite restrictii GD ale utilizatorului. in plus un obiect poate avea multiple interpretari, numite interpretarile obiectului, care rezulta din multiplele interpretari a structurii complexe ale obiectului. Interpretarile multiple deriva din drumurile verticale si compuse si formeaza interpretarea unui obiect. Toate interpretarile obiectului formeaza semantica acelui obiect.

Fie doua tipuri diferite de interpretari(a utilizatorului si a obiectului) descrise intr-o schema orientata obiect, normalizarea unui obiect poate fi privita ca un proces de potrivire, interpretarea utilizatorului comparandu-se cu cea a obiectului. Cand interpretarea utilizatorului este derivabila din interpretarea obiectului(prin axiomele de inferenta) atunci obiectul este in forma normala . Altfel, el este un obiect normalizat. in acest mod, formele normale asigura compatibilitatea intre interpretarile universului de catre utilizator si interpretarile reflectate de structura obiectului. Cand un obiect nu este in forma normala structura complexa a obiectului trebuie modificata sau restructurata pentru a reflecta caile induse de utilizator.

Definitie(Dependente coerente)

O dependenta A->B este coerenta daca A-B este o cale. Altfel, se numeste dependenta incoerenta.

Definitie(Interpretarea obiectuala)

Interpretarea unui obiect este o multime de G-dependente coerente ale obiectului. O interpretare este maximala daca si numai daca nu poate fi derivabila din alta interpretare obiectuala.

Formal, fie un obiect O notam:

-_user, interpretarea utilizatorului a lui O

- , modelul lui O.

Definitie(Model)

Fie toate interpretarile maximale ale unui obiect O, atunci se numeste model.

Folosind aceasta definitie a modelului unui obiect, caracterizam G-dependente prin structura complexa a obiectului, bazata pe conceptele de dependente coerente, constrangeri de chei si identitatile unui obiect.

Teorema M este un model al obiectului E daca M verifica urmatoarele conditii:

1) este identificatorul lui E si

a) A este atribut univoc al lui E, atunci ->A_M

b) A este atribut multivoc al lui E, atunci ->_M.

_{c) K este cheie a lui E si K nu este identificatorul lui E, atunci} K->_{M si} ->K_M

_{2) Daca este componenta complexa a lui E ,} este identificatorul lui _si

_{a) B este atribut univoc al lui , atunci} ->B_{M si} -> B _M

_{b) B este atribut multivoc al lui , atunci} ->_{M si} -> _M

_{c) este cheie a lui si nu este identificatorul lui , atunci} ->_M

_si ->_M.

_{3) Daca sunt componente ale lui E, unde este o cale a lui E,}

este identificator al lui si daca

_{a) B este atribut univoc al lui , atunci} ->B_M

_unde =.

b) _{B este atribut multivoc al lui atunci}-> ararrrs_M

_unde =.

_{c) este cheie a lui si nu este identificatorul lui atunci} ->_M   

_si ->_M.

_{4) Nu mai sunt dependente in M.}

_{V.1. FORME NORMALE ALE UNUI OBIECT}

_{Fie un obiect O, modelul lui O este notat}, multimea de restrictii ale lui O este user. Prin Fw(w-o dependenta si F o multime de dependente) intelegem faptul ca w este rezultatul a uneia sau mai multor aplicatii a axiomelor de inferenta pentru elementele lui F.

Definitie(Forma Normala a unui obiect)

Un obiect E este in forma normala daca:

-fiecare componenta complexa a lui E are un identificator si

-user .

Teorema Daca un obiect E este in forma normala, atunci sunt satisfacute conditiile:

1) Daca A->B_user unde A si B sunt componente ale lui E, atunci A->B.

2) Daca B este componenta univoca a obiectului din E, atunci exista o multime de    atribute cheie unde este cheie in in E si este componenta a lui si -> B _user

Daca B este componenta multivoca a obiectului din E, atunci exista o multime de atribute cheie unde este cheie in din E si este componenta a lui si _user

4) Nu exista dependente intre atributele componente ale lui O din E care nu sunt cheie.

_{V. 2. Reguli de normalizare}

_{Pentru a normaliza un obiect trebuie analizate dependentele incoerente si modificata structura obiectului pana cand aceste dependente devin coerente, adica reflecta calea de acces a utilizatorului.}

Teorema Un obiect E este in forma normala daca :

1) Daca A->B este o dependenta inuser atunci

a) A-B este cale in E .

b) A este o multime de chei care sunt componente ale lui E unde este

componenta a lui si B este componenta univoca a lui .

c) A este componenta a lui O avand cardinalul 1:n si B este univoc in O.

2) Daca A->user atunci

a) A-B este cale in E .

b) A este o multime de chei care sunt componente ale lui E, unde este atribut al

lui si B este componenta multivoca a lui .

c) A este componenta a lui O avand cardinalul 1:n si B este componenta univoca in O.

_{Aceasta teorema sta la baza identificarii regulilor de normalizare.}

_{Regula 1 Fie E un obiect, daca exista o dependenta incoerenta} A->B(sau A->) si o cale care contine A si B, atunci este despartita in doua sub-cai: . contine numai A si B, contine A si (tB).

_{Regula 2 Fie E un obiect, daca toate dependentele lui E care utilizeaza obiecte complexe sunt coerente, si mai mult, daca exista o restrictie de G-dependente} A->B astfel incat

_user A->B, atunci E este transformat prin creearea unui nou obiect dupa proprietatile:

- este componenta a lui E, avand cardinalul(min(),min()),unde A= si () sunt cardinalele minime si maxime ale atributului.devine univoc in .

-B este componenta a lui .

-A este cheie a lui .

VI.Algoritmi de normalizare

Algoritmii de normalizare urmatori se bazeaza pe doua principii:

Primul algoritm are ca fundament pricipiul ca o schema orientata-obiect este doar o schema initiala si trebuie restructurata pentru a reflecta restrictiile impuse de utilizator. Aceasta metoda de normalizare este iterativa, insemand ca rafinarile succesive ale obiectelor proiectate sunt efectuate pana la final, cand este obtinuta schema orientata-obiect.

Al doilea algoritm porneste de la consideratia ca schema orientata-obiect existenta nu este sursa principala de informatii, dar poate fi folosita numai ca punct de plecare. Se folosesc G-dependentele pentru a genera o schema compatibila cu interpretarea utilizatorului. Schema deja existenta este folosita ca multime de obiecte universale, in care toate atributele sunt plasate la acelasi nivel si in care algoritmul resconstruieste structurile de obiecte potrivite.

Modelul de operare al celor doi algoritmi este:

Primul algoritm foloseste regulile de normalizare, Regula 1 si Regula 2, pe obiectele schemei, pana cand G-dependentele utilizatorului devin coerente.

Cel de-al doilea algoritm pleaca de la G-dependentele utilizatorului si identifica posibilele cluster-e intre atributele obiectelor universale.Testarea este efectuata prin derivarea potentialelor chei din G-dependente. Incluziunea cheilor defineste complexitatea cluster-elor obiectelor.

VI.1.Generare de forme normale prin restructurare. Algoritmul de transformare

Algoritmul aplica regulile de normalizare recursiv, pana cand toate dependentele sunt reflectate de obiecte in schema.

Formal, fie o schema S, S=< _user>, algoritmul de transformare converteste S intr-o schema normalizata S_n=< _{n n} >.

Algoritmul de transformare

INPUT: Multimea obiectelor

Interpretarea utilizatorului, _user, incluzand G-dependentele.

OUTPUT: Multimea de obiecte normalizate,

METODA:

For fiecare obiect O_i O do

Begin

For fiecare A->B (sau A->) do

If A-B nu este drum, dar A si B apartin aceluiasi drum

Then aplica Regula 1 obiectului O_i, pentru a ajunge la A-B

Else aplica Regula 2 obiectului O_i, pentru a crea obiectul AB

End.

Complexitatea algoritmului depinde de urmatoarele variabile:

-numarul de obiecte continute de schema, n;

-lungimea maxima a unui drum, m;

-numarul maxim de drumuri orizontale pe care le poate contine un obiect, p.

Analizand aceasta complexitate, se observa ca , pentru un numar mic de atribute, m este mic, deci algoritmul este polinomial O(n), dar , pentru un m mare, algoritmul devine costisitor. Din acest motiv, s-a dezvoltat un alt algoritm, mult mai eficient: ADF (Algoritmul de Descompunere si Fuziune).

VI.2 Generare de forme normale prin reconstructie. Algoritmul de Descompunere si

Fuziune

in obtinere formei normale a unui obiect se folosesc trei algoritmi:

Algoritmul 2 are ca punct de plecare o multime de obiecte si elimina toate cluster-ele de atribute complexe, care produc obiecte universale.Se identifica potentialele cluster-e de atribute.Cerinta este executata prin indentificarea cheilor. Fiecare cluster poate fi descompus, daca acesta contine mai mult de o cheie, si daca un cluster poate fi descompus, atunci exista un subgrup de obiecte care trebuie identificat.

Dupa ce descompunerea cluster-elor este completa, atunci Algoritmul 3 construieste o structura de tip arbore pentru fiecare cluster care nu mai poate fi descompus, prin folosirea identificarii pe baza cheii cluster-ului, asa cum G-dependentele sunt legate de obiectele cluster-ului. Se construiesc structurile complexe ale obiectelor prin identificarea relatiilor dintre cluster-e, prin utilizarea cheilor. Cu alte cuvinte, daca o cheie K₁ K₂, K₂ cheie, atunci arborele cluster-ului determinat de K₁ contine arborele cluster-ului determinat de K₂. Impreuna, arborii si legatura creeaza forme potrivite ale obiectelor pentru a reflecta G-dependentele.

Dupa ce au fost construiti toti arborii prin Algoritmul 3, Algoritmul 4 ii uneste dupa nodurile si muchiile comune. Arborele obtinut in final reprezinta structura complexa a obiectului normalizat.

Algoritmul de descompunere si fuziune

Fie S o multime de G-dependente. Notam S(cover) inchiderea lui S definita ca fiind cea mai mica multime care contine toate G-dependentele, rezultata din S prin aplicarea axiomelor de inferenta. S(cover) poate cuprinde G-dependentele care sunt redundante sau derivabile din restrictiile existente. Din acest motiv, folosim S(minimal), acoperirea minimala a lui S. Reconstructia structurii complexe a unui obiect este realizata prin identificarea potentialelor cluster-e a componentelor obiectelor ,prin G-dependente, din acoperirea minimala. Analizand partea stanga a dependentelor, obtinem cheia cluster-ului, fara intersectii intre chei, asigurand interconectarea cluster-elor.

Definitie (G-dependente redundante)

Daca S este o multime de G-dependente, atunci X->Y in S(cover) este:

-triviala: daca Y= sau YCX

-redusa la stanga: daca Xa, XaCX si Xa->Y S(cover)

Definitie (Acoperire minimala)

O multime S de G-dependente este acoperire minimala daca:

-V w S, w este G-dependenta redusa

Sa, SaC S si Sa(cover)=S(cover)

Din acoperirea minimala a multimii S se definesc conceptele apropiate de cluster:

-KEYS(S): o multime care contine G-dependente reduse la stanga a lui S(minimal).

KEYS(S)=. KEYS(S) identifica potentialele cluster-e din S.

-DEP(X, S) : cuprinde toate obiectele dependente de X, folosind restrictiile lui S.

DEP(X, S)=. Pentru o cheie X a cluster-ului, sunt identifictae elementele dependente de X.

Fie o schema S=< >. Primul pas consta in identificarea cluster-elor obiectelor, prin procedura DECOMPOSE( ), care foloseste chei derivate din . Dupa ce s-a gasit un subgrup, toate obiectele sale si G-dependentele sunt identificate cu functia DEP(). Partitia este completa cand nu se mai poate descompune cluster-ul.Urmeaza construire arborilor, cu Algoritmul 3 (procedura BUILD_TREE()). in final, dupa generarea tuturor arborilor, acestia sunt uniti prin Algoritmul 4, rezultand obiectul final.

Fie E un obiect, T o submultime a componentelor lui E. Notam:

_T : submultime din (E)_user, care cuprinde numai elementele lui T.

_T

-KEYS(T): toate cheile lui T. KEYS(T)=

-SUB_TREE(X, _T): functia returneaza multimea obiectelor care sunt partial sau totla dependente de X , conform G-dependentelor din _T, unde X este cheie in T.

Algoritmul 2( Algoritmul de descompunere)

Procedure DECOMPOSE()

INITIALIZARE:

T=

_{T E})(minimal)

INPUT: O schema orientata-obiect < >.

OUTPUT: O multime de cluster-e care nu mai pot fi descompuse, T.

METODA:

Repeat:

For fiecare T_r T do

Call _Tr

Call KEYS(T_r);

Sterge din KEYS(T_r) cheia T_r si cluster-ele tata ale lui T_r;

Sterge cheile nemaximale din KEYS(T_r);

If KEYS(T_r)= then

Begin

Sterge T_r din T;

REPEAT

For fiecare X KEYS(T_r) do

Call SUB_TREE(X, _Tr

Adauga SUB_TREE(X, _Tr) la T si sterge X din KEYS(T_r);

UNTIL KEYS(T_r)=

End.

UNTIL nici un element din T nu mai poate fi descompus.

Algoritmul 3( Construirea arborelui clustere-lor care nu se mai pot descompune)

Procedure BUILD_TREE()

INPUT: Cluster-ul T cu obiectele A₁, A_n, o multime de G-dependente, _T. Presupuneam ca aceasta multime este S si cuprinde G-dependentele :GD_1,, GD_m.

OUTPUT:Un arbore reprezentand cluster-ul T.

INITIALIZARE:

G₁= G_m=

METODA:

1)Ordonarea G-dependentelor in grupuri, punand GD-urile cu aceeasi parte stanga intr-un grup.

For fiecare GD S, GD de forma X->Y do

-gaseste cluster-ul potrivit pentru GD, Gk, cluster ce contine doar GD-urile care il au pe X parte stanga.

-adauga GD in Gk

2).Ordonare G1 ..Gk

if Xi<Xj, unde Xj LHS(Di), Di Gi si Dj Gj

then i<j;

3).Construirea arborelui

For i=1 to m do

For fiecare G-dependenta D in Gi do

creeaza noduri interne (atribute) ca LHS(D);

creeaza noduri periferice ca DEP(LHS(D), _T

leaga nodurile interne de nodurile periferice.

Algoritmul 4 (Algoritmul de Fuziune)

Procedure MERGE()

INPUT: Multimea de arbori T1, Tk.

OUTPUT: Un arbore unit, TREE.

INITIALIZARE: TREE=T1;

SET=

METODA:

REPEAT
for fiecare Ti SET do

If Ti TREE

Then TREE=MERGE_TREE(Ti,TREE);

Sterge Ti din SET;

UNTIL SET=

Consideram : s=numarul maxim de atribute ale unui obiect;

r=numarul de G-dependente din schema.

Complexitatea procedurii DECOMPOSE() este de O(s).Pentru Algoritmul 3, construirea unui arbore pentru un cluster este O(sxr). Algoritmul 4 uneste arborii in s pasii, pentru ca fiecare obiect are maxim s arbori.In concluzie, complexitatea algoritmului ADF este O(sxr).

VII.Concluzii   

Scopul lucrarii a fost de a prezenta cateva aspecte ale teoriei de normalizare pentru modelele obiectuale, implicand definirea notiunilor de restrictii de integritate, forme normale, reguli de normalizare. Restrictiile de integritate pentru o schema orientata-obiect se incadreaza in doua categorii: la nivel de schema si al nivel de obiect. La nivelul schemei, restrictiile reprezinta legaturile inter-obiectuale prin drumurile orizontale, pe cand la nivelul obiectului, restrictiile specifica legaturile intra-obiectuale prin drumurile verticale. Folosind aceste restrictii, formele normale ale unui obiect s-au definit ca un model de compatibilitate intre interpretarea utilizatorului si interpretarile reflectate de obiectele unei scheme. Structurile obiectuale pot fi restructurate pentru a deveni

compatibile cu interpretarea utitlizatorului sau construite direct din interpretarea utilizatorului.

Aspectele normalizarii descrise in lucrarea de fata pun accentul mai mult pe intelegerea universului utilizatorului, decat pe problemele de implementare a bazei de date. Mai mult, aplicata unui obiect, tehnica de normalizare produce un obiect normalizat, reflectand interpretarea utilizatorului si permitand multiplelor interpretari sa co-existe in obiect. Rezultatul nu este un obiect echivalent cu FN3, FNBC sau FN4 (daca obbiectul este privit ca o relatie), ci un obiect derivat din G-dependente. De asemenea, tehnica mai utilizeaza obiecte complexe, mostenire si identitatea unui obiect, oferind o gama de dependente care acopera tipuri variate de legaturi neexistente in modelul conventional, deci pune la dispozitie capacitati mai bune de modelare a realitatii.

Atat P-dependentele, cat si L-dependentele, G-dependentele contribuie la cresterea semanticii modelului orientat-obiect.Formele normale asigura corectitudinea specificatiilor orientate-obiect, tinand cont de restrictii. Algoritmii propusi furnizeaza metode potrivite de obtinere a reprezentarilor corecte a schemei. Toate acestea constituie elemente de baza in proiectarea unei scheme orientate-obiect. Proiectarea unei scheme orientate-obiect este dificila, obiectele complexe avnd interpretari multiple. Cei doi algoritmi ofera posibilitatea obtinerii unei scheme normalizate fie prin restructurarea obiectelor, respectandu-se regulile de normalizare, fie prin constructie. Primul este compatibil cu metodele iterative orientate-obiect, programatorul detinand mai mult control si permitandu-i-se evaluarea succesiva a fiecarei etape . Dar, cel de-al doilea algoritm este mai eficient in cazul schemelor de proportii.

Referinte:

Baza lucrarii de fata este constituita de:

Tari,Z.,1997, Object Normal Forms and Dependency Constraints for OO Schemata

ACM Transactions on Database Systems, vol.22,No.4 (dec.).

Alte referinte:

Rumbaugh,J., Blaha,M.,Premerlani,W.,Eddy,F. si Lorensen, W.,1991 Object-Oriented

Modeling and Design . Prentice-Hall,Inc.Upper Saddle River,NJ.

Tari.Z,1992, On the design of object-oriented databases in Proccedings of the Conference

on Entity-Relationships (Karlsruhe,Germany),389-405.