TASWEET : optimizing disjunctive regular path queries in graph databases

Regular path queries (RPQs) have quickly become a staple to explore graph databases. SPARQL 1.1 includes prop- erty paths, and so now encompasses RPQs as a fragment. Despite the extreme utility of RPQs, it can be exceedingly difficult for even experts to formulate such queries. It is next to impossible for non-experts to formulate such path queries. As such, several visual query systems (VQSs) have been proposed which simplify the task of constructing path queries by directly manipulating visual objects representing the domain elements. The queries generated by VQSs may, however, have many commonalities that can be exploited to optimize globally. We introduce Tasweet, a framework for optimizing “disjunctive” path queries, which detects the commonalities among the queries to find a globally opti- mized execution plan over the plan spaces of the constituent RPQs. Our results show savings in edge-walks / time-to- completion of 59%.