3

I have a relation:

R4 = {{T,U,V}, {T → U, U → T, T → V}}

I know from looking at the answer key that this relation is in BCNF.

I'm going through the process of rigorously determining what normal form the relationship adheres to. It's clear to me why the relationship is in 1NF and 2NF, and if I assume it's in 3NF, BCNF follows easily.

However, the definition of 3NF states:

Every non-prime attribute is non-transitively dependent on every candidate key in the table.

But, as far as I can tell, both {T} and {U} are candidate keys of the table, and {V} is thus transitively dependent on {U}.

There is an alternate definition of 3NF available on wikipedia:

A 3NF definition that is equivalent to Codd's, but expressed differently, was given by Carlo Zaniolo in 1982. This definition states that a table is in 3NF if and only if, for each of its functional dependencies X → A, at least one of the following conditions holds:

  • X contains A (that is, X → A is trivial functional dependency)
  • X is a superkey
  • Every element of A-X, the set difference between A and X, is a prime attribute (i.e., each column in A-X is contained in some candidate key)

And the relation is clearly in 3NF by this definition (all of the functional dependencies are covered by "X is a superkey").

So why the discrepancy? How am I misapplying the definition? Please don't give me shortcuts that give me the answer in a way I don't want, unless you also help me understand why my application of 3NF (as described) is inaccurate.

2 Answers 2

6

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}.


Note that Wikipedia has the correct definition but the struck-out claim is incorrect:

A transitive dependency can occur only in a relation that has three or more attributes.

There have to be at least 3 different sets, but that doesn't imply at least 3 attributes, it implies at least 2. And indeed for attribute set {X, Z} and candidate key X and functional dependency {} → Z (all rows have the same Z value) transitive dependency X → Z holds:

  1. X → {} -- correct
  2. It is not the case that {} → X -- correct
  3. {} → Z -- correct

This is a CK determining a non-prime attribute. So we don't have 3NF. It's also partial so we don't even have 2NF. (Which also contradicts the common misconceptions that all CKs simple implies 2NF and that 2 attributes implies 2NF.)

(Thanks to philipxy for pointing this out.)

0
0

Based on the relation you provided, for BCNF we know that {T} and {U} are candidate keys that functionally determine {V}. The transitive dependency would occur if {U} was not a candidate key, but remained a determinant.

1
  • I'm not sure I understand your answer, but I'm not sure you understood the question either. I know why it's in BCNF. Why is it in 3NF? The definition states "EVERY nonprime attribute must be nontransitively dependent on EVERY candidate key in the table." It is this specific point that I'm stumbling over.
    – Wug
    Feb 20, 2013 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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