202
CHAPTER 3 Relations
8. Construct the partial order represented by the family tree shown here. The relation is
"is a descendant of."
Mary = John
Peter = Elaine
Maude = Harold
George
Elizabeth
9. For the set of all people, prove that the relation "weighs no more than" is not a partial
order.
10. For the set of all people, prove that the relation "weighs less than" is not a linear order.
11. (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, for
some
z E R, z #: , z
• #1, z
y
x
Y. Is I
prR
a linear ordering on
?R?
12. Prove Theorem 1 (a).
13. For the partial orders shown in Figures 3.11, 3.12, 3.14, and 3.15, identify all minimal,
minimum, maximum, and maximal elements.
14. Suppose A, B, C, D, E, and F are tasks that must be performed with the precedence
shown:
A
B /\C
D /
E /
F
For 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 diagram. Find a linear order S on T where R - IdT C S.
15. Challenge: Find a partial ordering with exactly one minimal element but where that
element is not a minimum element.
16. 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 information 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.
CHAPTER 3 Relations
8. Construct the partial order represented by the family tree shown here. The relation is
"is a descendant of."
Mary = John
Peter = Elaine
Maude = Harold
George
Elizabeth
9. For the set of all people, prove that the relation "weighs no more than" is not a partial
order.
10. For the set of all people, prove that the relation "weighs less than" is not a linear order.
11. (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, for
some
z E R, z #: , z
• #1, z
y
x
Y. Is I
prR
a linear ordering on
?R?
12. Prove Theorem 1 (a).
13. For the partial orders shown in Figures 3.11, 3.12, 3.14, and 3.15, identify all minimal,
minimum, maximum, and maximal elements.
14. Suppose A, B, C, D, E, and F are tasks that must be performed with the precedence
shown:
A
B /\C
D /
E /
F
For 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 diagram. Find a linear order S on T where R - IdT C S.
15. Challenge: Find a partial ordering with exactly one minimal element but where that
element is not a minimum element.
16. 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 information 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.