Partial Evaluation of Views.
Many database applications and environments, such as mediation over heterogeneous database sources and data warehousing for decision support, lead to complex queries. Queries are often nested, defined over previously defined views, and may involve unions. There are good reasons why one might want to remove pieces (sub-queries or sub-views) from such queries: some sub-views of a query may be effectively cached from previous queries, or may be materialized views&semi; some may be known to evaluate empty, by reasoning over the integrity constraints&semi; and some may match protected queries, which for security cannot be evaluated for all users.In this paper, we present a new evaluation strategy with respect to queries defined over views, which we call tuple-tagging, that allows for an efficient removal of sub-views from the query. Other approaches to this are to rewrite the query so the sub-views to be removed are effectively gone, then to evaluate the rewritten query. With the tuple tagging evaluation, no rewrite of the original query is necessary.We describe formally a discounted query (a query with sub-views marked that are to be considered as removed), present the tuple tagging algorithm for evaluating discounted queries, provide an analysis of the algorithm's performance, and present some experimental results. These results strongly support the tuple-tagging algorithm both as an efficient means to effectively remove sub-views from a view query during evaluation, and as a viable optimization strategy for certain applications. The experiments also suggest that rewrite techniques for this may perform worse than the evaluation of the original query, and much worse than the tuple tagging approach.
Introduction
1.1 Motivation and Objectives
Many current database applications and environments, as mediation over heterogeneous database sources
and data warehousing for decision support, incur complex queries. Queries are often nested, defined over
previously defined views, and may involve unions. special type of such queries called fusion queries,
which are self-joins of views defined over unions, was discussed in [25]). This is a necessity in mediation, as
views in the meta-schema are defined to combine data from disparate sources. In these environments, view
definition maintenance is of paramount importance.
There are many reasons why one might want to "remove" pieces (sub-queries) from a given query. Let us call
a "sub-query" an unfolding, as the query can be unfolded via view definition into more specific sub-queries.
These reasons include the following:
1. Some unfoldings of the query may be effectively cached from previous queries [5, 9], or may be materialized
views [16] themselves.
2. Some unfoldings may be known to evaluate empty, by reasoning over the integrity constraints [1, 3].
3. Some unfoldings may match protected queries, which for security cannot be evaluated for all users [22].
4. Some unfoldings may be subsumed by previously asked queries, so are not of interest.
5. An unfolding shared by two queries in an except (difference) operation can be removed from both
queries before the operation is carried out.
d
a
e

Figure

1: The AND/OR tree representation of the original query.
What does it mean to remove unfoldings from a query? The modified query should not subsume-and thus
when evaluated should never evaluate-the removed unfoldings, but should subsume "everything" else of
the original query.
In case 1, one might want to separate out certain unfoldings, because they can be evaluated much less
expensively, and in a networked, distributed environment be evaluated locally. Then, a "remainder query"
can be evaluated independently to find the remaining answers [5]. If the remainder query is less expensive
to evaluate than the original, this is an optimization. In case 2, the unfoldings are free to evaluate, since it
is known in advance that they must evaluate empty. In case 3, when some unfoldings are protected, it does
not mean that the "rest" of the query cannot be safely evaluated. In case 4, when a user is asking a series of
queries, he or she may just be interested in the stream of answers returned. So any previously seen answers
are no longer of interest. In case 5, except queries might be optimized by this technique.
Consider the following example.
Example 1. Let there be six relations defined in the database DB: Departments(did, address), Insti-
tutes(did, address) Faculty(eid, did, rank), Staff(eid, did, position), Health Ins(eid, premium,
provider), and Life ins(eid, premium, provider).
There are also three views defined in terms of these relations:
create view create view create view
Academic Units as Employees as Benefits as
(select did, address (select eid, did (select eid, premium, provider
from Departments) from Faculty) from Life Ins)
union union union
(select did, address (select eid, did (select eid, premium, provider
from Institutes) from Staff) from Health ins)
Define the following query Q:
Q: select E.eid
from Academic Units A, Employees E, Benefits B
where A.did=E.did and E.eid=B.eid and B.provider="Blue Cross"
Query Q can be represented as a parse tree of its relational algebra representation, which is an AND/OR
tree, as shown in Figure 1 (we ignore for brevity explicit representation of project and select operations).
Evaluating the query-in the order of operations as specified in its relational algebra representation-is
equivalent to materializing all nodes of the query tree. This type of evaluation (and representation) is
referred to as bottom-up.
Now assume that the the following query F has been asked before and its result is stored in cache.
select E.eid
from Departments D, Faculty F, Life Ins L
where D.did=F.did and F.eid=L.eid and L.provider="Blue Cross"

