Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS3101 > Transactions and Recovery > Flashcards

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>
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Describe Atomicity

A

Either all of the operations of a transaction are reflected in the database or none of them are

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Describe Consistency

A

Preserves the consistency of the database by executing transactions in isolation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Describe Durability

A

Once changes have been made they are made permenantly (will persist after failure)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Who is the responsible party for atomicity of transactions?

A

Database

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Who is the responsible party for consistency of transactions?

A

Application

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Who is the responsible party for isolation of transactions?

A

Database

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Who is the responsible party for durability of transactions?

A

Database

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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>
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Describe the active state

A

The initial state, transaction stays in this state while it is executing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

When is a transaction in a partially committed state?

A

After the final statement in the application logic has been executed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

When is a transaction in a failed state?

A

After the discovery that normal execution cannot proceed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

When is a transaction in the committed state?

A

After succesful completion and permenant storage of the change

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What state guarantees durability?

A

Committed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What state guarantees isolation?

A

Active

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What state guarantees atomicity?

A

Aborted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Describe a serial schedule

A

Transactions are run serially to completion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

For a set of n transactions, how many different serial schedules are there?

A

n!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is a benefit of serial schedules?

A

All serial schedules guarantee consistency

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What are the operations that must be considered when trying to make equivalent non serial schedules?

A

Read and write operations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

When is it important for the order of two transactions with I, J read write operations to be considered properly?

A

When I and J refer to the same data item

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is the condition for two schedules to be conflict equivalent?

A

<ul>
<li>One can be transformed into the other by a series of swaps of non-conflicting adjacent instructions</li>
</ul>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What does it mean for a schedule to be conflict serialisable?

A

<ul>
<li>If it is conflict equivalent to some serial schedule, meaning it's a correct schedule</li>
</ul>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

When should a vertex be drawn between edges Ti and Tj in a directed precedence graph?

A

<ul>
<li>Ti executes write before Tj executes read</li>
<li>Ti executes read before Tj executes write</li>
<li>Ti executes write before Tj executes write</li>
</ul>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What does it mean for an edge to be between Ti and Tj in a directed precedence graph?

A

Ti must be executed before Tj in any serial schedule S’ equivalent to S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What property must exist in a precedence graph for a schedule to be conflict serialisable?

A

Graph must be ACYLIC

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What are the two lock based protocols that are used to guarantee isolation?

A

<ul>
<li>Two phase protocol</li>
<li>Tree protocol</li>
</ul>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What is a lock and how is it related to when you can access an item?

A

Mechanism to control concurrent access to a data item, must acquire the item’s lock before accessing the item itself

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

What are the two modes that data can be locked in?

A

<ul>
<li>Exclusive(x)</li>
<li>Shared(s)</li>
</ul>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Describe the exclusive(x) mode

A

Data can be both read as well as written

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Describe the shared(s) mode

A

Data item can only be read

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

Who is a lock request made to?

A

The concurrency control manager

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

What are the only two combinations of locks that are compatible together?

A

Two shared locks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

What is a locking protocol?

A

A set of rules followed by all transactions while requesting and releasing locks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

What are some pitfalls of lock based protocols?

A

<ul>
<li>Deadlock</li>
<li>Starvation</li>
</ul>

40
Q

Describe deadlock

A

When two transactions are both waiting for locked data in the other transaction

41
Q

Describe starvation

A

Same transaction is being rolled back repeatedly due to deadlocks

42
Q

What are the two phases in the two phase locking protocol?

A

<ol>
<li>Growing phase</li>
<li>Shrinking phase</li>
</ol>

43
Q

What happens in the growing phase of the 2 phase locking protocol?

A

Transaction may obtain locks but it may not release locks

44
Q

What happens in the shrinking phase of the 2 phase locking protocol?

A

Transaction may release locks but may not obtain locks

45
Q

What does the 2 phase locking protocol assume?

A

Serialisability

46
Q

How can deadlocks be determined in a 2 phase locking protocol?

A

Finding cycles in a wait-for graph

47
Q

How is a wait for graph structured like?

A

If there is an edge between Ti from Tj, then Ti is waiting for Tj to release a data item

48
Q

What happens when deadlock is detected?

A

Some transaction will have to be rollbacked (made a victim)

49
Q

What is total rollback?

A

When the whole transaction is aborted and restarted

50
Q

How can we avoid starvation?

A

Include the number of rollbacks in the cost factor of a rollback

51
Q

What does a transaction timestamp hold?

A

When a transaction was started

52
Q

What is the wait die scheme?

A

Older transaction may wait for the younger one to release the data item
Younger transactions never wait for older ones, just rollbacked instead

53
Q

What is the wound-wait scheme?

A

Older transaction wounds younger transaction instead of waiting for it
Younger transactions may wait for older transactions

54
Q

What is a timeout based scheme?

A

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
Q

What are the important aspects when dealing with failure?

A

