Convergence of Datalog over (Pre-) Semirings

We present here a high-level overview of the main results in this paper. We start by recalling the syntax of a (traditional) datalog program $\Pi$, which consists of a set of rules of the form:

(1)

$\displaystyle R_{0}(\bm{X}_{0})$

$\displaystyle\text{ :- }R_{1}(\bm{X}_{1})\wedge\cdots\wedge R_{m}(\bm{X}_{m})$

where $R_{0},\ldots,R_{m}$ are relation names (not necessarily distinct) and each $\bm{X}_{i}$ is a tuple of variables and/or constants. The atom $R_{0}(\bm{X}_{0})$ is called the head, and the conjunction $R_{1}(\bm{X}_{1})\wedge\cdots\wedge R_{m}(\bm{X}_{m})$ is called the body. A relation name that occurs in the head of some rule in $\Pi$ is called an intensional database predicate or IDB, otherwise it is called an extensional database predicate or EDB. The EDBs form the input database, which is denoted $I$, and the IDBs represent the output instance computed by $\Pi$, which we denote by $J$. The finite set of all constants occurring in $I$ is called the active domain of $I$, and denoted $\textsf{ADom}(I)$. The textbook example of a datalog program is one that computes the transitive closure of a graph defined by the edge relation $E(X,Y)$:

	$\displaystyle T(X,Y)$	$\displaystyle\text{ :- }E(X,Y)$
	$\displaystyle T(X,Y)$	$\displaystyle\text{ :- }T(X,Z)\wedge E(Z,Y)$

Here $E$ is an EDB predicate, and $T$ is an IDB predicate. Multiple rules with the same head are interpreted as a disjunction, and in this paper we prefer to combine them in a single rule, with an explicit disjunction. In particular, the program above becomes:

(2)

$\displaystyle T(X,Y)$

$\displaystyle\text{ :- }E(X,Y)\vee\exists_{Z}(T(X,Z)\wedge E(Z,Y))$

The semantics of a datalog program is the least fixpoint of the function defined by its rules, and can be computed by the naïve evaluation algorithm, as follows: initialize all IDBs to the empty set, then repeatedly apply all rules, updating the state of the IDBs, until there is no more change to the IDBs. The algorithm always terminates in time polynomial in $\textsf{ADom}(I)$.

We introduce $\text{\sf datalog}^{\circ}$, a language that generalizes datalog to relations over a partially ordered, commutative pre-semiring, or POPS. A POPS, $\bm{P}$, is an algebraic structure with operations $\oplus,\otimes$ on a domain $P$, which is also a partially ordered set with an order relation $\sqsubseteq$ and a smallest element $\bot$. (Formal definition is in Sec. 2). For example, the Boolean semiring $\mathbb{B}$ forms a POPS where $(\oplus,\otimes)=(\vee,\wedge)$, over domain $\{0,1\}$, and the order relation is $0\leq 1$. For another example, the tropical semiring, Trop, consists of the real numbers $\mathbb{R}$, the operations are $\min,+$, and the order relation $x\sqsubseteq y$ is the reverse of the usual order $x\geq y$. If we restrict the tropical semiring to the non-negative reals and infinity, $\mathbb{R}_{+}\cup\infty$, then we denote the POPS by $\text{\sf Trop}^{+}$. For a fixed POPS $\bm{P}$, a $\bm{P}$-relation of arity $k$ is a function that maps all $k$-tuples over some domain to values in $\bm{P}$; for example, a standard relation is a $\mathbb{B}$-relation, where $\mathbb{B}$ is the Boolean semiring, while a relation with duplicates (a bag) is an $\mathbb{N}$-relation. A $\text{\sf datalog}^{\circ}$ program consists of a set of rules, e.g. like (2), where all relations are $\bm{P}$-relations, and the operators $\wedge,\vee,\exists_{Z}$ are replaced by $\otimes,\oplus,\bigoplus_{Z}$, and its semantics is defined as its least fixpoint, when it exists, or undefined otherwise. We will illustrate the utility of $\text{\sf datalog}^{\circ}$ through multiple examples in this paper, and give here only a preview.

