Systematic definition and classification of data anomalies in DBMS (English Version)

Haixiang Li, Xiao-Yan Li, Chang Liu, Xiaoyong Du, Wei Lu, Anqun PanarXiv 2021 · arXiv

Introduction

In the realm of database management systems (DBMS), ensuring data consistency during concurrent transaction processing is paramount. Historically, the industry has relied on an ad-hoc list of "data anomalies"—such as Dirty Reads, Non-Repeatable Reads, and Write Skews—to define isolation levels. This "whack-a-mole" approach is fundamentally limited; as distributed systems grow more complex, researchers continue to encounter previously undocumented edge cases. This paper addresses the gap by providing a formal, graph-based framework to systematically define and classify all possible data anomalies.

A Formal Graph-Based Framework

The authors move beyond case studies to a unified mathematical model using graph theory. The framework is built on three pillars:

  1. Formalizing Conflicts: Operations like Read (R), Write (W), Commit (C), and Abort (A) are mapped to identify exactly how they conflict when accessing the same data variables.
  2. Partial Order Pairs (POPs): All possible conflicting sequences between two transactions are categorized into 12 distinct POPs.
  3. Partial Order Pair Cycle Graphs (PCGs): These are directed graphs where nodes represent transactions and edges represent the POPs between them.

The central thesis of the paper is that a data anomaly is strictly equivalent to a cycle within a PCG.

Figure 1: A Partial Order Pair Cycle Graph (PCG) showing a complex anomaly involving three transactions ($t_1, t_2, t_3$) and multiple variables ($y, z$).

The Grand Taxonomy

By applying mathematical induction, the authors demonstrate that while the number of potential anomalies is theoretically infinite as the number of transactions scales, complex single-variable anomalies can always be reduced to simpler 2-transaction cycles.

Figure 3: A fundamental 2-transaction cycle illustrating a conflict between $t_i$ and $t_j$. The paper proves that complex anomalies can be reduced to these basic structures.

Based on the types of edges in these cycles, anomalies are grouped into three root families:

  • Write Anomaly Type (WAT): Cycles involving Write-Write conflicts.
  • Read Anomaly Type (RAT): Cycles involving Read-Write conflicts without Write-Write conflicts.
  • Intersect Anomaly Type (IAT): Complex intersections not covered by the above.

Key Results and New Isolation Levels

This systematic enumeration led to the discovery of 22 previously unreported anomalies, bringing the total discussed to 40. Beyond discovery, the framework allows for a more robust definition of isolation levels. Instead of forbidding specific "bugs," isolation levels should forbid specific graph structures.

The authors propose two new frameworks:

  • Simplified (Engineering-focused): Two levels—NRW (No Read-Write anomalies) and NA (No Anomalies, equivalent to Serializability).
  • Fine-grained (Educational): Four levels—NW (No Write anomalies), NRW, NPA (No Predicate Anomalies), and NA.

Conclusion and Future Work

While this framework currently excludes predicate-based anomalies (like Phantoms), it provides the first complete mathematical foundation for understanding transaction isolation. Future work aims to extend the PCG model to include predicates, enabling the design of optimized concurrency control algorithms that target the root causes of inconsistency.

Summary updated

BibTeX
@misc{li2021systematic,
  author = {Haixiang Li and Xiao-Yan Li and Chang Liu and Xiaoyong Du and Wei Lu and Anqun Pan},
  title = {{Systematic definition and classification of data anomalies in DBMS (English Version)}},
  year = {2021},
  eprint = {2110.14230},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2110.14230},
}
Figure