辅导案例-CS 348-Assignment 6

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top
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
51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468