Semistructured data usually is modeled as labeled directed graphs, and query languages are based on declarative path expressions that specify traversals through the graphs. Regular (or generalized) path expressions use regular expression operators to specify traversal patterns. Regular path expressions typically are evaluated at run-time by exploring the database graph. However, if the database includes a structural summary such as a DataGuide, then an alternative approach is to expand...