Reducing Conflict Graph Of Multi-step Transactions Accessing Ordered Data With Gaps

Abstract

Specifying the correctness of concurrent transactions contending to access a database is a crucial work. In this research, we adopt the serializability to be the correctness criterion for concurrent transactions accessing ordered data items. One of the most popular technique uses to test serializability is conflict graph. We add a realistic condition on the data items to show that the  corresponding conflict cyclicity can be reduced, in a way, to use temporal-logic-based verification approach in proving serializability.