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.   Search WWH ::

Custom Search