Description
ABSTRACT
In addition to satisfying data consistency requirements as in conventional database systems, concurrency control in real-time database systems must also satisfy timing constraints, such as deadlines associated with transactions. Concurrency control for a real-time database system can be studied from several different perspectives. This largely depends on how the system is specified in terms of data consistency requirements and timing constraints. The objective of this research is to investigate and propose concurrency control algorithms for real-time database systems, that not only satisfy consistency requirements but also meet transaction timing constraints as much as possible, minimizing the percentage and average lateness of deadline-missing transactions. To fulfill the goals of this study, we conduct our research in three phases. First, we develop a model for a real-time database system and study the performance of various concurrency control protocol classes under a variety of operating conditions. Through this study, we understand the characteristics of each protocol and their impact on the performance, and ensure the validity of our real-time database system model by reconfirming the results from previous performance studies on concurrency control for real-time database systems. Second, we choose optimistic technique as the basic mechanism for our study on concurrency control for real-time database systems, and investigate its behavior in a firm deadline environment where tardy transactions are discarded. We present a new optimistic concurrency control algorithm that outperforms previous ones over a wide range of operating conditions, and thus provides a promising candidate for the basic concurrency control mechanism for real-time database systems.
Finally, we address the problem of incorporating deadline information into optimistic protocols to improve their real-time performance.
We present a new priority-cognizant conflict resolution scheme that is shown to provide considerable performance improvement over priority-insensitive algorithms, and to outperform the previously proposed priority-based conflict resolution schemes over a wide operating range. In each step of our research, we report the performance evaluation results by using a detailed simulation model of real-time database system developed in the first phase. In addition to the three phases, we investigate semantic-based concurrency control techniques for real-time database systems, in which the semantics of operations on data objects are used to increase the concurrency of transactions executing on the data objects and to meet the timing constraints imposed on the transactions. We propose an object-oriented data model for real-time database systems.
We present a semantic-based concurrency control mechanism which can be implemented through the use of the concurrency control protocols for real-time database systems studied earlier along with a general-purpose method for determining capabilities of operations.
TABLE OF CONTENTS
iv Acknowledgment
v Abstract
vii Table of Contents
xi List of Figures
xii List of Tables
CHAPTER ONE
1.0 Introduction
1.1. Real-Time Database Systems
1.2. Related Work
1.3. Research Scope and Goals
1.4. Contributions of the Dissertation
1.5. Organization of the Dissertation
1.5 2. Performance of Concurrency Control Algorithms
CHAPTER TWO
2.0 Performance of Concurrency Control Algorithms
2.1. Introduction
2.2. Concurrency Control Algorithms
2.2.1. A Locking Algorithm
2.2.2. An Optimistic Concurrency Control Algorithm
2.2.3. Qualitative Analysis
2.2.4. Implementation Issues
2.3. RTDBS Model
2.3.1. Soft Deadline versus Firm Deadline
2.3.2. Resource Availability
2.4. Experimental Environment
2.4.1. Simulation Model
2.4.2. Parameter Setting
2.4.3. Performance Metrics
2.5. Experiments and Results
2.5.1. Experiment 1: Soft Deadline and Finite Resources
2.5.2. Experiment 2: Soft Deadline and Infinite Resources
2.5.3. Experiment 3: Firm Deadline and Finite Resources
2.5.4. Experiment 4: Firm Deadline and Infinite Resources
2.6. Summary
CHAPTER THREE
3. 0 Dynamic Adjustment of Serialization Order
3.1. Introduction
3.2. Optimistic Concurrency Control
3.2.1. Principles
3.2.2. Unnecessary Restarts
3.3. A New Optimistic Concurrency Control Algorithm
3.3.1. Validation Phase
3.3.2. Read Phase
3.3.3. Write Phase
3.3.4. Correctness
3.3.5. Discussion
3.4. Experimental Environment
3.5. Experiments and Results
3.6. Summary
CHAPTER FOUR
4.0 Design of Real-Time Optimistic Concurrency Control
4.1. Introduction
4.2. The Choice of Optimistic Protocol
4.3. Deadline-Cognizant Conflict Resolution Policies
4.3.1. No Sacrifice
4.3.2. Always Sacrifice
4.3.3. Conservative Sacrifice
4.3.4. Unavoidable Sacrifice
4.3.5. Adaptive Sacrifice
4.4. Our Approach
4.4.1. Feasible Sacrifice
4.4.2. Predictable Transaction Execution
4.5. Experimental Environment
4.6. Experiments and Results
4.6.1. Experiment 1: Moderate Data Contention
4.6.2. Experiment 2: High Data Contention
4.6.3. Experiment 3: Write Probability
4.7. Summary
CHAPTER FIVE
5. 0 Semantic-Based Concurrency Control
5.1. Introduction
5.1.1. Background
5.1.2. Our Work
5.2. An Object-Oriented Data Model for RTDBS
5.2.1. Basic Concepts
5.2.2. Object Model
5.2.3. Relationship Model
5.2.4. Transaction Model
5.2.5. An Example
5.2.6. Discussion
5.3. Design Issues
5.3.1. Compatibility Relation
5.3.2. Concurrency Control Algorithms
5.3.3. Inter-Object Data Consistency
5.4. Related Work
5.5. Our Approach
5.5.1. Compatibility Relation by Affected-Set
5.5.2. Real-Time Concurrency Control Algorithms
5.6. Summary
CHAPTER SIX
6.0 Conclusions
6.1. Summary of the Work
6.2. Future Directions
Bibliography
Appendix: Concurrency Control Theory
Concurrency Control Problem
A.1.1. Examples of Concurrency Control Anomalies
A.1.2. The Concept of Transaction
A.1.3. Serializability
A.2. Traditional Approaches to Concurrency Control
2.1. Two-Phase Locking
A.2.2. Timestamp Ordering
A.2.3. Multiversion Timestamp Ordering
A.2.4. Optimistic Concurrency Contro