Multiple-Query Optimization of Regular Path Queries

Graph databases have become increasingly important with the rise of social networks, and with the growth of the Semantic Web and characterization of biological networks. Regular path queries (RPQs) are a way to explore path patterns in graphs which have become a standard method to explore graph databases. SPARQL 1.1 includes property paths, and so now encompasses RPQs as a fragment. In many environments, such as visual query systems (VQSs), the RPQs are generated visually which may contain many commonalities that can be optimized globally. We introduce SWARMGUIDE, a framework for optimizing multiple regular path queries. The framework detects commonalities among the RPQs, in order to find an execution plan that is globally optimized over the plan spaces of the constituent RPQs.