OneCompiler

FDS

214

R(A,B,C,D) and FDs {AB -> C, C -> D, D -> A}.
(1) List all nontrivial FDs that can be inferred from the given FDs.
(2) Find all candidate keys.
(3) Find all BCNF violations.
(4) Decompose R into relations in BCNF.
(5) What FDs are not preserved by BCNF.
ANS
Given FDs: {AB -> C, C -> D, D -> A}

(1) List all nontrivial FDs that can be inferred from the given FDs:

  • Reflexivity: If A -> B, then also A -> A, B -> B.
  • Augmentation: If A -> B, then also AC -> BC for any C.
  • Transitivity: If A -> B and B -> C, then A -> C.

Using these axioms, we can infer:

  • AB -> D (using AB -> C and C -> D)
  • AC -> D (using AB -> C, C -> D, and Augmentation)

(2) Find all candidate keys:

A candidate key is a minimal superkey, meaning no proper subset is a superkey. In this case, we can try to find the closure of different combinations of attributes.

  • AB is a superkey since AB -> C, and C -> D and D -> A (closure is ABCD).
  • AC is a superkey since AC -> D and D -> A (closure is ACDB).
  • BC is not a superkey as it does not determine A.
  • BD is not a superkey as it does not determine C.
  • CD is not a superkey as it does not determine A.

Therefore, AB and AC are candidate keys.

(3) Find all BCNF violations:

A relation is in BCNF if, for every non-trivial FD X -> Y, X is a superkey. If X is not a superkey, it violates BCNF.

  • The given FDs are AB -> C, C -> D, D -> A.
  • AB -> C violates BCNF since AB is a superkey, but C is not a prime attribute (not part of any candidate key).

(4) Decompose R into relations in BCNF:

To decompose R into BCNF, we can use the FD AB -> C, which violates BCNF. We create two relations:

  • R1(AB, C)
  • R2(C, D, A)

Now, both R1 and R2 are in BCNF.

(5) What FDs are not preserved by BCNF:

BCNF may not preserve some FDs. In this case, the FD D -> A is not preserved because D is not a superkey in either R1 or R2.

  • (1) Nontrivial FDs: AB -> D, AC -> D.
  • (2) Candidate keys: AB, AC.
  • (3) BCNF violation: AB -> C.
  • (4) Decomposed relations: R1(AB, C), R2(C, D, A).
  • (5) FDs not preserved by BCNF: D -> A.