QuaQue: Design and SQL Implementation of Condensed Algebra for Concurrent Versioning of Knowledge Graphs
Jey Puget Gil, Emmanuel Coquery, John Samuel, Gilles Gesquière · 2026
Read QuaQue: Design and SQL Implementation of Condensed Algebra for Concurrent Versioning of Knowledge Graphs by Jey Puget Gil, Emmanuel Coquery, John Samuel, Gilles Gesquière (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-18654.txt.
Introduction
Puget and co-authors introduce QuaQue, a tool for querying many versions of a knowledge graph at once. QuaQue sits inside the ConVer-G system. It translates SPARQL queries into SQL that runs on a plain relational database. Version data is packed into bitstrings through a condensed algebra. That packing keeps concurrent version queries fast and compact. The authors detail the algebra and the translation steps. Benchmarks against a native RDF triple store show the approach is viable and faster in their tests.
Catalog record
| CREATOR | Jey Puget Gil, Emmanuel Coquery, John Samuel, Gilles Gesquière |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38282 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.18654
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
QuaQue: Design and SQL Implementation of Condensed Algebra for Concurrent Versioning of Knowledge Graphs Jey Puget Gil, Emmanuel Coquery, John Samuel, Gilles Gesquière Abstract The management of versioned knowledge graphs presents significant challenges, particularly in querying data across multiple versions efficiently. This paper introduces QuaQue, a key component of the ConVer-G system, which addresses this challenge by translating SPARQL (SPARQL Protocol and RDF Query Language) queries into SQL (Structured Query Language). QuaQue leverages a novel condensed algebra to operate on a relational model where versioning information is compactly stored using bitstrings. This approach allows for efficient querying of concurrent versions of knowledge graphs within a standard relational database system. We present the key concepts of our condensed algebra, detail the translation process from SPARQL algebra to SQL, and provide a comparative benchmark against a native RDF (Resource Description Framework) triple store, demonstrating the viability and performance benefits of our approach. keywords [name=Index Terms: ] SQL; algebra; translation; concurrent versioning; relational. I Introduction The representation of complex, evolving information has driven the widespread adoption of Knowledge Graphs (KGs) in both industry and academia [ 28 ] . However, as KGs move from static repositories to dynamic assets, there is a critical need for robust concurrent versioning systems . In domains, such as urban planning—where datasets undergo parallel modifications by multiple stakeholders—a linear history is insufficient. Systems must support branching, merging, and the analysis of concurrent states without excessive data redundancy. While the Resource Description Framework and SPARQL are the de facto standards for KGs, they were primarily designed for static or monotonically increasing datasets. Native support for versioning remains a challenge. Standard approaches often rely on Named Graphs [ 7 ] to isolate versions. While accessing a single version remains efficient, this strategy leads to significant data duplication and increased query latency when querying across multiple versions. Consequently, efficiently querying across multiple versions remains an open problem in database research. The ConVer-G project [ 21 ] addresses this by bridging the gap between graph versioning requirements and the mature optimization capabilities of Relational Database Management Systems (RDBMSs). At the core of ConVer-G is QuaQue , a system that translates SPARQL queries into SQL that exploits efficient bitwise operations for version filtering. QuaQue leverages a condensed relational model . In RDF, a quad is a tuple that extends the standard triple with a graph identifier. We associate every quad with a bitstring , where each bit represents the validity of the quad in a specific version. This allows us to push version-filtering logic down to the RDBMS engine using efficient bitwise operations, significantly reducing the I/O overhead typically associated with multi-version queries. This paper details the design and implementation of QuaQue. We introduce a condensed algebra —an extension of relational algebra tailored for bitstring-annotated relations—and define its translation to SQL. This enables the execution of complex graph pattern matching on standard PostgreSQL instances. Our specific contributions are: • A novel condensed relational model utilizing bitstrings for the storage of concurrent KG versions. • The implementation of a Condensed Algebra and the QuaQue translator which maps SPARQL algebra to SQL. • A comparative benchmark demonstrating that QuaQue outperforms a native RDF triple store (Apache Jena) in multi-version query scenarios. • A fully reproducible approach, with the ConVer-G tool and the benchmark framework publicly available as open-source software. The remainder of this paper is organized as follows. Section 2 presents the state of the art. Section 3 details the design of the QuaQue system and the condensed relational model. Section 4 presents the experimental evaluation and benchmark results. Finally, Section 5 concludes the paper and outlines future work. II State of the Art The challenge of querying versioned data has been a long-standing topic in database research [ 36 ] . The relational model [ 9 ] , introduced by Codd, provides a foundation with relational algebra and calculus as powerful query languages. The expressive power of these languages has been a central theme of research, with extensions proposed to handle more complex queries, such as those involving recursion [ 37 , 2 ] and aggregate functions [ 35 ] . A key milestone in bridging the gap between high-level query languages and efficient execution is the work of Ullman [ 40 ] , which systematically addresses the translation of relational algebra and calculus queries into implementations, laying the groundwork for query processing and optimization. This connection is important, as the development of new algebras or extensions—such as those needed for versioned or condensed data—must ultimately be supported by practical translation and execution strategies. Recent surveys, such as Hofer et al. [ 27 ] , Jiang et al. [ 30 , 1 ] , and Ji et al. [ 29 ] provide a comprehensive overview of the current state and challenges in knowledge graph construction, highlighting the increasing complexity of managing evolving and versioned knowledge graphs. They emphasize the need for scalable and efficient methods for both constructing and maintaining knowledge graphs, especially as these graphs become larger and more dynamic. This underscores the importance of advanced versioning and querying mechanisms to support the evolving requirements of knowledge graph applications. A notable example of leveraging versioned knowledge graphs in practice is the work by Gonzalez-Hevia and Gayo-Avello [ 24 ] , who utilize Wikidata’s edit history for knowledge graph refinement tasks. Their approach demonstrates the value of exploiting historical edit information to improve the quality and reliability of knowledge graphs, further motivating the need for efficient storage and querying of versioned data. Recent work by Zhong et al. [ 46 ] further illustrates the importance of knowledge graphs in real-world applications, specifically in the domain of intelligent audit. Their study discusses both the opportunities and challenges of applying knowledge graphs to extract insights from complex, evolving data sources. This highlights the direct link between the need for advanced versioning and querying mechanisms—such as those discussed in this section—and the practical requirements of domains where data evolution and efficient cross-version analysis are critical for generating reliable insights. II-A Extending Relational Algebra Relational algebra has been extended with techniques, such as rewriting queries with arbitrary aggregation functions using views, as discussed by Cohen et al. [ 11 ] . The extensibility of relational algebra has also been a subject of research, particularly in the context of supporting new data types and operations. Haas et al. [ 26 ] proposed an extensible query processor architecture that allows the integration of user-defined types and functions into the relational algebra framework. This extensibility adapts relational systems to various application domains, enabling the seamless incorporation of specialized operators and data structures without sacrificing the benefits of a declarative query language. II-B Relational Algebra in Query Languages The principles of relational algebra have been foundational to the design of numerous query languages. SQL, the de facto standard for relational databases, is based on a tuple relational calculus, which is equivalent in expressive power to relational algebra [ 10 ] . The translation of SPARQL [ 15 ] , the standard query language for RDF, to SQL has been a topic of interest for leveraging the performance and scalability of relational databases for semantic web data. Several systems, such as Ontop [