Database Reference
In-Depth Information
problem of computing the composition of mappings defined by dependencies that need
not be st-tgds,
Arenas et al.
(
2011a
) considered the problem of composing mappings that
are specified by st-tgds, target egds and weakly acyclic sets of target tgds, and
Libkin and
Sirangelo
(
2011
) proposed the language of CQ-SkSTDs, that slightly extends the syntax of
SO-tgds, and studied the composition problem under the closed-world semantics presented
in
Section 8.2
for mappings specified by CQ-SkSTDs.
Composability of XML mappings was considered by
Amano et al.
(
2009
), but the exact
formulation of the result and the proof come from
David et al.
(
2010
).
The first notion of inversion for schema mappings specified by st-tgds was proposed by
Fagin
(
2007
), who proved that there exist mappings specified by these dependencies that
do not admit an inverse. A necessary and sufficient condition for the existence of an inverse
for a mapping specified by st-tgds was proposed by
Fagin et al.
(
2008b
), and a more general
necessary and sufficient condition for the class of mappings that are total and closed-down
on the left was proposed by
Arenas et al.
(
2009b
). The
CO
NP-completeness of the problem
of deciding whether a mapping specified by st-tgds has an inverse was proved by
Fagin and
Nash
(
2010
), and the undecidability of the problem of verifying, given mappings
M
M
,
M
is an inverse of
specified by st-tgds, whether
was proved by
Arenas et al.
(
2009b
).
The notion of quasi-inverse was introduced by
Fagin et al.
(
2008b
). They proved that it
strictly generalizes the notion of inverse proposed by
Fagin
(
2007
), provided a necessary
and sufficient condition for the existence of a quasi-inverse for a mapping specified by st-
tgds, and used this condition to prove that there exist mappings that do not admit a quasi-
inverse. The undecidability of the problem of verifying, given mappings
M
M
specified
M
,
M
is a quasi-inverse of
by st-tgds, whether
was proved by
Arenas et al.
(
2009b
).
The notions of recovery and maximum recovery were introduced by
Arenas et al.
(
2009b
). They proposed a necessary and sufficient condition for a mapping
M
M
to be a
M
maximum recovery of a mapping
, provided a necessary and sufficient condition for the
existence of a maximum recovery for a mapping, proved that every mapping specified by
st-tgds admits a maximum recovery, showed that the notion of maximum recovery strictly
generalizes the notion of inverse proposed by
Fagin
(
2007
) for the class of mappings that
are total and closed-down on the left, established the relationship with the notion of quasi-
inverse for the class of mappings that are total and closed-down on the left, and proved the
undecidability of the problem of verifying, given mappings
M
specifiedbyst-tgds,
M
,
M
is a recovery (maximum recovery) of
whether
.
The exponential-time algorithm for computing maximum recoveries presented in
Chap-
ter 20
, which can also be used to compute inverses and quasi-inverses, was proposed by
Arenas et al.
(
2009b
). The same paper also gave a quadratic-time algorithm for comput-
ing maximum recoveries for the case of full st-tgds. The fact that there exists an invertible
mapping specified by st-tgds that does not admit an inverse specified by st-tgds was proved
by
Fagin et al.
(
2008b
).
The notions of extended recovery and maximum extended recovery were proposed by
Fagin et al.
(
2011
), who showed that there exists a mapping specified by tgds that does not
admit a maximum recovery if source instances are allowed to contain nulls, and proved
M
