CH H AH PI TH EI iRa 3 l I
Relations
Human language has many words and phrases to describe relationships between or among
objects. It may be that for two people, A and B, that A is a parent of B, that A is an
ancestor of B, that A is taller than B, or that A is in front of B. In algebra, it may be that
the value of variable x is less than the value of variable y. In geometry, it may be that one
point lies between two other points on a line. In set theory, it may be that a set X is a subset
of a set Y or that X is disjoint from Y. At a particular moment while a computer program
is running, it may be that the value of x is less than the value of y. All these notions are
special instances of a relation.
This chapter introduces the concept of a relation to formalize the familiar notion of a
relationship between or among objects. Relations provide a way of representing relation-
ships like the ones just described, so that they can be stored, studied, and reasoned about.
In this chapter, we first provide an introduction to relations, the important properties of
relations, and the fundamental operations on relations. We next deal with equivalence re-
lations, a generalization of the notion of equality, and then move on to ordering relations.
These relations generalize the ordering relations on R (<, >, <, >, =). Searching and sort-
ing operations are based on these relations. Finally, we show how the ideas in this chapter
are applied in a relational database.rnBinary Relations
Most card games are played with a standard deck of 52 cards. The deck is divided
into four groups, or suits, called Clubs (4), Diamonds (*), Hearts (Q), and Spades (*).
Each suit has 13 cards, ordered in increasing order of value: 2, 3, 4, 5, 6, 7, 8, 9, 10,
Jack, Queen, King, and Ace. The 2 card has the lowest value, and the Ace card has the
highest value. In this ordering, we say that one card has a higher value than, or is higher
than, another card if, ignoring their suits, the value of the first card occurs after the value of
the second in this ordering. To focus on the ideas presented in this chapter while keeping
matters simple, many of the examples that follow will use a deck with only six cards. This
set of cards, called SpecialDeck, consists of the 10, Jack, and Queen of Hearts as well as
the 10, Jack, and King of Clubs. The values of these cards are ordered as described. The
SpecialDeck has its elements shown in Table 3.1.
157