CSE 444 Final Examination

June 10th, 2010

Name:

Question Points Score

1 15
2 20
3 10
4 10
5 10
6 10
7 15
8 10
Total: 100

This exam is an open book exam. You have 1 hour 50 minutes; budget time carefully.
Intermediate steps are rarely required but often useful for partial credit. Good luck!

1
CSE 444 Final June 10, 2010

1 SQL
1. (15 points)
Consider the following Flickr-type database:

Users(uid, name)
Picture(pid, owner, size)
Comment(cid, auth, pict, text)

Where:

• [Link], [Link], [Link] are keys.

• [Link], [Link] are foreign keys into Users.
• [Link] is a foreign key to Picture.
(a) (5 points) Write a SQL query that counts, for every user, the number of other users
who have commented on their pictures. That is, for each user you need to compute
the total number of distinct users (including herself) who have commented on any
of her pictures. Your answer should return only those answers where the count is
≥ 1 (i.e. you don’t need to return users that have no comments on any of their
pictures).

Solution:
select [Link], count(distinct [Link])
from Picutre x, Comment y
where [Link] = [Link] and [Link] != [Link]

Page 2
CSE 444 Final June 10, 2010

Users(uid, name)
Picture(pid, owner, size)
Comment(cid, auth, pict, text)
(b) (5 points) A spammer is a user who comments on all pictures that are not owned
by him (her). Write a SQL query that returns all spammers.

Solution:
select *
from Users x
where not exists
select *
from Picture y
where [Link] != [Link] and
not exists select *
from Comment z
where [Link] = [Link] and [Link] = [Link]

Page 3
CSE 444 Final June 10, 2010

Users(uid, name)
Picture(pid, owner, size)
Comment(cid, auth, pict, text)
(c) (5 points) Two users are friends if they comment on each others’ pictures: that is,
x, y are friends if x made a commented on some picture of y, and y made a comment
on some picture of x. Write a SQL query that computes, for each user, the number
of his/her friends. Your query should return only those answers where the count is
≥ 1.

Solution:
select [Link], [Link], count(*)
from Users x, Users y
where exists (select *
from Picture u, Comment v
where [Link] = [Link] and [Link]=[Link]
and [Link] = [Link])
and exists ... symmetrically
group by [Link], [Link]

Page 4
CSE 444 Final June 10, 2010

2 Transactions
2. (20 points)
Consider a concurrency control manager by timestamps. Below are several sequences of
events, including start events, where sti means that transaction Ti starts and coi means
Ti commits. These sequences represent real time, and the timestamp-based scheduler
will allocate timestamps to transactions in the order of their starts. In each case below,
say what happens with the last request.
You have to choose between one of the following four possible answers:

1. the request is accepted,

2. the request is ignored,
3. the transaction is delayed,
4. the transaction is rolled back.
(a) (4 points) st1; st2; st3; r1(A); w1(A); r2(A);
The system will perform the following action for r2(A):

Solution: The system will perform the following action for r2(A): delayed.

(b) (4 points) st1; st2; r2(A); co2; r1(A); w1(A)

The system will perform the following action for w1(A):

Solution: The system will perform the following action for w1(A): rolled back.

(c) (4 points) st1; st2; st3; r1(A); w2(A); w3(A); r2(A);

The system will perform the following action for r2(A):

Solution: The system will perform the following action for r2(A): rolled back.

(d) (4 points) st1; st2; r1(A); r2(A); w1(B); w2(B);

Page 5
CSE 444 Final June 10, 2010

The system will perform the following action for w2(B):

Solution: The system will perform the following action for w2(B): accepted.

(e) (4 points) st1; st2; st3; r1(A); w3(A); co3; r2(B); w2(A)
The system will perform the following action for w2(A):

Solution: The system will perform the following action for w2(A): ignored.

Page 6
CSE 444 Final June 10, 2010

3 Conceptual Design
3. (10 points)
(a) (5 points) Decompose in BCNF the relation R(A, B, C, D, E) that satisfies the fol-
lowing functional dependencies. Show your steps, and show the keys in the decom-
posed relations.

A → B
CD → E

Solution:

A+ = AB

Decompose into R1 = AB, R2 = ACDE Continue with

CD+ = CDE

Decompose R2 into R3 = CDE and R4 = CDA

Page 7
CSE 444 Final June 10, 2010

(b) (5 points) For each of the statements below, indicate whether they are true or false.
You do not need to justify your answers.
• Every relation with only two attributes is in BCNF.
• If X and Y are super-keys then X ∪ Y is also a super-key.
• If X and Y are super-keys then X ∩ Y is also a super-key.
• If X → A and Y → A, then (X ∩ Y ) → A.
• If X + = X and Y + = Y then (X ∩ Y )+ = (X ∩ Y ).

