Time to Move on: Querying without Nulls and Bags

Time to Move on: Querying without Nulls and Bags Molham Aref

Leonid Libkin

Wim Martens

RelationalAI

RelationalAI University of Edinburgh

RelationalAI University of Bayreuth

arXiv:2608.10863v1 [cs.DB] 11 Aug 2026

Abstract SQL is the database community’s success story in terms of language design. The key reason for its success is its declarativeness: it gives rise to optimizability, reducing the programmer’s burden significantly. However, given the evolving complexity of problems to solve with query languages, our community needs to re-think some of the fundamental early query language design decisions. Our experience in having worked on the design of Rel (a language for end-to-end relational programming) tells us that it is possible to design, implement, and successfully deploy a language based on fully normalized relations. Such relations avoid what Codd called corrupted relations and what we commonly refer to as bags, and the “harmful” billion dollar mistake that we know as nulls. In the SQL world, it is accepted that bags and nulls are tolerated as an unavoidable evil. We argue that the evil is completely avoidable: reasons offered for justifying bags and nulls evaporate at a closer examination. In addition to debunking them, we also describe opportunities offered by a null-free language with set semantics.

Keywords Declarative languages, SQL, Nulls, Bags ACM Reference Format: Molham Aref, Leonid Libkin, and Wim Martens. 2026. Time to Move on: Querying without Nulls and Bags. In Proceedings of (...). ACM, New York, NY, USA, 6 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnn

1

Introduction

SQL is the database community’s greatest success story in terms of language design. It goes back to 1973 [7], it became an international standard in 1987, and remains extremely relevant today. In addition to being a solid part of our database curricula, it is often ranked as a top language required by employers.1 The main reason for its success is arguably its declarativity: by disconnecting intent and execution, it allows programmers to focus on getting the correct results instead of writing efficient programs to obtain them. By now, SQL is a 40-year-old design, and as is normal for any design so established, popular, and widely used, it has been dissected and analyzed in excruciating detail. With many points of criticism and known issues that programmers face daily, proposals 1 https://spectrum.ieee.org/top-programming-languages-2024 (or 2025), under "jobs".

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. ..., © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-XXXX-X/2018/06 https://doi.org/10.1145/nnnnnnn.nnnnnnn

for modifying and improving SQL have also emerged. In fact, early ideas of replacing SQL (or at least proposing an alternative to it) are already found in Date and Darwen’s Tutorial D [12]. This trend continued later with more modern proposals. Some of them, like [27, 28], try to sequentialize SQL and bring it closer to imperative programming; others, like Rel [2], SaneQL [25] fully adhere to the principle of declarativeness. A key criticism of SQL is the extremely high complexity of SQL Standard. This complexity is inherent in its design as a data sublanguage [9]. That is to say, it is a declarative sublanguage for handling operations with data, with the rest delegated to a general purpose programming language. This approach made perfect sense back in the 1970s and 1980s, when declarative programming had to win over alternative proposals: going fully declarative at once was too ambitious. In fact, it is still an unrealized dream expressed by Jim Gray as the holy grail of automatic programming [18], where the goal is to design a high-level language sufficiently powerful for specifying all application tasks. SQL’s sublanguage design, however, has led to problems. SQL lacks facilities for writing libraries, which entails that every new desired feature has to be added to the language itself, and therefore become part of the standard. Today, the core of the SQL Standard (SQL Foundation) is over 1,500 pages, and the entire standard is well over 4,000 pages. For comparison, the C standard is an order of magnitude smaller. A language that needs to be syntactically extended for each new functionality ends up with hundreds of reserved keywords. This makes queries error-prone: the more complex a language is, the easier it is to make mistakes. Thus, some of the recent language design efforts such as Rel [2] and SaneQL [25] advocate creating a small core of data operations. Most importantly, they both preserve what is truly important about SQL: its declarative nature. Beyond that, there are differences: Rel provides a small core with the ability to write libraries and move beyond the data sublanguage paradigm, while SaneQL keeps the data sublanguage approach and fixes several glaring SQL issues to achieve a less error-prone language. Where these languages differ most is in their approach to data modeling. SQL relations are not the same as the relations originally proposed by Codd. Those relations are sets of tuples of atomic values. SQL violates this in two ways: first, its relations are not tuples of atomic values, since they can contain nulls, which require their own special logic; second, these relations are not sets but multisets (bags), so the same tuple can occur multiple times. Rel eliminates both of these deviations and returns to Codd’s original model. SaneQL, by contrast, treats them as a necessary evil we have to live with. Our main goal is to show that this need not be the case. This should not be seen as a criticism of SaneQL: we think exploring different approaches to language design is an extremely valuable exercise. Our goal is to argue that one need not stick to solutions introduced by SQL four decades ago. Even if it is often