Figure

2: The AND/OR tree representation of the modified query.
Equivalently, we can assume that this formula represents a materialized view or that it matches a protected
query whose answers should not be displayed. If F is a protected query, then the join expression
it computes should not be evaluated. Thus, it has to be eliminated from the query. Otherwise, if F
is a cached query or a materialized view, it may still be beneficial to "remove" it from the query. We
call the result of this a discounted query.
One way to achieve this is to rewrite Q as a union of joins over base tables, then to remove the
join represented by F (which then is explicitly present), and finally to evaluate the remaining join
expressions. This may be very inefficient, however. The number of join expressions that remain to be
evaluated may be exponential in the size of the collection of view definitions. Furthermore, we have
shown in [11] that such an evaluation plan (which is often called top-down) may require evaluating
the same joins many times, and incur the expense that a given tuple may be computed many times
(whenever the projected parts of base tables overlap significantly). A top-down evaluation of Q from

Figure

1 is the union of the eight following join expressions:
Departments 1 Faculty 1 Life Ins Departments 1 Faculty 1 Health Ins
Departments 1 Staff 1 Life Ins Departments 1 Staff 1 Health Ins
Institutes 1 Faculty 1 Life Ins Institutes 1 Faculty 1 Health Ins
Institutes 1 Staff 1 Life Ins Institutes 1 Staff 1 Health Ins
A seemingly more efficient evaluation plan for the discounted query can be devised by rewriting the
query so that the number of operations (unions and joins) is minimized. (See Figure 2.) As a side effect
of this approach, the redundancy in join evaluation, as well as redundancy in answer computation, is
reduced. However, such redundancy is not entirely eliminated: for example, the join Institutes 1
Faculty is computed twice (implicitly in the left sub-tree and explicitly in the right sub-tree). One
can verify that there is no rewrite of the query tree that removes the join Departments 1 Faculty
Ins and yet guarantees at the same time that there is no redundancy in the computation of
other joins. Thus, the "optimized" query can sometimes cost more to evaluate than the original query;
our experimental results show (see Section 4) that this is, indeed, the case for this example.
In this paper, we present a new strategy for partial evaluation of queries defined over views, which we call
tuple-tagging, which offers many advantages over explicit query rewrites.
ffl Tuple-tagging is easily implemented at the logical level, and can be accomplished by rewriting the SQL
expression of the query.
ffl The technique is modular: it can be implemented independently of other optimization stages (in
particular, of traditional relational database query optimization) to work in conjunction with the other
stages.
ffl Tuple-tagging is not an algebraic rewrite of the query: it preserves the query tree as is, and thus scales
up for complex queries.
ffl The tuple-tagging is interleaved with query evaluation. Thus, reliable heuristics can be devised and
employed to decide step-wise whether a given "optimization" step should be applied.
The paper is organized as follows. Section 2 presents a formal framework for discounted queries (that section
can be skipped on the first reading). Section 3 presents a tuple-tagging technique for evaluating discounted
queries. Performance analysis of the technique, and experimental results over a TPC/D benchmark database
in DB2, are presented in Section 4. Section 5 concludes with issues and future work.
1.2 Related Work
There is a substantial body of research in rewrite based query optimization [4, 6, 7, 19]. However, all of
the techniques discussed in literature considered rewriting a query into a logically equivalent form. This is
a different goal than the one we consider here: we are interested in generating and efficiently evaluating a
query (view) from which an unfolding has been removed. Thus, the resulting query is not equivalent to the
original query.
The problem we address is also different from the problem of answering queries using materialized views [2,
14, 16, 20]. In the latter problem, the goal is to replace subqueries of a query by views (or other queries)
to generate a query equivalent or contained in the original query. Our goal, again, is to remove, or more
precisely to avoid evaluating, parts of a query for optimization or security reasons.
The work that is most closely related to our work here is [15], in which the authors consider queries that
involve nested union operations. They propose a technique for rewriting such queries, when it is known that
some of the joins evaluated as part of the query are empty. The technique applies, however, only to a simple
class of queries, and no complexity issues are addressed.
Another research area related to our problem is multiple query optimization [21]. The goal here is to optimize
evaluation of a set of queries, rather than a single query. Since the queries in the set are arbitrary, they may
not be related in any structured way to allow use of the techniques that we propose here. The developed
techniques for multiple query optimization are focused towards finding and reusing common subexpressions
across collections of queries and are heuristics-based.
The problem of query tree rewrites for the purpose of optimization has also been considered in the context
of deductive databases with recursion. In [12], the problem of detecting and eliminating redundant subgoal
occurrences in proof trees generated by programs in the presence of functional dependencies is discussed. In
[13], the residue method of [1] is extended to recursive queries.
We investigated the computational complexity of query rewrites in [10]. We showed that the optimal rewrite
of a query is NP-hard. We also identified a special class of queries and unfoldings for which rewrites result
is a simpler query, thus always providing an optimization.
Discounted Queries
In this section, we formally define the notion of an unfolding and a discounted query. For preciseness, we use
the notation of Datalog [24]. We will write a query as a set of atoms, to be interpreted as a conjunction of
the atoms. For instance, fa; e; bg represents the query of Example 1. 1 Some of the atoms may be intensional;
that is, they are written with view predicates defined over base table predicates and, perhaps, other views.
Definition 2. Given query sets Q and U , call U a 1-step unfolding of query set Q with respect to database
DB iff, given some q i 2 Q and a rule ha / b defining a view for a, such that q i ' j a' (for
most general unifier ' [17]), then
We present only "propositional" examples for simplicity's sake. They can be extended in a obvious way to queries with the
variables made explicit.
a
e
l h
(1)
(2) (1)
(2)
(1)
(2)

Figure

3: AND/OR tree of Example 1 with two unfoldings marked.
Denote this by U - 1 Q. Call U 1 simply an unfolding of Q, written as U 1 - Q, iff there is some finite
collection of query sets U
An unfolding U is called extensional iff, for every q i 2 U , atom q i refers to a base table. Call the
unfolding intensional otherwise (in other words, some of the atoms refer to views).
Example 3. The views of Example 1 can be represented in simplified Datalog (where letters represent
atoms) as:
a / d. e / f . b / l.
a / i. e / s. b / h.
Since b in the query Q can be unfolded into l using a single rule hb / l:i, then fa; e; lg is one of the
1-step unfoldings of Q.
Since all of the atoms in unfolding F of Q (d, f , and l) are extensional, it is an extensional unfolding
of Q.
It is easy to see how an unfolding's AND/OR tree can be ``inscribed'' in the query's AND/OR tree. The
atoms of an unfolding can be marked in the query's tree as shown in Figure 3 for unfoldings
and, say, bg.
A query is considered to be equivalent to the union of all its extensional unfoldings; define unfolds (Q) to
be the set of all such extensional unfoldings of Q. We can now define the concept of a discounted query,
which is to represent the query with some of its unfoldings "removed" (or discounted).
Definition 4. Given a query set Q and unfoldings U of Q, then the expression QnfU is a
discounted query. We define its meaning to be:
unfolds
unfolds (U i
We call U the unfoldings-to-discount, and the tuples in the answer sets of these unfoldings the
tuples-to-discount.
Example 5. Consider again the query Q of Example 1. Since
fd; f; lg; fd; f; hg; fd; s; lg; fd; s; hg; fi; f; lg; fi; f; hg; fi; s; lg; fi; s; hg
and
fd; f; lg
then
fd; f; hg; fd; s; lg; fd; s; hg; fi; f; lg; fi; f; hg; fi; s; lg; fi; s; hg
Similarly, for the unfolding G, fi; s; bg, in Figure 3, we have
and
fd; f; hg; fd; f; lg; fd; s; lg; fd; s; hg; fi; f; lg; fi; f; hg
Lastly,
fd; f; hg; fd; s; lg; fd; s; hg; fi; f; lg; fi; f; hg
We discuss more formally the semantics of discounted queries in [8].
3 The Tuple-Tagging Evaluation Strategy
3.1

Overview

Our strategy is a bottom-up materialization strategy for the query tree with the union and join operations
modified to account for the discounted unfoldings. The strategy ensures two things:
ffl that tuples resulting from an unfolding-to-discount do not contribute to the answer set of the discounted
query; and
ffl any join represented by an unfolding-to-discount is never fully evaluated.
The tuples resulting from an unfolding-to-discount can be removed either during or after the actual query
evaluation. To ensure the second property and thus to gain optimization, we need somehow to avoid evaluating
the unfoldings-to-discount; that is, to prevent those tuples from being materialized during query
evaluation.
Our proposed method, tuple-tagging, is to keep extra information in the temporary tables created during
the materialization of the query tree. In essence, each table will have an extra column for each unfolding-to-
discount. The domain of these tag columns is boolean. The value of a tag column for a given tuple is true
when that tuple is derived from the corresponding unfolding-to-discount; it is false otherwise. During each
union or join operation (which creates a new temporary table), these tag columns' values must be maintained
properly.
Example 6. Consider query Q of Example 1. Query F , which represents the unfolding-to-discount, is a
join of Departments, Faculty and Life Ins. For each of these tables, a new column CF is added
and its values initialized to true. Similarly, for tables Institutes, Staff, and Health Ins which are
unioned with the above tables, the same column is added and its values initialized to false.
By keeping this derivation information for each tuple during evaluation, we can easily ensure the first property
from above: after evaluation of the query, select those tuples which have all false values in the tag columns
(and also project away the tag columns). We shall be able further to use the tag columns-and ultimately
satisfy our second property-to determine during a join operation which tuples should be joined, and which
should not be (because the resulting tuple would be "from" an unfolding-to-discount). The computation
saved will primarily depend on the size of the true section in the table.
We present the evaluation strategy in two versions. The simpler version ensures only the first property;
that is, the final answer set contains no tuples that arise solely from unfoldings-to-discount. The strategy
is useful in the case when unfoldings are removed for security reasons. It does little, however, to optimize
query evaluation: gross savings are equal to the difference in the cost of writing back the results of the
original query versus the cost of writing back the results of the discounted query (which can sometimes be
new tag columns on a need-by basis.
For each U i
For
If A 2 U i then
Add column CU i
to
Instantiate all values of CU i
in to true.
For each U i
For
If CU i
belongs to but not to TB then
Add column CU i
to
Instantiate all values of CU i
in TB to false.
% Union the two tables.
Union TLN and TRN to create TN .
Algorithm 1: The Modified Union Operation
significantly smaller). These savings can only be substantial when query results are sent over a network. The
second version removes the tuples-to-discount during query evaluation, as soon as is possible. This strategy
can reduce the cost of query evaluation. Both versions of the algorithm require modifying the union and
join operations. This is what we define next.
3.2 The Modified Union Operation
We assume that the query tree contains only union and join nodes (that is, all other operations are implicit).
Furthermore, without loss of generality, we assume the the tree is binary. We refer to one child of any branch
(non-leaf) node N in a binary query tree as LN (for left child), and the other as RN (for right child). We
assume that any leaf N in the query tree has a corresponding table in the database; that is, the answer set
for N is derivable from some table (perhaps temporary) in the database via selects and projections. Call
N 's table (with any selects and projections implicit) TN .
To handle discounted queries, we modify the traditional algorithm for bottom-up query evaluation. This
involves replacing the union and join operations with specialized versions, which handle and exploit the
tag columns for the unfoldings-to-discount, as discussed above. Given discounted query QnfU
we introduce new columns, CU i
as the tag columns corresponding to the unfoldings-to-
discount (as described in Example 6).
We assume for any well-formed query tree that the tables to be unioned at any union step are union-
compatible. With our addition of tag columns, this could now be violated. The two tables to be unioned
may not be union-compatible over the tag columns. Thus, we need to modify the union step first to make
the tables union-compatible by adding any tag columns that are needed. Algorithm 1 shows this. This is
the only way in which we need to modify the union step.
Note that Algorithm 1 can be efficiently implemented in SQL by adding tag columns and initializing their
values not before, but during the execution of the union operator. As we show in Section 4, this adds very
little overhead to the cost of the query execution.
3.3 The Modified Join Operation
We must assign the correct values to tag columns of joined tables. If a tuple results from the join of one
tuple which was derived under a given unfolding-to-discount U (hence the value of its CU is true), and a
second tuple which was not (hence the value of its CU is false), then the resulting tuple is not in the answer
set of U . So CU for the resulting tuple should have the value false. Only when both tuples being joined
were derived under U should the resulting tuple's column CU be set to true. Thus, tags are conjunctively
combined.
Let N be a join node in a query tree for which the children are LN and RN and let U be an unfoldings-to-
discount with the tag column CU in both tables TLN and TRN . The modified join operation executed at
node N is modified by adding the following assignment statement 2 for each unfolding-to-discount U :
Example 7. Consider the final join of the query of Example 1. The three joined tables, Academic Units,
Employees, Benefits will each contain an extra column, CF , storing the values for the unfolding-
to-discount F . This column has been introduced during the execution of the union operations (as
described in Algorithm 1). The query with the modified join operation is as follows.
select E.eid, (A.CF AND E.CF AND B.CF ) as CF
from Academic Units A, Employees E, Benefits B
where A.did=E.did and E.eid=B.eid and B.provider="Blue Cross"
The modified union and join operations have no influence (except for adding extra columns) on the final
answer set of a query. Their only purpose is to keep the trace information about the unfoldings-to-discount
via the tag columns. The last step of the tuple-tagging algorithm in its first version then consists in using
this information to select only the tuples that are known to be derivable from some unfolding other than an
unfolding-to-discount. To ensure this, it is sufficient to select the tuples that have the value false for all their
tag columns.
We show that the tuple-tagging algorithm (that is, the modified union and join operations) is correct. To
prove it we need to show that all tuples, and only tuples, having the value true in a tag column for a given
unfolding-to-discount in the final answer set of a query are the tuples from the answer set of that unfolding.
Theorem 8. Let QnfU be a discounted query and let denote the answer set
(table) representing the result of evaluating QnfU using the tuple-tagging algorithm. Then,
for any tuple -
Proof. Assume without loss of generality that all unfoldings-to-discount are extensional (an intensional
unfolding can be always represented as a union of extensional unfoldings). Let unfolding U i be a join
Consider a tuple - which is marked true in the column for unfolding U i , that is, -:CU i
true. Assume
that - 62 cannot be that the initial value (set by the
modified union operator) for CU i
is true for each of R Thus, if at least one of them is false,
then the value of CU i
will be changed to false (and will remain such) sometime during the evaluation
of joins. This contradicts our assumption, hence - 2
2 The as statement (as per the SQL'92 standards [18]) perform the requisite logical ands between tag columns and introduces
the tag columns back into the new table.
F
Benefits
Academic Units Employees
Institutes

Figure

4: Final join for the query of Example 9.
Assume
will be initialized to true for each of R Since the modified join
operator assigns a conjunction of the values of CU i
from the join tables, CU i
will remain true for the
duration of the evaluation process (note that the modified union operator never changes values for tag
columns). Hence, -:CU i
3.4 Optimization
As stated in Section 3.1, removing tuples-to-discount from the final query answer set according to the
optimization described above does not, in general, improve efficiency of query evaluation. For complex
queries, however, such removal can be executed during query evaluation; that is, before the final answer set
is produced. In other words, we can push some of the selects for false over the tag columns further down in
the query tree. This constitutes the tuple-tagging algorithm in its second version. Consider the following
example.
Example 9. Let the query be as in Example 1 and the unfolding-to-discount be (marked as (2)
in

Figure

3). Thus, all tuples in the join Intitutes 1 Staff 1 Benefits should be removed from the
query's answer set. Let us assume that the final join of the query Academic Units 1 Employees
1 Benefits is executed as specified in the query tree (that is, left to right). Consider the result of
evaluating Academic Units 1 Employees. Some tuples in the result of that join will have the value
true for the column C G (see Figure 4). Now, all tuples in the table for Benefits have the value true
for that column (because the table is a part of the unfolding-to-discount G). Thus, all of the tuples
marked true in the result of the join Academic Units 1 Employees will remain true after the join
with Benefits, hence will be removed from the final query answer set. 3 If so, they can be eliminated as
soon as Academic Units 1 Employees is evaluated. Note that this provides optimization because
the size of one of the tables in the input to the final join decreases. The gross savings achieved through
this optimization can be estimated to the cost of the join of the result of Institutes 1 Staff with
Benefits (marked with dotted lines in Figure 4).
We introduce the notion of a closing of an unfolding-to-discount by a node in a query tree.
Definition 10. Unfolding-to-discount U is closed by node N with respect to binary query tree QT if all
tuple marked true in TN contribute to all and only tuples of U .
3 In the final tuple-tagging query plan, we would not even need to add a tag column CG to Benefits for this very reason.
Thus, the node representing the join of Academic Units 1 Employees is a closing node of unfolding-to-
discount G in Example 9. Of course, the root of a query tree is a closing node for all unfoldings-to-discount.
Next, we prove a theorem that specifies a method of identifying closing nodes in a query tree.
Theorem 11. Unfolding U is closed by node N with respect to binary query tree QT if every node in U
that cannot be reached from the root of QT through join nodes only, is in the subtree rooted by N .
Proof. Consider the nodes of U that do not lie under N . None of these nodes contain a column for U and
since none of these tables will be used in a union (because there are join nodes only between these
nodes and the query tree root) such columns will never be created for the tuples from these tables.
Hence, no tuple in the table represented by the node N could contribute to a change in the value in
the column CU when they are joined during evaluation with other tables represented by the nodes of
U . Thus, the tuples with the value true for any unfoldings closed in N can be removed immediately
after (or while) the table TN is materialized. 2
Since there may be several closing nodes for a given unfolding, it is useful to identify the first one (in the
sequence of operations specified by the query tree) in order to eliminate tuples-to-discount as soon as possible.
Again, the condition for this property is simple. If N is a closing node for U and U does not have a closing
node in the subtree rooted at N , then N is the first of the closing nodes for U .
The tuple-tagging algorithm can utilize (as described in Example 9) the existence of closing nodes not only
to eliminate unfoldings-to-discount, but also to provide optimization. Our experimental results confirm that
this is indeed the case.
Performance Analysis
4.1 Experiments
The purpose of our experiments is threefold:
1. to evaluate the overhead (in query evaluation time) introduced by the tuple-tagging algorithm through
the modification of union and join operations;
2. to compare the performance of tuple-tagging versus query rewrite techniques in eliminating unfoldings-
to-discount; and
3. to evaluate the optimization of query execution through tuple-tagging.
We used TPC/D benchmark database of size 100MB for our experiments (for details on this benchmark
see [23]) installed on DB2 in Windows-NT. In order to be able to define views with unions, we modified
slightly the TPC/D schema. Thus, the three tables Supplier, Partsupp, and Lineitem, which are base
tables in the TPC/D schema, have been partitioned horizontally in half, and new base tables representing
each of the sub-tables (Supplier1 and Supplier2, and so forth) have been created. Then, views Supplier-
v, Partsupp-v, and Lineitem-v have been defined as unions over Supplier1 and Supplier2, Partsupp1
and Partsupp2, and Lineitem1 and Lineitem2, respectively. Thus each of the views has exactly the same
content as the original tables in the TPC/D benchmark database.
We tested several versions of the following three queries.
select *
from Supplier-v S, Partsupp-v P from Supplier-v S, Partsupp-v P
where S.suppkey=P.suppkey where S.suppkey=P.suppkey
select *
(1)
(1) (1) (3)
(2) (2)
(2)

Figure

5: Query tree for Q 2 with marked unfoldings-to-discount.
from Supplier-v S, Partsupp-v P,
where S.suppkey=P.suppkey and
P.partkey=L.partkey and
For
1 , we defined one unfolding-to-discount:
ffl U 0 , a join of Supplier1 and Partsupp1.
For we defined the following three unfoldings-to-discount (marked in the query tree in Figure 5):
1. U 1 , a join of Supplier1, Lineitem1, and Partsupp1
2. U 2 , a join of Supplier2, Lineitem2, and Partsupp-v
3. U 3 , a join of Supplier2, Lineitem2, and Partsupp2
Then the following discounted queries were tested:
g.
Note that Q 2 and Q have exactly the same structure as, respectively, Q and QnfFg of Example 1.
Similarly, has the same structure as QnfGg of Example 9.
Since DB2 does not support boolean data types, we used integers (0 and 1) for tags, and we used multiplication
instead of logical AND for their manipulation. For example, the query Q evaluated under
the tuple-tagging strategy has the following form:
select *
from Supplier-v S, Partsupp-v P, Lineitem-v L
where S.suppkey=P.suppkey and P.partkey=L.partkey and P.suppkey=L.suppkey
and S.tag1 * P.tag1 *
Here tag1 and tag2 stand for tags for U 1 and U 3 respectively, and their values have been set up in the
definitions of the views Supplier-v, Partsupp-v, and Lineitem-v.

Table

1 presents the results of tests measuring the evaluation cost of several queries. We used both tuple-
tagging and explicit rewrites in evaluating the discounted queries. Thus, the suffixes tag, rew, and top mean
that a discounted query was evaluated using respectively tuple-tagging, explicit rewrite of its query tree to
minimize the number of operations (as described in Example 1), and the top-down approach (that is, by
evaluating all joins of base tables). In particular, the query tree for rew has the same structure as
the query tree of Figure 2. Similarly, Q rew has the following form: 4
AllAttributes [(Supplier1 [
4 We express this in relational algebra only for brevity.
Query Total Execution Time (s) Number of Retrieved Rows
tag 3.495 1
tag 17.5 7242
tag 364.38
rew 582.82 65219
tag 356.18
rew 482.65 55537
tag 298.88 56002

Table

1: Experimental Results
One can easily verify that this is the most compact representation of Q g. Recall that Q 2 nfU 1 g top
was evaluated as a union of all its extensional unfoldings-that is, a union over the joins of base tables-and
similarly for top .
4.2 Discussion
The purpose of testing Q 1 and Q 1 nfU 0 g is to measure the overhead of adding and manipulating tags. The
query is designed in such a way that no optimization in query execution time can possibly be achieved by
using tags. This is done by making the root the closing node for U 0 in Q 1 nfU 0 g (so that the joined tables
are of identical sizes as in Q) and minimizing the size of the answer set (thus making sure that there is no
benefit in writing less data back to a disk). Indeed, query execution time for is 3.495 seconds which
is larger than that for Q 1 , which is 3.485 seconds. The good news is that the difference is negligible: 0.29%
in the case of Q g. Once the size of the answer becomes substantial, tuple-tagging begins to
optimize. Queries Q 0
project all attributes of the two joined tables. By reducing the size of
the answer set, Q 0
provides optimization in query execution time over Q 0
vs. 25.6 seconds for Q 0
1 .
The purpose of queries is to compare tuple-tagging with two other techniques
for removing unfolding from a query: top-down query evaluation; and an explicit rewrite of a query tree
to minimize algebraic form. Tuple-tagging outperforms the other two techniques by a respectable margin.
In fact, both the top-down approach and the explicit query rewrite approach add substantial overhead to
the cost of evaluating discounted queries (see Table 2). As we conjectured in Section 1, this is due to the
introduction of redundancy in join evaluation for both techniques. On the other hand, both and
evaluated under the tuple-tagging strategy provide modest optimization over Q 2 (see Figure 6).
This is still achieved only through the reduction of the size of the answer set, and not through reduction of
the sizes of the joined tables.
The last query, Q 2 nfU 2 g, provides a crucial test for our technique. The temporary table created through
the join Supplier-v 1 Lineitem-v is a closing node for unfolding U 2 . This means, that all tuples marked
as true in that table can be eliminated before the next join (with Partsupp-v) is executed, thus reducing
Query Evaluation Strategy
Tuple-Tagging Top-Down Explicit Rewrite

Table

2: Evaluation time (in seconds) for discounted queries under different evaluation strategies.
the cost of that last join. Indeed, the reduction of the execution cost in Q 2 nfU 2 g over the original query Q 2
is 25.7%.
4.3 Heuristics
As stated in Section 1, one of the advantages of tuple-tagging over explicit query tree rewrites is that reliable
heuristics can be devised to decide step-wise whether a given "optimization" step should be applied. Such
a decision will depend on the reduction of the size of a table representing a closing node for some unfolding
(or a set of unfoldings) in the query tree. For example, in query Q half of the tuples in Supplier-v
and half of the tuples in Lineitem-v are marked true. Hence, the proportion of the tuples marked true
in the join Supplier-v 1 Lineitem-v (assuming a uniform distribution of values) is estimated to be 25%.
Once these tuples are eliminated, the cost of the join with Partsupp-v is roughly estimated to be reduced
by 25% as well. We show formally how such a reduction can be estimated in general, thus providing a main
component for heuristics that can be used with the tuple-tagging algorithm.
The proportion of tuples-to-discount versus all of the tuples, p, in a table representing a closing node N
depends on three factors: the proportion of tuples tagged with true for some unfolding-to-discount closed
by N ; the number of unfoldings-to-discount closed by N ; and the size of the join (how many tables
participate). We state this dependence formally as follows. (We assume a uniform distribution of tuples-to-
discount among all tuples in each table.)
Theorem 12. Let table T 0 be created through a join of tables T 1 ,.,T m each with n different tag columns
be the proportion of tuples in the table T j with the value true in the column
the proportion of tuples in T 0 for which all tag columns have the value true, is:
Proof. Induction on n.
1.
If there is only one unfolding-to-discount, then a tuple - is discounted only if it was created by
joining from the tables participating in a join, such that each tuple -
had the value true in column CU . The probability of this is \Pi m
which is the value of
the above formula for
2. Assume that the formula holds for n unfoldings-to-discount. We show it holds for
A tuple is discounted when are considered in one of the following
cases:
a. It would have been discounted when only n unfoldings-to-discount were considered.
b. It is discounted because it is in the answer set of the n 1-st unfolding-to-discount.
The probability of 2a is given by the induction hypothesis as:
Q2 Q2nfU1g Q2nfU2g

Figure

Comparison of execution times (s) of the original query and queries evaluated with tuple-tagging.
The probability of 2b is a conditional probability that the tuple has not been discounted when
only n unfoldings-to-discount were considered, but is discounted when the 1-st unfolding-to-
discount is considered. This probability can be expressed as: \Pi n
Thus, the probability that a tuple is discounted when n+ 1 unfoldings-to-discount are considered
is equal to the sum of the probabilitues of cases 2a and 2b:
In the special case when the proportion of tuples marked true in all tables and all tag columns is identical
and equal to some value P (T ) (that is,
reduces to:
We show the application of this result to predict the size of tables for closing nodes in our experiments.
Example 13. For queries g, the root of the query tree is the closing node. The
proportion of tuples marked true for both U 1 and U 3 is 0.5 for all three tables: Supplier-v, Partsupp-
v, and Lineitem-v. Thus, for query Q 2 nfU 3 g, Formula 1) has the form
Since the size of the answer of the original query Q was 73943 rows, reducing it by 12.5% would produce
a table of size 64700. This is very close to the actual size of 65219 rows observed for g.
Similarly, for query Q has the form 0:234. The predicted
size of the final query answer set is thus 56566, which again is close to the actual size of 55537 for
g.
The values for Formula 1) (p as a function of n) is plotted in Figure 7 for 2-way and 5-way joins with several
values of p(T ). Not surprisingly, the number of discounted tuples grows with the number of unfoldings-to-
discount as well as the proportion of the tuples-to-discount in the tables participating in the join. There is
also, however, a strong inverse relationship between the number of joins involved in a multiway join and the
number of discounted tuples. Even if each of the tables participating in the join has 30% tuples-to-discount
different unfolding are removed, the number of discounted tuples is very small for a 5-way join.
Conclusions
In this paper, we introduced a new framework in which a query is represented as a collection of selected
unfoldings of the query and a discounted query, which represents the query with those unfoldings "removed".
p(T)=10%
p(T)=30%
p(T)=50%
p(T)=90% p(T)=70%
100%6020(a) 2-way join
p(T)=30%
p(T)=50%
p(T)=70%
p(T)=90%2060100%
(b) 5-way join

Figure

7: Proportion of discounted tuples in the result of a join with respect to the number of unfoldings-
to-discount.
The selected unfoldings may be removed for security reasons, or because their answers are readily available
(through caching or materialized views). We presented an efficient evaluation strategy for discounted queries
called tuple-tagging. We showed through experiments that a discounted query can be, in general, evaluated
more efficiently than the query itself. The experiments also suggested that rewrite techniques, which seem
to be an intuitive approach to removing unfoldings from a query, may perform worse than the evaluation of
the original query, and much worse than the tuple tagging approach. Thus the discounting framework and
the tuple-tagging algorithm offer a viable approach to optimization of queries which employ views.
There are numerous issues to explore with respect to optimization of queries over views. This type of
optimization is orthogonal to other optimization techniques, and so can be directly used in conjunction
with existing optimizers. It would be beneficial to identify the types of interaction with the traditional
query optimizer that could increase overall optimization. Currently tuple-tagging is done in a prior stage,
and optimization is applied over the resulting queries. We also need to understand better the various cost
trade-offs in tuple-tagging, and how best to balance them.



--R


Optimizing queries with materialized views.
Implementation of two semantic query optimization techniques in DB2 universal database.
Rule languages and internal algebras for rule based optimizers.
data caching and replacement.
A rule specification framework for query optimizers.

A framework for intensional query optimization.
Answering queries by semantic caches.
View disassembly.
query optimization for bottom-up evaluation
Structural query optimization - a uniform framework for semantic query optimization in deductive databases
Pushing semantics inside recursion: A general framework for semantic optimization of recursive queries.
Computing queries from derived relations.
query reformulation in deductive databases.
Answering queries using views.
Foundations of Logic Programming.
Understanding the New SQL: A Complete Guide.
Extensible/rule based query rewrite optimization in Starburst.
Query folding.
On the multiple-query optimization problem
constraint processing in a multilevel secure distributed database management system.
Transaction Processing Performance Council
Principles of Database and Knowledge-Base Systems
Fusion queries over internet databases.
--TR
A rule-based view of query optimization
Foundations of logic programming; (2nd extended ed.)
Principles of database and knowledge-base systems, Vol. I
Logic-based approach to semantic query optimization
Structural query optimizationMYAMPERSANDmdash;a uniform framework for semantic query optimization in deductive databases
Extensible/rule based query rewrite optimization in Starburst
Understanding the new SQL
Answering queries using views (extended abstract)
Rule languages and internal algebras for rule-based optimizers
On the Multiple-Query Optimization Problem
Constraint Processing in a Multilevel Secure Distributed Database Management System
Fusion Queries over Internet Databases
Query Reformulation in Deductive Databases
Praire
Pushing Semantics Inside Recursion
Optimizing Queries with Materialized Views
Query Folding
View Disassembly
Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database
Semantic Data Caching and Replacement
Query Optimization for Bottom-Up Evaluation
Answering Queries by Semantic Caches

--CTR
Parke Godfrey , Jarek Gryz, View disassembly: A rewrite that extracts portions of views, Journal of Computer and System Sciences, v.73 n.6, p.941-961, September, 2007
query rewrite;query optimization;relational databases;database mediation;TPC/D benchmark;database security;data warehousing