# Intelligent Transaction Scheduling to Enhance Concurrency in High-Contention Workloads
## 3 Preliminaries
### Formalism of Transaction Processing  
**Definition 1** (Transaction): _A transaction \(T_{i}\) constitutes a finite sequence of database operations \(\{O_{1},\ldots,O_{in}\}\) executing as an atomic unit. Each operation \(O_{ij}\) represents either a \(\text{READ}(d)\) or \(\text{WRITE}(d)\) action on data item \(d\in\mathcal{D}\)._  
Operations within the same transaction can exhibit two types of dependencies, which arise based on the transaction's logical structure. We categorize these as _intra-transaction dependency_, which are further divided into (1) _data dependency_ and (2) _commit dependency_.  
**Definition 2** (Intra-Transaction Dependency): _For operations \(O_{ij}\) and \(O_{ik}\) within transaction \(T_{i}\), the partial order \(\prec_{intra}\) satisfies:_  
\[\forall O_{ij},O_{ik}\in T_{i},\ (j<k)\Rightarrow(O_{ij}\prec_{intra}O_{ik}) \tag{1}\]  
* **Intra-transaction data dependency** exists when \(O_{ik}\) relies on data computed by \(O_{ij}\). Formally, \(O_{ik}\) is said to be _data-dependent_ on \(O_{ij}\) if it requires a value produced by \(O_{ij}\).  
* **Intra-transaction commit dependency** ensures transaction atomicity when certain operations may be subject to logic-induced aborts. Logic-induced aborts result from violating integrity constraints defined by applications, which are captured by the set of constraints \(\prec_{\text{intra}}\). Intuitively, if an operation is associated with at least one constraint that may not be satisfied after the execution of the operation, then it is abortable.  
Another type of dependency exists between operations of different transactions, which the execution model induces.  
Definition 3 (Inter-Transaction Dependency): For distinct transactions \(T_{i}\
eq T_{k}\), a dependency \(O_{ij}\prec_{d\!\!op}O_{kl}\) exists iff:  
\[\exists d\in\mathcal{D}:\ (O_{ij}=WRITE(d))\wedge(O_{kl}\in\{READ(d),WRITE(d)\}) \tag{2}\]  
This general dependency can be classified into two specific cases:  
* **Write-read dependency:** If \(O_{kl}=\text{READ}(d)\), then \(O_{ij}\)'s commit must precede \(O_{kl}\)'s execution to prevent cascading aborts.
* **Write-write dependency:** If \(O_{kl}=\text{WRITE}(d)\), then \(O_{ij}\) and \(O_{kl}\) require mutual exclusion on \(d\), meaning they must be serialized to avoid data inconsistency. Unlike write-read dependency, this type of contention does not enforce a strict execution order.  
Transaction contentionTransaction contention primarily arises from inter-transaction dependencies, where multiple transactions contend for shared data. A transaction \(T_{i}\) is considered conflict-free with another transaction \(T_{j}\) if there are no contentions between them. The nature of these contentions is determined by the isolation level enforced by the CC protocol. For example:  
* Under serializability, contention occurs when two transactions access the same data item, and at least one modifies it.
* Under snapshot isolation, contention occurs if two transactions attempt to write the same data item.  
Effectively managing transaction contentions is essential for maintaining database integrity, ensuring correctness, and optimizing performance in a concurrent environment.