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:!• 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.!!!Index_nameTable_nameAttribute_nameBlevelDistinct_keysDept_dnumberDEPARTMENTDnumber150Proj_PnumberPROJECTPnumber12000Proj_DnumPROJECTDnum250Chapter 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.!!T1 T2T3 T4T1 T2T3 T4(a) (b)T1 T2T3 T4T1 T2T3 T4(c) (d)T1 T2T3 T4T1 T2T3 T4(e) (f)T1 T2T3 T4T1 T2T3 T4T5(g) (h)T1 T2T3 T4T5(i)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 CJ2b.!!CJ2b ! = 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 CJ2c.!!CJ2c ! = 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
View Full Document
Unlocking...