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.