CS 115 Final Exam May 10, 2023
This exam has 8 questions, for a total of 80 points.
Name and Tufts ID:
This exam is intended to be completed in 2 hours. Students may use a 8.5x11 sheet of notes, front and back.
Remember that the question with the lowest grade is automatically dropped from your total score. Good luck!
1. Normalization
1. (10 points) In order to help starting a book club among employees at the library, your aunt decided to made
a database to keep track of their favorite books of the year. Impressed by your skills in conceptual database
design, she asks you to look at her schema design. The given table lists favorite books of every library
employee. Note that the pay in this table is tied to years of service. Review the content of this table and
answer the questions below.
EMPLOYEE ID FAV. BOOK SERVICE TIME PAY FAV. BOOK AUTHOR
1 The Whistler 1 year $12 John Grisham
2 The Wrong Side of Goodbye 5 years $20 Michael Connelly
3 A Dog’s Purpose 3 years $16 W. Bruce Cameron
4 Come Sundown 2 years $14 Nora Roberts
5 The Wrong Side of Goodbye 1 years $12 Michael Connelly
(a) Is the schema for this table in Boyce-Codd Normal Form? Explain why or why not.
(b) If applicable, decompose the schema into BCNF. Show your work, including the functional dependency
you use at each step of the decomposition.
CS 115 Final Exam, Page 2 of 8 May 10, 2023
Name and Tufts ID:
2. SQL
2. (10 points) Consider the following schema:
musician(m_no, m_name, born, died, born_in, living_in)
place(place_no, place_town, place_country)
performance(perf_no, m_no, instrument, perf_type)
Performance’s m_no refers to musician.m_no. M usician.born_in and musician.living_in refer to place_no
keys.
Write both the relational algebra and SQL versions of the questions below (if possible). As stated in class,
assume that aggregation and sorting are not possible in relational algebra:
(a) Find the names of the musicians who were born in 1990 or later in Canada.
(b) List the names of all musicians born in the same city as John Evans in descending alphabetical order.
CS 115 Final Exam, Page 3 of 8 May 10, 2023
Name and Tufts ID:
3. Tree Indexes
3. (10 points) Consider the following (partial) B+ tree index:
80
19 30 60 100 120 140
10 15 18 19 20 40 50 60 65 70 75 80 85 90
Index file
Data file
10 15 18 19 20 40 50 60 65 70 75 80 85 90
(a) Draw the modified tree after the insertion of tuples with search key values 25, 26, and 27 into the base
relation and index. Draw the final tree only. Note that you only have to draw the parts of the tree that
changed.
(b) Consider the original tree again. Draw the modified tree after the deletion of tuples with search key
values 10 and 15. Draw the final tree only. Note that you only have to draw the parts of the tree that
changed.
CS 115 Final Exam, Page 4 of 8 May 10, 2023
Name and Tufts ID:
4. Hash Indexes
4. (10 points) Consider a small extendible hashing structure where:
• Each bucket can hold up to 2 records.
• It has just two primary pages or pages that are unconditionally allocated
• Uses the least-significant bits for the hash function (i.e., records in a bucket of local depth d agree on
the rightmost d bits.) For example, key 4 (0100) and key 12 (1100) agree on their rightmost 3 bits
(100).
An example of an empty instance of this index is:
1 1
0 A
1
1
Directory B
Buckets
(a) Draw this hash index after inserting keys 8 (1000), 5 (101), 14 (1110), 23 (10111), 12 (1100), and 30
(11110) (in that order).
(b) Consider the extendible hash index you drew above. What is the smallest, unique, positive (> 0) key
you can insert into it that will result in the directory doubling in size twice, giving it a global depth of
4?
CS 115 Final Exam, Page 5 of 8 May 10, 2023
Name and Tufts ID:
5. Query Planning
5. (10 points) Consider the following relations and physical query plan (Note that NCARD is the number of
tuples, ICARD is the number of distinct values, and values are all uniformly distributed within each relation):
R(a,b,c) S(d,e,f,g) T(h,i,j)
NCARD(R) = 10,000 NCARD(S) = 10,000 NCARD(T) = 10,000
Min(R,a) = 0 ICARD(S,e) = 10 ICARD(T,h) = 100
Max(R,a) = 9000 ICARD(S,f) = 100
ICARD(R,b) = 100 ICARD(S,d) = 50
ICARD(R,c) = 20 ICARD(S,g) = 40
(f) π a,b,c,g,I,j
R5
(Index Nested Loop) (e)
g=h
R4
(d) σ b=100 ∨ b=101
R3
T (Clustered index on h )
(Hash join) (c)
c=d
R2
(Use B+ tree index ) R1 (Use B+ tree index )
(a) σ a > 100 ∧ a <= 1000 (b) σ e = 10 ∧ f = 1000
R S
(Clustered index on a) (Unclustered index on (e,f) )
(a) Label the estimated output cardinalities (R1 to R6, where R6 is the final output) above each node in
the tree. Note that _ means OR and ^ means AND. Hint: The selectivity of an equi-join on attributes
A and B = 1 / MAX(ICARD(A), ICARD(B)).
(b) Assuming that each relation is roughly 1000 pages, which operator is likely to be the most expensive to
execute? Explain why.
CS 115 Final Exam, Page 6 of 8 May 10, 2023
Name and Tufts ID:
6. Query Optimization
6. (10 points) Consider the following queries. If we use the heuristics of pushing down filters and avoiding
cartesian products, how many distinct plans will a Selinger-style optimizer consider for each of them? Assume
we are only enumerating left-deep plans. Also, count plans that swap the inner and outer relations of a
proposed join as different plans, i.e., a plan with R ./ S is different from one with S ./ R. For your solutions,
show the different plans either as trees or relational algebra expressions.
(a)
SELECT DISTINCT [Link], [Link]
FROM R, S
WHERE [Link] = [Link] AND [Link] = ’John’ AND [Link] = ’USA’;
(b)
SELECT *
FROM R, S, T
WHERE [Link] = [Link] AND [Link] = [Link]
AND [Link] > 15 AND [Link] = ’dog’ AND [Link] = ’GEORGIA’;
CS 115 Final Exam, Page 7 of 8 May 10, 2023
Name and Tufts ID:
7. ACID
7. (10 points) Last weekend, your high school friend Briggy attempted to purchase seeds from Amazon. After
painstaking research, he chose an item and added it to his cart. However, when he tried to purchase it,
Amazon informed him that the item was out of stock. For this problem, explain why the item showed up as
available when he added it to his cart, but not when attempting to check out. Also, explain why Amazon
does not fix this issue. Use one or more of the ACID properties for database transactions when you write
your answer.
CS 115 Final Exam, Page 8 of 8 May 10, 2023
Name and Tufts ID:
8. Transactions
8. (10 points) For each of the following schedules, determine if they will result in deadlock. Assume we are
using rigorous (aka strong strict) two-phase locking. Draw a waits-for graph for each of them with all of the
edges that occurred during this schedule.
(a) T1(RA), T1(RB), T3(RA), T2(RB), T1(WB), T3(WC), T2(RC), T3(RB), T3(Commit), T2(RA),
T2(Commit), T1(WA), T1(Commit)
Does a deadlock happen? YES NO
Waits-for-graph:
(b) T1(RA), T3(RD), T2(WB), T3(RB), T4(RA), T2(WC), T1(WA), T2(RA), T4(RC), T1(Commit),
T2(WD), T3(Commit), T2(Commit), T4(Commit)
Does a deadlock happen? YES NO
Waits-for-graph:
