LMD RELATIONALE

LMD = limbaje pentru formularea interogarilor

Clasificare LMD: - navigationale (modelul ierarhic si modelul retea)

- relationale (modelul relational)

Caracteristici:

A. LMD navigational:

- se bazeaza pe utilizarea conceptului de cursor (indica

pozitia curenta in baza de date).

- actiuni utilizator asupra cursorului:

a1)modificare pozitie cursor

a2)modificare date din pozitia curenta cursor

- lmd navigationale exploateaza direct legaturile explicite

existente in baza de date rezolvarea interogarilor presupune

in general navigatia cursorului pe lanturile de legaturi

B. LMD relational:

Ceea ce diferentiaza Modelul de Date Relational in raport cu celelalte

modele, d.p.d.v. al posibilitatii formularii interogarilor:

LMD RELATIONAL

(celelalte modele permit doar LMD navigational)

In MR, intre relatii nu exista legaturi explicite pt. realizarea conexiunii

intre diferite relatii in vederea tratarii interogarilor este necesara cuplarea

dinamica a relatiilor (implementarea operatiilor de cuplare necesita

echipamente de calcul evoluate, dispozitive de memorare de suficient de

mare capacitate, tehnici avansate de programare si structurare a datelor)

Limbaje de Interogare pt. Modelul Relational ( grupe principale ):

A. Limbaje care au la origine Algebra Relationala (interogarile sunt

exprimate prin aplicarea unor operatori specializati asupra relatiilor)

Obs: Limbajele derivate se numesc Limbaje Algebrice.

B. Limbaje care au la origine Calculul Relational (interogarile descriu

multimea tuplelor rezultat prin specificarea unui predicat pe care

aceste tuple trebuie sa-l satisfaca)

Obs1: predicat = conditie ( in acest context)

Obs2: Obiecte primitive cu care se opereaza in Calculul Relational:

(1) tuple ==> Calculul Relational al Tuplelor

(2) valori din domenii ==> Calculul Relational al Domeniilor

B.1. Limbaje bazate pe Calculul Relational al Tuplelor

B.2. Limbaje bazate pe Calculul Relational al Domeniilor

Obs3: a. Algebra Relationala, Calculul Relational al Tuplelor si

Calculul Relational al Domeniilor sunt limbaje abstracte (nu

sunt implementate ca atare in nici un SGBD existent).

b. Algebra Relationala, Calculul Relational al Tuplelor si

Calculul Relational al Domeniilor servesc ca referinta pt.

evaluarea limbajelor reale existente in diferite SGBD-uri

(care sunt derivate din aceste formalisme abstracte); au fost

propuse (definite) ca atare de catre CODD; reprezinta

facilitatile minime pe care trebuie sa le posede orice limbaj de

interogare relational, pentru a putea fi considerat limbaj

relational complet.

c. Cele trei formalisme (AR, CRT si CRD) sunt echivalente ca

putere de expresie ( pt. orice interogare, exprimata in cadrul

unuia din formalisme, exista interogari echivalente in fiecare

din celelalte doua).

Obs4: Facilitatile suplimentare, necuprinse in formalismele

abstracte, de care dispun limbajele reale, includ:

- comenzi de inserare

- comenzi de stergere

- comenzi de modificare

- posib. efect. de calcule aritm.

- fctii de tiparire a relatiilor de atribuire a

acestora unor nume de variabile

- fctii de agregare care efectueaza diverse

operatii: medie, suma, min, max (pe valorile

unei coloane dintr-o relatie)

Limbaje reale derivate din formalismele prezentate (exemple):

Ex1. ISBL ( Information System Base Language) dezvoltat in

cadrul IBM (centrul stiintific din Peterlee) = limbaj de

interogare bazat pe Algebra Relationala

Ex2. QUEL = limbaj de interogare al SGBD relational INGRES,

dezvoltat la Univ. Berkley (California) sub sistem

UNIX; este bazat pe Calculul Relational al Tuplelor

Ex3. QBE ( Query By Example) dezvoltat in cadrul IBM; are la

baza Calculul Relational al Domeniilor.

Ex4: SQUARE si SEQUEL (SQL) limbaje intermediare intre

