Efficient evaluation of path queries over graph databases
Loading...
Date
2024
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Las consultas de caminos regulares (RPQs) son una característica central de todos los lenguajes y estándares de consulta de grafos modernos, como SPARQL, Cypher, SQL/PGQ y GQL. Si bien SPARQL devuelve puntos finales de RPQs, en Cypher, SQL/PGQ y GQL es también posible devolver los caminos completos. En esta tesis, presentamos el primer marco de trabajo para devolver caminos que coincidan con RPQs bajo los quince modos prescritos en los estándares SQL/PGQ y GQL. El núcleo de nuestro enfoque es la construcción del grafo de producto, combinada con una forma de representar de forma compacta un numero potencialmente exponencial de resultados que pueden coincidir con una RPQ. A lo largo de la tesis, describimos como opera este enfoque a nivel conceptual y brindamos garantías de tiempo de ejecución para evaluar RPQs. También desarrollamos una implementación de referencia sobre un motor de procesamiento de grafos de código abierto, mostrando así como se puede integrar en cadenas de procesamiento de grafos existentes, y realizamos un análisis detallado sobre la ejecución de RPQs en conjuntos de datos relevantes para evaluar la utilidad de nuestros métodos en un escenario realista. En comparación con varios motores de consulta modernos, obtenemos mejoras de ordenes de magnitud y un rendimiento notablemente estable, incluso para clases de RPQs teóricamente intratables.
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 thesis, we present the first framework for returning paths that match regular path queries under all fifteen modes prescribed 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 thesis, 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, thus showing how it can be integrated into existing graph processing pipelines, and perform a detailed analysis of path querying over relevant data sets to gauge the usefulness of our methods in a real-world scenario. Compared to several modern graph query engines, we obtain order-of-magnitude speedups and remarkably stable performance, even for theoretically intractable classes of path queries.
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 thesis, we present the first framework for returning paths that match regular path queries under all fifteen modes prescribed 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 thesis, 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, thus showing how it can be integrated into existing graph processing pipelines, and perform a detailed analysis of path querying over relevant data sets to gauge the usefulness of our methods in a real-world scenario. Compared to several modern graph query engines, we obtain order-of-magnitude speedups and remarkably stable performance, even for theoretically intractable classes of path queries.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2024
Keywords
Bases de datos de grafos, Consultas de caminos regulares, Grafos de propiedades, Algoritmos de búsqueda, Graph databases, Regular path queries, Property graphs, Search algorithms