Formal model for verifying compatibility among transactions

One major problem common to all semantic-based concurrency control systems that have been previously proposed is that of verifying that the allowable (non-serializable) schedules are mutually consistent. In all proposed methods, the verification was assumed to be done by the user. This assumption is both risky and unreasonable for complex database applications. Thus, a formal model is needed so that the verification can be performed by the system. We examine this problem in this paper. First, we develop a general model for utilizing semantic knowledge. Then, we develop a verification model based on the notion of compatibility among transactions. Our model shows that optimizing the verification is a difficult (NP-Hard) problem. Several near-optimal algorithms for performing the verification in polynomial time are also presented.