Efficient evaluation of path queries over graph databases

Simple item page
dc.catalogadoryvc
dc.contributor.advisorVrgoc, Domagoj
dc.contributor.authorFarias Valdés, Benjamín Felipe
dc.contributor.otherPontificia Universidad Católica de Chile. Escuela de Ingeniería
dc.date.accessioned2024-07-30T22:46:15Z
dc.date.available2024-07-30T22:46:15Z
dc.date.issued2024
dc.date.updated2024-07-30T22:19:44Z
dc.descriptionTesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2024
dc.description.abstractLas 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.
dc.description.abstractPath 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.
dc.fechaingreso.objetodigital2024-07-30
dc.format.extentx; 67 páginas
dc.fuente.origenSRIA
dc.identifier.doi10.7764/tesisUC/ING/87229
dc.identifier.urihttps://doi.org/10.7764/tesisUC/ING/87229
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/87229
dc.information.autorucEscuela de Ingeniería; Farias Valdés, Benjamín Felipe; S/I; 1045602
dc.information.autorucEscuela de Ingeniería; Vrgoc, Domagoj; 0000-0001-5854-2652; 243075
dc.language.isoen
dc.nota.accesocontenido completo
dc.rightsacceso abierto
dc.rights.licenseAtribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0)
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/deed.es
dc.subjectBases de datos de grafos
dc.subjectConsultas de caminos regulares
dc.subjectGrafos de propiedades
dc.subjectAlgoritmos de búsqueda
dc.subjectGraph databases
dc.subjectRegular path queries
dc.subjectProperty graphs
dc.subjectSearch algorithms
dc.subject.ddc620
dc.subject.deweyIngenieríaes_ES
dc.titleEfficient evaluation of path queries over graph databases
dc.typetesis de maestría
sipa.codpersvinculados1045602
sipa.codpersvinculados243075
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TESIS FARIAS_EFFICIENT EVALUATION OF PATH.pdf
Size:
623.85 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.98 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
3.01 Tesis magíster