Test 3: Questions
[8 pts] Without changing the HTML below, write CSS rules accomplishing each of the following.
a. Color only the names Washington, Jefferson, and Monroe blue.
b. Display only the year 1789 in boldface.
(Use font-weight: bold.)
<table>
<tr class="odd" id="first">
<td class="name">Washington<td>
<td class="year">1789</td>
</tr>
<tr class="even">
<td class="name">Adams<td>
<td class="year">1797</td>
</tr>
<tr class="odd">
<td class="name">Jefferson<td>
<td class="year">1801</td>
</tr>
<tr class="even">
<td class="name">Madison<td>
<td class="year">1809</td>
</tr>
<tr class="odd">
<td class="name">Monroe<td>
<td class="year">1817</td>
</tr>
</table>
[10 pts] For the relation R(a, b, c, d, e), convert the following FD basis to a minimal FD basis.
a b → b c d
b c → a e
c → d e
[8 pts] For the below B+-tree, each node has up to four keys and five pointers. Show the B+-tree that would result by inserting 11 as described in class.
[8 pts] For the below B+-tree, each node has up to four keys and five pointers. Show the B+-tree that would result by deleting 12 as described in class.
[8 pts] Suppose M is the number of blocks that can fit into memory, B(x) is the number of blocks in relation x, and T(x) is the number of tuples in relation x. How many disk accesses will the following algorithm to join R and S take? Explain your answer.
for each block T in R:
for each block U in S:
for each tuple r in T:
for each tuple s in U:
if r and s agree on the join key:
output r, s
[8 pts] The two-phase multiway merge sort we saw in class is restricted to tables with at most M² − M blocks. How can it be extended so as to sort tables with more blocks (but substantially less than M³ blocks)?
[10 pts] Suppose we have a database of products, customers, and customer orders for the products. Give an example of a transaction involving multiple SQL queries, and explain why it would be desirable to group the queries into a single transaction.
[6 pts] Identify and explain what the A stands for among the ACID database properties.
[10 pts] Suppose we have two transactions.
ID action operations 1. Copy A to B r_1(A), w_1(B) 2. Copy B to A r_2(B), w_2(A)
Suppose A starts at 100 while B starts at 300. Write three different valid schedules (not necessarily serializable schedules) for these transactions, each resulting in a different final value for A or B, and identify the final value of A and B for that schedule.
[8 pts] Draw a precedence graph for determining whether the schedule below is conflict-serializable, labeling each edge with the operations that lead you to include that edge.
r1(A), r2(B), r3(A), r3(C), w3(B), w1(C)
With specific reference to your graph, explain whether you can conclude that the schedule is conflict-serializable.
[8 pts] Suppose a transaction could request an exclusive lock while it holds a shared lock on that element. Explain how deadlock could occur even if our database had only one element.
[8 pts] Recall that we studied the validation technique for ensuring serializability. Without getting into details of the criteria for canceling transactions, summarize how this technique works.
Test 3: Solutions
a. tr.odd td.name { color: blue }
b. tr#first td.year { font-weight: bold }
b c → a
c → d
c → e
The first for loop (over T) ends up reading each block in R exactly once, for B(R) disk accesses. The second for loop (over U) ends up reading each block in S, for B(S) disk accesses each time it executes, and it will execute B(R) times. So the total number of disk accesses is B(R) + B(R) ⋅ B(S).
We divide the table into “superchunks,” each with M² − M blocks, and we apply two-phase multiway merge sort to each of these superchunks. We then add a third phase of merging these superchunks together, working exactly like the second phase. This third phase can handle merging up to M − 1 superchunks, so this process works for a table with up to (M² − M) (M − 1) = M³ − 2 M² + M blocks.
Suppose before allowing a customer to order a product we want
first to confirm that there is enough inventory to deliver the
product. We would first have a SELECT query to check
the inventory and only then would we have an UPDATE
query to decrease the imagined inventory.
If these are not part of the same transaction,
then two customers might simultaneously order the same product
of which there is only one in inventory.
Both customers may execute their SELECT query to find that
there is enough inventory, and then both customers may execute
the UPDATE query decreasing the inventory. This could
easily lead both customers to believe their order could be
satisfied, and the inventory would become negative.
Atomicity is the property that the operations requested by a transaction will either all be completed or all have no effect.
- r_1(A), w_1(B), r_2(B), w_2(A)
- A and B both end up at 100.
- r_1(A), r_2(B), w_1(B), w_2(A) (or r_2(B), r_1(A), w_1(B), w_2(A); or r_1(A), r_2(B), w_2(A), w_1(B); or r_2(B), r_1(A), w_2(A), w_1(B))
- A ends up at 300 while B ends up at 100.
- r_2(B), w_2(A), r_1(A), w_1(B)
- A and B both end up at 300.
The arrow from 3 to 1 comes from the operations r3(C) and w1(C), and the arrow from 2 to 3 comes from the operations r2(B) and w3(B).
Since the graph contains no cycles, we conclude that it is conflict-serializable. In particular, it is equivalent to the serial schedule completing transaction 2 first, then transaction 3, and finally transaction 1.
Suppose two transactions each acquire a shared lock on the same element. This is of course allowed, as having multiple transactions holding a shared lock is the point of having shared locks. Now suppose each of the two transactions request an exclusive lock. Neither will be able to acquire an exclusive lock immediately because the other transaction currently holds a shared lock. In fact, both will be waiting for the other transaction to release a shared lock, though neither will get around to completing since both are stuck waiting for an exclusive lock before proceeding.
With validation, a transaction executes as if there will be no problems with serializability, but it logs what elements the transaction accesses and, when the transaction requests any writes, it defers any writing the new values to disk. When the transaction is ready to complete, the transaction is “validated” to ensure that it has not violated serializability. If it has violated serializability, the transaction is canceled. But if it is consistent with serializability, the DBMS proceeds to execute all writes requested by the transaction as it commits the transaction.