The least fixpoint of $\text{\sf datalog}^{\circ}$, if exists, can be computed by the naïve algorithm, quite similar to datalog: initialize all IDBs to $\bot$, then repeatedly apply all rules of the $\text{\sf datalog}^{\circ}$ program, obtaining an increasing chain of IDB instances, $J^{(0)}\sqsubseteq J^{(1)}\sqsubseteq J^{(2)}\sqsubseteq\cdots$ When $J^{(t)}=J^{(t+1)}$, then the algorithm stops and returns $J^{(t)}$; in that case we say that the $\text{\sf datalog}^{\circ}$ program converges in $t$ steps, or we just say that it converges; otherwise we say that it diverges. Traditional datalog always converges, but this is no longer the case for $\text{\sf datalog}^{\circ}$ programs. There are five possibilities, depending on the choice of the POPS $\bm{P}$:

1. (i)

   For some $\text{\sf datalog}^{\circ}$ programs, $\bigvee_{t}J^{(t)}$ is not the least fixpoint.

2. (ii)

   Every $\text{\sf datalog}^{\circ}$ program has the least fixpoint $\bigvee_{t}J^{(t)}$, but may not necessarily converge.

3. (iii)

   Every $\text{\sf datalog}^{\circ}$ program converges.

4. (iv)

   Every $\text{\sf datalog}^{\circ}$ program converges in a number of steps that depends only on $|\textsf{ADom}(I)|$.

5. (v)

   Every $\text{\sf datalog}^{\circ}$ program converges in a number of steps that is polynomial in $|\textsf{ADom}(I)|$.

In this paper, we will only consider data-complexity (DBLP:conf/stoc/Vardi82, ), where the $\text{\sf datalog}^{\circ}$ program is assumed to be fixed, and the input consists only of the EDB instance $I$.

We study algebraic properties of the POPS $\bm{P}$ that ensure that we are in one of the cases (iii)-(v); we do not address cases (i)-(ii) in this paper. We give next a necessary and sufficient condition for each of the cases (iii) and (iv), and give a sufficient condition for case (v). For any POPS $\bm{P}$, the set $\bm{P}\oplus\bot\stackrel{{\scriptstyle\text{def}}}{{=}}\{{u\oplus\bot}\mid{u\in P}\}$ is a semiring (Proposition 2.4); our characterization is based entirely on a certain property, called stability, of the semiring $\bm{P}\oplus\bot$, which we describe here.

Given a semiring $\bm{S}$ and $u\in S$, denote by $u^{(p)}:=1\oplus u\oplus u^{2}\oplus\cdots\oplus u^{p}$, where $u^{i}:=u\otimes u\otimes\cdots\otimes u$ ($i$ times). We say that $u$ is $p$-stable if $u^{(p)}=u^{(p+1)}$; we say that the semiring $\bm{S}$ is $p$-stable if every element $u\in S$ is $p$-stable, and we say that $\bm{S}$ is stable if every element $u$ is stable for some $p$ that may depend on $u$. A $\text{\sf datalog}^{\circ}$ program is linear if every rule has at most one IDB predicate in the body. We prove:

In a nutshell, the theorem says that convergence of $\text{\sf datalog}^{\circ}$ is intimately related to the notion of stability. The proof, provided in Sec. 5, consists of an analysis of the infinite powerseries resulting from unfolding the fixpoint definition; for the proof of the first item we also use Parikh’s theorem (MR209093, ). As mentioned earlier, most prior work on fixpoint equations assumes an $\omega$-continuous semiring; when convergence is desired, one usually offers the Ascending Chain Condition, ACC (see Sec. 3) as a sufficient condition for convergence. Our theorem implies that ACC is only a sufficient, but not a necessary condition for convergence, for example $\text{\sf Trop}^{+}$ is $0$-stable, and therefore every $\text{\sf datalog}^{\circ}$ program converges on $\text{\sf Trop}^{+}$, yet it does not satisfy the ACC condition. A somewhat related result is proven by Luttenberger and Schlund (DBLP:journals/iandc/LuttenbergerS16, ) who showed that, if $1$ is $p$-stable, then Newton’s method requires at most $N+\log\log p$ iterations. As mentioned earlier, each step of Newton’s method requires the computation of another least fixpoint, hence that result does not inform us on the convergence of the naïve algorithm.

