Database Reference

In-Depth Information

patterns. Every solution for
T
with respect to the modified mapping is a solution for
T

with respect to the original mapping, and the claim follows.

By
Lemma 13.14
, we replace

n

n

i
=1
π
i
−→

i
=1
π
i

by

n

n

i
=1
π
i

i
=1
π
i

mrg
D
s

−→

mrg
D
t

π
(
x
,
z
) with equalities possibly on both sides, such

and get a single st-tgd

π

(
x
,
y
)

−→ ∃

z

π
admit injective realizations.

that

π

and

induced by equalities. We say that

x
i
is
unbounded on the source side
whenever for all variables

Let

≈
s
be the equivalence relation on variables in

π

ξ
≈
s
x
i
, on each path from

there exist two subsequent labels
,
such that

occurs in the production for
in
D
s
as
∗
or
+
. The relation

an occurrence of

ξ

in

π

to the root of

π

≈
t
and
unboundedness on

the target side
are defined analogously.

The mapping is absolutely consistent if and only if each
x
i
unbounded on the source side

is also unbounded on the target side and
x
i
≈
t
x
j
implies
x
i
≈
s
x
j
for all
i
,
j
(both conditions

in P
TIME
). This follows from two simple observations: an injective realization of

π

can easily guarantee that two variables get the same data value only if they are in the

corresponding relation,

π

or

≈
s
or

≈
t
;and
x
i
is unbounded if and only if it admits more then

one value in some tree.

If equalities are allowed on the source side, first universally guess a subset of st-tgds

whose source side patterns are to be satisfiable in a single tree, and then proceed like above.

To show hardness, we reduce SAT to the complement of A
B
C
ONS
. Fix a CNF formula

C
1
∧

C
2
∧···∧

C
n
over

{

z
1
,
z
2
,...,
z
m
}

. Let the source and target DTDs be
r

→

z
1
z
2
...
z
m
ft

and
r

→

C
0
C
1
...
C
n
where all labels except
r
store a single attribute. Let

Σ
st
contain the

st-tgds

r
/
t
(
x
)

−→

r
/
C
0
(
x
)
,

r
/
f
(
x
)

−→

r
/
C
n
(
x
)
,

r
[
z
k
(
x
)
,
t
(
x
)]

−→
r
[
C
i
(
y
)
,
C
i
−
1
(
y
)]

for all
C
i
containing
z
k
,

r
[
z
k
(
x
)
,
f
(
x
)]

−→
r
[
C
i
(
y
)
,
C
i
−
1
(
y
)]

for all
C
i
containing

¬
z
k
.

If a valuation
z
i
=
b
i
satisfies each clause,
r
[
z
1
(
b
1
)
,
z
2
(
b
2
)
,...,
z
m
(
b
m
)
,
f
(0)
,
t
(1)]

has no solution. For the converse implication, observe that if some

r
[
z
1
(
b
1
)
,
z
2
(
b
2
)
,...,
z
m
(
b
m
)
,
f
(
b
f
)
,
t
(
b
t
)] has no solution, then it must hold that
b
f

=
b
t

but the st-tgds enforce equality. Examining the st-tgds whose source side patterns were

satisfied we get a partial valuation of
z
i
making the formula true. The remaining variables

can be evaluated arbitrarily.