The mistake is in your understanding of transitive dependency. From wikipedia: Transitive dependency
In mathematics, a transitive dependency is a functional dependency which holds by virtue of transitivity. A transitive dependency can occur only in a relation that has three or more attributes. Let A, B, and C designate three distinct attributes (or distinct collections of attributes) in the relation. Suppose all three of the following conditions hold:
1. A → B
2. It is not the case that B → A
3. B → C
Then the functional dependency A → C (which follows from 1 and 3 by the axiom of transitivity) is a transitive dependency.
In your case though, (2) does not hold:
1. U → T -- correct
2. It is not the case that T → U -- wrong
3. T → V -- correct
Therefore {V}
is NOT transitively dependent on {U}
.
The goal of 3NF (and BCNF) is to avoid situations when a set of attributes is functionally determined by something that is not a key (or, more formally, a superkey), which may lead to anomalies and redundancy.
Keeping that in mind, we can describe certain functional dependencies as either "bad" (if they prevent the relation from being in 3NF) or "good" (if they do not).
So your solution is wrong, because "your" R1 has the E->D
dependency and E is not R1's key. Determining a key for a relation is another topic which, I suppose, is beyond the scope of the task you need to accomplish (we are told that ABC is a key). But if you are interested, you can look the method up using "attribute closure" keywords.
Anyway, the E->D
dependency is "bad". But that is not the only problem. Another one is that your decomposition is not a "lossless-join" one. In other words, if we have some real world data, split the relation according to your proposition and try to join R0 and R1 back, the data will be corrupted. Data corruption is not what normalization is designed for.
We have to solve 2 problems:
- Decide which dependencies are "bad" (the definition of normal forms is the answer to this)
- Decide how to split relations to prevent data corruption (we have Heath's theorem to help us)
Getting back to your problem, finally.
In R, neither B, nor E is the key. So both B->E
and E->D
are "bad", and we need to take measures. On the contrary ABC->EF
is "good", because ABC is a key.
Currently R is in 1NF, because B is a part of a key and functionally determines E, which is not a part of a key. This kind of situation is unacceptable in 2NF.
E->D
dependency is not that "bad", because E is not a part of a key.
Another thing to mention at this point is that a set of dependencies {B->E, E->D}
implies the dependency B->ED
(according to so called Armstrong axiom of transitivity).
So we decide to split using B->ED
dependency as "the worst" one. That's the way we do this, according to Heath:
R = ABCDEF
R0 = BED (B->E, E->D, B is a key)
R1 = ABCF (ABC->F, ABC is a key)
Now we have R1, which is in 3NF and R0, which is in 2NF (it has a transitive dependency B->E->D
, which is unacceptable in 3NF).
We need to split R0 and to do so we have to choose a "victim" dependency among B->E
and E->D
. As we see, B->E
is now a "good" one (B is a key) and E->D
is still "bad".
Our split:
R0 = BED
R2 = BE (B->E, B is a key)
R3 = ED (E->D, E is a key)
R1, R2 and R3 are the final decomposition.
Best Answer
The problem is in your application of step 2:
This means that you must add a new relation (but only one!) that contains one of the original candidate keys (any one!).
So correct decompositions in 3NF are
{R1, R3, R4}
or{R1, R3, R5}
. You can chose one of the two as result of the question (and this means yes, the synthesis algorithm can produce different decompositions).Finally we can note that this step is used to guarantee the lossless-join property (while the dependency preservation is guaranteed by the previous steps, since all the decompositions are considered). In fact a theorem exists that says that if a decomposition preserves the dependencies and has at least a relation which contain one of the original candidate keys, than this decomposition preserves the data (i.e. is a lossless-join decomposition).