Database Reference

In-Depth Information

Recall from
Theorem 7.4
that computing certain answers to conjunctive queries with

inequalities is an intractable problem. But
Example 8.3
above showed that for this class

of queries, the usual certain answers need not coincide with the universal certain answers.

This suggests that it may still be possible to compute universal certain answers for conjunc-

tive queries with inequalities in polynomial time. We will actually state a much stronger

result in
Theorem 8.5
: under the universal certain answers semantics, we have tractabil-

ity of query answering for a big and practically relevant class of FO queries that extends

unions of conjunctive queries.

Roughly, an
existential
FO query is given by an FO formula of the form

∃

y

ϕ

(
x
,
y
),where

ϕ

(
x
,
y
) is a quantifier-free formula in disjunctive normal form satisfying a safety condition.

More precisely, it is given by a formula of the form

y

i

j
α
ij
,

ψ

(
x
)=

∃

where

•

each

α
ij
is either an atomic formula, or the negation of an atomic formula;

•

the free variables of each

α
ij
come from
x
,
y
;and

•

(safety condition) if

α
ij
is a negated atom, i.e., of the form

¬

R
(
z
), then each variable in

z
must occur in some formula

α
ij
which is a nonnegated atom.

For example, both unions of conjunctive queries, and unions of conjunctive queries with

inequalities and negated atoms satisfy these three conditions.

Existential formulae ψ are known to be monotone in the following sense. If
I
is an

induced sub-instance
of
I
and
t
belongs to the evaluation of

over
I
,then
t
belongs to the

ψ

over
I
. Recall that an induced sub-instance
I
of an instance
I
is given by a

evaluation of

ψ

set
A
⊆

D
OM
(
I
); it contains exactly all the tuples of
I
whose elements come from
A
.

Since every universal solution contains a copy of the core as an induced sub-instance,

we conclude that the problem of computing the universal certain answers for an existential

FO query

over the core of the universal solutions, discarding

all tuples that contain nulls. Thus, in order to compute the universal certain answers of an

existential
Q
with respect to a source instance
S
, one can use the following procedure.

ψ

boils down to evaluating

ψ

Recall from
Theorem 6.18
that the core of the universal solutions can be computed in

polynomial time for every mapping whose sets of target dependencies consists of a set of

egds and a weakly acyclic set of tgds. Furthermore, existential queries are FO queries and

thus have polynomial time data complexity. Putting these two things together we obtain

the following positive result.

Theorem 8.5

Σ
t
consists of

a set of egds and a weakly acyclic set of tgds, and let Q be an existential query over
R
t
.

Then the algorithm
C
OMPUTE
U
NIVERSAL
C
ERTAIN
A
NSWERS
(Q,

Let

M

=(R
s
,
R
t
,

Σ
st
,

Σ
t
)
be a relational mapping such that

M

) correctly computes

universal certain answers of Q with respect to a source S under

M

in polynomial time.