Time-Constrained Query Processing in CASE-DB.
AbstractCASE-DB is a real-time, single-user, relational prototype DBMS that permits the specification of strict time constraints for relational algebra queries. Given a time constrained nonaggregate relational algebra query and a fragment chain for each relation involved in the query, CASE-DB initially obtains a response to a modified version of the query and then uses an iterative query evaluation technique to successively improve and evaluate the modified version of the query. CASE-DB controls the risk of overspending the time quota at each step using a risk control technique.
Introduction
A real-time database has strict, real-time timing constraints in responding to queries. A time-constrained
query is of the form "evaluate the query Q in at most t time units". In a multi-user, real-time DBMS, the
resources (i.e., CPU and data) are shared, and the issue of meeting the time constraint in evaluating the query
becomes complicated due to CPU scheduling and transaction management (concurrency control). In comparison,
in a single-user DBMS, the satisfaction of a time-constraint does not deal with resource sharing or transaction
management. Nevertheless, the problem of evaluating a time-constrained query in a single-user DBMS is far from
trivial. Also, its solution is useful in a multi-user DBMS for forcing a time-constrained query to have a fixed CPU
utilization time, which is an important parameter in multi-user real-time DBMSs for transaction scheduling.
CASE-DB is a real-time, single user, relational prototype DBMS that uses relational algebra (RA) as its
query language. In earlier papers [10, 11, 12], we presented query approximation techniques for aggregate
relational algebra queries, where the result of the query was estimated by using statistical estimators and sampling
techniques. In this paper, we present a query modification technique for processing non-aggregate, real-time
relational algebra queries.
In a single-user DBMS, the issue of time-constraint satisfaction is equivalent to controlling the evaluation time
of a query precisely. There are two points to observe:
1. The query evaluation time for an RA query is unknown prior to the evaluation and can only be estimated
with a certain probabilistic confidence. For example, consider the following query. Select a set of tuples
This research is supported by the National Science Foundation under Grants IRI-8811057, IRI-9009897, and IRI-9008632. A
preliminary version of this paper has appeared in the Proceedings of the 1992 IEEE DE Conference.
y Department of Computer Engineering and Science, Case Western Reserve University, Cleveland, OH 44106.
z Department of Computer Science, Southern Illinois University at Carbondale, IL 62901.
from a relation that satisfies a boolean formula F. In this query the number of tuples satisfying F may
vary significantly with different relations, and whether the selection can be completed within a given time
quota cannot be known a priori. In general, the evaluation time of a query changes not only with different
relations, but also with the selectivities 1 of the RA operators of the query.
2. A given time constraint T for a query may be so small or the query evaluation is so time consuming that
the probability of not being able to evaluate the query within T time units (referred to as the risk of
overspending in the rest of the paper) may be extremely high. For example, the probability that the join
of two disk-resident relations, each with 1,000 blocks, can be performed in 10 seconds is likely to be almost
zero, and, thus the risk of overspending the time quota of 10 seconds for such a join is almost one.
One can come up with various approaches for approximating or modifying a time-constrained RA query. The
approach used in CASE-DB is as follows:
1. The relations in the database are fragmented into semantically meaningful subsets (fragments).
2. For each query, in addition to the time quota, the user specifies the maximum risk of overspending to be
taken by the DBMS in evaluating (either) the query (or one of its modified versions). The concept of the
risk of overspending for a given query is introduced in [13].
3. To evaluate a time-constrained query, the DBMS modifies the original query by replacing the relations
with their fragments (Query Modification Technique). The fragments are selected such that the risk of
overspending the time quota while evaluating the modified query is closest to and less than the risk specified
by the user (Fragment Selection Problem).
4. If there is any time left after evaluating the modified query, step (3) is performed iteratively with higher
risks of overspending. This processes is carried out until the time quota is completely used (Iterative
Query Evaluation).
With the exception of [15 , 16], all other real-time database literature deals with the multi-user environment
and transaction management such as maximizing the number of transactions that complete within their deadlines.
Smith and Liu [15], and Vrbsky and Liu [16] give a methodology for finding approximate answers to relational
algebra queries. In their approach, as the amount of time used increases, the accuracy of the approximate result
is improved. Their approach does not contain a risk control mechanism, and the way in which they obtain and
improve the approximate result is different than ours.
The rest of the paper is organized as follows: In section 2, the query modification technique is described with
an algorithm and an example. In sections 3.1 and 3.2, we discuss two different formulations of the fragment
selection problem, and show that both problems are NP-complete. A heuristic solution is presented in section
3.3 for the fragment selection problem, which has been implemented in CASE-DB. In section 4 we present the
1 Selectivity of an RA operation (or an expression) E, denoted by sel E , is the ratio of the number of output tuples of E to the
product of the number of tuples in the operand relations in E.
transformations used in the query modification technique. In section 5 we report the experimental results and
the performance analysis. Section 6 concludes.
Query Modification Technique
In this technique, a time-constrained query is modified by replacing the relations with their fragments. The
user or the database administrator identifies relations that would probably be used in time-constrained query
processing, and divides each relation into three types of strata: required, strongly preferred and preferred
strata. Figure 2.1 shows the relation fragmentation chain for the relation FURNACES: the user prefers
that the query be evaluated with furnaces, strongly prefers that the query be evaluated with one of the two
fragments, critical-status-furnaces or high-priority-and-critical-status-furnaces, and absolutely requires that the
query is evaluated with the fragment high-priority-and-critical-status-and-dangerous-environment-furnaces. The
fragments in the required, preferred and strongly preferred strata are called as required, strongly preferred and
preferred fragments.
Example 2.1. In CASE-DB, each RA query has the keyword parameter "T=" which specifies the time constraint
(or time quota), and the keyword parameter "R=" which specifies the risk of overspending. Now, consider the
database relation FURNACES (fnumber, fname, priority, status, environment) that contains information about
furnaces, and the relation TEMPERATURES (fnumber, temperature, time, date) that maintains the recorded
temperatures of furnaces. Assume that the user has specified the relation fragmentation chains shown in figures
2.1.a and 2.1.b. Consider the query "List the furnace names and their temperatures in 10 seconds with the
risk at 0.5 or less" which is specified in RA as
first revises the query Q into Q 1 where FURNACES is replaced by HIGH-PRIORITY-AND-CRITICAL-
STATUS-AND-DANGEROUS-ENVIRONMENT-FURNACES and TEMPERAT-URES is replaced by LAST-
3DAY-TEMPERATURES, i.e., the required fragments. Q 1 is then evaluated.
Assume that the evaluation of Q 1 took 2 seconds. CASE-DB then finds the risks of evaluating the query with
different combinations of fragments from the two chains for the time of 8 seconds. Assume that, among these risks,
the risk that comes closest to and is less than 0.5 is 0.48, and it is for the query "List the last day temperatures
of high-priority-and-critical-status-furnaces" which is
Then CASE-DB evaluates Q 2 . Assume that the evaluation of Q seconds. Then, for the remaining 2
seconds, CASE-DB chooses larger fragments from the two chains using a very high risk of overspending (e.g., 0.95)
and repeats the query evaluation. The reason for choosing high risks in later iterations is to reduce the number of
additional iterations, and thus to control the overhead of iterations. On the average, the number of iterations are
always upper bounded by 4. CASE-DB keeps evaluating modified versions of Q, each time with bigger fragments,
until the time quota T runs out. Then, CASE-DB returns the very last completed response to the user together
with the modified query of that response. Figure 2.2 presents an outline of the non-aggregate, real-time query
evaluation algorithm used in CASE-DB. Please note that the major random variables that introduce an error
in query evaluation time (and thus cause multiple query evaluation steps) are the selectivities of RA operators
in the query. At the end of each query evaluation step, we have better information about operator selectivities,
which is used to revise the selectivity estimations.
Please note that, in the algorithm in figure 2.2, there is a transformation of the modified query Q s into Q 0
s
such that Q 0
s uses "the previous step's response''. The first revision of the query Q obtained by replacing each
relation with its required fragment and the evaluation of the revised query constitutes the first query evaluation
step. CASE-DB then spends the remaining time by iteratively improving the query with additional steps.
Clearly, from step 2 onwards, the DBMS may save time if, instead of evaluating the current step's query with base
relations, it can revise the current step's query such that (a) previous step's output can be used in the current
step's output, and (b) it can ``add'' new tuples to the output due to the ``larger'' fragments utilized in the current
step. The point (b) is, of course, true in general for only monotone 2 queries.
Figure

