Database Reference
In-Depth Information
q
(
x
) ::=
ε
|
(
a
,
x
)[
q
(
x
)]
x
and
x
|
q
(
x
)
,
q
(
x
)
are subtuples of
x
(
x
,
y
)
return
q
(
x
,
y
)
|
for
π
y
is disjoint from
x
Figure 14.2 The syntax of forest queries
Definition 14.2 A
TQL
query
Q
is an expression of the form
(
a
)[
q
]
,
where
q
is a forest query without free variables. The syntax of forest queries is given in
Figure 14.2
; patterns in comprehensions are required to come from
π
∈
Π
p
(C
ONST
,
⇓
,
=).
For a tree
T
and a query
Q
=
(
a
)[
q
],wedefine
Q
(
T
) as the tree
(
a
)[
q
T
],i.e.,the
forest
q
T
under root
(
a
).
), trees (
(
a
,
x
)[
q
]), unions of forests (
q
,
q
),
Forest queries include the empty forest (
ε
F
of forests we mean the forest
obtained by putting together
F
and
F
(i.e., it may contain more than one copy of a tree).
By
(
a
)[
F
] we mean a tree obtained by attaching a common
-labeled root with values
a
on top of the forest
F
.
We next define the semantics of forest queries. Even though in the definition of
TQL
queries (i.e.,
(
a
)[
q
]) we use forest queries
q
without free variables, in general one can
have forest queries with free variables occurring as subqueries. For instance, the subquery
of query
Q
2
in
Example 14.1
on page
193
has
x
as a free variable. Hence, we need to define
semantics of forest queries with free variables too.
Specifically, if we have a forest query
q
(
x
),atree
T
, and a valuation
v
:
x
return
q
). By a union
F
∪
and comprehensions (
for
π
→
C
ONST
∪
V
AR
of free variables, we define
q
(
x
)
T
,
v
as the semantics of
q
in
T
under the valuation
v
.
This is done by the following rules:
ε
(
a
,
x
)[
q
(
x
)]
T
,
v
=
(
a
,
v
(
x
))
q
T
,
v
ε
T
,
v
=
q
(
x
)
,
q
(
x
)
q
T
,
v
∪
q
T
,
v
T
,
v
=
T
,
v
=
q
T
,
(
v
,
v
)
T
(
v
(
x
)
,
v
(
y
))
.
(
x
,
y
)
return
q
(
x
,
y
)
for
π
|
=
π
In the last rule, by (
v
,
v
) we mean a valuation that acts as
v
on
x
and as
v
on
y
.
Note that according to this semantics,
TQL
queries can be applied not only to ground
trees (i.e., trees in which all data values are constants from C
ONST
), but also to trees with
nulls, i.e., trees whose data values come from C
ONST
∪
V
AR
. This will provide an analog
of naıve evaluation of queries.
It is easy to see that data complexity of
TQL
queries is polynomial.
