Dependențe Funcționale

1.1. Introducere

Când descriem un univers real sau conceptual printr-un model relaţional ne confruntăm cu următoarea problemă:

Care este mulţimea de relaţii care va fi o reprezentare fidelă a schemei conceptuale (a obiectivelor şi a legăturilor) şi deci a universului real fară ca să riscăm problemele de cosistenţă (la operaţiile de actualizare sau operaţiile de descompunere). Plecând de la regulile semantice care traduc restricţiile universului modelat, proiectantul trebuie să definească “dependenţele “ şi să le introducă în definiţia schemei de relaţie. Proprietăţile dependenţelor sunt proprietăţi pentru schema de relaţie (intensiuni) a bazei de date şi nu pentru o extensie oarecare, adică aceste dependenţe constituie invarianţi care trebuie să fie satisfăcute de toate extensiile legale de relaţii ale schemei.

Crearea unei baze de date are două obiective esenţiale : să reducă excedentul de date şi să mărească siguranţa în exploatare. Orice cunoştinţă apriori despre diferite tipuri de restricţii referitoare la totalitatea datelor poate fi de mare folos pentru atingerea acestor obiective.

Un procedeu de formalizare a unor cunoştinţe despre date este dat de dependenţe. În acest paragraf vom considera numai un singur tip de dependenţe şi anume dependenţa funcţională, pe care o vom numi F- dependenţă. Dependenţa funcţională este o generalizare a noţiunii de cheie.

Exemplul 1.1. Fie relaţia grafic( PILOT CURSA DATA ORA DECOLARE ) care arată ce pilot participă la o cursa dată, la o anumită dată şi ora la care are loc decolarea (fig. 1). Se au în vedere următoarele restricţii:

- o cursa are aceeaşi ora de decolare ( de exemplu cursa 75 decolează întotdeauna la ora

10:15 ).

un pilot nu se poate afla decât într o singură cursa la o anumită ora de decolare.

Aceste restricţii sunt exemple de F- dependenţe. Intuitiv vorbind, o F- dependenţă are loc când valorile tuplurilor după o mulţime de atribute definesc în mod unic valorile unei alte mulţimi de atribute. Astfel, restricţiile arătate mai sus pot fi astfel formulate:

ORA DECOLARE depinde funcţional de CURSA,

- CURSA depinde funcţional de {PILOT DATA ORA DECOLARE },

- PILOT depinde funcţional de {CURSA DATA }.

În mod obişnuit, ordinea acestor secvenţe se poate schimba şi spunem că,

{ CURSA DATA} defineşte în mod funcţional pe { PILOT }, sau simbolic

{CURSA DATA} { PILOT }.

Vom da o definiţie strictă a dependenţei funcţionale folosind operatorii relaţionali.

grafic(PILOT CURSA DATA ORA DECOLARE )

Dragoş 75 9 03 10:15

Dragoş 80 10 03 13:25

Mihai 80 8 03 13:25

Mihai 80 12 03 18:50

Mihai 75 11 03 10:15

Mircea 75 13 03 10:15

Mircea 80 12 03 13:25

Costin 85 9 03 5:50

Costin 85 13 03 5:50

Costin 90 5 03 13:25

Figura 1. Relaţia grafic

Definiţia 1.1. Fie relaţia r de schemă R, X şi Y submulţimi ale lui R. Relaţia r satisface dependenţa funcţională X Y dacă Y( X=x(r)) are nu mai mult de o singură ocurenţă pentru fiecare X valoare x.

În F- dependenţa X Y submulţimea X se numeşte partea stângă iar Y se numeşte partea dreaptă.

Un procedeu de a verifica că o relatie satisface X Y este dat de următoarea proprietate :

Dacă pentu orice două tupluri t1,t2 r, cu t1(X) = t2(X) rezultă t1(Y)=t2(Y) atunci r satisface X Y.

Această caracterizare stă la baza procedurii satisfie dată mai jos. Presupunem că relaţia r este ordonată după valorile lui X, apoi după ale lui Y.

0 procedure satisfie(X,Y;v)

1 vtrue

2 Input (t)

3 While not eof (r)

3.1 Input { t'}

3.2 If t(X) = t'(X)