Concurrency Flashcards
1
Q
Definition of transaction
A
Is a sequence of actions that are executed on a shared database to perform some higher-level function
-> basic unit of change in the DBMS
2
Q
ACID
A
- Atomicity
- Consistency
- Isolation
- Durability: effects after commit persist
3
Q
Definition Schedule
A
- DBMS gets as input a set of transactions and executes a schedule
-> gets list of actions from a set of transactions (must appear in the same order as in the transaction
4
Q
Types of Schedules
A
- Serial schedule: Schedule that does not interleave the actions of different transactions
- Equivalent schedules: For any database state, the effect (on the set of objects in the database) of executing the first schedule is identical to the effect of the executing the second schedule
- Serializable schedule: A schedule that is equivalent to some execution of the transaction
5
Q
2PL / Strict 2PL
A
- Rule 1: Each transaction obtains a shared lock before reading and an exclusive lock before writing
- Rule 2: A transaction cannot request additional locks once it releases any locks (not serializable!)
- Strict 2PL:
-> Rule 3: All locks released when the transaction aborts
6
Q
Deadlocks
A
- Cycle of transactions waiting for locks to be released by each other
-> Deadlock detection: Create waits-for-graph and check for cycles
-> Deadlock prevention: Transactions are assigned priorities based on timestamps (Wait-Die, Wound-wait)
7
Q
Kung-Robinson Model
A
- Optimistic approach
- Key idea: Timestamp ordering is imposed on transactions, and validation phase checks that all conflicting actions occurred in the same order
- If this is not the case, abort the transaction that started later
8
Q
Validation steps
A
- For all I and j such that Ti < Tj, check that Ti completes before Tj begins
- […] Ti completes before Tj begins its Write phase AND the intersection of WriteSet(Ti) and ReadSet(Tj) is empty
- Intersection of WriteSet(Ti) and WriteSet(Tj) is empty
