Abstract

Data in real-time databases has to be logically consistent as well as

temporally consistent. The latter arises from the need to preserve the
temporal validity of data items that react the state of the environment
that is being controlled by the system. Some of the timing constraints on
the transactions that process real-time data come from this need. These
constraints, in turn, necessitate time-cognizant transaction processing so
that transactions can be processed to meet their deadlines.

This paper explores the issues in real-time database systems and

presents an overview of the state of the art. After introducing the
characteristics of data and transactions in real-time databases, we
discuss issues that relate to the processing of time-constrained
transactions. Specially, we examine die rent approaches to resolving
contention over data and processing resources. We also explore the
problems of recovery, managing I/O, and handling overloads. Real-time
databases have the potential to trade o the quality of the result of a
query or a transaction for its timely processing. Quality can be
measured in terms of the completeness, accuracy, currency, and
consistency of the results. Several aspects of this tradeoff are also
considered

Page 1 of 29
 CONTENTS

1 Introduction…………………………………………………………………………………………3
1.1 Databases and Real-Time Systems………………………………………………4
1.2 Why Real-Time Databases? ………………………………………………………..5

2 Characteristics of Data in Real-Time Database Systems……………………….7

3 Characteristics of Transactions in Real-Time Database Systems………….10

4 Relationship to Active Databases ………………………………………………………12

5 Other Issues in Real-Time Database Systems………………………………… ….14

5.1 Managing I/O and Bu ers………………………………………………………….14
5.2 Performance Enhancement: Trading o Quality for Timeliness. ….19
5.3 Recovery Issues………………………………………………………………………..17
5.4 Managing Overloads………………………………………………………………..21

6 Conclusions………………………………………………………………………………………22

Page 2 of 29
 1. Introduction
Many real-world applications involve time-constrained access to data as
well as access to data that has temporal validity. For example, consider
telephone switching systems, network management, program stock
trading, managing automated factories, and command and control
systems. More specially, consider the following activities within these
applications: looking up the \800 directory", radar tracking and
recognition of objects and determining appropriate response, as well as
the automatic tracking and directing of objects on a factory
our. All of these involve gathering data from the environment, processing
of gathered information in the context of information acquired in the past,
and providing timely response. Another aspect of these examples is that
they involve processing both temporal data, which loses its validity after a
certain interval, as well as archival data.
For instance, consider recognizing and directing objects moving along a set
of conveyor belts on a factory our. An object's features are captured by a
camera to determine its type and to recognize whether it has any
abnormalities. Depending on the observed features, the object is directed
to the appropriate work cell. In addition, the system updates its database
with information about the object. The following aspects of this example
are noteworthy. First of all, features of an object must be collected while
the object is still in front of the camera. The collected features apply just to
the object in front of the camera, i.e., they lose their validity once a direct
object enters the system. Then the object must be recognized by matching
the features against models for different objects stored in a database. This
matching has to be completed in time so that the command to direct the
object to the appropriate destination can be given before the object
reaches the point where it must be directed onto a different conveyor belt
that will carry it to its next work cell. The database update must also be
completed in time so that the system's attention can move to the next
object to be recognized. If, for any reason, time-constrained actions are
Page 3 of 29
not completed within the time limits, alternatives may be possible. In this
example, if feature extraction is not completed in time, the object could be
discarded for now to be brought back in front of the camera at a later
point in time. Applications such as these introduce the need for real-time
database systems.
During the last few years, the area of real-time databases has attracted the
attention of researchers in both real-time systems and database systems.
The motivation of the database researchers has been to bring to bear
many of the benefits of database technology to solve problems in
managing the data in real-time systems. Real-time system researchers
have been attracted by the opportunity real-time database systems
provides to apply time-driven scheduling and resource allocation
algorithms. However, as we shall see, a simple integration

of concepts, mechanisms, and tools from database systems with those from
real-time systems is not feasible. Even a cursory examination of the
characteristics of database systems and the requirements of real-time
systems will point out the various forms of \impedance mismatch" that
exist between them. Our goal in this paper is to point out the special
characteristics, in particular the temporal consistency requirements, of
data in real-time databases, and show how these lead to the imposition of
time constraints on transaction execution. Meeting these timing
constraints demands new approaches to data and transaction
management some of which can be derived by tailoring, adapting, and
extending solutions proposed for real-time systems and database systems.
Hence, as we present the issues in real-time database systems, we review
recent attempts at developing possible approaches to addressing these
issues.

1.1 Databases and Real-Time Systems;

Traditional databases, hereafter referred to simply as databases, deal with

persistent data. Transactions access this data while maintaining its
Page 4 of 29
consistency. Serializability is the usual correctness criterion associated with
transactions. The goal of transaction and query pro- cussing approaches
adopted in databases is to achieve a good throughput or response time.

In contrast, real-time systems, for the most part, deal with temporal data,
i.e., data that becomes outdated after a certain time. Due to the temporal
nature of the data and the response time requirements imposed by the
environment, tasks in real-time systems possess time constraints, e.g.,
periods or deadlines. The resulting important di erence is that the goal of
real-time systems is to meet the time constraints of the activities.
One of the key points to remember here is that real-time does not just
imply fast. Recall the story of the tortoise and the hare. The hare was fast
but was \busy" doing the wrong activity at the wrong time. Even though
we would like real-time systems to be faster than the tortoise, we do
require them to possess its predictability. Also, real-time does not imply
timing constraints that are in nanoseconds or seconds. For our purposes,
real-time implies the need to handle explicit time constraints, that is, to
use time-cognizant protocols to deal with deadlines or periodicity
constraints associated with activities.

