Cost-Based Optimization of Regular Path Queries on Large Graphs.
André Koschmieder · 2010
The significance of regular path queries (RPQs) on graph-like data structures has grown steadily over the past decade. Prominent application areas are XML/XPath, RDF/SPARQL, analysis of social networks, and queries on biomedical networks. However, current implementations of RPQ are restricted either in the type of the graph (e.g., only trees), the type of regular expressions (e.g., only single steps), and/or the size of the graphs. No research has yet tried to evaluate general RPQs on large graphs, i.e., with millions of nodes/edges. The predominant current techniques for dealing with RPQ use automata. However, we show that this approach, devel-oped for tree-structured XML, does not work well in gen-eral graphs. We developed a novel approach for answering RPQs using ideas from cost-based query optimization. Es-sentially, our method exploits the fact that not all labels in a graph are equally frequent. We devise an algorithm which decomposes an RPQ into a series of smaller queries by concentrating on rare labels, i.e., those elements of the query which have fewer matches in the graph. Comparison of this rather simple method to automata-based techniques across a wide range of queries and graphs shows that the automata-based approach is not able to handle large graphs due to the enormous amount of memory that is required, and that the cost-based method outperforms the automata-based approach in all cases. 1.