12 Pages
Unlock Document

Electrical and Computer Engineering
ECE 356
Wojciech Golab

E&CE456: Database Systems (W2000) Department of Electrical and Computer Engineering University of Waterloo FINAL EXAMINATION SOLUTIONS INSTRUCTOR: Mattias Hembruch CLOSED BOOK, NO AIDS April 18, 2000 TIME ALLOWED: 3 Hours ANSWER ALL QUESTIONS It’s almost over!! person( pno, name, street, city, tel_no, postal_code) book( isbn, title, date, edition, book_type ) book_author( isbn, pno, position ) book_editor( isbn, pno, position ) book_keywords( isbn, kwd_no, position ) keyword( kwd_no, keyword ) where the “ position” field indicates the order in which the authors, editors and keywords are listed in the book. For example, the E&CE 456 textbook lists three authors in the following order: Silberschatz, Korth, Sudershan. Silberschatz would be assigned position 1, Korth position 2, and Sudarshan position 3. Similarly for editors and keywords. Note that a new revision of a book is assigned a new isbn, so that edition is NOT part of the primary key. Answer the following queries using the indicated query language (SQL = Structured Query Language, TRC = Tuple Relational Calculus, DRC = Domain Relational Calculus, RA = Relational Algebra). a) Find the Pno of all authors who have worked on at least 5 books [SQL] [3 marks] Select pno from book_author group by pno having count(pno) >= 5 If included checking book_editor, that’s also ok. b) Find the titles of all books that have the keyword “ databases” assigned to them. [DRC, RA] { | ∃ in, dt, ed, bt ( ∈ book /\ ∃ ( ∈ book_keywords /\ ∈ kw ( ∈ keyword /\ kw=’databases’ ) ) ) } ∏ (σ ( book ⊗ book_keywords ⊗ keyword) ) title title = ‘databases’ c) Find the address (street, city, postal_code) of the 2nd author of the book titled “ All about Databases” (you can assume the title is unique). [TRC] { t | ∃ b ∈ book, a ∈ book_author, p ∈ person ( b[isbn] = a[isbn] /\ a[position] = 2 /\ b[title] = “ All about Databases” /\ p[pno] = a[pno] /\ t[street]=p[street] /\ t[city]=p[city] /\ t[postal_code]=p[postal_code] d) Find all pairs of authors (return only two Pnos) such that the authors have worked on the same book, and they have they same postal code. Ensure that you do not include both (Pno_x, Pno_y) AND (Pno_y, Pno_x) in your solution. Also, ensure each pair of Pnos is returned only once. [SQL] SELECT Distinct a1.pno a2.pno FROM book_author AS a1, book_author AS a2, person AS p1, person AS p2 WHERE a1.pno = p1.pno AND a2.pno = p2.pno AND p2.postal_code = p1.postal_code AND a1.isbn = a2.isbn AND a1.pno > a2.pno ii) Convert the schema from part i) into an equivalent E-R diagram. Show all mapping cardinalities. city tel_no position isbn title date edition street postal_code book_type book name author book person pno book editor position book keyword position kwd_no keyword keyword iii) Consider the following set of functional dependencies: F = ( A->EF, B->DE, A->B, C->E, B->CD, C->D, A->C ) Find F c the canonical cover of F. B->CD, B->DE, D is extraneous Î B->CD, B->E A->B, A->EF but B->E, Î A->F B->CD, C->E, B->E Î B->E is extraneous B->CD (by decomposition, B->C), and A->C and A->B Î A->C is extraneous B->CD (by decomposition, B->C) and C->D, Î D is extraneous Canonical cover: A->B, A->F, B->C, C->E, C->D iv) Consider the set of attributes R = { A, B, C, D, E, F, G, H } and the set of functional dependencies F = { A->BDH, C->EF, G->H, H->C }. Perform a BCNF decomposition of R. State whether or not the decomposition is dependency preserving. Create: (A,B,D,H), (A,C,E,F,G) Create: (C,E,F), (A,B,D,H), (A,C,G) Not dependency preserving: G->H and H->C are not preserved. Question Two [13 marks] i) Consider the following schedule. Only the pertinent read (RD) and write (WR) instructions are shown with the target data item in parentheses. Time T1 T2 T3 T4 1 RD(R) 2 RD(R) 3 WR(T) 4 RD(T) 5 WR(S) 6 RD(S) 7 WR(R) 8 RD(T) 9 WR(W) 10 RD(S) 11 WR(R) 12 WR(S) a) There are several algorithms to build precedence graphs. Examine the above schedule and state which algorithm appears to be the more appropriate (justify your conclusion). Unconstrained writes (write without read), so labelled precedence graph. b) Give a brief description of the algorithm which you selected in part a) see notes c) Use the algorithm you selected in part a) to build the appropriate precedence graph for the given schedule. Graph after step 1: Tb T1 T2 T3 T4 Tf After Step 2: Tb T1 1 T2 T3 1 T4 Tf d) By reference to the constructed graph, determine whether the schedule is serializable (justify your decision) and if so, give the equivalent serial schedule. If you pick the arc from T3 to T1 to REMOVE, there is NO cycle, and it IS serializable. Note: all unlabelled arcs have a ‘0’ on them.. Question Three [19 marks] i) One protocol that ensures serializability is the Two Phase Locking Protocol. List the two phases of this protocol, and briefly explain each one. See notes ii) Consider the following graph structure used in a database system as part of implementing the graph locking protocol. Consider two transactions, T1 and T2 that will operate as A follows: T1 subtracts 10% f
More Less

Related notes for ECE 356

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.