..., 2026,

Aref, Libkin, Martens

2

We are here and are working hard to get here.

how good

Losing Intuition With Bags and Nulls

Multiple issues related to errors or intuition-defying behavior due to duplicates or nulls have been well-documented over the years. Here we present a couple, to set the stage, before debunking some “necessity myths” about nulls and bags in the following sections.

2.1

Intuition-Defying Nulls 

SELECT DISTINCT A FROM R WHERE A NOT IN (SELECT * FROM S)

rs

so

some paramete

m ep ar

am

et er s

Consider relations R(A) and S(A) and three queries:



Figure 1: The Design Space of Query Languages

claimed that we must accept nulls and bags as part of building a relational query language, most reasons offered why we need them can be debunked. This is precisely what we do here. We begin with a few quick examples showing how the logic of nulls and bags differs from the logic programmers are used to, and how it can easily lead to intuition-defying behavior. We then look at nulls and three-valued logic, and debunk three myths: that nulls are needed to model incomplete information; that they are needed to avoid unnecessary joins when one chooses to eliminate nulls through full normalization; and that three-valued logic is necessary to capture the semantics of nulls. Having debunked these, we present the case for a language with no nulls and no threevalued logic, showing that we can dispense with both without losing expressiveness, while gaining more natural queries, additional optimization opportunities, and more. We then turn to bag semantics and examine the arguments offered in its favor: that bags are necessary for correct aggregate computation, that multiplicities may carry built-in semantics, and that bags are needed for performance. We debunk these one by one. We then examine how bags behave in more advanced languages needed for today’s workloads (in particular with recursive computation) and show that bags interact disastrously with recursion, both in terms of performance and semantics. We close the section by making the case for sets, rather than bags, as the core data model. We show that adopting sets uncovers additional optimizations lost under bag semantics, and that it is necessary for the consistency of the language and for a coherent understanding of what tuple counts actually mean. We also argue that simply scattering DISTINCT throughout SQL queries does not fix the problem. We end the introduction with the following thought. Consider Fig. 1. It shows us where we are in terms of query language design. With SQL and newer alternatives, we are not that far off a local peak, but there are better options if we are willing to leave our small local world. Instead of looking for incremental improvements, we should consider climbing a different hill: the one with a clean data model, no sublanguage paradigm, with the ultimate goal of automatic programming at the top. The goal here is to show that we can exit our local world and start a new climb by dispensing with some heavy baggage that came in the shape of nulls and bags.

SELECT DISTINCT A FROM R WHERE NOT EXISTS (SELECT * FROM S WHERE S.A=R.A) SELECT * FROM R EXCEPT SELECT * FROM S





Assume that R and S contain no duplicates; all queries use set semantics. Are they equivalent? Most people would say yes, because they compute R − S. This is true if no nulls are present, but with nulls, the picture changes completely. If R={(1),(NULL)} and S={(NULL)}, the first query produces no tuples, the second outputs the entire relation R, and the third produces a single tuple (1). This happens due to two complementary ways of treating nulls. In the first two queries, all comparisons involving nulls result in the truth value unknown, and the condition in WHERE passes only if it evaluates to true; thus in the first query nothing gets selected while in the second, the subquery produces no tuples making the NOT EXISTS condition true. On the other hand, in set operations, nulls are treated syntactically: suddenly null equals null, accounting for the result. Nulls also invalidate some natural query equivalences that could be useful for optimization. For example, 𝜎𝜃 (𝑅) ∪ 𝜎¬𝜃 (𝑅) need not equal 𝑅: the law of excluded middle does not apply. Likewise, the IN predicate is not the same as membership test: 𝑎 ∈ 𝑅 is not captured by 𝑎 IN 𝑅 in the presence of nulls. Keeping the three-valued logic, varying treatment of nulls depending on query operations, and their divergence from the common logic in one’s head is a tricky proposition. It leads to many errors: “You can never trust the answers you get from a database with nulls” [13].

