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.