Browse Prior Art Database

CONCURRENCY, C6ftA I OL PERFORMANCE EVALUATION

IP.com Disclosure Number: IPCOM000128166D
Original Publication Date: 1982-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 23 page(s) / 58K

Publishing Venue

Software Patent Institute

Related People

Oded Shmueli: AUTHOR [+4]

Abstract

Concurrency Control Mechanisms (CCMs) in multi-user database systems are assigned the task of regulating the concurrent access to shared data so that basic integrity constraints of the database are preserved. Although the theory o f COI correctness has achieved a degree of mathemati-cal maturity, the theory of quantitative performance evaluation of the various CCMs is still in its infancy. This stems from the enormous number of C01s, the complexity of the algorithms, the lack of a precise descrip-tion in some standard terminology and different (and sometimes incorkparable) assumptions employed about the underlying environment.

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

Page 1 of 23

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

CONCURRENCY, C6ftA I OL PERFORMANCE EVALUATION

(A Methodology and an Application to Two Phase Locking)

Oded Shmueli* Paul Spirakis**

November 1982 Ub Technicylkelport - No; -54

Hebrew University, Jerusalem, Israel

Courant Institute of Mathematical Sciences, New York Universitv

This work was supported in part by the NSF grant NSF-MC579-21024 and the ONR Contract N00014-80-C-0674.

The simulations for this paper were done during the summer of 1982, when both authors were at Harvard University.

ABSTRACT

Concurrency Control Mechanisms (CCMs) in multi-user database systems are assigned the task of regulating the concurrent access to shared data so that basic integrity constraints of the database are preserved. Although the theory o f COI correctness has achieved a degree of mathemati-cal maturity, the theory of quantitative performance evaluation of the various CCMs is still in its infancy. This stems from the enormous number of C01s, the complexity of the algorithms, the lack of a precise descrip-tion in some standard terminology and different (and sometimes incorkparable) assumptions employed about the underlying environment.

in this paper we propose a methodology for analyzing the Performance of CC14s. The methodology is based on paradigms of the physical sciences. Controlled experiments lead to hypotheses about system behavior and then a model is proposed, trying to explain the experimental data. The model is then refined by comparing its predicted results to results of new experiments. we apply this methodology to

(Equation Omitted)

The experimental tools used are detailed simulation programs. Several interesting trends of behavior were observed. For example, the mean dead-lock rate was observed to be logarithmic in the ratio of transactions in the system divided by total number of database items.

We also propose a model for explaining t he experimental results, using the theory of the occupancy problems and Markov processes. The model cap-tures the basic trends of the system behavior with a high degree of accuracy. Also, several variations of dynamic 2PI, are compared and tested.

1. INTRODUCTION

Northwestern University Page 1 Dec 31, 1982

Page 2 of 23

CONCURRENCY, C6ftA I OL PERFORMANCE EVALUATION

Concurrency Control Mechanisms (CCMs) in multi-user database systems are assigned the task of regulating the concurrent access to shared data. A concurrency control mechanism operates correctly if it presents a con-sistent and coherent view to each user; one way to express that mathematically is by the theory of

(Equation Omitted)

in additiL to correctness, good performance determines the usefulness of a CCM. The word performance (applied to Cals) is a vague term and has been quantified differently by various authors. while the studies of correctness of CC.Ms achieved a degree of mathematical maturity, the theory of CCM performance is still in its infancy.

The reason for th...