Databases Reference
In-Depth Information
system, which is the query module in Orchestra, focuses on keywords queries rather
than on XQuery queries.
Calvanese et al.
[
2004
] address data interoperability in P2P systems using expres-
sive schema mappings, also following the GAV/LAV paradigm, and show that the
problem is in PTIME only when mapping rules are expressed in epistemic logic.
6.4
Normalizing Schema Mappings
Schema mappings, as high-level specifications describing the relationships between
two database schemas, are subject to optimization.
Fagin et al.
[
2008
] lay the foun-
dations of schema mapping optimization, by introducing three kinds of equivalence:
(1) logical equivalence, stating that two schema mappings
M
D
.
S
;
T
;˙/
and
M
0
.
S
;
T
;˙
0
/
3
are logically equivalent if for every source instance
I
and target
instance
J
,wehavethat
.I; J/
D
˙
0
; (2) data-exchange
equivalence, if for every source instance
I
, the set of universal solutions for
I
under
M
ˆ
˙
if and only if
.I; J/
ˆ
M
0
; (3) conjunctive-
query equivalence, if for every target conjunctive query
Q
and for every source
instance
I
, the set of solutions for
I
under
coincides with the set of universal solutions for
I
under
M
is empty if and only if the set of
M
0
is empty, and, whenever they are not empty, the set of
certain answers of
Q
on
I
under
solutions for
I
under
M
coincides with the set of certain answers
M
0
. Equivalences (2) and (3) coincide with equivalence (1)
of
Q
on
I
under
when
˙
˙
st
, but differ on richer classes of equivalences, such as second-order
tgds and sets of both
˙
st
and
˙
t
. The assumption of logical equivalence has also
been done in
Gottlob et al.
[
2009
], which focuses on the normalization of schema
mappings with respect to four optimality criteria, precisely cardinality-minimality,
antecedent-minimality, conclusion-minimality, and variable-minimality. Following
these criteria, given a set of st-tgds in
˙
, the total number of st-tgds in this set,
the total number of atoms in the antecedent and conclusion of each st-tgd shall
be minimal, along with the total number of existentially quantified variables in the
conclusion. The presence of egds is not considered in
Gottlob et al.
[
2009
] and rep-
resents a natural extension. Other than that, much work remains to be done toward
defining new heuristics for schema mapping optimization, extending the above cri-
teria to larger classes of rules, and considering the impact of all the equivalences
discussed above.
D
7
Conclusions and Future Work
In this chapter, we have discussed the state of the art of schema mapping algorithms,
along with their most recent developments and applications.
We believe that there are quite a lot of open problems in this area, which we
attempt to briefly discuss below.
3
We do not distinguish here between
˙
st
and
˙
t
and consider
˙
as a set of generic constraints.
