Lossless Partecipa e decomposizione Da dipendenze funzionali

Question

Supponiamo che la relazione R(K, L, M, N, P), e le dipendenze funzionali che tengono il R sono:

- L -> P 
- MP -> K 
- KM -> P 
- LM -> N 

Supponiamo decompongono in 3 rapporti nel modo seguente:

- R1(K, L, M) 
- R2(L, M, N) 
- R3(K, M, P) 

Come possiamo dire se questa decomposizione è senza perdite? I used this example

R1 ∩ R2 = {L, M}, R2 ∩ R3 = {M}, R1 ∩ R3 = {K, M} usiamo dipendenze funzionali, e questo non è lossless, a mio parere, ma un po ' un po 'confuso.

Answer 1

Aiuta se ci demistificare il concetto di decomposizione senza perdita di dati un po ': in realtà significa solo che l'adesione R1, R2 e R3 dovrebbe produrre l'originale R.

Sai the chase prova a.k.a "il metodo Tableau"? È un ottimo algoritmo per testare l'assenza di perdite. È facile da programmare ed è effettivamente utilizzato nel settore quando si ragiona sulla coerenza dei dati.

Iniziamo con il cosiddetto "tableau della scomposizione", una matrice n * m dove n è il numero di relazioni ed m è il numero di attributi. Per ogni campo, se la relazione n contiene l'attributo m, scriviamo il nome dell'attributo; altrimenti scriviamo il nome attributo con il numero della relazione.

| K L M N P 
----------------------- 
1 | K L M n1 p1 
2 | k2 L M N p2 
3 | K l3 M n3 P 

Ora il tableau sarà "inseguito" (da cui il nome dell'algoritmo). Notiamo che la prima e la seconda riga concordano sui loro valori L e M. La dipendenza LM-> N implica che anche i loro valori N dovrebbero essere d'accordo. Cambiamo n1 del primo fila in N del secondo fila:

| K L M N P 
----------------------- 
1 | K L M N p1 
2 | k2 L M N p2 
3 | K l3 M n3 P 

Ora la prima e la terza fila sono d'accordo sui loro valori di K e M. Abbiamo una dipendenza KM-> P, quindi dovrebbero essere d'accordo anche sul loro valore di P.

| K L M N P 
----------------------- 
1 | K L M N P 
2 | k2 L M N p2 
3 | K l3 M n3 P 

E abbiamo finito! Non appena una delle righe ha tutti gli attributi corretti (come fa la prima riga), l'algoritmo termina e dimostra che la decomposizione era effettivamente senza perdite.

Nota come le applicazioni ripetute delle dipendenze rappresentano unire le relazioni sulle chiavi che condividono. Quindi quello che abbiamo fatto è stato unire R1 e R2 su L e M (mettendoci in contatto con noi (K, L M, N)), quindi unire il risultato con R3 su K e M (che produce R).

Answer 2

L'algoritmo di cui sopra è corretto, ma il calcolo è sbagliato
come R1 contiene K, L, M non K, L, P
ecco 2º passo LM - sarà usato> N
e sarà da N1 a N in R1
e poi MP -> K verrà utilizzato e R1 conterrà tutti gli attributi di R
in modo che l'algoritmo terminerà.