Next, we introduce an extension of the semi-naïve evaluation algorithm to $\text{\sf datalog}^{\circ}$. It is known that the naïve evaluation algorithm is inefficient in practice, because at each iteration it repeats all the computations that it has done at the previous iterations. Most datalog systems implement an improvement called the semi-naïve evaluation, which keeps track of the delta between the successive states of the IDBs and applies the datalog rules as a function of these deltas to obtain the new iteration’s deltas. Semi-naïve evaluation is one of the major optimization techniques for evaluating datalog, however, it is defined only for programs that are monotone under set inclusion, and the systems that implement it enforce monotonicity, preventing the use of aggregation in recursion. Our second result consists of showing how to adapt the semi-naïve algorithm to $\text{\sf datalog}^{\circ}$, under certain restrictions of the POPS $\bm{P}$, thus, enabling the semi-naïve algorithm to be applied to programs with aggregation in recursion.

Let’s illustrate the semi-naïve algorithm on the APSP program in Example 1.1. For that, let’s first review the standard semi-naïve algorithm for pure datalog on the transitive closure program (2). While the naïve algorithm starts with $T^{(0)}(X,Y)=\emptyset$ and repeats $T^{(t+1)}(X,Y)=E(X,Y)\vee\bigvee_{Z}T^{(t)}(X,Z)\wedge E(Z,Y)$ for $t=0,1,2,\ldots$, the semi-naïve algorithm starts by initializing $T^{(1)}(X,Y)=\delta^{(0)}(X,Y)=E(X,Y)$, then performs the following steps for $t=1,2,3,\ldots$:

(5)		$\displaystyle\delta^{(t)}(X,Y)$	$\displaystyle=\left(\bigvee_{z}\delta^{(t-1)}(X,Z)\wedge E(Z,Y)\right)\setminus T^{(t)}(X,Y)$
	$\displaystyle T^{(t+1)}(X,Y)$	$\displaystyle=T^{(t)}(X,Y)\cup\delta^{(t)}(X,Y).$

Thus, the semi-naïve algorithm avoids re-discovering at iteration $t$ tuples already discovered at iterations $1,2,\ldots,t-1$.

In order to apply the same principle to the APSP program (4), we need to define an appropriate “minus” $\ominus$ operator on the tropical semiring. This operator is:

(6)

$\displaystyle v\ominus u=$

$\displaystyle\begin{cases}v&\mbox{if }v<u\\ \infty&\mbox{if }v\geq u\end{cases}$

The semi-naïve algorithm for the APSP problem in (3) is a mirror of that in (5):

(7)		$\displaystyle\delta^{(t)}(X,Y)$	$\displaystyle=(\min_{Z}\delta^{(t-1)}(X,Z)+E(Z,Y))\ominus T^{(t)}(X,Y),$
	$\displaystyle T^{(t+1)}(X,Y)$	$\displaystyle=\min(T^{(t)}(X,Y),\delta^{(t)}(X,Y))$

where the difference operator $\ominus$ is defined in (6). The reason why this algorithm is more efficient than the naïve algorithm is the fact that, in general, a database system needs to store only the tuples that are “present” in a relation, i.e. those whose value is $\neq\bot$. In our example, only those tuples $\delta^{(t)}(X,Y)$ whose value is $\neq\infty$ need to be stored. The $\ominus$ operator in (7) checks if the new value $\min_{Z}\delta^{(t-1)}(X,Z)+E(Z,Y)$ is strictly less than the old value $T^{(t)}(X,Y)$: if not, then it returns $\infty$, signaling that the value of $(X,Y)$ in both $\delta^{(t)}(X,Y)$ and $T^{(t)}(X,Y)$ does not need to be updated. As a consequence, only those tuples $T^{(t+1)}(X,Y)$ need to be processed at step $t$ where the value has strictly decreased from the previous step.

