211L7Solutions

Exercises

1. Consider the database described in the first section. Write down the relations and their arities that are represented by the tables Names, Gender2, and BankAccounts.

• Names has an arity of 3 and shows the relations {(00,Elaine,Aziz),(01,Robert,Simmons),(02,Andrei,Goncharov),(03,Michael,Love),(04,Steven,Hosking),(05,Nevil,Hosking),(06,Ann,Fong),(07,Bruce,McDonald),(08,Cynthia,Roberts),(09,Marina,Mendes)}.
• Gender2 has an arity of 1 and shows the relationship { (01),(02),(03),(04),(05),(07) }.
• BankAccounts has an arity of 3 and shows the relationship {(00,National,712456001),(01,Union,713456501),(02,National,712456001),(03,West-Union,512566001),(04,West-Uniion,712406006),(05,Westlake,Bank,212456708),(06,Westlake,Bank,415456051),(07,National,912454087),(08,National,032456548),(09,Westlake,Bank,945456100)}.

2. Consider the graph G representing a binary relation R. How do we change G to represent the relation -/R?

Let all the edges of graph g be R. The complement of R is the relation A^k\R. In other words wherever there is no edge, create one and if there is an existing edge, remove it.

3. Let R be a k-pace relation with k > 1. Let i be such that 1 <= i <= k. Prove that that ExiR = -/(Axi -/R).

{(a1, . . . , ai−1, ai+1, . . . , ak) | there is an a which is an element from A, such that (a1, . . . , ai−1, a, ai+1, . . . , ak) is an element of R}

a is-an-element-of ExiR. There is an i from A such that (i,a) is in R. which is the same as, there is no i from A such that (i,a)

4. Let R be a k-pace relation. Prove that that Exk+1c(R) = R.

R= {a1, . . . , ak}

Then:

c(R) = {a1, . . . , ak,ak+1}

Thus taking Exk+1 which was the cylindrification of ak+1. We get

{a1, . . . , ak} back.

5. Consider the following relational database (D; S, Add,Mult,Div,<=), where

• The domain D is {0, 1, 2, 3, 4}.
• The successor relation: S = {(x, y) | y = x + 1 and x 2 D}.
• The addition relation: Add = {(x, y, z) | x + y = z and x, y, z 2 D}.
• The multiplication relation: Mult = {(x, y, z) | x · y = z and x, y, z 2 D}.
• The divisibility relation: Div = {(x, y, z) | x/y = z and x, y, z,2 D}.
• The order relation: �= {(x, y) | x � y and x, y 2 D}.

Do the following:

(a) Write down the tables for S, Add, Mult, and Div.

(b) Write down the following relations Add [Mult, S, 9x1S, 9x2S, 8x1Mult, Inst(� , 2, 1), Inst(Mult, 1, 1).

(c) Write down the following relations Link1(S, S), Link1(Add, S), Link2(Add,Mult).

(d) Write down the following relations 9x3Add, 9x3Mult, 8x29x3Add, 8x29x3Mult.

6. Consider the set A consisting of all soccer players of a city. Assume no player belong to two distinct teams. Consider the relation E = {(x, y) | x and y are in the same team }. Prove that E is an equivalence relation. What are the equivalence classes of E?

E is reflexive, symmetric, and transitive. For each player, that player is only in one team. For any pair in a team, it doesn't matter which order you take the pair to be, that pair will always belong to the same team. For any two players in a team, other players in the same team with either of the pair, will also be parable with the other person of the pair.

7. List all the equivalence relations on set A = {x, y, z}. With each equivalence relation list all of its equivalence classes.

x

• [x]

xy

• [x]
• [y]

xz

• [x]
• [z]

xyz

• [x]
• [y]
• [z]

8. Consider the set N. On the set P(N) of all subsets of N define the following relation E: {(X, Y ) | (X \ Y ) [ (Y \ X) is a finite set}. Show that E is an equivalence relation on P(N). Describe equivalence classes of E.

9. Prove that if E1 and E2 are equivalence relations on A then so is E1 n E2. Is E1 U E2 always an equivalence relation?

If E1 and E2 are equivalence relations on A, then they are reflexive, symmetric and transitive. As such

10. List all partial orders on the set {a, b, c}.

(a,a)(b,b)(c,c)

11. Consider the relation R = {(x, y) | x, y are positive natural numbers and x is a factor of y} on the set of all positive integers. Is it a partial order?

Yes. R is reflexive, antisymmetric, and transitive. For any x, (x,x) exists as it is a factor of itself and is thus reflexive. For any y which has a factor x, and if x

12. Consider the power set P(A). Prove that the relation � on P(A) is a partial order.

13. Define the least and minimal elements in a partially ordered set (This should be similar to the definitions of the greatest and the minimal elements).

14. Consider the following set A = {2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15}. On this set consider the relation R = {(x, y) | x divides y}. Prove that (A,R) is a partially ordered set. List all maximal and minimal elements of this partially ordered set.

15. On the set N consider the following binary relation R = {(x, y) | there is a natural number n such that y = 2n ·x}. Prove that this is a partial order of N. What are the minimal elements of the partially ordered set (N,R)?