Semirings in Databases, Automata, and Logic

Semiring semantics for first-order logic evaluates formulae not just to true or false but to values from a commutative semiring. Depending on the underlying semiring, this allows us to track descriptions of the atomic facts that are responsible for the truth of a statement or practical information about the evaluation such as costs or confidence. Also classical semantics appears as a special case when the Boolean semiring is used, which raises the question to what extent model-theoretic results can be generalized beyond the Boolean semiring and how this relates to the algebraic properties of the underlying semiring. In this talk, we investigate the availability of compactness, which states that a set of sentences is satisfiable if every finite subset is. By defining satisfiability as the existence of non-zero valuations, this implication can be generalized to every absorptive semiring. For the, in Boolean semantics equivalent, formulation via entailment, the situation is different: Based on an order on the semiring, the entailment relation naturally extends to semiring semantics, but this yields a stronger variant of compactness, which fails for the tropical semiring, the Łukasiewicz semiring, and the semirings of generalized absorptive polynomials. However, it still holds for finite semirings and (possibly infinite) lattice semirings.

Codd’s Theorem, a fundamental result of database theory, asserts that relational algebra and relational calculus have the same expressive power on relational databases. We explore Codd’s Theorem for databases over semirings and establish two different versions of this result for such databases: the first version involves the five basic operations of relational algebra, while in the second version the division operation is added to the five basic operations of relational algebra. In both versions, the difference operation of relations is given semantics using semirings with monus, while on the side of relational calculus a limited form of negation is used. The reason for considering these two different versions of Codd’s theorem is that, unlike the case of ordinary relational databases, the division operation need not be expressible in terms of the five basic operations of relational algebra for databases over an arbitrary positive semiring; in fact, we show that this inexpressibility result holds even for bag databases.

Some applications of semirings require infinitary semirings with addition and multiplication operators over infinite collections of values. For example, in semiring semantics for first-order logic, existential and universal quantifiers over infinite domains are interpreted using infinitary addition and multiplication, respectively. In order to guarantee well-defined and informative semiring semantics in the infinitary setting, infinitary operations must satisfy core algebraic properties, such as distributivity and invariance under partition and re-ordering of the operands, which are analogous to associativity and commutativity from the finite setting.

We present an overview of infinitary semirings and precise definitions of their core algebraic properties, and we discuss further properties such as compactness. It turns out that some semirings do not admit infinitary operations, some semirings must be extended in order to allow infinitary operations, and other semirings, such as semirings induced by complete lattices, naturally admit infinitary operations. Finally, we outline the impact of infinitary operations on free polynomial semirings, which are used for provenance analysis in logic, databases and game theory. Our analysis shows that, with suitable definitions for infinitary semirings, large parts of the theory of semiring provenance can be successfully generalized to infinite domains.

The tutorial highlights a recent reinterpretation of certain parts of computational complexity theory from the viewpoint of a weighted automata theorist. It explains how the framework of weighted Turing machines over semirings can be used to capture various sorts of quantitative complexity classes – such as those of counting and optimisation problems – in a consistent manner as instances of weighted complexity classes over different semirings. Several basic results about the classical complexity classes of decision problems turn out to generalise to this weighted setting, while new appealing connections to weighted logics arise. The tutorial gives a brief overview of the most substantial observations of this kind.

Many semirings used in semiring semantics are naturally ordered and admit an additional subtraction-like operation, often called monus. It turns out that multiplication-free reducts of such semirings are very well known in universal algebra and algebraic logic under the name of dual hoops. A dual hoop is an algebra $𝐀=(A;+,-,0)$ such that $(A;+,0)$ is a commutative monoid, and moreover the following identities hold:

• $\mathrm{■}$

  $x-x=0$,

• $\mathrm{■}$

  $(x-y)+y=(y-x)+x$,

• $\mathrm{■}$

  $x-(y+z)=(x-y)-z$.

This implies that $x\le y\iff x-y=0$ defines an order, $-$ is a co-residual of $+$ in this order, and moreover the order is natural. In algebraic logic, these algebras are more often presented in the order-dual form, with $\cdot$, $\to$ and $1$, so from now on I will always speak of hoops, relying on the reader to identify the correct order.