Algebra Relationala si Calculul Relational;

dezvoltate in cadrul IBM (sectia din San Jose) ca

limbaje de interogare pentru SGBD-ul SystemR

ALGEBRA RELATIONALA

Def. Formalism abstract propus de Codd pentru interogarea b.d.

relationale

Bazat pe : set de operatori folositi ca primitive pt. construirea

interogarilor.

Obs. AR = limbaj abstract de tip procedural (interogarile

exprimate cu ajutorul ei sunt de fapt secvente de

operatori care specifica explicit modul de obtinere al

relatiei rezultat)

Operatorii AR: - operatori unari sau binari care actioneaza

asupra relatiilor; rezultatul lor sunt tot relatii

posibilitatea asocierii si imbricarii pt. a forma

interogari complexe

Grupe de Operatori:

O1: Operatori pt. Multimi

Reuniune

Intersectie

Diferenta

Produs Cartezian

OBS: Pt. Operatiile de Reuniune, Intersectie si Diferenta, cele doua relatii operand trebuie sa fie compatibile la reuniune, ceea ce

inseamna ca trebuie sa fie de acelasi grad, iar atributele

corespondente trebuie sa fie derivate din acelasi domeniu.

Definitii:

Reuniunea a doua relatii A si B, notata A B, este o relatie R care contine

toate tuplele care apartin relatiei A sau relatiei B.

Intersectia a doua relatii A si B, notata A B, este o relatie R care contine

toate tuplele care apartin atat relatiei A cat si relatiei B.

Diferenta a doua relatii A si B, notata A - B, este o relatie R care contine

toate tuplele care apartin relatiei A dar nu apartin relatiei B.

Produsul Cartezian a doua relatii A si B, notat A x B, A fiind de gradul m

iar B de gradul n, este o relatie R de grad m+n, care contine toate

tuplele obtinute prin concatenarea fiecarei tuple din relatia A cu

fiecare tupla din relatia B (exemplificare).

O2: Operatori Relationali Speciali

O2.1 Operatori Relationali Speciali Unari:

- Proiectia

- Selectia

O2.2 Operatori Relationali Speciali Binari:

- Cuplarea (Join)

- Diviziunea

Definitii:

O2.1 :

Selectia printr-un predicat P a unei relatii A, notata P(A), este o relatie

R care contine toate tuplele din relatia A care satisfac

predicatul P. Predicatul P este o formula (conditie) care

poate contine:

- operanzi ce sunt fie nume de atribute fie

constante

- operatori de comparatie ( =, , , = )

- operatori logici ( &, | , ! )

Proiectia pe atributele A1, A2, A3,..., An a unei relatii B de grad m>n si

care cuprinde atributele A1, A2, A3,..., An , notata A1, A2, A3,..., An(B), este o relatie R de grad n obtinuta din relatia B astfel:

Pasul 1: Se elimina din relatia B atributele care nu sunt specificate in

lista de proiectie, a.i. raman doar coloanele corespunzatoare

atributelor A1, A2, A3,..., An

Pasul 2: Se reordoneaza atributele ramase in ordinea specificata in

lista de proiectie A1, A2, A3,..., An

Pasul 3: Se elimina tuplele duplicat.

Proiectia unei relatii = o selectie verticala a acesteia (se selecteaza

coloanele coresp. atributelor din lista de proiectie), urmata

de eliminarea tuplelor duplicat si reordonarea atributelor

ramase in ordinea specificata prin lista de proiectie.

O2.2 :

Cuplarea (Join) :

Fie un operator aritmetic de comparatie ( =, , , = );

Fie X un atribut al relatiei A si Y un atribut al relatiei B, X si Y fiind definite pe domenii compatibile;

Numim - cuplare a relatiilor A si B dupa atributele X si Y , notata

A 43 B X Y

o relatie R care contine acele tuple ale produsului cartezian AxB

care au proprietatea ca valorile x si y corespunzatoare atributelor X

respectiv Y sunt in relatia x y.

OBS:

A 43 B = X Y (AxB) X Y

Diviziunea relatiei A de grad m prin relatia B de grad n , notata A B,

este o relatie R de grad m-n, formata din multimea tuplelor r

