Week 9 Flashcards
(35 cards)
What is a Transaction?
An executing program that forsm a logical unit of database operations
- A transaction includes one or more database operations eg., insertion, deletion, updating, retrieval
What are the properties of ACID?
Atomicity: All or nothing
Shouldn’t take money from A without giving it to B
Consistency: transforms the database from one consistent state to another consistent state
money isn’t lost or gained
Isolation: partial effects of incomplete transactrions should not be visible to other transactions
other transactions shouldn’t see such a change until completion
Durability: successfully committed transactions are permanently recorded in the database, not list, even in the event of a system failure
After completion, such a change in A and B is saved in the database
What is a Schedule?
An ordering of operations for concurrent transactions
What are the 2 types of Schedules?
Serial Schedule: A schedule in which the operations for concurrent transactions are not interleaved
But unacceptable in practice
Non-serial schedule: A schedule in which the operations for concurrent transactions are interleaved
What are the 2 desired properites of a Schedule?
Serializability
Recoverability
What are Conflicting Operations?
If 2 operations belong to different transactions, access the same same database item, and at least one operation is a writing operation
Eg. R1(x) & W2(X), W1(Y), W2(Y)
How do you test for Conflict Serializability?
Step 1: build a precedence graph
-Each node corresponds to one transaction
- Each edge (Ti -> Tj): if one of the operations in Ti appears in the schedule before some conflicting operations in Tj
Step 2: check for cycles in the graph
-If yes, the schedule is not serializable
- If no, the schedule is serializable
What is a Recoverable Schedule?
A schedule, where, for each pair of transactions Ti and Tj, if Tj reads a data item previously written by Ti, then Ti should commit before Tj
“Write first then commit first” - lecturer
What is Concurrency Control?
The process of managing simultaneous operations on the database without having them interfere with another
Objectives:
- Schedule transactions to avoid intereference
- Guarantee serializability
What are the 2 Concurrency Control Techniques?
Pessimistic:
Assumes that conflict is likely and take steps to prevent it
eg. Locking, Timestamping
Optimistic:
Assumes that conflict is unlikely and only checks for it when transaction commits
What can Locks be applied to?
-The whole database
-A file
-A page/ a disk block
-A record
-A field value of a record
What is a Shared/Exclusive Locking Scheme?
A transaction must issue read_lock(X), or write_lock(X) before any read(X)
A transaction must issue write_lock(X) before any write(X)
A transaction must issue unlock(X) after read(X) and write(X)
What is a problem with Shared/Exclusive Locking?
It does not guarantee serializability
More strict protocols are required, eg. two-phase locking (2PL)
What is Basic Two-Phase Locking (2PL)?
All locking operations precede the first unlock operation in a transaction
Growing/Expanding phase: during which new locks on items can be acquired but none can be released
Shrinking phase: during which existing locks can be released but no new locks can be acquired
Advantage: It assures serializability
What is a problem with 2PL?
Deadlock: A circular situation where each of two (or more) transactions are waiting to acquire locks that are held by the other
What are the 3 techniques for handling Deadlock?
- Timeouts
- Deadlock detection and recovery
- Deadlock prevention
What is the Timeouts technique?
A transaction will wait for a (database defined) period to acquire a lock
If this time runs out then the whole transaction is rolled back and restarted
What is the Deadlock Detection and Recovery Technique?
A Wait-for Graph (WFG) is constructed
-node for each transaction
-directed edge from transaction T1 to transaction T2 if T1 is waiting to lock and item currently held in T2
A deadlock exists if the graph contains a cycle
What is the Deadlock Prevention technique?
Conservative 2PL algorithm
- prevents deadlock by locking all desired data items before transaction begins execution
Strict 2PL algorithm
-unlocking is performed after a transaction terminates (commits or aborts/rolled-back)
Each transaction is timestamped
Wait-die algorithm
-only older transactions can wait for younger ones
Wound-wait algorithm
-only younger transactions can wait for older ones
otherwise, younger transaction is rolled back and restarted with the same timestamp
What is Timestamping?
A concurrency control protocol that orders transactions in such a way that older transactions get priority in the event of conflict
What is a Timestamp?
A unique identifier created by the DBMS that indicates the relative starting time of a transaction
-Either a logical counter or the system clock
What is a Backup?
A copy of the database
taken periodically
Stored in safe place which enables database to be restored with an acceptable loss of data
What are the 3 types of Backup?
Full Backup
-The whole database
Differential Backup
-All changes made since the last full backup
Incremental
-All changes made since the last incremental backup
What is Recovery?
The process of restoring the database to a correct state in the event of failure
