Coo: Rethink Data Anomalies In Databases

Haixiang Li, Xiaoyan Li, Yuxing Chen, Yuean Zhu, Xiaoyong Du, Wei Lu, Chang Liu, Anqun PanarXiv 2021 · arXiv

Introduction

In modern database systems, isolation levels such as Read Committed or Serializable are the primary safeguards for data consistency. However, the industry-standard definitions for these levels—codified in the ANSI/ISO SQL standard—suffer from significant limitations. These definitions are largely informal, relying on plain-English descriptions of a few specific "anomalies" like Dirty Reads or Phantoms. This lack of mathematical rigor leads to implementation ambiguity across different database engines and an incomplete understanding of the full spectrum of potential data corruption.

The Coo framework addresses these gaps by providing a mathematically complete and quantitative definition of all possible data anomalies. By formalizing anomalies through extended conflict graphs and predicate logic, Coo allows researchers and engineers to measure the frequency of anomalies and their real-world impact on performance.

The Coo Framework

Coo moves beyond traditional models by introducing several key technical innovations to the concept of a conflict graph:

  • Predicate Logic Integration: Standard conflict graphs typically track operations on individual data items. Coo incorporates predicate logic to handle "predicate-based" anomalies, such as Phantoms, where a transaction's behavior is dictated by a set of records (e.g., "all active accounts").
  • Partial Order Pairs (POP): By including the final status of a transaction (Commit or Abort) into the graph, Coo can formally define anomalies involving uncommitted data, such as "Aborted Reads" or "Intermediate Reads."
  • Anomaly Classification: The framework classifies anomalies into three distinct types based on graph edges: Read Anomaly Type (RAT), Write Anomaly Type (WAT), and Intersect Anomaly Type (IAT).
A conflict graph incorporating predicate logic to model complex anomalies like Phantoms.

The Power of Simplification

A critical breakthrough of the Coo framework is the proof that complex, multi-transaction anomaly cycles can often be reduced to simpler 2-transaction cycles. This "Cycle Simplification" makes it significantly easier for database systems to detect and prevent anomalies without the overhead of monitoring massive, multi-variable dependency chains.

The reduction of a 5-transaction ring into simpler 2-transaction cycles, demonstrating that most data corruption stems from simple interactions.

Key Insights and Results

The authors evaluated Coo using syntactic history testing—generating every possible permutation of transaction histories—alongside standard benchmarks like YCSB and TPC-C. Their findings challenge several long-held assumptions in database theory:

  1. The "Known" is a Tiny Fraction: The study identified over 20 new entity-based anomalies that are not covered by standard textbooks or the SQL standard.
  2. Simplicity Dominates: Over 83% of all possible anomalies are "Single-variable Double-transaction Anomalies" (SDA). This suggests that most data corruption can be prevented using relatively simple, low-cost detection rules.
  3. The Performance Myth: While it is often assumed that weak isolation levels provide a massive performance boost, Coo demonstrates that the benefit of sacrificing isolation is often less than 5%, except in scenarios of extreme data contention.
  4. Dirty Write Frequency: In syntactic tests, "Dirty Write" emerged as the most frequent anomaly, appearing in over 36% of cases.

Conclusion

By establishing the first one-to-one mapping between data anomalies and conflict graphs, Coo provides a rigorous foundation for the next generation of database systems. The framework also introduces new, clearer isolation levels: NRW (No Read and Write anomalies) and NA (No Anomalies, equivalent to true Serializability). While the cost of detecting obscure, multi-variable anomalies remains an engineering challenge, Coo’s insights into the dominance of simple anomalies offer a clear path forward for optimizing concurrency control protocols.

Summary updated

Abstract

Transaction processing technology has three important contents: data anomalies, isolation levels, and concurrent control algorithms. Concurrent control algorithms are used to eliminate some or all data anomalies at different isolation levels to ensure data consistency. Isolation levels in the current ANSI standard are defined by disallowing certain kinds of data anomalies. Yet, the definitions of data anomalies in the ANSI standard are controversial. On one hand, the definitions lack a mathematical formalization and cause ambiguous interpretations. On the other hand, the definitions are made in a case-by-case manner and lead to a situation that even a senior DBA could not have infallible knowledge of data anomalies, due to a lack of a full understanding of its nature. While revised definitions in existing literature propose various mathematical formalizations to correct the former argument, how to address the latter argument still remains an open problem. In this paper, we present a general framework called Coo with the capability to systematically define data anomalies. Under this framework, we show that existing reported data anomalies are only a small portion. While we theoretically prove that Coo is complete to mathematically formalize data anomalies, we employ a novel method to classify infinite data anomalies. In addition, we use this framework to define new isolation levels and quantitatively describe the concurrency and rollback rate of mainstream concurrency control algorithms. These works show that the C and I of ACID can be quantitatively analyzed based on all data anomalies.
BibTeX
@misc{li2021coo,
  author = {Haixiang Li and Xiaoyan Li and Yuxing Chen and Yuean Zhu and Xiaoyong Du and Wei Lu and Chang Liu and Anqun Pan},
  title = {{Coo: Rethink Data Anomalies In Databases}},
  year = {2021},
  eprint = {2109.06485},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.06485},
}
Figure