Database Reference

In-Depth Information

Q
=

=
z
) with respect to
S
is
true
, since every universal solution
T

for
S
must contain a fact of the form
P
(
a
,
b
,

∃

x

∃

y

∃

z
(
P
(
x
,
y
,
z
)

∧

x

⊥

),where

⊥

is a value in V
AR
. On the other

hand,
certain
M
(
Q
,
S
)=
false
since
T
=

{

P
(
a
,
b
,
a
)

}

is a solution for
S
. Notice that
T
is

not a universal solution for
S
.

Query answering under universal solutions semantics

Recall from
Theorem 7.2
that certain answers for unions of conjunctive queries can be

computed in polynomial time, if the set of target dependencies consists of a set of egds and

a weakly acyclic set of tgds.
Proposition 8.2
then says that the same is true for universal

certain answers. But what can we say about universal certain answers for more expressive

relational calculus queries?

First of all, for all of relational calculus, the problem of computing universal certain

answers of FO queries is still undecidable, just as the problem of computing the usual

certain answers. Indeed, we can just mimic the proof of
Proposition 7.1
that shows the

result for the usual certain answers. In that proof we constructed, from each relational

mapping

M
without target dependencies and an FO query
Q

such that for every source instance
S
the following holds:

M

, a relational mapping

certain
M
(
Q
,
S
)=
false

⇐⇒

S
has a solution under

M

.

Using exactly the same construction we can prove that for every source instance
S
,we

have:

certain
u

M
(
Q
,
S
)=
false
⇐⇒
S
has a
universal
solution under
M
.

Now using
Theorem 6.5
which says that there exists a relational mapping for which the

problem of checking for the existence of universal solutions is undecidable, we obtain the

following:

Proposition 8.4

There exists a Boolean
FO
query Q over
R
t
and a mapping

M

=

(R
s
,
R
t
,

Σ
st
)
, such that the following problem is undecidable: Given a source instance S, is

certain
u

M

(
Q
,
S
)=
true
?

Summing up, so far we know the following with respect to the complexity of the problem

of computing universal certain answers of relational calculus queries:

•

For unions of conjunctive queries it is
tractable
, since in this case universal certain

answers coincide with the usual certain answers.

•

For FO queries, it is
undecidable
, since the problem can be reduced to checking the

existence of universal solutions.

But, of course, there is a wide range of interesting classes of relational calculus queries

between these two extremes. We now demonstrate that some of these classes lead to ef-

ficient query answering algorithms under the universal certain answers semantics, which

will be in sharp contrast with the case of the standard certain answers semantics.