Limitations of Interpretations in Semiring Semantics

arXiv:2611.08474 · cs.DB · Submitted 2026-11-05 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Monus vs. Interpretations in Semiring Semantics".

Jane: Here's the gist of the paper. Interpretations have been widely used in the study of provenance of queries on semiring-annotated databases Here, we consider two different interpretation-based semantics for firstorder formulas in negation normal form, namely, the canonical-interpretation semantics and the compatible-interpretation semantics We show that the resulting query languages cannot express the monus operation on semiring-annotated relations, when the annotations come from the bag semiring or the tropical semiring or the fuzzy semiring Consequently, the semantics of SQL cannot be captured using these interpretation-based semantics.

Tom: Conceptual Framework for Semantics The paper introduces two distinct interpretation-based semantics for first-order formulas in negation normal form: the canonical-interpretation semantics and the compatible-interpretation semantics Canonical-interpretation semantics is a stricter notion than compatible-interpretation semantics because a special interpretation, called the canonical interpretation is associated with every semiring-annotated database, while in compatible-interpretation semantics different interpretations can be used on different databases as long as they are “compatible” with the semiring-annotated database at hand.

Jane: Technical Results on Inexpressibility The main technical result asserts that, in general, the monus operation on semiring-annotated databases cannot be expressed by any first-order formula in negation normal form under the interpretation-based semantics introduced here.

Tom: This inexpressibility result holds true for databases over each of the following three well known semirings: the bag semiring N = (N, +, ·, 0, 1), the tropical semiring T = (R ∪ ∞, min, +, ∞, 0), and the fuzzy semiring F = (

0, 1: , max, min, 0, 1).

Title and authors: Jane: So, moving into the paper's title and authors, "Monus vs. Interpretations in Semiring Semantics," it sets up the entire debate we're hearing about—the tension between the monus operation and how we define semantics.

Tom: The authors are Phokion G. Kolaitis from the University of California Santa Cruz, who is clearly focused on this intersection of database theory and logic.

Lu: Kolaitis’s work here is about formally defining how to use first-order formulas in negation normal form when working with databases that have been annotated with values from a semiring.

Meng: I don't know much about the specific work of Kolaitis, but what this paper is doing is taking the general framework of semiring semantics and testing its limits against the monus operation.

Jane: Exactly. The authors are introducing two specific interpretation-based semantics: canonical-interpretation semantics and compatible-interpretation semantics, to see which one works better for designing a query language.

Tom: And they use the bag semiring N as their primary example because it’s a very common structure in database literature, linking it directly to SQL's operations like set difference.

Lu: The paper is essentially answering the conceptual question of how we can use these interpretation-based semantics to define languages for expressing queries over semiring-annotated databases, which they say hasn't been fully done before

GT17, GT25: .

Meng: So what this means practically is that they are trying to build a formal way to write rules for querying data that has these semiring annotations attached.

Jane: They show that the canonical interpretation is stricter because it assigns one fixed interpretation to every database instance, while compatible allows different databases to use different interpretations as long as they are compatible with the base semiring.

Tom: It’s a formal way of saying that you can have a global rule versus a local rule for how you read the data annotations.

Lu: And their main contribution is proving that neither of these semantics can express the monus operation on relations when those relations are annotated by N, T, or F.

The paper's summary: Jane: So, let's go over what the paper actually summarizes about this entire problem. It boils down to showing that for the bag semiring N, tropical semiring T, and fuzzy semiring F, the monus operation is unexpressible in these two semantic systems.

Tom: That’s a very clear statement: if you have data annotated with any of those three specific structures, you can't write a first-order formula that performs a monus query.

Lu: The paper builds on earlier work to show that the monus operation itself can be characterized by a set of four simple identities in naturally ordered semirings, which is important context for why this operation is so central here

Ame84, Suc24: .

Meng: So the paper isn't just stating a limitation; it’s showing that the limitation is tied to the algebraic structure of these monus-containing semirings.

Jane: Right. They define what it means for a semiring to have a monus operation—it has an addition, multiplication, zero and one, plus this new difference operation that satisfies some specific identities Suc24.

Tom: And they show that regardless of whether you use the canonical or compatible semantics to define your query language, the monus query qm which is R minus S is not definable by any first-order formula in negation normal form.

Lu: This result has immediate consequences: if you try to capture SQL semantics using these interpretation-based methods, it just doesn't work for bag or tropical, and fuzzy semirings.

Meng: So the paper’s summary is essentially a negative result for query language design under these specific constraints—the system fails to model subtraction.

