# 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.
• Find pairs of drinkers that frequent the SAME SET of bars.
• A beer is called "popular" if it is sold by at least 4 different bars. Find drinkers that like all the popular beers.
• We say that a bar b is redundant if there exists a bar b1 such that (i) b1 sells all the beers that b sells, and (ii) All the drinkers that frequent b and like some beer that b sells, also frequent b1. Find all redundant bars.

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')
```
• Give a relational algebra expression that is equivalent to Q1. Assume bag semantics, i.e., assume that the relational algebra operators are bag operators.
• Are Q1 and Q2 equivalent (return the same bags, i.e, same tuples with the same number of duplicates)? If yes, PROVE it. If not, show a counter example.
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.
• 2.4.1 (i). Note that you can't use the aggregate operator here.
• 2.4.10.
• 6.3.1 (f).
• 6.3.6.
• 6.4.6 (j).