Finally, the last topic we address in this paper is a possible way of introducing negation in $\text{\sf datalog}^{\circ}$. We will show that by interpreting $\text{\sf datalog}^{\circ}$ over a particular POPS called THREE (Sec. 2.5.2) and by appropriately defining a function not, $\text{\sf datalog}^{\circ}$ can express datalog queries with negation under Fitting’s three-valued semantics (DBLP:journals/jlp/Fitting85a, ). The crux in Fitting’s approach is to apply to the three-valued logic (with truth values $\{0,1,\bot\}$, where $\bot$ means “undefined”) the knowledge order $\leq_{k}$ with $\bot\leq_{k}0$ and $\bot\leq_{k}1$. Then, the function not defined as $\mathtt{not}(0)=1$, $\mathtt{not}(1)=0$, and $\mathtt{not}(\bot)=\bot$ is monotone w.r.t. $\leq_{k}$, and one can apply the usual least fixpoint semantics to datalog programs with negation (and, likewise, to $\text{\sf datalog}^{\circ}$ programs with the function not). Hence, in cases when Fitting’s 3-valued semantics coincides with the well-founded semantics, so does $\text{\sf datalog}^{\circ}$ equipped with the function not when interpreted over the POPS THREE.

We define POPS in Sec. 2 and give several examples. In Sec. 3 we consider the least fixpoint of monotone functions over posets, and prove an upper bound on the number of iterations needed to compute the least fixpoint. We define $\text{\sf datalog}^{\circ}$ formally in Sec. 4, and give several examples. The convergence results described in Theorem 1.2 are stated formally and proven in Sec. 5. Sec. 6 presents a generalization of semi-naïve evaluation to $\text{\sf datalog}^{\circ}$. We discuss how $\text{\sf datalog}^{\circ}$ can express datalog queries with negation using 3-valued logic in Sec. 7. Finally, we conclude in Sec. 9.

In any (pre-)semiring $\bm{S}$, the relation $x\preceq_{S}y$ defined as $\exists z:x\oplus z=y$, is a preorder, which means that it is reflexive and transitive, but it is not anti-symmetric in general. When $\preceq_{S}$ is anti-symmetric, then it is a partial order, and is called the natural order on $\bm{S}$; in that case we say that $\bm{S}$ is naturally ordered.

A key idea we introduce in this paper is the decoupling of the partial order from the algebraic structure of the (pre-)semiring. The decoupling allows us to inject a partial order when the (pre-)semiring is not naturally ordered, or when we need a different partial order than the natural order.

A POPS satisfies the identities $\bot\oplus\bot=\bot$ and $\bot\otimes\bot=\bot$, because, by monotonicity and the fact that $(P,\oplus,0)$ and $(P,\otimes,1)$ are commutative monoids, we have $\bot\oplus\bot\sqsubseteq\bot\oplus 0=\bot$, and $\bot\otimes\bot\sqsubseteq\bot\otimes 1=\bot$. We say that the multiplicative operator $\otimes$ is strict if the identity $x\otimes\bot=\bot$ holds for every $x\in P$.

Throughout this paper we will assume that $\otimes$ is strict, unless otherwise stated. One of the reasons for insisting on the strictness assumption is that we can “extract” from a POPS a semiring, called the core semiring of the POPS, as shown in the following simple proposition.

Every naturally ordered semiring is a POPS, where $\bot=0$ and $\otimes$ is strict, and its core is itself, $\bm{S}\oplus 0=\bm{S}$. The converse does not hold: some POPS are not naturally ordered; a simple example of a non-naturally ordered POPS is the set of lifted reals⁴⁴4The term “lifted” comes from the programming languages community where adding bottom to a set ‘lifts’ the set., $\mathbb{R}_{\bot}\stackrel{{\scriptstyle\text{def}}}{{=}}(\mathbb{R}\cup\{\bot\},+,*,0,1,\sqsubseteq)$, where $x+\bot=x*\bot=\bot$ for all $x$, and $x\sqsubseteq y$ iff $x=\bot$ or $x=y$. Its core semiring is the trivial semiring $\mathbb{R}_{\bot}+\bot=\{\bot\}$ consisting of a single element. We will consider similarly the lifted natural numbers, $\mathbb{N}_{\bot}$.