Jane: And they point out that this failure holds even when we restrict our look to databases where the active domains are just single sets, which forces the compatible interpretation to default back to the canonical one.

Tom: That means you can't escape this problem by just playing around with different database structures; it’s inherent in the logic and semantics.

The paper's improvements: Jane: Now for the part where they discuss what improvements they suggest or clarify about their approach, which is actually more about clarifying the limitations of their framework.

Tom: They don't really propose a new way to express monus; instead, they focus on proving that the current framework cannot do it. The improvement is in sharpening the proof by showing exactly why the limitation holds for these specific semirings.

Lu: They show that for bag or tropical or fuzzy semirings, there’s no way to define a query language under canonical-interpretation semantics that supports monus because of those algebraic identities Ame84.

Meng: The improvement is in providing the rigorous link between the abstract algebra—those identities—and the concrete failure to define a query.

Jane: And they also show how this limitation persists even for compatible-interpretation semantics by demonstrating that their specific test cases force any compatible interpretation on those small databases to be the canonical one.

Tom: So, it’s not a fix; it’s more about showing the boundaries of what these two semantics can achieve in terms of modeling monus.

Conclusion: Tom: So to wrap up this paper, "Monus vs. Interpretations in Semiring Semantics," the main implication is that for the bag, tropical, and fuzzy semirings, you cannot use these interpretation-based semantics to define a query language that supports monus.

Jane: The practical reality is that SQL semantics simply can't be captured using either canonical or compatible interpretation methods for these specific database structures.

Lu: This means we need to find an entirely different way to model the query, one that doesn't rely on these two specific semantic paths when subtraction is required.

Meng: For deployment, this tells us that if you’re building a system over bag or tropical data, you won't get subtraction just by using these formal logic rules.

Tom: It suggests we need to look at other proof systems entirely if we want to capture the full scope of relational algebra operations in this context.

Jane: That’s the big picture: the paper shows that these interpretation methods hit a hard wall when trying to model subtraction on bags, tropical, and fuzzy relations.

Lu: We need a new semantic tool that handles monus differently if we want to keep the broader relational algebra connection alive.

Meng: So for now, this means sticking to other approaches for now until we find something else that can handle these algebraic structures properly.

University of California Santa Cruz

cs.DB

Submitted: 2026-11-05

Updated: 2026-11-18

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 79/100

The gist: Interpretations have been widely used in the study of provenance of queries on semiring-annotated databases Here…

Key concepts

Canonical-interpretation semantics
This is a strict interpretation where every database has one fixed special interpretation associated with it. It is more restrictive than the compatible version because there is only one possible way to interpret the data for any given database structure.
Compatible-interpretation semantics
This allows different interpretations to be used on different databases, as long as those interpretations are 'compatible' with the specific database being considered. It offers more flexibility than the canonical approach.
Monus operation
The monus operation is a specific mathematical operation (like set difference) that is used in database queries. The paper investigates whether this fundamental operation can be expressed using first-order logic formulas under these different semantics.
FO(NNF)-formula
This refers to a specific type of first-order logic formula written in negation normal form (NNF). The paper tests if complex database queries, like the monus operation, can be defined using only these types of logical expressions.

Terminology

Summary

Interpretations have been widely used in the study of provenance of queries on semiring-annotated databases Here, we consider two different interpretation-based semantics for firstorder formulas in negation normal form, namely, the canonical-interpretation semantics and the compatible-interpretation semantics We show that the resulting query languages cannot express the monus operation on semiring-annotated relations, when the annotations come from the bag semiring or the tropical semiring or the fuzzy semiring Consequently, the semantics of SQL cannot be captured using these interpretation-based semantics. p. 0

Where the paper says it

Here, we consider two different interpretation-based semantics for firstorder formulas in negation normal form, namely, the canonical-interpretation semantics and the compatible-interpretation semantics. We show that the resulting query languages cannot express the monus operation on semiring-annotated relations, when the annotations come from the bag semiring or the tropical semiring or the fuzzy semiring.

Conceptual Framework for Semantics

The paper introduces two distinct interpretation-based semantics for first-order formulas in negation normal form: the canonical-interpretation semantics and the compatible-interpretation semantics Canonical-interpretation semantics is a stricter notion than compatible-interpretation semantics because a special interpretation, called the canonical interpretation is associated with every semiring-annotated database, while in compatible-interpretation semantics different interpretations can be used on different databases as long as they are “compatible” with the semiring-annotated database at hand.

Technical Results on Inexpressibility

