Dependențe funcționale în bazele de date – Axiomele lui Armstrong

O dependență funcțională (functional dependency, FD) este o relație între două atribute, de obicei între PK și alte atribute non-cheie dintr-un tabel. Pentru orice relație R, atributul Y este funcțional dependent de atributul X (de obicei PK), dacă pentru fiecare instanță validă a lui X, acea valoare a lui X determină în mod unic valoarea lui Y. Această relație este indicată de reprezentarea de mai jos:

X –-> Y

Partea stângă a diagramei FD de mai sus se numește determinant, iar partea dreaptă este dependent. Iată câteva exemple.

În primul exemplu de mai jos, SIN determină numele, adresa și data nașterii. Având în vedere SIN, putem determina oricare dintre celelalte atribute din tabel.

SIN–-> Name, Address, Birthdate

Pentru al doilea exemplu, SIN și Course determină data finalizării (DateCompleted). Acest lucru trebuie să funcționeze și pentru un PK compozit.

SIN, Course–> DateCompleted

Al treilea exemplu indică faptul că ISBN determină Titlul.

ISBN–-> Title

Regulile dependențelor funcționale

Luați în considerare următorul tabel de date r(R) al schemei de relații R(ABCDE) prezentat în Tabelul 11.1.

A	B	C	D	E
al	bl	Cl	dl	el
a2	bl	C2	d2	el
a3	b2	Cl	dl	el
a4	b2	C2	d2	el
a5	b3	C3	dl	el

Tabelul R

Tabelul 11.1. Exemplu de dependență funcțională, de A. Watt.

Când vă uitați la acest tabel, întrebați-vă: Ce fel de dependențe putem observa printre atributele din Tabelul R? Deoarece valorile lui A sunt unice (a1, a2, a3 etc.), din definiția FD rezultă că:

A → B, A → C, A → D, A → E

• Rezultă, de asemenea, că A → BC (sau orice alt subset al ABCDE).
• Acest lucru poate fi rezumat ca A → BCDE.
• Din înțelegerea noastră a cheilor primare, A este o cheie primară.

Deoarece valorile lui E sunt întotdeauna aceleași (toate e1), rezultă că:

A → E, B → E, C → E, D → E

Cu toate acestea, în general nu putem rezuma cele de mai sus cu ABCD → E deoarece, în general, A → E, B → E, AB → E. Alte observații:

1. Combinațiile BC sunt unice, deci BC → ADE.
2. Combinațiile de BD sunt unice, prin urmare BD → ACE.
3. Dacă valorile C se potrivesc, la fel și valorile D.
   1. Prin urmare, C → D
   2. Cu toate acestea, valorile D nu determină valorile C
   3. Deci C nu determină D, iar D nu determină C.

O privire asupra datelor reale poate ajuta la clarificarea care atribute sunt dependente și care sunt factorii determinanți.

Reguli de inferență

Axiomele lui Armstrong sunt un set de reguli de inferență utilizate pentru a deduce toate dependențele funcționale ale unei baze de date relaționale.

Au fost dezvoltate de William W. Armstrong. În cele ce urmează este descris ce va fi folosit, în termeni de notație, pentru a explica aceste axiome.

Fie R(U) o schemă de relație peste setul de atribute U. Vom folosi literele X, Y, Z pentru a reprezenta orice subset de și, pe scurt, unirea a două seturi de atribute, în loc de X U Y obișnuit. .

Axioma reflexivității

Această axiomă spune că, dacă Y este un subset al lui X, atunci X îl determină pe Y (vezi Figura 11.1).

Dacă Y X, atunci X → Y

Figura 11.1. Ecuația pentru axioma reflexivității.

De exemplu, PartNo -> NT123 unde X(PartNo) este compus din mai multe informații; adică Y(NT) și partID(123).

Axioma augmentării

Axioma augmentării, cunoscută și sub numele de dependență parțială, spune că dacă X determină Y, atunci XZ determină YZ pentru orice Z (vezi Figura 11.2).

Dacă X → Y, atunci XZ → YZ pentru orice Z

Figura 11.2. Ecuația pentru axioma augmentării.

Axioma augmentării spune că fiecare atribut non-cheie trebuie să fie pe deplin dependent de PK. În exemplul prezentat mai jos, StudentName, Address, City, Prov și PC (cod poștal) depind numai de StudentNo, nu de StudentNo și Grade.

StudentNo, Course -> StudentName, Address, City, Prov, PC, Grade, DateCompleted

Această situație nu este de dorit, deoarece fiecare atribut non-cheie trebuie să fie pe deplin dependent de PK. În această situație, informațiile despre studenți depind doar parțial de PK (StudentNo).

