Static and dynamic aspects of goal-oriented concurrency control

A new correctness criterion for schedules of update transactions is proposed, which captures users' intended changes to the database. This is motivated by the observation that traditional serializability may lead to anomalies by not taking into account semantics related to such intended changes. The alternate criterion —goal-correctness — is orthogonal to serializability, and is based on realizing goals associated with each transaction. The problems involved in goal-oriented concurrency control are first identified in a general framework. The analysis suggests that this approach is practical only for restricted transaction languages where goals can be inferred and manipulated efficiently. One such language is then considered, capturing a class of updates of practical interest. For this language, it is shown that goal-oriented concurrency control is tractable and compares favorably to serializability with respect to complexity: testing goal-correctness takes polynomial time, while testing serializability is NP-complete. The set of schedules which are correct with respect to the two criteria are incomparable. Thus, goal-correctness may allow increased concurrency. The results highlight the feasibility and advantages of goal-oriented concurrency control in restricted frameworks. The paper also discusses the dynamic aspects of goal-oriented concurrency control; in particular, an optimistic approach to the dynamic generation of goal-correct schedules is presented.An extended abstract of this paper appeared in the Proceedings of the 2nd Symposium on Mathematical Fundamentals of Database Systems (MFDBS), LNCS 364 (Springer, 1989) pp. 398–414.This author was supported in part by the National Science Foundation, under Grant Number IRI-8816078.