McMaster University
SE 3DB3 Fall 2016 Assignment 3
Due: November 28, 2016 at 11:59pm
Michael Liut October 12, 2016
I. Database Design (55 marks) Question 1 (6 marks)
Consider a relation R(A,B,C,D,E,F), and functional dependency F : A → BCDEF, that holds over R.
(a) [6 marks] Define two other functional dependencies F1 and F2, which satisfy the following three properties:
i. Neither F1 nor F2 can be inferred from F using Armstrongs axioms. ii. Relation R with functional dependencies F and F1 is in BCNF.
iii. Relation R with functional dependencies F, F1, and F2 is in 3NF but not in BCNF.
State your two FDs F1 and F2, and justify how your FDs satisfy the above properties. Question 2 (12 marks)
Consider a relation R(A,B,C,D,E,F). Now, consider the decomposition of R into R1(ABCD) and R2 (DEF).
(a) [4 marks] Give a set of functional dependencies (FDs) such that the decomposition into R1 and R2 is lossless join and dependency preserving. Justify why your FDs satisfy the criteria.
(b) [4 marks] Give a set of functional dependencies such that the decomposition into R1 and R2 is lossless join, but not dependency preserving. Justify why your FDs satisfy the criteria.
(c) [4 marks] Give a set of functional dependencies such that the decomposition into R1 and R2 is not lossless join, but dependency preserving. Justify why your FDs satisfy the criteria.
1
Question 3 (15 marks)
You have been contracted by McMaster University to design a better schema for its current TimeTable relation. Specifications are as follows:
TimeTable (course, room, day, time, professor, ta)
where:
course represents the course code, room represents the room the course is held in, day represents the day of the week the course is offered, time represents the time of day the course is held, professor represents the name of the course instructor, and ta represents the name of the head TA of the course.
From the TimeTable relation, you are required to represent the following additional informa- tion:
a) A course/day/time combination uniquely determines the professor. b) No two rooms can be assigned the same course, day, and time.
c) No two rooms have the same professor/day/time combination.
d) There is at most one lead TA per course.
e) Two courses cannot share the same room/day/time combination.
f) Twodistinctcoursescannothavethesameprofessorteachingatthesamedayandtime.
g) Two professors cannot share the same room/day/time combination.
Answer the following questions:
1. What are the functional dependencies that can be inferred from the additional information? List all of them.
2. McMasterwillonlybesatisfiedifyourdesignisagoodone,i.e.,theschemasatisfieseither the 3NF or the BCNF.
Is the design of your schema with the functional dependencies from part (1) above a good one? Justify your answer. If the design is not a good one, provide a better one, using one of the decomposition algorithms discussed in class.
Question 4 (22 marks)
Consider a relation schema R with attributes A = {A, B, C, D, E, F, G, H} and the set of func- tional dependencies:
F = {A → B, ABD → FGH, AEH → BD, BC → EH, C → ACG, C → AFH,
DE → HB, DF → AC, E → F, H → EA}.
(a) [7 marks] Find all candidate keys (i.e., minimal keys) of relation R. Show all the steps you took to derive each key, and clearly state which of Armstrongs axioms are used in each step.
2
(b) [15 marks] Find a minimal cover (also known as a minimal basis, or a canonical cover). Give your FDs in alphabetical order. Provide a 3NF decomposition of relation R, and indi- cate the key(s) for each relation. You must include all steps in your solution.
(Refer to Section 8.4.3 of the textbook and the reference document mincover- FDDublin.pdf, which both provide further details on how to compute a minimal cover.)
II. Transactions and Concurrency (25 marks) Question 5 (10 marks)
(a) [5 marks] Give an example of a transaction schedule that is conflict-serializable, but which is not possible using 2PL. In other words, the schedule should be conflict-serializable, but there should be no way to acquire and release read/write locks in a way that is consistent with the 2PL protocol.
(b) [5 marks] Is every schedule that is allowed under the Strict 2PL locking protocol also allowed under the 2PL locking protocol? Or vice versa? Give an example schedule that is allowed in one of the two locking protocols, but not in the other locking protocol.
Question 6 (15 marks)
This question requires you to execute a few concurrent transactions against a banking table named accounts, displayed in Table 1 below. Create the accounts table in DB2. You may assume username is of type char(10), name is char(20), and balance is of type deci- mal(10,2). Write the appropriate INSERT INTO statements to load the four records shown into your accounts table.
Table 1: accounts
Setup
You will simulate concurrent database queries, using two different database connections, against the accounts table. You will open two terminal sessions, and execute the following commands to prepare your environments. For simplicity we will call the two sessions, A and B.
username
name
balance
ana
Anakin
3250.00
chewy
Chewbacca
5750.00
pad
Padme ́
350.00
r2d2
R2-D2
1450.00
3
In Session A
1. Invoke db2 using db2 +c. This command turns off the AUTO COMMIT feature in DB2. You will now be at the DB2 command line.
2. Verify AUTO COMMIT is turned OFF by running the command list command options. You should see “Auto-Commit OFF”in the second entry of the table.
3. Change the transaction isolation level to ‘Read Stability’ by running the command change isolation to rs.Transactionisolationlevelsdefinethedegreeofac- cess and interaction among a set of concurrent transactions which operate against the same data. Please see the DB2 reference for more information on isolation levels in DB2.
4. Connect to your database.
In Session B
1. Invoke DB2 by typing db2 (do not turn AUTO COMMIT off). 2. Run change isolation to rs.
3. Connect to your database.
Transactions
Run the following commands (in the given order) and provide your answers to the stated ques- tions.
1. In Session A, insert the record (‘yoda’, ‘Yoda’, 6000.00), followed by a select * from accounts.
2. In Session B, run select * from accounts. Is the output you get the same or dif- ferent than in (1)? Why did this occur? What is a possible solution?
3. Return to Session A, and implement your solution from the previous step.
4. In Session B, do the SELECT * query again (to list all records). Provide your output.
5. We will update accounts from two different transactions. In Session A, change the isolation level to cursor stability (CS). In Session B, change the isolation level to uncommitted read (UR). (You will have to disconnect and reconnect to the database.)
6. In Session A, transfer $750 from Anakin’s account into Chewbacca’s account.
7. In Session B, list all accounts and their balances. Then issue a $300 transfer from Padme ́’s
account to Chewbacca’s account. What happens and why?
8. Commit the transaction in Session A. What is Chewbacca’s balance now?
9. Change the transaction isolation level in Session A to ‘Uncommitted Read’.
10. Now, in Session A, transfer 80% of Chewbacca’s account balance to R2-D2’s account. Commit the transaction.
4
11. In Session A, transfer 50% of Yoda’s funds to R2-D2’s account. In Session B, list all data records. What is R2-D2’s balance? Does it reflect the latest transfer from Yoda? Based on your transaction in step (7) and this step, what can you say about the allowed actions in CS and UR isolation levels? How do these compare with the RS isolation level?
12. Abort the Yoda to R2-D2 transfer transaction in Session A, by executing the command rollback.
13. In Session A and B, list all data records. What are the final balances for each user?
Grading
This assignment is worth 15% of your final grade in this course. A request for re-mark of an as- sessment must be submitted to the course instructor with the completed re-mark form within 7-days (seven days) of being returned.
Submission
All files are to be submitted using the Avenue to Learn platform (avenue.mcmaster.ca). Please ensure you submit all files with the correct names, as described below. Your submissions must be typed and clearly legible. You must include your name and student ID number in all files. Upload four files with theindicatedfileextensions(nocompressionbased.tar, .zip, .rarfiles).
You are to submit all your solutions to the questions above in one file: asg3.pdf.
Plagiarism
Please refer to the course outline and introduction slides. To serve as a reminder: Turnitin will be used for all written work and MOSS for all code submissions. McMaster’s policy on Academic Integrity: http://www.mcmaster.ca/academicintegrity/students/typeofad/plagiarism/
5