2.1. Relation Fragmentation Chains
The motivations for our approach are listed below.
1. There is a compromise between the sizes of operand relations of the query and the risk of overspending.
Under the expected case (with the possible exception of the set difference operator of the RA), as the
relations are replaced by their subsets (i.e., fragments), the query evaluation time and hence the risk of
overspending get smaller.
A query is monotone when adding tuples to its input relations does not make it lose any of its output tuples; otherwise, it is
nonmonotone. RA queries with unions, intersections, projections, and joins are monotone. However, the inclusion of the set difference
operator makes an RA query nonmonotone.
2. By specifying the fragments of relations and how much risk (s)he is willing to take for overspending in a
query, the user guides the DBMS in choosing the modified query.
3. The modified query is semantically meaningful, and represents the "best" query that the DBMS can answer
for the given risk and the given time constraint.
Algorithm Time-Constrained-Ad-Hoc-and-Non-Aggregate-Query-Evaluation(Q, T, fi)
input: Q: an arbitrary relational algebra query.
T: a given amount of clock time quota.
fi: (upper bound for) the risk of overspending to be used in step 2.
Output: a revised query Qs and its response produced within T clock time units.
begin
Set the timer interrupt to T units
While TRUE do begin
if Step=1 then
begin
ReplaceRequiredFragments(Q;Qs ); ffor each r in Q, select the
required fragment f and replace r with f in Q to obtain Qsg
Execute(Qs ); fStandard relational algebra query executiong
else begin
if Step=2 then fi 0
else
,Step) fdecides the risk to be taken in
step 3 and above g
previous ,fi 0
,TimeLeft,Qs ); fsolves the fragment selection
problem with the risk fi 0
to obtain
the revised query Qsg
if (Q previous = Qs) then goto END; fif a relation could not be obtained
such that the constraints are satisfied or if the given query(Q) has been evaluated.g Transform(Qs ,Q 0
fTransform Qs into Q 0
s
such that Q 0
s uses the previous step responseg
endif
CurrentTime - StartTime;
previous := Qs ;
endwhile
3 When the timer interrupt occurs, interrupt service routine returns the control to the statement after the while loop. Therefore,
the while loop in the next line is an infinite loop.
END:Return(Qs,ResponseToQs

Figure

2.2. Query Evaluation Algorithm for Real-Time, Non-Aggregate Queries in CASE-DB
3 Fragment Selection Problem, Its Complexity and Heuristics
In this section, we formally define the fragment selection problem using two different risk factor formulations,
and prove that both formulations lead to NP-complete problems. We then briefly describe the heuristic approach
used in CASE-DB.
For each r, let S r denote the fragments in the relation fragmentation lattice of r, i.e., S rg.
Consider Q with input relations r i . For a query evaluation step of Q, let us say we choose the fragment f i from
(S r i of) each relation r i . We call the resulting list of fragments F=ff 1 the fragment list
of Q.
Below we describe two different risk factor formulations.
3.1 Risk Factor ff
In [11] we gave a risk factor ff approach for sampling and evaluating an estimate for aggregate queries. We
now revise that approach for fragment selection in non-aggregate queries.
Assume that we are at the i th query evaluation step. Let F ng be a fragment list of Q selected
at step i. We first characterize the probability of exceeding the time quota when Q is evaluated with fragments
of F i , that is, the risk ff i of overspending for F i . Let T i be the amount of time left after
the random variable representing the actual amount of time that will be spent at the i th step with mean - t i and
variance simply, sel i ) denote the selectivity of the operator Op at the i th step. SEL(E)
(or, simply, SEL) denotes the set of sel i (Op) for each operator Op in E (i.e., sel i 2 SEL). Let COSTQ
be the time-cost formula of the query at the i th step. Clearly, the equality
is satisfied. Since SEL and, hence, t i are unknown until the step i ends, we use the expected version of the above
equation, i.e.,
where \Xi denotes the expected value function. Now, assuming that, for a given fragment list F
have (a) approximations for SEL, and (b) the time cost formula COSTQ of the query Q is derived, we solve for
using equation (3.2).
The risk of overspending at step i, denoted by ff i , is defined to be P denotes the probability.
For the risk ff i , a number d ff i
can be obtained such that the actual amount of time spent at step i will be less
than or equal to - t i
Therefore,
if we use the equality
then t i will be less than or equal to T i with probability known and - t i is obtained
from equation (3.2), we can use equation (3.3) to solve for d ff i , and hence for ff i . Thus, the risk ff i of overspending
when Q is evaluated using the fragments in the fragment list F i can be computed. We now state the fragment
selection problem and discuss its complexity.
Fragment Selection Problem (FSP ff ff be the given risk of overspending at step i. Let X denote the
set f F j jF j is a fragment list, 0 - ff - ff j - ", " is a pre-chosen small constant g. Choose from all fragment lists
in X the list F i with the risk ff i such that ff \Gamma ff i is minimum.
2FSP a is a particular case of FSP a where each relation r j has only two fragments in S r j
Theorem 1: 2FSP ff is NP-complete.
Proof: See the Appendix.
Thus, the complexity of finding F i with ff i among all possible fragment lists is high. However, for monotone
queries several fragment lists can be eliminated from consideration. For example, consider two fragment lists F 1
and F 2 with risks ff 1 and ff 2 , respectively. Assume that each fragment of F 1 contains the corresponding fragment
of F 2 . Clearly, when Q is monotone, ff 2 - ff 1 . If ff 2 is evaluated and it is found that ff - ff 2 then we do not
need to compute ff 1 and can eliminate F 1 from consideration. Nevertheless, the fragment selection problem still
remains to be NP-Complete.
Theorem 2: FSP -M ff is NP-Complete where FSP -M ff denotes the fragment selection problem with monotone
queries.
Proof: See the Appendix.
In addition, as discussed in section 5, we use "stratified relation fragmentation lattices" that are defined and
maintained a priori so that the number of "eligible" fragment lists to consider is significantly reduced and tightly
controlled. Essentially, when there are too many fragments in the fragment set of a relation r, we stratify the
fragments, and, for the fragment selection problem, consider only fragments in a single stratum.
There are various ways to approximate each sel i (Op) in SEL [14, 2, 3]. In our earlier work [11, 10], we have
approximated sel i (Op) by sampling and evaluating COUNT estimators. The overhead of approximating sel i (Op)
can be reduced to zero disk accesses if a sample of each fragment f i is also pre-retrieved and stored along with
Please note that the selectivity of an operator Op 1 (in Q) that uses as an operand the output of another
operator Op 2 in Q is dependent on the selectivity of Op 2 . That is, selectivities are not independent, and for
precise selectivity estimations, covariances between selectivities need to be estimated. Unfortunately, covariance
formulas are usually quite complicated [9]. Moreover, the complexity changes with the sampling method used.
In equation (3.3), we assumed that we have an approximation for function of the
fragments used and the variances among selectivities in SEL, which can be replaced by the sample selectivity
variances obtained during sel i (Op) approximations.
3.2 Risk Factor fi Op
We now discuss another risk factor computation approach, also adapted and revised from [11], for the
fragment selection problem.
In the previous section, we control the risk ff of overspending for the whole query Q. The approach we
pursue in CASE-DB is to define the risk fi Op of overspending in each operator Op in Q. Such an approach is
computationally simpler than the ff-Risk approach and has the advantage that we can use separate risk factors
for different operators. For example, if a join operator in Q has large operand relations and a high variance of
selectivity then we may want to take a small risk of overspending for that operator. On the other hand, we take
a large risk of overspending for a selection operator with a small operand relation regardless of the variance in its
selectivity.
Our approach is as follows. Assume that, at step i for a given fragment list F i , we know the selectivities sel i (Op)
and Var(sel i (Op)) for each operator Op in Q. Instead of using sel i in our query time cost formula COSTQ , we
use sel
i such that sel
In other words, the
probability that the actual selectivity sel i for Op (with the fragment list F i ) is greater than sel
(thereby resulting
in an overspending in Op execution-the risk) is fi Op . Such a selectivity sel
i can be derived by using the equation
sel
is the mean of sel i , V ar(sel i ) is the variance of sel i , and d fi Op
is a proper value chosen by the system
(based on the distribution of sel i ) for controlling the risk fi Op .
We approximate V ar(sel i ) in equation (3.4) using the variance of the corresponding sample selectivity. For
simple random sampling and cluster sampling, [9] gives the formulas for the variance of the sample selectivity.
Let us now state the fragment selection approach that uses the fi approach.
Fragment Selection Problem FSP denote the set of sel
's. Let X denote the set
is a pre-chosen small constant g. Choose from all
fragment lists in X the list F fi i
such that T \Gamma COSTQ among all fragment lists in X.
2FSP fi is a particular case of FSP fi where each relation has only two fragments in its fragment list.
Theorem
Proof: Similar to the proofs of Theorems 1 and 2, and is omitted.
Thus, the problem of finding F i with the fi Op risk is also NP-Complete, similar to the complexity of finding
F i with the ff risk-except that the expected value of the function COSTQ in the ff risk approach is much more
complex. And, as in the ff risk approach, similar complexity reduction techniques can be used to control the time
spent in the fragmentation selection problem.
3.3 Heuristic Approach with fi Risk Factor
In CASE-DB we have implemented the fi-risk factor and a heuristic approach to locate an F fi i
such that T
constant. In this approach, we consider the following properties for
our heuristics:
(i) Selectivity,
(ii) types of operators involved,
time costs of subqueries where r is involved
(iv) file organization type, and
(v) positions of input relations in the parse tree of the query
We use "selectivity" because if the selectivity of an operator is high, a slight increase in the fragment size of the
relation involved with the operator would drastically increase the output, thereby increasing the time cost, and
might overspend the allocated time. So, we would like to increase the fragment size of an input relation whose
associated operator has a high selectivity, when we are ready to take a large risk. We use "the types of operators"
to determine the monotonicity property of the subquery involved. For some relations and some operators, if the
fragment size is increased (decreased) then we may observe a priori an increase (decrease) in the output size,
and hence in the time cost. For some relations, the reverse is true : an increase (decrease) in the fragment size
decreases (increases) the output size. We would like to increase the fragment size of those relations which increase
the time cost (maximize) when the available time is larger.

Figure

3.1. The parse tree of (r
The time-cost of the subqueries involving only base relations is expected to have smaller variance. Hence, the
time-cost of a query involving few operators would have smaller variance.
The type of an operator in a subquery plays a part in the time-cost of the subquery. The file organization of
the relation involved in the subquery also plays a role in determining the time-cost of the subquery. For example,
in the case of the 'selection' operator if there is an indexed file whose index is over the same attribute used in the
selection formula, then the time-cost is much less than that of evaluating the selection operator on a non-indexed
file.
To justify the use of the position of the relation in the parse tree of the query, we use the following example:
Assume we have the following query Q=(r whose parse tree is shown in figure 3.1. If we increase the
size of r 1 or r 2 the variance of the output size will also increase since the output size of the query as a random
variable will be dependent on the output size of r
The heuristic procedure proceeds as follows: At any given iteration, the system fits into one of the following
scenario. We choose a relation depending on the scenario, increase the fragment size of that relation, compute
the risk taken. If the risk is "acceptable" the query is evaluated with the chosen fragment.
time is insufficient 4 , and the risk taken is small 5 .
We do not increase the fragment size of a relation if it is
ffl associated with an operator with high selectivity 6 , or
ffl lower in the parse tree, i.e., away from the root 7 , or
ffl involved with an expensive operator, i.e., the time-cost is of higher order (e.g., O(n 2 )).
4 The available time is less than the time taken to evaluate the query with the required fragment.
5 If the risk is less than 0.1.
7 The relation is at a level 3 or greater.
We increase the fragment sizes of a relation if it is
ffl associated with an operator whose selectivity is low, or
ffl closer to the root of the parse tree, or
ffl involved with inexpensive operators.
time is insufficient, and the risk taken is high.
Similar to scenario 1, we do not increase the fragment size of a relation if it is involved with an expensive
operator or lower in the parse tree because the available time is less. Instead, we increase the fragment size of a
relation if it is associated with an operator whose selectivity is high because we are ready to take a larger risk.
Scenario 3 Available time is sufficient, and the risk taken is small.
In contrast with scenario 2 we increase the fragment sizes of a relation if it is lower in the parse tree or involved
with expensive operators or involved with operators whose selectivity is low.
time is sufficient, and the risk taken is high.
Algorithm SelectFragments(Q, fi, AvailableTime, Qm )
Modified query from the previous iteration.
fi: the risk to be taken in the next step.
AvailableTime: Time available for the next iteration.
modified Query to be used in the present iteration.
begin
HeuristicChoose(Q, r, fi, AvailableTime); fchoose a relation r using the heuristic.g
while (EstimatedTime ! AvailableTime) and (r !? EMPTY) do begin
EstimatedTime := 0;
fchooses a fragment f j (r) for the relation r where
is the fragment used in the previous iterationg
previous :=Qm ;
ReplaceFragment(Q previous , f j (r), f i (r), Qm ); replaces the fragment f i (r) with f j (r) in the query Qmg
for each subquery (SUBQ =(r 1 Op r 2 )) or (SUBQ= (Op r 1 )) in Qm
such that sizes of r 1 and r 2 are known (available or estimated)
do begin
sel
switch Op
case Op=oe fOp is a selection operationg
EstimatedTime
fr 0 is the output relation and r 1 is the input relationg
case Op=- fOp is a projection operationg
EstimatedTime
case is a union operationg
EstimatedTime
fr 0 is the output relation and r 1 and r 2 are the input relationsg
case is an intersection operationg
EstimatedTime
case Op =1 fOp is a natural join operationg
EstimatedTime
case difference operationg
EstimatedTime
endfor
fif the selected fragment
is the entire relation then choose another relation with the help of the heuristicsg
then HeuristicChoose(Q previous , r, fi, AvailableTime);
endwhile
(EstimatedTime ? AvailableTime) then Qm:=Q previous ;
fif the estimated time is not within the
available time discard the new fragment
and use the previously found fragment that
could be evaluated within the available timeg

Figure

3.2. Algorithm for selecting a fragment.
In this scenario we increase the fragment size of a relation if it is lower in the parse tree, or involved with
operators having high selectivities or involved with expensive operators.
3.4 Algorithms for selecting a fragment
The algorithm SelectFragments given in figure 3.2 outlines the method used for selecting a fragment for the
fragment selection problem using the heuristic approach suggested in section 3.3. In this algorithm, the procedures
SelectCost, ProjectCost, UnionCost, IntersectionCost and JoinCost return the time estimation for the
corresponding operators, which are specified in section 4.3. Algorithm HeuristicChoose shown in figure 3.3
specifies the process of choosing a relation based on the four scenarios.
Algorithm HeuristicChoose(Q,r,fi,TimeLeft)
arbitrary query.
Risk to be taken in the present iteration.
available for the current iteration.
involved in Q.
taken to evaluate the query with the required fragment.
begin
switch cond begin
case BaseTime and fi ! .1)
case Basetime and fi - .1)
case BaseTime and fi - :1)
case BaseTime and fi ! :1)
endcase