2.2

Intuition-Defying Bags

This is a classical example, but it never gets old. Suppose we have orders and lineitem relations, and we want to know how much each customer spends on electronics items. One naturally writes this query in SQL:



SELECT o.cust_name, SUM(o.amount) FROM orders o JOIN lineitem l ON o.oid=l.oid WHERE l.category="electronics" GROUP BY o.cust_name



Suppose that Jane placed one $1000 order with two electronics items, a laptop and a phone. The query output will then tell us that Jane spent $2000, because the join produces one row per matching lineitem, duplicating the order amount before it gets summed. Such mistakes are easy to make and hard to spot, as duplicates sneak in unexpectedly. Similarly to nulls, bags also invalidate some query equivalences we take for granted over sets. For example, distributivity 𝑅 ∩ (𝑆 ∪





Time to Move on: Querying without Nulls and Bags

..., 2026,

𝑇 ) = (𝑅 ∩ 𝑆) ∪ (𝑅 ∩ 𝑇 ) is no longer true if ∩ and ∪ are interpreted as INTERSECT ALL and UNION ALL.

3

Nulls and 3-Valued Logic

Nulls are considered "harmful" [14] and "fundamentally flawed" [13]. A related concept of null references in programming languages was branded a "billion dollar mistake" by Hoare, their inventor. So why do we use them? Arguments for nulls and three-valued logic (3VL) usually go along these lines: (1) We need nulls to model incomplete information. (2) We need nulls to avoid joins. (3) 3VL is needed to capture the logic of nulls and provide the necessary expressiveness to SQL queries. We can debunk each of them. Debunk 1: Nulls are Needed for Incomplete Information. Many applications must deal with some sort of incomplete information. However, SQL’s NULL is hardly an ideal tool to handle it for at least two reasons. First, there are multiple types of incomplete information, and a single NULL is inadequate to represent them all. Second, even if we agree that we only model one type of incomplete information, NULL can be completely avoided in the query language. Concerning different types of incomplete information, a recent survey of database practitioners [29] revealed the following most common cases of the use of nulls (with 23 cases identified in total): • NULL means an attribute is non-applicable. • NULL means we have no information whatsoever. • NULL means the value exists but is not known at the moment. • NULL means dirty data. • NULL means fixed known value that we do not want to record (e.g. 0 to avoid runtime division errors, or confidential data). Thus, even if we put NULL in the database, it hardly tells us what is going on. Second, SQL’s NULL can completely be avoided by fully normalizing the data into 6NF. For example, the 6NF decomposition of A

B

5 NULL 7 NULL

NULL 6 8 NULL

has three relations with a tuple_id attribute added: tuple_id

tuple_id

A

tuple_id

B

id_1 id_2 id_3 id_4

id_1 id_3

5 7

id_2 id_3

6 8

We can obtain the original table as the outer join of these. This may be countered by a performance argument, which we address next. Debunk 2: We Need Nulls to Avoid Extra Joins. If we design a query language around fully normalized data as we just suggested, does not this lead to many extra (expensive) joins? We do not think so, and offer several orthogonal reasons.

