Optimizing regular path expressions using graph schemas

TLDR

Query languages for irregularly structured data use regular path expressions for navigation, which is useful when parts of the structure are unknown, unavailable, or frequently changing, but naive execution is inefficient because it ignores data structure. We describe two optimization techniques for queries with regular path expressions. Both techniques rely on graph schemas to specify partial knowledge about data structure; one prunes navigation to a fragment via an efficient rewriting algorithm, and the other uses state extents to eliminate or reduce navigation, with a polynomial‑space algorithm that finds all such optimizations. For restricted forms of regular path expressions the algorithm is provably efficient, and we also provide an efficient approximation algorithm that works on all regular path expressions.

Abstract

Query languages for data with irregular structure use regular path expressions for navigation. This feature is useful for querying data where parts of the structure is either unknown, unavailable to the user, or changes frequently. Naive execution of regular path expressions is inefficient however, because it ignores any structure in the data. We describe two optimization techniques for queries with regular path expressions. Both rely on graph schemas for specifying partial knowledge about the data's structure. Query pruning uses this structure to restrict navigation to only a fragment of the data; we give an efficient algorithm for rewriting any regular path expression query into a pruned one. Query rewriting using state extents can eliminate or reduce navigation altogether; it is reminiscent of optimizing relational queries using indices. There may be several ways to optimize a query using state extents; we give a polynomial space algorithm that finds all such optimizations. For restricted forms of regular path expressions, the algorithm is provably efficient. We also give an efficient approximation algorithm that works on all regular path expressions.