P ROBLEM :
( Q )
I NPUT :
Source tree S , tuple s .
Q UESTION :
certain M ( Q , S ) ?
In what follows we investigate how the complexity of this problem depends on the fea-
tures allowed in schemas, st-tgds and queries.
13.2 An upper bound
We have seen that in the relational case the certain answers problem for CQs with inequal-
ities is in CO NP. In the XML setting this is no longer the case: the problem can be un-
decidable for some mappings and queries. This happens either with mappings and queries
permitting downward navigation, or child/next-sibling navigation, as long as inequalities
are allowed in queries. Specifically, the following is true.
+ , or the child and next-sibling
Proposition 13.2 Let
include either downward axes
. Then there exist a mapping
) and a query Q
that CERTAIN M ( Q ) is undecidable.
As soon as we forbid inequalities in queries, we get the CO NP upper bound back, but
the proof is more involved. Below, we only give a sketch of the main ideas.
Theorem 13.3 For every schema mapping M from SM(
) and every query Q from
, =) , the problem CERTAIN M ( Q ) is in CO NP .
Proof idea Take a query Q
), an XML schema mapping
S s ,
S t ,
Σ st ), and a source tree S conforming to
S s . Without loss of generality we can
assume that Q is a Boolean query.
A tree conforming to the target schema is a solution for S iff it satisfies every pattern
from the following set:
( a , z ) ϕ
( a , b )
Δ S ,M =
( x , y )
( x , z )
∈ Σ st and S
Note that for a fixed mapping the set
Δ S ,M can be computed in P TIME .
The certain answer to Q is false iff there exists a counter-example tree T such that
S t ,
Δ S ,M ,and
= Q .
Assume that there exists such a counter-example T . Fix a set of nodes witnessing
Δ S ,M .
Observe that since Q does not use
=, we can assume that all the nonwitnessing nodes store
unique data values. Under this assumption, we will show that we can trim most of the non-
witnessing nodes without satisfying Q , or violating
S t ,sothat T becomes of polynomial
size. This gives an NP algorithm for checking whether certain answers are false: simply
guess a tree T of polynomial size, and check if it satisfies the three conditions of being a