In pure mathematics and classical logic, collections of items are treated as sets. In a set, an element is either present or absent; duplicates do not exist. Early database theory—including relational algebra, classical Datalog, and description logics—inherited this elegant foundation.
However, real-world database engines (such as SQL and SPARQL) operate on multisets, commonly referred to as bags. In a bag, the exact same record can appear multiple times. This discrepancy is not just a minor implementation detail; it represents a fundamental rift between theory and practice.
To understand why this matters, consider an aggregate query like SUM or COUNT. If a database collapses the collection {5, 5, 10} into the unique set {5, 10}, the sum drops from 20 to 15, and the count drops from 3 to 2. As highlighted by Mudathir Mohamed et al. in Verifying SQL queries using theories of tables and relations, theoretical verification tools or query optimization proofs that assume set semantics can incorrectly validate query rewrites, leading to silent data corruption and inaccurate results in production systems.
To bridge this gap, a major research direction focuses on formalizing bag semantics across database theory, query optimization, knowledge representation, and formal verification.
Defining Multiplicity Formally
To reason about duplicates mathematically, theorists had to find a way to inject "counts" into declarative logic without relying on procedural, non-declarative row identifiers.
An early breakthrough came from Inderpal Singh Mumick et al. in The Magic of Duplicates and Aggregates. The authors proposed that the cardinality of a fact in a logic program should be defined as the number of unique derivation trees that prove that fact. If a system can deduce a conclusion via three distinct logical paths or underlying records, that fact is assigned a multiplicity of three. This allowed researchers to reason about duplicates purely declaratively.
In modern frameworks, this is formalized by replacing sets of elements with a multiplicity function that maps every possible tuple to a non-negative integer representing its occurrence count. For instance, in team semantics—a logical framework used to model data dependencies and statistical independence—Arnaud Durand et al. introduced "multiteam semantics" in Approximation and Dependence via Multiteam Semantics. By replacing sets of variable assignments with multisets, the logic can natively capture the weight and frequency of different observations, aligning formal logic with statistical reality.
The Breakdown of Relational Operators
Why does moving from sets to bags break standard database proofs? The answer lies in how basic relational algebra operators behave when duplicates are preserved.
Consider the projection operator ($\pi$), which selects specific columns from a table. In set semantics, projecting a table automatically eliminates duplicate rows. In bag semantics, those duplicates must be retained. Similarly, the union operator ($\cup$) becomes ambiguous: do we add the counts of matching tuples from both tables (sum-union), or do we take the maximum count between the two (max-union)?
This operational shift complicates query rewriting, particularly in Ontology-Based Data Access (OBDA) and data integration. In OBDA, a high-level conceptual model (an ontology) is used to query underlying relational databases. Charalampos Nikolaou et al. demonstrated in The Bag Semantics of Ontology-Based Data Access that standard unions of conjunctive queries are insufficient for this task. Rewriting queries under bag semantics requires a more sophisticated relational algebra equipped with explicit arithmetic operations and differences to prevent double-counting and accurately track multiplicities.
Set Semantics:
[A, B, B, C] ---Union--- [B, C, D] ===> {A, B, C, D}
Bag Semantics (Sum-Union):
[A, B, B, C] ---Union--- [B, C, D] ===> {A, B, B, B, C, C, D}
This challenge extends to incomplete databases, where some information is missing or represented by null values. As shown by Marco Console et al. in On Querying Incomplete Information in Databases under Bag Semantics, standard relational operations must be carefully adapted to track tuple multiplicities across all possible database completions, making even basic query answering a delicate balancing act.
The Complexity and Verification Frontier
Tracking exact counts instead of binary presence/absence significantly increases computational complexity.
For example, in probabilistic databases—where tuples are associated with a probability of existence—Martin Grohe et al. proved in Probabilistic Query Evaluation with Bag Semantics that a sharp complexity dichotomy exists. While calculating the expected number of results for a query can be surprisingly straightforward, computing the exact probability of obtaining a specific result count is highly intractable for certain query structures.
Despite these hurdles, capturing bag semantics is essential for modern automated verification tools, such as Satisfiability Modulo Theories (SMT) solvers. If an SMT solver cannot reason about duplicate elements, it cannot reliably verify real-world software or database schemas.
To address this, Mudathir Mohamed et al. developed techniques detailed in Solving Set Constraints with Comprehensions and Bounded Quantifiers to extend solvers like cvc5 with set comprehensions and bounded quantifiers. By modeling tables as multisets of tuples and leveraging higher-order operators like map and filter, these solvers can now automatically prove query equivalence or generate concrete counterexample databases when a proposed optimization violates bag semantics.
Key Foundational Work
The Magic of Duplicates and Aggregates (1990) — contributed 3 concept elements to this direction.
Equivalences Among Aggregate Queries with Negation (2002) — contributed 1 concept elements to this direction.