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
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.  Search WWH ::

Custom Search