Database Reference
In-Depth Information
5. INTENSIONAL QUERY EVALUATION
We have already shown at the end of
Subsubsection 4.1.6.2
that
H
1
∈
UCQ
NR
, yet it is
clearly not in
UCQ
NR
(P )
, which proves that the latter two classes are separated. The former two
classes are separated by the query:
UCQ
H
∩
Q
=∃
F(y)
]
=∃
x
1
.
∃
y
1
.A(x
1
), B(x
1
), C(y
1
), F (y
1
)
∨∃
x
2
.
∃
y
2
.A(x
2
), D(x
2
), E(y
2
), F (y
2
)
x.
∃
y.
[
A(x)
∧
((B(x)
∧
C(y))
∨
(D(x)
∧
E(y)))
∧
The expression on the first line is non-repeating; hence, the query is in
UCQ
NR
, and the query is also
tractable: in fact, one can check that
any
UCQ query over a unary vocabulary is
R
6
-safe and, hence,
tractable. On the other hand, this query is not in
UCQ
H,NR
because its lineage is not read-once:
over an active domain of size
≥
2 the primal graph of the lineage contains the following edges (this
is best seen on the second line above)
(B(
1
), F (
1
))
,
(F (
1
), A(
2
))
,
(A(
2
), E(
2
))
. This induces the
graph
P
4
because there are no edges
(B(
1
), A(
2
))
,
(B(
1
), E(
2
))
,or
(F (
1
), E(
2
))
.
5.4.2.2
UCQ(OBDD)
This class, too, admits a simple syntactic characterization. Let
Q
be a query expression, and assume
that, for every atom
R(v
1
,v
2
,...)
, the terms
v
1
,v
2
,...
are distinct variables: that is, there are no
constants, and every variable occurs at most once. This can be ensured by ranking all attribute-
constant, and all attribute-attribute pairs, see the ranking rules in
Subsection 4.1.2
. For every atom
L(x
1
,x
2
,...,x
k
)
let
π
L
be the permutation on
representing the nesting order of the quantifiers
for
x
1
,...,x
k
. That is, the existential quantifiers are introduced in the order
[
k
]
∃
x
π(
1
)
.
∃
x
π(
2
)
...
For
∃
x
2
...
∃
x
3
...
∃
x
1
.R(x
1
,x
2
,x
3
)...
then
π
R(x
1
,x
2
,x
3
)
example, if the expression is
=
(
2
,
3
,
1
)
.
Definition 5.18
A UCQ query expression
Q
is
inversion-free
if it is hierarchical and for any two
unifiable atoms
L
1
,L
2
, the following holds:
π
L
1
π
L
2
. A query is called
inversion-free
if it is
=
equivalent to an inversion free expression.
One can check
2
that
Q
is inversion free iff its minimal representation as a union of con-
junctive queries is inversion free. For example, the query
Q
J
=
R(x
1
), S(x
1
,y
1
), T (x
2
), S(x
2
,y
2
)
(
Example 4.7
) is inversion-free because it can be written as
Q
J
=∃
x
1
.(R(x
1
),
∃
y
1
.S(x
1
,y
1
))
∧
∃
x
2
.(T (x
2
),
∃
y
2
.S(x
2
,y
2
))
, and the variables in both
S
-atoms are introduced in the same order.
On the other hand, the query
Q
V
=
R(x
1
), S(x
1
,y
1
)
∨
S(x
2
,y
2
), T (y
2
)
∨
R(x
3
), T (y
3
)
(defined
in
Example 4.8
) has an inversion: in the hierarchical expression, the variables in
S(x
1
,y
1
)
are intro-
duced in the order
∃
y
2
.
∃
x
2
.
The connection between inversion-free queries and safety is the following. If a query
Q
is
inversion free, then it is
R
6
-safe. Indeed, write
Q
as a union of conjunctive queries
Q
1
∨
Q
2
∨
...
If at least one of
Q
i
is disconnected,
Q
i
=
∃
x
1
.
∃
y
1
while in
S(x
2
,y
2
)
they are introduced in the order
Q
i
∧
Q
i
, then apply the distributivity law to write
Q
=
Q
∧
Q
(where
Q
=
Q
1
∨
...
∨
Q
i
∨
...
and
Q
=
Q
1
∨
...
∨
Q
i
∨
...
), then use the
2
If a query expression is inversion free, then, if we rewrite it as a union of conjunctive queries
Q
1
∨
Q
2
∨
...
by repeatedly apply
the distributivity law, the expression remains inversion free. Moreover, by minimizing the latter expression, it continues to be
inversion free.
