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 (nonserializable) 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. The authors examine this problem. First, they develop a general model for utilizing semantic knowledge. Then, they develop a verification model based on the notion of compatibility among transactions. Their 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