Browsing by Author "Vrgoc, Domagoj"

Now showing 1 - 14 of 14
  • Thumbnail Image
    Item
    A framework for annotating CSV-like data
    (2016) Arenas Saavedra, Marcelo Alejandro; Maturana, F.; Riveros Jaeger, Cristian; Vrgoc, Domagoj
  • Thumbnail Image
    Item
    Containment of queries for graphs with data
    (2018) Kostylev, Egor V.; Reutter de la Maza, Juan; Vrgoc, Domagoj
  • No Thumbnail Available
    Item
    Efficient enumeration algorithms for regular document spanners
    (2020) Florenzano Hernández, Fernando Alberto; Riveros Jaeger, Cristian; Ugarte, M.; Vansummeren, S.; Vrgoc, Domagoj
  • 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.
  • Thumbnail Image
    Item
    Expressive power of linear algebra query languages
    (2020) Muñoz Serrano, Thomas; Riveros Jaeger, Cristian; Vrgoc, Domagoj; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    Los algoritmos del álgebra lineal a menudo requieren algún tipo de iteración o recursión, como lo ilustran los algoritmos estándar para la eliminación gaussiana, la inversión de matrices y la clausura transitiva. Una característica clave compartida por estos algoritmos es que permiten que se repitan varios pasos, pero limitados por la dimensión de la matriz. En esta tesis, ampliamos el lenguaje de consulta para matrices MATLANG con este tipo de recursión, y evidenciamos que esto es suficiente para expresar algoritmos clásicos del álgebra lineal. Estudiamos el poder expresivo de este lenguaje y demostramos que corresponde naturalmente a las familias de circuitos aritméticos, que a menudo se dice que capturan el álgebra lineal. Además, analizamos varios sub-fragmentos de nuestro lenguaje, y se demuestra que su poder expresivo está estrechamente relacionado con formalismos lógicos en las relaciones anotadas en semi-anillos.
  • Thumbnail Image
    Item
    Foundations of Modern Query Languages for Graph Databases
    (2017) Angles, R.; Arenas Saavedra, Marcelo Alejandro; Barceló Baeza, Pablo; Hogan, A.; Reutter de la Maza, Juan; Vrgoc, Domagoj
  • Thumbnail Image
    Item
    Is it Possible to Verify if a Transaction is Spendable?
    (FRONTIERS MEDIA SA, 2021) Arenas, Marcelo; Reisenegger, Thomas; Reutter, Juan; Vrgoc, Domagoj
    With the popularity of Bitcoin, there is a growing need to understand the functionality, security, and performance of various mechanisms that comprise it. In this paper, we analyze Bitcoin's scripting language, Script, that is one of the main building blocks of Bitcoin transactions. We formally define the semantics of Script, and study the problem of determining whether a user-defined script is well-formed; that is, whether it can be unlocked, or whether it contains errors that would prevent this from happening.
  • Thumbnail Image
    Item
    JSON : Data model and query languages
    (2020) Bourhis, P.; Reutter de la Maza, Juan; Vrgoc, Domagoj
  • Thumbnail Image
    Item
    Querying Graphs with Data
    (2016) Libkin, Leonid; Martensm, Wim; Vrgoc, Domagoj
  • Thumbnail Image
    Item
    Regular expressions for data words
    (2015) Libkin, Leonid; Tan, Tony; Vrgoc, Domagoj
  • Thumbnail Image
    Item
    Size bounds and algorithms for conjunctive regular path queries
    (2022) Cucumides Faúndez, Tamara A.; Vrgoc, Domagoj; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    Las conjuctive regular path queries (CRPQs) son una de las principales clases de consultas que se realizan sobre bases de datos de grafos. Su estructura se deriva de la estructura de consultas relacionales de joins, pero además permiten caminos de largo arbitrario para conectar puntos que deben ser considerados en dichos joins. Sin embargo y pese a su popularidad, hasta este momento se conoce poco acerca de cuales son los mejores algoritmos para procesar CRPQs. En este trabajo nos enfocamos en algoritmos óptimos en el peor caso, esto es, algoritmos cuyo tiempo de ejecución esta acotado por la cota superior del tamaño de las consultas que procesan. Aplicaciones recientes de este tipo de algoritmos se han llevado a cabo para consultas simples en grafos con resultados promisorios. En esta tesis, mostramos que la famosa cota sobre el número de resultados de una consulta propuesta por Atserias, Grohe y Marx puede ser extendida para CRPQs, pero que para obtener cotas ajustadas, se debe trabajar con un perfil de cardinalidad ligeramente mayor. Además de establecer dicha cota, discutimos acerca de los algoritmos que provienen de esta: si se procesa y materializa previamente todas las consultas del grafo (lo que demanda memoria cuadrática en términos de los vértices del grafo), entonces las técnicas desarrolladas para consultas conjuntivas pueden ser aplicadas. Por otro lado, si se impone una restricción en la memoria de trabajo de los algoritmos, entonces estos deben ser adaptados con cuidado: el orden de variables con el cual se procesa las consultas puede tener un gran impacto sobre su tiempo de ejecución.
  • Thumbnail Image
    Item
    Static analysis of navigational XPath over graph databases
    (2016) Kostylev, Egor V.; Reutter de la Maza, Juan; Vrgoc, Domagoj
  • Thumbnail Image
    Item
    Trial: A Navigational Algebra for RDF Triplestores
    (2018) Libkin, Leonid; Reutter de la Maza, Juan; Soto Suárez, Adrián Andrés; Vrgoc, Domagoj
  • Thumbnail Image
    Item