Databases Reference
In-Depth Information
of attributes Y is
functionally dependent
on another set of attributes X, that is, X -> Y, if for
functionally dependent
every valid instance of X, the values of X uniquely determine the values of Y (Codd, 1972;
Connolly & Begg, 2002; Dutka & Hanson, 1989; Hoffer, Prescott & McFadden, 2002). Or,
for any two tuples, t1 and t2, if t1[X] = t2[X], then t1[Y] = t2[Y], where t[X] represents the
projection of t on X (Date, 2000; Elmasri & Navathe, 2000; Rob & Coronel, 2002). That
is, whenever two tuples agree on their X values, they also agree on their Y values. A set of
attributes X is a candidate key if all other attributes of the relation are fully functionally
dependent on X (Codd, 1972; Hoffer, Prescott & McFadden, 2002; Rob & Coronel, 2002;
Ullman & Widom, 1997).
An alternate defi nition of BCNF using the term superkey is that a relation, R, is in
BCNF if whenever a nontrivial functional dependency X -> Y holds, then X is a superkey
of R (Elmasri & Navathe, 2000; Dutka & Hanson, 1989; Ullman & Widom, 1997). A set
of attributes is a
superkey
of a relation if those attributes functionally determine all other
attributes of the relation (Rob & Coronel, 2002; Ullman & Widom, 1997). The functional
dependency X -> Y is nontrivial if Y is not a subset of X. This paper uses the earlier defi ni-
tion of BCNF that is simpler to apply. As shown later in this section, the results would be
the same using both defi nitions since they state the same concept.
Is ASSIGNMENT in BCNF? To answer this question, we check whether ASSIGN-
MENT qualifi es as a relation, and if it does, whether every determinant of ASSIGNMENT
is a candidate key. First, ASSIGNMENT is a relation since it has all the properties of a
relation. In particular, it meets the important requirement that there are no duplicate tuples,
since every tuple has a unique value for ID or COMPUTER_NO.
Second, both ID and COMPUTER_NO are determinants. Attribute ID is a determi-
nant since the functional dependency ID -> {NAME, TITLE} holds. By assumption, every
employee has a unique identifi cation number represented by ID that determines the name
and title. The left hand side of the dependency, ID -> {NAME, TITLE}, is null only in the
trivial case when the right hand side also is null. Attribute COMPUTER_NO is another de-
terminant since the functional dependency, COMPUTER_NO -> {MODEL, RAM}, holds.
There are no other determinants.
If ID and COMPUTER_NO are determinants, are they also candidate keys? ID is a
candidate key if all other attributes of ASSIGNEMNT are fully functionally dependent on
ID. We already established that ID -> {NAME, TITLE}. Does the functional dependency
ID -> {COMPUTER_NO, MODEL, RAM} hold when ID may be null in some tuples in
which the attributes on the right hand side, COMPUTER_NO, MODEL, and RAM, are
not null? For every valid instance of ID, the value of ID uniquely determines the values of
COMPUTER_NO, MODEL, and RAM. That is, every employee has a unique computer,
if the employee has one. Further, ASSIGNMENT satisfi es the requirement that whenever
two tuples agree on their ID values they also agree on their values of COMPUTER_NO,
MODEL, and RAM. Thus, ID -> {COMPUTER_NO, MODEL, RAM} holds even though
ID may be null in certain tuples. Hence, ID is a candidate key of ASSIGNMENT. Whether
a functional dependency holds when the left-hand side may be null but the right hand side
is not is discussed in more detail in the section entitled “The Solution”.
If ID is a candidate key, for similar reasons, COMPUTER_NO also is a candidate key.
Thus, all the determinants of ASSIGNMENT are candidate keys. Hence, ASSIGNMENT is
in BCNF. The same result is obtained if the alternate defi nition of BCNF based on the term
superkey is used. Since ID and COMPUTER_NO are the only determinants, for every non-
