PathFinder: Returning Paths in Graph Queries

PathFinder: Returning Paths in Graph Queries

연구 분야: Databases

학회: International Semantic Web Conference

Path queries are a central feature of all modern graph query languages and standards, such as SPARQL, Cypher, SQL/PGQ, and GQL. While SPARQL returns endpoints of path queries, it is possible in Cypher, SQL/PGQ, and GQL to return entire paths. In this paper, we present the first framework for returning paths that match regular path queries under all fifteen modes in the SQL/PGQ and GQL standards. At the core of our approach is the product graph construction combined with a way to compactly represent a potentially exponential number of results that can match a path query. Throughout the paper we describe how this approach operates on a conceptual level and provide runtime guarantees for evaluating path queries. We also develop a reference implementation on top of an existing open-source graph processing engine, and perform a detailed analysis of path querying over Wikidata to gauge the usefulness of our methods in a real world scenario. Compared to several modern graph engines, we obtain order-of-magnitude speedups and remarkably stable performance, even for theoretically intractable queries.