First and foremost, one major strength of query languages is data independence: the user does not need to worry about how the data is stored. In particular, even if the query language would treat relations as fully normalized, the engine does not necessarily need to. It can choose to store a relation however it wants, one option being a table with nulls. Notice that we are not contradicting ourselves here: we are saying that (a saner version of) nulls may have its place in lower-level languages for databases (using outer joins, for example) and in data structures, but not in the highest-level query language, especially due to the large number of semantic problems they bring. Second, even if a database would internally use several relations to represent a conceptual single table that would result from a join, it is not clear that this representation is computationally more expensive. This is precisely the underlying idea of factorized databases [26], which in fact can perform certain operations faster because they avoid materializing large results. Indeed, several products have now demonstrated that worst-case optimal join algorithms and factorization can temper this performance sacrifice. Third, if we do not have nulls in our query language, do we need to write many joins in our queries? We can just define a view. For coding agents, simple design and consistency are more important. Debunk 3: We Need 3VL to Reason About Nulls. Some believe that reasoning about incomplete information requires an expressive logic. At least that was the reason SQL chose a 3-valued logic (we denote it here by 3VL, though there are many 3-valued logics out there, and SQL chose a particular one, known as Kleene’s logic). However, this is not the case. It is known that using the standard two-valued Boolean logic instead of 3VL makes no change in terms of expressiveness of SQL: whatever we could express with with 3VL, we can still express with Boolean logic. This was first shown for relational calculus queries [11] and then extended to grouping, aggregation, and recursive queries [22]. To give an idea how evaluation based on Boolean logic works, note that three different truth values arise in evaluating conditions in WHERE and HAVING. These appear typically in comparisons conditions 𝑒 𝜔 𝑒 ′ where 𝜔 is one of =, ≠, <, >, ≤, ≥, and 𝑒, 𝑒 ′ are expressions producing values. Of these comparisons, three subsume equality: =, ≤, ≥. Now we can say that 𝑒 𝜔 𝑒 ′ is true if neither 𝑒 nor 𝑒 ′ evaluates to NULL and 𝑒 𝜔 𝑒 ′ holds in the usual sense, or if both 𝑒 and 𝑒 ′ evaluate to NULL and 𝜔 subsumes equality. In all other cases (that is, when one argument is NULL or both are and the comparisons are ≠, <, >), the result is false. Here we treat NULL syntactically, the way grouping and set operations do in SQL. In fact it is not only this specific way of handling nulls with Boolean logic, but every way that is not unreasonable (e.g., saying that NULL equals 42 and nothing else) gives us a language that is as expressive as SQL under 3VL [22].

The Case for No Nulls and No 3VL We believe that query languages are better off without three-valued logic (3VL) and, more radically, without nulls altogether. Dispensing with 3VL. Replacing 3VL with ordinary Boolean logic in query evaluation does not cost us anything in terms of expressiveness. At the same time, it brings several tangible benefits.

..., 2026,

To start with, for the overwhelming majority of queries, the switch changes nothing at all: 3VL and Boolean evaluation agree on all TPC-H and TPC-DS queries but one—over 99% of these standard benchmark queries. Their disagreement is rare. Boolean logic removes a longstanding source of confusion around the third truth value unknown. In SQL, its application depends on where it occurs: in the WHERE-clause and join conditions, unknown is effectively treated as false (only tuples evaluating to true are kept), whereas in constraints it is effectively treated as true (a constraint holds if it is not false). A logic that needs two different conflations to make sense operationally is bound to create confusion leading to programming errors. Furthermore, Boolean logic restores useful algebraic identities that are lost under 3VL, but can facilitate query optimization. For instance, 𝜎𝜃 (𝐸) ∪ 𝜎¬𝜃 (𝐸) = 𝐸 holds under Boolean logic but fails under 3VL, since tuples for which 𝜃 evaluates to unknown are excluded from both sides. For a more detailed list of such recovered identities, related to ALL, SOME, and negation interactions, see [22]. Last but not least, a user study showed that respondents prefer the Boolean semantics by roughly a 2-to-1 margin [22], suggesting that few tears will be shed if future query languages do not use 3VL. Dispensing with nulls. Once 3VL is off the table, nulls lose much of their original motivation, and the more principled position is to do without nulls entirely. This is not a new proposal: it was already taken three decades ago by Date and Darwen in their Tutorial D language [12], where missing information is instead represented explicitly, e.g. via default values or relation-valued attributes, rather than through a distinguished marker value threaded through every operator’s semantics. We are now much better equipped to make this a reality. We have already shown that nulls can be eliminated as a language concept, for example, by resorting to full normalization. The experience of the Rel language [2] whose clean semantics simplifies reasoning tasks and reduces development costs while still delivering good performance, is a testament to the implementability of this principled approach to language design.

4

Bag Semantics

