CSCI 370 Spring 2019 – Assignment 4
Due: 11:30am, 10 April 2019, Wednesday
This assignment is worth 6% of your overall course grade.
Questions:
1. Functional Dependencies
Which of the following relation instances satisfies the functional dependency (name -> price)?
2. Relation Instance A
3. code
4. name
5. price
6. 1001
7. flower
8. 8.50
9. 1002
10. clothes
11. 29.99
12. 1003
13. pizza
14. 3.00
15. 1004
16. clothes
17. 39.99
18. 1005
19. water
20. 1.29
21.
22. Relation Instance B
23. code
24. name
25. price
26. 1001
27. pizza
28. 7.50
29. 1002
30. flower
31. 12.50
32. 1002
33. clothes
34. 39.99
35. 1003
36. clothes
37. 39.99
38. 1004
39. water
40. 1.29
41.
42. Relation Instance C
43. code
44. name
45. price
46. (empty relation)
47. Normal Forms
Given a relation with schema R(A, B, C, D, E) and a set of FD’s F = {A -> BC, E -> D, B -> E, CE -> A}.
a. List all the candidate keys of R?
b. R is not in BCNF. Why?
c. find a lossless join decomposition to decompose R into collections of relations that are in BCNF.
d. Is R in third normal form?
48. Security
Assume that you are the DBA of a company and created a relation called Employees with attributes empName, deptName and salary
a. Define a view called DeptInfo with attributes deptName and avgsalary which lists the average salary of employees working for each department.
b. You want a user with the user name “archor” to be able to read the relation Employees and update records in Employees but not add records into or delete records from Employees, what privilege(s) should you grant to “archor”? Show the appropriate command.
c. If you want the user “archor” to have the authority to allow other users to read the Employees table, how should you grant the privilege to “archor”? Show the appropriate command.
49. Transaction Management
For each of the following two schedules:
i. r3(B);r3(A);w3(A); r1(C);r1(B);r2(A); w2(A);w1(C);w1(B); w3(C);
ii. r2(D);r2(A);w2(D); r4(B);r1(C);r3(C); r4(D);w4(D);w4(B); r3(B);w3(C);r1(A); w1(A);
50. Answer the following questions:
a. Draw the precedence (serialization) graph for the schedule.
b. Is the schedule conflict-serializable? If your answer is yes, list all the equivalent serial schedules. If your answer is no, why?
c. Is the schedule cascadeless? Justify your answer.
51. Transactions and Lock Management
Consider the following actions taken by transaction T1 on database objects x and y: r1(x);w1(x);r1(y);w1(y);C1
a. Give an example of another transaction T2 such that, if run concurrently to transaction T1 without some form of concurrency control, it could interfere with T1 (i.e., anomalies could happen).
b. Explain how the use of Strict 2PL would prevent interference between the two transactions.
52. Recovery
When a database system restarts, the following log file is loaded into the system.
53. Start of the log ==>
54. A, begin
55.
56. A, u, 301.5, 327.3
57.
58. A, v, ‘TRUE’, ‘FALSE’
59.
60. B, begin
61.
62. B, w, 17, 11
63.
64. A, u, 327.3, 314.2
65.
66. B, x, 70, 35
67.
68. B, w, 11, 20
69.
70. C, begin
71.
72. C, x, 35, 60
73.
74. C, abort
75.
76. B, commit
77.
78. B, end
79.
80. D, begin
81.
82. C, end
83. End of the log ==>
84. D, w, 20, 35
a. Inferring from the above WAL log, try to determine which isolation level (serializable, repeatable read, read committed or read uncommitted) the database ran on before the crash. Briefly justify your answer.
b. Can the scheduler using strict 2PL (strict two phase locking) protocol generate a schedule that’s consistent with the above WAL log? How about if the scheduler used 2PL (two phase locking) protocol? Justify your answer.
c. Regardless whether the schedule is a cascadeless schedule, if the recovery manager still uses ARIES algorithm to recover from the crash, what would be the values stored in the database objects u, v, w and x respectively after the recovery is successfully completed?
85. Indexing
The data pages of an instance of a hypothetical relation T with three attributes A, B and C are shown in the next page. Assume that a B+ tree internal node can store at most 4 values and 5 pointers and its leaf node can store at most 4 data items and 2 pointers (to doubly link the leaf nodes together). Also assume that there is already a clustered (sparse) B+ tree index built on the relation T using attribute C as the search key.
You are asked to build another B+ tree index on T using attribute A as the search key. Can you build this index as a clustered (sparse) index or a non-clustered (dense) index? Draw this B+ tree index.
86. A
87. B
88. C
89. 1
90. 2
91. 34
92. 3
93. 18
94. 32
95. 5
96. 26
97. 30
98. –
99. –
100. –
101.
102. 7
103. 16
104. 28
105. 9
106. 4
107. 26
108. 11
109. 24
110. 24
111. –
112. –
113. –
114.
115. 13
116. 12
117. 22
118. 15
119. 32
120. 20
121. 17
122. 6
123. 18
124. 19
125. 14
126. 16
127.
128. 21
129. 30
130. 14
131. 23
132. 8
133. 12
134. 25
135. 20
136. 10
137. 27
138. 34
139. 8
140.
141. 29
142. 10
143. 6
144. 31
145. 28
146. 4
147. 33
148. 22
149. 2
150. –
151. –
152. –
153.
How to Submit
Submit a hard copy of your solution before the submit deadline. Make your answer precise and concise. Make your document easily understandable.
If you prefer to submit your assignment electronically, you can login to otter and go to the directory that has the file(s) you want to submit, and run the following command:
~liuh/bin/submit 370 A4 .
You can check what you have submitted for this assignment by running the following command:
~liuh/bin/checksubmit 370 A4
Currently, the submit script accepts any file with one of the following extension names: .pdf or .txt. If you want to submit any file with other extension names, please contact the instructor before you submit.
Remember that the electronic submission has a hard submit deadline at 11:30am, 10 April 2019, Wednesday.