3

I came across this example that I can't normalize to 2NF, so I was wondering if relations that could not be normalized existed.

Here is the example relation:

  • R(A, B, C, D, E)

with the functional dependencies:

  • {A, B} → D
  • C → B
  • E → A

or, diagrammatically:

enter image description here

The primary key of that relation is {C, E}, and if we suppose that all the attributes are atomic, then R is in first normal form (1NF).

But how can we normalize it to 2NF?

Since A and B are not fully dependent on {C, E}, I feel like they should be set aside in two different relations, but then D isn't dependent on anything in R. What am I missing?

  • There are no formal algorithms described in textbooks or elsewhere to normalize in Second Normal Form, only for Third Normal Form and Boyce-Codd Normal Form. How are you supposed to normalize in Second Normal Form? – Renzo May 20 at 16:41
  • 1
    There are no formal algorithm? I guess this answer my question, then. I don't understand your question ("How are you supposed to …"): I have no idea what the second form of that relation should be, hence my question! – Clément May 20 at 16:43
  • You can split this relation into (C,E) and (A,B,D). Both relations are in 3NF - no partial and no transitive dependecies. – Kondybas May 20 at 19:14
  • @Kondybas This seems destructive to me: we are losing the dependencies between C and B, and between E and A with your proposition. Also, this is a "big step" to the 3rd NF, which I read as "No, this relation cannot be written in 2NF". – Clément May 20 at 20:01
  • Those dependencies are not lost. (ABD) can be functionally projected on (CE). Saying practically we split the initial table into two ones that can be joined any time we need to restore relations C->B, E->A and {CE}->{AB}->D – Kondybas May 20 at 20:12
2

Note that the normalization of a relation is an operation that in general is performed to eliminate or reduce anomalies like redundancy, while in general preserving the meaning of the data, and more formally, preserving two essential properties: the dependencies holding on the original data, and the data itself (through the concept of lossless decomposition).

So, the normalization decomposes a relation in a set of relations that are in a so-called Normal Form, and the normal forms used in a decomposition are usually the Boyce-Codd Normal Form, the Third Normal Form, or even higher level ones. For these decompositions, there are formal algorithms that can be used, and that guarantees a set of properties, like being lossless and preserving the dependency (not in all cases, for instance it is known that certain relations cannot be decomposed in BCNF without the loss of some dependency).

Note that the second normal form is not used in practice, has only an historical interest, and there are no published formal algorithm since it is more weaker that the 3NF and the BCNF.

All these topics are discussed in detail in any good book on databases, and you can find even some of them free on line.

In your example, assuming that the dependencies that you shown are a cover of all the dependencies of the relation, the decomposition of R in the the relations R1(CE) and R2(ABD) does not preserves the functional dependencies (E->A and C->B are lost), and is not lossless.

A decomposition which preserves data and dependencies, and that can be found both with the synthesis algorithm to produce the 3NF, and with the analysis algorithm to produce the BCNF is the following (each relation schema is followed by a cover of the dependencies holding in it):

R1(A B D) {AB -> D}

R2(B C) {C -> B}

R3(A E) {E -> A}

R4(C E) {}

where each schema is in BCNF.

Of course, since a schema in BCNF is also in 2NF, the previous decomposition also respects the Second Normal Form. This answers to your original question: since each relation can be normalized at least in 3NF without loss of data or dependencies, each relation can be normalized at least in 2NF.

0

Here is the normalization where both relations are in 3NF.

enter image description here

  • 2
    This decomposition is not lossless, and does not preserve the dependencies. You cannot maintain dependencies between different relations. – Renzo May 21 at 7:50
  • @Renzo But why? If C->A and E->B then we can join both relations on functional dependencies. They are still persist. – Kondybas May 21 at 8:12
  • If C->A in the original relation, it means that every time there is a certain value for C, the same value for A must be present. In your decomposition, you can insert different tuples with the same value of C in the first relation, and different tuples with a different value of A in the second relation. When you join the two relations, you will have the same value for C with different values of A, so in fact violating the dependency C -> A. – Renzo May 21 at 8:37
  • Note, moreover, that the decomposition is not lossless: if you project the original relation R on CE and on ABD, and then join the two relations obtained, you will produce not R, but a relation with more tuples than R. This is beacause the relations do not have common attributes, and joining them is equivalent to perform a cross product. So, there is a loss of information, and that decomposition cannot be practically used. – Renzo May 21 at 8:40
  • @Renzo Oh, I see your answer with additional (EA) and (CD) storing functional dependencies. I've stopped with arrows. – Kondybas May 21 at 10:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.