Codd’s reference to bags as corrupted relations [10] is already sufficient to give us an impression of his opinion about them. So, why do our query languages have bag semantics? Arguments for bag semantics typically fall into three categories: (1) We need bags for aggregation. (2) We need bags because multiplicities have semantics. (3) We need bags for performance (e.g., union). We will debunk arguments 1 and 2. While the third argument is true on the surface, we will argue that its disadvantages – rarely discussed – outweigh its benefits. We outline two further, fundamental issues of bag semantics. One is its interaction with iteration or recursion, turning simple computations into ones with astronomical (and beyond) outputs. The other is the inability to provide a clear declarative semantics in the presence of bags: to explain how they are handled, we must rely on procedural languages. Debunk 1: Bags Are Needed for Aggregation. This perceived need is due to thinking of aggregation as first project and then

Aref, Libkin, Martens

aggregate. For example, SELECT SUM(B) FROM R for a relation R(A,B) with tuples (1,2), (2,2) may be thought of as: project on column B and create a bag {{2, 2}} then apply the SUM aggregate to this bag. In principle, a simple change in SQL’s formal semantics can solve this issue. Instead, this query can be defined as ∑︁ 𝑡 .𝐵 𝑡 ∈𝑅

without ever producing a bag with projections on the 𝐵 column. In fact, query language design could stick to fundamental operators from the programming language community, and think about aggregation in terms of reduce or fold operations. Then, the above query is simply reduce[0, 𝑓 ] (𝑅) which iterates over tuples in 𝑅 and adds 𝑡 .𝐵 to the accumulator value 𝑎𝑐𝑐. Here 𝑓 (𝑎𝑐𝑐, 𝑡) = 𝑎𝑐𝑐 + 𝑡 .𝐵. As a case in point, the language Rel [2] works entirely with set semantics and completely supports aggregation. For example, with relations DE of departments and employees and ES of employees and salaries, the average salaries in departments for which the sum of salaries are larger than 100 are computed by def DES(d,e,s) : DE(d,e) and ES(e,s) def q[d] : average[DES[d]] where sum[DES[d]] > 100 The application q[d] effectively performs grouping; we refer the reader to [2]. The key point is that the language never abandons set semantics: the join DES is a set, and aggregations are computed as above, over entire sets, without projecting first. Note that by itself this is not surprising: we have known for a long time that the power of relational languages under bag semantics is the same as of languages under set semantics with added aggregation [19, 23], even though it took several decades to turn this knowledge into a commercially viable implementation. Debunk 2: Multiplicities Should Have Semantics. This sometimes comes in more specific forms, such as needing bags for (a) dealing with duplicate rows in the input data or (b) being able to output a list with duplicate rows. We first discuss these two cases before diving deeper. These arguments are specifically about input and output behavior, which we should separate from the principles of our data model. Why? Because our many possible desired forms of query output should not dictate what the data model is. Sometimes we may want database queries to output an ordered list (say, using ORDER BY). This does not mean that we should change the entire relational database model to use ordered relations: the fact that relations are unordered gives us the freedom to process and optimize queries how we want. As argued in [16], a query language should never leave the data model to provide bespoke user representations for different tasks. It is perfectly fine to separate input/output behavior from the internal data model of systems. There are more reasons why (a) and (b) should not convince us to use bag semantics. If the source data has duplicate rows, it means that some entity that should have been modeled is being overlooked. Thus, bag semantics enables bad modeling. For example, if we read an input file of person names that contains duplicates representing different persons, we should generate person IDs that correspond to the entities (i.e., persons) that these names belong to. A similar argument holds for (b). If we need to produce a list of names for

