Information Technology Reference
In-Depth Information
Query set:
#R: root
#X: /a
#Y: /a//*/b
#Z: /a/b/*
#W: /a/b/*/d
#R
1
#R
1
#R
a
#X
*
2
#X
2,3,6
#X
3
6
b
3,4,7
*
4
7
3,4
#Y,Z
*
#Y
#Z
3,4,8,9
b
8
#Z
3,4,5,8,9
5
#Y
#Z
3,4,5
9
3,4,10
#W
d
#Y
#U
10
#U
FIGURE 9.9
DFA for XPath query evaluation.
The SPEX system progressively matches all the elements with query one
by one, to form the output query result [35]. The SPEX system will evaluate
the predicates during the matching of the incoming elements. As shown in
Figure 9.12
, the query node (b) can be visited several times and a data node
(a) can be visited once at most by a query node. In addition to the above
techniques, there are several important theoretic bounds that should be
introduced after some modii cation for the scientii c workl ow.
9.3.3.3
Theoretic Lower Bounds for Scientifi c Workfl ow Scheduling
As an important standard for the system consumption and expense, the
lower-bounds problem is critical. It is also a measurement for us to conceive
(a) Xpath queries
(b) A corresponding NFA
{Q1}
{Q3, Q8}
c
Q1=/a/b
Q2=/a/c
Q3=/a/b/c
Q4=/a/b/c
Q5=/a/*/c
Q6=/a//c
Q7=/a/*/*/c
Q8=/a/b/c
b
{Q2}
a
c
ε
*
c
{Q4}
b
c
{Q6}
*
{Q5}
c
c
*
{Q7}
FIGURE 9.10
Transforming queries into NFA.
Search WWH ::
Custom Search