Browse Prior Art Database

An Optimality Theory of Concurrency Control for Databases

IP.com Disclosure Number: IPCOM000128134D
Original Publication Date: 1980-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 38K

Publishing Venue

Software Patent Institute

Related People

H. T. Kung: AUTHOR [+4]

Abstract

A concurrency control mechanism (or a schcdulcr) is the component of a database systein that &ifeguards the consistency of the database in the presence of interleaved accesses and update requests. We formally show that die performance of a schedulcr, i.e., the amount of parallelism that it supports, depends explicitly upon the amount of information that is available to the scheduter. We point out that most previous work on concurrency control is simply concerned with specific points of this basic trade-off between performance and information. In fact, several of these approaches are shown to be optimal for the amount of information that they use.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

An Optimality Theory of Concurrency Control for Databases'

H. T. Kung C. H. Papadimitriou

Department of Computer Science Carnegie-Mellon University Pittsburgh, Pennsylvania 15213

Laboratory for Computer Science Massachusetts Institute of Technology Cambridge, Massachusetts 02139

April 1979

[Last revised September 19801

(This paper is issued simultaneously as a QIU and MIT Technical Memorandum)

KEYWORDS AND PHRASES: Database,Concurrency Control, Schedulers, Performance vs. Informa:tion of Schedulers, Optimal Schedulers.

This research is supported in part by the National Science Foundation under Grants MCS 7S- 222-55, MCS 77-01193, MCS 77-05314, the Office of Naval Research under Contract N00014- 76-C-0370, and a Miller Fellowship.

Abstract

A concurrency control mechanism (or a schcdulcr) is the component of a database systein that &ifeguards the consistency of the database in the presence of interleaved accesses and update requests. We formally show that die performance of a schedulcr, i.e., the amount of parallelism that it supports, depends explicitly upon the amount of information that is available to the scheduter. We point out that most previous work on concurrency control is simply concerned with specific points of this basic trade-off between performance and information. In fact, several of these approaches are shown to be optimal for the amount of information that they use.

1. Introduction

A database system may interact with many transactions in an interleaved manner. Even if we assume that each such individual transaction is correct (that is, it preserves the consistency of the databases when run by itself), the interleaved mode of operation may result in inconsistencies (see, for example, [21). It is the task of the concurrency control mechanism of the database system, called scheduler in this paper, to safeguard the consistency of the database by granting or rejecting the execution of atomic steps of transactions, when requests for such executions are made.

The design of schedulers for databases has proved to be a non-trivial problem, and some theoretical work on the subject has appeared (see, for example, [2, 6,7, 91). Several solutions to this problem have been proposed under a variety of assumptions. In this paper, we give a uniform framework for evaluating these solutions, and, in some cases, for establishing their optimality. A scheduler is evaluated in terms of its performance, which is measured by the set of

Massachusetts Institute of Technology Page 1 Dec 31, 1980

Page 2 of 12

An Optimality Theory of Concurrency Control for Databases

request sequences that the schedulcr can authorize for execution without any delay. This set of request sequences is called the fixpoint set of the schcduler. ne idea is that the richer this set is, the more likely that no delays will be imposed by the schedulcr. In this sense the fixpoint set is a fair measure of the p...