Modeling and Analysis of Real-Time Database Systems in the Framework of Discrete Event Systems

Abstract

Real-time systems are currently an active area of research currently, motivated by the potential of widespread applicability in areas like stock trading, network management, air traffic control, robotics and factory automation. Since these systems deal with large quantities of information, real-time systems are being coupled with database systems to aid in the efficient storage, processing and retrieval of data. Such database systems are called Real-Time Database Systems (RTDBS).<P>The problem of concurrency control and scheduling of transactions in real time database systems is studied in the framework of discrete event dynamical systems (DEDS) modeled by deterministic finite automata (DFAs). Concurrency control and scheduling are separated into two different modules (a logical DEDS model for the CC module and a heuristic implementation of a scheduler) to allow modular analysis of various combinations of concurrency control and scheduling algorithms. The model is developed analytically using the theory of discrete event dynamical systems. Subsequently the design of a simulation software is reported that uses this model to simulate transaction execution for a (concurrency controller, scheduler) pair. Finally, we show that our approach can also be viewed as a special case of a supervisory control theory (SCT) synthesis technique. The goal of this thesis is to demonstrate the applicability of DEDS theory as a powerful tool in modeling and analyzing transaction models in real time database systems and to show potential applications of modern SCT techniques in this area.