Transactions

Question 1

What are the ACID properties?

Answer 1

Atomicity - either all operations of the transaction happens or none of it does
Consistency - execution of a transaction in isolation preserves the consistency of the database
Isolation - it appears to each transaction as though no other transactions are active at the same time
Durability - after a successful transaction, the changes persist after failures

Question 2

Who are the responsible parties for ACID transactions?

Answer 2

AID: database
C: application

Question 3

What are the 5 states a transaction can be in?

Answer 3

Active - initial state: the transaction stays in this state while it is executing
Partially committed - after the final statement (in the application logic) has been executed
Failed - after the discovery that normal execution can no longer proceed
Aborted - after the transaction has been rolled back. two options from here: restart or kill the transaction
Committed - after successful completion

Question 4

What is a transient inconsistent state?

Answer 4

when the database is temporarily inconsistent during execution of a transaction

Question 5

In what situation can two consecutive write/read on the same data instructions be swapped?

Answer 5

if A and B both read

can’t be done if

A reads and B writes
A writes and B reads
A and B both write

Question 6

What is conflict equivalence?

Answer 6

Two schedules are conflict equivalent if one can be transformed into the other by a series of swaps of non-conflicting adjacent instructions. All conflict equivalent schedules give the same result.

Question 7

When is a schedule conflict serialisable?

Answer 7

If it conflict equivalent to some serial schedule

Question 8

how to draw a directed precedence graph? what is the significance of an edge?

Answer 8

add an edge from A to B if:

• A writes(q) before B reads(q)
• A writes(q) before B writes(q)
• A reads(q) before B writes(q)

an edge A -> B tells us that A must be executed before B in a serial schedule

if the graph has no cycles then the schedule can be conflict serialisable

Question 9

what are the two locking modes?

Answer 9

exclusive(X). data can be written and read by only this transaction
shared(S). data can only be read, by buy all

in general: X locks require no locks on the thing and prevent all locks on the thing

Question 10

describe the two phase locking protocol

Answer 10

ensures conflict serialisable schedules
phase 1: growing
- transaction may only obtain locks
phase 2: shrinking
- transaction may only release locks

ensures serialisablity
CAN ensure deadlock prevention if all transactions share phases
can have independant phases but doesn’t guarantee deadlock freedom
deadlocks can be determined using a wait-for graph

Question 11

how can deadlocks be determined?

Answer 11

using a wait-for graph

A points to B if A is waiting for B to release an item

Question 12

how can we recover from a deadlock?

Answer 12

transaction(s) will have to be rolled back
total rollback: abort the transaction and restart
more effective to partially rollback

Question 13

when does starvation occur, how is it prevented

Answer 13

when a transaction is always chosen as the victim of a rollback. we can include the number of rollbacks in the cost factor of the rollback to avoid this

Question 14

name 3 roll back schemes

Answer 14

total rollback

wait-die

• older transactions wait for younger ones
• younger ones will never wait for older ones, they are rolled back instead
• transactions may die several time

wound-wait

• older transaction “wounds” (forces the rollback of) the younger transaction instead of waiting for it
• younger transactioons may wait for older ones

timeout-based

• a transaction waits for a lock only for a specified amount of time
• after that the wait times out and the transaction is rolled back

Question 15

describe the tree protocol

Answer 15

data items are organised into a tree

1. only exclusive locks are allowed
2. the first lock by A may be on any data item. subsequently data item X may only be locked by A if the parent of X is also locked by A
3. data items may be unlocked at any time
4. a data item that has been locked and unlocked cannot be relocked by the same transaction

ensures conflict serialisabilty as well as freedom from deadlock

however, a transaction may have to lock data items tehy dont need in order to access their children
a database has to be amenable to the tree structure