CSE 532 Assignment #1

Due 16th February, 2015 (at the start of class).

Do it in groups of TWO (or one, if you wish). Beyond your group, you are not allowed to discuss the problem with other classmates. Neither are you allowed to refer to any other resource (online, any book other than our textbook, etc). However, you are welcome to discuss (over email or in person) with me (or TA) -- I will glady guide you appropriately.

Problem Set (100 points)

  1. (30 points) Consider the tables Frequents(drinker, bar), Likes(drinker, beer), Sells(bar, beer), with the following meanings: A tuple (d,b) in Frequents means that d frequents the bar b, a tuple (d,b) in Likes means that d likes the beer b, and a tuple (B,b) in Sells means that the bar B sells the beer b. Assume the tables do not have any duplicates. Answer the following queries in Relational Algebra. Do not use the aggregate operator.

  2. (10 points) Consider the following two queries over R(a,c) and S(a,b).
    Q1:
    Select  r.a, r.c
    From    R r
    Where   NOT EXISTS (Select s.a
                       From  S s
                       Where s.b > '4' and r.a = s.a)
    
    Q2:
    Select  r.a, r.c
    From    R r,  (select distinct S.a, S.b From  S) s
    Where   NOT (r.a = s.a and s.b > '4')
    
  3. (10 points) Consider the following two queries over R(a,b) and S(b,c).
    Q1:        SELECT   A
               FROM     R NATURAL JOIN S
               GROUPBY  A
               HAVING   COUNT(*) < 2
    
    Q2:        SELECT   A
               FROM     R
               WHERE    B NOT IN (SELECT   B
                                  FROM     S
                                  GROUPBY  B
                                  HAVING   COUNT(*) > 1)
    
    
    Treating Q1 and Q2 as multisets (bags), which one of the following is true? Prove your answer (perhaps, by using a counter example or otherwise).
    . Q1 and Q2 always produce the same answer for all databases.
    . The answer to Q1 is always contained in the answer to Q2 for all databases.
    . The answer to Q2 is always contained in the answer to Q1 for all databases.
    . None of the above.
    
  4. (50 points) Do the following exercises from the textbook.