Flexible Concurrency Control by Reasoning About Database Queries and Updates

Other Titles


A number of database management problems involve reasoning about queries and updates. Concurrency control is the most important example: two transactions should not be executed simultaneously if it is possible that an update command issued by one transaction might change information used in answering a query issued by the other. Existing concurrency control schemes are based on the idea of protecting discrete items of data. This thesis describes a concurrency control scheme called adaptive locking that is based instead on logical reasoning. The central notion is that of independence. Informally, a query is independent of an update if executing the update cannot change the result of evaluating the query. First the general properties of the concept of independence are investigated, using a formal model-theoretic definition in the context of deductive databases. Then proof-theoretic sufficient conditions are obtained for the independence of queries and updates. These results apply to arbitrary queries and updates, and they take into account integrity constraints and recursive rules. For the special case where a query and an update are both specified by conjunctive relational algebra expressions, a decision procedure for independence is given. The procedure is of practical use because typically it requires linear time, and it produces answers that are precise enough to be relied upon. The procedure takes into account functional dependencies, so it constitutes a solution to an open problem identified by Blakeley, Coburn, and Larson. It is of theoretical interest for two reasons. First, its quadratic worst-case time complexity cannot be improved unless the reachability problem for directed graphs can be solved in sublinear time. Second, it applies to the widest possible natural class of queries, since deciding independence is NP-hard for nonconjunctive queries and updates.

Journal / Series

Volume & Issue



Date Issued



Cornell University


computer science; technical report


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record