Database assignment

CS486/586 Introduction to Databases

Fall 2017 Quarter

Assignment 7 – Query Evaluation, Transactions and

Normalization

Due: Wednesday, November 29, 2017 at the beginning of

class

Reminder: Second exam, Monday, December, 4 7:30-

9:20p.

You may do this assignment individually or you may work with one partner. That is, this assignment is to be completed by individuals or by teams of two students. You should only talk to the instructor, the TA and your partner about this assignment. You may also post questions to the Piazza discussion list.

Please turn in your completed assignments on paper. Put your last name, first name, the assignment number in that order in the first line of your assignment. List last name and first name for your partner, if you have one, on the second line of your assignment. (If you are working with a partner, turn in one assignment paper.)

Question 1: Relational Algebra Equivalences

Each of the proposed equivalences below on relations r(R) and s(S) only holds under certain conditions. In the equivalences,

• X, R and S are sets of attributes, • C is a single attribute, • COUNT(r) returns the number of tuples in r, and

• ⋈ is natural join.

(a) (4 points each) For each equivalence, give example schemas and instances for r and s where the equivalence does not hold. (Assume that the expressions contain no syntax errors. For example, in ii, X is assumed to be a subset of R.)

(b) (6 points) For each equivalence, give a side condition that guarantees the equivalence will hold. The condition should be at the schema level (relation schemes, keys, foreign keys) and not at the instance level (number of tuples, specific values). The less restrictive the condition, the better.

i. pX(r ⋈ s) º pX(r) ⋈ s

ii. pX(r – (sC=5(r))) º pX(r) – pX(sC=5(r))

iii. COUNT(r ⋈ s) º COUNT(r) * COUNT(s)

iv. COUNT(r ⋈ s) º COUNT(r)

Question 2: Statistics

a. (5 points) Determine the min and max salary values in the agent table, and the number of rows in that table. b. (5 points) Give an estimate for the number of rows in agent with salary < 75000, assuming a uniform distribution of salaries between min and max salary. Explain how you derived your estimate. c. (5 points) Find the 25th, 50th and 75th percentile values for salaries in the agent table. (The 50th percentile value, for instance, is the smallest number s such that 50% of the rows have salary value less than or equal to s.) d. (5 points) Give an estimate of the number of rows in agent with salary < 75000, assuming in a uniform distribution in each quartile determined in c. Explain how you derived your estimate. e. (5 points) How many rows in agent actually have salary < 75000?

Question 3: Query Plans

For each SQL statement below, draw the query plan that Postgres chooses (which you can obtain with the EXPLAIN command). For each plan, suggest a reason that the particular join algorithms were chosen.

a. (10 points) SELECT A1.last, A2.last FROM agent A1, agent A2, languagerel LR, Language L WHERE A1.salary < A2.salary AND A2.agent_ID = LR.agent_ID AND LR.lang_ID = L.lang_ID AND L.language = 'French';

b. (10 points)

SELECT A1.last, A2.last FROM agent A1, agent A2, languagerel LR, Language L WHERE A1.salary = A2.salary AND A2.agent_ID = LR.agent_ID AND LR.lang_ID = L.lang_ID AND L.language = 'French'; c. (10 points)

SELECT A1.last, A2.last FROM agent A1, agent A2, languagerel LR, Language L WHERE A1.salary > A2.salary AND A2.agent_ID = LR.agent_ID AND LR.lang_ID = L.lang_ID AND L.language <> 'French';

Note: You can find info on the EXPLAIN command at https://www.postgresql.org/docs/9.6/static/performance-tips.html

Question 4: Recovery (10 points)

There have been proposals to use multiple log files for recovery. Log records can be appended to any one of the files, but all records from the same transaction must go to the same file. Give one advantage of multiple log files and one disadvantage.

Question 5: Decomposition

Consider the following relational schema:

viols(VID VT VD InD BID SNu SNa SCo Bro BrI Zip).

(The names are short for Violation ID, Violation Type, Violation Description, Inspection Date, Building ID, Street Number, Street Name, Street Code, Borough, Boro ID, Zip Code.)

Assume the following functional dependencies hold on violations.

VID ® VT VD InD BID SNu SNa SCo Bro BrI Zip

BID ® SNu SNa SCo Bro BrI Zip

Bro ® BrI

BrI ® Bro

VT ® VD

VD ® VT

SCo ® SNa

SNu SCo Zip ® Bro

a. (15 points) Show a decomposition of violations into BCNF. Show

each step in your decomposition and the keys for each relation scheme. (You can have more than one key per scheme.) b. (5 points) Find a functional dependency in the original scheme that does not correspond to a key in your normalized scheme. c. (10 points) Is it possible that a legal (satisfies all keys) database instance d on your normalized scheme violates the FD in b., in the sense that if you join all the relations in d together, the result r violates the FD? Explain why or why not.