Figure

3.3. Algorithm for choosing a relation based on the heuristics.
Algorithm LessTimeLowRisk chooses a relation based on the scenario 1 : Available time is insufficient and the
risk of overspending is small. In this algorithm we have used three functions namely Level(r) which returns the
level of the relation in the parse tree; OperatorValue(r) returns a value associated with the operator which operates
on r directly (value depends on the time complexity of the operator) and Selectivity(r) returns the selectivity
of r.
Algorithm LessTimeLowRisk(Q,SelectedRelation)
arbitrary query.
relation involved in Q.
begin
For every relation r in Q begin
if(SelectedRelation=EMPTY) then
if the entire relation has not been used for processing in the previous iteration then
else
else
else
endfor

Figure

3.4. Algorithm for choosing a relation to modify under a given scenario.
Similar to LessTimeLowRisk procedure, we have algorithms LessTimeHighRisk, MoreTimeHighRisk and More-
for choosing a relation based on the scenarios 2,3 and 4, respectively.
The algorithm ChooseFragment chooses a fragment from the fragment set of the relation. In CASE-DB, we use
linear search to find the right fragment for a given relation. Following is the algorithm for ChooseFragment as
implemented in CASE-DB.
Algorithm ChooseFragment(f j (r), f i (r), r)
is the fragment that is being currently used.
The relation for which we are choosing the fragment.
new fragment chosen for the relation r, such that f j oe f i .
begin

