Database Reference
In-Depth Information
and ensure that it makes the internal
true for
x
1
,
x
2
,...,
x
n
encoded in the
source tree and
y
1
,
y
2
,...,
y
n
guessed in the target tree
r
e
(
u
1
)
,
e
(
u
2
)
,...,
e
(
u
n
)
Π
2
part of
ϕ
−→
r
e
(
u
1
)
−→
→
e
(
u
1
)
,
e
(
u
2
)
→
e
(
u
2
)
,...,
e
(
u
n
)
→
e
(
u
n
)
,
e
(
v
1
)
e
(
v
n
)
,
a
1
(
x
1
,
x
1
)
,
a
2
(
x
2
,
x
2
)
,...,
a
n
(
x
n
,
x
n
)
,
b
1
(
y
1
,
y
1
)
,
b
2
(
y
2
,
y
2
)
,...,
b
n
(
y
n
,
y
n
)
,
g
(
X
1
,
Y
1
,
Z
1
)
,
g
(
X
2
,
Y
2
,
Z
2
)
,...,
g
(
X
m
,
Y
m
,
Z
m
)
→
e
(
v
1
)
,
e
(
v
2
)
→
e
(
v
2
)
,...,
e
(
v
n
)
→
(the literals
X
j
,
Y
j
,
Z
j
are taken from
).
The obtained mapping is absolutely consistent iff
ϕ
is a tautology. Indeed, if the map-
ping is absolutely consistent, in particular it has a solution for each source tree that uses
two different data values in
e
-positions. By construction, such trees have solutions iff
ϕ
ϕ
is a tautology. If the data values in
e
-positions are equal, the st-tgds are satisfied trivially.
Disjunction can be eliminated from the source schema at a cost of allowing data com-
parisons on the source side. To achieve this, replace (
a
i
|
a
i
) with
a
i
storing two attributes,
and encode the truth value as an (in)equality of the two data values.
Tractable case
In order to guarantee tractability, stronger assumptions are required.
Theorem 18.12 A
B
C
ONS
is in
P
TIME
for mappings in
SM
nr
(
,
=)
without equality on
the source side. Allowing equality on the source side makes the problem
CO
NP
-complete.
↓
Proof
Throughout the proof we assume that each variable is used in exactly one st-tgd.
Since satisfiability of
,
=-patterns with respect to a nested relational DTD can be tested
in P
TIME
, without loss of generality we can assume that all patterns in the mapping are
satisfiable: for each
↓
π
−→
π
,if
π
is not satisfiable, the st-tgd can be removed, and if
π
is
π
is not, the mapping is not absolutely consistent.
Under this assumption,
satisfiable but
{
π
i
−→
π
i
i
= 1
,
2
,...,
n
(
D
s
,
D
t
,
}
)
is absolutely consistent if and only if so is
D
s
,
D
t
,
n
.
n
i
=1
π
i
−→
i
=1
π
i
The second condition is clearly necessary. To see that it is sufficient, observe that since we
disallow alternatives in schemas and inequality, the conjunctions of patterns are satisfiable,
because each pattern is satisfiable on its own. Moreover, as equality is disallowed on the
source side, each
T
=
D
s
can be extended to
T
|
|
=
D
s
satisfying all original source side
