Chapter Review
213
property. Focusing on reflexive, symmetric, and transitive relations leads to equivalence
relations and partitions. Focusing on antisymmetric and transitive relations leads to partial and total orders. When discussing ordering relations, it is important to understand the
notion of comparable elements. Special comparable elements include minimal, minimum,
maximal, and maximum elements. Finally, the chapter deals with relations in the context
of the operations that are used by a relational database.
Applications in this chapter include lexicographical or dictionary ordering, finding a
minimal element, and embedding a partial order in a total order. The examples dealing with
relational databases point out the operations that are used for processing queries in such a
database.
3.12.1 Summary
3.1 and 3.2 Summary
TERMS
binary relation
n-tuples
composition
property
deck of 52 cards
query
empty relation
relations
equality relation
ternary relation
family tree
trivial relation
identity relation
unary relation
inverse
universal relation
irreflexiv
void relation
n-ary relation
3.4 Summary
TERMS
antisymmetric
reflexive closure
graph
reflexive and transitive closure
irreflexive
symmetric
nth power of R
symmetric closure
R +
transitive
R*
transitive closure
reflexive
THEOREMS
"A relation R on a set X is reflexive if and
The reflexive closure of a relation R on a
only if IDx C R.
set X is R U IDx.
"A relation R on a set X is irreflexive if and
The symmetric closure of a relation R on a
only if R n Idx = 0.
set X is R U R1 .
"A relation R on a set X is symmetric if and
The transitive closure of a relation R on a
only if R = R-1.
set X is R+.
"A relation R on a set X is transitive if and
The reflexive and transitive closure of a
only if R o R C R.
relation R on a set X is R*.