The main technical result asserts that, in general, the monus operation on semiring-annotated databases cannot be expressed by any first-order formula in negation normal form under the interpretation-based semantics introduced here. This inexpressibility result holds true for databases over each of the following three well known semirings: the bag semiring N = (N, +, ·, 0, 1), the tropical semiring T = (R ∪ ∞, min, +, ∞, 0), and the fuzzy semiring F = ([0, 1], max, min, 0, 1). p. 1

Where the paper says it

The main technical result reported here asserts that, in general, the monus operation on semiringannotated databases cannot be expressed by any first-order formula in negation normal form under the interpretation-based semantics introduced here. Actually, we show that this inexpressibilty result holds true for databases over each of the following three well known semirings: the bag semiring N = (N, +, ·, 0, 1), the tropical semiring T = (R ∪ {∞}, min, +, ∞, 0), and the fuzzy semiring F = ([0, 1], max, min, 0, 1).

An immediate consequence of this result is that the semantics of SQL cannot be captured using canonical-interpretation semantics or compatible-interpretation semantics. p. 1
Where the paper says it

Actually, we show that this inexpressibilty result holds true for databases over each of the following three well known semirings: the bag semiring N = (N, +, ·, 0, 1), the tropical semiring T = (R ∪ {∞}, min, +, ∞, 0), and the fuzzy semiring F = ([0, 1], max, min, 0, 1). An immediate consequence of this result is that the semantics of SQL cannot be captured using canonical-interpretation semantics or compatible-interpretation semantics.

Definitions of Query Languages

The paper defines notions for defining queries using interpretation-based semantics, distinguishing between canonical and compatible interpretations. A query is definable under canonical-interpretation semantics if there is a FO(NNF)-formula such that the query on a K-database I is equal to πA(I)[[φ]] for every K-database I. p. 6

Where the paper says it

