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.
