------------------------------------------------------------------------------- B O S T O N U N I V E R S I T Y Computer Science Department P H D D E F E N S E Friday June 17, 1994 2:00pm (Coffee served at 1:30pm) Seminar Room / MCS 135 ------------------------------------------------------------------------------- Concurrency Control Protocols for Real-Time Databases Ph.D. Thesis Defense by Spyridon Braoudakis Abstract Concurrency control methods developed for traditional database systems are not appropriate for real-time database systems (RTDBS), where, in addition to database consistency requirements, satisfying timing constraints is an integral part of the correctness criterion. Most real-time concurrency control protocols considered in the literature combine time-critical scheduling with traditional concurrency control methods to conform to transaction timing constraints. These methods rely on either transaction "blocking" or "restarts", both of which are inappropriate for real-time concurrency control because of the "unpredictability" they introduce. Moreover, RTDBS performance objectives differ from those of conventional database systems in that maximizing the number of transactions that complete before their deadlines becomes the decisive performance objective, rather than merely maximizing concurrency (or throughput). Recently, Speculative Concurrency Control (SCC) was proposed as a categorically different approach to concurrency control for RTDBS. SCC relies on the use of "redundant" processes ("shadows"), which "speculate" on alternative schedules, once conflicts that threaten the consistency of the database are detected. SCC algorithms utilize added system resources to ensure that correct (serializable) executions are discovered and adopted as early as possible, thus increasing the likelihood of the timely commitment of transactions. This dissertation starts by reviewing the Order-Based SCC (SCC-OB) algorithm which associates almost as many shadows as there are serialization orders of transactions. After demonstrating SCC-OB's excessive use of redundancy, we introduce a host of novel SCC-based protocols. Conflict-Based SCC (SCC-CB) reduces the number of shadows that a running transaction needs to keep by maintaining one shadow per uncommitted conflicting transaction. We show that the quadratic number of shadows maintained by SCC-CB is optimal, covering "all" serialization orders produced by SCC-OB. We establish SCC-CB's correctness by showing that it admits only serializable histories. Next, we explore the trade-off between the number of shadows and timeliness. We present a generic SCC algorithm (SCC-kS) that operates under a limited redundancy assumption; it allows no more than a constant number $k$ of shadows to coexist on behalf of any uncommitted transaction. Next, we propose a novel technique to incorporate additional information such as "deadline", "priority" and "criticalness" within the SCC methodology. SCC with Deferred Commit (SCC-DC) utilizes this additional information to improve the timeliness through the controlled "deferment" of transaction commitments. We develop a probabilistic Value Induced Shadow Allocation (VISA) policy which aims at preserving the most "valuable" shadows for each system transaction. The thesis of this dissertation is that SCC-based algorithms offer a new dimension, "redundancy", to improve the "timeliness" of RTDBS. SCC-based algorithms are efficient (quadratic number of shadows is optimal), scalable (redundancy can be traded-off for timeliness), and easily amendable (deadline and priority information can be incorporated). Major Advisor: Prof. Azer Bestavros -------------------------------------------------------------------------------