Database Reference
In-Depth Information
counter-example. This, in turn, implies that checking whether certain answers are true is in
CO NP.
Consider a first-order logic (FO) formula equivalent to Q ,andlet k be its quantifier rank,
i.e., the depth of quantifier nesting. The k -type of a node is the set of all FO formulae of
quantifier rank k with one free variable it satisfies. It is known that there are only finitely
many nonequivalent FO formulae of any given quantifier rank. In consequence, there are
only finitely many different k -types. Since k depends only on the query, we have a fixed
number of k -types.
Now, roughly, for any pair u , v of nonwitnessing nodes with the same FO k -type, we cut
the nodes in-between and merge u , v (provided that cutting neither removes any witnessing
node nor leads to violation of the schema). Cutting this way, vertically and horizontally,
we make sure all the witnesses are not too far apart, and the resulting tree has polynomial
size. Since u and v above have the same k -type, it can be shown that after cutting, the tree
satisfies all the same FO formulae of quantifier rank k as before; in particular, the cut tree
satisfies Q iff the original tree did.
13.3 Sources of intractability
The certain answers problem easily becomes CO NP-hard. In the this section we investigate
the reasons for hardness which will help us isolate a fairly expressive tractable case, that is
further analyzed in the next section.
The reasons for hardness may come from three main sources: schemas, st-tgds, and
queries.
Hardness due to schemas
Let us first consider schemas. It can be shown that for SM dtd (
, =) there
is a dichotomy: if schemas (DTDs ) allow enough disjunction, the problem is CO NP-hard,
otherwise it is polynomial. Without giving the precise (and rather technical) characteriza-
tion of the class of mappings that gives hardness, we show how simple these mappings can
be.
To do so, we will give examples of an XML schema mapping
, =) and UCTQ(
and a Boolean query
Q such that the well-known NP-complete problem 3SAT is reducible to the complement
of CERTAIN M ( Q ), i.e., for each 3SAT instance (a propositional formula )
M
ϕ
,wehave
certain M ( Q , S ϕ ) is false iff
ϕ
is satisfiable ,
where S ϕ
described below.
Suppose we are given a 3-CNF formula
is a tree encoding of
ϕ
= i =1 j =1 c ij ,where c ij is a literal and in
each clause all three literals are different. The tree encoding, S ϕ , is best explained on a
concrete example. A formula ( x 1 ∨¬
ϕ
x 3
x 4 )
( x 2
x 3 ∨¬
x 4 ) is encoded as
Search WWH ::




Custom Search