Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems Page 1 of 12 This exam paper must not be removed from the venue School of Information Technology and Electrical Engineering EXAMINATION Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems This paper is for St Lucia Campus students. Examination Duration: 120 minutes Reading Time: 10 minutes Exam Conditions: This is a Central Examination This is a Closed Book Examination – specified materials permitted During reading time – write only on the rough paper provided This examination paper will be released to the Library Materials Permitted In The Exam Venue: (No electronic aids are permitted e.g. laptops, phones) Calculators – Casio FX82 series or UQ approved (labelled) Materials To Be Supplied To Students: Instructions To Students: Additional exam materials (eg. answer booklets, rough paper) will be provided upon request. Please answer all questions on the examination paper. For Multiple Choice Questions, please circle a single answer. Total Marks: 100 (to be scaled down to 60) Venue ____________________ Seat Number ________ Student Number |__|__|__|__|__|__|__|__| Family Name _____________________ First Name _____________________ For
Examiner
Use
Only
Question
Mark
Total
________
Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems Page 2 of 12 Question 1 [4 marks] Which of the following is a false statement about B+ trees? A. B+-trees are balanced B. non-leaf nodes include direct pointers to data records C. insertion of a key can lead to node splitting D. deletion of a key can lead to node coalescing Question 2 [4 marks] Which of the following factors determines the size of a bitmap index on an attribute “X” in relation “R”? A. The number of distinct values in “X” B. The number of tuples in “R” C. The data type for attribute “X” D. Answers A & B above E. Answers A & B & C Question 3 [4 marks] Which of the following is a false statement about cost- based query optimization? A. It selects a query plan in a shorter time than heuristic-based optimization B. It requires estimating the execution cost of a query plan C. It selects the query plan with the minimum execution cost D. All of the above Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems Page 3 of 12 Questions 4-5 Consider the following relation: Make Model Color Price Honda Accord Blue Medium Honda Civic Red Low Toyota Corolla Black Low Toyota Camry Red Medium Question 4 [4 marks] Assume the relation shown above and a bitmap index is created on attribute ‘Price’. The total number of bits required for that index is: A. 2 B. 4 C. 8 D. 12 Question 5 [4 marks] Again, assume the relation shown above, what is the bitmap corresponding to the value ‘Honda’. A. 1 1 0 0 B. 1 1 C. 1 0 1 0 D. 0 0 Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems Page 4 of 12 10 TREE-STRUCTURED INDEXING Exercise 10.1 Consider the B+ tree index of order d = 2 shown in Figure 10.1. 1. Show the tree that would result from inserting a data entry with key 9 into this tree. 2. Show the B+ tree that would result from inserting a data entry with key 3 into the original tree. How many page reads and page writes does the insertion require? 3. Show the B+ tree that would result from deleting the data entry with key 8 from the original tree, assuming that the left sibling is checked for possible redistribu- tion. 4. Show the B+ tree that would result from deleting the data entry with key 8 from the original tree, assuming that the right sibling is checked for possible redistribution. 5. Show the B+ tree that would result from starting with the original tree, inserting a data entry with key 46 and then deleting the data entry with key 52. 6. Show the B+ tree that would result from deleting the data entry with key 91 from the original tree. Root 32*39* 41*45* 52* 58* 73* 80* 91*99* 8573 50 27*18*10*8*6*5*2*1* 8 18 32 40 Figure 10.1 Tree for Exercise 10.1 122 Questions 6-8: Consider a B+ tree index as shown in figure, where index nodes are labeled: N1, N2, …, N11. Also, assume the following rule applies for redistributing keys after a leaf node split: Three keys stay in the old leaf node and the remaining keys move to a new leaf node. Question 6 [4 marks] Which nodes in the B+ tree index that must be fetched to answer the query: “Get all records with key greater than 30 and less than 75” A. N1 N2 N6 N7 N8 N9 N10 B. N1 N2 N7 N8 N9 C. N1 N3 N7 N8 N9 D. N1 N3 N7 N8 N9 N10 Question 7 [4 marks] What is the number of leaf nodes after inserting an entry with key “3”? A. 8 B. 9 C. 11 D. 12 Question 8 [4 marks] What is the number of non-leaf nodes after inserting an entry with key “3”? A. 3 B. 4 C. 11 D. 12 N3 N2 N5 N6 N7 N8 N9 N10 N11 N4 N1 Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems Page 5 of 12 Questions 9-11 Given two relations R1 and R2, where R1 contains N1 tuples, R2 contains N2 tuples, and N2 > N1 > 0, answer the following questions. Question 9 [4 marks] The minimum and maximum number of tuples produced from R1 ∪ R2 is: A. minimum 0, and maximum N1+N2 B. minimum N1, and maximum N2 C. minimum N1, and maximum N1+N2 D. minimum N2, and maximum N1+N2 Question 10 [4 marks] The minimum and maximum number of tuples produced from R1 X R2 is: A. minimum 0, and maximum N1*N2 B. minimum N1, and maximum N1+N2 C. minimum N1*N2, and maximum N1*N2 D. minimum N2, and maximum N1+N2 Question 11 [4 marks] Assume relation R1 contains an attribute named x, the minimum and maximum number of tuples produced from σx=5 (R1) is: A. minimum 0, and maximum N1 B. minimum N1, and maximum N1 C. minimum 1, and maximum N1 D. minimum N1, and maximum N2 Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems Page 6 of 12 Questions 12-13: Suppose we have two unary (one attribute only) relations, R and S as shown below. Use R for the outer loop and S for the inner loop. R S 7 8 2 4 9 2 8 1 3 3 9 2 1 7 3 3 6 Question 12 [4 marks] Assume a natural join between R and S using Nested Loop join (one tuple at a time). The first five results of that join in the order that they would be produced by the nested loop is: A. 7, 2, 8, 3, 1 B. 7, 2, 2, 8, 3 C. 7, 2, 8, 3, 3 D. None of the above Question 13 [4 marks] Again, assume a natural join between R and S using Nested Loop join (one tuple at a time). The number of iterations needed to finish this join operation is: A. 1 B. 8 C. 9 D. 5 Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems Page 7 of 12 Questions 14-15 Consider the relation Student(Id, Major, Status), which has: • A B+ tree index on Major and no other indexes. • 10,000 tuples of data spread over 100 different blocks. • The domain of Status has 9 values and that of Major has 10 different values. Question 14 [4 marks] What is the estimated number of results returned by the expression σ Major=′IT′ (Student): A. 10 B. 100 C. 1,000 D. 10,000 E. None of the above Question 15 [4 marks] What is the selectivity of the expression σ Major=′IT′ OR Major=”CS” (Student): A. 0.0 B. 0.1 C. 0.2 D. 1 E. None of the above Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems Page 8 of 12 Question 16 [4 marks] Which of the following is a correct statement about transactions? A. Redo is needed for atomicity B. Undo is needed for durability C. Concurrency Control is realized using Triggers and Assertions D. Deadlocks do not occur in serial executions E. None of the above. Question 17 [4 marks] Which of the following transaction schedules does not contain conflicting operations? Recall that r = read and w = write. A. r1 (A), r2 (A), w1 (C), r1 (B), r2 (B) B. r1 (A), r1 (B), w1 (A), r2 (B), r2 (A), w2 (A) C. r1 (A), w1 (A), r1 (B), w1 (B),
r2 (A), w2 (A), r2(B), w2(B) D. r1(A), w1(A), r2(B), w2(B), r2(A), w2(A), r1 (B), w1 (B) E. All (A)-(D) contain conflicts Question 18 [4 marks] The write-ahead logging (WAL) protocol simply means that: A. writing of a data item should be done ahead of any logging operation. B. the log record for an operation should be written before the actual data is written. C. all log records should be written before a new transaction begins execution. D. the log never needs to be written to disk. Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems Page 9 of 12 Question 19 [4 marks] If a database system supports ACID properties for transaction execution, which of the following pairs of values is a possible result for A and B, after executing the below transactions T1 and T2 concurrently, with an initial value of A=100 and B=200? 8 [3 points] Which of the following is a correct statement about transactions? A. Redo is needed for atomicity B. Undo is needed for durability C. Concurrency Control is realized using Triggers and Assertions. D. Deadlocks do not occur in serial executions E. None of the above. ANSWER: D 9 [3 points] Which of the following transaction schedules does not contain conflicting opera- tions? Recall that r = read and w = write. A. r1(A), r2(A), w1(C), r1(B), r2(B) B. r1(A), r1(B), w1(A), r2(B), r2(A), w2(A) C. r1(A), w1(A), r1(B), w1(B), r2(A), w2(A), r2(B), w2(B) D. r1(A), w1(A), r2(B), w2(B), r2(A), w2(A), r1(B), w1(B) E. All (A)-(D) contain conflicts ANSWER: A 10 [4 points] Which of the following is a correct statement about the two transactions schedules H3 and H4? Recall that r = read and w = write. H3= r1(x), r3(z), w1(y), r2(x), w1(z), w2(x), r2(y), w2(y) H4= r1(x), w3(z), w1(z), r2(x), w1(y), r2(y), w2(x), w2(y) A. Have different serialization order and they are not conflict equivalent. B. Have different serialization order and they are conflict equivalent. C. Have same serialization order and they are not conflict equivalent. D. Have same serialization order and they are conflict equivalent. E. None of the above ANSWER: C 11 [4 points] If a database system supports ACID properties for transaction execution, which of the following (A)-(D) pairs of values is a p s- sible result for A and B, after executing the be- low transactions T1 and T2 concurrently, with an initial value of A=100 and B=200? T1: read(B) B=B+50 write(B) read(A) A=A-50 write(A) T2: read(B) tmp=B*0.1 B=B-tmp write(B) read(A) A=A+tmp write(A) A. A=70 , B=230 B. A=50 , B=180 C. A=120 , B=250 D. A=50 , B=250 E. None of the above ANSWER: A A B C D a1 10 5 x a2 20 5 y a3 10 10 z a4 20 5 z Figure 3: Relation r4 12 [3 points] Assume relation r4 (Fig. 3) and query B=20. The selectivity of that query is: A. 0% B. 25% C. 50% D. 75% E. 100% ANSWER: C 13 [3 points] Assume relation r4 (Fig. 3) and a bitmap index is created on attributeD. The total number of bits required for that index is: A. 1 B. 3 6 A. A=70 , B=230 B. A=50 , B=180 C. A=120 , B=250 D. A=50 , B=250 E. None of the above Question 20 [4 marks] If a steal/no-force buffer management policy is in place, which of the following is true about system recovery? A. Both the Redo and Undo operations are needed B. Neither the Redo nor the Undo operations is needed C. Redo is needed but Undo is not needed D. Redo is not needed but Undo is needed Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems Page 10 of 12 Question 21 [6 marks]: You are given the following tables: Student(StudId, Name, Addr, Status) Transcript(Id, CrsCode, Semester, Grade) Consider a query that outputs the names of all students who took INFS2200 in 2017. An execution plan for that query can be expressed as follows: πName(σId=StudId AND CrsCode=′INFS2200′ AND Semester=′2017′ (Student × Transcript)) In the following, fill in the missing subscripts of the different operators (i.e., Π, σ, I) so that to create an optimized plan that is equivalent to the one above. ΠNAME [ (Π−−−−−−−−−−−−−−−−− Student) −−−−−−−−−−−−−−−− (σ−−−−−−−−−−−−− (Π−−−−−−−−−−−−−− Transcript)) ] Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems Page 11 of 12 Question 22 [6 marks]:: Consider the following sequences of actions, listed in the order they are submitted by transactions T1, T2, and T3. Question 3 [20 points] Serializability and Recoverability Consider the following classes of schedules: serializable, conflict-serializable, recoverable, avoids-cascading-aborts (same as cascadeless), and strict. For each of the following schedules, state which of the preceding classes it belongs to. It is important to note that serializability concerns only committed transactions while recoverability concerns both committed and aborted transactions. Furthermore, when we talk about recoverability, we assume that at any point of the schedule, a transaction may be aborted due to errors. Even if we annotate a transaction with a commit, it should be interpreted as an “intended commit” — in practice, it can commit if no errors occur. The actions are listed in the order they are scheduled and prefixed with the transaction name. (1) T1:R(A), T2:W(A), T1:W(A), T2:Abort, T1:Commit (2) T1:W(A), T2:R(A), T1:W(A), T2:Commit, T1:Commit Answer: (5 points each) (1) It is serializable, conflict-serializable; It is recoverable and avoids cascading aborts; It is not strict. (2) It is not serializable, not conflict-serializable; It is not recoverable, therefore not avoid cascading aborts, not strict. Ques ion 4 [40 points] Concurrency Control Protocols Consider the following sequences of actions, listed in the order they are submitted to the DBMS: T1: R(A) W(B) (Commit) T2: W(A) W(B) (Commit) T3: W(B) (Commit) For each sequence and for each of the following concurrency control mechanisms, describe how the concurrency control mechanism handles the sequence. Assume that the timestamp of transaction Ti is i. For lock-based concurrency control mechanisms, add lock and unlock requests to the previous sequence of actions as per the locking protocol. The DBMS processes actions in the order shown. If a transaction is blocked, assume that all its actions are queued until it is resumed; the DBMS continues with the next action (according to the listed sequence) of an unblocked transaction. time Describe how strict 2PL with deadlock detection (assume wait-for-graph is used) executes this sequence of actions. Specifically, complete the sequence listed below to show the lock and unlock requests made by these transactions as well as the blocked and unblocked operations. If a transaction is blocked, assume that all its actions are queued until it is resumed; the DBMS continues with the next action of an unblocked transaction. T1 acquires shared-lock on A. T2 blocks waiting for an exclusive-lock on A. … Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems Page 12 of 12 Question 23: For each of the following schedules: 1) construct a precedence graph, 2) determine if the schedule is conflict serializable, and 3) determine the equivalent serial schedule. (a) [4 marks] r1(X); r3(X); w1(X); r2(X); w3(X) (b) [4 marks] r3(X); r2(X); w3(X); r1(X); w1(X) END OF EXAMINATION
