Lossless Join und Zersetzung von Funktionale Abhängigkeiten

Question

Angenommen, die Beziehung R(K, L, M, N, P), und die funktionalen Abhängigkeiten, die auf R halten sind:

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

Angenommen, wir es in drei Beziehungen zersetzen wie folgt:

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

Wie Können wir sagen, ob diese Zersetzung verlustfrei ist? I used this example

R1 ∩ R2 = {L, M}, R2 ∩ R3 = {M}, R1 ∩ R3 = {K, M} wir funktionale Abhängigkeiten verwenden, und dies ist meiner Meinung nach nicht verlustlos, aber ein wenig bisschen verwirrt.

Answer 1

Es hilft, wenn wir das Konzept der lossless Zersetzung etwas entmystifizieren: es wirklich bedeutet nur, dass R1, R2 und R3 verbinden sollte die ursprüngliche R. ergeben

Kennen Sie the chase Test a.k.a „Tableau-Methode“? Es ist ein cooler Algorithmus, um auf Verlustfreiheit zu testen. Es ist einfach zu programmieren, und es wird tatsächlich in der Industrie verwendet, wenn es um Datenkonsistenz geht.

Wir beginnen mit dem sogenannten "Tableau der Zerlegung", einer n * m Matrix, wobei n die Anzahl der Relationen und m die Anzahl der Attribute ist. Für jedes Feld, wenn die Beziehung n das Attribut m enthält, schreiben wir den Attributnamen; Andernfalls schreiben wir den Attributnamen, der mit der Nummer der Beziehung indiziert ist.

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

Jetzt wird das Tableau "gejagt" (daher der Name des Algorithmus). Wir bemerken, dass die erste und die zweite Zeile über ihre L- und M-Werte übereinstimmen. Die Abhängigkeit LM-> N bedeutet, dass ihre N-Werte übereinstimmen sollten. Lassen Sie sich die erste Zeile der n1 in die zweiten Reihe der N ändern:

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

Nun ist die erste und dritte Reihe einigen sich auf ihren K und M-Werten. Wir haben eine KM-> P-Abhängigkeit, daher sollten sie sich auch auf ihren P-Wert einigen.

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

Und wir sind fertig! Sobald irgendeine der Zeilen alle richtigen Attribute aufweist (wie die erste Zeile), endet der Algorithmus und beweist, dass die Zerlegung tatsächlich verlustfrei war.

Beachten Sie, wie die wiederholten Anwendungen der Abhängigkeiten das Verbinden der Beziehungen auf den Schlüsseln darstellen, die sie teilen. Also haben wir R1 und R2 auf L und M (Netting (K, L M, N)) verbunden, dann verbinden wir das Ergebnis mit R3 auf K und M (das ergibt R).

Answer 2

Der Algorithmus, der oben erwähnt ist richtig, aber die Berechnung ist falsch
als R1 K enthält, L, M nicht K, L, P
hier so in dem 2. Schritt LM -> N verwendet wird
und es wird Machen Sie N1 zu N in R1 und dann wird MP -> K verwendet und R1 wird alle Attribute von R
enthalten, damit der Algorithmus beendet wird.