Hoops were first considered by Bosbach in [1, 2], then studied by Büchi and Owens in [3], and then investigated thoroughly by Blok and Ferreirim in [4]. Hoops have a number of pleasant algebraic properties, and a number of them follow from something more general than the hoop structure, namely, from the fact that they are subtractive. The property of subtractivity was isolated and thoroughly studied by Aglianò and Ursini in a series of articles starting from [5] (with a prequel by Ursini). The hoop structure adds natural (in the technical sense) residuated order to subtractivity, yelding algebras resembling ordered rings.

Furthermore, expanding a hoop to a semiring preserves the pleasant algebraic properties alluded to above. The theory of such expansions was studied, somewhat more generally, by Blok and Pigozzi in [6].

My talk will be a sightseeing tour, introducing such expanded hoops and presenting a few examples: in particular showing that some commonly used semirings such as $\mathbb{N}[X]$ have an implicit dual hoop structure.

A recent research topic in database theory is the computational complexity of resilience of queries. For a fixed conjunctive query, the problem is to compute the number of facts that need to be removed from a given database so that it does not satisfy the query. Mathematically, this problem can be viewed as removing tuples from relations of a relational structure so that it does not satisfy a fixed primitive positive sentence. In this talk, I will explain how resilience problems can be viewed as valued constraint satisfaction problems (VCSPs) of structures that are finite or at least finite-like (in the sense that they have an oligomorphic automorphism group). A VCSP is parameterized by a valued structure, which consists of a domain and cost functions, each defined on some finite power of the domain with values in the semiring of rational numbers extended with positive infinity. Building on the known results about VCSPs on finite domains, we explore how the setting can be generalized to infinite domains and give some general powerful hardness and tractability conditions for the resilience problem.

Datalogo is an extension of Datalog that allows for aggregation and recursion over an arbitrary commutative semiring. Unlike Datalog, the natural iterative evaluation of some Datalogo programs over some semirings may not converge. It is known that the commutative semirings for which the iterative evaluation of Datalogo programs is guaranteed to converge are exactly those semirings that are stable.

Previously, the best known upper bound on the number of iterations until convergence over $p$-stable semirings is exponential in data complexity. In this talk, we present a recent finding that the native iterative algorithm for Datalogo converges in polynomial time.

Working with weighted automata naturally leads to the problem of the definition of the (Kleene) star operation on the semiring of (formal power) series. And proving that rational series are realised by weighted finite automata (one direction of the Kleene Theorem) may require to establish the identity: ${(s_0+s_p)}^{\ast }={(s_0)}^{\ast }{(s_p{(s_0)}^{\ast })}^{\ast }$ where $s_0$ and $s_p$ are respectively the “constant term” and the “proper part” of a series $s$.

In my book “Elements of Automata Theory”, I gave a proof of the above identity under the hypothesis that the weight semiring has the property that the product of two summable families is a summable family. I called such semirings “strong” and even though all semirings that I knew are strong, I stated the conjecture that there should exist some semirings which are not strong.

I have presented the problem but for want of time, I have not been able to describe the example of a semiring which is not strong that my colleague David Madore gave me and that will be the subject of a forthcoming publication. At least, I was able to announce the existence of such a semiring which justifies the title.

In this talk, we ask the following question: given a Boolean Conjunctive Query, what is the smallest circuit that computes the provenance polynomial of the query over a given semiring? We answer this question by giving upper and lower bounds. We show a circuit construction that matches this bound when the semiring is idempotent. The techniques we use combine several central notions in database theory: provenance polynomials, tree decompositions, and disjunctive Datalog programs. We extend our results to lower and upper bounds for formulas. Finally, we briefly present open problems related to circuit constructions.

We study consistent answers of queries over databases annotated with values from a naturally ordered positive semiring. In this setting, the consistent answers of a query are defined as the minimum of the semiring values that the query takes over all repairs of an inconsistent database. The main focus is on self-join free conjunctive queries and key constraints, which is the most extensively studied case of consistent query answering over standard databases. We introduce a variant of first-order logic with a limited form of negation, define suitable semiring semantics, and establish that the consistent query answers of a self-join free conjunctive query under key constraints are rewritable in this logic if and only if the attack graph of the query contains no cycles. This result generalizes an analogous result of Koutris and Wijsen for ordinary databases, but also yields new results for a multitude of semirings, including the bag semiring, the tropical semiring, and the fuzzy semiring. Moreover, we relate our logic to particular arithmetic circuit complexity classes defined over semirings.

