Assignment 7: Databases—Inside the Blackbox

3DB3: Databases – Fall 2021

Cheating and plagiarism. This assignment is an individual assignment: do not submit work of others. All parts of your submission must be your own work and be based on your own ideas and conclusions. If you submit work, then you are certifying that you have completed the work for that assignment by yourself. By submitting work, you agree to automated and manual plagiarism checking of the submitted work.

Cheating and plagiarism are serious academic ofenses. All cases of academic dishonesty will be handled in accordance with the Academic Integrity Policyvia the O伍ce of Academic Integrity.

Late submission policy. There is a late penalty of 20% on the score per day after the deadline. Submissions fve days (or later) after the deadline are not accepted. Do not wait until the deadline to ask questions or raise problems.

Description

A fnancial service provider came to the conclusion that their system, which processes complex money transfers between people, is not fast enough. Hence, they asked an consultant to come up with a higher- performance system. The consultant took a look at the original system and concluded that lock-based access was the main culprit. To deal with these performance issues, the consultant came up with a novel design

that reduces the duration of locks. Next, we detail the proposed design.

In the system, all transactions can be written as a sequence of transfers of the form

transfer（$x,from, to) = “transfer $x from account from to account to”,

that should only be executed if each transfer is possible (the from-account has sufcient funds). E.g., the transaction

r = [  transfer（$500, Bo, Alicia), transfer（$300, Eva, Celeste)]

of two such transfers is equivalent to

“if Bo has at-least $500 and Eva has at-least $300,

then transfer $500 from Bo to Alicia and transfer $300 from Eva to Celeste”.

The consultant wants to execute these transactions with a minimal amount of locking. To do so, the

consultant designed the minimal-locking operations upDArE-BAiANcE and rAKE-BAiANcE-coNDkrkoNAi

(see Figure 1 for the pseudo-code of these operations). Using these operations, the consultant proposes

to execute transactions r with n transfers, e.g., r =  [  transfer（$x1, from1, to1 ), . . . , transfer（$xn , fromn , ton)] ,

using the ExEcurE-rRANsAcrkoN algorithm (see Figure 2 for the pseudo-code of this algorithm).  The

ExEcurE-rRANsAcrkoN algorithm will visit each from-account, check whether that account has sufcient

upDArE-BAiANcE(r, account, amount):

1:  Lockr（account).

2:  account := account＋amount.

3:  Releaser（account).

rAKE-BAiANcE-coNDkrkoNAi(r, account, amount):

4:  Lockr（account).

5:  if account 0 amount then

6:       account := account - amount.

7:      Releaser（account).

8:      return True.

9:  else

10:      Releaser（account).

11:      return  False.

12:  end if

Figure 1:  The pseudo-code for the minimal-locking operations upDArE-BAiANcE and rAKE-BAiANcE-

coNDkrkoNAi.

funds (at-least the funds required for the transfer), and take away the funds that are to-be transferred (a reservation of funds). This reservation can be used in two ways:

1. If all from-accounts have sufcient funds, then all reserved funds will be transferred to their respective to-accounts (the transaction is successful). To do so, the variable Commit lists all upDArE-BAiANcE operations necessary to transfer reserved funds to their respective to-accounts.

2. Otherwise, if a from-account is found without sufcient funds, then all previously reserved funds will be returned to their respective from-accounts (the transaction failed). To do so, the variable Rollback lists all upDArE-BAiANcE operations necessary to transfer reserved funds back to their respective from-accounts.

The consultant believes that this setup will reduce locking, but might introduce unwanted interfer- ence between transactions. The fnancial service provider has already been instructed about the risks of interference, and decided that it can agree to interference as long as the following constraints are never broken:

C1. No account should ever receive a negative balance (assuming that all accounts start with a positive balance).

C2. As the transfers only move money between accounts, no money should be lost or created. Hence, if at any time t no transactions are being executed, then the sum of the balances of all accounts at that time t should be equivalent to the initial sum of the balances of all accounts.

C3. Successful transactions must have their lasting efects, while failed transactions must not have lasting efects. Hence, if at any time t no transactions are being executed, then the balance of each account should re1ect the balance updates due to all transactions that executed successfully before t.

We note that these constraints do not rule out inconsistencies in the data while transactions are being executed.

Faced with the complexity of the approach proposed by the consultant, the fnancial service provider has contacted you to evaluate the proposed approach.

Figure 2: The pseudo-code for the transaction execution algorithm.

Your evaluation

To evaluate the approach, the fnancial service provider asked you to investigate and answer the following questions:

1. Does the proposed approach follow strict two-phase locking? Does the proposed approach follow two-phase locking? Explain your answer. E.g., if the approach does not follow (strict) two-phase locking, then provide a transaction, its execution schedule, and argue that this schedule does not follow the (strict) two-phase locking protocol.

2. Does the proposed approach sufer from deadlocks? Explain your answer.

3. Does the proposed approach expose read-write, write-read, or write-write con1icts? Explain your answer. E.g., if there are con1icts, then provide two transactions, a valid interleaved execution schedule for these transactions, and argue that this schedule has these con1icts.

4. Does the proposed approach sufer from dirty reads? Explain your answer. E.g., if there are dirty reads, then provide two transactions, a valid interleaved execution schedule for these transactions, and argue that this schedule has dirty reads.

5. Does the proposed approach sufer from unrepeatable reads? Explain your answer. E.g., if there are unrepeatable reads, then provide two transactions, a valid interleaved execution schedule for these transactions, and argue that this schedule has unrepeatable reads.

6. Is the proposed approach serializable? Explain your answer.

7. Are the constraints C1-C3, as set out by the fnancial service provider, satisfed? Explain your answer. E.g., if a constraint is satisfed, then argue why that is the case.

Assignment

The goal of the assignment is to help out the fnancial service provider. To do so, you will write a report in which you answer Questions 1–7. Your submission:

1. must be a PDF fle;