Domagoj Vrgoč

Constraints are powerful declarative constructs that allow users to conveniently restrict variable values that potentially range over an infinite domain. In this paper, we propose a constraint path query language over property graphs, which extends Regular Path Queries (RPQs) with SMT constraints on data attributes in the form of equality constraints and Linear Real Arithmetic (LRA) constraints. We provide efficient algorithms for evaluating such path queries over property graphs, which exploits optimization of macro-states (among others, using theory-specific techniques). In particular, we demonstrate how such an algorithm may effectively utilize highly optimized SMT solvers for resolving such constraints over paths. We implement our algorithm in MillenniumDB, an open-source graph engine supporting property graph queries and GQL. Our extensive empirical evaluation in a real-world setting demonstrates the viability of our approach.

Graph databases have become an important data management technology across various domains, including biology, sociology, industry (e.g. fraud detection, supply chain management, financial services), and investigative journalism, due to their ability to efficiently store and query large-scale knowledge graphs and networks. Recently, the Graph Query Language (GQL) was introduced as a new ISO standard providing a unified framework for querying graphs. However, this initial specification lacks a formal type system for query validation. As a result, queries can fail at runtime due to type inconsistencies or produce empty results without prior warning. Solving this issue could have great benefits for users in writing correct queries, especially when handling large datasets. To address this gap, we introduce a formal type model for a core fragment of GQL extended with property-based filtering and imprecise types both in the schema and the queries. This model, named FPPC, enables static detection of semantically incorrect and stuck queries, improving user feedback. We establish key theoretical properties, including emptiness (detecting empty queries due to type mismatches) and type safety (guaranteeing that well-typed queries do not fail at runtime). Additionally, we prove a gradual guarantee, ensuring that removing type annotations either does not introduce static type errors or only increases the result set. By integrating imprecision into GQL, FPPC offers a flexible solution for handling schema evolution and incomplete type information. This work contributes to making GQL more robust, improving both its usability and its formal foundation.

Leapfrog Triejoin (LTJ) is arguably the most practical and popular worst-case-optimal (wco) algorithm for solving basic graph patterns in graph databases. Its main drawback is that it needs the database triples (subject, predicate, object) represented as paths in a trie, for each of the six orders of subject, predicate, and object. The resulting blowup in space makes most systems disregard LTJ or implement it only partially, which makes their corresponding algorithms non-wco. In this paper we show that, by using compact data structures, it is possible to build an index that at the same time matches the query time performance of the fastest classic wco index, and uses a fraction of the space of non-wco indices (which are much slower). Concretely, we make use of compact tree representations to store functional tries using one bit per trie edge, instead of one pointer, and further reduce the space by storing partial tries. Our most compact variant uses 5–6 times less space than classic wco implementations and 2–3 times less than classic non-wco systems. At solving queries, it is on par with the fastest classic wco system, and 30–40 times faster than non-wco systems. We further incorporate improved query resolution strategies into CompactLTJ variants, which makes it considerably faster than classic wco systems as well, on queries that do not output too many results. Finally, we show how CompactLTJ can incorporate dynamism without altering its performance, even under very demanding update regimes. We leave a public fully-functional implementation of CompactLTJ that can be directly used by practitioners.

In this paper we present TelarKG, a knowledge graph (KG) that consolidates multiple sources of information regarding the Chilean Constitutional process, particularly about the work of the members of the Constitutional Convention. TelarKG contains a wide range of public data, such as the materials from the commissions and information about the members' interventions and votes. In addition, the KG has been enriched with online user-generated content including posts from social networks related to the constitutional process, and transcriptions from the YouTube videos of the plenary sessions. Among other features, TelarKG leverages the semantic similarity search capabilities of the MillenniumDB endpoint to compute text similarity among convention members' Twitter messages. Additionally, we employ Entity Linking techniques to identify references to members of the Convention and Parties within these messages. TelarKG constitutes one of the most comprehensive historical archives on a political event, enabling users to query and navigate through diverse aspects of Chile's constitutional process.

Leapfrog Triejoin (LTJ) is arguably the most practical and popular worst-case-optimal (wco) algorithm for solving basic graph patterns in graph databases. Its main drawback is that it needs the database triples (subject, predicate, object) represented as paths in a trie, for each of the six orders of subject, predicate, and object. The resulting blowup in space makes most systems disregard LTJ or implement it only partially, and their corresponding algorithms be non-wco. In this paper we show that, by using compact data structures, it is possible to build an index that at the same matches the query time performance of the fastest classic wco index, and uses half the space of non-wco indices (which are much slower). Concretely, we make use of compact tree representations to store functional tries using one bit per trie edge, instead of one pointer. The resulting structure, called compactLTJ, uses 25% of the space of classic wco implementations and 45%-65% of classic non-wco systems. At solving queries, it is on par with the fastest classic wco system, and two orders of magnitude faster than non-wco systems. We further incorporate improved query resolution strategies into compactLTJ, which makes it considerably faster than any other alternative to display the first query results.