Database Reference
In-Depth Information
8
Alternative semantics
So far, our default semantics for answering queries in data exchange was the certain an-
swers semantics. But is it always right to use it? After all, we have seen that even in the
simplest possible,
copying
mappings, that essentially say “copy the source to the target”,
some relational algebra queries cannot be answered (see
Proposition 7.16
in
Section 7.6
).
This is rather counter-intuitive behavior: one should expect that, in a copying mapping, re-
lations simply change name but not content, and queries should be answerable over a copy
of the source.
The standard certain answers semantics presents us with a host of problems:
•
some queries are not rewritable even under the simplest mappings;
•
computing answers to relational algebra queries is in general an undecidable problem;
and
•
computing certain answers could be intractable even for very simple and practically
relevant classes of queries (e.g., conjunctive queries with inequalities, or SQL queries
admitting inequalities in the
where
clause, as shown in
Theorem 7.4
).
Should we always follow the certain answers semantics? Is it really sacred in data ex-
change? Or perhaps we can find an alternative data exchange semantics that avoids the
problems we listed above?
In a way, there is no fully satisfactory answer to these questions. Every semantics one
presents is going to work well in some scenarios, and exhibit problems in others, and thus
the choice of the semantics depends on the precise interpretation of what the mapping rules
actually mean. But alternative semantics have been proposed, and we present several here
that attempt to solve the problems above.
Each of these semantics follows the same idea as certain answers semantics, but
restricts
the space of solutions
. That is, they are defined as
(
Q
,
S
)=
certain
good
M
{
Q
(
T
)
|
T
is a “good” solution for
S
}
,
(8.1)
where “good” somehow determines the preferred solutions in data exchange.
The first of these takes “good” to be universal solutions, which, as we stated in
Chapter
6
, are the preferred solutions in data exchange. This semantics offers good complexity
