Discrete Mathematics for Computer Science

Binary Relations 161

Table 3.5 IsMarriedTo

Relation

IsMarriedTo

John Mary

Mary John

Peter Elaine

Elaine Peter

Maude Harold

Harold Maude

(b) IsParentOf= {(Mary, Elaine), (John, Elaine), (Mary, Maude),

(John, Maude), (Peter, George), (Elaine, George),

(Maude, Elizabeth), (Harold, Elizabeth))

(c) Peter and Harold do not appear in the relation IsSameGeneration, because this relation

deals with direct descendants only. In this case, the family tree has more information

than is required to define this relation:

IsSameGeneration = {(Elaine, Maude), (Maude, Elaine),

(George, Elizabeth), (Elizabeth, George), (Mary, John),

(John, Mary), (John, John), (Mary, Mary), (Elaine, Elaine),

(Maude, Maude), (George, George), (Elizabeth, Elizabeth)} )

A specific computer application of relations appears in Section 3.10, which introduces
the concept of relational databases. A relational database consists of a number of relations.
To answer questions concerning the information contained in the relations, the user poses
a question or a query that is processed by the database system. If, for example, a user
makes a query about who is married to whom, the database system would respond with
a table such as Table 3.5. In relational database systems, the answer to any query is a
relation.
For example, let X be any set, then

Idx = {(x,y) :x, yEX and x=yl

Since Idx is a set of ordered pairs of elements in X, it defines a relation on X. This re-
lation is called the identity relation, or the equality relation, and may be denoted as
=x. The trivial relation, or void relation, or empty relation, on any set consists of 0.
The universal relation on a set consists of all possible ordered pairs of elements of a
set.
For any set X C R, let

Ltx= {(x, y) : x, y e X and x <y}

Lex={(x,y):x, yEX and x < y}

GtX = {(x, y) : x, y E X and x > yj

Gex={(x,y):x,yEX and x>y