Compsci 223 Assignment 1

Assignment 1
Question 1: Read up and very briefly describe the inode data structure used in Unix style file
systems. Compare its advantages/disadvantages compared to extent-based file allocation when
files are used to store database relations.
Question 2: Provide examples of how processing transactions without guaranteeing ACID
properties can lead to incorrect behavior. Provide an example for each one of the four properties
(Each example should define transactions, what operations they do, and the corresponding
violation to one of the ACID properties, and why it leads to incorrect behavior).
Question 3: Consider a B+ tree being used as a secondary index into a relation. Assume that at
most 2 keys and 3 pointers can fit on a page.
(a) Construct a B+ tree after the following sequence of key values are inserted into the tree.
12, 13, 3, 4, 1, 10, 58, 17, 16, 14, 5, 90, 19
(b) Consider the B+ tree constructed in part (a). For each of the following search queries,
write the sequence of pages of the tree that are accessed in answering the query. Your
answer must not only specify the pages accessed but the order of access as well.
Assume that in a B+ tree the leaf level pages are linked to each other using a doubly
linked list.
(i) Find the record with the key value 10.
(ii) Find records with the key values in the range from 14 to 19 inclusive.
(c) For the B+ tree in part 1, show the structure of the tree after the following sequence of
deletions.
12, 13, 3, 4, 1, 10, 58
Question 4: 2PL requires that locks for a transaction are held until all transaction operations are
complete. Show how violating this property (by allowing transaction to release locks before the
transaction’s other operations are performed) can lead to incorrect behavior.
Question 5: Consider the following nested transaction that executes sequentially from left to
right. That is, there is no concurrency within the transaction. Each node is marked as a _C or
an _R to denote if the subtransaction corresponding to that node committed or aborted.
Assume the initial value of X is 10. What is the value of X when the nested transaction T1
commits.
Question 6: Clearly illustrate using a concrete example what would go wrong if REDO/UNDO
logging is used for recovery, but the system does not use write ahead logging.
Question 7: What does the term blocking mean in the context of atomic commit protocols. Also,
illustrate clearly using an example when executing 2PC may lead to blocking.