Relative Serializability: An Approach for Relaxing the Atomicity ofTransactions

In the presence of semantic information, serializability is too strong acorrectness criterion and unnecessarily restricts concurrency. We use thesemantic information of a transaction to provide different atomicity views ofthe transaction to other transactions. The proposed approach improvesconcurrency and allows interleavings among transactions which arenon-serializable, but which nonetheless preserve the consistency of thedatabase and are acceptable to the users. We develop a graph-based tool whoseacyclicity is both a necessary and suffcient condition for the correctness ofan execution. Our theory encompasses earlier proposals that incorporatesemantic information of transactions. Furthermore it is the first approachthat provides an effcient graph based tool for recognizing correct scheduleswithout imposing any restrictions on the application domain. Our approach iswidely applicable to many advanced database applications such as systems withlong-lived transactions and collaborative environments.