Database Reference
In-Depth Information
P
S
1
.Let
S
2
be an instance of R
1
consisting only of the fact
P
(
t
0
),thatis,
P
S
2
=
t
0
∈
{
t
0
}
and
R
S
2
= 0 for all the other relations
R
in R
1
.Since
Σ
12
is a set of st-tgds, we have that:
S
OL
M
(
S
2
)
.
S
OL
M
(
S
2
)
⊆
S
OL
M
(
S
2
) and
S
2
⊆
S
1
, which shows that (
S
1
,
S
2
) is also a wit-
Hence, S
OL
M
(
S
1
)
⊆
.Nowlet
T
1
,
T
2
be the canonical universal
ness for the noninvertibility of mapping
M
solutions for
S
1
and
S
2
under
M
, respectively. Given that
T
1
∈
S
OL
M
(
S
1
),wehavethat
S
OL
M
(
S
2
) and, therefore, there exists a homomorphism
h
from
T
2
to
T
1
.Weuse
h
to construct the desired quadratic-size witness for the noninvertibility of mapping
T
1
∈
.
More precisely, let
S
1
be an instance of R
1
defined as follows. For every
R
in R
2
and tuple
t
M
R
T
2
, choose a st-tgd
b
such that (1)
∈
ϕ
(
x
)
→∃
y
ψ
(
x
,
y
) and tuples
a
,
ϕ
(
x
)
→∃
y
ψ
(
x
,
y
)
Σ
12
,
a
is a tuple of values from D
OM
(
S
1
) and
b
is a tuple of values from
D
OM
(
T
1
),(2)
is a st-tgd in
(
a
,
b
) holds in
T
1
,and(4)
R
(
h
(
t
)) is a conjunct in
ϕ
(
a
) holds in
S
1
,(3)
ψ
(
a
,
b
). It should be noticed that such a tuple exists since (
S
1
,
T
1
) satisfies
ψ
12
and
R
(
h
(
t
))
is a fact in
T
1
(given that
h
is a homomorphism from
T
2
to
T
1
). Then include all the con-
juncts of ϕ(
a
) as facts of
S
1
. Next we show that (
S
1
,
S
2
) is a witness for the noninvertibility
of
Σ
S
1
S
2
2
).
M
and
+
is
O
(
Σ
12
. By definition of
S
1
,we
have that the homomorphism
h
mentioned above is also a homomorphism from
T
2
Let
T
1
be the canonical universal solution for
S
1
under
M
to
T
1
.
Thus, given that
T
1
is a universal solution for
S
1
under
is closed under target
homomorphisms (see
Proposition 21.1
in
Section 21.1
), we conclude that S
OL
M
(
S
1
)
M
and
M
⊆
S
OL
M
(
S
2
). Moreover, given that
S
1
⊆
S
1
,wealsohavethat
S
2
⊆
S
1
and, hence, (
S
1
,
S
2
) is
. Finally, given that
S
2
consists of only one fact, we
a witness for the noninvertibility of
M
T
2
have that
. Therefore, given that the number of tuples that are
included in
S
1
for each fact
R
(
t
) in
T
2
is bounded by
is bounded by
Σ
12
S
1
Σ
12
,wehavethat
is bounded
2
. Thus, it holds that
S
1
S
2
2
), which concludes the proof of the
by
Σ
12
+
is
O
(
Σ
12
theorem.
M
,whether
A problem related to checking invertibility is to check, for mappings
M
and
M
is an inverse of
. Somewhat surprisingly, this problem is undecidable even for the
class of mappings specified by st-tgds.
M
M
=
Theorem 20.11
The problem of verifying, given mappings
M
=(R
1
,
R
2
,
Σ
12
)
and
M
is an inverse of
(R
2
,
R
1
,
Σ
21
)
with
Σ
12
and
Σ
21
finite sets of st-tgds, whether
M
is
undecidable.
A fundamental, and arguably the most important, issue about any notion of inverse is the
problem of computing an inverse for a given mapping. We shall handle this problem in
Section 20.3
.
A relaxation of inverses: quasi-inverse
The notion of inverse is rather restrictive as there are many mappings that do not possess
an inverse. Thus, there is a need for weaker notions of inversion. We now briefly outline
one, known as quasi-inverses of schema mappings.
