Databases Reference
In-Depth Information
will contain the current pattern. This crucial task is done by relying on a proce-
dure called
certain()
, which rewrites the certain answers of a query on the target
as a query on the source. Given a source instance
I
, a schema mapping
M
,and
a query
q
on the target schema, the set of
certain answers
to
q
in
I
with respect
to
M
, is the intersection of the results from the query
q.J
i
/
over all the possible
solutions
J
i
to the mapping. The authors introduce a practical version of the algo-
rithm in which
certain()
relies on a variant of the MiniCon algorithm [
Pottinger and
Halevy
2001
], which works for conjunctive formulas, and they also announce [
ten
Cate and Kolaitis
2009
] a more general algorithm to compute
certain()
on arbitrary
FO queries. In the example, the precondition for the pattern
Company
.I;n;s/
is the
left hand side of mapping
m
0
1
above. In the third step, the algorithm generates addi-
tional
side-conditions
to handle special cases with self-joins in the conclusion, i.e.,
s-t tgds in which the same relation symbols occurs more than once in the right-hand
side. Side-conditions are Boolean combination of formulas with inequalities. In our
example, side-conditions are not generated as there are not self-joins. In the final
step, the algorithm put together the laconic schema mapping with preconditions and
side-conditions in the left-handside and the respective pattern in the right-handside,
thus generating mappings such as
m
0
1
above.
In terms of dependencies generated by the algorithm, laconic mappings from the
algorithm in
ten Cate et al.
[
2009
] tend to contain a lower number of dependencies
with more complex premises with respect to the core schema mappings from
Mecca
et al. [
2009a
], which typically contain more rules. In fact, laconic mappings rea-
son on patterns at a “global” level, while the rewriting algorithm for core schema
mappings works at a “local” level, i.e., at the tgd level.
5
Query Answering in Mapping Scenarios
An important application of schema mappings arises in all the scenarios in which
queries are formulated against one of the two schemas connected by the mappings
and need to be translated against the other schema. In the early years, the semantics
of query answering in indefinite databases adopted the notion of “certain answers.”
This notion has also been adopted in data exchange [
Fagin et al. 2005a
], while study-
ing the computational complexity of target query answering, i.e., the problem of
computing certain answers for a target query
q
.
As already explained in Sect.
4.3
, to represent all possible databases, we must
consider the set of all possible target instances
J
i
and the source
instance
I
. Since there may be several target instances
J
i
, we must consider the
consistent with
M
intersection
T
J
i
q.J
i
/
, the intersection being called the set of the
certain answers
of
q
.
In
Fagin et al.
[
2005a
], the semantics of query answering has been defined by
considering the universal solutions. Indeed, it is important to ascertain whether
certain answers of a query can be computed by query evaluation on the “good”
target instance that has been chosen for materialization. In Sect.
2
, we have already
