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

Start

End

FIGURE 9.8 Sample segmentation of workl ow schema.

9.3.3.2 Automata for XML Streams and Scientifi c Workfl ow

To process the tree structure or schema, under the XML schema, the most
popular technique is automata theory. For query processing over XML
data streams or a workl ow schema after the tree-like separation as men-
tioned previously, lots of i nite-state machines (FSMs) or automata-based
i ltering algorithms [19,28,32,33] can be introduced. FSMs are a natural
and effective way of representing and processing path expressions. Ele-
ments of a path expression are mapped to states. A transition from an
active state is i red when an element is found in the document that matches
that transition. If an accepting state is reached, then the document is said
to satisfy the query. For example, XFilter [19] has focused on the efi cient
evaluation of path expressions over streaming XML data, using indexed
FSMs to allow many structure-based queries to be processed simultane-
ously. However, XFilter makes no attempt to eliminate redundant process-
ing for similar queries. Figure 9.9 shows the DFA-based techniques for
processing multiple queries. The query trees are i nally transformed into
some dei nite states for processing.
YFilter [22,34] combines multiple queries into a single NFA. The use of a
combined NFA allows a dramatic reduction in the number of states needed
to represent the set of user queries and greatly improves i ltering perfor-
mance by sharing execution work. YFilter also extends this NFA model to
efi ciently handle predicates within path expressions. Figure 9.10 shows
that a set of queries (a) has been transformed into an NFA (b) for query
evaluation. The NFA will then be indexed as shown in Figure 9.11 , which
is used to match the elements from the incoming stream [22,34].