Transactions Flashcards
What are transactions?
A transaction is a unit of program execution that accesses and, possibly updates, various data item
What are the main issues to deal with in terms of transactions?
◦ Failures of various kinds, such as hardware failures and system crashes.
◦ Concurrent execution of multiple transactions
What are the properties required for a transaction?
ACID - Atomicity, Consistency, Isolation, Durablity
What does Atomicity mean?
Atomicity guarantees that each transaction is treated as a single unit, which either succeeds completely, or fails completely
◦ If any of the statements constituting a transaction fails to complete, the entire transaction fails and the database is left unchanged
◦ Atomicity must be guaranteed in every situation, including power failures, errors and crashes The system should ensure that updates of a partially executed transaction are
not reflected in the database
In short “All or Nothing Transactions”
What does Consistency mean?
In general, consistency requirements include
. Explicitly specified integrity constraints
− primary keys and foreign keys
. Implicit integrity constraints
− sum of balances of all accounts, minus sum of loan amounts must equal value of cash-in-hand
Consistency ensures that a transaction can only bring the database from one valid state to
another, maintaining database invariants
◦ Any data written to the database must be valid according to all defined rules, including constraints,
cascades, triggers, and any combination thereof
In short “Guarantees Committed Transaction State”
What does Isolation Requirement mean?
Transactions are often executed concurrently (multiple transactions reading and writing to a table at the same time)
◦ Isolation ensures that concurrent execution of transactions leaves the database in the same state
that would have been obtained if the transactions were executed sequentially
In short “Transactions are independent”
What does Durability requirement mean?
Durability guarantees that once a transaction has been committed, it will remain committed
even in the case of a system failure (like power outage or crash)
◦ This usually means that completed transactions (or their effects) are recorded in non-volatile memory
In short “Committed data is never lost”
What are the various transaction states?
Every transaction can be in one of the following states (like Process States in OS)
◦ Active -The initial state; the transaction stays in this state while it is executing
◦ Partially committed -After the final statement has been executed
◦ Failed - After the discovery that normal execution can no longer proceed
◦ Aborted - After the transaction has been rolled back and the database restored to its state prior to the start of the transaction. Two options after it has been aborted:
− Restart the transaction: Can be done only if no internal logical error
− Kill the transaction
◦ Committed - After successful completion
◦ Terminated - After it has been committed or aborted (killed)
What are concurrent executions?
Multiple transactions are allowed to run concurrently in the system. Advantages are:
1. Increased processor and disk utilization
2. Reduced average response time
what are concurrency control schemes?
Mechanisms to achieve isolation
◦ To control the interaction among the concurrent transactions in order to prevent them from destroying the consistency of the database
What is a schedule?
Schedule: A sequence of instructions that specify the chronological order in which instructions of concurrent transactions are executed. A schedule for a set of transactions must consist of all instructions of those
transactions. Must preserve the order in which the instructions appear in each individual transaction.
When will a transaction complete?
A transaction that successfully completes its execution will have a commit instruction as the last statement.
◦ By default, transaction assumed to execute commit instruction as its last step. A transaction that fails to successfully complete its execution will have an abort
instruction as the last statement.
What is a serial schedule?
A schedule is said to be serial schedule if only after the commit of one transaction, the other transaction begins.
A (possibly concurrent) schedule is serializable if it is equivalent to a serial schedule and is free from inconsistency problems. In a serial schedule, transactions are executed one after the other.
What is the problem with concurrent schedules?
Though it has better utilization of resources, some of the transactions could leave the database in an inconsistent state.
How to solve the inconsistency problems associated with the concurrent schedules?
By converting the concurrent schedule into an equivalent schedule which is serializable.
If this is possible, we call such a concurrent schedule as a “Serializable schedule”.
What are different forms of schedule equivalence?
a) Conflict Serializability
b) View Serializability
What is a conflict serializable schedule?
A Schedule is said to be “Conflict serializable” , if one of its conflict equivalent schedule is serializable.
What is a conflict equivalent schedule?
If a schedule S can be transformed into a schedule S’ by a series of swaps of non-conflicting instructions, we say that S and S’ are conflict equivalent.
- If we swap conflicting pairs, then the output would change and could be inconsistent and hence the schedule may not remain “Equivalent”
What are conflicting instructions?
Let li and lj be two Instructions from transactions Ti and Tj respectively
* Instructions li and lj conflict if and only if there exists some item Q accessed by both li and lj, and at least one of these instructions write to Q
a) li = read(Q), lj = read(Q). li and lj don’t conflict
b) li = read(Q), lj = write(Q). They conflict
c) li = write(Q), lj = read(Q). They conflict
d) li = write(Q), lj = write(Q). They conflict
* Intuitively, a conflict between li and lj forces a (logical) temporal order between them
◦ If li and lj are consecutive in a schedule and they do not conflict, their results would remain the same even if they had been interchanged in the schedule
What are conflict pairs ?
conflict pairs - 1) R(A), W(A) or W(A), R(A)
2) W(A),R(A) or R(A)W(A)
3) W(A),W(A)
Order doesn’t matter among them, no matter in which order they exist, they are problematic.
What are non conflict pairs?
The following tranasactions do not affect the consistency of the database. Hence are swappable.
1. R(A)R(B)
2. R(A)R(A)
3. W(A), W(B)
4. R(A),W(B)
How to find Conflict Equivalent Schedule?
We swap non conflicting pairs and try to bring a serial order. Thus we have converted an concurrent schedule into a conflict Equvivalent Schedule aka we have made the concurrent schedule serializable.
- Are all serializable schedules conflict-serializable?
No.
What is conflict serializable schedule?
We say that a schedule S is conflict serializable if it is conflict equivalent to a serial schedule.
What is a quicker method to check serializabiliity? (Conflict Serializability)
Precedence Graph Method. Nodes represent transactions, edges represent various conflicts that occur between various transactions in a schedule.
What are precedence graph?
A direct graph where the vertices are the transactions (names). We draw an arc/edge from Ti to Tj if the two transactions conflict, and Ti accessed the data item on which the conflict arose earlier. We may label the arc by the item that was accessed.
