Concurrency

concurrency control

The goal of a concurrency control is to generate an execution schedule that is equivalent to some serial execution:

• serial schedule: a schedule does not interleave the actions of different transactions
• equivalent schedules: the effect of executing two schedules are same
• serializable schedule: a schedule is equivalent to some serial execution of transactions.

There are some problems when interleaves the operations:

• Read-write conflicts (unrepeatable reads): A transaction cannot get the same value when reading the same object multiple Times.
• Write-read conflicts(Dirty read): a transaction sees the write effects of a different transaction before that transaction committed its changes.
• Write-Write conflicts (Lost updates): one transaction overwrites the uncommitted data of another concurrent transitions.

Schedule S is conflict serializable if you are able to transform S into a serial schedule by swapping consecutive non-conflicting operations of different transactions. We could use dependency graphs to check. $T_i$ -> $T_j$ means if one operation $O_i$ of $T_i$ conflicts with an operation $O_j$ of $T_j$ and $O_i$ appears earlier in the schedule in $O_j$. A schedule is conflict serializable if and only the graph is acyclic.

For View serializable, it means if one write is overwrote by another transaction and there is no read, it is fine. It allows all conflict serializable schedules and blind writes. It is hard to enforce efficiently. It allows more schedules.

For durability. All of the changes of committed transactions must be durable (i.e., persistent) after a crash or restart. The DBMS can either use logging or shadow paging to ensure that all changes are durable.

---

Children

1. 2PC
2. 2PL
3. ACID
4. Basic
5. Cap
6. Consistency
7. MVCC
8. Recovery
9. Replication
10. TOCC