What normal forms are these two relations in

database-designnormalizationrelational-theory

I have a set of relations {A, X, Y, Z}:

Given that the functional dependencies: AX→Y, AX→Z, Y→A, Z→X, I would think that this relation would be in the normal form 1NF, because there is a partial dependency for the composite key, YZ; Y determines A and Z determines X. However, I ran across this example on a university website claiming the relationship was in 3NF. Am I wrong about this relation being in 1NF?

On a similar note, given the same relation but with functional dependencies: A→XY, Y→AZ, would this be in 3NF or BCNF, I do not see any reason why this would not be in BCNF, but I have seen a similar example where there was a further decomposition, that was also BCNF. So is the decomposition wasteful because the original relation with given dependencies was already in BCNF?

Best Answer

The relation is actually in 3NF (so that it is also in 1NF and 2NF). The reason is that each attribute of the relation is prime, that is, it belongs to a (candidate) key (the are four keys in this relation: (A X), (A Z), (X Y), (Y Z)).

The definition of the 2NF (which has only an historical interest), is the following (Database System Concepts, 6th edition, Korth, Silberschatz, Sudharshan):

A functional dependency X → Y is called a partial dependency if there is a proper subset Z of X such that Z → Y . We say that Y is partially dependent on X. A relation schema R is in second normal form (2NF) if each attribute A in R meets one of the following criteria:

• It appears in a candidate key.

• It is not partially dependent on a candidate key.

so the relation respects this definition, since each attribute appear in a key.

While the definition of Third Normal Form is (same source as above):

A relation schema R is in third normal form with respect to a set F of functional dependencies if, for all functional dependencies in F⁺ of the form X → Y, where X ⊆ R and Y ⊆ R, at least one of the following holds:

• X → Y is a trivial functional dependency.

• X is a superkey for R.

• Each attribute A in Y − X is contained in a candidate key for R.

so the relations respects this definition too.

For your second question, the relation has two keys, A and Y, and it is already in BCNF as well as in 3NF.

Note that the analysis algorithm to decompose a relation in BCNF should return the original relation, since no dependency violates its definition (each determinant is a superkey).

Related Solutions

Simple scenario needs to go from Unnormalized Data to 3NF – Review Please

Yes, it's in 1NF.

You can't side-step the often hard work of determining all the candidate keys by hanging a number off the end of the table and saying, "There. I've got a primary key." One natural candidate key for this table is {Name, Bought from, Date bought}. Consider using "Time bought" instead of "Date bought".

Your definition of 2NF is wrong. Instead of

Second Normal Form: A relation that is in First Normal Form and every non-primary-key attribute is fully functionally dependent on the primary key.

you need something more like this.

Second Normal Form: a relation that is in First Normal Form, and every non-prime attribute is fully functionally dependent on every candidate key.

The term non-prime attribute doesn't mean quite what non-primary-key attribute means.

Your definition of 3NF is wrong, and it's wrong for the same reasons as your definition for 2NF was wrong.

Instead of this

Third Normal Form: A relation that is in First and Second Normal Form and in which no non-primary-key attribute is transitively dependent on the primary key.

you need something closer to this.

Third Normal Form: A relation that is in Second Normal Form and in which every non-prime attribute is nontransitively dependent on every candidate key. (There isn't a really good way to express all those negative in one sentence.)

Decomposition In Boyce-Codd Normal Form may lose relations

Your decomposition is not correct, since in R2 you still have dependencies that violates the BCNF, for instance UtilisateurID → Nom (UtilisateurID is not a key of that relation).

The problem is that your algorithm is not correct. When you find a dependency X → A that violates the BCNF, you should decompose a relation in two relations, the first with X⁺, not XA, and the second one with T – X⁺ + X. Then you should repeat the algorithm, if you find in one of the two decomposed relation some other dependency that violates the BCNF.

So, in your example, a correct decomposition is:

R2 < (AdresseEmail ServeurMail UtilisateurID) ,
{ AdresseEmail → UtilisateurID
AdresseEmail → ServeurMail } >

R3 < (Nom Prenom UtilisateurID) ,
{ UtilisateurID → Nom
UtilisateurID → Prenom } >

R4 < (Login Passwd ServeurMail UtilisateurID) ,
{ ServeurMail UtilisateurID → Login
ServeurMail UtilisateurID → Passwd } >

Note that this decomposition preserves the functional dependencies.

Addition

How the decomposition is obtained? Starting from the original relation:

R(AdresseEmail Login Nom Passwd Prenom ServeurMail UtilisateurID)

let's consider a dependency that does violates the BCNF, for instance:

ServeurMail UtilisateurID → Login

the closure of ServeurMail UtilisateurID is (Login Nom Passwd Prenom ServeurMail UtilisateurID, so we decompone initially in two relations:

R1(Login Nom Passwd Prenom ServeurMail UtilisateurID) 
R2(AdresseEmail ServeurMail UtilisateurID)

R1 is not in BCNF, since the key is ServeurMail UtilisateurID, so for instance the dependency UtilisateurID → Nom violates the normal form. Applying the algorithm, R1 is decomposed in:

R3(Nom Prenom UtilisateurID)
R4(Login Passwd ServeurMail UtilisateurID)

Both relations are in BCNF, and the final decomposition is given by R2, R3, and R4.

Finally, note that sometimes the algorithm can produce different solutions, depending on the functional dependency chosen at each step.

Best Answer

Related Solutions

Simple scenario needs to go from Unnormalized Data to 3NF – Review Please

Decomposition In Boyce-Codd Normal Form may lose relations

Related Question