some output, but are bound to set semantics, we can simply produce unique identifiers for the persons and output (ID, name) pairs. Finally, if multiplicities are important, it is somewhat primitive to represent them through multiple occurrences of a tuple in a table, i.e., in space consuming unary encoding. Decimal or binary encodings seem more natural: instead of producing 42 copies of a tuple in the output, produce the pair (name,42) or (name,101010). In any case, the reader should ask themselves if these points about consuming input and writing output outweigh the long-term advantages of set semantics, see the end of this section. Debunk 3: Performance. A valid argument for bags is that they allow performance improvements for simple operations. In particular, inserting a tuple into a relation can be done without checking if it already exists. Taking the union of two relations can be done by simply appending tables. Projection can be done without duplicate elimination. In fact, this may be the exact reason why early systems used bags and why we still use them five decades later. But are we amputating an arm for the sake of losing weight? While giving some performance gains on the surface, bag semantics costs us many opportunities for query optimization. Every optimization rewrite that is possible under bag semantics is also possible under set semantics. But the converse is not true. The classical example is optimization of many-way joins, or more generally, conjunctive queries (CQs): 𝑅1 ⊲⊳ 𝑅2 ⊲⊳ · · · ⊲⊳ 𝑅𝑛 where 𝑅1, . . . , 𝑅𝑛 are database relations. Under set semantics, we know that there is a unique optimal equivalent query [8]. It can be found in NP, based on NP-completeness of containment 𝑄 1 ⊆ 𝑄 2 of CQs. This result is very robust: • containment of unions of such queries, i.e. 𝐶𝑄 1 ∪ · · · ∪ 𝐶𝑄𝑚 , is also decidable in NP, • so is containment when disequalities (≠) can be used in join conditions (instead of just equijoins). In the case of bags, however: • for the general containment problem, its decidability is still unknown (and even if proved, it is likely the algorithm will be completely impractical), • for the above extensions (union and disequalities), containment becomes undecidable, • some cases remain decidable (e.g. no projection), but algorithms are significantly more complex. CQ containment has been used in a variety of tasks in data integration [17], data exchange [3], answering queries under ontologies [6], to name some. We lose these tools with bags. Recursion. With database tasks growing more diverse and complex, recursion is more and more common. We now offer another thought experiment, addressing the issues of both performance and the meaning of multiplicities for simple recursive queries. As an example, we take the canonical recursive query computing the transitive closure (TC) of a relation. There are two ways to write it: we can connect the non-recursive and the recursive parts by UNION, forcing set semantics, or by UNION ALL, forcing bag semantics. Assume that 𝑅 contains tuples (1, 2), (2, 3), . . . , (𝑁 − 1, 𝑁 ); to make it into a bag, we put two copies of each tuple into 𝑅. We look

..., 2026,

Output size

Time to Move on: Querying without Nulls and Bags

1010 109 108 107 106 105 104 103 102 101

TC(R)/TC(TC(R)) set semantics TC(R) bag semantics TC(TC(R)) bag semantics

timeout

5 6 7 8 9 10 11 12 13 14 15 16 17 18

N

Figure 2: Growth of query outputs in set vs. bag semantics.

at the transitive closure query, and also at a query that applies the transitive closure twice, i.e., TC (TC (𝑅)). Under set semantics, this changes nothing: transitive closure of a relation is transitive, and hence TC (TC (𝑅)) = TC (𝑅), with both having 𝑁 (𝑁 − 1)/2 tuples. Under bags, however, it is a completely different story. Figure 2 plots, on the log scale, the sizes of TC (𝑅) and TC (TC (𝑅)) under set and bag semantics. With set semantics and UNION, we are under 200 tuples for 𝑁 = 18. With bag semantics, TC (𝑅) has hundreds of thousands of tuples for the same 𝑁 , and for TC (TC (𝑅)) we are in the timeout land (with expected size roughly 1.5 · 1010 ); even for 𝑁 = 17 the size is well over a billion tuples. In fact, it takes only 𝑁 = 134 (and thus 266 tuples in 𝑅) for the size of the output to exceed the number of protons in visible universe. Even beyond computational issues, what is the significance of having 64 edges from 3 to 9 in the bag transitive closure or 2048 edges in the TC of TC? Playing devil’s advocate, let us try to counter this argument by saying: no, these numbers have a meaning, they tell you how many times a tuple was derived. This looks reasonable on the surface but upon closer examination, this argument reveals another fundamental problem with bag semantics: it does not exist for declarative languages. The number of derivations of a tuple for a declarative query has no meaning per se until we translate it into a procedural query, and such a translation is far from being unique. Diving deeper, note that early formal definitions of bag semantics [1, 19, 23] were given for procedural languages like relational algebra; even for datalog it was defined procedurally, either in terms of counting proof trees or applying chase and reducing to sets [5, 24]. To understand why
this is so, consider a logical query 𝑞(𝑥, 𝑧) = ∃𝑦 𝑅(𝑥, 𝑦) ∧ 𝑆 (𝑦, 𝑧) , that we can also write as a Datalog rule 𝑞(𝑥, 𝑧):–𝑅(𝑥, 𝑦), 𝑆 (𝑦, 𝑧). The number of occurrences of a tuple (𝑎, 𝑏) Í ¯ denotes in the output is given by 𝑐 #𝑅 (𝑎, 𝑐) · #𝑆 (𝑐, 𝑏), where #𝑅 (𝑢) the multiplicity of a tuple 𝑢¯ in relation 𝑅 [20]. Why this particular expression? Simply because the above conjunctive query written in logical notation translates into 𝑅 Z𝑦 𝑆 = 𝜋𝑥,𝑧 (𝑅 × 𝑆), and the expression we used is the one that corresponds to the well-accepted bag semantics of Cartesian product and projection. In other words, our declarative bag semantics is driven by a particular translation from logic into algebra! But we know well that such a translation, in the set case, is by no means unique: even different textbooks

