Database Reference
In-Depth Information
However, if a query is both hierarchical and non-repeating, then it is safe.
Definition 4.26
A query expression given by
Eq. (2.1)
is called
non-repeating
if every relation
symbol occurs at most once. A query is called non-repeating if it is equivalent to a non-repeating
expression. We denote
NR
the class of non-repeating queries in the language
; in particular,
RC
NR
L
L
is the class of non-repeating relational queries.
An expression is called
hierarchical-non-repeating
if it is both hierarchical and non-repeating,
and a query is called hierarchical-non-repeating if it is equivalent to such an expression. We denote
L
H,NR
the class of hierarchical-non-repeating queries.
RC
H,NR
is
R
6
-safe. In particular, Q is tractable.
Proposition 4.27
Every query Q
∈
Proof.
By induction on the structure of the non-repeating, hierarchical expression. If
Q
=
Q
1
∧
Q
2
then
Q
1
and
Q
2
are syntactically independent (because
Q
is non-repeating), similarly for
Q
=
x.Q
,
then
x
is a root variable, and, since no relational symbol is repeated,
x
is also a separator variable;
hence, we can apply an independent project. Finally, if
Q
Q
1
∨
Q
2
. In these cases, we apply an independent join or an independent union. If
Q
=∃
Q
, then we apply the negation.
=¬
One needs to use care when applying
Proposition 4.27
because the class
RC
H,NR
is
not
the same as
RC
H
RC
NR
.Tobein
RC
H,NR
, a query must be given by an expression that is
both
hierarchical and non-repeating, and this corresponds to a strictly smaller class of queries than
RC
H
∩
RC
NR
. For example, consider the query
H
1
=
∩
R(x
0
), S(x
0
,y
0
)
∨
S(x
1
,y
1
), T (y
1
)
, which
clearly is a hierarchical query. It can also be written as
∃
x.
∃
y.(S(x, y)
∧
(R(x)
∨
T (y)))
, which is a
RC
NR
, but
H
1
cannot be written as an expression
that is both hierarchical and non-repeating, so it is not in
RC
H,NR
.
RC
H
non-repeating expression. Hence,
H
1
∈
∩
4.1.6.3 Conjunctive Queries Without Self-Joins
A non-repeating conjunctive query is called a
conjunctive querywithout self-joins
.Thus,
CQ
NR
denotes
the set of conjunctive queries without self-joins. We show that, when restricted to this class, the
converse to
Proposition 4.27
also holds. In other words, a conjunctive query without self-joins is
safe if and only if it is hierarchical.
We start by giving a simple criteria for a conjunctive query to be hierarchical. Let
Q
be a
conjunctive query expression, and let
L
1
,L
2
,...,L
k
be its atoms. For each variable
x
, denote
at (x)
the set of atoms
L
i
that contain
x
.If
Q
is hierarchical, then the following condition holds:
Hierarchy Condition
For any two variables
x,y
, either
at (x)
∩
at (y)
=∅
,or
at (x)
⊆
at (y)
,or
at (x)
⊇
at (y)
.