Fix a POPS $\bm{P}=(P,\oplus,\otimes,0,1,\sqsubseteq)$. We are interested in analysing behaviors of vector-valued multivariate functions on $P$ defined by composing $\oplus$ and $\otimes$. These functions are multivariate polynomials. Writing polynomials in $\bm{P}$ using the symbols $\oplus,\otimes$ is cumbersome and difficult to parse. Consequently, we replace them with $+,\cdot$ when the underlying POPS $\bm{P}$ is clear from context; furthermore, we will also abbreviate a multiplication $a\cdot b$ with $ab$. As usual, $a^{k}$ denotes the product of $k$ copies of $a$, where $a^{0}\stackrel{{\scriptstyle\text{def}}}{{=}}1$.

Let $x_{1},\ldots,x_{N}$ be $N$ variables. A monomial (on $\bm{P}$) is an expression of the form:

(8)

$\displaystyle m\stackrel{{\scriptstyle\text{def}}}{{=}}$

$\displaystyle c\cdot x_{1}^{k_{1}}\cdot\cdots\cdot x_{N}^{k_{N}}$

where $c\in P$ is some constant. Its degree is $\text{\sf deg}(m)\stackrel{{\scriptstyle\text{def}}}{{=}}k_{1}+\cdots+k_{N}$. A (multivariate) polynomial is a sum:

(9)

$\displaystyle f(x_{1},\ldots,x_{N})\stackrel{{\scriptstyle\text{def}}}{{=}}$

$\displaystyle m_{1}+m_{2}+\cdots+m_{q}$

where each $m_{i}$ is a monomial. The polynomial $f$ defines a function $P^{N}\rightarrow P$ in the obvious way, and, with some abuse, we will denote by $f$ both the polynomial and the function it defines. Notice that $f$ is monotone in each of its arguments.

A vector-valued polynomial function on $\bm{P}$ is a function $\bm{f}:P^{N}\rightarrow P^{M}$ whose component functions are polynomials. In particular, the vector-valued polynomial function is a tuple of polynomials $\bm{f}=(f_{1},\ldots,f_{M})$ where each $f_{i}$ is a polynomial in variables $x_{1},\ldots,x_{N}$.

We note a subtlety when dealing with POPS: when the POPS is not a semiring, then we cannot “remove” monomials by setting their coefficient $c=0$, because $0$ is not absorbing. Instead, we must ensure that they are not included in the polynomial (9). For example, consider the POPS of the lifted reals, $\bm{R}_{\bot}$, and the linear polynomial $f(x)=ax+b$. If we set $a=0$, we do not obtain the constant function $g(x)=b$, because $f(\bot)=a\bot+b=\bot+b=\bot\neq g(\bot)=b$. We just have to be careful to not include monomials we don’t want.

Fix a relational vocabulary, $\sigma=\{R_{1},\ldots,R_{m}\}$, where each $R_{i}$ is a relation name, with an associated arity. Let $D$ be an infinite domain of constants, for example the set of all strings over a fixed alphabet, or the set of natural numbers. Recall that an instance of the relation $R_{i}$ is a finite subset of $D^{\text{arity}(R_{i})}$, or equivalently, a mapping $D^{\text{arity}(R_{i})}\rightarrow\mathbb{B}$ assigning $1$ to all tuples present in the relation. Following (DBLP:conf/pods/GreenKT07, ), we generalize this abstraction from $\mathbb{B}$ to an arbitrary POPS $\bm{P}$.

Given a relation name $R_{i}\in\sigma$, a ground atom of $R_{i}$ is an expression of the form $R_{i}(\bm{u})$, where $\bm{u}\in D^{\textsf{arity}(R_{i})}$. Let $\textsf{GA}(R_{i},D)$ denote the set of all ground atoms of $R_{i}$, and $\textsf{GA}(\sigma,D)\stackrel{{\scriptstyle\text{def}}}{{=}}\bigcup_{i}\textsf{GA}(R_{i},D)$ denote the set of all ground atoms over the entire vocabulary $\sigma$. The set $\textsf{GA}(\sigma,D)$ is the familiar Herbrand base in logic programming. Note that each ground atom is prefixed by a relation name.