..., 2026,

present different logic-to-algebra translations. So we somehow end up depending on one a priori chosen translation, which looks as a bizarre choice, to say the least. Even if for CQs it may pretend to have some element of “canonicity” (though this is questionable too), beyond CQs any choice of a translation into a procedural language will have a huge element of arbitrariness in it, extending thus to the semantics of a declarative language itself.

The Case for Sets In terms of query optimization, we already mentioned that every optimization rewrite that is possible for bags is also possible for sets. By sticking to bags, however, we are leaving many optimization opportunities, especially for join optimizations. Another point is consistency. As the scope of query languages continues to grow, it becomes increasingly difficult to apply bag semantics consistently. Recursive queries are becoming increasingly important in query languages for complex workloads involving graph analytics, ontological, predictive, and prescriptive reasoning. The perils of bag semantics are especially noticeable in graph languages such as SPARQL, and the newly released standards GQL and SQL/PGQ. In the former, bag semantics assigned to each path a multiplicity corresponding to how many times it was derived. This however resulted in simple queries with astronomical size output [4]. The common pattern matching language of GQL and SQL/PGQ [15], well aware of this issue, imposed several restrictions. One of them limited the class of available regular expressions, in a way that reduced expressiveness of the language. This is a high price to pay for having duplicates. Worse yet, the pattern matching algorithm of the PGQ and GQL standards enforces duplicate elimination as one of its steps, to reduce the space of possible matches. However, it was not the last step, and subsequent steps, applying classical relational operators under bag semantics, reintroduce duplicates. Thus, sticking to bag semantics makes the number of duplicates essentially meaningless: it has no declarative semantics — it is a consequence of one specific procedural algorithm. Occasionally, one hears an argument “if the user wants sets, they can always use DISTINCT”. This does not hold water however. Such an approach leads to mixing sets and bags with unpredictable semantics. Returning to the example from Section 2.2, if we wrote SELECT DISTINCT instead of SELECT, would it fix the double counting problem? The answer is negative: DISTINCT does not prevent double-counting, as it happens in the join. By the time DISTINCT is applied, the aggregate is already computed, and its value is wrong. It is a much more principled solution to use one semantics throughout, and given problems with bags that set semantics avoids, it better be set semantics.

5

Concluding Remarks

Chamberlin [7] lists three main criticisms of SQL: nulls, duplicates (bags), and impedance mismatch. It is almost like admitting that we actually know what is wrong. In fact, why does SQL have bags and nulls? Is this because of language design reasons or due to performance reasons? If the answer is performance only, is it a case of premature optimization being the root of all evil [21]? Concerning bags, it seems that we only have them for performance reasons: to efficiently compute unions and inserts. However, the

Aref, Libkin, Martens

performance costs of bags down the line are huge: bags tie our hands together when we want to do query optimization. Even worse, they are semantically problematic in the presence of recursion, which means that we are more likely to solve the wrong problem. In our query languages, nulls and 3VL create way more problems than they solve. Going back to Boolean logic recovers optimizations and eliminates semantic inconsistencies. We now know that, in principle, a language based on the first principles — relations as sets of tuples of atomic values — can be designed, implemented, and successfully deployed. We should separate concerns: query languages should hide unnecessary complexity from the user, whether semantic or algorithmic. Nulls and bags may have their place in data structures and lower-level languages, but in query languages it is time to seriously consider getting rid of the old baggage that they are.

