Databases Reference
In-Depth Information
the application of resolution to them. The computation is a tree, whose branching
factor corresponds to the multiple ways of applying a resolution step to a query. The
resolution step terminates if the set of source constraints obtained by translating the
target constraints is acyclic.
However, the query rewriting algorithm may still be incomplete, as it explicitly
avoids recursion. The validity of the incomplete results is proved experimentally, by
measuring their approximation with respect to the complete set of certain answers.
However, it is still an open problem how to bridge the completeness gap in an
efficient way.
Target query answering is addressed in HePToX [
Bonifati et al. 2010
] as back-
ward translation, i.e., translation of a query
q
over the target schema and against the
direction of the mappings. In HePToX, the opposite direction of query translation,
namely the forward translation, is also considered, to highlight the importance of
having bidirectional mappings, which can be traversed either ways. A key compli-
cation in forward translation is that
, the mapping that transforms instances of
S
to those of
T
, may not be invertible [
Fagin 2007
]. In this direction, the semantics
of query answering is still based on certain answers over all possible pre-images
I
k
for which
J
.I
k
/
. This direction is novel and has not been handled in previous
D
work.
To handle this translation, the query
q
posed against
S
is transformed into a tree
pattern (for simplicity, only one tree pattern is considered, although the query trans-
lation module can handle joins of tree patterns). The tree pattern is matched against
each of the rule bodies in
˙
st
; this phase is called
expansion
. The tree pattern, possi-
bly augmented with dummy nodes at the end of the expansion, is translated against
the rules in
˙
st
, leading to the
translation
phase. Several translated tree patterns
may be merged in the
stitching
phase, and dummy and redundant nodes may be
eliminated in the
contraction
phase.
6
Developments and Applications
In this chapter, we discuss the recent developments and applications of schema
mapping. Schema mapping is widely known as the “AI-complete” problem of
data management, and, as such, exhibits strong theoretical foundations, as it has
been highlighted in the previous sections. However, the question we ask ourselves
is: what are the real application scenarios in which schema mapping is used? is
schema mapping an everyday life problem? All the scenarios that entail the access
to multiple heterogenous datasets represent natural applications of schema map-
ping [
Halevy 2010
]. For instance, executing a Web search leads to dispatch the
request to several web sites that are differently structured and have possible over-
lapping content. Thus, providing a common semantic layer that lets obtain a uniform
answer from multiple sites, by means of explicit or implicit correspondences, is the
common objective of schema mapping tools. There are several directions on which
researchers have focused their attention, and achieved promising results, namely:
