$$Problem Set #5, Fall 2010 mcmillan / Version 19
Comp 521: Files and Databases -- Fall 2010
Homework Information : Some of the problems are probably too long to attempt the night before the due date, so plan accordingly. Late homework will penalized by a factor of 70.71% for each late class period. Feel free to work with others, but the work you hand in should be your own.
Question 1
For each of the following relations, tell which normal form it is (none, 1NF, 2NF, 3NF, or BCNF) and why. If it is less than 3NF, give an equivalent 3NF schema
A) Rentals [SailorId, SailorName, BoatId, Date]
[SailorId, BoatId, Date] is the primary key. SailorId → SailorName.
B) ShimpmentUpdates [TrackingNumber, Datetime, FacilityId, Status, ResponsibleEmployee]
[TrackingNumber, Datetime] is the primary key.
[TrackingNumber, Datetime, FacilityId] → ResponsibleEmployee
C) Customers [Id, Name, Address, PhoneNumber]
PhoneNumbers is a comma-delimited list. Id and name are keys. There are no other FDs.
D) TeachingSchedule [Dept, CourseNo, SemesterId, ProfessorId]
[Dept, CourseNo, SemesterId] is the primary key. ProfessorId → Dept.
E) Genotype [MouseId, Chromosome, Position, Value, BaseType]
The primary key is [MouseId, Chromosome, Position]. Value → BaseType.
Question 2
Consider the following schema:
Alumni (First, Last, Year, Address, State, Zip, HomePhone, MobilePhone ) = F L Y A S Z H M
With these five functional dependencies:
D1 : F L Z → M
D2 : Z → S
D3 : F L A → H
D4 : H → Z L
D5 : F L → Y A S
A) Show that FL is a key for Alumni
B) Find a minimal cover for these functional dependencies.
C) Using the result from part A, find a 3NF lossless-join dependency-preserving decomposition
D) Find a lossless-join BCNF decomposition.
Question 3
Consider the following schema:
Supplier (sid : integersname : text, address : text) Part (pid : integer, sid:integer , pnamecost : real, num_avail : integer)You are told that the following three queries are extremely important:
Finding the total number of parts available from all suppliers of a given part speficied by name
Listing the names of parts with the highest cost
Computing the value of each supplier's inventory (Σp=parts available from supplier p.cost*p.num_avail)
A) Describe the indices and file layout that you would use for each relation. Note the queries addressed by each of your index and clustering choices.
Question 4
Which of the following schedules are serializable?
A) R1 (x ) R2 (y ) R1 (z ) R3 (z ) R2 (x ) R1 (y ) B) R1 (x ) W2 (y ) R1 (z ) R3 (z ) W2 (x ) R1 (y ) C) R1 (x ) W2 (y ) R1 (z ) R3 (z ) W1 (x ) R2 (y ) D) R1 (x ) R2 (y ) R1 (z ) R3 (z ) W1 (x ) W2 (y ) E) W1 (x ) R2 (y ) R1 (z ) R3 (z ) R1 (x ) W2 (y )
For each non-serializable schedule from above show that Strict 2PL disallows it.
Question 5
Write a function in Python that takes as parameters
- a string representing the attributes of a table
- a list of (string, string) tuples representing functional dependencies.
(For instance, AB → C would be represented as ("AB", "C") )
"CSJDPQV", [("SD", "P"), ("J", "S"), ("JP", "C")]
(This is the example from lecture 20 slide 27.) Also show the result of running it on
"ABCDEFGH", [("A", "B"), ("ACD", "E"), ("EF", "GH")]
Posted by jbrian on 2010-12-06 05:25:13 (references Version 19)
For question 5, the BCNF decomposition must be lossless-join, but it need not be dependency-preserving. There may be more than 1 such decomposition. Also, "lecture 20 slide 27" should say "lecture 19 slide 26".