Stanford InfoLab Publication Server

Compile-Time Path Expansion in Lore

McHugh, J. and Widom, J. (1998) Compile-Time Path Expansion in Lore. Technical Report. Stanford InfoLab. (Publication Note: Workshop on Query Processing for Semistructured Data and Non-Standard Data Formats, 1998)




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

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:query processing, compile time query optimization, lore, semistructured data, regular path expressions
Subjects:Computer Science > Query Processing
Computer Science > Semistructured Data
Related URLs:Project Homepage
ID Code:306
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:29 Dec 2008 12:29

Download statistics

Repository Staff Only: item control page