cu proprietatea ca pentru orice tupla b din B exista o tupla a

in A egala cu rezultatul concatenarii tuplelor r si b.

OBS:

a) Multimea atributelor relatiei B trebuie sa fie o submultime a

multimii atributelor relatiei A. Relatia R contine doar acele

atribute din relatia A care nu apar in relatia B.

b) O tupla din relatia A este retinuta in urma operatiei de diviziune

numai daca este legata de fiecare tupla din relatia B printr-o conditie predefinita.

c) Relatia obtinuta prin produsul cartezian al relatiilor R si B este

inclusa in relatia A (rezulta direct din definitie); notand prin Rest

multimea tuplelor din relatia A care nu apar in produsul cartezian

al relatiilor B si R obtinem urmatoarea relatie ( asemanatoare cu teorema impartirii cu rest din aritmetica):

A = B x R Rest

NORMALIZAREA RELATIILOR. FORME NORMALE

Normalizarea tehnica obligatorie in proiectarea conceptuala a oricarei

b.d., dar in mod special in b.d. relationale

Concepte fundamentale:

(1) Dependenta functionala (FN1, FN2, FN3, FNBC/F.N. Boyce-Codd)

(2) Dependenta multivalorica (FN4)

(3) Dependenta de cuplare (FN5)

Schema de relatie = tupla care cuprinde: (a) numele relatiei si

(b) atributele asociate

Problema proiectarii robuste a unei b.d. relationale:

(a) alegerea schemelor de relatie si

(b) modul de grupare a atributelor in relatii pt. a reprezenta

tipuri de entitati sau legaturi intre tipurile de entitati

Criteriul central de proiectare: Dependenta Datelor

Dependenta Functionala (Def.):

Fie: - schema de relatie R(A1, A2,..., An)

- X si Y atribute simple sau compuse, submultimi ale

multimii de atribute {A1, A2,..., An}

Spunem ca atributul X determina functional atributul Y (sau Y

depinde functional de X) ddca oricarei valori a atributului X ii

corespunde o singura valoare a atributului Y.

Notatie: X Y.

Dependenta Functionala Totala & D. F. Partiala (Defs.):

Dependenta functionala X Y este totala daca nu exista nici

un subset Z al atributului X ( Z X) a. i. Z Y. In caz contrar dependenta se numeste partiala.

OBS1: Daca X Y, atunci pt. orice subset Z al lui Y avem XZ.

OBS2: Daca X Y si X este un atribut simplu, atunci Y este dependent

functional total fata de X.

OBS3: Daca Y este dependent functional total fata de Z, atunci X Y pt.

orice atribut compus X care contine pe Z.

Axiomele lui ARMSTRONG: (set de reguli pt. deducerea dependentelor

functionale care sunt consecinte ale unui set de dependente

functionale date initial)

Ipoteza: Fie X, Y si Z submultimi ale multimii de atribute { A1, A2,..., An }

(A1) reflexivitate: Daca Y X atunci X Y.

(A2) - augmentare: Daca X Y, atunci X Z Y Z.

(A3) - tranzitivitate: Daca X Y si Y Z, atunci si X Z.

OBS. A3 este singura axioma care conduce la dependente noi si netriviale.

Celelalte doua axiome sunt utile in combinatie cu A3.

Inchidere Tranzitiva a setului de dependente functionale F (notata F*) =

=multimea dependentelor functionale care se pot obtine prin

aplicarea repetata, in toate modurile posibile, a regulilor A1-A3

asupra unui set initial de dependente functionale F .

Dependente Multivalorice :

- mai putin restrictive decat dep. Functionala

- au implicatii in normalizarea relatiilor

Def.:

Fie schema de relatie R(X,Y,Z),

unde X,Y si Z sunt atribute simple sau compuse.

Notam cu x, y si z valori ale atributelor X, Y si Z.

Spunem ca exista o Dependenta Multivalorica a atributului Z fata de Y

(sau Y multidetermina pe Z) si notam Y Z daca pt. orice valori x1, x2,y,

z1 si z2, cu x1x2 si z1z2 , astfel incat tuplele (x1,y, z1) si (x2,y, z2) fac parte

