Lossless Dołącz i rozkładu Od Zależności funkcjonalne

Question

Załóżmy relację R(K, L, M, N, P) i funkcjonalne zależności, które posiadają na R są:

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

Załóżmy, że rozkłada się go na 3 stosunkach następująco:

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

Jak czy możemy powiedzieć, czy ta dekompozycja jest bezstratna? I used this example

R1 ∩ R2 = {l, M}, R2 ∩ R3 = {M} R1 ∩ R3 = {k, m} używamy zależności funkcyjnych, a nie jest bezstratna moim zdaniem, ale nieco nieco zmieszany.

Answer 1

Pomaga jeśli demystify pojęcie rozkładu bezstratnej trochę: to tak naprawdę oznacza, że ​​łączenie R1, R2 i R3 powinna przynieść oryginalną R.

Wiesz the chase testu a.k.a „metodzie tableau”? Jest to fajny algorytm do testowania bezstratności. Jest łatwy do zaprogramowania i jest używany w przemyśle, gdy rozważa spójność danych.

Zaczynamy od tak zwanego "tableau of the decomposition", macierzy n * m, gdzie n jest liczbą relacji, a m jest liczbą atrybutów. Dla każdego pola, jeśli relacja n zawiera atrybut m, zapisujemy nazwę atrybutu; w przeciwnym razie wpisujemy nazwę atrybutu indeksowaną z numerem relacji.

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

Teraz tabela będzie "ścigana" (stąd nazwa algorytmu). Zauważamy, że pierwszy i drugi wiersz zgadzają się na ich wartości L i M. Zależność LM-> N oznacza, że ​​ich wartości N również powinny się zgadzać. Zmieńmy pierwszy wiersz n1 na drugi rząd N:

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

Teraz pierwszy i trzeci rząd zgadzają się na swoje wartości K i M. Mamy zależność KM-> P, więc powinni także uzgodnić ich wartość P.

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

Skończyliśmy! Gdy tylko któryś z wierszy ma wszystkie właściwe atrybuty (tak jak robi to pierwszy wiersz), algorytm kończy się i dowodzi, że rozkład był rzeczywiście bezstratny.

Należy zwrócić uwagę, jak powtarzające się aplikacje zależności reprezentują łączenie relacji na udostępnianych kluczach. Więc to, co zrobiliśmy, to połączenie R1 i R2 na L i M (sieciowanie nas (K, L M, N)), a następnie dołączenie do wyniku z R3 na K i M (który daje R).

Answer 2

Algorytm wspomniano powyżej, jest prawidłowe, ale obliczenie jest źle
jako R1, zawiera K, L, M, K, L, Nie, P
więc tu w 2 etapie lm -> N zostaną wykorzystane
i będzie make N1 do N w R1
, a następnie MP -> K zostanie użyty, a R1 będzie zawierał wszystkie atrybuty R
, więc algorytm się zakończy.