3

Trying to follow the chase algorithm as I understand it,

  1. If two rows agree in the left side of a functional dependency (FD for brevity), make their right sides agree too.
  2. Always replace a subscripted symbol by the corresponding unsubscripted one, if possible.
  3. If we ever get an unsubscripted row, we know any tuple in the project-join is in the original (the join is lossless).
  4. Otherwise, the final tableau is a counter example

So I tried to perform the chase algorithm on an example schema. Given R (A, B, C, D, E) decomposed into relations {A, B, C}, {B, C, D}, {A, C, E} and FDs, A → D, CD → E and E → D

Beginning the chase test

+-----+-----+---+-----+-----+
| a   | b   | c | d   | e   |
+-----+-----+---+-----+-----+
| a   | b   | c | d_1 | e_1 |
+-----+-----+---+-----+-----+
| a_2 | b   | c | d   | e_2 |
+-----+-----+---+-----+-----+
| a   | b_3 | c | d_3 | e   |
+-----+-----+---+-----+-----+

And ending

+-----+-----+---+-----+-----+
| a   | b   | c | d   | e   |
+-----+-----+---+-----+-----+
| a   | b   | c | d_1 | e   |
+-----+-----+---+-----+-----+
| a_2 | b   | c | d   | e_2 |
+-----+-----+---+-----+-----+
| a   | b_3 | c | d_1 | e   |
+-----+-----+---+-----+-----+

So the final tableau is a counter example and this isn't lossless.

  • 2
    You are correct, the decomposition is not lossless. – Renzo Jul 13 '17 at 17:53
  • Seems that given FDs are not sufficient. – Kondybas Jul 13 '17 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.