CODEWITHSUNDEEP
database-designrelational-databasedatabase-normalizationfunctional-dependenciesbcnf
Arnav Kaushik
Arnav Kaushik

Reputation: 79

Decompose the following relation into BCNF

Given a Relation R with attributes A, B, C, D, E and set of Functional Dependencies A->B, BC->E, ED->A. Decompose it into high normal form.

Upvotes: 0

Views: 3124

Answers (1)

Sumeet
Sumeet

Reputation: 8292

From the definition of candidate key:

In the relational model of databases, a candidate key of a relation is a minimal superkey for that relation; that is, a set of attributes such that:

  1. The relation does not have two distinct tuples (i.e. rows or records in common database language) with the same values for these attributes (which means that the set of attributes is a superkey)
  2. There is no proper subset of these attributes for which (1) holds (which means that the set is minimal).

Given the F.D's only C and D come on the left side, which means every key must possess C and D.

closure(CD) is not equal to all attributes, however, from the F.D's we can clearly see that:

closure(CDA) = closure(CDB) = closure(CDE) = set of all attributes, this means that all three CDA, CDB and CDE are candidate keys.

Now let us follow the BCNF decomposition algorithm given in this stanford lecture.

Given a schema R.

  1. Compute keys for R.
  2. Repeat until all relations are in BCNF.
    • Pick any R' having a F.D A --> B that violates BCNF.
    • Decompose R' into R1(A,B) and R2(A,Rest of attributes).
    • Compute F.D's for R1 and R2.
    • Compute keys for R1 and R2.

A-->B violates BCNF as A is not a key, so we decompose R into

R1(A,C,D,E) and R2(A,B).

R2 is in BCNF now, but R1 is not due to F.D ED-->A, as ED is not a key. So we decompose R1 further as:

R3(C,D,E) and R4(A,E,D), now clearly both R3 an R4 are in BCNF.

Upvotes: 1

Related Questions