DOC PREVIEW
MIT 6 830 - Quiz I

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Department of Electrical Engineering and Computer Science MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6.830 Database Systems: Fall 2008 Quiz I There are 17 questions and 10 pages in this quiz booklet. To receive credit for a question, answer it according to the instructions given. You can receive partial credit on questions. You have 80 minutes to answer the questions. Write your name on this cover sheet AND at the bottom of each page of this booklet. Some questions may be harder than others. Attack them in the order that allows you to make the most progress. If you find a question ambiguous, be sure to write down any assumptions you make. Be neat. If we can’t understand your answer, we can’t give you credit! THIS IS AN OPEN BOOK, OPEN NOTES QUIZ. NO PHONES, NO LAPTOPS, NO PDAS, ETC. Do not write in the boxes below 1-4 (xx/20) 5-7 (xx/16) 8-10 (xx/20) 11-13 (xx/21) 14-17 (xx/23) Total (xx/100) Name:I 6.830 Fall 2008, Quiz 1 Page 2 of 10 Short Answer 1. [6 points]: To reduce the number of plans the query optimizer must consider, the Selinger Opti-mizer employs a number of heuristics to reduce the search space. List three: (Fill in the blanks below.) A. B. C. 2. [4 points]: Give one reason why the REDO pass of ARIES must use physical logging. (Write your answer in the space below.) Name:6.830 Fall 2008, Quiz 1 Page 3 of 10 II Optimistic Concurrency Control For the following transaction schedules, indicate which transactions would commit and which would abort when run using the parallel validation scheme described in the Kung and Robinson paper on Optimistic Concurrency Control. Also give a brief justification for your answer. You may assume that if a transaction aborts, it does not execute its write phase, rolling back instantly at the end of the validation phase. 3. [4 points]: Read Validate WriteRead set: {A,B} Write set: {B,C}T1Read set: {A,D} Write set: {A,B}T2Time(Write your answer in the spaces below.) Transactions that commit: Transactions that abort: Justification: 4. [6 points]: Read set: {D} Write set: {D}T3Read Validate WriteRead set: {A,B} Write set: {B,C}T1Read set: {A,B} Write set: {B,D}T2(Write your answer in the spaces below.) Transactions that commit: Transactions that abort: Justification: Name:6.830 Fall 2008, Quiz 1 Page 4 of 10 III Schema Design Consider a relational table: Professor( professor name, professor id, professor office id, student id, student name, student office id, student designated refrigerator id, refrigerator owner id, refrigerator id, refrigerator size, secretary name, secretary id, secretary office ) Suppose the data has the following properties: A. Professors and secretaries have individual offices, students share offices. B. Students can work for multiple professors. C. Refrigerators are owned by one professor. D. Professors can own multiple refrigerators. E. Students can only use one refrigerator. F. The refrigerator the student uses must be owned by one of the professors they work for. G. Secretaries can work for multiple professors. H. Professors only have a single secretary. 5. [10 points]: Put this table into 3rd normal form by writing out the decomposed tables; designate keys in your tables by underlining them. Designate foreign keys by drawing an arrow from a foreign key to the primary key it refers to (see example below.) Note that some of the properties listed above may not be enforced (i.e., guaranteed to be true) by a 3NF decomposition. (Write your answer in the space below.) emp : eid, name, dnodept : did, bldg, nameExample decomposition of emp/dept tables showing primary and foreign keys. Name:� � 6.830 Fall 2008, Quiz 1 Page 5 of 10 6. [3 points]: Which of the eight properties (A–H) of the data are enforced (i.e., guaranteed to be true) by the 3NF decomposition and primary and foreign keys you gave above? (Write your answer in the space below.) 7. [3 points]: What could a database administrator do to make sure the properties not explicitly en-forced by your schema are enforced by the database? (Write your answer in the space below.) IV External Aggregation Suppose you are implementing an aggregation operator for a database system, and you need to support aggre-gation over very large data sets with more groups than can fit into memory. Your friend Johnny Join begins writing out how he would implement the algorithm. Unfortunately, he stayed up all night working on Lab 3 and so trails off in an incoherent stream of obscenities and drool before finishing his code. His algorithm begins as follows: input : Table T , aggregation function f name, aggregation field agg f , group by field gby f /* Assume T has |T | pages and your system has |M| pages of memory */ /* Partition phase */ n |T | ;←|M|Allocate bu f s, n pages of memory for output buffers ; Allocate f iles, an array of n files for partitions ; foreach record r ∈ T do h ← hash(r.gby f ) ; /* h ∈ [1 . . . n] */ Write r into page bu f s[h] ; if page bu f s[h] is full then Add bu f s[h] to file f iles[h], and set the contents of bu f s[h] to empty ; end end /* Aggregate phase */ foreach f ∈ f iles do /* Your code goes here. */ end Name:6.830 Fall 2008, Quiz 1 Page 6 of 10 8. [6 points]: Relative to |T |, how big must |M| be for the algorithm to function correctly? Justify your answer with a sentence or brief analytical argument. (Write your answer in the space below.) 9. [8 points]: Assuming the aggregate phase does only one pass over the data, and that f name = ’AVG’, describe briefly what should go in the body of the for loop (in place of “Your code goes here”). You may write pseudocode or a few short sentences. Suppose the system provides a function emit(gr oup,val) to output the value of a group. (Write your answer in the space below.) 10. [6 points]: Describe an alternative to this hashing-based algorithm. Your answer shouldn’t require more than a


View Full Document
Download Quiz I
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Quiz I and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Quiz I 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?