Page 8
CSE 444 Final June 10, 2010

4 Indexes
4. (10 points)
Consider the following database about word occurrences in Webpages:

Webpage(url, author)
Occurs(url, wid)
Word(wid, text, language)

where:

• [Link] and [Link] are keys.

• [Link] and [Link] are foreign keys to Webpage and Word respectively.

Assume the following statistics

T (Webpage) = V (Occurs, url) = 109

T (Occurs) = 1012
T (Word) = V (Occurs, wid) = 106
V (Webpage, author) = 107
V (Word, language) = 100

Assume ten records can be fit in one block, hence B(Webage) = T (Webpage)/10 and
similarly for all other tables.
(a) (5 points) Consider the following plan:

index-lookup
(σauthor=’John’ (Webpage) 1index-join
url=url Occurs)

1main-memory-hash-join
wid=wid
index-lookup
σlanguage=’French’ (Word)

Compute the cost of the plan in each of the following cases:

Page 9
CSE 444 Final June 10, 2010

1. We have the following indexes:

[Link] = primary index

[Link] = secondary index
[Link] = secondary index
[Link] = primary index
[Link] = primary index
[Link] = secondary index

Solution:

Unclustered Index Lookup on Author = 102

Unclustered Index Join = 102 ∗ 103
Unclustered Index Lookup on Language = 104
Main Memory Hash Join = 0

Total = 102 + 105 + 104

2. We have the following indexes:

[Link] = secondary index

[Link] = primary index
[Link] = primary index
[Link] = secondary index
[Link] = secondary index
[Link] = primary index

Solution:

Clustered Index Lookup on Author = 10

Clustered Index Join = 102 ∗ 102
Clustered Index Lookup on Language = 103
Main Memory Hash Join = 0

Total = 10 + 104 + 103

Page 10
CSE 444 Final June 10, 2010

(b) (5 points) Consider the following plan:

(Webpage 1merge-join
url=url Occurs) 1merge-join
wid=wid Word
Choose a set of indexes that minimizes the total number of disk I/O’s for the plan.
Each index should be on a single attribute, and you can choose as many (or as few)
indexes as you want. Indicate for each index if it is primary or secondary. For each
merge-join we assume to have sufficient main memory to complete it in two pass.
(There are no index-join operators in this plan: you need to figure out how indexes
can help at all in this query plan.)

Solution: Primary Index on Wepage(url)

Primary Index on Occurs(url)
Primary Index on Word(wid)

These clustered indexes allow the two-pas merge join to skip the initial sorting
step for each of the tables.

Page 11
CSE 444 Final June 10, 2010

5 Query Optimization
5. (10 points)
For the following questions, we consider the schema R(A, B), S(C, D), T (E, F ), U (G, H).
(a) (5 points) Write a logical plan for the following query:
select R.A, sum(T.F)
from R, S, T
where R.B = S.C and S.D = T.E
group by R.A
having count(*) > 20

Solution:

Page 12
CSE 444 Final June 10, 2010

(b) (5 points) Consider the following query:

select *
from R, S, T, U
where R.B = S.C and S.D = T.E and S.D = U.G
• Write all left-deep, cartesian-free join trees for this query. Assume that the
join operator is not commutative: that is, you should report both R 1 S and
S 1 R as distinct plans. Note: you need to turn in several plans.

Solution:

R1S1T 1U
R1S1U 1T

S 1R1T 1U
S 1R1U 1T
S 1T 1R1U
S 1T 1U 1R
S 1U 1R1T
S 1U 1T 1R

T 1S1R1U
T 1S1U 1R
T 1U 1S1R

U 1S1R1T
U 1S1T 1R
U 1T 1S1R

Page 13
CSE 444 Final June 10, 2010

• Write a full semijoin reducer for this query.

Solution:

S0 = SnT
S 00 = S0 n U
S 000 = S 00 n R
R0 = R n S 000
T0 = T n S 000
U0 = U n S 000

Q = S 000 1 T 0 1 U 0 1 R0

Page 14
CSE 444 Final June 10, 2010

6 Statistics
6. (10 points)
Consider the relations R(A, B), S(C, D), T (E, F ) and the following histograms on R.A
and T.F :
R.A 0 . . . 999 1000 . . . 1999 2000 . . . 2999 3000 . . . 3999 4000 . . . 4999
104 2 · 104 3 · 104 3 · 104 2 · 104
T.F 0 . . . 2499 2500 . . . 2699 2700 . . . 3999 4000 . . . 7999
104 104 104 104
(a) (1 point) What kind of histogram is R.A and what kind of histogram is T.F ?

