Database Reference
In-Depth Information
the lineage of
Q
U
is read-once, on any database instance. Indeed, denoting
Z
1
,...Z
n
the Boolean
variables associated with the
T
-tuples, the query's lineage is:
Q
U
=
(X
i
Y
ij
∨
Z
i
Y
ij
)
=
[
(X
i
∨
Z
i
)
∧
Y
ij
]
ij
ij
Example 5.17
We show two examples where the lineage is not a read-once formula. First, consider
Q
J
=
R(x
1
), S(x
1
,y
1
), T (x
2
), S(x
2
,y
2
)
; we have seen in
Example 4.7
that
P (Q)
can be evaluated
by applying a few simple rules. Its lineage is not read-once, in general, because the query cannot be
written as a hierarchical non-repeating expression
1
. We can also check directly that the lineage is not
read once. Denote
X
i
,Y
ij
,Z
i
the Boolean variables associated with the tuples
R(i),S(i,j),T(i)
of
a database instance. The lineage is:
⎛
⎝
i,j
⎞
⎛
⎝
k,l
⎞
⎠
=
i,j,k,l
⎠
∧
Q
J
=
X
i
Y
ij
Z
k
Y
k,l
X
i
Z
k
Y
ij
Y
kl
(5.11)
Assume that both
R
and
T
contain at least two elements each, say
{
1
,
2
}⊆
R
and
{
1
,
2
}⊆
T
, and
that
S
contains at least three of the four possible pairs; for example,
{
(
1
,
1
), (
1
,
2
), (
2
,
1
)
}⊆
S
. Then
the primal graph of
Q
J
is not normal: it contains the edges
(Y
11
,Y
12
), (Y
11
,Y
21
), (Y
12
,Y
21
)
, but
there is no conjunction containing
Y
11
Y
12
Y
21
.
Finally, consider the query
Q
V
, discussed in
Example 4.8
. Its lineage is not a read-once either
because the primal graph contains the edges
(S(
1
,
1
), T (
1
))
,
(T (
1
), R(
2
))
,
(R(
2
), S(
2
,
2
))
, but no
other edges between these four nodes; hence, the induced subgraph is
P
4
.
We end the discussion on queries with read-once lineage expressions by poiting out an im-
portant distinction between CQ and UCQ. For CQ, we have seen in
Theorem 4.29
that if a query
is hierarchical and also non-repeating, then it is simultaneously hierarchical and non-repeating, and,
moreover that these queries are precisely the tractable queries:
CQ
H,NR
CQ
NR
(P )
=
CQ
H
CQ
NR
=
∩
For UCQ queries, however, this property fails. The tractable non-repeating queries,
UCQ
NR
(P )
, lie
strictly between the two classes:
UCQ
H,NR
UCQ
NR
(P )
UCQ
H
UCQ
NR
∩
1
This can be verified by exhaustively trying all unions of conjunctive queries that use each of the relation symbols
R
,
S
,
T
exactly
once.
