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

(i.e., <, <=, >, >=), because for them it sufi ce to buffer just the maximum or
minimum value of the a children.
The lower bound is in fact stated with respect to any relational operator
R , not just comparisons. The bound is given in terms of a graph-theoretic
property of relations, which is called the “dominance cardinality.” So this
type of lower bound is named dominance lower bound.

Theorem 1. For the query Q = / c [ R ( a , b )], for every integer k , and for
every i ltering algorithm A for Q on XML streams, there exists a docu-
ment D of candidate cardinality k with respect to u on which A uses Ω (log

DOM k ( R )) bits of space.

The proof of Theorem 1 can be referred to in [20]. Theorem 1 clarii es the
minimum space consumption clearly for any query with several predicates
belonging to the same query node. Note that for the equality operators
(=, !=), the above lower bound is (log(| U |)) for sufi ciently

small k 's. That means that if R is an equality operator, evaluation of Q on
documents that have a node with k children matching u a (or u b ) would
require buffering the distinct data values of these children. In addition,
when R is an inequality operator (<, <=, >, >=), evaluation of Q requires only
Ω

Ω (log( U / k )) = Ω

(log|U|) bits of space, which is what is needed to buffer the maximum or
minimum data value of the k children that match u a (or u b ). The detailed
dei nitions and proof of two space lower bounds can be found in [33,37].
In traditional workl ow modeling, most attention has been paid to the
dei nition of the activities. However, considering the scientii c workl ow
requirements of data and computation intensity, we should focus on the
calculation to coordinate different activities such as synchronization,
parallelisation, and so on.
Considering the scientii c workl ow environments, we remove the
concepts of predicate, and keep the previous concepts such as “ live ” to
dei ne the activated activities. Similarly, we can get the concept for the con-
currency activity and the dominance activity. Using the upper lower
bounds, we can get the minimum expense required to execute a given sci-
entii c workl ow schema.

9.4 Scientific Workflow Runtime Scheduling

and XML Stream Optimization
In this section, the comparison of DSMS and DSWMS is given to explore
the similarity between them. At a conceptual level, query processing can
also be treated as a workl ow application, so the results of DSMS research
w i l l cer t a i n ly e n r ic h t he re s ea rc h of DSW MS. O ne of t hem i s “ optimization, ”
which is indispensable in terms of any DSMS.