Transactions and Recovery Flashcards
1
Q
What does ACID stand for?
A
<ul> <li>Atomicity</li> <li>Consistency</li> <li>Isolation</li> <li>Durability</li> </ul>
2
Q
Describe Atomicity
A
Either all of the operations of a transaction are reflected in the database or none of them are
3
Q
Describe Consistency
A
Preserves the consistency of the database by executing transactions in isolation
4
Q
Describe Isolation
A
Even with concurrently executing transactions, it appears to each transaction that no other transaction was active at the same time
5
Q
Describe Durability
A
Once changes have been made they are made permenantly (will persist after failure)
6
Q
Who is the responsible party for atomicity of transactions?
A
Database
7
Q
Who is the responsible party for consistency of transactions?
A
Application
8
Q
Who is the responsible party for isolation of transactions?
A
Database
9
Q
Who is the responsible party for durability of transactions?
A
Database
10
Q
What are the five states a transaction can be in?
A
<ul> <li>Active</li> <li>Partially committed</li> <li>Failed</li> <li>Aborted</li> <li>Committed</li> </ul>
11
Q
Describe the active state
A
The initial state, transaction stays in this state while it is executing
12
Q
When is a transaction in a partially committed state?
A
After the final statement in the application logic has been executed
13
Q
When is a transaction in a failed state?
A
After the discovery that normal execution cannot proceed
14
Q
Describe the aborted state for a transaction
A
After the transaction has been rolled back, the database is restored to its prior state
15
Q
What are the two options after a transaction has been aborted?
A
<ul>
<li>Restart the transaction</li>
<li>Kill the transaction</li>
</ul>
16
Q
When is a transaction in the committed state?
A
After succesful completion and permenant storage of the change
17
Q
What state guarantees durability?
A
Committed
18
Q
What state guarantees isolation?
A
Active
19
Q
What state guarantees atomicity?
A
Aborted
20
Q
What does a schedule for transactions contain?
A
The order in which instructions of transactions should be executed with all instructions, preserving the order in which the instructions appear in each transaction
21
Q
Describe a serial schedule
A
Transactions are run serially to completion
22
Q
For a set of n transactions, how many different serial schedules are there?
A
n!
23
Q
What is a benefit of serial schedules?
A
All serial schedules guarantee consistency
24
Q
What are the operations that must be considered when trying to make equivalent non serial schedules?
A
Read and write operations
25
When is it important for the order of two transactions with I, J read write operations to be considered properly?
When I and J refer to the same data item
26
What is the condition for two schedules to be conflict equivalent?
- One can be transformed into the other by a series of swaps of non-conflicting adjacent instructions
27
What does it mean for a schedule to be conflict serialisable?
- If it is conflict equivalent to some serial schedule, meaning it's a correct schedule
28
When should a vertex be drawn between edges Ti and Tj in a directed precedence graph?
- Ti executes write before Tj executes read
- Ti executes read before Tj executes write
- Ti executes write before Tj executes write
29
What does it mean for an edge to be between Ti and Tj in a directed precedence graph?
Ti must be executed before Tj in any serial schedule S' equivalent to S
30
What property must exist in a precedence graph for a schedule to be conflict serialisable?
Graph must be ACYLIC
31
What are the two lock based protocols that are used to guarantee isolation?
- Two phase protocol
- Tree protocol
32
What is a lock and how is it related to when you can access an item?
Mechanism to control concurrent access to a data item, must acquire the item's lock before accessing the item itself
33
What are the two modes that data can be locked in?
- Exclusive(x)
- Shared(s)
34
Describe the exclusive(x) mode
Data can be both read as well as written
35
Describe the shared(s) mode
Data item can only be read
36
Who is a lock request made to?
The concurrency control manager
37
What are the only two combinations of locks that are compatible together?
Two shared locks
38
What is a locking protocol?
A set of rules followed by all transactions while requesting and releasing locks
39
What are some pitfalls of lock based protocols?
- Deadlock
- Starvation
40
Describe deadlock
When two transactions are both waiting for locked data in the other transaction
41
Describe starvation
Same transaction is being rolled back repeatedly due to deadlocks
42
What are the two phases in the two phase locking protocol?
- Growing phase
- Shrinking phase
43
What happens in the growing phase of the 2 phase locking protocol?
Transaction may obtain locks but it may not release locks
44
What happens in the shrinking phase of the 2 phase locking protocol?
Transaction may release locks but may not obtain locks
45
What does the 2 phase locking protocol assume?
Serialisability
46
How can deadlocks be determined in a 2 phase locking protocol?
Finding cycles in a wait-for graph
47
How is a wait for graph structured like?
If there is an edge between Ti from Tj, then Ti is waiting for Tj to release a data item
48
What happens when deadlock is detected?
Some transaction will have to be rollbacked (made a victim)
49
What is total rollback?
When the whole transaction is aborted and restarted
50
How can we avoid starvation?
Include the number of rollbacks in the cost factor of a rollback
51
What does a transaction timestamp hold?
When a transaction was started
52
What is the wait die scheme?
Older transaction may wait for the younger one to release the data item
Younger transactions never wait for older ones, just rollbacked instead
53
What is the wound-wait scheme?
Older transaction wounds younger transaction instead of waiting for it
Younger transactions may wait for older transactions
54
What is a timeout based scheme?
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
55
What are the important aspects when dealing with failure?
- Data itself
- Consistency of data
56
What needs to happen when a failure occurs in a database?
Database needs to be restored to a consistent state
57
Describe rollback
All effects of the transaction must be removed and any writes to the disk undone
58
What are the two options after rollback?
- Restart the transaction
- Discard the transaction
59
In what case would you restart the transaction?
If the failure was caused by some external factor
60
Give an example of an external factor
Temporary damage to the motherboard
61
In what case would you discard the transaction?
If the failure was due to the transaction itself
62
What would be an example problem with the transaction?
Wrong data types given, wrong table referred to
63
What are the three possible types of failure?
```
- Transaction failure
- System crash
- Disk failure
64
Describe the two types of transaction failures
Logical error : transaction failures due to some internal error
System error : transaction can't be executed due to some system reason
65
Give examples of things that are classed as system crashes
Power failure, hardware malfunction, OS internal error
66
How do we try and ensure atomicity despite chances of failure?
Output information describing modifications to stable storage without modifying database itself
67
What is the approach to outputting modifications to stable storage without modifying database itself called?
Log based recovery
68
What is a log?
Sequence of log records that maintains a record of update activities on the database
69
Where is a log stored?
Stable storage
70
Describe the four parts of a log record
Ti - transaction i
X - value being modified
V1 - value before modification
V2 - value after modification
71
What is put on the log record after all the work of a transaction is done?
Ti commit
72
What are the two approaches to using logs?
- Deferred database modification
- Immediate database modification
73
Give an overview of deferred database modification
Records all modifications to the log but defers all the writes to after the partial commit
74
What does deferred database modification need to store for a write(X) operation
where V is the new value for X
75
When does a transaction need to be redone after failure with deferred database modification?
If and only if both Ti start and Ti commit are present in the log
76
What is the recovery procedure operation for deferred database modification?
redo(Ti)
77
What does redo(Ti) do in deferred database modification?
Sets the value of all data items updated by the transaction to the new values
78
What characteristic must redo(Ti) have?
Must be idempotent
79
What does idempotent mean?
You can apply the same operation n times and it will give the same result
80
When can crashes occur in deferred database modification?
- When the transaction is executing the original updates
- When recovery action is being taken
81
Describe the immediate database modification protocol
Allows database updates of an uncommitted transaction to be made as the writes are issued
82
What is stored in the log of immediate database modification?
Both the old and new items as undoing might be needed
83
What order is the update log/item done in?
the log record must be written before database item is written
84
What are the two recovery operations of immediate database modification?
- Redo(Ti)
- Undo(Ti)
85
Describe the redo operation of immediate database modification
Sets the values of all the data items updated by the transaction to the new values, going forward from the first log record
86
Describe the undo operation of immediate database modification
Restores the value of all data items updated by the transaction to their old values, going backward from the last log record
87
What must the undo and redo operations of immediate database modification be?
Idempotent
88
What conditions hold for a transaction needing to be redone in immediate database modification?
The log contains both the record Ti start and Ti commit
89
What conditions hold for a transaction needing to be undone?
If the log contains the record Ti start but does not contain the record Ti commit
90
What's the problem with log files being unbounded?
On failure, whole log file has to be examined which causes an expensive recovery process and big storage overheads
91
What is the solution to log files being unbounded and the disadvantages with this?
Periodic checkpoints
92
Describe periodic checkpoints
- All records are flushed to the disk
- Checkpoint record written to log
- Completed transactions removed from log
93
What does the checkpoint record tell?
What has been flushed to the disk now so don't have to do excessive work?
94
Describe log record buffering
Log records are outputted to stable storage when a block of log records in the buffer in main memory becomes full OR a log force is executed
95
What is a log force?
An operation performed to commit a transaction by forcing all its log records (including the commit record) to stable storage (equivalent to a flush)
96
What are the rules that have to be followed for log record buffering?
- Outputted to stable storage in the order they are created
- Transaction enters commit stage only when log record has been output to stable storage
- Before data in main memory is output to database, all relevant log records must go into stable storage
97
Describe the write ahead logging rule
Before data in main memory is output to database, all relevant log records must go into stable storage
