Proiectarea Bazelor de Date

Proiectarea Bazelor de Date

• Proiectarea corectă a unei baze de date este un pas important pentru implementarea cu succes a aplicațiilor software.
• Trebuie respectate metodologiile care impun normalizarea schemelor de relație, menținerea integrității datelor și eliminarea anomaliilor.
• Proiectarea trebuie privită sub două aspecte: conceptuală și logică.
• Schema conceptuală descrie modul abstract în care se dorește stocarea datelor reale.
• Procesul de realizare a schemei conceptuale se numește modelare conceptuală.

Dependențe Funcționale - Convenții de Notare

• R, S, T, …: reprezintă scheme de relații.
• r, s, …: reprezintă instanțe ale relațiilor R, respectiv S.
• A, B, C, D, …: reprezintă atribute ale unei relații (litere mari de la începutul alfabetului).
• X, Y, Z, W, U, …: reprezintă mulțimi de atribute dintr-o schemă de relație (litere mari de la sfârșitul alfabetului).
• X ⊆ R: Mulțimea de atribute X este inclusă în mulțimea atributelor relației R.
• Y ⊆ X: Mulțimea de atribute Y este inclusă în mulțimea de atribute X.
• A ∈ X: Atributul A aparține mulțimii de atribute X.
• t, t1, t2, …: reprezintă tupluri ale unei relații.
• t[X]: valorile atributelor din mulțimea X aflate în tuplul t.
• F, G, …: reprezintă mulțimi de dependențe funcționale atașate unei scheme de relație.

Dependențe Funcționale - Definiții

• Termenul de relație se referă atât la schema relației (descrierea structurii), cât și la o instanță a acesteia (datele propriu-zise).
• Dependența datelor este o restricție asupra relațiilor (instanțelor) care pot constitui valoarea curentă a unei scheme de relație R.
• Dependența funcțională este o legătură între două atribute, unde valoarea unui atribut determină valoarea celuilalt.
• Exemplu: atributul Matricol determină unic atributul Nume al unui student.
• X determină funcțional pe Y (X → Y) dacă, pentru oricare două tupluri t1 și t2 din orice instanță a lui R, dacă t1[X] = t2[X], atunci t1[Y] = t2[Y].
• Cu alte cuvinte, dacă două tupluri au aceleași valori pe atributele X, atunci ele au aceleași valori și pe atributele Y.

Exemple de Dependențe Funcționale

• Relația FURNIZORI (ID_furniz, Den_furniz, Adresa):
  • ID_furniz → Den_furniz
  • ID_furniz → Adresa
• Relația COMPONENTE (ID_com, Den_com, ID_furniz, Pret, Um):
  • ID_com → Den_com
  • ID_com → ID_furniz
  • ID_com → Pret, Um
  • ID_com → ID_furniz, Pret
• Single cale de a găsi dependențe funcționale valabile pentru o schemă R este analiza atentă a intelesului fiecărui atribut.

Interpretarea Dependențelor Funcționale

• ID_com → ID_furniz, Pret: ID-ul componentei identifică unic un produs, achiziționat de la un singur furnizor la un anumit preț.
• Dacă un produs cu același nume este achiziționat de la alt furnizor, acesta trebuie să aibă un alt ID_com.
• ID_furniz → Den_furniz: ID-ul furnizorului identifică unic un furnizor de componente.
• Două componente cu același ID_furniz înseamnă că sunt achiziționate de la același furnizor.
• Dependențele funcționale se determină din semnificația atributelor, nu prin inspectarea valorilor relației.

Axiomele și regulile lui Armstrong

• Pornind de la un set de dependențe funcționale, se pot deduce alte dependențe funcționale valide, folosind reguli de inferență.
• Exista mai multe reguli de inferență, dar trei dintre ele au fost alese ca axiome, restul fiind deduse din acestea.
• Axiomele lui Armstrong sunt:
  • Reflexivitate: Dacă Y ⊆ X, atunci X → Y.
  • Augmentare: Dacă X → Y, atunci XZ → YZ.
  • Tranzitivitate: Daca X → Y si Y → Z atunci X → Z
• Dependențele funcționale care rezultă din axioma reflexivității sunt considerate triviale.

Reguli de inferență derivate din axiomele lui Armstrong

• Descompunere: Fie X, Y, Z ⊆ R. Dacă X → Y și Z ⊆ Y, atunci X → Z.
• Reuniune: Fie X, Y, Z ⊆ R. Dacă X → Y și X → Z, atunci X → YZ.
• Pseudotranzitivitate: Fie X, Y, Z, W ⊆ R. Dacă X → Y și YZ → W, atunci XZ → W.
• Regula descompunerii permite rescrierea unui set de dependențe funcționale, astfel încât partea dreaptă să conțină doar un singur atribut.

Închiderea unei Mulțimi de Dependențe Funcționale

• Pornind de la un set de dependențe funcționale F, utilizând axiome și reguli, se obține o mulțime de alte dependențe, triviale sau nu.
• Mulțimea tuturor dependențelor funcționale care se pot deduce din F se numește închiderea mulțimii de dependențe funcționale F, notată cu F+.
• F+ = {X → Y | F ⇒ X → Y}, unde "⇒" indică faptul că dependența respectivă se poate deduce din F folosind axiome și reguli.
• F+ conține foarte multe dependențe, inclusiv dependențe triviale (ex: ABC → A, ABC → B, etc.).
• Calculul complet al F+ este evitat de algoritmii care au nevoie de ea.
• Noțiunea de închidere este folosită pentru a explica dependențele moștenite în cazul descompunerii unei scheme de relație.

