Page 608 - Discrete Mathematics and Its Applications

9.2 n-ary Relations and Their Applications 587

TABLE 2 GPAs. TABLE 3 Enrollments. TABLE 4 Majors.
Student_name GPA Student Major Course Student Major
Ackermann 3.88 Glauser Biology BI 290 Glauser Biology
Adams 3.45 Glauser Biology MS 475 Marcus Mathematics
Chou 3.49 Glauser Biology PY 410 Miller Computer Science
Goodfriend 3.45 Marcus Mathematics MS 511
Rao 3.90 Marcus Mathematics MS 603
Stevens 2.99 Marcus Mathematics CS 322
Miller Computer Science MS 575
Miller Computer Science CS 455

EXAMPLE 8 What results when the projection P 1,3 is applied to the 4-tuples (2, 3, 0, 4),
(Jane Doe, 234111001, Geography, 3.14), and (a 1 ,a 2 ,a 3 ,a 4 )?

Solution:The projection P 1,3 sends these 4-tuples to (2, 0), (Jane Doe, Geography), and (a 1 ,a 3 ),
respectively. ▲

Example 9 illustrates how new relations are produced using projections.
EXAMPLE 9 What relation results when the projection P 1,4 is applied to the relation in Table 1?

Solution: When the projection P 1,4 is used, the second and third columns of the table are deleted,
and pairs representing student names and grade point averages are obtained. Table 2 displays
the results of this projection. ▲

Fewer rows may result when a projection is applied to the table for a relation. This happens
when some of the n-tuples in the relation have identical values in each of the m components of
the projection, and only disagree in components deleted by the projection. For instance, consider
the following example.
EXAMPLE 10 What is the table obtained when the projection P 1,2 is applied to the relation in Table 3?

Solution: Table 4 displays the relation obtained when P 1,2 is applied to Table 3. Note that there
are fewer rows after this projection is applied. ▲

The join operation is used to combine two tables into one when these tables share some
identical fields. For instance, a table containing fields for airline, flight number, and gate, and
another table containing fields for flight number, gate, and departure time can be combined into
a table containing fields for airline, flight number, gate, and departure time.

DEFINITION 4 Let R be a relation of degree m and S a relation of degree n. The join J p (R, S),
where p ≤ m and p ≤ n, is a relation of degree m + n − p that consists of all
(m + n − p)-tuples (a 1 ,a 2 ,...,a m−p ,c 1 ,c 2 ,...,c p ,b 1 ,b 2 ,...,b n−p ), where the m-tuple
(a 1 ,a 2 ,...,a m−p ,c 1 ,c 2 ,...,c p ) belongs to R and the n-tuple (c 1 ,c 2 ,...,c p ,b 1 ,b 2 ,...,
b n−p ) belongs to S.

In other words, the join operator J p produces a new relation from two relations by combining all
m-tuples of the first relation with all n-tuples of the second relation, where the last p components
of the m-tuples agree with the first p components of the n-tuples.