A query algorithm based on homomorphism counts is a procedure for determining whether a given instance satisfies a property by counting homomorphisms between the given instance and finitely many predetermined instances. In a left query algorithm, we count homomorphisms from the predetermined instances to the given instance, while in a right query algorithm we count homomorphisms from the given instance to the predetermined instances. Homomorphisms are usually counted over the semiring $\mathbb{N}$ of non-negative integers; it is also meaningful, however, to count homomorphisms over different semirings, including the Boolean semiring $𝔹$, where the homomorphism count indicates whether or not a homomorphism exists. I will present some results from joint work with Victor Dalmau, Phokion G. Kolaitis and Wei-Lin Wu (ICDT 2024), where we compare the relative expressive power of query algorithms over $\mathbb{N}$ and over $𝔹$. One of the main results asserts that if a property is closed under homomorphic equivalence, then that property admits a left query algorithm over $𝔹$ if and only if it admits a left query algorithm over $\mathbb{N}$.

Uncertainty arises naturally due to data quality issues such as missing values, constraint violations, and outliers. As the ground truth clean version of a dirty database is typically not recoverable, there is a need to reason about all possible outcomes of computations over all possible clean versions of the database and to determine which outcomes will be certainly returned by the computation irrespective of uncertainty about the ground truth clean dataset. These problems have been studied in reachability analysis in control theory and in the context of certain answers and consistent query answering in databases. As both problems are known to be computationally hard for many interesting classes of computation, there is a need for conservative approximations: under-approximate what is certainly known to be true and over-approximate what is possibly true. In this talk, I will introduce techniques for computing such approximations for relational queries, yielding a query semantics for uncertain data for full relational algebra queries with aggregation and sorting-based operations that has PTIME data complexity and an approach for training and inference with linear models where both the training data and test data may be dirty. On the side of over-approximating all possible outcomes both approaches are shown to be instances of abstract interpretation, a technique from programming languages for over-approximating a set of inputs as an element from a so-called abstract domain and for computations in the abstract domain that preserve this over-approximation. In the cases of relational queries, $K$-relations over a naturally-ordered semiring $K$ can be used as the abstract domain and standard $K$-relational query semantics is sufficient to preserve the over-approximation. To deal with aggregation and value uncertainty, the domain of these $K$-relations are intervals. In case of machine learning, the abstract domain of zonotopes, a restricted type of convex polytopes expressed as affine transformations of the unit hypercube, is used to encode uncertainty. This domain has the advantage of being able to encode correlations between values, but necessitates new methods for computing closed form solutions to models that will be briefly introduced in this talk.

An additively-idempotent semiring is a semiring whose addition is an idempotent operation. In such a semiring, one can define a partial ordering, called the natural partial ordering, which is compatible both with addition and multiplication, and has the zero as the smallest element. Relative to the natural partial ordering, an additively-idempotent semiring is positively ordered, and besides, it forms an upper semilattice in which the binary supremum operation coincides with addition. In the case when that upper semilattice is complete, in the sense that every subset, whether finite or infinite, has a supremum, then it is convenient to treat infinite suprema as infinite sums, seeing that they satisfy all properties from the definition of infinite addition. If, in addition, infinite distributive laws hold, then we say that the considered semiring is a complete additively-idempotent semiring. The class of such semirings is quite broad and includes many important types of semirings, such as complete max-plus semirings, complete min-plus (tropical) semirings, as well as various semirings that are semiring reducts of algebras widely used in fuzzy set theory.

The key property of complete additively-idempotent semirings is the existence of residuation, that is, the existence of a pair of binary operations adjoined to multiplication, which enable certain types of inequations and equations to be solved in such a semiring. In addition, residuation is transferred to matrices and vectors over such a semiring, which gives the possibility to solve various inequalities and equations involving matrices and vectors. The purpose of this talk is to show how residuation can be applied in solving some very important problems in weighted automata theory (containment and equivalence, simulations and bisimulations, state reduction), in social network analysis (positional analysis, blockmodeling) and modal logics.

The tree languages recognizable by deterministic top-down tree automata form a proper subclass $D$ of the class of regular tree languages, and this proper containment also applies to its (strictly larger) Boolean closure $\mathrm{BC}(D)$. We present two results around the decades-long open problem whether for regular tree languages one can decide membership in $\mathrm{BC}(D)$. First, a characterization of $\mathrm{BC}(D)$ by a natural extension of deterministic top-down tree automata is presented, giving a convenient method to show that certain regular tree languages are outside $\mathrm{BC}(D)$. Secondly, it is shown that, for fixed $k$, it is decidable whether a regular tree language is a Boolean combination of $k$ tree languages of $D$.