Let $\bm{P}$ be a POPS. A $\bm{P}$-instance for $\sigma$ is a function $I:\textsf{GA}(\sigma,D)\rightarrow\bm{P}$ with finite support, where the support is defined as the set of ground atoms that are mapped to elements other than $\bot$. For example, if $\bm{P}$ is a naturally ordered semiring, then the support of the function $I$ is the set of ground atoms assigned to a non-zero value. The active domain of the instance $I$, denoted by $\textsf{ADom}(I)$, is the finite set $\textsf{ADom}(I)\subseteq D$ of all constants that occur in the support of $I$. We denote by $\textsf{Inst}(\sigma,D,\bm{P})$ the set of $\bm{P}$-instances over the domain $D$. When $\sigma$ consists of a single relation name, then we call $I$ a $\bm{P}$-relation.

An equivalent way to define a $\bm{P}$-instance is as a function $I:\textsf{GA}(\sigma,D_{0})\rightarrow\bm{P}$, for some finite subset $D_{0}\subseteq D$; by convention, this function is extended to the entire set $\textsf{GA}(\sigma,D)$ by setting $I(a):=\bot$ for all $a\in\textsf{GA}(\sigma,D)\setminus\textsf{GA}(\sigma,D_{0})$. The set $\textsf{Inst}(\sigma,D_{0},\bm{P})$ is isomorphic to $P^{N}$, where $N=|\textsf{GA}(\sigma,D_{0})|$, and, throughout this paper, we will identify a $\bm{P}$-instance with a tuple in $P^{N}$.

Thus, a $\bm{P}$-instance involves two domains: $D$, which is called the key space, and the POPS $\bm{P}$, which is called the value space. For some simple illustrations, a $\mathbb{B}$-relation is a standard relation where every ground tuple is either true or false, while an $\mathbb{R}$-relation is a sparse tensor.

In the Boolean world, conjunctive queries and unions of conjunctive queries are building-block queries. Analogously, in the POPS world, we introduce the concepts of sum-product queries and sum-sum-product queries. In the most simple setting, these queries have been studied in other communities (especially AI and machine learning as reviewed below). In our setting, we need to introduce one extra feature called “conditional”, in order to cope with the fact that $0$ is not absorptive.

Fix two disjoint vocabularies, $\sigma,\sigma_{\mathbb{B}}$; the relation names in $\sigma$ will be interpreted over a POPS $\bm{P}$, while those in $\sigma_{\mathbb{B}}$ will be interpreted over the Booleans. Let $D$ be a domain, and $V=\{X_{1},\ldots,X_{p}\}$ a set of “key variables” whose values are over the key space $D$. They should not be confused with variables used in polynomials, which are interpreted over the POPS $\bm{P}$; we refer to them as “value variables” to contrast them with the key variables. We use upper case for key variables, and lower case for value variables. A $\sigma$-atom is an expression of the form $R_{i}(\bm{X})$, where $R_{i}\in\sigma$ and $\bm{X}\in(V\cup D)^{\text{arity}(R_{i})}$.

Without the conditional term $\Phi$, the problem of computing efficiently sum-products over semirings has been extensively studied both in the database and in the AI literature. In databases, the query optimization and evaluation problem is a special case of sum-product computation over the value-space of Booleans (set semantics) or natural numbers (bag semantics). The functional aggregate queries (FAQ) framework (DBLP:conf/pods/KhamisNR16, ) extends the formulation to queries over multiple semirings. In AI, this problem was studied by Shenoy and Schafer (DBLP:conf/uai/ShenoyS88, ), Dechter (DBLP:journals/constraints/Dechter97, ), Kohlas and Wilson (DBLP:journals/ai/KohlasW08, ) and others. Surveys and more examples can be found in (DBLP:journals/tit/AjiM00, ; DBLP:books/daglib/0008195, ). These methods use a sparse representation of the $\bm{P}$-relations, consisting of a collection of the tuples in their support.

The use of a conditional $\Phi$ in the sum-product is non-standard, but it is necessary for sum-product expressions over a POPS that is not a semiring, as we illustrate next.

