Browsing by Author "Vrgoc, Domagoj"

Now showing 1 - 20 of 20
  • 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
  • No Thumbnail Available
    Item
    Matrix Query Languages
    (2021) Geerts, Floris; Munoz, Thomas; Riveros, Cristian; Van den Bussche, Jan; Vrgoc, Domagoj
    Due to the importance of linear algebra and matrix operations in data analytics, there has been a renewed interest in developing query languages that combine both standard relational operations and linear algebra operations. We survey aspects of the matrix query language MATLANG and extensions thereof, and connect matrix query languages to classical query languages and arithmetic circuits.
  • No Thumbnail Available
    Item
    MillenniumDB: An Open-Source Graph Database System
    (Springer International Publishing, 2023) Vrgoc, Domagoj; Rojas, Carlos; Angles, Renzo; Arenas, Marcelo; Arroyuelo, Diego; Buil-Aranda, Carlos; Hogan, Aidan; Navarro, Gonzalo; Riveros, Cristian; Romero, Juan
    In this systems paper, we present MillenniumDB: a novel graph database engine that is modular, persistent, and open source. MillenniumDB is based on a graph data model, which we call domain graphs, that provides a simple abstraction upon which a variety of popular graph models can be supported, thus providing a flexible data management engine for diverse types of knowledge graph. The engine itself is founded on a combination of tried and tested techniques from relational data management, state-of-the-art algorithms for worst-case-optimal joins, as well as graph-specific algorithms for evaluating path queries. In this paper, we present the main design principles underlying MillenniumDB, describing the abstract graph model and query semantics supported, the concrete data model and query syntax implemented, as well as the storage, indexing, query planning and query evaluation techniques used. We evaluate MillenniumDB over real-world data and queries from the Wikidata knowledge graph, where we find that it outperforms other popular persistent graph database engines (including both enterprise and open source alternatives) that support similar query features.
  • No Thumbnail Available
    Item
    Querying APIs with SPARQL
    (2022) Mosser, Matthieu; Pieressa, Fernando; Reutter, Juan L.; Soto, Adrian; Vrgoc, Domagoj
    Although the amount of RDF data has been steadily increasing over the years, the majority of information on the Web is still residing in other formats, and is often not accessible to Semantic Web services. A lot of this data is available through APIs serving JSON documents. In this work we propose a way of extending SPARQL with the option to consume JSON APIs and integrate this information into SPARQL query answers, obtaining a language that combines data from the "traditional" Web to the Semantic Web. Our proposal is based on an extension of the SERVICE operator with the ability to connect to JSON APIs. With the aim of evaluating these queries as efficiently as possible, we show that the main bottleneck is the amount of API requests, and present an algorithm that produces "worst-case optimal" query plans that reduce the number of requests as much as possible. We note that the analysis of this algorithm is studied in terms of an algorithm for evaluating relational queries with access methods with the minimal number of access queries, which is of independent interest. We show the superiority of the worst-case optimal approach in a series of experiments that take existing SPARQL benchmarks, and augment them with the ability to connect to JSON APIs in order to obtain additional information. (C) 2020 Elsevier Ltd. All rights reserved.
  • Thumbnail Image
    Item
    Querying Graphs with Data
    (2016) Libkin, Leonid; Martensm, Wim; Vrgoc, Domagoj
  • No Thumbnail Available
    Item
    Recursion in SPARQL
    (2021) Reutter, Juan L.; Soto, Adrian; Vrgoc, Domagoj
    The need for recursive queries in the Semantic Web setting is becoming more and more apparent with the emergence of datasets where different pieces of information are connected by complicated patterns. This was acknowledged by the W3C committee by the inclusion of property paths in the SPARQL standard. However, as more data becomes available, it is becoming clear that property paths alone are not enough to capture all recursive queries that the users are interested in, and the literature has already proposed several extensions to allow searching for more complex patterns.
  • Thumbnail Image
    Item
    Regular expressions for data words
    (2015) Libkin, Leonid; Tan, Tony; Vrgoc, Domagoj
  • No Thumbnail Available
    Item
    REGULAR EXPRESSIONS FOR QUERYING DATA GRAPHS
    (2014) Tan, Tony; Vrgoc, Domagoj
    The standard regular expressions over finite alphabets have been widely accepted as the most basic formalism to query graph databases. However, the major drawback of this approach is that it ignores the presence of data. In this paper we study the so called regular expressions with binding (REWB), that is, regular expressions equipped with variables to store data within a well defined scope. In particular, we study the complexity of the query evaluation of REWB queries over graph databases.
  • No Thumbnail Available
    Item
    Representing Paths in Graph Database Pattern Matching
    (2023) Martens, Wim; Niewerth, Matthias; Popp, Tina; Rojas, Carlos; Vansummeren, Stijn; Vrgoc, Domagoj
    Modern graph database query languages such as GQL, SQL/PGQ, and their academic predecessor G-Core promote paths to first-class citizens in the sense that their pattern matching facility can return paths, as opposed to only nodes and edges. This is challenging for database engines, since graphs can have a large number of paths between a given node pair, which can cause huge intermediate results in query evaluation., We introduce the concept of path multiset representations (PMRs), which can represent multisets of paths exponentially succinctly and therefore bring significant advantages for representing intermediate results. We give a detailed theoretical analysis that shows that they are especially well-suited for representing results of regular path queries and extensions thereof involving counting, random sampling, and unions. Our experiments show that they drastically improve scalability for regular path query evaluation, with speedups of several orders of magnitude.
  • 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