Database Reference
In-Depth Information
This includes mappings using patterns starting at the root, that do not use descendants, nor
child-paths of length greater than
d
.
We next show that A
B
C
ONS
is
p
4
-hard even for schema mappings of depth 1.
Π
p
4
-hard for bounded-depth mappings, even for depth 1
Theorem 18.11 A
B
C
ONS
is
Π
mappings from
SM
dtd
(
↓
,
→
,
=)
.
Proof
We provide a reduction from T
AUTOLOGY
for
Π
4
quantified propositional formu-
lae. Let
ϕ
=
∀
x
1
,
x
2
,...,
x
n
∃
y
1
,
y
2
,...,
y
n
m
∀
u
1
,
u
2
,...,
u
n
∃
v
1
,
v
2
,...,
v
n
X
i
∨
Y
i
∨
Z
i
i
=1
x
j
,
y
j
,
u
j
,
v
j
,
x
j
,
y
j
,
u
j
,
v
j
j
= 1
,...,
n
with
X
i
,
Y
i
,
Z
i
∈{
}
. Let the source schema be given by
(
a
1
|
a
1
)(
a
2
|
a
2
)
...
(
a
n
|
a
n
)
ee
,
where
e
has a single attribute, and the target schema by
r
→
eeea
1
a
2
...
a
n
b
1
b
2
...
b
n
g
7
,
r
→
where
e
has a single attribute,
a
i
and
b
j
have two attributes, and
g
has three attributes. The
source tree encodes a valuation of
x
1
,
x
2
,...,
x
n
,
a
i
means that
x
i
is
true
,
a
i
means it is
false
.
In
e
-positions we store values representing
true
and
false
. On the target side, we want to
keep a copy of the valuation of
x
i
'sandaguessedvaluationof
y
i
's, except this time we use
a different coding. The first attribute of the label
a
i
stores the value of
x
i
,
true
or
false
,and
the second attribute stores the value of the negation of
x
i
. Similarly,
b
i
's store values of
y
i
.
We also want in the target word two copies of
true
and a copy of
false
arranged so as to
enable a nondeterministic choice between a pair (
true
,
false
)or(
false
,
true
), as well as all
triples with at least one entry
true
,storedin
g
-nodes, which will help us to check that each
clause of ϕ is satisfied.
Let us now describe the st-tgds. First we make sure that values representing
true
and
false
are copied properly,
r
e
(
x
)
e
(
x
)
,
for each
i
translate the
a
i
/
a
i
coding of values of
x
i
into true/false coding,
r
a
i
,
e
(
t
)
e
(
y
)
−→
r
e
(
x
)
→
→
→
e
(
y
)
e
(
f
)
−→
→
r
/
a
i
(
t
,
f
)
,
r
a
i
,
e
(
t
)
e
(
f
)
−→
→
r
/
a
i
(
f
,
t
)
,
and enforce in the target tree all triples with at least one entry
true
,
r
e
(
t
)
→
e
(
f
)
−→
r
g
(
f
,
f
,
t
)
,
g
(
f
,
t
,
f
)
,...,
g
(
t
,
t
,
t
)
.
Next, we guess a value of
y
i
for each
i
,
r
e
(
x
)
e
(
y
)
,
b
i
(
x
,
y
)
,
r
−→
→
