CS 6360 Final Exam Extra Practice Exercises Chapter 19 Query Optimization Consider the following join DEPARTMENT Dnumber Dnum PROJECT Using attribute values from Figure 19 8 in your textbook for reference including the info in the table below calculate the values of the following attributes Index name Table name Attribute name Blevel Distinct keys Dept dnumber DEPARTMENT Dnumber 1 50 Proj Pnumber PROJECT Pnumber 1 2000 Proj Dnum PROJECT Dnum 2 50 DEPARTMENT table Number of rows rD Number of blocks bD Blocking factor bfrD PROJECT table Number of rows rP Number of blocks bP Blocking factor bfrP DEPARTMENT Dnumber Dnum PROJECT Blocking factor of resulting join bfrDP Selectivity of join sl Selection Cardinality of join s Compare the cost difference between both DEPARTMENT as outer loop and PROJECT as outer loop and determine the more optimal cost of the two Hint Use variations of J2 for both directions Chapter 21 Transaction Processing 21 22 Which of the following schedules is conflict serializable For each serializable schedule determine the equivalent serial schedules a r1 X r3 X w1 X r2 X w3 X b r1 X r3 X w3 X w1 X r2 X c r3 X r2 X w3 X r1 X w1 X d r3 X r2 X r1 X w3 X w1 X 21 23 Consider the three transactions T1 T2 and T3 and the schedules S1 and S2 given below Draw the serializability precedence graphs for S1 and S2 and state whether each schedule is serializable or not If a schedule is serializable write down ALL of the equivalent serial schedule s If a schedule is non serializable write down ALL of the cycles T1 r1 X r1 Z w1 X T2 r2 Z r2 Y w2 Z w2 Y T3 r3 X r3 Y w3 Y S1 r1 X r2 Z r1 Z r3 X r3 Y w1 X w3 Y r2 Y w2 Z w2 Y S2 r1 X r2 Z r3 X r1 Z r2 Y r3 Y w1 X w2 Z w3 Y w2 Y Determine all equivalent serial schedules for each serialization graph Note that complete serialization graphs require item labels for each directed edge This exercise is only to practice identification of equivalent serial schedules a b T1 T2 T1 T2 T3 T4 T3 T4 c d T1 T2 T1 T2 T3 T4 T3 T4 e f T1 T2 T1 T2 T3 T4 T3 T4 T1 T2 g h T1 T2 T5 T3 T4 T3 i T1 T2 T5 T3 T4 T4 Answer Key Chapter 19 Query Optimization Consider the following join DEPARTMENT Dnumber Dnum PROJECT Using attribute values from Figure 19 8 in your textbook for reference calculate the values of the following attributes DEPARTMENT table Number of rows rD 50 Number of blocks bD 5 Blocking factor bfrD 50 5 10 PROJECT table Number of rows rP 2000 Number of blocks bP 100 Blocking factor bfrP 2000 100 20 DEPARTMENT Dnumber Dnum PROJECT Blocking factor of resulting join bfrDP 1 1 bfrD 1 bfrP 1 1 10 1 20 1 2 20 1 20 1 3 20 20 3 6 Selection Cardinality of join s sDnum rP rD 2000 50 40 projects in each join group assuming an even distribution Selectivity of join is js PROJ DEPT PROJ DEPT 2000 100000 1 50 0 02 Each join group selects 1 50th of the PROJECT records Compare the cost difference between both DEPARTMENT as outer loop and PROJECT as outer loop and determine the more optimal cost of the two Hint Use variations of J2 for both directions Using method J2b with DEPARTMENT as the outer loop PROJECT has a clustering index on Dnum so we can use C CJ2b J2b bD DEPT xDnum sDnum bfrP js DEPT PROJ bfrRS 5 50 2 40 20 1 50 50 2000 6 5 200 333 538 Using method J2c with PROJECT as the outer loop DEPARTMENT has a primary key on Dnumber so we can use C CJ2c J2c bP PROJ xB 1 js PROJ DEPT bfrRS 100 2000 1 1 1 50 50 2000 6 100 4000 333 4433 The first Join strategy with PROJECT as the outer loop is the more optimal Chapter 21 Transaction Processing 21 22 Which of the following schedules is conflict serializable For each serializable schedule determine the equivalent serial schedules a r1 X r3 X w1 X r2 X w3 X b r1 X r3 X w3 X w1 X r2 X c r3 X r2 X w3 X r1 X w1 X d r3 X r2 X r1 X w3 X w1 X Let there be three transactions T1 T2 and T3 They are executed concurrently and produce a schedule S S is serializable if it can be reproduced as at least one serial schedule T1 T2 T3 or T1 T3 T2 or T2 T1 T3 or T2 T3 T1 or T3 T1 T2 or T3 T2 T1 a This schedule is not serializable because T1 reads X r1 X before T3 but T3 reads X r3 X before T1 writes X w1 X where X is a common data item The operation r2 X of T2 does not affect the schedule at all so its position in the schedule is irrelevant In a serial schedule T1 T2 and T3 the operation w1 X comes after r3 X which does not happen in the question b This schedule is not serializable because T1 reads X r1 X before T3 but T3 writes X w3 X before T1 writes X w1 X The operation r2 X of T2 does not affect the schedule at all so its position in the schedule is irrelevant In a serial schedule T1 T3 and T2 r3 X and w3 X must come after w1 X which does not happen in the question c This schedule is serializable because all conflicting operations of T3 happens before all conflicting operation of T1 T2 has only one operation which is a read on X r2 X which does not conflict with any other operation Thus this serializable schedule is equivalent to r2 X r3 X w3 X r1 X w1 X e g T2 T3 T1 serial schedule d This is not a serializable schedule because T3 reads X r3 X before T1 reads X r1 X but r1 X happens before T3 writes X w3 X In a serial schedule T3 T2 and T1 r1 X will happen after w3 X which does not happen in the question 21 23 Consider the three transactions T1 T2 and T3 and the schedules S1 and S2 given below Draw the serializability precedence graphs for S1 and S2 and state whether each schedule is serializable or not If a schedule is serializable write down ALL of the equivalent serial schedule s If a schedule is non serializable write down ALL of the cycles T1 r1 X r1 Z w1 X T2 r2 Z r2 Y w2 Z w2 Y T3 r3 X r3 Y w3 Y S1 r1 X r2 Z r1 Z r3 X r3 Y w1 X w3 Y r2 Y w2 Z w2 Y S2 r1 X r2 Z r3 …
View Full Document
Unlocking...