Browsing by Author "Farias Valdés, Benjamín Felipe"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Efficient evaluation of path queries over graph databases
    (2024) Farias Valdés, Benjamín Felipe; Vrgoc, Domagoj; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    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.