View source for 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)?'''