10. Transactions and Concurrency I Flashcards
3 main types of concurrency issues in DBMS
• Inconsistent Reads: A user reads only part of what was updated.
– User 1 updates Table 1 and then updates Table 2.
– User 2 reads Table 2 (which User 1 has not updated yet) and then Table 1 (which User 1 already updated) so it reads the database in an intermediate state.
• Lost Update: Two users try to update the same record so one of the updates gets lost. For example:
– User 1 updates a toy’s price to be price * 2.
– User 2 updates a toy’s price to be price + 5, blowing away User 1’s update.
• Dirty Reads: One user reads an update that was never committed.
– User 1 updates a toy’s price but this gets aborted.
– User 2 reads the update before it was rolled back.
Transaction - def
A transaction is a sequence of multiple actions that should be executed as a single, logical, atomic unit.
ACID properties of transactions
- Atomicity: A transaction ends in two ways: it either commits or aborts. Atomicity means that either all actions in the Xact happen, or none happen.
- Consistency: If the DB starts out consistent, it ends up consistent at the end of the Xact.
- Isolation: Execution of each Xact is isolated from that of others. In reality, the DBMS will interleave actions of many Xacts and not execute each in order of one after the other. The DBMS will ensure that each Xact executes as if it ran by itself.
- Durabilty: If a Xact commits, its effects persist. The effects of a committed Xact must survive failures.
What is a transaction schedule? Which operations does it consist of?
Transaction schedules show the order that operations are executed in. These operations include: Begin, Read, Write, Commit and Abort.
E.g. if one transaction has operations O1, O2, and another transaction has operations O4, O5 some possible schedules are:
O1, O4, O5, O2
O1, O2, O4, O5
O4, O5, O1, O2
What is a serial schedule?
Main advantage and drawback? The main practical goal?
Serial schedule ensures that we run all the operations of one transaction to completion before beginning the operations of next transaction.
Pros: It definitely ensures isolation by def.
Cons: it is not efficient and completely eliminates concurrency.
The main practical goal is to find a schedule that is equivalent to serial but allows some concurrency.
3 rules of transaction schedule equivalence
For schedules to be equivalent they must satisfy the following three rules:
- They involve the same transactions
- Operations are ordered the same way within the individual transactions
- They each leave the database in the same state
What is a serializable transaction schedule?
a schedule whose results are equivalent to a serial schedule
Which transaction operations may conflict with each other? 3 rules.
For two operations to conflict they must satisfy the following three rules:
- The operations are from different transactions
- Both operations operate on the same resource
- At least one operation is a write
Transaction schedule conflict equivalence - def.
When two schedules order their conflicting operations in the same way the schedules are said to be conflict equivalent, which is a stronger condition than being equivalent.
I.e. all conflict equivalent operations are equivalent,
but NOT all equivalent are conflict equivalent.
Conflict serializable transaction schedule - def.
a schedule that is conflict equivalent to some serial schedule.
Conflict serializable schedule is always serializable. So it always maintains transaction isolation property + may allow some concurrency, which is our main goal!
dependency graph - describe.
Why do we need it?
Dependency graphs have the following structure:
- One node per Xact
- Edge from T_i to T_j if:
– an operation O_i of T_i conflicts with an operation O_j of T_j
– O_i appears earlier in the schedule than O_j
Theorem: A schedule is conflict serializable if and only if its dependency graph is acyclic. So all we have to do is check if the graph is acyclic to know for sure that it is serializable!
