Compile-Time Path Expansion in Lore

Abstract

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 regular path expressions at compile-time using the structural summary, reducing the run-time overhead of database exploration. This paper describes algorithms for compile-time regular path expression expansion in the context of the Lorel query language for semistructured data, and reports on performance results conducted on the Lore system illustrating the benefits of compile-time expansion