Browsing by Author "Arroyuelo, Diego"

Now showing 1 - 3 of 3
  • 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
    Optimal Joins Using Compressed Quadtrees
    (2022) Arroyuelo, Diego; Navarro, Gonzalo; Reutter, Juan L.; Rojas-Ledesma, Javiel
    Worst-case optimal join algorithms have gained a lot of attention in the database literature. We now count several algorithms that are optimal in the worst case, and many of them have been implemented and validated in practice. However, the implementation of these algorithms often requires an enhanced indexing structure: to achieve optimality one either needs to build completely new indexes or must populate the database with several instantiations of indexes such as B+-trees. Either way, this means spending an extra amount of storage space that is typically one or two orders of magnitude more than what is required to store the raw data.
  • Thumbnail Image
    Item
    Optimizing RPQs over a compact graph representation
    (2024) Arroyuelo, Diego; Gomez-Brandon, Adrian; Hogan, Aidan; Navarro, Gonzalo; Rojas-Ledesma, Javiel
    We propose techniques to evaluate regular path queries (RPQs) over labeled graphs (e.g., RDF). We apply a bit-parallel simulation of a Glushkov automaton representing the query over a ring: a compact wavelet-tree-based index of the graph. To the best of our knowledge, our approach is the first to evaluate RPQs over a compact representation of such graphs, where we show the key advantages of using Glushkov automata in this setting. Our scheme obtains optimal time, in terms of alternation complexity, for traversing the product graph. We further introduce various optimizations, such as the ability to process several automaton states and graph nodes/labels simultaneously, and to estimate relevant selectivities. Experiments show that our approach uses 3-5x\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\times $$\end{document} less space, and is over 5x\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\times $$\end{document} faster, on average, than the next best state-of-the-art system for evaluating RPQs.