1.2 Why Real-Time Databases?

Databases combine several features that facilitate (1) the description of

data, (2) the main- tenance of correctness and integrity of the data, (3) e
cient access to the data, and (4) the correct executions of query and
transaction executions in spite of concurrency and failures. Speci cally,

 database schemas help avoid redundancy of data as well as of its

description,

 data management support, such as indexing, assists in e cient access

to the data, and

Page 5 of 29
  transaction support, where transactions have ACID (Atomicity,
Consistency, Isolation, and Durability) properties, ensures correctness
of concurrent transaction executions and ensure data integrity
maintenance even in the presence of failures.

However, support for real-time database systems must take into account
the following. Firstly, not all data in a real-time database are permanent;
some are temporal. Secondly, temporally-correct serializable schedules are
a subset of the serializable schedules. Thirdly, since timeliness is more
important than correctness, in many situations, (approximate) cor-
rectness can be traded for timeliness. Similarly, atomicity may be relaxed.
For instance, this happens with monotonic queries and transactions, which
are the counterparts of monotonic tasks [35] in real-time systems.
Furthermore, many of the extensions to serializability that have been
proposed in databases are also applicable to real-time databases (See [41]
for a review of these proposals). Some of these assume that isolation of
transactions may not always be needed.

In spite of these di erences, given the many advantages of database

technology, it will be bene cial if we can make use of them for managing
data found in real-time systems. In a similar vein, the advances made in
real-time systems to process activities in time could be exploited to deal
with time-constrained transactions in real-time database systems.
As illustrated by the examples cited at the beginning of this section, many
real-time applications function in environments that are inherently
distributed. Furthermore, many real-time systems employ parallel
processing elements for enhanced performance. Hence parallel and
distributed architectures are ubiquitous in real-time applications and
hence real-time database systems must be able to function in the context
of such architectures.
The above discussion indicates that while many of the techniques used in
real-time sys- tems on the one hand, and databases systems on the other
hand, may be applicable to real-time database systems, many crucial di
Page 6 of 29
erences exist which either necessitate fresh ap- proaches to some of the
problems or require adaptations of approaches used in the two areas. In
the rest of the paper we will be substantiating this claim.

2 Characteristics of Data in Real-Time Database Systems

