CODEWITHSUNDEEP
database-normalizationfunctional-dependencies3nfbcnfcanonical-form
Paludan
Paludan

Reputation: 622

What is the correct approach when decomposing dependencies

I am struggling with Carnonical Cover, Dependency Preservation and Lossless Decomposition.

Are the approach and thoughts here correct?

R(ABCDEFG)

Provided is the following set of dependencies after a canonical cover has been made. I did not do the canonical cover myself but the assignment said I had to assume it had been done.

Fc:
  A -> C
  E -> A
  C -> ABF
  F -> CDG

A+ = ABCDFG
E+ = ABCDEFG
C+ = ABCDFG
F+ = ABCDFG

E = Candidate Key.

This list of functional dependencies is in 2NF since there are no partial dependencies. It is however not in 3NF since there are transitive dependencies.

However decomposing into the following 4 relations will result in it being not only in 3NF but also BCNF

R1 = {E,A}
  E -> A
R2 = {A, C}
  A -> C
R3 = {CABF} 
  C -> ABF
R4 = {FCDG}
  F -> CDG

I use A in R1 as a foreign key to R2 and C in R2 as a foreign key to R3 etc.

There are no transitive dependencies and since all left hand sides are candidate keys in their respective relations it is in BCNF.

Is also lossless and dependency preserving?

Upvotes: 1

Views: 1421

Answers (1)

Renzo
Renzo

Reputation: 27454

What is decomposed

In the title you say:

What is the correct approach when decomposing dependencies

but one does not decompose dependencies, but relation schemas. So, in this case, here there is a relation schema R(ABCDEFG) with a set of functional dependencies and one must decompose that schema.

What is a decomposition

A decomposition produces a set of relation schemas with the following properties: a) every attribute of the original schema is present in some (possibly more than one) subschema; b) no other attributes are present. Moreover, a decomposition is redundant when a relation subschema is contained in another. In your case, this is true for R2, which is contained in R3: there is no need to have both relations, since it would imply unuseful data redundancy.

What is a good decomposition

To be really useful, a decomposition should satisfy two important properties: preserve functional dependencies and preserve data (lossless decomposition). But another property characterizes a good decomposition: it should be as small as possible: there is no point in decomposing a schema in too many subschemas, since this would produce a non natural and complex database.

Actually your decomposition is lossless and preserves the dependencies.

How to decompose

The final objective of all this stuff is to produce a decomposisition (lossless and dependency preserving) in which the subschemas are in BCNF or 3NF. The simple solution of decomposing by using the attributes of the functional dependencies is not, however, a good solution. For this, there are algorithms, described in textbooks, that produces decompositions either for BCNF or for 3NF (the so-called “analysis” algorithm for BCNF, and “synthesis” algorithm for 3NF), trying to produce not too many subschemas. For instance, the “analysis” algorithm in this case produce the following decomposition in BCNF, with only two subschemas:

R1 < (A B C D F G) ,
    { F → C
      F → D
      F → G
      C → A
      C → B
      C → F
      A → C } >

R2 < (A E) ,
    { E → A } >

This decomposition is lossless and preserves the dependencies (which is not always true for the analysis algorithm).

Upvotes: 2

Related Questions