2NF: Remove Partial Dependencies
R = {A, B, C, D, E, F, G, H, I, J}
includes partial dependencies.
D and E depend only on A, F depends only on B, G, H, I and J don't depend on the key (directly) at all.
R0 = {A, B, C}
R1 = {A, D, E, I, J}
R2 = {B, F, G, H}
R0, R1, and R2 contain no partial dependencies (or repeating groups) so they are 2NF. However R1 and R2 are still an issue, because they contain transitive dependencies.
3NF: Remove Transitive Dependencies
I and J depend on D, not on the key of R1. Therefore you need to further normalize R1 as follows:
R1 = {A, D, E, I, J}
R1a = {A, D, E}
R1b = {D, I, J}
Similarly, G and H depend only on F so R2 must be decomposed as follows:
R2 = {B, F, G, H}
R2a = {B, F}
R2b = {F, G, H}
Now all of your remaining relations (R0, R1a, R1b, R2a, R2b) are devoid of repeating groups, partial dependencies and transitive dependencies. That means your relations are in 3NF.
When you are looking at an relation that hasn't been normalized and a series of dependencies, you can often normalize by inspection just by recognizing what your primary keys are going to be. Any attribute or combination of attributes that functionally determine other attributes are going to end up as primary keys. Once you've got your primary keys defined, you just need to figure out which non-key attributes go with each key. This is obvious from the statement of what your functional dependencies are.
But am I right, that every relation has at least one functional dependency?
Relation can has no functional dependencies, if it has no non-key attributes, i.e. it is full-keyed relation.
Best Answer
Here is the proof.
(⇐) Suppose T1 ∩ T2 → T1 ∈ F+. Let r a valid instance of R⟨T, F⟩, and s = π T1(r ) ⨝ π T2(r ). If t ∈ s, then we need to show that t ∈ r. By definition of s, we have two tuples u and v in r such that u [T1] = t [T1], v [T2] = t [T2] and u [T1 ∩ T2] = v [T1 ∩ T2] = t [T1 ∩ T2]. Since T1 ∩ T2 → T1 ∈ F+, then u [T1] = v [T1] and so t = v.
The case T1 ∩ T2 → T2 ∈ F+ can be proved in the same way.
(⇒) Suppose that, for each valid instance r of R⟨T,F⟩, r = π T1(r ) ⨝ π T2(r ); we need to show that T1 ∩ T2 → T1 ∈ F+ or T1 ∩ T2 → T2 ∈ F+.
Using reductio ad absurdum, we suppose that none of the two functional dependencies is implied by F. Let W = (T1 ∩ T2)+, Y1 = T1 − W and Y2 = T2 − W. Y1 and Y2 are not empty by hypothesis, and W, Y1 and Y2 are a partition of T. For each Ai ∈ T, 1 ≤?? i ≤?? k, we consider two values ai, ai′ ∈ dom(Ai), such that ai ≠ ai′. Let’s build a relation r with attributes WY1Y2 constituted by the two tuples:
e1[Ai] = ai, 1 ≤? i ≤?? k ?
e2[Ai] = ai if Ai ∈ W; ai′ if Ai ∈ Y1Y2
r satisfies each dependency V → Z ∈ F. In fact, if V ⊈ W, then e1[V] ≠ e2[V], and r obviously satisfies the dependency. If V ⊆ W, then (T1 ∩ T2) → V, so (T1 ∩ T2) → Z for transitivity, from which Z ⊆ W, and so e1[Z] = e2[Z], an this implies that r satifies the dependency. Moreover, since Y1 and Y2 are not empty, π T1 (r ) and π T2 (r ) contain two tuples and their natural join contains four tuples, more than those of r:
π T1 (r ) ⨝ π T2 (r )
contradicting the hypothesis.