Pentru a remedia această problemă, trebuie să împărțim tabelul original în două după cum urmează:

• Tabelul 1: StudentNo, Course, Grade, DateCompleted
• Tabelul 2: StudentNo, StudentName, Address, City, Prov, PC

Axioma tranzitivității

Axioma tranzitivității spune că dacă X determină Y, iar Y determină Z, atunci X trebuie să determine și Z (vezi Figura 11.3).

Dacă X → Y și Y → Z, atunci X → Z

Figura 11.3. Ecuația pentru axioma tranzitivității.

Tabelul de mai jos conține informații care nu au legătură directă cu studentul; de exemplu, ProgramID și ProgramName ar trebui să aibă un tabel propriu. ProgramName nu depinde de StudentNo; depinde de ProgramID.

StudentNo -> StudentName, Address, City, Prov, PC, ProgramID, ProgramName

Această situație nu este de dorit, deoarece un atribut non-cheie (ProgramName) depinde de un alt atribut non-cheie (ProgramID).

Pentru a remedia această problemă, trebuie să împărțim acest tabel în două: unul pentru a conține informații despre student și celălalt pentru a deține informații despre program.

• Tabelul 1: StudentNo -> StudentName, Address, City, Prov, PC, ProgramID
• Tabelul 2: ProgramID -> ProgramName

Cu toate acestea, trebuie totuși să lăsăm un FK în tabelul studenților, astfel încât să putem identifica în ce program este înscris studentul.

Combinarea

Această regulă sugerează că, dacă două tabele sunt separate, iar PK este același, vă recomandăm să le puneți împreună. Se afirmă că dacă X determină Y și X determină Z atunci X trebuie să determine și Y și Z (a se vedea Figura 11.4).

Dacă X → Y și X → Z, atunci X → YZ

Figura 11.4. Ecuație pentru regula combinării

De exemplu, dacă:

• SIN -> EmpName
• SIN -> SpouseName

Poate doriți să combinați aceste două tabele într-unul singur, după cum urmează:

SIN -> EmpName, SpouseName

Unii administratori de baze de date (DBA) ar putea alege să păstreze aceste tabele separate din câteva motive. În primul rând, fiecare tabel descrie o entitate diferită, astfel încât entitățile ar trebui ținute separat. În al doilea rând, dacă SpouseName trebuie lăsat NULL de cele mai multe ori, nu este necesar să îl includeți în același tabel cu EmpName.

Descompunerea

Descompunerea este inversul regulii combinării. Dacă aveți un tabel care pare să conțină două entități determinate de același PK, vă recomandăm să le împărțiți în două tabele. Această regulă afirmă că, dacă X determină Y și Z, atunci X determină Y și X determină Z separat (vezi Figura 11.5).

Dacă X → YZ, atunci X → Y și X → Z

Figura 11.5. Ecuația pentru regula descompunerii.

Diagrama dependenței

O diagramă a dependenței, prezentată în Figura 11.6, ilustrează diferitele dependențe care ar putea exista într-un tabel non-normalizat. Un tabel non-normalizat este unul care conține redundanță de date.

Figura 11.6. Diagrama dependenței.

Următoarele dependențe sunt identificate în acest tabel:

• ProjectNo și EmpNo, combinate, sunt PK.
• Dependențe parțiale:
  • ProjectNo -> ProjectName
  • EmpNo -> EmpName, DeptNo,
  • ProjectNo, EmpNo -> HrsWork
• Dependență tranzitivă:
  • DeptNo -> DeptName

Termeni cheie

• axiomele lui Armstrong: un set de reguli de inferență utilizate pentru a deduce toate dependențele funcționale ale unei baze de date relaționale
• DBA: administrator de baze de date
• descompunere: o regulă care sugerează dacă aveți un tabel care pare să conțină două entități care sunt determinate de același PK, luați în considerare împărțirea lor în două tabele
• dependent: partea dreaptă a diagramei funcționale de dependență
• determinant: partea stângă a diagramei funcționale de dependență
• dependență funcțională (FD): o relație între două atribute, de obicei între PK și alte atribute non-cheie dintr-un tabel
• tabel non-normalizat: un tabel care conține redundanță de date
• combinare: o regulă care sugerează că, dacă două tabele sunt separate, iar PK este același, luați în considerare asamblarea lor

Sursa: Adrienne Watt, Database Design – 2nd Edition. Descărcare gratuită de la B.C. Open Textbook Collection. © 2014 Adrienne Watt and Nelson Eng. Licența (inclusiv imagini) CC BY 4.0. Traducere Nicolae Sfetcu

© 2021 MultiMedia Publishing, Baze de date, Volumul 1