(b) (4 points) Estimate the number of tuples returned by σ500≤A≤3499 (R). Show your
work for partial credit.

(c) (5 points) Estimate the number of tuples returned by the following query:
SELECT *
FROM R, S, T
WHERE R.A = 2432 and R.B = S.C and S.D = T.E and T.F = 1234
assuming the two histograms above, plus the following statistics:

T (R) = 105 T (S) = 6 · 106 T (T ) = 4 · 105

V (R, B) = V (S, C) = 3 · 103
V (S, D) = V (T, E) = 2 · 104

Show your work for partial credit.

Page 15
CSE 444 Final June 10, 2010

7 Parallel Databases
7. (15 points)
Consider the following relations R(A, B), S(C, D) and the following query:

select R.A, sum(S.D)

from R, S
where R.B = S.C
group by R.A

(a) (5 points) Write the query in Pig Latin.

(b) (5 points) How many map-reduce tasks does Pig Latin require to evaluate the query
?

(c) (5 points) Give the total I/O cost of your Pig Latin program, as a function of
B(R), B(S), B(R 1 S), and P (the number of processors). Assume that each
processor’s main memory is ≥ max(B(R), B(S), B(R 1 S))/P . Note: your analysis
should be based on the actual implementation of map-reduce, and should not assume
any other optimizations.

Page 16
CSE 444 Final June 10, 2010

8 Bloom Filters
8. (10 points)
(a) (1 point) Is the following statement true or false ? Bloom filters are used to improve
cardinality estimation.

(a)
True or false ?

Solution: FALSE. Bloom filter is used for reducing communication costs be-
tween two nodes in a distributed system.

(b) (2 points) A Bloom filter using a hash map of 1k Bytes has a false positive error
rate of 19%. In order to improve the error rate, the systems administrator decides
to double the size of the hash map to 2k Bytes, and, at the same time, to double the
number of hash functions used by the Bloom filter. What is the new false positives
error rate ?

(b)
The new false positive error rate is:

Solution: We are given that [1 − exp(−kn/m)]k = .19. If m and k are now

doubled, we have:

[1−exp(−2kn/2m)]2k = [1−exp(−kn/m)]2k = [[1−exp(−kn/m)]k ]2 = .192 = .0361

Thus the new false positive rate is 3.61%.

(c) (2 points) A regular hash map of 1k Bytes has a false positive error rate of 19%.
In order to improve this rate, the systems administrator decides to double the size
of the hash map to 2k Bytes. What is the new false positive error rate ?

(c)
The new false positive error rate is:

√ given that 1 − exp(−n/m) = .19. So exp(−n/m) = .81 ⇒

Solution: We are
exp(−n/2m) = .81 = .9. Thus the new false positive rate is 1−exp(−n/2m) =
1 − .9 = .1.

Page 17
CSE 444 Final June 10, 2010

(d) (5 points) Data supplier S1 has n = 1M (= 106 ) documents. Data supplier S2 has
also n = 1M documents. Each document has 1k bytes. They have 50 documents
in common and they want to compute these. They will proceed as follows:
• S1 computes a hash map M with cn bits, where c=8 and sends it to S2
• S2 checks its items in M and sends all matches to S1
• S1 computes the result and sends the matching 50 documents to S2
Indicate the total number of bytes transferred over the network in each step as-
suming (a) the hash map is a standard hash table, (b) the hash map is a bloom
filter.

Solution: There are three parts to the cost:

1. S1 computes a hashtable / bloom filter and sends it to S2. This takes cn

bits = 8M bytes = 1MB.

2. S2 sends back documents that is positive when matched against the hashtable
/ bloom filter. The number of documents is 50 + (number of false posi-
tives).

• For hash table, the false positive rate is 1 − exp(−n/m) = 1 −

exp(−n/8n) = 1 − exp(−1/8), or 11%. So there are 110,000 false
positive documents, making the total number of documents 110,050
and size 110,050KB.
• For bloom filter, the false positive rate is (1 − exp(−k/8))k .

Assuming optimal number of hash functions, the false positive rate is

2(−8ln2) , or 2%. So there are 20,000 false positive documents, making the
total 20,050 and size 20,050KB.

3. S1 computes and sends the 50 common documents back to S2. This takes
50KB.

So for hash table, the total cost is 1M B + 110.05M B + 0.05M B = 111.10M B.

For bloom filter, the total cost is 1M B + 20.05M B + 0.05M B = 21.20M B.
(Full credit was given if second step was left in terms of exponentials or in terms
of k if optimal bloom filter was not assumed.)

Page 18