Stanford InfoLab Publication Server

Optimizing Branching Path Expressions

McHugh, J. and Widom, J. (1999) Optimizing Branching Path Expressions. Technical Report. Stanford InfoLab.




Path expressions form the basis of most query languages for semistructured data and XML, specifying traversals through graph-based data. We consider the query optimization problem for path expressions that "branch," or specify traversals through two or more related subgraphs; such expressions are common in nontrivial queries over XML data. Searching the entire space of query plans for branching path expressions is generally infeasible, so we introduce several heuristic algorithms and post-optimizations that generate query plans for branching path expressions. All of our algorithms have been implemented in the Lore database system for XML, and we report experimental results over a variety of database and query shapes. We compare optimization and execution times across our suite of algorithms and post-optimizations, and for small queries we compare against the optimal plan produced by an exhaustive search of the plan space.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:Query Optimization, Path Expressions, XML, Semistructured Data
Subjects:Computer Science > Semistructured Data
Related URLs:Project Homepage
ID Code:405
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:28 Dec 2008 09:38

Download statistics

Repository Staff Only: item control page