Typically, a real{time system consists of a a controlling system and a

controlled system. For example, in an automated factory, the controlled
system is the factory oor with its robots, assembling stations, and the
assembled parts, while the controlling system is the computer and human
interfaces that manage and coordinate the activities on the factory oor.
Thus, the controlled system can be viewed as the environment with which
the computer interacts.
The controlling system interacts with its environment based on the data
available about the environment, say from various sensors, e.g.
temperature and pressure sensors. It is imperative that the state of the
environment, as perceived by the controlling system, be consistent with
the actual state of the environment. Otherwise, the e ects of the
controlling systems' activities may be disastrous. Hence, timely monitoring
of the environment as well as timely processing of the sensed information
is necessary. The sensed data is processed further to derive new data. For
example, the temperature and pressure information pertaining to a
reaction may be used to derive the rate at which the reaction appears to
be progressing. This derivation typically would depend on past
temperature and pressure trends and so some of the needed information
may have to be fetched from archival storage (a temporal database [46]).
Based on the derived data, where the derivation may involve multiple
steps, actuator commands are set. For instance, in our example, the
derived reaction rate is used

to determine the amount of chemicals or coolant to be added to the

reaction. In general, the history of (interactions with) the environment are
Page 7 of 29
 also logged in archival storage.
In addition to the timing constraints that arise from the need to
continuously track the environment, timing correctness requirements in a
real{time (database) system also arise because of the need to make data
available to the controlling system for its decision-making activities. For
example, if the computer controlling a robot does not command it to stop
or turn on time, the robot might collide with another object on the factory
oor. Needless to say, such a mishap can result in a major catastrophe.
The need to maintain consistency between the actual state of the
environment and the state as re ected by the contents of the database
leads to the notion of temporal consistency. Temporal consistency has two
components [48, 4]:

Absolute consistency { between the state of the environment and its re

ection in the database.
As mentioned earlier, this arises from the need to keep the controlling
system's view of the state of the environment consistent with the actual
state of the environment.
Relative consistency { among the data used to derive other data.
This arises from the need to produce the sources of derived data close to
each other.

Let us de ne these formally. Let us denote a data item in the real-time

database by d : (value; avi; timestamp)
where dvalue denotes the current state of d, and dtimestamp denotes the
time when the obser- vation relating to d was made. davi denotes d's
absolute validity interval, i.e., the length of the time interval following
dtimestamp during which d is considered to have absolute validity.
A set of data items used to derive a new data item form a relative
consistency set. Each such set R is associated with a relative validity
interval denoted by Rrvi.
Assume that d 2 R.
d has a correct state i
Page 8 of 29
1. dvalue is logically consistent { satis es all integrity constraints.

2. d is temporally consistent:

Absolute consistency: (current time - dtimestamp) < davi.

Relative consistency: for all di belongs to R; j timestamp d0j Rrvi:

Consider the following example: Suppose temperatureavi = 5, pressureavi =

10, R = ftemperature; pressureg, and Rrvi = 2: If current time = 100, then
(a) temperature = (347; 5; 95) and pressure = (50; 10; 97) are temporally
consistent, but (b) temperature = (347; 5; 95) and pressure = (50; 10; 92)
are not. In (b), even though the absolute consistency requirements are
met, R's relative consistency is violated.
Whereas a given avi can be realized by sampling the corresponding real-
world parameter often enough, realizing an rvi may not be that
straightforward. This is because, achieving a given rvi implies that the data
items that belong to a relative consistency set have to be observed at
times close to each other.
Also, achieving an rvi along with the avi's will mean that smallest of the
avi's of the data items belonging to the relative consistency set will prevail.
Consider the temperature and pressure example, where both of them
belong to R. The transactions writing temperature and pressure,
respectively, must always write them within 2 time units of each other.
This will implicitly lower the avi of pressure to 5.
One way out of this predicament is to realize that relative consistency
requirements result from the need to derive data from data produced
within close proximity of each other. Thus meeting relative consistency
requirements is necessary only when data is used to derive other data. So
rather than reducing the avi's, we need to ensure that an rvi is satis ed just
when a transaction is executed to derive new data.
If two data items belong to multiple relative consistency sets, the smallest
Page 9 of 29
of the rvi's will prevail. Suppose temperature and pressure also belong
to relative consistency sets R0
where R0= 1. Clearly, the timestamps of temperature and pressure
must be within 1 time unit of each other to satisfy the relative consistency
requirements of R and R0 .
Another issue in this context relates to the manner in which timestamps of
derived data are set. Clearly, there will be some correlation between these
timestamps and those of the data from which new data is derived. One
possibility is to assign the timestamp of d0 derived from data items in R
to be equal to mind 2 R (timestamp) [48]. That is, derived data is only as
recent as the oldest data from which the derivation occurs. In general,
however, temporal validity criteria are likely to be application dependent
and so the timestamp of derived data can be stated as some function of
those of the data in the corresponding R [4].

3 Characteristics of Transactions in Real-Time Database Systems

In the rst part of this section, transactions are characterized along three
dimensions based on the nature of transactions in real-time database
systems: the manner in which data is used by transactions, the nature of
time constraints, and the signi cance of executing a transaction by its
deadline, or more precisely, the consequence of missing speci ed time

constraints. Subsequently, we show how the temporal consistency

requirements of the data lead to some of the time constraints of
transactions.
Real-time database systems employ all three types of transactions
discussed in the database literature. For instance,

Write-only transactions obtain state of the environment and write into

the database.

Page 10 of 29
 Update transactions derive new data and store in the database.

Read-only transactions read data from the database and send them to
actuators.

The above classi cation can be used to tailor the appropriate concurrency
control schemes.
Some transaction time constraints come from temporal consistency
requirements and some come from requirements imposed on system
reaction time. The former typically take the form of periodicity
requirements: For example,
Every 10 seconds Sample wind velocity.
Every 20 seconds Update robot position.
We show later in this section how the periodicity requirements can be
derived from the avi of the data.
System reaction requirements typically take the form of deadline
constraints imposed on aperiodic transactions: For example,
If temperature > 1000
within 10 seconds add coolant to reactor.
In this case, the system's action in response to the high temperature must
be completed by
10 seconds.
Transactions can also be distinguished based on the e ect of missing a
transaction's deadline. In this paper, we use the terms hard, soft and rm to
categorize the transactions. Viewed di erently, this categorization tells us
the value imparted to the system when a transaction meets its deadline.
Whereas arbitrary types of value functions can be associated with
activities [28], we con ne ourselves to simple functions as described below.

Hard deadline transactions are those which may result in a catastrophe if

the deadline is missed. One can say that a large negative value is imparted
to the system if a hard deadline is missed.
These are typically safety-critical activities, such as those that respond to
Page 11 of 29
life or environment-threatening emergency situations.

Soft deadline transactions have some value even after their deadlines.
Typically, the value drops to zero at a certain point past the deadline. If
this point is the same as the deadline, we get rm deadline transactions {
which impart no value to the system once their deadlines expire [21].
For example, if components of a transaction are assigned deadlines derived
from the deadline of the transaction, then even if a component misses its
deadline, the overall transaction might still be able to make its deadline.
Hence these deadlines are soft. Another example is that of a transaction
that is attempting to recognize a moving object. It must complete
acquiring the necessary information before the object goes outside its view
and hence has a rm deadline.

4 Relationship to Active Databases

Many of the characteristics of data and transactions discussed in the last

two sections may remind a reader of active databases. Hence this section
is devoted to a discussion of the speci c distinctions between active
databases and real-time databases.
The basic building block in active databases is the following: ON event
IF condition DO action.
Upon the occurrence of the speci ed event, if the condition holds, then the
speci ed action can be taken. This construct provides a good mechanism
by which integrity constraints can be maintained among related or
overlapping data or by which views can be constructed [13]. The event can
be arbitrary, including external events (as in the case of real-time events
generated by the environment), timer events, or transaction related events
(such as the begin and commit of transactions). The condition can
correspond to conditions on the state of the data or the environment.
The action is said to be triggered [33, 12] and it can be an arbitrary
transaction.
Page 12 of 29
Given this, it is not di cult to see that active databases provide a good
model for the arrival (i.e., triggering) of periodic/aperiodic activities based
on events and conditions. Even though the above construct implies that an
active database can be made to react to timeouts, time constraints are
not explicitly considered by the underlying transaction

processing mechanism.
However, as we have discussed before, the primary goal of real-time
database systems is to complete the transactions on time. One can thus
state the main de ciency in active databases in relation to what is required
for them to deal with time constraints on the completion of transactions:
time constraints must be actively taken into consideration.
Consider a system that controls the landing of an aircraft. Ideally, we would
like to ensure that once the decision is made to prepare for landing,
necessary steps, for example, to lower the wheels, to begin deceleration,
and to reduce altitude, are completed within a given duration, say 10
seconds. Here the steps may depend on the landing path, the constraints
speci c to the airport, and the type of aircraft, and hence may involve
access to a database containing the relevant information. In those
situations where the necessary steps have not been completed in time, we
would like to abort the landing within a given deadline, say within 5
seconds; the abort must be completed within the deadline, presumably
because that is the \cushion" available to the system to take alternative
actions. This requirement can be expressed as follows:
ON (10 seconds after \initiating landing preparations")
IF (steps not completed)
DO (within 5 seconds \Abort landing").

In summary, while active databases possess the necessary features to deal

with many aspects of real-time database systems, the crucial missing
ingredient is the active pursuit of the timely processing of actions.

Page 13 of 29
 5 Other Issues in Real-Time Database Systems

In this section, we would like to bring together a number of issues that have
not been adequately addressed in the real-time database literature. These
include managing resources other than CPU and data, trading o timeliness
for quality, managing recovery, and handling overloads. The subsections in
this section deal with these topics individually. Since little work has been
done in these areas, the discussion is, by necessity, speculative.

5.1 Managing I/O and Bffers

Whereas the scheduling of CPU and data resources has been studied fairly
extensively in the real-time database literature, studies of scheduling
approaches for dealing with other resources, such as disk I/O, and bu ers
has begun only recently. In this section we review some recent work in this
area and discuss some of the problems that remain.
I/O scheduling is an important area for real-time systems given the large di
Terence in speeds between CPU and disks and the resultant impact of I/O
devices' responsiveness on performance. However, real-time systems
research has essentially ignored this problem

Because of the perception that disk access introduces high degree of

unpredictability and so disks are seldom accessed when time constraints
exist. However, in real-time database systems the reading and writing of
(archival) data is essential and so disk scheduling when transactions have
time constraints becomes a signi cant problem. Since the traditional disk
scheduling algorithms attempt to minimize average I/O delays, just like
traditional CPU scheduling algorithms aim to minimize average processing
delays, time-cognizant I/O scheduling approaches are needed.
It must be recognized that what is important is the meeting of transaction
deadlines and not the individual deadlines that may be attached to I/O
requests. Assume that we model a transaction execution as a sequence of
Page 14 of 29
 (disk I/O, computation) pairs culminating in a set of disk I/O's, the latter
arising from writes to log and to the changed pages. Suppose we assign
(intermediate) deadlines to the I/O requests of a transaction given the
transaction's deadline. One of the interesting questions with regard to disk
I/O scheduling is: How does one derive the deadline for an I/O request
from that of the requesting transaction? First of all, it must be recognized
that depending on how these I/O deadlines are set, deadlines associated
with I/O requests may be soft since even if a particular I/O deadline is
missed, the transaction may still complete by its deadline. This is the case
if I/O deadlines are set such that the overall laxity (i.e., the di erence
between the time available before the deadline and the total computation
time) of a transaction is uniformly divided among the computations and
the I/O. On the other hand, assume that an intermediate deadline is equal
to the latest completion time (i.e., the time an I/O must complete
assuming that subsequent computations and I/O are executed without
delay). This is the less preferred method since we now have a rm deadline
associated with I/O requests { if an I/O deadline is missed, there is no way
for the transaction to complete by its deadline and so the requesting
transaction must be aborted.
Recent work on I/O scheduling includes [10, 3, 11]. The priority driven
algorithm de- scribed in [10] is a variant of the traditional SCAN algorithm
which works on the elevator principle to minimize disk arm movement.
Without specifying how priorities are assigned to individual I/O requests,
[10] proposes a variant in which the SCAN algorithm is applied to each
priority level. Requests at lower priority are serviced only after those at
higher priority are served. Thus, if after servicing a request, one or more
higher priority requests are found waiting, the disk arm moves towards the
highest priority request that is closest to the current disk arm position. In
the case of requests arising from transactions with deadlines, priority
assignment could be based on the deadline assigned to the I/O request.
Another variant of SCAN, one which directly takes I/O deadlines into
account is FD-

Page 15 of 29
SCAN [3]. In this algorithm, given the current position of the disk arm, the
disk arm moves towards the request with the earliest deadline that can
be serviced in time. Requests that lie in that direction are serviced and
after each service it is checked whether (1) a request with an even earlier
deadline has arrived and (2) the deadline of the original result cannot be
met. In either case, the direction of disk arm movement may change.
Clearly, both these protocols involve checks after each request is served and
so incur substantial run-time overheads. The protocols described in [11]
are aimed at avoiding the impact of these checks on I/O performance.
Speci cally, the protocols perform the neces- sary computations while I/O is
being performed. In the SSEDO algorithm (Shortest-seek and Earliest
Deadline by Ordering), the need to give higher priority to requests with
ear- lier deadlines is met while reducing the overall seek times. The latter is
accomplished by giving a high priority to requests which may have large
deadlines but are very close to the current position of the disk arm. A
variant of SSEDO is SSEDV which works with speci c Deadline Values, rather
than Deadline Orderings. [11] shows how both the algorithms can be
implemented so as to perform disk scheduling while service is in progress
and shows that the algorithms have better performance than the other
variants of the SCAN algorithms.
Another resource for which contention can arise is the database bu er.
What we have here is a con ict over bu er slots { akin to con icts that occur
over a time slot, in the case of a CPU. Thus, similar issues arise here also.
Speci cally, how to allocate bu er slots to transactions and which slots to
replace when a need arises are some of the issues. Consider bu er
replacement: in case there is a need to replace an existing bu er slot to
make room for a new entry, the replacement policy may have an impact
on performance, especially if the slot being replaced is used by an
uncommitted transaction. Work done in this area includes [24, 10].
Whereas [24] reports of no signi cant performance improvements when
time-cognizant bu er management policies are used, studies discussed in
[10] show that transaction priorities must be considered in bu er
management. Clearly, the jury is still out on the issue and further work is
Page 16 of 29
needed.

5.2 Performance Enhancement:

Trading o Quality for Timeliness

Before we examine the speciec performance enhancement possibilities
unique to real-time database systems, it is important to point out that
several proposals made for performance enhancement in traditional
databases are also applicable to real-time databases. For in- stance, given
that the data objects in real-time database systems will be abstract data
type objects, as opposed to read/write objects, the semantics of the
operations on these objects

can be exploited to improve concurrent access to these objects (see, for

example, [5]). Gen- eralizing this, the parallelism and distribution inherent
in real-time systems, which by their very nature function in physically
distributed environments with multiple active processing elements, can be
put to use to improve performance. Of course, as we discussed earlier,
distribution brings with it some special problems in the real-time context.
With regard to predictability many advantages can be gained by the use of
main memory databases. Also, the bene ts a orded by database machines
[30] for real-time database systems are worth exploring.
Now let us consider approaches that are in some sense unique to real-time
database systems. In the context of activities having timing constraints,
the statement, \it is better to produce a partial result before the deadline
instead of the complete result after the deadline" has become a cliche.
However, it is not always clear what an acceptable partial result is or how
a computation can be structured to provide acceptable partial results.
Recent work in the real-time area can lead us to some partial answers [35].
In general, timeliness, a key performance measure, could be achieved by
trading it o with completeness, accuracy, consistency, and currency [19,
40]. Below we consider each of these in turn.
Let us rst consider completeness. Suppose a transaction updates the screen
Page 17 of 29
 of an oper- ator in a chemical plant periodically. If during a certain time
interval, during overloads, it is unable to update all the valve positions,
but has the time to update those that are crucial to the safety of the plant,
then such a transaction should be allowed to execute even if not all its
actions may be performed.
When query processing involves computing aggregates, especially in a
time-constrained environment, then one can achieve di erent degrees of
accuracy by resorting to approximate query processing by sampling data
[23]. Here, depending on time availability, results with di erent accuracies
can be provided. Another example is that of a transaction that does not
have all the necessary data for its processing but can recover from this
situation by extrapolating based on previous data values. Here again, if
previous data values of di erent data items are used, their relatively
consistency must be considered.
Turning to consistency, in the context of traditional databases, it has often
been men- tioned that correctness notions that relax serializability are
appropriate (see [41] for a review of such relaxed notions.). For instance,
epsilon serializability [38] allows a query to execute in spite of concurrent
updates wherein the deviation of the query's results, from that of a
serializable result, can be bounded. Such relaxations allow more
transactions to execute concurrently thereby improving performance.
In the context of currency of a transaction's results it may not always be
necessary for

a transaction to use the latest version of a data item. This is true, for
example, when a transaction is attempting to derive trends in the changes
to some data. Clearly, old versions of the data are required here and the
transaction can complete even if the latest version is unavailable.
The examples mentioned above make it clear that there are situations
where imprecision can be tolerated, and in fact must be exploited, to
improve performance. However, how to achieve this systematically is yet
to be studied. What we need are notions similar to the degrees of
consistency adopted in traditional database systems [17]. In this context,
Page 18 of 29
scheduling approaches that have been developed for the imprecise
computation model in real-time systems could be tailored to apply to real-
time database systems. Preliminary work in this area is reported in [45].

5.3 Recovery Issues

Recovery is a complex issue even in traditional databases and is more so in

real-time database systems for two reasons. (The approach discussed at
the end of Section 5.1 was motivated in part by these complexities.) Firstly,
the process of recovery can interfere with the pro- cessing of ongoing
transactions. Speci cally, suppose we are recovering from a transaction
aborted due to a deadline miss. If locks are used for concurrency control, it
is important to release them as soon as possible so that waiting
transactions can proceed without de- lay so as to meet their deadlines.
However, it is also necessary to undo the changes done by the transaction
to the data if in-place updates are done. But this consumes processing time
that can a ect the processing of transactions that are not waiting for locks
to be re- leased. Whereas optimistic concurrency control techniques or a
shadow-pages based recovery strategy can be used to minimize this time,
they have several disadvantages [18]. Secondly, unlike traditional
databases where permanent data should always re ect a consistent state,
in real-time databases, the presence of temporal data, while providing
some opportunities for quicker recovery [51], adds to the complexities of
the recovery of transactions. Speci cally, if a transaction's deadline expires
before it completes the derivation of a data item, then rather than
restoring the state of the data to its previous value, it could declare the
data to be invalid thereby disallowing other transactions from using the
value. The next instance of the transaction, in case the data is updated by
a periodic transaction, may produce a valid state.
In general, real-time database recovery must consider time and resource
availability to determine the most opportune time to do recovery without
jeopardizing ongoing transactions, whether they are waiting for locks or
not. Available transaction as well as data semantics
Page 19 of 29
(Or state) must be exploited to minimize recovery overheads. Contingency
or compensating transactions [32] are applicable here: Contingency
transactions can take the form of multiple versions of a transaction each
with different values and different computational and data requirements.
If we know that one with the highest quality will be unable to complete in
time, the system can recover by trying an alternative with acceptable
quality. This is a situation where quality is traded o to minimize recovery
costs and to achieve timeliness. Revisiting the factory oor example from
the introduction, we saw that if there is insufficient time to complete
object recognition, the system discards the object for now and directs the
object to appear once again in front of the camera (at perhaps a later
point in time). In case a real-time transaction has interacted with the
environment, a compensating transaction may have to be invoked to
recover from its failure [32]. The nature and state of the environment can
be used to determine recovery strategies. In some situations, in the
absence of new data that was to have been produced by an aborted
transaction, extrapolation of new values from old values may be possible.
In other cases, more up-to-date data may be available soon.
The following highly simplified example may help in illustrating some of the
considerations in recovery. Suppose two robots on a factory oor have to
rendezvous at point x by time t: t is arm deadline by which either both
should be at x or both should know that they cannot make it. The
controller of the robot, i.e., the real-time system, rst obtains their
current position and those of the pertinent objects on the factory oor. It
determines the type of moves the robots are capable of by retrieving their
characteristics from archival storage. It then creates a path for each robot
to follow to reach x by time t and sends this path to each robot. The
controller also reserves this path for the duration for these two robots. As
the robots follow this path, the controller monitors their movement,
looks out for obstacles in their slated path and continually checks if there is
a delay in reaching speci c points along the path due to incorrect
estimations made during path construction or unanticipated other
Page 20 of 29
delays. If it detects such a situation, the controller recovers from it by
determining an alternative path given the robots' current position. Should
there be no time to follow the new path; recovery involves instructing the
robots to halt, informing each of them that their rendezvous is not
possible. In either case, path reservation information is modifed
appropriately. Note that all of this involves reading information from the
environment, retrieving information from the database, and updating
other information. It also shows some aspects of recovery: Recovery here
comprises two contingency actions, one of which involves termination of
the transaction after informing the robots.

5.4 Managing Overloads:

Perhaps the most critical of the outstanding issues is one of managing

overloads. How should real-time transaction processing be done when
more transactions arrive than can meet their deadlines? In traditional
systems, if an overload does not remain for too long, in most cases, the
result is a slow response for the duration of the overload. However, in real-
time databases that interact with the environment, catastrophic
consequences can arise. These can be minimized by ensuring that
transactions that are critical to the performance of the system are
declared to possess hard deadlines and are guaranteed to meet deadlines
even under overloads. In addition, if we make sure that transaction values
are considered for priority assignment and during con ict resolution, then
the transaction that misses its deadline will typically have a low value.
However, missing too many low-valued transactions with soft deadlines
may eventually lead to situations where many transactions with high
values arrive thus stressing the system: For example, if periodic
maintenance is postponed due to the arrival of more important activities,
it may eventually be necessary to shut down the system. Hence dealing
with overleads is complex and solutions are still in their infancy [6, 8, 31].

Page 21 of 29
 6. Conclusions

In this paper, we presented the characteristics of data and transactions in

real-time database systems and discussed the di erences between real-
time database systems and traditional databases. Many of the di erences
arise because temporal consistency requirements are imposed on the data
in addition to the usual integrity constraints. Maintaining temporal
consistency imposes time constraints on the database transactions. In
addition, the re- action requirements demanded by the environment can
also place time constraints. The performance of real-time database
systems is measured by how well the time constraints as- sociated with
transactions are met. The system must meet all hard deadlines and
minimize the number of transactions whose soft deadlines are missed. This
is a crucial difference from traditional databases and necessitates time-
cognizant transaction processing.
We examined various aspects of transaction processing in real-time
database systems including concurrency control and recovery and showed
that recovery becomes an even more complex problem when transactions
have time constraints. In many situations, one can

Trade o timeliness for quality of the transaction's results where the quality
depends on the completeness, accuracy, currency, and consistency of the
results. Furthermore, many recent advances in databases, for exploiting
parallelism, distribution, object semantics, and transaction semantics
should be very useful in real-time database systems also.
Whereas recently there has been a spurt of research activity in the area,
many open questions remain. These include the derivation of transaction
timing properties from the temporal consistency requirements of the data,
developing suitable hardware and software architectures for real-time
database systems, seamless management of transactions with hard and
soft deadlines, real-time transaction processing in distributed databases,
transaction recovery, and the tradeo s between timeliness and quality.

Page 22 of 29
 References
[1] R. Abbott and H. Garcia-Molina, \Scheduling Real-Time Transactions: A
Performance Evaluation," Proceedings of the 14th VLDB Conference, Aug.
1988.

[2] R. Abbott and H. Garcia-Molina, \Scheduling Real-Time Transactions

with Disk Resi- dent Data," Proceedings of the 15th VLDB Conference,
1989.

[3] R. Abbott and H. Garcia-Molina, \Scheduling I/O Requests with

Deadlines: A Perfor- mance Evaluation," Proceedings of the Real-Time
Systems Symposium, Dec. 1990.

[4] N. Audsley, A. Burns, M. Richardson, and A. Wellings, \A Database

Model for Hard Real-Time Systems", Technical Report, Real-Time Systems
Group, Univ. of York, U.K., July 1991.

[5] B. R. Badrinath and K. Ramamritham. \Semantics-Based Concurrency

Control: Be- yond Commutativity," ACM Transactions on Database
Systems, March 1992.

[6] S. Baruah, G. Koren, D. Mao, B. Mishra, A. Raghunathan, L. Rosier, D.

Shasha, F. Wang, \On the Competitiveness of On-Line Real-Time
Scheduling", Proceedings of the Real-Time Systems Symposium,
December 1991.

[7] P.A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control

and Recovery in Database Systems. Addison-Wesley, Reading, MA, 1987.

[8] S. Biyabani, J.A. Stankovic, and K. Ramamritham, \The Integration of

Deadline and Criticalness in Hard Real{Time Scheduling," Proceedings of
the Real-Time Systems Symposium, December 1988.
Page 23 of 29
[9] A.P. Buchmann, D.R. McCarthy, M. Chu, and U. Dayal, \Time-Critical
Database Scheduling: A Framework for Integrating Real-Time Scheduling
and Concurrency Con- trol", Proceedings of the Conference on Data
Engineering, 1989.

[10] M.J. Carey, R. Jauhari, and M. Livny, \Priority in DBMS Resource

Scheduling", Pro- ceedings of the 15th VLDB Conference, Aug 1989, pp.
397-410.

[11] S. Chen, J. Stankovic, J. Kurose, and D. Towsley, \Performance

Evaluation of Two New Disk Scheduling Algorithms for Real-Time Systems",
Real-Time Systems, Sept. 1991.

[12] U. Dayal, et. al. \The HiPAC Project: Combining Active Databases and
Timing Con- straints", SIGMOD Record, 17, 1, March 1988, 51-70.

[13] K. R. Dittrich and U. Dayal. Active Database Systems (Tutorial Notes).

In The Sev- enteenth International Conference on Very Large Databases,
September 1991.

[14] K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. The Notion of

Consistency and Predicate Locks in a Database System. Communications of
the ACM, 19(11):624{633, November 1976.

[15] Peter A. Franaszek, John T. Robinson, and Alexander Thomasian,

\Access Invariance and its Use in High Contention Environments",
Proceedings of the Sixth International Conference on Database
Engineering, 1990, pp 47-55.

[16] M.C. Graham. \Issues in Real-Time Data Management", CMU/SEI-91-

TR-17, July 1991.

[17] J. N. Gray, R. A. Lorie, G. R. Putzulo, and I. L. Traiger. Granularity of

Page 24 of 29
locks and degrees of consistency in a shared database. In Proceedings of
the First International Conference on Very Large Databases, pages 25{33,
Framingham, MA, September 1975.

[18] J.N. Gray and A. Reuter, \Transaction Processing: Techniques and

Concepts", Morgan- Kaufman (book in preparation).

[19] N. Gri eth and A. Weinrib, \Scalability of a Real-Time Distributed

Resource Counter", Proceedings of the Real-Time Systems Symposium,
Orlando, Florida (December 1990).

[20] J.R. Haritsa, M.J. Carey and M. Livny, \On Being Optimistic about Real-
Time Con- straints," Proceedings of ACM PODS, 1990.

[21] J.R. Haritsa, M.J. Carey and M. Livny, \Dynamic Real-Time Optimistic
Concurrency Control," Proceedings of the Real-Time Systems Symposium,
Dec. 1990.

[22] J.R. Haritsa, M.J. Carey and M. Livny, \Earliest Deadline Scheduling for
Real-Time Database Systems," Proceedings of the Real-Time Systems
Symposium, Dec. 1991.

[23] W. Hou, G. Ozsoyoglu, B. K. Taneja, \Processing Aggregate Relational

Queries with Hard Time Constraints", Proceedings of the ACM SIGMOD
International Conference on the Management of Data, June 1989.

[24] J. Huang and J. Stankovic, \Real-Time Bu er Management," COINS TR

90-65, August 1990.

[25] J. Huang, J.A. Stankovic, D. Towsley and K. Ramamritham,

\Experimental Evaluation of Real-Time Transaction Processing,"
Proceedings of the Real-Time Systems Sympo- sium, Dec. 1989

Page 25 of 29
[26] J. Huang, J.A. Stankovic, K. Ramamritham and D. Towsley,
\Experimental Evaluation of Real-Time Optimistic Concurrency Control
Schemes", Proceedings of the Conference on Very Large Data Bases, Sep
1991.

[27] J. Huang, J.A. Stankovic, K. Ramamritham and D. Towsley, \On Using

Priority In- heritance in Real-Time Databases," Proceedings of the Real-
Time Systems Symposium December 1991.

[28] Jensen, E. D., Locke, C. D. and Tokuda, H., \A Time-Driven Scheduling

Model For Real-Time Operating Systems", Proceedings of 1985 IEEE Real-
Time Systems Sympo- sium, pp. 112-122.

[29] W. Kim and J. Srivastava, \Enhancing Real-Time DBMS Performance

with Multi- version Data and Priority-Based Disk Scheduling", Proceedings
of the Real-Time Sys- tems Symposium, Dec 1991, pp. 222-231.

[30] Kitsurgawa, \The next generation of database machines", this issue.

[31] G. Koren and D. Shasha, \D-Over: an optimal on-line scheduling
algorithm for over- loaded real-time systems" Real-Time Systems
Symposium, Dec 1992.

[32] H. F. Korth, E. Levy, and A. Silberschatz. Compensating Transactions: A

New Recovery Paradigm. In Proceedings of the Sixteenth International
Conference on Very Large Databases, pages 95{106, Brisbane, Australia,
August 1990.

[33] H. F. Korth, Soparkar, Silberschatz, A. \Triggered Real-Time databases

with consis- tency constraints", Proceedings of the Conference on Very
Large Data Bases, 1990.

[34] Y. Lin and S.H. Son, \Concurrency Control in Real-Time Databases by

Dynamic Ad- justment of Serialization Order," Proceedings of the Real-
Page 26 of 29
Time Systems Symposium, Dec. 1990.

[35] J. Liu, K. Lin, W. Shih, A. Yu, J. Chung, and W. Zhao, \Algorithms for
Scheduling Imprecise Computation", IEEE Computer, Vol. 24, No. 5, May
1991.

[36] J. E. B. Moss, Nested Transactions: An approach to reliable distributed

computing. PhD thesis, Massachusetts Institute of Technology, Cambridge,
MA, April 1981.

[37] P. O'Neil, K. Ramamritham, and C. Pu, \Towards Predictable

Transaction Executions in Real-Time Database Systems", Technical Report
92-35, University of Massachusetts, August, 1992.

[38] C. Pu and A. Le . Replica Control in Distributed Systems: An

Asynchronous Approach. In Proceedings of the ACM SIGMOD International
Conference on Management of Data, pages 377{386, May 1991.

[39] K. Ramamritham, J. Stankovic, and P. Shiah, \E cient Scheduling

Algorithms for Real{Time Multiprocessor Systems," IEEE Transactions on
Parallel and Distributed Systems, Vol. 1, No. 2, April 1990, pp. 184-194.

[40] K. Ramamritham, S. Son, A. Buchmann, K. Dittrich, and C. Mohan,

\Real-Time Databases" panel statement, Proceedings of the Conference on
Very-Large Databases, September, 1991.

[41] K. Ramamritham and P. Chrysanthis, \In Search of Acceptability

Criteria: Database Consistency Requirements and Transaction Correctness
Properties" in Distributed Ob- ject Management, Ozsu, Dayal, and
Valduriez Ed., Morgan Kaufmann Publishers, 1992.

[42] L. Sha, R. Rajkumar, and J. Lehoczky, \Priority Inheritance Protocols: An

Page 27 of 29
Approach to Real-Time Synchronization", IEEE Transactions on Computers,
39(9), pp. 1175-1185, 1990.

[43] L. Sha, R. Rajkumar and J.P. Lehoczky, \Concurrency Control for

Distributed Real- Time Databases," ACM SIGMOD Record, March 1988.
[44] C. Shen, K. Ramamritham, and J. Stankovic, Resource Reclaiming in
Real-Time, Proc Real-Time System Symposium, December 1990. (to appear
in IEEE Transactions on Parallel and Distributed Systems).

[45] K. P. Smith and J.W.S. Liu, \Monotonically improving approximate

answers to rela- tional algebra queries", Proceedings of Compsac,
September 1989.

[46] R. Snodgrass and I. Ahn, \Temporal Databases", IEEE Computer, Vol

19, No. 9, September 1986, pp. 35-42.

[47] S. .H. Son, Y. Lin, and R. P. Cook, \Concurrency Control in Real-Time

Database Sys- tems", in Foundations of Real-Time Computing: Scheduling
and Resource Management, edited by Andre van Tilborg and Gary Koob,
Kluwer Academic Publishers, pp. 185-202, 1991.

[48] X. Song and J.W.S. Liu, \How Well Can Data Temporal Consistency be
Maintained?" Proceedings of the IEEE Symposium on Computer-Aided
Control Systems Design, (to appear) 1992.

[49] J.A. Stankovic, K. Ramamritham, and D. Towsley, \Scheduling in Real-

Time Trans- action Systems," in Foundations of Real-Time Computing:
Scheduling and Resource Management, edited by Andre van Tilborg and
Gary Koob, Kluwer Academic Publish- ers, pp. 157-184, 1991.

[50] Y. C. Tay and Nathan Goodman and Rajan Suri, \Locking performance
in centralized databases", ACM Transactions on Database Systems, volume
10, number 4, December, 1985, pp. 415{462.
Page 28 of 29
[51] S. V. Vrbsky and K.J. Lin. \Recovering Imprecise Computations with
Real-Time Con- straints", Proceedings of the Seventh Symp. on Reliable
Distributed Systems, October 1988, pp. 185-193.

Page 29 of 29