A Data Stream View of Scientific Workflow - Grid Computing: Infrastructure, Service, and Applications - page 237

1: <a>
2: <b>
3: <e>
4: </e>
5: <c>
6: </c>
7: </b>
8: <b>

9: <e>
10: </e>
11: </b>
12: <b>
13: <e>
14: </e>
15: </b>
16: </a>

a

b b b

P

e c e e

FIGURE 9.13 Concurrency of D with respect to Q = a [ p ]/ b [ c ]/ e .

As shown in Figure 9.13, document D is represented as a stream of 16
events called time steps. The concurrency of the document D with respect
to query Q at step t Π[1, m ] is the number of content-distinct nodes in D
that are alive at step t . As shown in Figure 9.13, let Q = a [ p ]/ b [ c ]/ e . At Step
14, two e elements are alive. The i rst is at Step 3 because whether it will be
selected depends on whether its a grandparent will have a p child. The
second is at Step 13, because whether it will be selected depends on
whether its b parent will have a c child and its a grandparent will have a p
child. So the concurrency at Step 14 is 2. The document concurrency of D
with respect to Q , denoted as CONCUR(D,Q), is the maximum concur-
rency over all steps t [1, m ]. For example, CONCUR(D,Q) in Figure 9.13

is 2. The concurrency lower bound is suitable for single-variable predicate
queries. For queries with a multi-variable predicate, the dominance lower
bound is dei ned in [29]. It is simple to verify that if Q is a nonpredicate
query, CONCUR(D,Q) is 1. However, for queries with single predicate, it is
easy to construct documents with arbitrarily large concurrency.

∈

9.3.3.3.2
A predicate that consists of a comparison of two nodes (e.g., a = b or a > b )
is said to be a multivariate comparison predicate [29,30]. On the other
hand, univariate comparison predicates are ones that compare a node
with a constant (e.g., a = 5 or b > 4). It has been proved that evaluation
(whether fully l edged or i ltering) of queries that consist of multivariate
comparison predicates may require substantially more space than evalua-
tion of queries that have only univariate comparison predicates.
The existing semantics of XPath implies that a predicate of the form
/ c [ R ( a , b )], where R is any comparison operator (e.g., =, >), is satisi ed if and
only if the document has a c node with at least one a child with a value x
and one b child with a value y , so that R ( x ; y ) = true. Thus, if all the a
children of the c node precede its b children, the evaluation algorithm may
need to buffer the (distinct) values of the a children, until reaching the i rst
b child. It is proved that such a buffering is indeed necessary when R is
an equality operator (i.e., =, !=). It is not needed for inequality operators

Multivariate Comparison Predicates