<ul>
<li>Data itself</li>
<li>Consistency of data</li>
</ul>

56
Q

What needs to happen when a failure occurs in a database?

A

Database needs to be restored to a consistent state

57
Q

Describe rollback

A

All effects of the transaction must be removed and any writes to the disk undone

58
Q

What are the two options after rollback?

A

<ul>
<li>Restart the transaction</li>
<li>Discard the transaction</li>
</ul>

59
Q

In what case would you restart the transaction?

A

If the failure was caused by some external factor

60
Q

Give an example of an external factor

A

Temporary damage to the motherboard

61
Q

In what case would you discard the transaction?

A

If the failure was due to the transaction itself

62
Q

What would be an example problem with the transaction?

A

Wrong data types given, wrong table referred to

63
Q

What are the three possible types of failure?

A 
<ul>
<li>Transaction failure</li>
<li>System crash</li>
<li>Disk failure</li>
</ul>
64
Q

Describe the two types of transaction failures

A

Logical error : transaction failures due to some internal error
System error : transaction can’t be executed due to some system reason

65
Q

Give examples of things that are classed as system crashes

A

Power failure, hardware malfunction, OS internal error

66
Q

How do we try and ensure atomicity despite chances of failure?

A

Output information describing modifications to stable storage without modifying database itself

67
Q

What is the approach to outputting modifications to stable storage without modifying database itself called?

A

Log based recovery

68
Q

What is a log?

A

Sequence of log records that maintains a record of update activities on the database

69
Q

Where is a log stored?

A

Stable storage

70
Q

Describe the four parts of a log record

A

Ti - transaction i
X - value being modified
V1 - value before modification
V2 - value after modification

71
Q

What is put on the log record after all the work of a transaction is done?

A

Ti commit

72
Q

What are the two approaches to using logs?

A

<ul>
<li>Deferred database modification</li>
<li>Immediate database modification</li>
</ul>

73
Q

Give an overview of deferred database modification

A

Records all modifications to the log but defers all the writes to after the partial commit

74
Q

What does deferred database modification need to store for a write(X) operation

A

where V is the new value for X

75
Q

When does a transaction need to be redone after failure with deferred database modification?

A

If and only if both Ti start and Ti commit are present in the log

76
Q

What is the recovery procedure operation for deferred database modification?

A

redo(Ti)

77
Q

What does redo(Ti) do in deferred database modification?

A

Sets the value of all data items updated by the transaction to the new values

78
Q

What characteristic must redo(Ti) have?

A

Must be idempotent

79
Q

What does idempotent mean?

A

You can apply the same operation n times and it will give the same result

80
Q

When can crashes occur in deferred database modification?

A

<ul>
<li>When the transaction is executing the original updates</li>
<li>When recovery action is being taken</li>
</ul>

81
Q

Describe the immediate database modification protocol

A

Allows database updates of an uncommitted transaction to be made as the writes are issued

82
Q

What is stored in the log of immediate database modification?

A

Both the old and new items as undoing might be needed

83
Q

What order is the update log/item done in?

A

the log record must be written before database item is written

84
Q

What are the two recovery operations of immediate database modification?

A

<ul>
<li>Redo(Ti)</li>
<li>Undo(Ti)</li>
</ul>

85
Q

Describe the redo operation of immediate database modification

A

Sets the values of all the data items updated by the transaction to the new values, going forward from the first log record

86
Q

Describe the undo operation of immediate database modification

A

Restores the value of all data items updated by the transaction to their old values, going backward from the last log record

87
Q

What must the undo and redo operations of immediate database modification be?

A

Idempotent

88
Q

What conditions hold for a transaction needing to be redone in immediate database modification?

A

The log contains both the record Ti start and Ti commit

89
Q

What conditions hold for a transaction needing to be undone?

A

If the log contains the record Ti start but does not contain the record Ti commit

90
Q

What’s the problem with log files being unbounded?

A

On failure, whole log file has to be examined which causes an expensive recovery process and big storage overheads

91
Q

What is the solution to log files being unbounded and the disadvantages with this?

A

Periodic checkpoints

92
Q

Describe periodic checkpoints

A

<ul><li>All records are flushed to the disk</li><li>Checkpoint record written to log</li><li>Completed transactions removed from log</li></ul>

93
Q

What does the checkpoint record tell?

A

What has been flushed to the disk now so don’t have to do excessive work?

94
Q

Describe log record buffering

A

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
Q

What is a log force?

A

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
Q

What are the rules that have to be followed for log record buffering?

A

<ul>
<li>Outputted to stable storage in the order they are created</li>
<li>Transaction enters commit stage only when log record has been output to stable storage</li>
<li>Before data in main memory is output to database, all relevant log records must go into stable storage</li>
</ul>

97
Q

Describe the write ahead logging rule

A

Before data in main memory is output to database, all relevant log records must go into stable storage

CS3101 (13 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions