Discrete Mathematics for Computer Science

214 CHAPTER 3 Relations

3.6 Summary

TERMS

congruent quotient

divisible by refines

equivalence class remainder

equivalence relation x =- y (mod p)

partition

THEOREMS

Let P be a partition of a set X. For x • y E X, define x - y to mean that x and y are in the

same element of the partition. Then, -is an equivalence relation. The equivalence classes

of -are exactly the elements of P.

3.8 Summary

TERMS

above maximal

ASCII code maximum

below minimal

comparable minimum

dictionary ordering optimal

divides partial ordering

embedding strict partial ordering

law of trichotomy total ordering

lexicographical ordering

linear ordering

ALGORITHMS

Finding a Minimal Element

3.10 Summary

TERMS

attribute query

cartesian product relational algebra

database relational database

equijoin selection

join table

natural join tuples

projection value

quadruples

ALGORITHM

Join Two Relations