![](https://csdnimg.cn/release/download_crawler_static/15825366/bg5.jpg)
Optimal and efficient generalized twig pattern processing
A generalized tree pattern (GTP) is an extension of TPQ,
which enables expressing the XQuery semantics more accu-
rately [10]. Edges of GTP can be mandatory and optional and
they are denoted by solid and dashed lines in a tree, respec-
tively. A mandatory edge connects a subexpression corre-
sponding to the FOR and WHERE clauses with the rest of
the query. An optional edge connects a subexpression corre-
sponding to the LET and RETURN clauses with the rest of
the query. The GTP model contains two types of output query
nodes: (1) identifying output query nodes, and (2) optional
output query nodes. A GTP query node is an identifying
query node if it corresponds to the last query node in the FOR
path expression. The nodes corresponding to the identifying
query nodes form a so-called GTP result tuple identifier.An
output of an XQuery query contains only result tuples with
unique result tuple identifiers. In other words, query matches
with the same identifier are represented by one GTP result
tuple. An output query node is optional if it corresponds to
the last query node of the LET or RETURN path expression.
Optional nodes are grouped together for every GTP result
tuple identifier; therefore, optional nodes of query matches
corresponding to the same tuple identifier are stored in one
GTP result tuple. GTP enables to model logical expressions
in a query. Any query node having more than one child has a
corresponding logical expression. The AND logical operator
is an implicit connector for the twig query branches; there-
fore, we explicitly write only expressions with the NOT and
OR operators as in the case of #b in the GTP Q3 in Fig. 1c.
Example 2 Consider the GTP Q2 in Fig. 1b and the XML
tree in Fig. 2a. The node pairs corresponding to the
identifying query nodes a and d form three result tuple
identifiers: (a
1
, d
1
), (a
1
, d
2
), and (a
1
, d
3
). We can find query
matches corresponding to one GTP result tuple identifier,
e.g., the query matches (a
1
, b
1
, b
4
, d
3
), (a
1
, b
3
, b
4
, d
3
), and
(a
1
, b
4
, b
4
, d
3
) correspond to the (a
1
, d
3
) result identifier.
These query matches form one result tuple (a
1
, d
3
, b
1
,
b
3
, b
4
). We can observe that the nodes corresponding to the
optional output query node #b are grouped together in this
result tuple. The GTP result of Q2 is a set of three tuples
since we have three tuple identifiers. On the other hand, the
TPQ result of Q2 is a set of twelve query matches.
2.3 Holistic algorithms
Holistic approaches use an abstract data type (ADT) called a
stream which is an ordered set of node labels with the same
schema node label. There are many options how to create the
schema node labels (also known as streaming schemes [9]
or partitions of data nodes [19]). A cursor pointing to the
first node label is assigned to each stream at the beginning
of a query processing. Given a stream T , let us define the
following operations:
– NodeLabel H(T )—returns the node label at the cursor’s
position,
– Bool eof(T )—returns true if the cursor is at the end of T ,
– advance(T )—moves the cursor to the next node label
in T .
Two important assumptions ensuring the linear I/O com-
plexity are that we can access only a single node from each
stream in every step of a holistic algorithm and cursors can
be only forwarded. Note that a stream ADT can be easily
implemented by an inverted list.
In the following text, we use methods x.preceding(y),
x.following(y), x.ancestor(y), and x.descendant
(y) returning true if the corresponding relationship between
the nodes x and y is satisfied. We write x < y if the node x
has a lower document order than the node y.
2.4 DataGuide search
The TwigStack algorithm [6] utilizes the Tag streaming
scheme. In [9
], the authors propose an extension of this
algorithm by using various streaming schemes and introduce
Tag+level and Prefix path streaming schemes. The Prefix
path streaming scheme is basically a utilization of labeled
paths [21,44]. For the sake of simplicity, let us use the abbre-
viation LPS for ‘Labeled path streaming scheme’ or ‘Prefix
path streaming scheme’ and T+LS instead of ‘Tag+Level
streaming scheme’. Moreover, we use the terms ‘labeled
path’ and ‘tag+level’ instead of labeled path and tag+level
scheme node labels, respectively.
The content of a stream depends on the streaming scheme
used. For example, in the case of LPS, the stream T
a/b/c
includes all nodes corresponding to the labeled path a/b/c.
Example 3 Consider the XML document in Fig. 2a. Then,
for instance, T
a/b
={b
1
, b
3
, b
4
} and T
a/b/c/c/ f
={f
1
} in
the case of LPS, T
b,2
={b
1
, b
3
, b
4
} and T
b,3
={b
2
} in the
case of T+LS.
In any algorithm using LPS or T+LS, we must first
find labeled paths and tag+levels, respectively, matching the
query in the DataGuide tree [3]. Searching for the matching
labeled paths or tag+levels is called a stream pruning in [9].
By PRU
#q
we denote a set of streams corresponding to #q.
In other words, PRU
#q
is a set of streams which can contain
nodes that are a part of a full query match.
Example 4 Consider the XML document in Fig. 2a and
the query //b[./c]//d. Under LPS, PRU
#b
={T
a/b
},
PRU
#c
={T
a/b/c
}, and PRU
#d
={T
a/b/b/d
, T
a/b/d
}.Note
that T
a/b/b
is not a part of PRU
#b
since the necessary
a/b/b/c labeled path is not in the DataGuide; therefore,
a/b/b cannot contain a fully matched node.
The isEnd(#q) function returns true if all streams from
PRU
#q
are completely read (i.e., eof(T ) returns true for
123