din relatia R, atunci si tuplele (x1,y, z2) si (x2,y, z1) fac parte din relatia R.

OBS1: Dependenta multivalorica YZ implica si dependenta

multivalorica complementara YX (acest lucru rezulta direct din simetria

definitiei dependentei multivalorice).

OBS2: In particular, unele dependente multivalorice pot fi de fapt

dependente functionale.

Axiomele lui Armstrong pentru dependentele functionale si

multivalorice, precum si pt. legatura dintre acestea: (set de reguli

pt. determinarea sistematica a tuturor dependentelor multivalorice care

sunt o consecinta logica a unui set initial)

Ipoteza: Fie X, Y si Z submultimi ale multimii de atribute U={ A1, A2,..., An }

(A1) reflexivitate pt. dep. functionale:

Daca Y X atunci X Y.

(A2) - augmentare pt. dep. functionale:

Daca X Y, atunci X Z Y Z.

(A3) - tranzitivitate pt. dep. functionale:

Daca X Y si Y Z, atunci si X Z.

(A4) complementare pentru dep. multivalorice:

Daca XY, atunci X U-(X Y) ,

unde U-(X Y) este atributul complementar lui Y in raport cu atributul X

(aceasta regula deriva din caracterul simetric al dependentelor multivalorice)

(A5) augmentare pentru dep. multivalorice:

Daca XY, si V W, atunci WX V Y.

(A6) - tranzitivitate pt. dep. multivalorice:

Daca XY si Y Z, atunci X Z-Y.

(A7) Daca XY atunci XY (orice dependenta functionala este in

acelasi timp si o dependenta multivalorica)

(A8) Daca XY, Z Y si pt. W disjunct fata de Y avem: W Z,

atunci X Z.

OBS1: Aceste axiome extind setul de axiome date pentru dependenta

functionala, constituind un set complet si sigur de reguli de inferenta,

adica permit deducerea tuturor dependentelor functionale si

multivalorice care sunt logic deductibile din setul initial de

dependente orice relatie care satisface setul initial de

dependente va satisface de asemenea orice dependenta din inchiderea

tranzitiva a acestui set.

OBS2: Axiomele (A5) si (A6) pun in legatura dependentele functionale cu

cele multivalorice.

Descompunerea Schemelor de Relatie

Calea principala de eliminare a Dependentelor Functionale din schemele

de relatie (pt. evitarea redondantei datelor):

Descompunerea schemei de date intr-o colectie de scheme mai simple care

trebuie sa evite aceste probleme

Conventie:

Schema de Relatie == Multimea atributelor relatiei

R(A1, A2,..., An) echivalent cu R = { A1, A2,..., An }

Def. 1: Descompunerea unei Scheme de Relatie R = { A1, A2,..., An }

inseamna inlocuirea acesteia printr-o colectie = { R1, R2,..., Rk } de submultimi ale lui R , a.i.

R = R1 R2 ... Rk unde R1, R2,..., Rk nu sunt neaparat disjuncte.

OBS.1: Printr-o astfel de descompunere se realizeaza o separare a

continutului de informatie din relatia initiala a.i. fiecare din

schemele de relatie rezultate sa reprezinte un singur tip de entitate

sau o legatura intre doua tipuri de entitati.

OBS.2: Numai o parte dintre descompunerile de acest tip au proprietatea ca

din relatiile corespunzatoare schemelor descompunerii se poate

reconstitui relatia initiala; pt. o astfel de reconstituire se foloseste

operatorul de cuplare.

Def. 2: Descompunere echivalenta a relatiei R, notata cu :

Descompunerea a relatiei R este echivalenta cu relatia R daca satisface urmatoarele doua proprietati:

(1) cuplare fara pierdere de informatie ( lossless join property )

(2) conservarea dependentelor ( dependency preservation )

(1) Cuplarea fara pierdere de informatie (LJP) = proprietatea unei

descompuneri de a conserva continutul de informatie al oricarei relatii

asupra careia se aplica aceasta descompunere.

Formalizarea matematica:

Fie R o schema de relatie descompusa in schemele R1, R2, ..., Rk.

