211L7Solutions

From Marks Wiki
Revision as of 22:35, 8 March 2008 by Mark (talk | contribs) (1 revision(s))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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)?