Revisiting the Algebraic Foundation of Relational Data Yisu Remy Wang
Paul Talma
University of California, Los Angeles Department of Computer Science Los Angeles, CA, USA
University of California, Los Angeles Department of Philosophy Los Angeles, CA, USA
Abstract We revisit Tarski’s Algebra of Relations (TAR), an old formalism of relations predating Codd’s relational algebra by over 100 years, as a new foundation for relational databases. We argue TAR provides a better abstraction at both the semantic level and the physical level, in the context of modern application code and system architecture. To demonstrate the strengths of TAR, we design and implement Prela, a compositional and controllable query language, and show that queries written in Prela are concise, clear, and efficient.
arXiv:2607.26356v1 [cs.DB] 29 Jul 2026
1
Introduction
Over the past 50 years, Codd’s relational model [3] has cemented its status as the foundation underlying database systems. The relational algebra has therefore become the central abstraction bridging high-level semantics to low-level execution. However, the world has changed both below and above this abstraction. At the system level, OLAP engines increasingly adopt column-oriented storage, while transactional systems are built upon a key-value core. On the application side, researchers are pushing towards higher abstractions like the Entity/Relationship model [2, 5], with the goal to better support nested and graph data, and to reconcile the long-standing impedance mismatch between relational schema and application code. As a result, both the physical layer and the semantic layer have drifted away from the original table-oriented abstraction. Yet, as if by serendipity, the independent evolution of the physics and the semantics of relational data have led to the same destiny! This reunion calls for new abstractions that better connect queries to their execution. In this paper, we revisit an old formalism of relations predating Codd’s relational algebra by over 100 years. This formalism was developed by logicians from De Morgan, Peirce, Schröder, to Tarski and Givant, and is now commonly know as Tarski’s Algebra of Relations (TAR) [21, 29, 30]. To demonstrate the potential of TAR as a new foundation for modern database systems, we design and implement Prela, a compositional and controllable query language. Using Prela, the programmer can write concise, clear, and efficient queries, all the while retaining fine-grained control over low-level details of query execution. The power of Prela is best illustrated with an example. Consider query 16b from the Join Order Benchmark [17], whose SQL formulation spans 23 clauses, 11 of which are used to specify join conditions. Figure 1 shows the complete Prela source for the same query. We will revisit this query in detail later, but the intent is already clear at a glance: it looks for movies made by American companies with keyword matching “character-name-in-title”, then outputs the movie title along with the alias for each cast member. There are several notable differences between the Prela query and the SQL version. First, there is no explicit FROM clause in Prela; instead, relations appear as arguments to relation combinators like .with, .and, and .select, revealing the structure of the query. Similarly, join
movie . with ( company . s ( country ). eq ( " [ us ] " ) . and ( keyword . eq ( " character - name - in - title " )) . select ( title . and ( cast . s ( person ). s ( alias ). s ( text )))
Figure 1: JOB query 16b in Prela
conditions are not specified by explicit join clauses, but by query structure. Finally, thanks to Prela’s algebraic nature, queries can be written in a compositional way: in the example, every subexpression, including company.s(country).eq("[us]"), keyword.eq(...), and cast.s(person).s(alias).s(text), is on its own a valid query, and they appear directly as inputs to relation combinators to build up the larger query. The reader may be surprised to learn that the query in figure 1 is in fact regular Rust code. Indeed, movie, company, country, etc., are Rust variables, and combinators like .with, .and, .select, etc., are Rust functions. In other words, Prela is an embedded query language, or more simply, a library. This means Prela queries seamlessly integrate with application code, and the programmer can pass in regular Rust functions as UDFs. Under the hood, every Prela query is also a query plan, since each relational combinator corresponds precisely to an operator in TAR. A common complaint in SQL is the difficulty of guiding the query optimizer when it fails to find an efficient plan; by contrast, the Prela user has complete control over all aspect of query planning, including join ordering, operator pushdown, materialization, and selection of physical data structures. This level of control is increasingly relevant in the age of AI, as it puts the user—human or machine—back in the driver seat of performance tuning. Nevertheless, this great power need not come with great responsibility, and Prela/TAR can just as well serve as the intermediate representation underlying a query optimizer—the implementation of which we leave as future work. Finally, Prela queries are surprisingly “closer to the metal” than even the standard relational algebra, thanks again to the foundation of TAR. In our running example, variables like country and keyword are backed directly by vectors in a column store, and relation combinators compile to efficient operations over the columns. In summary, figure 2 compares the architecture of a traditional database with one based on TAR. Unlike the layers of abstractions that pull the programmer away from the data, TAR serves as the universal representation shared by the programmer, the storage engine, the execution engine, and the optimizer, bringing each component closer to each other and enabling cross-cutting optimizations.
2
Related Work
“What goes around comes around”. Despite countless attempts at replacement, the relational model has stood the test of time [27].
Yisu Remy Wang and Paul Talma
SQL
Relational Algebra optimize (future work)
ORM Programmer
TAR
Physical Plan
ID 646 478 583
title The Godfather Seven Samurai Casablanca
year 1972 1954 1942
keyword Crime War Romance
# 0 1 2
title The Godfather Seven Samurai Casablanca
# 0 1 2
# 0 1 2
Columnar Storage ID 646 478 583
Figure 2: Conventional database abstractions (top route) v.s. unified abstraction based on TAR (bottom route) This paper does not try to supplant the relational model, but rather to refine and evolve it to meet modern needs. TAR—despite being a century older—can be understood as an evolution of the relational algebra towards column stores and modern application code; the Prela language can also be considered a prototype demonstrating how SQL can be extended and made more flexible. In particular, TAR and Prela stand upon the two pillars of physical and logical independence: the relation-centric TAR assumes an abstract data model allowing for different physical implementations including dense vectors, hash maps, or bit sets; the corresponding Prela query accepts type annotations to specify any of these data structures. Queries can be declared as views and used as inputs to other queries, should the logical schema change; addition and deletion of orthogonal attributes and relationships also will not break existing queries. We believe ideas of TAR and Prela can be incorporated into mainstream relational databases to simplify their design and implementation. TAR in theory. The connection between Tarski and Codd has been noted as early as the first PODS conference in 1982, when Imielinski and Lipski [14] demonstrated how to emulate Codd’s relational algebra with Tarski’s cylindric algebras [13], an extension of Boolean algebras related to TAR. Gyssens, Saxton and Van Gucht [11] proposed an alternative approach to modeling relational algebra by enhancing TAR with certain pairing/tagging operations that introduce tuple values. Prela’s product operation .and fills a similar role to pairing and tagging, but is more natural for writing queries. Database theorists have also used TAR to analyze graph and tree query languages like Regular Path Queries, XPath, and SPARQL [7, 12, 19, 28]. This is thanks to how TAR’s main operator, the relational composition, conveniently models path traversal. Nevertheless, none of these languages were built upon TAR a priori. Van den Bussche [4] gives an introduction and survey of how Tarski’s ideas have been applied to database theory. TAR in practice. There have been sporadic efforts to bring the theory of TAR into practice. In 1992, Paredaens et al. [23] presented GOOD, a “Graph-Oriented Object Database”, and envisioned an implementation over a data model based on TAR. The GOOD system itself, however, was built atop a standard relational engine. A follow-on technical report by Sarathy and Van Gucht [24] describes an implementation of the GOOD model in the IUGQL query language. More recently, Libkin et al. developed TriAL [20], a language for recursive queries over RDF data based on a triple algebra related to TAR. Compared to these languages, Prela focuses on traditional non-recursive queries over relational data. Prela also uses TAR directly both as the surface syntax and the underlying storage abstraction, whereas
# 0 1 2
year 1972 1954 1942
keyword Crime War Romance
Figure 3: A wide table (top) and its decomposition (bottom) the aforementioned systems all come with a separate, declarative query syntax. This indirection complicates system design, obstructs performance tuning, and obscures the beauty of TAR. Dataframes. Dataframe libraries like pandas [22] and polars [33] provide an interface to tabular data based on relational algebra. As such, these libraries also struggle to express multi-table queries succinctly, as each join operation must specify the join condition explicitly. At the engine level, pandas executes queries as-is, albeit eagerly – every dataframe operation immediately produces a result when it is called. Other more optimized engines like polars generate and optimize query plans, much like traditional OLAP databases. Prela’s engine can be thought of as implementing a lazy, push-based execution model. Operators do not materialize intermediate results unless necessary, and the unoptimized queries already run fast. SQL extensions. The secret behind the longevity of SQL is its ability to absorb ideas proposed in new query languages. Recent work by Shute, Zheng, and Kudtarkar [26] proposed SQL extensions to better support semantic data modeling and graph workloads. Their proposal lead to several design points strikingly similar to those taken by Prela. For example, they also support implicit joins without specifying join conditions, as well as multi-hop join/access syntax similar to the last line of figure 1. With Prela, we aim to demonstrate that such extensions to SQL can be grounded on the firm theoretical foundation of TAR, and that they are not merely syntactic sugar, but can produce tangible performance benefits when connected to the underlying execution engine. Functional data models. Several functional data models have been proposed over the years [1, 10, 16, 25], and a recent position paper by Dittrich [6] envisions a data model and query language where “everything is a function”. He then proposes a function algebra where the operators are higher-order functions consuming and producing functions. Prela can be considered a realization of that vision over TAR: a relation in TAR is precisely a (multi-valued) function. Prela also goes beyond the syntax and semantics of the query language itself and explores the synergy between high-level abstraction and low-level execution.
3
The Prela Language
This section defines the data model, syntax, and semantics of the Prela query language. Table 1 provides a reference of TAR operators, their meaning, and their spelling in Prela.
Revisiting the Algebraic Foundation of Relational Data
Table 1: Relational operators in Prela Name compose product predicate filter restrict map gather invert group by
3.1
Syntax r.select(t) / r.s(t) r.and(t) r.eq(v), r.lt(v), ... r.filt(p) r.with(t) r.map(f) r.gather(t) r.inv() r.group_by(t)
Semantics 𝜋𝑟 .1,𝑡 .2 (𝑟 ⊲⊳𝑟 .2=𝑡 .1 𝑡) 𝑟 ⊲⊳𝑟 .1=𝑡 .1 𝑡 𝜎𝑟 .2=𝑣 (𝑟 ), 𝜎𝑟 .2<𝑣 (𝑟 ), ... 𝜎𝑝 (𝑟 .2) (𝑟 ) 𝑟 ⋉𝑟 .2=𝑡 .1 𝑡 𝜋𝑟 .1,𝑓 (𝑟 .2) (𝑟 ) nested compose1 𝜋𝑟 .2,𝑟 .1 (𝑟 ) 𝜋𝑡 .2,𝑡 .1 (𝑡 ⋉𝑡 .1=𝑟 .2 𝑟 )
Data Model
The fundamental datatype of Prela is the binary relation. Although restricting relations to be binary may appear limiting, it is simple to recover the flexibility of multi-column tables with ones over only two columns: every relation with 𝑘 columns is represented with 𝑘 binary relations, each mapping the row number to the corresponding column entry. Figure 3 shows an example: a movie relation with columns title, year, and keyword decomposes to 4 binary relations: the first maps each ID to its row, and the other 3 map each row to its title, year, and keyword, respectively. The special treatment of the ID column will make sense when we join across tables. Decomposing a wide table into many binary tables may appear expensive: while the original table had 𝑘 columns, the decomposed tables now span a total of 2𝑘 columns. However, since one column of each binary relation simply contains the row number, that column need not be explicitly stored, and each binary relation can be represented by a vector! In section §4 we will also show how Prela’s implementation eliminates the additional joins needed to “re-assemble” a wide table from its columns. In other words, the “binarization” takes a detour to arrive at the same physical representation found in column stores. This detour is nevertheless necessary, as it allows us to query the columns in a compositional way.
3.2
Select, Project, and Join
Prela queries are composed of operators applied to relational arguments. The most important operator in Prela is the relational composition r.select(t) which is equivalent to the relational algebra expression 𝜋𝑟 .1,𝑡 .2 (𝑟 ⊲⊳𝑟 .2=𝑡 .1 𝑡), where 𝑟 .𝑖 indicates the 𝑖-th column of 𝑟 . Intuitively, relational composition generalizes function composition in the same way (binary) relations generalize functions: the composition 𝑔 ◦ 𝑓 is sometimes written 𝑓 ; 𝑔 and first applies 𝑓 , then 𝑔. If the relation r maps each x value to some y values, and if t maps each y to some zs, then r.select(t) first maps x via r to get ys, then maps each y via t to get zs. Using our example in figure 3, if we call the binary relations movie, title, year, and keyword from left to right, then movie.select(title) returns a binary relation mapping each movie ID to its title, and similarly for movie.select(year) and movie.select(keyword). Composition also plays the role of joins in Prela. Consider a movie_company table with three columns: the company ID, name, and 1 Nested compose is not expressible in standard relational algebra; formally, the seman-
Ð Ð tics of r.gather(t) is (𝑥, ¥ 𝑦 ∈𝑟 [𝑥 ] 𝑡 [𝑦 ] ) | 𝑥 ∈ 𝑟 .1 where ¥ is the bag union and 𝑟 [𝑥 ] is the bag of 𝑦 such that (𝑥, 𝑦) ∈ 𝑟 (similar for 𝑡 [𝑦 ] ).
# 0 1 2
company 657 188 353
ID 657 188 353
# 0 1 2
# 0 1 2
name Paramount Toho Warner Bros.
# 0 1 2
country USA Japan USA
Figure 4: Left: decomposed company column from the movie table; right: decomposed columns from the movie_company table
country, each of which becomes a binary relation in Prela as shown on the right of figure 4. We also add a company column to the movie table linking each movie to the ID of its production company. Now, we can look up the country of a movie’s production company with movie.s(company).s(id2row).s(country), where .s is shorthand for .select, and id2row is the relation mapping company IDs to row numbers. Because joining via foreign keys almost always require “resolving” the key to its row, Prela automatically inserts .s(id2row) to key/foreign key joins, similar to how programming languages like Rust automatically dereference pointers upon a field access. This allows us to simply write movie.s(company).s(country) which is pronounced “movie’s company’s country”. This is also what happened on the last line of figure 1. Given that composition “throws away” the join attributes, the reader may be wondering if there are certain SQL queries that Prela cannot express. Our answer is two-fold. On one hand, real world queries almost always join on key/foreign keys, and keys rarely serve any other purpose — it does not make sense to aggregate over them. So dropping the keys after the join is not a real sacrifice. On the other hand, it is true that the original TAR is strictly less expressive than Codd’s relational algebra. One approach to bridging this gap is to introduce the so-called pairing operators to TAR [11]. In Prela, we propose the product operator .and as an equivalent yet more practical extension. r.and(t) joins the relations on their first column, i.e., 𝑟 ⊲⊳𝑟 .1=𝑡 .1 𝑡. Crucially, the output is still a binary relation, whose first column is the intersection of 𝑟 .1 and 𝑡 .1, and the second column is the Cartesian product of 𝑟 .2 and 𝑡 .2 for each matching 𝑟 .1 = 𝑡 .1. For example, title.and(year) is the relation mapping 0 to (The Godfather, 1972), 1 to (Seven Samurai, 1954), and 2 to (Casablanca, 1942). Combining with .select, the expression movie.select(title.and(year).and(keyword)) implements the SQL query SELECT title, year, keyword FROM movie. The next Prela operator exercised by figure 1 is the predicate r.eq(v) which returns all rows of r whose right column equals v. Other predicates like .gt (greater than), and .rx (regular expression match) work the same way. There is also a generic r.filt(p) operator that filters r by any Boolean function p. Going back to the example, keyword.eq("character-name-in-title") returns rows in keyword (which maps a movie to its keywords) such that the keyword is “character-name-in-title”; company.s(country).eq("[us]") first composes company (mapping a movie to its company) with country (mapping a company to its country) to get a mapping from each movie to its country, then keeps only those in the US. Finally, the .and operator joins the filtered relations, keeping only American movies with character name in their titles. The last operator used in our example is the restriction r.with(t) which is exactly the left-semijoin 𝑟 ⋉𝑟 .2=𝑡 .1 𝑡, and it emulates SQL’s
Yisu Remy Wang and Paul Talma
SELECT FROM GROUP HAVING
keyword , min ( year ) movie BY keyword min ( year ) > 1950
movie . group_by ( keyword ) . gather ( year ) . map ( min ) . gt (1950)
Figure 5: Grouping and aggregation in SQL and Prela
lhs . select ( rhs ). drive ( k ) = lhs . drive (| x , y | rhs . probe (y , | z | k (x , z ))) lhs . and ( rhs ). probe (x , k ) = lhs . probe (x , | y | rhs . probe (x , | z | k (( y , z )))) col . drive ( k ) = for i in 0.. col . len : k (i , col [ i ]) col . probe (i , k ) = k ( col [ i ])
Figure 6: CPS protocol for .select, .and, and columns
WHERE clause.2 A happy accident is that .and doubles as “logical conjunction” inside .with, because the semijoin ignores the second
column of its right-hand-side.
3.3
UDFs, Structured Output, and Aggregation
Just like the original form of Codd’s relational algebra, TAR was designed to model first order logic, and requires extensions to support practical workloads. Prela supports “generalized projection” with the .map operator: r.map(f) maps the function f over each value in the second column of r. One advantage of embedding Prela in Rust is to allow arbitrary Rust code to be used as UDFs. In particular, the query can construct structured outputs. For example, the following query returns a list of Movie structs instead of tuples: movie . select ( title . and ( year )) . map (|( id ,( t , y ))| Movie { title : t , year : y })
Another extension allows Prela to return nested outputs: r.gather(t) is like r.select(t), but maps each distinct r.1 to a list of t.2 values. For example, movie.gather(keyword) returns a binary relation mapping each movie ID to all the keywords associated with that movie. Together with .map, we can use .gather to implement aggregation: movie.gather(year).map(min) returns the minimum year associated with each movie, by mapping the list function min over the list of years per movie. To support grouping, we need to introduce one last operation from the original TAR: the inverse t.inv() simply flips the two columns of t. We can now implement Prela’s r.group_by(t) as t.inv().with(r.inv()), or 𝜋𝑡 .2,𝑡 .1 (𝑡 ⋉𝑡 .1=𝑟 .2 𝑟 ) in relational algebra. For example, the first line of the Prela query in figure 5 desugars to keyword.inv().with(movie.inv()). First, keyword.inv() flips the keyword relation to map each keyword to the rows it appears in; restricting with movie.inv() is a no-op, but would be meaningful if movie were already restricted by other predicates. Line 2 composes the result from line 1 with year to obtain a mapping from keyword to years. Line 3 aggregates with min to find the earliest year associated with each keyword. Finally, the last line .gt(1950) implements the HAVING clause in the SQL query. Grouping by multiple columns can be achieved with the help of .and, for example movie.group_by(keyword.and(year)). To aggregate over multiple columns, we can pass in a function that reduces all of them at once.
3.4
Discussion
Looking back at the example in figure 1, we see another, more intuitive way to understand the query: pretend that there are movie objects with field company, keyword, title, and cast, where company is its own object with field country, and similarly for cast, person, and alias. Then the Prela query appears to access fields and apply 2 Unfortunately where is a reserved keyword in Rust.
predicates to them. This is not accidental. Central to the design of both TAR and Prela is the focus on binary relations which closely model both attributes and relationships à la Entity/Relationship. Modern business logic usually start life as an E/R diagram, and the application code—commonly written in some object-oriented language—naturally mirrors the E/R model. Built with a set of compositional operators, Prela queries blend into the surrounding application, obviating the need for ORMs.
4
Implementation
In Section §3.1 we explained how the apparent storage overhead of binary relations is eliminated by columnar storage. It may appear a computational overhead remains, when we need to reassemble a table from its columns. Consider the following SQL query: SELECT ID , title , keyword FROM movie
It outputs the ID, title, and keyword of each movie. In a conventional database the query requires only a simple scan over the movie table. Specifically, the execution over a column store would look something like this: for i in 0.. n : print ( movie [ i ] , title [ i ] , keyword [ i ])
In the above, a single loop co-iterates over the selected table columns. The corresponding Prela query is movie.select(title.and(year)). Implemented naively, the Prela query would require two joins, one each for .and and .select. In general, the number of joins grows proportionally with the number of columns involved in a Prela query, which is rather expensive. The textbook solution to remove intermediate state during query execution is the iterator model [9]. Iterators incur overhead like method calls and other bookkeeping operations, and two standard remedies are vectorization and query compilation [15]. Unfortunately, both approaches require significant engineering effort that would exceed the scope of a prototype like Prela. To achieve good performance while keeping Prela’s implementation simple and modular, we turn to a technique from functional compilers — deforestation in continuation-passing style (CPS) [8]. The basic idea of CPS is for combinators to push computation down from the query root to its leaves instead of pulling data up from leaves to root. More specifically, Prela queries can be accessed in two ways. Calling query.drive(k) applies the closure k (the continuation) to each row of query. Calling query.probe(key, k) looks up key in query and applies k to each resulting value. For example, movie.s(title).drive(print) prints each (id, title) pair, while movie.s(title).probe(3, print) prints the title of the movie with ID 3. Since every combinator receives and returns binary relations, .drive and .probe are well-defined for all Prela queries. Figure 6
Revisiting the Algebraic Foundation of Relational Data
movie . select ( title . and ( keyword )). drive ( k )
To save space we will abbreviate movie, title, keyword, .drive, and .probe with m, t, w, .drv, and .prb, respectively. Expanding .drive on .select drives its left-hand-side and probes its right-hand-side: m . drv (| x , y | t . and ( w ). prb (y , | z | k (x , z )))
As m is an input column, driving it expands to a loop: for i in 0.. m . len : t . and ( w ). prb (i , | z | k ( m [ i ] , z ))
Next, probing .and propagates to probing its arguments:
Join Order Benchmark
10 1
TPC-H
y = x (parity) prela
100
prela time (s, log)
shows the definition of .drive and .probe for .select, .and, as well as input columns. Let us unfold the definitions for our example query. We start by driving the query with a continuation k which may print each result, or append it to a buffer:
DuckDB faster
10 1
10 2
10 3 3 10
y = x (parity) prela (idiomatic) prela (optimized)
100
DuckDB faster
10 2
Prela faster 10 2
10 1
DuckDB time (s, log)
100
10 3 3 10
Prela faster 10 2
10 1
DuckDB time (s, log)
100
Figure 7: Performance comparison of Prela and DuckDB: each data point represents a query, where the 𝑥-coordinate is DuckDB’s run time, and the 𝑦-coordinate is Prela’s run time
for i in 0.. m . len : t . prb (i , | y | w . prb (i , | z | k ( m [ i ] , (y , z ))))
Finally, probing title and keyword expand to array accesses: for i in 0.. m . len : k ( m [ i ] , ( t [ i ] , w [ i ]))
At this point, we recover exactly the fused co-iteration shown earlier in this section! Note how we use the term expand: in Prela’s implementation, all we had to do is annotate the definition of .drive and .probe for each combinator with #[inline], and the Rust compiler would automatically fuse the operations into tight loops. The main motivation for implementing Prela in continuationpassing style is to derive a self-contained, easy-to-understand prototype that can guide the construction of more full-fledged systems. On one hand, relying on the Rust compiler has unacceptably high latency for queries that must be compiled on-the-fly; on the other hand, data warehouses repeatedly execute the same query over gradually-changing data, which can amortize the compilation cost [32]. Another advantage of embedding Prela in Rust is to allow arbitrary Rust code to be used as UDFs, as described in section §3.3. We pose a challenge to future research to match Prela’s flexibility and run time performance, while incurring much lower compilation overhead.
5
Evaluation
In section §1 we promised that Prela leads to concise, clear, and efficient queries. Clarity is subjective, and measuring conciseness in lines of code only tells part of the story. We therefore invite the reader to compare Prela queries to their SQL counterparts to judge for themselves.3 Nevertheless, we share some “quick numbers” here: the Prela code for all 113 queries in the Join Order Benchmark [17] (JOB) total ~1000 lines, while the original SQL queries span over 4000 lines; for TPC-H [31], it takes Prela ~300 lines to express all 22 queries, whereas the SQL queries span ~600 lines. Prela achieves more savings on JOB because the queries there join together many tables, and the implicit/structural joins in Prela avoids spelling out the join conditions, as demonstrated in figure 1. Does the brevity of Prela queries sacrifice their performance? To answer this question, we benchmark Prela against DuckDB v1.5.3 on JOB and TPC-H. Care must be taken to interpret our results. On one hand, Prela is an early prototype and has not implemented 3 The source code for Prela and example queries are available at https://prela-lang.org.
the myriad of optimizations found in mature systems; on the other, Prela is also not weighed down by a large set of features. In addition, Prela has no query optimizer, but offers more flexibility for performance tuning. One way to understand our experiments is that they gauge the performance ceiling of a database system built on a foundation of TAR, assuming such a system implements a competent query optimizer as well as low-level optimizations. All experiments run on an M2 MacBook Air with 16 GiB of RAM. Data is pre-loaded into memory. Since Prela is currently singlethreaded, we also run DuckDB on a single thread for fairness. Each query is executed 5 times and the median run time is reported. Summaries of the results are collected in figure 7. Prela executes all 113 queries of JOB in 8.68s, a 4.5× speedup over DuckDB’s 38.82s. Prela’s advantage is mainly due to data representation: because JOB’s primary keys are contiguous integers, the ID to row mapping degenerates to the identity after sorting; instead of materializing the relation, we represent this mapping with the identity function which is optimized away during compilation. And because each column is stored as a vector indexed by the row number, joins degenerate to fast array accesses. We tried to port the same optimizations back to DuckDB but were not successful. The only user-accessible index provided by DuckDB is the hashing-based adaptive radix tree [18], and its query optimizer ignored every foreign key index. DuckDB frequently picks bushy join plans, whereas Prela follows left-deep plans shaped by the query structure and uses index nested loop joins to avoid allocation. For TPC-H, the plot shows two sets of queries: the circular dots represent idiomatic queries which are written in the most natural way without regard to performance. These queries run in 1.13s, which is 1.11× faster than DuckDB’s 1.26s. It is easy to further improve the performance of the Prela queries. By directly rewriting the queries, we were able to speed them up by reordering joins, introducing materialization points, and specifying data structures like bit sets for materialized intermediates. The tuned queries take 0.44s, 2.86× faster than DuckDB. The experiments show how Prela empowers the programmer to fine tune query performance, and a future query optimizer can achieve results on par or exceeding that of current systems.
Yisu Remy Wang and Paul Talma
6
Conclusion
We have presented the design and implementation of Prela, a query language based on TAR. At the core of Prela is the binary relation which connects columnar storage with entity/relationship semantics, resulting in succinct and efficient queries. Our experiments show there is strong potential for a database system based on TAR to outperform state-of-the-art OLAP systems. Future work include parallelization, fast compilation, and query optimization of TAR, as well as consideration of transactional workloads.
References [1] Peter Buneman and Robert E. Frankel. 1979. FQL - A Functional Query Language. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston, Massachusetts, USA, May 30 - June 1, Philip A. Bernstein (Ed.). ACM, 52–58. doi:10.1145/582095.582104 [2] Peter P. Chen. 1976. The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1, 1 (1976), 9–36. doi:10.1145/320434.320440 [3] E. F. Codd. 1970. A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13, 6 (1970), 377–387. doi:10.1145/362384.362685 [4] Jan Van den Bussche. 2001. Applications of Alfred Tarski’s Ideas in Database Theory. In Computer Science Logic, 15th International Workshop, CSL 2001. 10th Annual Conference of the EACSL, Paris, France, September 10-13, 2001, Proceedings (Lecture Notes in Computer Science, Vol. 2142), Laurent Fribourg (Ed.). Springer, 20–37. doi:10.1007/3-540-44802-0_2 [5] Amol Deshpande. 2025. Beyond Relations: A Case for Elevating to the Entity-Relationship Abstraction. In 15th Conference on Innovative Data Systems Research, CIDR 2025, Amsterdam, The Netherlands, January 19-22, 2025. www.cidrdb.org. https://vldb.org/cidrdb/2025/beyond-relations-a-case-forelevating-to-the-entity-relationship-abstraction.html [6] Jens Dittrich. 2026. A Functional Data Model and Query Language is All You Need. In Proceedings 29th International Conference on Extending Database Technology, EDBT 2026, Tampere, Finland, March 24-27, 2026, Wolfgang Lehner, Vanessa Braganholo, Kostas Stefanidis, Zheying Zhang, Alexander Krause, and João Felipe Nicolaci Pimentel (Eds.). OpenProceedings.org, 619–626. doi:10.48786/ EDBT.2026.50 [7] George H. L. Fletcher, Marc Gyssens, Dirk Leinders, Jan Van den Bussche, Dirk Van Gucht, Stijn Vansummeren, and Yuqing Wu. 2011. Relative expressive power of navigational querying on graphs. In Database Theory - ICDT 2011, 14th International Conference, Uppsala, Sweden, March 21-24, 2011, Proceedings, Tova Milo (Ed.). ACM, 197–207. doi:10.1145/1938551.1938578 [8] Andrew John Gill, John Launchbury, and Simon L. Peyton Jones. 1993. A Short Cut to Deforestation. In Proceedings of the conference on Functional programming languages and computer architecture, FPCA 1993, Copenhagen, Denmark, June 9-11, 1993, John Williams (Ed.). ACM, 223–232. doi:10.1145/165180.165214 [9] Goetz Graefe. 1994. Volcano - An Extensible and Parallel Query Evaluation System. IEEE Trans. Knowl. Data Eng. 6, 1 (1994), 120–135. doi:10.1109/69.273032 [10] Peter M. D. Gray. 2005. The Functional Approach to Data Management: Modelling, Analysing and Integrating Heterogeneous Data. Program 39, 4 (2005), 401. doi:10.1108/PROG.2005.39.4.401.14 [11] Marc Gyssens, Lawrence V. Saxton, and Dirk Van Gucht. 1991. Tagging as an Alternative to Object Creation. In Query Processing for Advanced Database Systems, Selected Contributions from a Workshop on "Query Processing in Object-Oriented, Complex-Object and Nested Relation Databases", Interationales Begegnungs- und Forschungszentrum für Informatik, Schloss Dagstuhl, Germany, June 1991, Johann Christoph Freytag, David Maier, and Gottfried Vossen (Eds.). Morgan Kaufmann, 201–242. [12] Jelle Hellings, Yuqing Wu, Marc Gyssens, and Dirk Van Gucht. 2022. The power of Tarski’s relation algebra on trees. J. Log. Algebraic Methods Program. 126 (2022), 100748. doi:10.1016/J.JLAMP.2022.100748 [13] Leon Henkin, J. Donald Monk, and Alfred Tarski. 1971. Cylindric Algebras, Part I. Studies in Logic and the Foundations of Mathematics, Vol. 64. North-Holland,
Amsterdam. [14] Tomasz Imielinski and Witold Lipski Jr. 1984. The Relational Model of Data and Cylindric Algebras. J. Comput. Syst. Sci. 28, 1 (1984), 80–102. doi:10.1016/00220000(84)90077-1 [15] Timo Kersten, Viktor Leis, Alfons Kemper, Thomas Neumann, Andrew Pavlo, and Peter Boncz. 2018. Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask. Proc. VLDB Endow. 11, 13 (2018), 2209–2222. doi:10.14778/3275366.3275370 [16] K. G. Kulkarni and Malcolm P. Atkinson. 1986. EFDM: Extended Functional Data Model. Comput. J. 29, 1 (1986), 38–46. doi:10.1093/COMJNL/29.1.38 [17] Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2015. How Good Are Query Optimizers, Really? Proc. VLDB Endow. 9, 3 (2015), 204–215. doi:10.14778/2850583.2850594 [18] Viktor Leis, Alfons Kemper, and Thomas Neumann. 2013. The adaptive radix tree: ARTful indexing for main-memory databases. In 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8-12, 2013, Christian S. Jensen, Christopher M. Jermaine, and Xiaofang Zhou (Eds.). IEEE Computer Society, 38–49. doi:10.1109/ICDE.2013.6544812 [19] Leonid Libkin, Wim Martens, and Domagoj Vrgoc. 2016. Querying Graphs with Data. J. ACM 63, 2 (2016), 14:1–14:53. doi:10.1145/2850413 [20] Leonid Libkin, Juan L. Reutter, Adrián Soto, and Domagoj Vrgoc. 2018. TriAL: A Navigational Algebra for RDF Triplestores. ACM Trans. Database Syst. 43, 1 (2018), 5:1–5:46. doi:10.1145/3154385 [21] Roger D. Maddux. 1991. The Origin of Relation Algebras in the Development and Axiomatization of the Calculus of Relations. Studia Logica 50, 3-4 (1991), 421–455. doi:10.1007/bf00370681 [22] Wes McKinney. 2010. Data Structures for Statistical Computing in Python. In Proceedings of the 9th Python in Science Conference, Stéfan van der Walt and Jarrod Millman (Eds.). 56–61. doi:10.25080/Majora-92bf1922-00a [23] Jan Paredaens, Jan Van den Bussche, Marc Andries, Marc Gemis, Marc Gyssens, Inge Thyssens, Dirk Van Gucht, Vijay M. Sarathy, and Lawrence V. Saxton. 1992. An Overview of GOOD. SIGMOD Rec. 21, 1 (1992), 25–31. doi:10.1145/130868. 130872 [24] Vijay M Sarathy and Dirk Van Gucht. 1993. Implementation of a Graph Oriented Query Language: IUGQL. databases 6 (1993), 10. [25] David W. Shipman. 1979. The Functional Data Model and the Data Language DAPLEX (Abstract). In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston, Massachusetts, USA, May 30 - June 1, Philip A. Bernstein (Ed.). ACM, 59. doi:10.1145/582095.582105 [26] Jeff Shute, Colin Zheng, and Romit Kudtarkar. 2026. Semantic Data Modeling, Graph Query, and SQL, Together at Last?. In 16th Conference on Innovative Data Systems Research, CIDR 2026, Chaminade, CA, USA, January 18-21, 2026. www.cidrdb.org. https://vldb.org/cidrdb/2026/semantic-data-modeling-graphquery-and-sql-together-at-last.html [27] Michael Stonebraker and Joseph M. Hellerstein. 2005. What Goes Around Comes Around. In Readings in Database Systems (4th ed.), Michael Stonebraker and Joseph M. Hellerstein (Eds.). MIT Press, Cambridge, MA, 2–41. [28] Dimitri Surinx, George H. L. Fletcher, Marc Gyssens, Dirk Leinders, Jan Van den Bussche, Dirk Van Gucht, Stijn Vansummeren, and Yuqing Wu. 2015. Relative expressive power of navigational querying on graphs using transitive closure. Log. J. IGPL 23, 5 (2015), 759–788. doi:10.1093/JIGPAL/JZV028 [29] Alfred Tarski. 1941. On the Calculus of Relations. J. Symb. Log. 6, 3 (1941), 73–89. doi:10.2307/2268577 [30] Alfred Tarski and Steven Givant. 1987. A Formalization of Set Theory without Variables. Colloquium Publications, Vol. 41. American Mathematical Society, Providence, RI. [31] Transaction Processing Performance Council. [n. d.]. TPC Benchmark H (Decision Support) Standard Specification. Technical Report. Transaction Processing Performance Council. http://www.tpc.org/tpch/ [32] Alexander van Renen, Dominik Horn, Pascal Pfeil, Kapil Vaidya, Wenjian Dong, Murali Narayanaswamy, Zhengchun Liu, Gaurav Saxena, Andreas Kipf, and Tim Kraska. 2024. Why TPC Is Not Enough: An Analysis of the Amazon Redshift Fleet. Proc. VLDB Endow. 17, 11 (2024), 3694–3706. doi:10.14778/3681954.3682031 [33] Ritchie Vink and Polars Contributors. 2024. Polars: Lightning-fast DataFrame library for Rust and Python. https://github.com/pola-rs/polars