Database Reference
In-Depth Information
7
Query answering and rewriting
In data exchange, we are interested in computing certain answers to a query. However, we
do not yet know when such a computation is feasible. The goal of the chapter is to answer
this question.
The bad news is that the problem of computing certain answers for relational calculus
(equivalently, relational algebra or FO) queries is undecidable, even in the absence of target
dependencies. But the good news is that the problem becomes decidable, and, indeed,
tractable, for unions of conjunctive queries over mappings with a weakly acyclic set of
tgds. Conjunctive queries, as was already mentioned several times, play a very important
role and are very common, and mappings with weakly acyclic sets of tgds, as we have seen,
are the ones behaving particularly well when it comes to materializing solutions.
The positive result, however, breaks down when we extend conjunctive queries with
inequalities. But we can still find a meaningful class of queries capable of expressing in-
teresting properties in the data exchange context that extends conjunctive queries with a
limited amount of negation and shares most of their good properties for data exchange.
Finally, we study the notion of query rewriting, i.e., when certain answers to a query Q
can be computed by posing a possibly different query Q over a materialized solution. Such
rewritings are easy for unions of conjunctive queries; our study concentrates on rewritings
of relational algebra queries. We compare rewritings over different solutions, and develop
easily applicable tools that determine when rewritings are not possible.
7.1 Answering relational calculus queries
In this chapter we are interested in the problem of computing certain answers for a
relational mapping
M
and a query Q over R t . Recall that a mapping
M
is a tuple
(R s , R t ,
Σ st ,
Σ t ),whereR s is the source schema, R t is the target schema,
Σ st is the set of
source-to-target dependencies, and
Σ t is the set of target dependencies. Given a source in-
stance S , certain answers to Q are defined as certain M ( Q , S )= {
Q ( T )
|
T
S OL M ( S )
}
.
The problem we study is formulated as follows.
Search WWH ::




Custom Search