Database Reference
In-Depth Information
Tractable query answering within relational algebra
We now give an example of moderately good behavior within relational algebra: we show
that for some relational algebra queries, certain answers
certain
M
(
Q
,
S
) can be computed
efficiently, but not by naıve evaluation; in fact, not even by any query that itself is express-
ible in relational algebra.
Recall that a
conjunctive query with negated atoms
is an FO formula of the form
∃
x
α
(
x
,
y
),where
α
(
x
,
y
) is a conjunction of atoms and negated atoms (that is, inequali-
ties of the form
x
R
(
x
)). Again, as a safety
condition we impose the constraint that each variable that appears in the query appears in
at least one nonnegated atom.
=
y
or negated relational atoms of the form
¬
Theorem 7.5
Σ
st
)
without target dependencies
and a union of conjunctive queries with negated atoms Q such that:
There is a
L
AV
mapping
M
=(R
s
,
R
t
,
1. certain
M
(
Q
,
S
)
can be computed in polynomial time; and
2. there is no relational algebra query Q
such that Q
(
T
)=
certain
M
(
Q
,
S
)
,whereT is
the canonical universal solution.
In particular, in this case
certain
M
(
Q
,
S
) cannot be computed by naıve evaluation on the
canonical solution.
Proof
Consider the L
AV
mapping
Σ
st
) such that R
s
consists of a binary re-
lation
E
and unary relations
A
and
B
, R
t
consists of a binary relation
G
and unary relations
P
and
R
,and
M
=(R
s
,
R
t
,
Σ
st
consists of the following st-tgds:
E
(
x
,
y
)
→
G
(
x
,
y
)
A
(
x
)
→
P
(
x
)
B
(
x
)
→
R
(
x
)
.
Notice that if
S
is a source instance, then the canonical universal solution
T
for
S
is such
that
E
S
=
G
T
,
A
S
=
P
T
and
B
S
=
R
T
.
Let
Q
be the following query over R
t
:
∃
x
∃
y
(
P
(
x
)
∧
R
(
y
)
∧
G
(
x
,
y
))
∨∃
x
∃
y
∃
z
(
G
(
x
,
z
)
∧
G
(
z
,
y
)
∧¬
G
(
x
,
y
))
.
This is a union of conjunctive queries with a single negated relational atom and no inequal-
ities. It is also a Boolean query. We show next that for every source instance
S
, the certain
answers
certain
M
(
Q
,
S
) are true if and only if there exist elements
a
,
b
in D
OM
(
T
) such
that
a
belongs to
P
T
,
b
belongs to
R
T
and (
a
,
b
) belongs to the transitive closure of the re-
lation
G
T
. Or equivalently,
certain
M
(
Q
,
S
)=
true
if and only if there exist elements
a
,
b
in D
OM
(
S
) such that
a
belongs to
A
S
,
b
belongs to
B
S
and (
a
,
b
) belongs to the transitive
closure of the relation
E
S
.
Assume first that there exist elements
a
,
b
in D
OM
(
T
) such that
a
belongs to
P
T
,
b
belongs to
R
T
and (
a
,
b
) belongs to the transitive closure of the relation
G
T
.Let
T
1
be an
arbitrary solution of
S
. We prove that
Q
holds in
T
1
, and hence that
certain
M
(
Q
,
S
)=
true
.
