Optimization Of Concurrency Control Algorithms In Real-Time Database Systems

A Real-Time Database System (RTDBS) is a database system designed to process transactions with timing constraints, i.e. deadlines. In RTDBSs, the primary criterion is the percentage of the transactions that miss their deadlines, i.e. miss ratio. Lower the miss ratio, better the performance of RTDBSs. The transactions are scheduled by their priorities assigned according to their deadlines and values, but the concurrency control algorithms for traditional database systems are not priority-cognizant. In recent years, many researches have been devoted to designing appropriate concurrency control algorithms for RTDBSs, which need not only satisfy consistency requirements but also meet transaction timing constraints as much as possible to minimize the percentage of late transactions. There are still some problems in concurrency control algorithms for RTDBSs, such as wasted restart, wasted wait, wasted execution, unnecessary restart. In this thesis, the studies emphasize on optimization of concurrency control algorithms for real-time database systems. The main works are shown below:First, a new method, called sacrifice of restarted transactions which can improve the performance of RTDBSs under high load condition, is proposed to resolve wasted execution problem. Sacrifice of restarted transactions can give the transactions never restarted higher priorities under high load condition for the possibility of satisfying the deadlines of restarted transactions is lower than that of satisfying the deadlines of the transactions never restarted. The simulation results show that the algorithm based on sacrifice of the restarted transactions, called OCC-CLRTP, outperforms the previous algorithms.Second, a new method, called dynamic adjustment of execution order which can reduce the number of transaction restarts and minimize the miss ratio of RTDBSs, is proposed to resolve unnecessary restart problem. Dynamic adjustment of execution order can not only adjust the serialization order dynamically but also adjust the execution order of read and write operations dynamically to avoid the unnecessary restarts efficiently.Third, a new optimistic concurrency control algorithm based on dynamic adjustment of execution order using commit space in RTDBSs, called OCC-CS, is introduced and the complexity of this algorithm is analyzed. The extra memory spent in OCC-CS can be reduced by restricting the size of the semi-committed set which doesn't impact the performance of OCC-CS. Four algorithms are presented to implement the OCC-CS algorithm, including CS-LEFT, CS-RIGHT, CS-ALT and CS-LRC. The simulation results show that the CS-ALT algorithm can avoid more unnecessary restarts than the OCC-DATI algorithm based on dynamic adjustment of serialization order and outperforms OCC-DATI.Fourth, a new algorithm integrating sacrifice of restarted transactions and dynamic adjustment of execution order, called CS-ALT-CLRTP, is proposed to optimize the performance of RTDBSs. This algorithm can not only decrease the wasted execution under high load condition but also reduce the number of transaction restarts to improve the performance of RTDBSs. The simulation results show that theCS-ALT-CLRTP algorithm behaves the best under all load conditions.Finally, a real-time database test platform which is extensible and configurable is designed and developed to analysis and compare the concurrency control algorithms for RTDBSs. The architecture of the test platform is introduced and the architecture and implementation of concurrency control are discussed. Furthermore, how to implement sacrifice of restarted transactions and dynamic adjustment of execution order over the basic concurrency control architecture is discussed in this thesis.