Database Reference
In-Depth Information
interpretation of nulls. These are defined as
certain
(
Q
,
S
)=
{
Q
(
S
)
|
S
∈
Rep
(
S
)
}
.
Recall that when
Q
is a Boolean (
true
/
false
) query, we associate
true
with the set
containing the empty tuple, and
false
with the empty set. Then the above definition says
that for a Boolean query,
certain
(
Q
,
S
) is true iff
Q
is true in every
S
from
Rep
(
S
).
The problem of computing certain answers is not solvable algorithmically for all FO
queries. However, it is solvable efficiently (essentially, with the standard query evaluation
techniques) for unions of conjunctive queries. This is done by
naıve evaluation
,definedas
follows.
If we have a query
Q
and a database instance
S
with nulls, define
Q
naıve
(
S
) as the result
of a two-step process:
⊥
or
1. first, evaluate
Q
as if nulls were values (e.g.,
⊥
=
⊥
is true but
⊥
=
⊥
=
c
for a
constant
c
are false); and
2. second, eliminate tuples containing nulls from the result.
As an example, consider the instance below:
⊥
1
⊥
U
2
:
⊥
4
U
1
:
⊥
⊥
56
2
and the query
v
U
1
(
x
,
v
)
U
2
(
v
,
y
,
z
)
.
Q
(
x
,
y
,
z
)=
∃
∧
The first step of evaluating
Q
naıvely results in a table
⊥
14
256
⊥
) is eliminated, as it contains a null. The end result has
In the second step, the tuple (1
,
4
,
one tuple, (2,5,6).
For general queries, naıve evaluation need not coincide with certain answers. However,
if
Q
is a conjunctive query, or a union of conjunctive queries, then
certain
(
Q
,
S
)=
Q
naıve
(
S
)
.
This result is essentially optimal, as every larger subclass of relational calculus will contain
a query for which naıve evaluation will fail to compute certain answers.