Aceasta descompunere are proprietatea LJP daca pt. orice relatie r

reprezentand valoarea actuala a relatiei R, avem:

r = R1(r) R2(r)... Rk(r)

( deci r este rezultatul cuplarii proiectiilor sale dupa schemele de relatie

R1, R2, ..., Rk ) .

Caz particular: Teorema lui ULLMAN

Fie = { R1, R2 } o descompunere a schemei de relatie R. In acest caz

particular, constituie o descompunere fara pierdere de informatie in raport cu un set dat de dependente functionale initiale, daca in urma

descompunerii obtinem una din urmatoarele dependente functionale:

(R1 R2 ) (R1- R2 ),

(R1 R2 ) (R2 R1) .

COROLAR:

Daca intersectia celor doua proiectii ale unei descompuneri, R1 R2 este sau contine o cheie a uneia dintre componentele R1 sau R2 , atunci

descompunerea este fara pierdere de informatie. Acest lucru se verifica

prin existenta cel putin uneia din dependentele:

(R1 R2 ) R1 (R1 - R2 ),

(R1 R2 ) R2 (R2 R1 ).

OBS:

Proprietatea de conservare a informatiei depinde nu numai de

descompunerea , ci si de setul initial de dependente functionale existente in schema de relatie R.

(2) Conservarea dependentelor (DP) = proprietatea unei descompuneri de

a permite deducerea tuturor dependentelor din relatia initiala pe baza

dependentelor existente in descompunere.

Formalizarea matematica:

Fie R o schema de relatie si = { R1, R2 ,..., Rk } o descompunere a sa: - o parte dintre dependentele functionale existente in R se vor regasi

in cadrul schemelor de relatie Ri din descompunerea sa

- dependentele care implica atribute din componente diferite Ri si Rj

ale descompunerii nu vor fi regasite in cadrul schemelor

individuale Ri, ca atare se pierd.

Obs: Proprietatea (DP) este importanta d.p.d.v. al integritatii bazei de date,

deoarece dependentele din cadrul unei scheme de relatie R pot fi privite ca si

constrangeri de integritate a datelor din cadrul schemei.

FN1: Forma Normala 1.

Def: O relatie R este in forma normala FN1 ddaca toate atributele sale

iau numai valori atomice. (valori atomice = valori care nu pot fi

descompuse in elemente constitutive mai fine; ex: atributul Adresa nu are

valoare atomica).

Obs: Conditia ca o relatie sa se afle in FN1 impune ca domeniile pe care se

definesc atributele relatiei R sa contina doar elemente atomice

toate tuplele unei relatii au acelasi numar de campuri, cu aceeasi

dimensiune.

FN2: Forma Normala 2.

Def: O relatie R este in forma normala FN2 daca este in FN1 si orice

atribut neprim este total dependent fata de orice cheie a relatiei.

FN3: Forma Normala 3.

Def: O relatie R este in forma normala FN3 daca este in FN2 si nici un

atribut neprim nu este functional dependent fata de un alt atribut neprim al

relatiei.

Forma Normala BOYCE CODD (FNBC)

Def: O relatie R este in forma normala FNBC daca pentru orice

dependenta functionala X A din cadrul relatiei R, unde A este un atribut

care nu face parte din X, atributul X (care poate fi si un atribut compus) este

o cheie in R sau include o cheie din R.

OBS: O relatie care este in FNBC, se afla si in FN3, FN2 si FN1.

FN4: Forma Normala 4.

Def: O relatie R este in forma normala FN4 daca oricare ar fi dependenta

multivalorica X Y, unde Y nu este un subset al lui X si X Y nu

contine toate atributele lui R, atunci atributul simplu sau compus X este o

cheie sau contine o cheie a lui R.

DEPENDENTA DE CUPLARE. FORMA NORMALA FN5:

OBS1: Rezolvarea neredondantei datelor in contextul bazei de date necesita

analiza atat a dependentelor functionale si multivalorice, cat si a asa-numitor

dependente de cuplare.

Def:

Fie R(A1, A2, ... , An) o schema de relatie si R1, R2, ... , Rk submultimi

ale multimii { A1, A2, ... , An } . Spunem ca exista o dependenta de cuplare ,