Acoperirea și Echivalența Mulțimilor de Dependențe Funcționale

• Fie R o schemă de relație și F, G două mulțimi de dependențe funcționale pentru R.
• F acoperă G dacă și numai dacă G ⊆ F+.
• F este echivalentă cu G dacă și numai dacă F acoperă G și G acoperă F (adică, G ⊆ F+ și F ⊆ G+).

Forma Canonică a unei Mulțimi de Dependențe Funcționale

• O mulțime de dependențe este în formă canonică dacă:
  • Orice dependență are un singur atribut în partea dreaptă (se obține prin descompunere).
  • Mulțimea de dependențe este minimală (niciuna dintre dependențe nu poate fi dedusă din celelalte).

Exemple de Transformare în Formă Canonică

• Exemplul 1: F = {AB → CDE, C → DE} devine F = {AB → C, C → D, C → E}.
• Exemplul 2: Pentru relația COMPONENTE = (ID_com, Den_com, Pret, ID_furniz, Den_furniz) cu F = {ID_com → Den_com, Pret, ID_furniz, Den_furniz; ID_furniz → Den_furniz}, forma canonică este F = {ID_com → Den_com, ID_com → Pret, ID_com → ID_furniz, ID_furniz → Den_furniz}. Dependența redundantă ID_com → Den_furniz este eliminată.

Implicații Logice ale Dependențelor

• F implică logic X→Y, dacă orice relație r pentru R, care satisface dependențele din F, satisface si X→Y.
• Dacă R are atributele A, B, C și dependențele A→B și B→C sunt valabile, atunci A→C este de asemenea valabilă (tranzitivitate).
• Închiderea mulțimii de dependențe F (notată cu F+) poate fi definită ca mulțimea dependențelor funcționale implicate logic de F.

Cheia si supercheia unei relatii

• In acest punct poate fi data o definitie echivalenta a cheii unei relatii pe baza dependentelor functionale.
• Definitia este: Fie R o schema de relatie, F multimea de dependente functionale asociata si X ⊆ R.
• Atunci X este cheie pentru R daca si numai daca: F ⇒ X → R (deci X → R se poate deduce din F); X este minimala: oricare ar fi Y ⊂ X, Y ≠ X atunci ¬(F ⇒ Y → R) (deci orice submultime stricta a lui X nu mai indeplineste conditia anterioara).
• Observatie: cunoscandu-se valorile pe atributele X, pot fi determinate unic valorile pentru toate atributele relatiei, deci este determinat unic un tuplu din relatie.

Proiectia Multimii de DF

• Fie o relatie R, o multime asociata de dependente functionale F si o submultime de atribute S ⊆ R.
• Proiectia multimii de dependente F pe S, notata cu πS(F) este multimea dependentelor din F + care au atributele din partea stanga si cea dreapta incluse in S.
• Când se descompune o structură pot apărea pierderi ale anumitor dependențe.

Închiderea unei mulțimi de atribute

• Fie R o schema de relatie, F multimea de dependente asociata si X ⊆ R.
• Se poate defini X+ ca fiind închiderea multimii de atribute X in raport cu F astfel: X+ = { A | X → A ∈ F+ }
• Scopul introducerii acestei notiuni este si acela de a putea ocoli calculul lui F+ in alti algoritmi sau definitii.

Euristica de gasire a cheilor unei relații

• Pentru gasirea cheilor unei relatii pornim de la observatia ca atributele care nu sunt in partea dreapta a niciunei dependente nu pot sa apara in procesul de inchidere a unei multimi de atribute, deci ele apartin oricarei chei a relatie.
• Procesul se opreste cand nu se mai pot face augmentari.
• Este necesar ca atributele să aparțină oricărei chei.
• Se adaugă la chei atribute din R-X+.

Acoperiri de multimi de dependinte

• Fie F, G – multimi de dependente functionale. Daca F+=G+, spunem ca F si G sunt echivalente.
• Daca o dependenta Y→Z din F nu este in G+, atunci sigur F +≠G+.
• Daca fiecare dependenta din F este in G+, atunci fiecare dependeta V→W din F + este in G+; pentru a arata ca V→W este in G+, se demonstreaza ca fiecare Y→Z din F este in G+, apoi ca V→W este in F +.
• F si G vor fi echivalente daca fiecare dependenta din F este si in G+, iar fiecare dependenta din G este si in F +.
• Fiecare multime de dependente functionale F este acoperita de o multime de dependente G, in care nicio dependenta nu are in parte dreapta mai mult de un atribut. .

Multime minimala de dependinte

• O multime de dependente F este minimala daca: Partea dreapta a fiecarei dependente din F contine un singur atribut. Pentru nicio dependenta X→A din F, multimea F-{X→A} nu este echivalenta cu F; Pentru nicio dependenta X→A din F si pentru nicio submultime Z ⊆X, multimea F-{X→A} ∪ {Z→A} nu este echivalenta cu F.