In the paper “Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs” to be presented at PODS 2025, we proved that a Datalogo program converges after a polynomial number of steps. The convergence time is roughly $𝒪(p{n}^4)$, where $n$ is the output size. The best known lower bound is $\mathrm{\Omega }((p+1)n)$.

The open problem is to close this gap. We think that an upper bound of $𝒪((p+1)n)$ is possible.

Many semirings have a natural structure of “semiring with monus”, i.e. they possess a term operation which acts as a dual implication and it forms a residuated pair with $+$ w.r.t. the natural ordering. However always asking such term to be present can cause unwanted problems with the current understanding of the theory. Of course it is possible to formulate the definitions in such a way that a semiring with monus is an algebra (in the universal algebraic sense). This suggests that a way out could be solving the following problem.

This could be useful because

1. 1.

   from the general theory we know that this class is at least a quasivariety, so it has strong structural properties;

2. 2.

   the embedding allows one to use the monus operation “as if it were present”, but without having it interfere with the (quasi)equational properties of the class.

The equivalences of statements $1$ and $2$, $2$ and $3$ respectively $3$ and $4$ are fundamental theorems of Schützenberger [1], McNaughton and Papert [2] resp. Kamp [3]. A proof of these and more equivalences can be found in the survey by Diekert and Gastin [4]. This raises the question whether analogous results hold for weighted languages $s:{\mathrm{\Sigma }}^{\ast }\to 𝒮$, where $𝒮$ is a semiring.

• $1^{\prime }$

  It is still unclear how statement $1$ shall be translated to the weighted setting. A star-free language in the classical sense is a language that can be constructed from finite languages using Boolean operators, including complementation, and concatenation, but no Kleene star. In the semiring setting, the problem arises what to do with the complement.

• $2^{\prime }$

  For statement $2$, an adequate translation is already known: $s$ is called aperiodic if $s=⟦𝔄⟧$ for some aperiodic, polynomially ambiguous NFA $𝔄$. Polynomially ambiguous means that $𝔄$ shall only admit polynomially many paths for any input.

• $3^{\prime }$

  Statement (3) can be translated to: $s$ is definable in weighted $\mathrm{FO}$.

• $4^{\prime }$

  It is still open to define a suitable weighted version of $\mathrm{LTL}$.

First results on formulations of statements $1^{\prime }$ and $2^{\prime }$ and their equivalence are contained in [5]. An equivalence of statements $2^{\prime }$ and $3^{\prime }$ was given more recently in [6].

There are natural formulations of a weighted $\mathrm{LTL}$ for which the implication $4^{\prime }$ implies $3^{\prime }$ is straightforward. The difficulty is to obtain an equivalence. An ideal result would be a formulation of a weighted $\mathrm{LTL}$ which, possibly through the implication of $4^{\prime }$ implies $2^{\prime }$, would lead to procedures for quantitative model checking, similar to the seminal developments for the unweighted case.

In summary, it is still open to find adequate formulations for statements $1^{\prime }$ and $4^{\prime }$ and to prove or disprove their equivalence to the remaining statements.

The conjunctive query containment problem asks: given two conjunctive queries $q$ and $q^{\prime }$ of the same arities, is it true that on every relational database $D$, it holds that $q(D)\subseteq q^{\prime }(D)$?

In 1977, Chandra and Merlin showed that, for standard relational databases, this problem is NP-complete [1]. In 1993, Chaudhuri and Vardi raised the question of whether or not the conjunctive query containment problem is decidable for bag databases, i.e., when the databases considered are databases over the semiring $(\mathbb{N},+,\times ,0,1)$ of the natural numbers [2]. In spite of concerted efforts by several different groups of researchers, the conjunctive query containment problem for bag databases remains open to date. It is known, however, that it the containment problem for bag databases becomes undecidable if slightly larger classes of queries are considered, such as unions of conjunctive queries [3] or conjunctive queries that include negated equalities as atoms [4].

It should be noted that the conjunctive query containment problem is also meaningful for databases over naturally ordered semirings. Results concerning the decidability and complexity of this problem over such semirings have been obtained by T. J. Green in 2011 [5] and by Kostylev, Reutter, and Salamon in 2014 [6].