CS 245 Final Exam
Spring 2019 (Solutions)
● Please read all instructions (including these) carefully.
● There are seven problems, some with multiple parts, for a total of 100 points. You have
2.5 hours (150 minutes) to work on the exam.
● The exam is open notes. You may use a laptop with all communication facilities (Wi-Fi,
Bluetooth, etc.) disabled.
● Please write your answers in the space provided on the exam, and clearly mark your
solutions. You may use the backs of the exam pages as scratch paper. Please do not use
any additional scratch paper.
● Solutions will be graded on correctness and clarity. For the long-answer problems, please
show your intermediate work. Each problem has a relatively simple to explain solution,
and we may deduct points if your solution is much more complex than necessary. Partial
solutions will be graded for partial credit.
NAME: __________________________________________________________________
SUID: ___________________________________________________________________
In accordance with both the letter and spirit of the Honor Code, I have neither given nor received
assistance on this examination.
SIGNATURE: _____________________________________________________________
Grading: P1=20pt, P2=17pt, P3=12pt, P4=14pt, P5=10pt, P6=15pt, P7=12pt, total=100pt.
Page 1/17
,Problem 1: Short Answer Questions (20 points)
1. (2 points) Which of these statements about serializable schedules is true? (Circle one answer.)
(a) Every serializable schedule is recoverable.
(b) Every serializable schedule contains no conflicting actions.
(c) Every 2PL schedule is serializable.
(d) None of the above.
2. (2 points) Which of these statements about recoverable schedules is true? (Circle one answer.)
(a) Every recoverable schedule is serializable.
(b) In a recoverable schedule, if a transaction T commits, then any other transaction that T
read from must also have committed.
(c) In a recoverable schedule, no transaction will ever be aborted because a transaction that it
read from has aborted.
(d) None of the above.
3. (2 points) In which of the following situations is optimistic concurrency control with
validation likely to perform better than locking with 2PL? (Circle one answer.)
(a) A high-contention workload where all the transactions need to update a single record.
(b) A read-mostly workload, where most transactions just read a small number of data items,
and a few transactions write data items.
(c) A distributed database where all the transactions need to read and write objects on
multiple servers.
(d) All of the above.
Page 2/17
, 4. (2 points) What is the main benefit of extendible hashing over a traditional hash table based
on a single array of buckets? (Circle one answer.)
(a) Extendible hashing requires fewer random disk I/Os to access each item.
(b) Extendible hashing requires less storage space for the hash table data structure.
(c) Extendible hashing reduces the I/O needed to update the data structure when we fill a
hash bucket.
(d) Extendible hashing produces fewer hash collisions.
5. (2 points) Which of these statements about deadlock are true? (Fill in all that are true.)
☐ If all transactions use two-phase locking, they cannot deadlock.
☐ Once two transactions deadlock, one of them must be aborted to maintain correctness.
☐ Systems that support update locks (S, X and U modes) cannot deadlock.
☐ Validation based concurrency control schemes cannot deadlock.
6. (2 points) Why is the increment lock mode (I) incompatible with both the S and X modes?
Transactions holding an item in increment mode can add values to it, so it is unsafe for other
transactions to either read or write the object because this could change the results they observe.
7. (2 points) In the database below with hierarchical locking, transaction T1 holds some locks.
Which of the following transactions can still acquire the locks they need to run? (Fill in all that
can; assume that only one of these candidate transactions would run at a time.)
☐ T2: write t1.
☐ T3: write t2.
☐ T4: read f2 and
write f1.
☐ T5: insert a child node under t2.
Page 3/17
Spring 2019 (Solutions)
● Please read all instructions (including these) carefully.
● There are seven problems, some with multiple parts, for a total of 100 points. You have
2.5 hours (150 minutes) to work on the exam.
● The exam is open notes. You may use a laptop with all communication facilities (Wi-Fi,
Bluetooth, etc.) disabled.
● Please write your answers in the space provided on the exam, and clearly mark your
solutions. You may use the backs of the exam pages as scratch paper. Please do not use
any additional scratch paper.
● Solutions will be graded on correctness and clarity. For the long-answer problems, please
show your intermediate work. Each problem has a relatively simple to explain solution,
and we may deduct points if your solution is much more complex than necessary. Partial
solutions will be graded for partial credit.
NAME: __________________________________________________________________
SUID: ___________________________________________________________________
In accordance with both the letter and spirit of the Honor Code, I have neither given nor received
assistance on this examination.
SIGNATURE: _____________________________________________________________
Grading: P1=20pt, P2=17pt, P3=12pt, P4=14pt, P5=10pt, P6=15pt, P7=12pt, total=100pt.
Page 1/17
,Problem 1: Short Answer Questions (20 points)
1. (2 points) Which of these statements about serializable schedules is true? (Circle one answer.)
(a) Every serializable schedule is recoverable.
(b) Every serializable schedule contains no conflicting actions.
(c) Every 2PL schedule is serializable.
(d) None of the above.
2. (2 points) Which of these statements about recoverable schedules is true? (Circle one answer.)
(a) Every recoverable schedule is serializable.
(b) In a recoverable schedule, if a transaction T commits, then any other transaction that T
read from must also have committed.
(c) In a recoverable schedule, no transaction will ever be aborted because a transaction that it
read from has aborted.
(d) None of the above.
3. (2 points) In which of the following situations is optimistic concurrency control with
validation likely to perform better than locking with 2PL? (Circle one answer.)
(a) A high-contention workload where all the transactions need to update a single record.
(b) A read-mostly workload, where most transactions just read a small number of data items,
and a few transactions write data items.
(c) A distributed database where all the transactions need to read and write objects on
multiple servers.
(d) All of the above.
Page 2/17
, 4. (2 points) What is the main benefit of extendible hashing over a traditional hash table based
on a single array of buckets? (Circle one answer.)
(a) Extendible hashing requires fewer random disk I/Os to access each item.
(b) Extendible hashing requires less storage space for the hash table data structure.
(c) Extendible hashing reduces the I/O needed to update the data structure when we fill a
hash bucket.
(d) Extendible hashing produces fewer hash collisions.
5. (2 points) Which of these statements about deadlock are true? (Fill in all that are true.)
☐ If all transactions use two-phase locking, they cannot deadlock.
☐ Once two transactions deadlock, one of them must be aborted to maintain correctness.
☐ Systems that support update locks (S, X and U modes) cannot deadlock.
☐ Validation based concurrency control schemes cannot deadlock.
6. (2 points) Why is the increment lock mode (I) incompatible with both the S and X modes?
Transactions holding an item in increment mode can add values to it, so it is unsafe for other
transactions to either read or write the object because this could change the results they observe.
7. (2 points) In the database below with hierarchical locking, transaction T1 holds some locks.
Which of the following transactions can still acquire the locks they need to run? (Fill in all that
can; assume that only one of these candidate transactions would run at a time.)
☐ T2: write t1.
☐ T3: write t2.
☐ T4: read f2 and
write f1.
☐ T5: insert a child node under t2.
Page 3/17
