辅导案例-CS 348-Assignment 6
CS 348: Assignment 6 for Sections 1 and 2 Spring 2020 (due by 11pm EDT on Monday, August 3rd) Overview This assignment consists of four questions. As an aid to scheduling your work on this assignment, you should plan on spending about four hours total on the questions. Question 1. Assume the DBA group has chosen the following standard physical design (as defined in Module 10) for the relational database schema for bibliography information given on Slide 10 of Module 2: • A primary index called T-A is chosen for each table T , where a is the attribute name of the first column of T . The chosen data structure in each case is a Btree on a. For example, the primary index of table WROTE is called WROTE-AUTHOR and is a Btree on author, and, for querying, has arity 3: WROTE-AUTHOR / (rid, author, publication). Like all indices, recall that attribute rid is prepended to the list of attributes for WROTE-AUTHOR. • A secondary index called WROTE-PUBLICATION is chosen for table WROTE that is a Btree on attribute publication, and, for querying, also has arity 3 WROTE-PUBLICATION / (rid, publication, wrote-author-rid). 1 Recall that there is a foreign key on attribute wrote-author-rid to attibute rid of primary key table WROTE-AUTHOR. • A secondary index called ARTICLE-APPEARS-IN is chosen for table ARTICLE that is a Btree on attribute appears-in, and, for querying, has arity 3 ARTICLE-APPEARS-IN / (rid, appears-in, author-pubid-rid). Translate each of the following queries in SQL to an RA expression over this physical design, that is, in which all relation names are names of indices. Your RA expression should be as efficient as possible, assuming the implementation of operations and simple cost model given in Module 10. For example, you should consider using nested index scans. Recall from Slide 39 of Module 10 that these are expressed with the syntax E × σ#i=#j`(R), where #j refers to a column of a subexpression E and where R is an index for which #i is its rid column or its search key column (i.e., either column #1 or #2 for the primary index WROTE-AUTHOR). 1. Names of all authors of books published in 2019 last year. select distinct name from AUTHOR a where exists ( select * from WROTE w, BOOK b where w.publication = b.pubid and w.author = a.aid and b.year = 2019 ) 2. All publication identifiers of articles appearing in volume 1 number 1 of the journal ACM TODS. select distinct pubid from ARTICLE a where exists ( select * from JOURNAL j, PUBLICATION p where j.pubid = p.pubid and p.title = 'ACM TODS' and j.volume = 1 and j.number = 1 and a.appears-in = j.pubid ) 2 Question 2. Determine whether or not each of the following four transaction execution schedules is conflict serializable. If a schedule is conflict serializable, specify a serial order of transaction execution to which it is equivalent. S1 = r1[x], r2[y], w2[x], r1[z], r3[z], w3[z], w1[z] S2 = w1[x], w1[y], r2[u], w2[x], r2[y], w2[y], w1[z] S3 = w1[x], w1[y], r2[u], w1[z], w2[x], r2[y], w1[u] S4 = w1[x], w2[u], w2[y], w1[y], w3[x], w3[u], w1[z] Question 3. Consider the following sequence of operations, where, e.g., c1 and a4 are commit and abort requests by transactions T1 and T4, respectively. If the database system uses strict two-phase locking, will any of these requests cause a transaction to block? If so, indicate which will block. Will deadlock occur? Taking blocking into account, and assuming operations for transactions that become unblocked are given priority, give an execution order which could result from these requests. r1[x], r2[x], w3[x], r2[y], r1[y], r1[z], c1, w4[z], c2, w5[z], a4, c3, c5 Question 4. Suppose that after a system failure, the transaction log looks as shown below (the log tail is at the bottom). Describe what the database system must do to recover from the system failure. Indicate which objects must be modified, and in what order those modifications occur. Indicate which transactions are committed and which are aborted after the failure recovery is complete. 3 T1, BEGIN T1, UNDO, x, 0 T1, REDO, x, 10 T2, BEGIN T2, UNDO, y, 10 T2, REDO, y, 20 T3, BEGIN T1, COMMIT T3, UNDO, x, 10 T3, REDO, x, 400 T4, BEGIN T3, UNDO, z, 0 T3, REDO, z, 100 T5, BEGIN T4, UNDO, a, 0 T4, REDO, a, 1 T6, BEGIN T4, ABORT T5, UNDO, a, 0 T5, REDO, a, 2 T3, COMMIT T6, UNDO, x, 400 T6, REDO, x, 0 T5, COMMIT T6, UNDO, a, 2 T6, REDO, a, 3 Assignment Submission Assignment submission should be a single file uploaded to dropbox on Learn. The file should be a pdf file that may be computer generated or a scan/photo of a handwritten solution, as long as it is legible. 4