Page 605 - Discrete Mathematics and Its Applications

584 9 / Relations

school are sophomores majoring in mathematics or computer science and have greater than a
3.0 average? Which employees of a company have worked for the company less than 5 years
and make more than $50,000?

n-ary Relations

We begin with the basic definition on which the theory of relational databases rests.

DEFINITION 1 Let A 1 ,A 2 ,...,A n be sets.An n-ary relation on these sets is a subset of A 1 × A 2 × ··· × A n .
The sets A 1 ,A 2 ,...,A n are called the domains of the relation, and n is called its degree.

EXAMPLE 1 Let R be the relation on N × N × N consisting of triples (a,b,c), where a, b, and c are integers
witha< b < c.Then(1, 2, 3) ∈ R,but(2, 4, 3)/∈ R.Thedegreeofthisrelationis3.Itsdomains
are all equal to the set of natural numbers. ▲

EXAMPLE 2 Let R be the relation on Z × Z × Z consisting of all triples of integers (a,b,c) in which
a, b, and c form an arithmetic progression. That is, (a,b,c) ∈ R if and only if there is
an integer k such that b = a + k and c = a + 2k, or equivalently, such that b − a = k and
c − b = k. Note that (1, 3, 5) ∈ R because 3 = 1 + 2 and 5 = 1 + 2 · 2, but (2, 5, 9)/∈ R be-
cause 5 − 2 = 3 while 9 − 5 = 4. This relation has degree 3 and its domains are all equal to the
set of integers. ▲

+
EXAMPLE 3 LetR betherelationonZ × Z × Z consistingoftriples(a,b,m),wherea,b,andmareintegers
with m ≥ 1 and a ≡ b(mod m). Then (8, 2, 3), (−1, 9, 5), and (14, 0, 7) all belong to R,but
(7, 2, 3),(−2, −8, 5),and(11, 0, 6)donotbelongtoR because8 ≡ 2 (mod 3),−1 ≡ 9 (mod 5),
and 14 ≡ 0 (mod 7), but 7 ≡ 2 (mod 3), −2 ≡−8 (mod 5), and 11 ≡ 0 (mod 6). This relation
has degree 3 and its first two domains are the set of all integers and its third domain is the set of
positive integers. ▲

EXAMPLE 4 Let R be the relation consisting of 5-tuples (A,N,S,D,T ) representing airplane flights,
where A is the airline, N is the flight number, S is the starting point, D is the destination, and T is
the departure time. For instance, if Nadir ExpressAirlines has flight 963 from Newark to Bangor
at 15:00, then (Nadir, 963, Newark, Bangor, 15:00) belongs to R. The degree of this relation
is 5, and its domains are the set of all airlines, the set of flight numbers, the set of cities, the set
of cities (again), and the set of times. ▲

Databases and Relations

The time required to manipulate information in a database depends on how this information is
stored. The operations of adding and deleting records, updating records, searching for records,
and combining records from overlapping databases are performed millions of times each day in a
large database. Because of the importance of these operations, various methods for representing
databases have been developed. We will discuss one of these methods, called the relational
data model, based on the concept of a relation.
A database consists of records, which are n-tuples, made up of fields. The fields are the
entries of the n-tuples. For instance, a database of student records may be made up of fields
containing the name, student number, major, and grade point average of the student. The rela-
tional data model represents a database of records as an n-ary relation. Thus, student records