Robustness Against Read Committed for Transaction Templates with Functional Constraints

Abstract

The popular isolation level multiversion Read Committed (RC) exchanges some of the strong guarantees of serializability for increased transaction throughput. Nevertheless, transaction workloads can sometimes be executed under RC while still guaranteeing serializability at a reduced cost. Such workloads are said to be robust against RC. This paper provides a high level overview of deciding robustness against RC. In particular, we discuss how a sound and complete test can be obtained through the formalization of transaction templates. We then increase the modeling power of transaction templates by extending them with functional constraints which are useful for capturing data dependencies like foreign keys. We show that the incorporation of functional constraints can identify more workloads as robust than would otherwise be the case. Even though the robustness problem becomes undecidable in its most general form, we establish that various restrictions on functional constraints lead to decidable and even tractable results that can be used to model and test for robustness against RC for practical scenarios.