References [1] J. Albert. Algebraic properties of bag data types. In VLDB, pages 211–219, 1991. [2] M. Aref et al. Rel: A programming language for relational data. In SIGMOD, pages 283–296, 2025. [3] M. Arenas, P. Barceló, L. Libkin, and F. Murlak. Foundations of Data Exchange. Cambridge University Press, 2014. [4] M. Arenas et al. Counting beyond a yottabyte, or how SPARQL 1.1 property paths will prevent adoption of the standard. In WWW, pages 629–638, 2012. [5] L. Bertossi et al. Datalog: Bag semantics via set semantics. In ICDT, pages 16:1–16:19, 2019. [6] M. Bienvenu and M. Ortiz. Ontology-mediated query answering with datatractable description logics. In Reasoning Web, LNCS 9203, pages 218–307, 2015. [7] D. D. Chamberlin. Early history of SQL. IEEE Ann. Hist. Comput., 34:78–82, 2012. [8] A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In STOC, pages 77–90, 1977. [9] E. F. Codd. A database sublanguage founded on the relational calculus. In SIGFIDET, pages 35–68, 1971. [10] E. F. Codd. The relational model for database management: version 2. AddisonWesley Longman Publishing Co., Inc., 1990. [11] M. Console et al. Propositional and predicate logics of incomplete information. Artificial Intelligence, 302:103603, 2022. [12] H. Darwen and C. J. Date. The third manifesto. SIGMOD Record, 24:39–49, 1995. [13] C. J. Date. SQL and Relational Theory: How to Write Accurate SQL Code. O’Reilly Media, 2009. [14] C. J. Date. Database Technology: Nulls Considered Harmful. Technics Publ., 2024. [15] A. Deutsch et al. Graph pattern matching in GQL and SQL/PGQ. In SIGMOD, pages 2246–2258, 2022. [16] J. Dittrich. A functional data model and query language is all you need. In EDBT, pages 619–626, 2026. [17] A. Doan, A. Halevy, and Z. Ives. Principles of Data Integration. Morgan Kaufmann, 2012. [18] J. Gray. What next?: A dozen information-technology research goals. J. ACM, 50:41–57, 2003. [19] S. Grumbach and T. Milo. Towards tractable algebras for bags. Journal of Computer and System Sciences, 52:570–588, 1996. [20] A. Hernich and P. G. Kolaitis. Foundations of information integration under bag semantics. In LICS, pages 1–12, 2017. [21] D. E. Knuth. Structured programming with go to statements. ACM Comput. Surv., 6:261–301, 1974. [22] L. Libkin and L. Peterfreund. SQL nulls and two-valued logic. In PODS, pages 11–20, 2023. [23] L. Libkin and L. Wong. Query languages for bags and aggregate functions. Journal of Computer and System Sciences, 55:241–272, 1997. [24] I. S. Mumick et al. The magic of duplicates and aggregates. In VLDB, pages 264–277, 1990. [25] T. Neumann and V. Leis. A critique of modern SQL and a proposal towards a simple and expressive query language. In CIDR, 2024. [26] D. Olteanu and J. Závodný. Size bounds for factorised representations of query results. ACM Transactions on Database Systems, 40:2:1–2:44, 2015. [27] PRQL. PRQL: Pipelined relational query language, 2022. [28] J. Shute et al. SQL has problems. we can fix them: Pipe syntax in SQL. Proc. VLDB Endow., 17:4051–4063, 2024. [29] E. Toussaint et al. Troubles with nulls, views from the users. Proc. VLDB Endow., 15:2613–2625, 2022.

Related documents

• Few Rows Tell Them Apart: Equivalence of Queries Mixing Set and Bag Semantics#673610
• The Pragmatics of Empty Names#778073
• In Search of the Semantics of Emptiness#772271
• Tailwind: A Practical Framework for Query Accelerators#155427
• Diva++: Dynamic Range Filtering over Hard Workloads#780919