We say that q is definable under canonical-interpretation semantics if there is a FO(NNF)-formula φ(x1, . , xn) such that q(I) = πA(I) [[φ]] holds for every K-database I = (R1, .

Conversely, it is definable under compatible-interpretation semantics if there exists an interpretation π compatible with A and a FO(NNF)-formula φ such that the query on a K-database I is equal to (π[[φ]](a1,. p. 7
Where the paper says it

We say that q is definable under compatible-interpretation semantics if there is a FO(NNF)-formula φ(x1, . , xn) such that for every K-database I = (R1, .

.., an), if (a1,..., an) ∈ adom(I), 0, if (a1,. p. 3
Where the paper says it

, Rp) be a K-database. The active domain of I, denoted by adom(I), is the set of all elements of D that occur in the support of a relation Ri of I.

.., an) ̸∈ adom(I). p. 3
Where the paper says it

, Rp) be a K-database. The active domain of I, denoted by adom(I), is the set of all elements of D that occur in the support of a relation Ri of I.

Limitations of Interpretation-Based Query Languages

The paper demonstrates that the interpretation-based query languages cannot express the monus operation on K-databases. Specifically, Theorem 2 proves that for three semirings (N, T, F), the monus query qm = Rˆ - Sˆ is not definable by any FO(NNF)-formula under canonical-interpretation semantics. p. 7

Where the paper says it

Let K be one of the following three semirings with monus: • the bag semiring N = (N, +, ×, 0, 1); • the tropical semiring T = (R ∪ {∞}, min, +, ∞, 0); • the fuzzy semiring F = ([0, 1], max, min, 0, 1). Then the monus query qm on K-databases is not definable by any FO(NNF)-formula under canonicalinterpretation semantics.

Furthermore, the proof shows that this limitation also holds for compatible-interpretation semantics because the K-databases used in the proof have singleton sets as their active domains, meaning the only compatible interpretation on adom(I) is the canonical one. p. 1
Where the paper says it

Both these notions give semantics to first-order formulas in negation normal form on semiring-annotated databases. Canonical-interpretation semantics is a stricter notion than compatible-interpretation semantics, because a special interpretation, called the canonical interpretation is associated with every semiring-annotated database, while in compatible-interpretation semantics different interpretations can be used on different databases as long as they are “compatible” with the semiring-annotated database at hand, i.

This leads to Corollary 2, stating that SQL semantics cannot be captured using compatible-interpretation semantics. p. 1
Where the paper says it

Actually, we show that this inexpressibilty result holds true for databases over each of the following three well known semirings: the bag semiring N = (N, +, ·, 0, 1), the tropical semiring T = (R ∪ {∞}, min, +, ∞, 0), and the fuzzy semiring F = ([0, 1], max, min, 0, 1). An immediate consequence of this result is that the semantics of SQL cannot be captured using canonical-interpretation semantics or compatible-interpretation semantics.

Broader Implications for Relational Algebra

The findings imply that there is no version of Codd’s theorem involving relational algebra with monus on one side and compatible-based interpretations on the other side. Since the monus operation on bags is used in the semantics of SQL, this suggests that the semantics of SQL cannot be captured using either canonical-interpretation semantics or compatible-interpretation semantics. p. 1

Where the paper says it

Actually, we show that this inexpressibilty result holds true for databases over each of the following three well known semirings: the bag semiring N = (N, +, ·, 0, 1), the tropical semiring T = (R ∪ {∞}, min, +, ∞, 0), and the fuzzy semiring F = ([0, 1], max, min, 0, 1). An immediate consequence of this result is that the semantics of SQL cannot be captured using canonical-interpretation semantics or compatible-interpretation semantics.

Corollary 1 further shows that for the provenance semiring N[X], the monus query qm on N[X]-databases is not definable by any FO(NNF)-formula under canonical-interpretation semantics. p. 6
Where the paper says it

• Let q be a n-ary query on K-databases. We say that q is definable under canonical-interpretation semantics if there is a FO(NNF)-formula φ(x1, .

References

[Ame84] K. Amer. Equationally complete classes of commutative monoids with monus, Algebra Universalis, 18:129–131, 1984

[BKN25] Guillermo Badia, Phokion G. Kolaitis, and Carles Noguera. p. 0

Where the paper says it

Interpretations in Semiring Semantics Phokion G. Kolaitis∗ University of California Santa Cruz kolaitis@ucsc.

Codd’s theorem for databases over semirings, Proc. p. 0
Where the paper says it

Specifically, in [BKN25], it was shown that, relational algebra with the monus as the semantics of difference can express the same queries on semiring-annotated databases as first-order logic with the (‘but not’) connective does. This result not only generalizes Codd’s classical theorem about relational algebra and relational calculus [Cod72], but also yields an analogous theorem for bag databases, since SQL uses the monus operation on the natural numbers to give semantics to the difference operation on bags.

ACM Manag. Data, 3(5):277:1–277:26, 2025

[Cod70] Edgar F. Codd. A relational model of data for large shared data banks, Communications of the ACM, 13(6):377–387, 1970

[Cod72] Edgar F. Codd. Relational completeness of data base sublanguages, In R. p. 0

Where the paper says it

1 Introduction During the past two decades, there has been a growing body of research on semiring-annotated databases, where the tuples in the relations of a database are annotated with values from some semiring of interest. This approach provides a unifying framework, known as semiring semantics, that contains as special cases both standard relational databases (as the databases over the Boolean semiring B = ({0, 1}, ∨,∧, 0, 1}) and bag databases (as the databases over the bag semiring N = (N, +, ×, 0, 1)).

Rustin, editor, Proceedings of 6th Courant Computer Science Symposium (May 24–25, 1971: New York, N.Y.), pages 65–98. Prentice-Hall, 1972

[DGNT21] Katrin M. Dannert, Erich Gr¨adel, Matthias Naaf, and Val Tannen. p. 0

Where the paper says it

This result not only generalizes Codd’s classical theorem about relational algebra and relational calculus [Cod72], but also yields an analogous theorem for bag databases, since SQL uses the monus operation on the natural numbers to give semantics to the difference operation on bags. Gr¨adel and Tannen [GT17, GT25] gave semantics to first-order formulas in negation normal form using interpretations.

Semiring provenance for fixed-point logic, In Christel Baier and Jean Goubault-Larrecq, editors, 29th EACSL Annual Conference on Computer Science Logic, CSL 2021

[DMRT14] Daniel Deutch, Tova Milo, Sudeepa Roy, and Val Tannen. Circuits for datalog provenance, In Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy, editors, Proc. p. 0

Where the paper says it

The main focus of [GKT07] was on the provenance of unions of conjunctive queries for which intuitive and unambiguous semiring semantics can be given. In the same paper, semiring semantics were also given to Datalog programs (see also [DMRT14]); later on, semiring semantics were given to richer formalisms supporting recursion, such as least-fixed point logic [DGNT21].

17th International Conference on Database Theory (ICDT), Athens

[GKT07] Todd J. Green, Grigoris Karvounarakis, and Val Tannen. p. 0

Where the paper says it

This approach provides a unifying framework, known as semiring semantics, that contains as special cases both standard relational databases (as the databases over the Boolean semiring B = ({0, 1}, ∨,∧, 0, 1}) and bag databases (as the databases over the bag semiring N = (N, +, ×, 0, 1)). The catalyst for this investigation was the paper by Green, Karvounarakis, and Tannen [GKT07], who used semirings of polynomials to formalize and study the provenance of database queries.

Provenance semirings, In PODS 2007 Proceedings of the Twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of Database Systems

[GP10] Floris Geerts and Antonella Poggi. On database query languages for K-relations, Journal of Applied Logic, 8(2):173–185, 2010

[GT17] Erich Gr¨adel and Val Tannen. Semiring provenance for first-order model checking, CoRR, abs/1712. p. 1

Where the paper says it

atoms and negated atoms to arbitrary first-order formulas in negation normal form. While interpretations have been successful in formalizing and studying the provenance of first-order formulas in negation normal form, they have not been used to design languages for expressing queries over semiringannotated databases so far, the main reason being that [GT17, GT25] do not give interpretation-based semantics to first-order formulas in negation normal form on semiring-annotated databases.

01980, 2017

[GT25] Erich Gr¨adel and Val Tannen. Provenance analysis and semiring semantics for firstorder logic, In Model Theory, Computer Science, and Graph Polynomials, pages 351–401. p. 0

Where the paper says it

This approach provides a unifying framework, known as semiring semantics, that contains as special cases both standard relational databases (as the databases over the Boolean semiring B = ({0, 1}, ∨,∧, 0, 1}) and bag databases (as the databases over the bag semiring N = (N, +, ×, 0, 1)). The catalyst for this investigation was the paper by Green, Karvounarakis, and Tannen [GKT07], who used semirings of polynomials to formalize and study the provenance of database queries.

Birkh¨auser, 2025

[KPVW25] Phokion G. Kolaitis, Nina Pardal, Jonni Virtema, and Jef Wijsen. p. 0

Where the paper says it

Interpretations in Semiring Semantics Phokion G. Kolaitis∗ University of California Santa Cruz kolaitis@ucsc.

Rewriting consistent answers on annotated data, Proc. p. 0
Where the paper says it

Here, we consider two different interpretation-based semantics for firstorder formulas in negation normal form, namely, the canonical-interpretation semantics and the compatible-interpretation semantics. We show that the resulting query languages cannot express the monus operation on semiring-annotated relations, when the annotations come from the bag semiring or the tropical semiring or the fuzzy semiring.

ACM Manag. Data, 3(2):110:1–110:26, 2025

[Mon16] Mika¨el Monet. Example of a naturally ordered semiring which is not an msemiring, https://math. p. 2

Where the paper says it

The semiring N[X] is called the provenance semiring because of its use in the study of database provenance, as initiated in [GKT07]. It should be pointed out that there are naturally ordered semiring that cannot be expanded to a semiring with monus; for a concrete example, see [Mon16].

stackexchange.com/questions/1966858/example-of-a-naturallyordered-semiring-which-is-not-an-msemiring, 2016

[Suc24] Dan Suciu.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Canonical-interpretation semantics can be used to define queries by restricting them to formulas definable under canonical-interpretation semantics, such as There is a FO(NNF)-formula φ(x1,..., xn) such that q(A) = πA[[φ]] holds for every K-structure A.

  2. The system can distinguish between queries definable by canonical-interpretation semantics and those definable by compatible-interpretation semantics, as shown in the example where q∗ is definable under the compatible-interpretation semantics, but it is not definable under the canonical-interpretation semantics.

  3. For databases over bag semirings N, tropical semirings T, and fuzzy semirings F with monus operations, the system can be designed to recognize that certain queries like qm = Rˆ - Sˆ are not definable by any FO(NNF)-formula under canonical-interpretation semantics.

  4. The system can utilize the fact that the compatible-interpretation semantics suffer from the same limitation on every positive semiring with monus that contains an isomorphic copy of the bag semiring N, allowing for a broader understanding of query language limitations.

Abstract

Interpretations have been widely used in the study of provenance of queries on semiring-annotated databases. Here, we consider two different interpretation-based semantics for first-order formulas in negation normal form, namely, the canonical-interpretation semantics and the compatible-interpretation semantics. We show that the resulting query languages cannot express the monus operation on semiring-annotated relations, when the annotations come from the bag semiring or the tropical semiring or the fuzzy semiring. Consequently, the semantics of SQL cannot be captured using the interpretation-based semantics considered here.

Sources

Related papers