From: L. Yan (lanti@u.washington.edu)
Date: Wed May 05 2004 - 01:38:16 PDT
This paper describes processing XML documents with DFA. DFA
is very efficient but the size is a major concern. In
principle it could grow as the exponential of number of
XPath expressions.The occurrence of multiple *'s and //'s
are both causes to the exponential growth. But the lazy
DFA, constructed dynamically during query execution, seems
to offer a good solution in pracitice, with bounded size in
theory and a modest size in practical XML data, while keep a
steady procssing rate after the warm-up stage. The warm-up
stage is required to construct DFA states and
transitions. The most striking conclusion is probably
Theorem 3, which gives an upper bound on the number of DFA
states, although a bit loose, given a simple graph schema,
that the number does not depend on number of XPath
expressions, but on the depth of it. This is a significant
gain comparing with the eager DFA, the number of states of
which grows exponentially with number of XPath expressions.
One thing I am not sure is how to do unfolding (with a
footnote 11 on page 9).
In the experimental part, thex data presented here is really
impressive, but the graphs are a bit hard to read.
- Li
This is Unix
explanatory error messages are seen as a sign of
weakness ...
This archive was generated by hypermail 2.1.6 : Wed May 05 2004 - 08:12:48 PDT