notata cu *( R1, R2, ... , Rk), ddaca orice instantiere r a lui R este rezultatul

cuplarii proiectiilor sale pe R1, R2, ... , Rk

< = = > r = R1(r) R2(r)... Rk(r)

Def. echivalenta:

*( R1, R2, ... , Rk) este o dependenta de cuplare pe R ddaca

descompunerea lui R dupa componentele R1, R2, ... , Rk este fara pierdere

de informatie.

OBS2: Dependentele multivalorice sunt cazuri particulare de dependente de

cuplare.

Transcriere matematica: Orice relatie R(X,Y,Z) care satisface dependentele

multivalorice XY si XZ satisface si dependenta de cuplare

*(XY,XZ).

FORMA NORMALA FN5:

Def: O relatie R este in forma normala FN5 ddaca toate dependentele de

cuplare existente in relatie sunt implicate de o cheie a acesteia.

OBS3:

Forma normala FN5 este o generalizare a formei normale FN4, avand ca

punct de pornire conceptul de dependenta de cuplare.

Procesul de trecere a unei relatii in forma normala FN5 :

- eliminarea dependentelor de cuplare din cadrul

relatiei, impreuna cu anomaliile pe care le cauzeaza

- selectarea in acest scop a dependentelor de cuplare

care prezinta interes d.p. de vedere al generarii de

redondante

Ex. de dependente de cuplare care nu conduc la redondanta in memorarea

datelor si, ca atare nu cauzeaza anomalii: dependentele de cuplare cauzate de

o cheie a relatiei.

CONCLUZII privind NORMALIZAREA RELATIILOR:

FN1 - se obtine prin atomizarea tuturor atributelor relatiei

FN2 = FN1 + eliminarea tuturor dependentelor functionale partiale

ale atributelor neprime in raport cu orice cheie a relatiei

FN3 = FN2 + eliminarea tuturor dependentelor functionale dintre

toate atributele neprime ale relatiei

FNBC = eliminarea tuturor dependentelor functionale fata de atribute

care nu sunt chei sau nu contin o cheie.

DEFINITIE GLOBALA PT. FNBC, FN4 si FN5:

O relatie este in FNBC (respectiv FN4 sau FN5) ddaca

singurele dependente functionale (respectiv multivalorice

sau de cuplare) existente sunt cele implicate de o cheie a

relatiei R.

OBS: Orice dependenta intre atributele unei relatii, indiferent de tipul

acesteia (functionala, multivalorica sau de cuplare), este

producatoare de redondante si anomalii, doar atunci

cand nu este implicata de o cheie a relatiei.

*************************************************************

Scopul normalizarii relatiilor: Eliminarea din schemele de relatie a dependentelor functionale,

multivalorice si de cuplare, cu scopul de a produce o schema

relationala cu proprietati mai bune d.p.d.v. al neredondantei

datelor, precum si al posibilelor anomalii ce pot sa apara in cazul

operatiilor de adaugare, stergere si actualizare.

*************************************************************

Locul normalizarii in contextul activitatii de proiectare a B.D.

Teoria Normalizarii = cadru de ghidare a proiectantului b.d. in vederea

realizarii de scheme relationale mai bune.

OBS1: Prin procesul normalizarii, sunt inglobate in modelul relational

aspectele semantice aferente dependentelor care apar in contextul general

al datelor modelate, decurgand din semnificatia pe care insusi proiectantul

o atribuie diferitelor categorii de date.

OBS2: Dependentele sunt formulate sub forma unor constrangeri, care

reflecta caracteristici sau aspecte suplimentare ale partii din lumea reala ce

se modeleaza prin schema relationala.

OBS3: Decizia de a aplica sau nu o anumita etapa de normalizare este la

latitudinea proiectantului b.d. , aceasta decizie depinzand de contextul

existent. Normalizarea este avantajoasa in principiu , dar in unele cazuri

normalizarea completa (adica pana la obtinerea FN5) poate fi

dezavantajoasa.

OBS4: Prin aplicarea corecta a unei metodologii de proiectare descendente

(de ex. folosind modelul E/R), obtinem modele care au tendinta de a fi gata

normalizate.