We now formally define the semantics of (conditional) sum-product queries. Due to the subtlety with POPS, we need to consider an alternative approach to evaluating the results of sum-product queries: first compute the provenance polynomials of the query (10) to obtain the component polynomials of a vector-valued function, then evaluate these polynomials. The provenance polynomials, or simply provenance, are also called lineage, or groundings in the literature (DBLP:conf/pods/GreenKT07, ).

Given an input instance $I_{\mathbb{B}}\in\textsf{Inst}(\sigma_{\mathbb{B}},D,\mathbb{B})$, $I\in\textsf{Inst}(\sigma,D,\bm{P})$, and let $D_{0}\subseteq D$ be the finite set consisting of their active domains and all constants occurring in the sum-product expression (10). Let $N\stackrel{{\scriptstyle\text{def}}}{{=}}|\textsf{GA}(\sigma,D_{0})|$ and $M\stackrel{{\scriptstyle\text{def}}}{{=}}|\textsf{GA}(T,D_{0})|=|D_{0}|^{k}$ be the number of input ground atoms and output ground atoms respectively.

To each of the $N$ input atoms $\textsf{GA}(\sigma,D_{0})$ we associate a unique POPS variable $x_{1},\ldots,x_{N}$. (Recall that we use upper case for key variables and lower case for value variables.) Abusing notation, we also write $x_{R(\bm{u})}$ to mean the variable associated to the ground atom $R(\bm{u})$. A valuation is a function $\theta:V\rightarrow D_{0}$. When applied to the body of the rule (10), the valuation $\theta$ defines the following monomial:

(12)

$\displaystyle\theta(\text{body})\stackrel{{\scriptstyle\text{def}}}{{=}}$

$\displaystyle x_{R_{1}(\theta(\bm{X}_{1}))}\cdot x_{R_{2}(\theta(\bm{X}_{2}))}\cdots x_{R_{m}(\theta(\bm{X}_{m}))}$

The provenance polynomial (DBLP:conf/pods/GreenKT07, ) of the output tuple $T(\bm{a})\in\textsf{GA}(T,D_{0})$ is the following:

(13)

$\displaystyle f_{T(\bm{a})}(x_{1},\ldots,x_{N})\stackrel{{\scriptstyle\text{def}}}{{=}}$

$\displaystyle\sum_{\begin{subarray}{c}\theta:V\rightarrow D_{0}:\\ \theta(X_{1},\ldots,X_{k})=\bm{a},\\ I_{\mathbb{B}}\models\Phi[\theta]\end{subarray}}\theta(\text{body})$

In other words, we consider only valuations $\theta$ that map the head variables to the tuple $\bm{a}$ and satisfy the FO sentence $\Phi$. There are $M$ provenance polynomials, one for each tuple in $\textsf{GA}(T,D_{0})$, and they define an $M$-tuple of polynomials in $N$ variables, $\bm{f}$, which in turn defines a function $\bm{f}:\bm{P}^{N}\rightarrow\bm{P}^{M}$. The semantics of the query (10) is defined as the value of this polynomial on the input instance $I\in\textsf{Inst}(\sigma,D_{0},\bm{P})$, when viewed as a tuple $I\in\bm{P}^{N}$.

Note that, once we have constructed the provenance polynomial, we no longer need to deal with the conditional $\Phi$, because the grounded version does not have $\Phi$ anymore. In most of the rest of the paper we will study properties of vector-valued functions whose components are these provenance polynomials.

We notice that, as defined, our semantics depends on the choice of the domain $D_{0}$: if we used a larger finite domain $D^{\prime}_{0}\supseteq D_{0}$, then the provenance polynomials will include additional spurious monomials, corresponding to the spurious grounded tuples in $D_{0}^{\prime}$. Traditionally, these spurious monomials are harmless, because their value is 0. However, in our setting, their value is $\bot$, and they may change the result. This is precisely the role of the conditional $\Phi$ in (10): to control the range of the variables and ensure that the semantics is domain independent. All examples in this paper are written such that they are domain independent.

Finally, (conditional) sum-sum-product queries are defined in the natural way:

The provenance polynomials of a sum-sum-product query are defined as the sum of the provenance polynomials of the expressions $E_{1},\ldots,E_{q}$.

We end this section by presenting several properties of POPS and illustrating them with a few examples.