202 CHAPTER 3 Relations
- Construct the partial order represented by the family tree shown here. The relation is
"is a descendant of."
Mary = JohnPeter = Elaine Maude = HaroldGeorge Elizabeth- For the set of all people, prove that the relation "weighs no more than" is not a partial
order. - For the set of all people, prove that the relation "weighs less than" is not a linear order.
- (a) Fordx,r y E definexIprNyif,forsomeZ E N,z :0,z 0 1,z x =y.Wesay
x is a proper divisor of y. Is IpreN a linear ordering on N?
(b) In the real numbers, define x I pR Y if, some for z E R, z #: , • z #1, y z x
Y. Is I a linear ordering on prR ?R?- Prove Theorem 1 (a).
- For the partial orders shown in Figures 3.11, 3.12, 3.14, and 3.15, identify all minimal,
minimum, maximum, and maximal elements. - Suppose A, B, C, D, E, and F are tasks that must be performed with the precedence
shown:
AB /\CD / E / FFor example, E must be completed before either B or C can be performed, but
D, E, and F can be completed in any order relative to one another. Let T ={A, B, C, D, E, Fl, and define the partial order R on T as represented by the dia-
gram. Find a linear order S on T where R - IdT C S.- Challenge: Find a partial ordering with exactly one minimal element but where that
element is not a minimum element. - Prove Theorem 2. (Hint: The proof of part (e) should be quite short.)
rnRelational Databases: An Introduction
A database is a shared collection of interrelated data designed to meet the varied infor-
mation needs of an organization. To describe many interrelationships among many types
of objects, there needs to be a good way to represent these interrelationships. The diagram
of Figure 3.2 is a clear illustration of a family tree, but it uses certain specific facts about
family relationships-for example, that each person has exactly two parents. It would be
much harder to represent more complicated relationships using the same type of diagram.