Page 607 - Discrete Mathematics and Its Applications

586 9 / Relations

EXAMPLE 6 Is the Cartesian product of the domain of major fields of study and the domain of GPAs a
composite key for the n-ary relation from Table 1, assuming that no n-tuples are ever added?

Solution: Because no two 4-tuples from this table have both the same major and the same GPA,
this Cartesian product is a composite key. ▲

Because primary and composite keys are used to identify records uniquely in a database,
it is important that keys remain valid when new records are added to the database. Hence,
checks should be made to ensure that every new record has values that are different in
the appropriate field, or fields, from all other records in this table. For instance, it makes
sense to use the student identification number as a key for student records if no two
students ever have the same student identification number. A university should not use the
name field as a key, because two students may have the same name (such as John Smith).

Operations on n-ary Relations

There are a variety of operations on n-ary relations that can be used to form new n-ary relations.
Applied together, these operations can answer queries on databases that ask for all n-tuples that
satisfy certain conditions.
The most basic operation on an n-ary relation is determining all n-tuples in the n-ary relation
that satisfy certain conditions. For example, we may want to find all the records of all computer
science majors in a database of student records. We may want to find all students who have a
grade point average above 3.5. We may want to find the records of all computer science majors
who have a grade point average above 3.5. To perform such tasks we use the selection operator.

DEFINITION 2 Let R be an n-ary relation and C a condition that elements in R may satisfy. Then the selection
operator s C maps the n-ary relation R to the n-ary relation of all n-tuples from R that satisfy
the condition C.

EXAMPLE 7 To find the records of computer science majors in the n-ary relation R shown in Table 1, we use
, where C 1 is the condition Major = “Computer Science.” The result is the two
the operator s C 1
4-tuples (Ackermann, 231455, Computer Science, 3.88) and (Chou, 102147, Computer Science,
3.49). Similarly, to find the records of students who have a grade point average above 3.5 in
, where C 2 is the condition GPA > 3.5. The result is the
this database, we use the operator s C 2
two 4-tuples (Ackermann, 231455, Computer Science, 3.88) and (Rao, 678543, Mathematics,
3.90). Finally, to find the records of computer science majors who have a GPA above 3.5, we
, where C 3 is the condition (Major = “Computer Science” ∧ GPA > 3.5).
use the operator s C 3
The result consists of the single 4-tuple (Ackermann, 231455, Computer Science, 3.88). ▲

Projections are used to form new n-ary relations by deleting the same fields in every record
of the relation.

DEFINITION 3 The projection P i 1 i 2 ,...,i m where i 1 <i 2 < ··· <i m , maps the n-tuple (a 1 , a 2 ,...,a n )tothe
), where m ≤ n.
m-tuple (a i 1 , a i 2 ,...,a i m

deletes n − m of the components of an n-tuple, leaving
In other words, the projection P i 1 ,i 2 ,...,i m
the i 1 th, i 2 th,..., and i m th components.