Figure

3.5. Algorithm for choosing a fragment from a given fragment set.
Algorithm CalculateSelPlus implements the computation of sel
i for an operator O p in CASE-DB.
an arbitrary query.
sel :Estimated selectivity from the previous i-1 iterations.
The risk to be taken in step i.
assumed larger selectivity of the operator Op .
value chosen such that P (sel
total number of points in the point space of Op given as are the number of tuples in the
relations involved in the operation.
the number of points in the point space of Op at the step j.
the number of points which have not been included in the previous i-1 iterations.
begin
sel
sel
return(sel
end.

Figure

3.6. Algorithm for calculating sel
Iterative Query Evaluation Transformations
We illustrate the iterative query evaluation transformations with an example.
Example 4.1. Consider the query Q 2 of Example 2.1.
Assume that the evaluations of Q 1 and Q 2 took 8 seconds, and there still are 2 seconds left in the time quota. In
the third step, using the risk of 0.95, the DBMS chooses to evaluate
We can transform Q 0
3 into an equivalent query Q 3 that uses Q 2 as follows.
[- fname;temperature (CRITICAL-STATUS-FURNACES
We make two observations. First, each of the two union operators in the right hand side of equation (4.1)
is a union of two disjoint sets. Therefore, there is no need for duplicate tuple elimination which leads to a
very fast implementation. Second, in the implementation of relation fragmentation chains for FURNACES and
TEMPERATURES, we actually maintain(physical files for) f 0
\Gammag
at each node. Thus, when evaluating (f
3 and g 0
respectively, that are already
stored in the database and available; this leads to a very fast implementation of Q 3 . 2
Consider a single-operator query with input relation r. CASE-DB evaluates Q using fragments f
from r such that f i ae f
Example 4.2. Consider a relation r with a relation fragmentation chain for r. Assume we have already evaluated
there is still time left in the time quota. Let f 2 be the next fragment chosen. We then evaluate Q(f 2 )
in terms of Q(f 1 ) which in turn, is used in evaluating Q(f i
The evaluation of Q(f i+1 ) in terms of Q(f i ) is done (almost always 8 ) as follows. Through algebraic manipula-
tions, Q(f i+1 ) is converted into Q(f i )[Q 0
;. In other words,
uses f i and f 0
in its evaluation-two relations each strictly smaller than f i+1 .
We call f 0
i+1 the complement fragment of f i+1 .
(ii)The union operation between Q 0 and Q is a union of two disjoint sets.
Let us denote the union of two disjoint sets by ], and call it the disjoint union.
Let r and s be two relations. Then r
Please note that disjoint union can be implemented very fast since, unlike union, it does not require duplicate
tuple elimination, which is normally implemented by sorting in databases-an expensive task. Therefore, whenever
possible, we use disjoint union over union. We illustrate with an example.
Example 4.3. Let Q(r, with r and s having the relation fragmentation chains f
respectively. Assume, at a previous iteration, Q(f evaluated, and, at the current
are chosen to evaluate Q, i.e., Q(f j+1 is to be evaluated. We transform
the relation fragmentation chains of r and s contain g 0
j+1 and
computed and stored in the database already (before the query session starts). 2
8 There are some exceptions which are discussed in [4].
4.1 Transformations for Single-Operator Queries
We now generalize our approach for single-operator queries. Assume Q(f evaluated before, and Q(f k
is to be evaluated. Let f i;k denote f 0
k and g j;m denote g 0
m . We
is an RA operator, and
evaluate the transformed form. We now list for each single-operator query Q such transformations.
Projection:
4.2 Transformations for Multiple-Operator Queries
Consider an RA query with multiple operators and its parse tree, e.g., the RA query
parse tree is shown in figure 3.1. At each query evaluation step, internal nodes of the parse tree are associated
with (output) relation instances obtained by evaluating the operator at that node. Our approach is to store
and use whenever possible the last instances of such relations. For monotone queries, such an approach is quite
efficient.
4.2.1 Monotone Queries
Assume that the RA expression does not have any set difference operators (i.e., a monotone query). Let
be the output relations of an internal node in the parse tree obtained in two consecutive query evaluation
steps. We now summarize the query transformations at each node of the parse tree. Let E and -
E be arbitrary
RA expressions (possibly relations) that are evaluated at the i th step to give e i and -
respectively, and, at the
th step to give e i+1 and -
respectively. From the relation fragmentation chains of the relations involved
in E and -
E, we can compute e 0
Clearly, for E' -
(or '(E) in unary operator case), where ' 2 f[; ";
correspond to Q(f j;m , in section
4.1 respectively. Then we use exactly the same transformations given in section 4.1 for evaluating e i+1 '-e i+1 (or
'(e i+1 )). For example, when
e i is available, the transformation for
4.2.2 Nonmonotone Queries
Whenever a set difference operator appears in the parse tree (i.e., a non-monotone query), we may have
are two consecutive output relations of the set difference operator. This results in complicated
transformations if we are to use in the computation of thus making the iterative evaluation too costly.
Note that, in r-s, the consecutive evaluations of f 1 -g 1 , f 2 -g 1 , f 3 -g 1 , ., etc., do create monotonously increasing
output relations our approach in CASE-DB for any subexpression
E in the query is to evaluate E-
once, and afterwards, to evaluate E-
E with new fragments only in E (but not
in -
E). Such an approach guarantees that consecutive output relations of any set difference operator
. In this case, to compute use the transformation
4.3 Time-costs for the transformations
For a given operator, we choose a transformation by comparing the cost formulas of all the transformations
for that operator. We now briefly present these cost formulas. Please note that the chosen cost formula for an
operator is also used in the algorithm SelectFragments to estimate the iteration time (and hence to choose the
fragments).
We use sequential files sorted on the key to store the fragments of a relation. As a notation, jF j denotes the
number of records of F and jjF jj denotes the number of blocks used in storing F (jjF jj is used in computing the
disk access cost, since the tuples are read/stored in blocks from/to the disk). We have two ways of maintaining
intermediate results obtained during an iterative evaluation step: either in main memory until the evaluation
is over or on the disk. Since we use the iterative evaluation method to process the fragments of a relation,
intermediate results are repeatedly used in each iterative step. Therefore, we keep intermediate results in main
memory. The final results obtained from each iterative step are kept on the disk.
In what follows, we give the time-costs for the transformations. For union and set difference which have more
than one transformation, we only give the time costs of the transformation with (1) the smallest expected number
of disk accesses; (2) the smallest expected number of comparisons. Since the query is evaluated in an iterative
fashion, we only compute the costs of the tranformations in a certain iteration step.
Among the four equivalent transformations for union listed in section 4.1, transformation u.3, Q(f
has the smallest time cost.
are constants.
Among the three equivalent transformations for union listed in section 4.1, transformation d.3, (Q(f
has the smallest time costs.
are constants.
The only transformation for
are constants.
are constants.
Using algorithm Selection(f i;k ; Condition), the costs for transformation s are
are constants.
Projection:
Using algorithm Projection(f i;k ; Attributes), the costs for transformation are
are constants.
5 Experimental Results
5.1 Implementation of CASE-DB
The implementation of the query modification technique has been carried out on ERAM - a relational prototype
DBMS [8]. ERAM is built on top of Unix 4.3BSD operating system on Sun 3/60 workstations and is written
in the C programming language.
CASE-DB consists of five basic modules, namely, file management module which performs the functions
of reading and writing tuples; relation maintenance module which creates, retrieves, updates and destroys
relations; algebra module which executes all algebra operations with the help of the file management module;
command interpreter module which supports a relationally complete query language and relation maintenance
commands; and lattice maintenance module which executes commands to create, update and delete
lattices (i.e., in the simplest case, fragmentation chains). Details of CASE-DB implementation are in [7] .
Information of all relations and their associated fragment chains are stored in two different dictionaries with
the same basic structure. The dictionaries are divided into pages 9 , and, at the end of each page, there is a pointer
to the next available space in the page, a pointer to the next page and the page number information.
In CASE-DB, the complement fragments (discussed in section are stored. There are two reasons for this
choice
ffl The query modification technique uses the complement fragment for transformations (discussed in section
and not the entire fragment.
Less amount of space is required.
5.2 Creation of input relations
For each relation used in the experiment, the first and second attribute (C 1 and C 2 ) are of integer type and
the third attribute (C 3 ) is of character type. The first attribute is an unique random integer, which is the key for
the relation. The second attribute, which is not a key of the relation, is used to determine the selectivity of an
operator. The distribution of the attributes is uniform. Each relation involved in the experiment contains 5000
tuples, where the tuple size is 100 bytes. The number of tuples in the required fragment is always 100, and the
9 A page is 1024 bytes.
number of tuples in other complement fragments vary between 100 to 200. All the relations are indexed unless
specified otherwise.
5.3 Factors Affecting CASE-DB
The factors that affect the performance of CASE-DB are discussed below.
(a) Risk
Probabilistic risk of overspending plays an important role in the selection of a fragment list i.e., solving the
fragment selection problem. In CASE-DB, depending on the risk given by the user, the SEL
giving different time estimates for different risk values. This leads to the selection of a larger fragment when the
risk is higher, and a smaller fragment when the risk is lower.
(b) Complement Fragment Size
The time-cost COSTQ is a function of the size of the input fragments. Since we are using complement
fragments in iterative query evaluation steps, size of the complement fragment affects the fragment selection
process.
(c) Selectivity
The selectivity of an operator O p affects the selection of a fragment for the relations involved with O p . The
selectivity of O p when O p is either a Union, Intersection, Difference, Projection or Selection, is defined as the
ratio of the number of output tuples to the total number of input tuples. If O p is a Natural Join operator, the
selectivity of O p is defined as the ratio of the number of output tuples to the product of the input tuples. The
expected time of evaluation is a function of selectivity and thus a change in the selectivity alters the expected
time.
(d) Time
As the available time increases, more and more input tuples will be used, leading to the evaluation of the
original query.
5.4 Single Operator Queries
In this section, we present the results of single operator queries and see how the factors presented in the
earlier section affect the performance of CASE-DB. CASE-DB normally uses the risk given by the user only in
the second iteration. In the third and succeeding iterations, CASE-DB computes a higher risk value so that the
number of iterations can be reduced. However, in order to see the actual effect of risk given by the user (fi), in
the experiments we have used the risk fi in all the iterations excluding the first iteration.
In each of the following tables, the column "Risk" denotes the risk of overspending given by the user.
The column "selp" denotes sel
(the selectivity used in the time-cost formula during the second iteration). As
explained in previous sections, for a given query, time-quota and the risk of overspending, CASE-DB evaluates
the query by substituting the relations in the query with their corresponding required fragments. If there is any
time left after the first iteration, CASE-DB iterates until the time available is very small or overspending of time
occurs. The column "itr" denotes the total number of iterations that the query has gone through, including the
iteration where the available time is overspent. Column "ptu" is the percentage of tuples used in the last iteration
where overspending did not occur. "pts" denotes the percentage of tuples selected to be used in the last iteration.
Note that "pts" includes those tuples that are used in the iteration where overspending might have occurred.
"ptu" and "pts" columns will have the same value when overspending did not occur, i.e., CASE-DB terminated
the process when it could not select a fragment that could be used for the next iteration such that the evaluation
of that iteration could be completed within the available time with the given risk. Finally "ovsp" represents the
amount of time overspent (in seconds).
5.4.1 Selection Operation
No. of tuples in complement fragment
Risk 100 150 200
selp itr ptu pts ovsp selp itr ptu pts ovsp selp itr ptu pts ovsp
.3
sel 1 =.54 time=10sec

Table

Effect of Risk on a Single Selection Operation.
A selection query of the following form:
select from rel where c2 ? 500 risk=.5 time=10sec
is used in the experiments. 'rel' is the relation name and c2 is the second attribute of the relation. By varying
the selection formula (e.g., c2 ! 500) we have obtained different selectivities for the selection operator. The
distribution of c2 in the relation and the fragment chain is uniform. Using a uniform distribution has given us a
consistent value for the selectivity to be used in the calculation of SEL
In the query modification technique, the following equations are used to compute SEL
From the above equations, it can be seen that with an increase in the risk of overspending (fi), d fi value decreases,
thereby reducing SEL
. Since the time-cost is a function of SEL
i , the time-cost decreases as the risk increases.
This leads to the selection of larger fragments with an increase in risk. From Table 5.1 it can be seen that the
number of tuples selected for processing increases linearly with risk, except when the risk is almost 1 (.999).
When the risk (fi) is almost 1, SEL
i tends to zero (shown in "selp" column), which leads to the selection of a
large number of tuples
No.
of
input
tuples
used
Time

Figure

Effect of Time on a Single Selection Operation1500250035000
No.
of
input
tuples
used
in
2nd
iteration
risk=.5 time=10sec 100 tuples/frag-comp

Figure

Effect of Selectivity on a Single Selection Operation
For the selection operator, with the increase in the complement fragment size, the number of tuples selected
increases linearly. For the risk of 0.7 the percentage of tuples selected are 19, 20.5 and 23 for complement fragment
sizes 100, 150, and 200, respectively (Table 5.1). This increase can be attributed to the cost of the disjoint unions.
For example, to use 1000 tuples (these tuples have not been used in the first iteration) in the second iteration, we
10 The expected time which is used in the selection of fragments is a function of SEL
need unions for a lattice with a complement fragment size of 100, and 5 disjoint unions for a lattice
with a complement fragment size of 200. Though the disjoint union is not an expensive operator, it does increase
the total time required for processing the iteration.
As the available time increases, the number of input tuples selected for processing also increases linearly

Figure

5.1). Since we are comparing the expected time with the available time, if the expected time is less
than or equal to the available time, we use the fragment selected. So, when the available time increases, a larger
fragment can be selected such that the expected time would be within the available time.
The selectivity from the (i-1) th iteration is used to compute SEL
which in turn is used to compute the
expected time (time cost) of the i th query evaluation step. Hence, the selectivity of an iteration should affect the
selection of a fragment in the next iteration. An increase in selectivity in (i-1) th iteration increases SEL
which
in turn increases the expected time of the i th query evaluation step. Therefore with an increase in selectivity, the
size of the fragment used in the following iteration decreases linearly (Figure 5.2).
5.4.2 Natural Join operation
No. of tuples in complement fragment
Risk 100 150 200
selp itr ptu pts ovsp selp itr ptu pts ovsp selp itr ptu pts ovsp
.3
sel 1 =0.008 and time=20sec

Table

Effect of Risk on a Single Natural Join operation
In the experiments conducted for the natural join operator, the second attribute of the relations is used as
the join attribute. The join attribute values of the relations are uniformly distributed. To test the effect
of risk on natural join operator, for complement fragment size of 150 and risks of .001, .3, .5, .7 and .999, the
percentage of tuples selected is 30.5, 33.5, 35, 35 and 36 respectively. From this data, it can be seen that the total
number of tuples selected for processing linearly increases with risk. Unlike the selection operator where there is
a digression from the linear increase when the risk approaches 1, the increase in the number of tuples selected
for processing does not show any deviation from the linear increase. This linear increase can be attributed to
the very small values of the natural join selectivity. So when the risk fi tends to 1, the SEL
very small.
Actual selectivity by itself is a small value, and does not change the expected time drastically. When the
selectivity of the operator is increased while the complement fragment size, available time and risk remains the
same, the number of fragments selected for processing increases. Even for a small increase in the selectivity, a
larger fragment is selected; for example, for a change of .008 in selectivity (from .001 to .009), there is a difference
of 200 tuples.
5.4.3 Projection Operation
For the projection operator, the relation is projected on the second attribute. The distribution of the second
attribute in the relation and the fragments is uniform.2000400060008000
No.
of
input
tuples
used.
time
200tuples/comp-frag risk=.5 sel=.001

Figure

Effect of Time on a Single Natural Join Operation900110013001500
No.
of
input
tuples
used
in
2nd
iteration
Selectivity of the join operator in the first iteration
time=10sec risk=.5 tuples/frag-comp=150

Figure

Effect of Selectivity on a Single Natural Join Operation
No. of tuples in complement fragment
Risk 100 150 200
selp itr ptu pts ovsp selp itr ptu pts ovsp selp itr ptu pts ovsp
.3
sel 1 =0.87 and time=10sec

Table

Effect of Risk on Single Projection
No.
of
input
tuples
used
Time

Figure

Effect of Time on a Single Project Operation5001500250035000
No.
of
input
tuples
used
in
2nd
iteration
Selectivity in the first iteration

Figure

Effect of Selectivity on a Single Project Operation
From

Table

5.3 we can see that for a complement fragment size of 100, a risk of .7 and .999, the percentage
of tuples selected for processing are 32 and 34, respectively. Though the percentage of tuples selected for the risk
of .999 is higher than the percentage of tuples selected for the risk of .7, there is an overspending of the available
time for the risk of .7. It should be noted that the overspending (for the risk of .7) occurs in the third iteration,
and the total number of iterations for the risk of .999 is only 2, i.e., the number of tuples selected in the second
iteration in case the of .999 risk is higher than the number of tuples used in the second iteration when the risk is
.7. From this, it can be deduced that, when the number of iterations are reduced, higher number of tuples can be
processed. As the risk fi increases the number of iterations is reduced. Using the above two results, CASE-DB
has been designed to use a higher risk value for the third and succeeding iterations, irrespective of the risk given
by the user.
In the case of projection operator, with an increase in the available time, the number of tuples selected for
processing linearly increases. When the selectivity of operator changes, unlike the Join operator, the slope of the
curve is very small (figure 5.6).
5.4.4 Intersection Operation
Intersection operation can be considered as a special case of the join operation which returns a relatively
low number of output tuples.
No. of tuples in complement fragment
Risk 100 150 200
selp itr ptu pts ovsp selp itr ptu pts ovsp selp itr ptu pts ovsp
.3
sel 1 =.4 time=20sec

Table

Effect of Risk on Single Intersection Operation.
From

Table

5.4 it can be seen that the effect of risk changes on the number of tuples selected is minimal i.e.,
the variation in the number of tuples selected with respect to the increase in risk value is just 2% (from 12% to
14%) for the complement fragment size of 100. As stated in the beginning of this section, the first attribute of
all the relations used in experiments is the key for the relation, and all the relations are indexed unless specified
otherwise. When the relations are indexed, disjoint union of the indexed relations resulting in an indexed relation
is as expensive as a union operation. The time cost formula is made up of the time for reading and writing tuples,
disjoint union and processing the data. Since the cost of disjoint union is equal to the cost of union, the effect of
risk (used in writing and processing cost of tuples) is reduced.

Figure

5.7 shows the effect of time on the number of tuples selected for the intersection operator. With an
increase in time, the number of tuples selected for processing increases linearly.
No.
of
input
tuples
selected.
time

Figure

Effect of Time on a Single Intersection Operation
5.4.5 Union Operation
No. of tuples in complement fragment
Risk 100 150 200
selp itr ptu pts ovsp selp itr ptu pts ovsp selp itr ptu pts ovsp
.3
sel 1 =.6 time=20sec

Table

Effect of Risk on Single Union Operation.
Effects of risk and time variations are tested for the union operation. Like the intersection operator, the cost
of disjoint union is very high. Table 5.5 shows the effect of risk for different complement fragment sizes. For a
complement fragment size of 200 and risks of .3 and .999 the number of tuples selected for processing are 14%
and 16%, respectively, which is just a 2% increase in the number of tuples.
No.
of
input
tuples
used.
time

Figure

Effect of Time on a Single Union Operation

Figure

5.8 shows the linear increase in the number of tuples selected for processing with increase in available
time.
Difference Operator
No. of tuples in complement fragment
Risk 100 150 200
selp itr ptu pts ovsp selp itr ptu pts ovsp selp itr ptu pts ovsp
sel 1 =.1 time=20sec

Table

Effect of Risk on Single Difference Operation.
Experiments similar to union and intersection operator were conducted with the difference operator. The
transformation of difference operator for the iterative query evaluation is more complicated than the union and
difference operator. One has to note that due to the non-monotonicity of the difference operator, we might have
to delete certain tuples from the output of the previous iteration. Figure 5.9 shows the effect of time on a single
difference operation. As the available time increases, more and more input tuples are choosen for processing.
No.
of
input
tuples
used.
time

Figure

Effect of Time on a Single Difference Operation

Table

5.6 shows the effect of risk as well as the complement fragment size on difference operator. Consider
the percentage of tuples selected for the risk of .7 for complement fragment sizes of 100, 150 and 200, they are
13, 15.5 and 18%, respectively, it can be seen that with an increase in the fragment size the percentage of tuples
selected for the same risk and time increased. With larger complement fragments, the number of disjoint unions
are reduced, thereby reducing the expected time; and higher number of tuples are selected.
5.6 Multi-operator Queries
Queries that contain monotone operators (Union, Intersection, Join, Selection and Projection) are used in
the experiments. The experiments are mainly designed to test the effect of risk variations in multi-operator
queries.
The relations used in these experiments contained 5000 tuples, and 200 tuples per complement fragment
with a base fragment containing 100 tuples.
From

Table

5.7 and Table 5.8 it can be seen that, with an increase in the risk value, the number of input
tuples selected for the evaluation increases. Also note that overspending the available time quota does not happen
but when such an overspending occurs, the total time overspent is usually large. This is due to the
complex nature of the time-cost formula, especially when the number of operators in a query increases. Since the
number of tuples in the intermediate results depends on the selectivity of the operators, a small discrepancy in
the estimated value can either overestimate or underestimate the time-cost, resulting in either overspending or
risk
itr ptu pts ovsp itr ptu pts ovsp
.3
200 tuples/comp-frag, time=30sec

Table

Performance of CASE-DB in case of multi-operator queries
risk
itr ptu pts ovsp itr ptu pts ovsp itr ptu pts ovsp
.3
200 tuples/comp-frag, time=100sec

Table

Performance of CASE-DB in case of multi-operator queries
underspending the time quota.
The incorporation of difference (nonmonotone) operator in a query leads to a complicated transformation
during the iterative query evaluation. In the current version of CASE-DB the monotonicity property is preserved
in the transformation by not including new tuples for the minuend of the difference operator in the second and
succeeding iterations. The solution to efficiently processing a nonmonotone multi-operator query will be the
subject of another report.
6 Conclusion and Future Work
In this paper, we discuss non-aggregate query processing techniques in CASE-DB, a real-time DBMS, and
present the results of the experiments conducted on CASE-DB. We analyze the complexity of risk control methods,
and propose, implement and evaluate a heuristic solution for controlling the risk of overspending. For the difference
operator in a multi-operator query, we preserve the monotonicity property, thereby making the transformations
and evaluations simpler. This is achieved by not including new tuples for the minuend of the difference operator
after the first iteration.
Using the risk factor, the user indirectly specifies how aggressive (s)he wants to be in getting the query
evaluated with as "large" input relations (fragments) as possible and within the time quota. If the given risk is
high, the DBMS becomes bold and chooses "larger" input relations. If, on the other hand, the risk very low then
the DBMS chooses small input relations to make sure that the query is not overspent. Another way of looking at
risk factors is as "query hints". The DBMS is given a hint about the level of aggressiveness in choosing fragments.
Please note that we use the risk control approach only in the second query evaluation step after making sure
that a (possibly, lower-quality) query response is obtained in the first query evaluation step. Also note that, in
the third step, we use a very high risk; so the fourth step is rarely executed (thereby controlling the overhead
introduced due to iterative query evaluation).
The risk factor approach is essentially a query modification technique that, through a priori and run-time
protocols between the user and the DBMS, evaluates the query or its modified versions within a qiven time quota.
Our risk-based approach introduces a new paradigm for real-time system (DBMS) users in that, in addition to
time constraints, they are asked to specify a risk factor that guides the DBMS in deciding how aggressive it should
be in evaluating the query in the second step.
Note that in our approach, the choice of relation fragments are completely semantics-based, and, hence,
they will change on the basis of each application. We do not therefore provide any guidance in the paper for the
selection of fragments. However, as discussed in the experimental part, the sizes of complement fragments do
influence the performance; this is empirically evaluated in the paper.
In our study of time-constrained queries, we make the following choices: (a) Timing constraints are always
satisfied. (b) Each query is evaluated in at most 4 query evaluation iterations (steps). This minimizes the overhead
due to iterations. (c) We use the risk factor approach only in the second step, and attempt to use a risk as close
as possible, from the lower end, to the user-specified risk. Under the choices (a)-(c), the experimental results
section of the paper reports the performance of our approach in terms of a number of parameters such as (i) the
total number of iterations, (ii) the number of tuples used, (iii) the percentage of tuples used in the last iteration
where overspending did not occur, (iv) the amount of time overspent, (v) the amount of time wasted, etc. One
can certainly use any of the above-listed parameters as a performance metric, and choose risk factors in order to
have desired values for the above-listed parameters.
In some real-time databases, transactions that complete are given "values". Usually, values assigned to
transaction reduces with time after the transaction passes its time deadline. Viewing a query as a read-only
transaction, a value is assigned to a completed query. And, the sum of the values accumulated for completed
transactions serves as a performance metric. In comparison with our approach, value-based models do not have
any notion of controlled revision/rescaling of queries. Perhaps, the value-based approach can be extended by
adding query modification and a way of assigning varying "values" to modified versions of the query. But, such
an approach would require more guidance from the user as it is not clear how one would judge the "value of
a modified query". Also, the DBMS would need additional guidance, perhaps in terms of values, as to how it
should modify the query. The risk-based approach can also be used for processing real-time transactions.
If each transaction specifies its "optional" and "required" parts (subtransactions) then the DBMS can modify
transactions (by downsizing them), and make sure that all or most of the transactions can complete within their
deadlines. We are currently investigating such an approach.

Appendix


Proof of Theorem 1: 2FSP ff 2 NP since a nondeterministic algorithm needs only to guess a fragment list F i
and check in polynomial time that ff i - ff and ff \Gamma ff i - ".
For a transformation, we first define the 0/1 knapsack problem:
Consider a finite set U and the set Z of positive integers. For each u 2 U we associate a size s(u) 2 Z and
a value v(u) 2 Z. Let B and K be two positive integers. Is there a U 0
' U such that
The 0/1 Knapsack problem is proven to be NP-Complete, and remains to be NP-Complete even when s(u)=v(u)
for all u 2 U [5]. In what follows, we assume
We now give the transformation from the 0/1 Knapsack problem to 2FSP ff .
We construct a set D of relations r j , a fragment list S r j for each r j in D, ff , ff i and " as follows.
1. The set D contains relations r is the number of elements in un g.
2. S r j
g.
3. ff j B=N and "
u2U s(u).
4. ff i j
this transformation takes polynomial time. We now prove that there exists a set U 0
only if there exists a fragment list
Assume that such a fragment list F i exists. Then
construct U 0
as follows. For each f j in F i , if f
. Then
has the property that K -
Assume that there does not exist F i with ff i - ff and ff \Gamma ff . For any possible F i consider the corresponding
constructed as follows. For each f j in F i , if f
1. F i does not satisfy the condition ff i - ff. Then, since ff
we have
2. F i does not satisfy the constraint ff \Gamma ff i - ". Then since
Since there is a one-to-one and onto function and its inverse between the set of all possible F i 's and all possible
subsets U 0
of U, we conclude that there does not exist any U 0
with K -
Proof of Theorem 2: Reduction from 0/1 Knapsack problem to 2FSP ff -M 11 is exactly the same as the
reduction of the 0/1 knapsack problem to 2FSP ff . The transformation is the same with the transformation of
0/1 Knapsack to 2FSP ff . We note that, in monotone queries, we do not check some of the fragment lists. We can
show that those fragment lists which are not being checked correspond to those U 0
which need not be checked
also. Given a fragment list F i , we can construct its corresponding U 0
as follows. For each f j in F i , if f
add
Consider three fragment lists F 1 ' F 2 ' F 3 with risks ff respectively. When Q is monotone,
1. If ff ! ff 2 we do not evaluate ff 3 . When ff ! ff 2 , we have
u2U 0s(u). Since F 2 ' F 3 we have
u2U 0s(u) which means we need not check
3 .
2. If ff 2 - ff and ff \Gamma ff 2 ? ", we need not evaluate ff 1 . When ff 2 - ff and ff \Gamma ff
which means that we need not check U 0
1 .
So we conclude that 2FSP ff -M is NP-Complete. Q.E.D.



--R

"Generalization and a Framework for Query Modification"
"Estimating Record Selectivities"
"On the Estimation and Use of Selectivities in Database Performance Evaluation"
"On Automated Query Modification in Databases"
"Computers and Intractability-A Guide to the Theory of NP-Completeness"
"Set Query Optimization in Distributed Database Systems"
"CASE-DB: A System for Processing Real-Time, Non-Aggregate Relational Algebra Queries"
"The Implementation of the Extended Relational Database Management System"
"Relational Aggreate Query Processing Techniques for Real-Time Databases"
"Statistical Estimators for Relational Alegbra Expressions"
"Processing Aggregate relational Queries with Hard Time Constraints"
"Statistical Estimators for Aggregate Relational Algebra Queries"
"Processing Time-Constrained Aggregate Queries in CASE-DB"
"Statistical Profile Estimation in Database Systems"
"Monotonically Improving Approximate Answers to Relational Algebra Queries"
"An Object-Oriented Query Processor That Produces Monotonically Improving Approximate Answers"
--TR

--CTR
SungKil Lee , Gltekin zsoyolu, Distributed processing of time-constrained queries in CASE-DB, Proceedings of the fifth international conference on Information and knowledge management, p.279-287, November 12-16, 1996, Rockville, Maryland, United States
Kyoung-Don Kang , Sang H. Son , John A. Stankovic, Managing Deadline Miss Ratio and Sensor Data Freshness in Real-Time Databases, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1200-1216, October 2004
Kyoung-Don Kang , Sang H. Son , John A. Stankovic, Differentiated Real-Time Data Services for E-Commerce Applications, Electronic Commerce Research, v.3 n.1-2, p.113-142, January-April
M. Amirijoo , J. Hansson , S. H. Son , S. Gunnarsson, Experimental evaluation of linear time-invariant models for feedback performance control in real-time systems, Real-Time Systems, v.35 n.3, p.209-238, April     2007
Nevzat Hurkan Balkir , Gultekin Ozsoyoglu , Z. Meral Ozsoyoglu, A Graphical Query Language: VISUAL and Its Query Processing, IEEE Transactions on Knowledge and Data Engineering, v.14 n.5, p.955-978, September 2002
Gultekin Ozsoyoglu , Richard Thomas Snodgrass, Temporal and Real-Time Databases: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.7 n.4, p.513-532, August 1995
query modification;relational databases;databases;real-time databases;query processing