Database Reference
In-Depth Information
data inequalities. Under these assumptions, a syntactic representation can be computed
in exponential time.
•
Some alternative semantics for the inverse operator for schema mappings have been
proposed. A first such semantics is based on the idea that a mapping
M
is an inverse
M
is equal to the identity schema
of a mapping
M
if the composition of
M
with
mapping.
•
A different approach to define an inverse operator is followed when defining the notions
of recovery and maximum recovery. The underlying idea of the notion of maximum
recovery is to give a formal definition for what it means for a mapping
M
to recover a
maximal amount of sound information with respect to a mapping
M
.
•
There exists a mapping specified by st-tgds that does not admit an inverse, but every
mapping specified by these dependencies admits a maximum recovery.
•
Maximum recoveries for mappings specified by st-tgds can be computed by an
exponential-time algorithm based on query rewriting.
•
There exist structural characterizations for the classes of mappings specified by st-tgds,
LAV st-tgds and GAV st-tgds. These structural characterizations can be used to prove the
NP-completeness of the problem of verifying whether a mapping specified by st-tgds
can be specified by LAV st-tgds, or by GAV st-tgds.
22.2 Bibliographic comments
Consistency problems for XML schema mappings were first considered by
Arenas and
Libkin
(
2008
) in the absence of sibling order and data comparisons. In the general setting,
consistency was studied by
Amano et al.
(
2009
), who also gave a partial solution to the
absolute consistency problem. A general algorithm for absolute consistency was designed
by
Bojanczyk et al.
(
2011
).
A general framework for metadata management, where mapping operators such as com-
position and inversion play a central role, was proposed by
Bernstein
(
2003
). Mapping
composition in the relational setting was first studied by
Fagin et al.
(
2005b
), who proved
that the problem C
OMPOSITION
(
M
12
,
M
23
) is in NP for every pair of mappings
M
12
,
M
23
specified by st-tgds, and showed that there exist mappings
M
12
,
M
23
specified by
st-tgds such that C
OMPOSITION
(
23
) is NP-complete. They also proved that the
class of mappings specified by st-tgds is not closed under composition, proposed the lan-
guage of SO tgds, proved that the class of mappings specified by SO tgds is closed under
composition, provided an exponential-time algorithm for computing the composition of
two mappings specified by SO tgds, and showed that every SO tgd defines the composi-
tion of a finite number of mappings specified by st-tgds. Interestingly, it was proved by
Arocena et al.
(
2010
) that the composition of two LAV mappings can be defined by a
LAV mapping. The equivalence problem for SO tgds was studied by
Feinerer et al.
(
2011
).
Some extensions of the framework proposed by
Fagin et al.
(
2005b
) have been studied in
the literature. In particular,
Nash et al.
(
2007
)and
Bernstein et al.
(
2008
) considered the
M
12
,
M
