Convolution Sum-Product Queries

Convolution Sum-Product Queries Kyle Deeds1 , Timo Camillo Merkl2,3 , and Dan Suciu4 1

Boston University, United States, kdeeds@bu.edu Max Planck Institute for Software Systems, Germany 3 TU Wien, Austria, timo.merkl@tuwien.ac.at 4 University of Washington, United States, suciu@cs.washington.edu

arXiv:2609.03672v1 [cs.DB] 3 Sep 2026

2

Abstract We study query evaluation for an extension of sum-product queries (SPQ) that allows atoms with linear combinations of variables (e.g. A(2X + 3Y − Z, Y + Z)), which we call convolution sum-product queries (CSPQs). These queries arise in both practical settings (e.g. image processing workloads) and theoretical ones (e.g. the (min, +)-convolution and k-SUM conjectures), and capture SPQs with added linear equality constraints. While prior work has considered the impact of linear in- and dis-equality constraints on query evaluation, the techniques developed in that setting are asymptotically sub-optimal for CSPQs. To address this, we describe several evaluation algorithms for CSPQs that leverage linear algebra techniques like rank analysis, quotient spaces, and variable substitution. First, we adapt Worst-Case Optimal Joins to CSPQs, achieving a runtime similar in spirit to that for conjunctive queries. Then, we extend the definition of tree decompositions (TDs) to CSPQs, and describe a factorized execution. In this extension, linear combinations are first-class citizens and play the same role as variables in traditional TDs. We define three width measures that bound the complexity of this execution with respect to the size of the domain values, of the active domain, and of the relation’s support. Lastly, we show how these methods can be applied to arbitrary fields beyond the rationals.

1

Introduction

The literature on query evaluation has extended conjunctive queries (CQs) in a variety of ways to capture new problems of interest. Sum-product queries (SPQs) generalize CQs from the Boolean semiring to an arbitrary semiring [13], allowing them to express operations such as matrix multiplication, while CQs with disequalities (̸=) enabled the analysis of constraint satisfaction and subgraph-isomorphism problems within the CQ paradigm. In this work, we investigate an extension of conjunctive queries with linear expressions over P variables in the query. For example, the convolution of two arrays A, B can be expressed as C(X) = Y A(Y ) · B(X − Y ). We call this class of queries Convolution Sum-Product Queries (CSPQs). We are motivated by a large class of applications, in a variety of domains, which already use linear expressions. For example, SQL allows arbitrary expressions over attributes in the WHERE clause. Query optimizers based on dynamic programming already incorporate joins involving linear expressions, like R1 .A + R2 .B = R4 .D + R5 .E − R3 .C, see [30]. Linear expressions on the variables also occur in a large class of important workloads in tensor, image, and signal processing. For example, matrix convolution is a key operation in image processing pipelines and is not expressible via standard sum-product queries. In this operation, a smaller pattern matrix is iteratively applied to patches of the larger image matrix A in the following manner: X B(i, j) = A(i + l, j + k) · Pattern(l, k) l,k

By selecting an appropriate pattern matrix, this operation is the core computational primitive in image processing tasks such as edge detection and blurring, scientific simulations that use stencil computations, and in the convolution layers of neural networks [10, 11, 15, 26, 33, 29]. Several languages or formalisms

1

already consider linear expressions, but typically as second-class citizens, represented as predicates separate from the main body of the query. Some fine-grained complexity conjectures are expressable in this way [9, 6]. For example, the 3SUM conjecture states that, given three sets A, B, C, of size n, checking if there exists i ∈ A, j ∈ B, k ∈ C so that i + j = k cannot be done in time O(n2−ε ) and can be expressed as: _ Q() = A(i) ∧ B(j) ∧ C(k) such that i + j = k i,j,k

while the MinConv conjecture states that the following cannot be evaluated in time O(n2−ε ): Q(k) = min(A(i) + B(j)) such that i + j = k i,j

In this paper, we introduce Convolution Sum-Product Queries, and describe new algorithms for evaluating them. CSPQs extend Sum-Product Queries with linear expressions, while keeping them first-class citizens. The linear expressions occur directly in the query’s atoms, for example, the 3SUM and the MinCov queries above are written as follows in our formalism: Q() ← A(X) ∧ B(Y ) ∧ C(X + Y )

Q(K) ← A(I) + B(K − I)

(1)

We define the semantics of CSPQs, showing that they have always a well-defined answer. This is not obvious a priori. For example, the query Q() = R(X + Y ) would normally be interpreted as P JQK = x,y R(x + y), which results in an infinite sum. We use the concept of quotient space from linear algebra to ensure that every CSPQs has a well-defined semantics. In Sec. 3 we introduce CSPQs formally, define their semantics, and discuss some of their properties. Next, we describe several algorithms for evaluating a CSPQ in Sec. 4. We first describe a simple algorithm that runs in time O(|adom(D)|k ), where adom(D) is the active domain of the (support of the) input database, and k is the dimension of the query’s span, (defined in Sec. 3). This algorithm is best suited for dense databases, as found, for example, in processing dense tensors. Second, we describe an algorithm, which is best suited for sparse databases, ∗ which runs in time O(|D|ρ (Q) ). Here ρ∗ (Q) is the fractional edge covering number of a CSPQ, and is defined as a significant generalization of the traditional fractional edge covering number of a conjunctive query, or a hypergraph. This algorithm is quite non-obvious. For example, consider the following query, which is a slight variation of the 3SUM query above (Eq. (1)): Q() ← A(X, Y ) ∧ B(Y, Z) ∧ C(X + Y, Y + Z) We show that ρ∗ (Q) = 3/2, and therefore Q can be evaluated in time O(|D|3/2 ), were |D| is the size of the database (number of tuples in A, B, C). Although our definition of ρ∗ (in Def. 4.2) looks very different from the traditional one, we show that it coincides with the traditional one when the CSPQ is a traditional conjunctive query. Finally, we adapt tree decompositions to CSPQs. Similarly to ρ∗ , the definition of a tree decomposition requires a careful extension to linear spaces: we present the definition of a Convolution Tree Decomposition (CTD) in Sec. 5, and describe factorized evaluation algorithms based on CTDs in Sec. 6. We also extend our techniques to arbitrary fields in Sec. 7, then conclude. Related Work. Other extensions of conjunctive queries with numerical operations or predicates can be found in the literature. In all cases the arithmetic operations are considered second-class citizens, designed to be included in predicates, separate from the main body of the conjunctive query. For example, Arithmetic Constrains are simple comparisons X < Y over a dense domain; Klug [24], Afrati et al. [2, 3], and Brisaboa et al. [7] study the containment and the query rewriting using views problems under this extension. Kiani and Shiri [22, 23, 21] study the query answering using views problem for conjunctive queries extended with linear equality constraints (which are equivalent to our CSPQs). Srivastava [34], and Ibarra and Su [16] study the containment (subsumption) problem for queries with linear constraints, like 2X + 3Y < 7. The query evaluation problem has been considered in several papers. Extensions of conjunctive queries with general constraints has been discussed in [17, 18], and in [38, 39]. These references apply a technique due to Willard to handle complex predicates, such as X 2 + XY > 5Z, but since they target more general queries than CSPQs, their runtimes are worse than what we propose in this paper: see the discussion in Sec. 4. Koutris et al. [25] and Abo Khamis et al. [19] introduce specialized algorithms for evaluating conjunctive queries with disequality predicates, X ̸= Y . In contrast 2

to these lines of work, the algorithms we present in this paper treat the linear expressions as first class citizens, and show how to apply worst-case optimal joins [32, 36, 31] and tree decompositions [12], by combining them with core ideas in linear algebra. Constraint databases, which have been heavily studied in the literature [27], are unrelated to our paper. They consider input relations that are infinite, defined implicitly using linear or algebraic constraints. In our paper we always assume the support of the input relations is finite. Beyond databases, expressions equivalent to our CSPQs over dense tensors have been intensively study by the compilers community. This work has resulted in the polyhedral model, which can represent various transformations of loops over arrays with linear index expressions, and has been leveraged in several widely used high-performance compilers for tensor algebra [35, 5, 8, 37]. Our work applies similar linear transformations but goes further by analyzing them also in the sparse setting and extending them to leverage tree decompositions style factorizations. Summary of Results. • We extend sum-product queries to allow linear expressions on the variables, keeping them as first-class citizens (see Sec. 3). • We extend the notion of tree decompositions to CSPQs and prove that these induce a factorization of the queries. (see Sec. 5) • We analyze the complexity of CSPQs. We provide basic algorithms (essentially for full queries) and modify worst-case optimal join algorithms to achieve AGM-style bounds (see Sec. 4). Then, we apply these algorithms to the factorizations induced by our novel extension to tree decomposition. The complexity of the evaluation algorithm is characterized by three new width parameters that capture different input density regimes (see Sec. 6). Most proof are deferred to the appendix and in Appendix F we explain precisely how CSPQs capture SPQs with added linear equality constraints.

2

Background

In this section we introduce the notation used throughout the paper. If a = (a1 , . . . , an ) is a tuple, then we write |a| := n, and denote by f (a) the tuple (f (a1 ), . . . , f (an )), where f is any function. With some abuse, we will blur the distinction between a tuple a and the set of its values. For example, if a = (a1 , . . . , an ) and b = (b1 , . . . , bm ), then a ⊆ b means {a1 , . . . , an } ⊆ {b1 , . . . , bm }. Databases and Sum-Product Queries. We follow the definition of K-relations from [13], where a relation is a function from tuples to a commutative semiring. Throughout this paper, the domain of the tuples are the rational numbers Q (unless otherwise stated), and the commutative semiring is denoted by S = (S, ⊕, ⊗, 0, 1). Thus, if R is a relation symbol of arity r := ar (R), then an S-relation instance, or simply S-relation, is a function RD : Qr → S with finite support, where the support is supp(RD ) := {x ∈ Qr | RD (x) ̸= 0}. We say that tuples x ∈ supp(RD ) are annotated by R(x). We assume that RD is represented as a list of tuple-annotation pairs, of size |RD | := |supp(RD )|. The active domain adom(R) ⊆ Q of R is the set of all domain elements that appear in the support. A database instance D overSa vocabulary R1 , . . . , Rm is D tuple ofPS-relations, D = (R1D , . . . , Rm ). Its active domain is adom(D) = i adom(RiD ) and its size is D |D| := i |Ri |. If R is a relation symbol of arity r, and X is an r-tuple of variables, then the expression R(X) is called an atom. A sum-product query (SPQ) is an expression of the form: Q(X0 ) ← R1 (X1 ) ⊗ . . . ⊗ Rm (Xm ) (2) S where R1 (X S 1 ), . . . , Rm (Xm ) are atoms, and X0 ⊆ i=1,m Xi (called the safety condition). We write var (Q) := i=1,m Xi for set of all variables in Q, and call X0 the head variables of Q. The arity of Q is |X0 |. A conjunctive query (CQ) is an SPQ interpreted in the Boolean semiring B: we write ∧ for ⊗. Fix a database instance D and query Q. A valuation is a function v : var (Q) → Q that maps each variable to a value in the domain; v maps each atom Ri (Xi ) to a semiring value, namely to RiD (v(Xi )). The answer of Q over D is the S-relation JQKD obtained by summing over all valuations:   M O  ∀x ∈Q|X0 | : JQKD (x) := RiD (v(Xi )) . (3) v : var (Q)→Q, s.t. v(X0 )=x

3

i=1,m

We sometimes omit the superscripts D and write simply JQK. Note that JQK has finite support. Linear Algebra. We fix a d-dimensional vector space V over the rationals Q, and write dim(V ) := d for its dimension. For any set A ⊆ V we write span(A) for the smallest vector subspace containing A. Given two subspaces V1 , V2 ⊆ V , V1 + V2 denotes span(V1 ∪ V2 ). Further, for a subspace P ⊆ V , V /P is the quotient space of V modulo P , which consists of equivalence classes where two vectors v, v ′ ∈ V are in the same class when v − v ′ ∈ P . Its dimension is dim(V /P ) = dim(V ) − dim(P ). We write [v]P for the equivalence class of v, or just [v] when P is clear from the context. When V = Qd , then we denote by ⟨u | v⟩ the dot product of vectors u, v ∈ V . Given two sets of vectors A, B ⊆ V , we write A ⊥ B when ⟨x | y⟩ = 0 for all x ∈ A, y ∈ B, and write A⊥ := {v ∈ V | ∀x ∈ A : x ⊥ v} for the subspace orthogonal to A. Its dimension is dim(A⊥ ) = d − dim(span A). If v ∈ V is fixed, then ⟨− | v⟩ is a linear function V → Q, defined by u 7→ ⟨u | v⟩. We extend this function to a tuple of vectors, ⟨− | v⟩ : V n → Qn : if A = (u1 , . . . , un ) ∈ V n then ⟨A | v⟩ := (⟨u1 | v⟩, . . . , ⟨un | v⟩) ∈ Qn . If B ⊆ V then we define ⟨− | [v]B ⊥ ⟩ : span B → Q as follows: for all u ∈ span B, ⟨u | [v]B ⊥ ⟩ := ⟨u | v⟩. This is well defined in the following sense: if [v]B ⊥ = [v ′ ]B ⊥ then v − v ′ ∈ B ⊥ ; since u ∈ span B, it follows that ⟨u | v − v ′ ⟩ = 0, or equivalently ⟨u | v⟩ = ⟨u | v ′ ⟩, proving that the definition of ⟨u | [v]B ⊥ ⟩ does not depend on the representative from [v]B ⊥ . Computational Model. We assume the RAM model where each cell holds a single domain or semiring element. Every operation in classical or semiring arithmetic is assumed to take constant time. We omit the single log factor associated with looking up tuples from relations or sorting them and write upper bounds as O rather than Õ. We focus solely on the data complexity of queries in this work, so we assume queries to be fixed.

3

Convolution Sum-Product Queries

In this section, we define convolution sum-product queries (CSPQs). The goal is to extend SPQs to allow atoms with linear expressions, like in Sec. 1. For example, consider the atom R(X + 2Y, 2X + Z). Using dot products we can write X + 2Y = ⟨(1, 2, 0) | (X, Y, Z)⟩ and 2X + Z = ⟨(2, 0, 1) | (X, Y, Z)⟩, and the atom becomes R(⟨A | (X, Y, Z)⟩), where A is the tuple of vectors (1, 2, 0) and (2, 0, 1). For conciseness, we omit the variables and abbreviate the atom by R(A). In general, if R is any relation symbol of arity r = ar (R), then we define a convolution atom to be an expression R(A), where A is a tuple of r vectors in Qd (or, equivalently, a d × r matrix). Here, d is the total number of variables. A convolution sum-product query is defined as follows (we first give the full definition and then delve into the intuition): Definition 3.1. A convolution sum-product query (CSPQ) over Qd is an expression of the form: Q(A0 ) ← R1 (A1 ) ⊗ · · · ⊗ Rm (Am )

(4)

1 where each Ri (Ai ), i = 1, m is a convolution atom, S and the following safety condition holds: A0 ⊆ span(Q), where the span of Q is span(Q) := span( i=1,m Ai ). The arity of Q is ar (Q) := |A0 |.

For a brief example, the query Q() ← A((1, 0)) ∧ B((0, 1)) ∧ C((1, 1)) is the same as the 3SUM query in Eq. (1); we will return to it shortly. When defining a CSPQ we may omit the head attributes A0 when they are implicit and the focus is on the body structure. Given a CSPQ over V := Qd , we associate the following subspaces: the null space is (span(Q))⊥ , and the active space is V act := Qd /(span(Q))⊥ . Notice that dim(span(Q)) = dim(V act ). ForSa convolution atom R(A), we will write, with some abuse, span(R) for span(A), and write span(R) = R∈R (span(R)) for a set of atoms R. Note the similarity of an SPQ given in Eq. (2) and a CSPQ given in Eq. (4): Vectors in CSPQs play the role of variables in SPQs. This will be the running theme of this paper. A CSPQ is interpreted in a semiring S as follows: Definition 3.2. Let Q be a CSPQ given by Eq. (4), and let V act be its active space. The answer of Q D over an S-database instance D = (R1D , . . . , Rm ) is the S-relation JQKD : M O ∀x ∈Q|A0 | : JQKD (x) := RiD (⟨Ai | v⟩). (5) v∈V act : ⟨A0 |v⟩=x i=1,m

As usual, we omit the superscript D when clear from the context, and write simply JQK. 1 Recall that we identify a tuple A

0 = (v1 , . . . , vk ) with a set {v1 , . . . , vk }: the safety condition states vj ∈ span(Q), ∀j.

4

A 1 2 3 4

B 1 3 4 5

-1 0 0

0 -1 1

Q(2X + 2Z) ← A(X) · B(Y − X, Z − Y ) · C(Z)

C 1 5 3

1 2 3 4

1 3 4 5

6 10 14

27 108 160

Fig. 1: Example Evaluation of a Convolution Sum-Product Query. The notation ⟨Ai | v⟩ in Eq. (5) is well-defined for v ∈ V act = V /(span(Q))⊥ , because Ai ⊥ (span(Q))⊥ . We prove in Appendix A that JQKD has finite support and that there are only finitely many non-0 terms in the summation (5): Lemma 3.3. JQKD is an S-relation (meaning: it is well-defined and has finite support). Proof Sketch. Every non-0 term on the right hand side of Equation (5) for some JQK(x) has all its factors non-0, since 0 is absorbing. Hence each combination (⟨A1 | v⟩, . . . , ⟨Am | v⟩) occurring in a non-0 term belongs to the finite product of the relation supports. Only finitely many such combinations are possible. If two corresponding elements v, v ′ ∈ V act yield the same combination, then v − v ′ is in span(Q)⊥ = span(A1 ∪ · · · ∪ Am )⊥ , so v = v ′ in V act . Thus the sum defining JQK(x) has finitely many non-0 terms. Moreover, JQK(x) is non-0 only if there is at least some non-0 term. However, there are only finitely many v ∈ V act that lead to a non-0 term and v determines x through ⟨A0 | v⟩ = x. As explained above, the vectors Ai in an atom Ri (Ai ) indicate which variables are used in the atom, and with what multiplicities. To make the analogy even clearer, let X1 , . . . , Xd be d variables, then an atom Ri (Ai ) represents the atom Ri (⟨Ai | (X1 , . . . , Xd )⟩). The expression Ri (⟨Ai | v⟩) in Eq. (5) with v = [(v1 , . . . , vd )] should be interpreted as applying the valuation {Xj 7→ vj | j = 1, d} to the variables, as in the semantics of traditional SPQs given in Eq. (3). When span(Q) = Qd , then (span(Q))⊥ = {0} and the active space V act = Qd /{0} is isomorphic to Qd . Then, the summation in Eq. (5) can be replaced with a summation over vectors v ∈ Qd . We illustrate this with a simple example: Example 3.4. The 3SUM query from Sec. 1 Eq. (1) is a query interpreted in the Boolean semiring, and is written as a CSPQ over Q2 as follows Q() ←A((1, 0)) ∧ B((0, 1)) ∧ C((1, 1)). As discussed above, we can write Q more naturally as: Q() ← A(X) ∧ B(Y ) ∧ C(X + Y ). We will often 2 use this notation for readability. Here W the span of Q is Q = span{(1, 0), (0, 1), (1, 1)}, and the semantics in Eq. (5) can be written as JQK = x,y∈Q (A(x) ∧ B(y) ∧ C(x + y)).

In this paper, we study the query evaluation problem for CSPQs. The “intuitive” way to compute the |A0 | answer JQK in Eq. (5) is as follows. Maintain a hash table → S (initialized with supp(T ) = ∅), N T: Q act iterate over the active space v ∈ V , compute sv := i Ri (⟨Ai | v⟩), then increment T (⟨A0 | v⟩) := T (⟨A0 | v⟩) ⊕ sv . Once all vectors v have been processed, return JQK := T . Of course, this not a real algorithm, because the summation over the active space V act is an infinite sum: we describe practical algorithms in Sections 4 and 6. Here, we illustrate the basic idea with an example.

Example 3.5. Consider the query2 Q, given in Fig. 1, over Q3 and interpreted in the semiring of natural numbers (N, +, ·, 0, 1). The N-relation instances are bags of rational numbers, A, C : Q → N, and B : Q2 → N and shown in Fig. 1. To evaluate Q, we iterate over triples x, y, z ∈ Q such that A(x) ̸= 0, B(y − x, z − y) ̸= 0, and C(z) ̸= 0. To determine these triples, we can iterate over all values a supp(B), c ∈ supp(C), and solve the overdetermined system of linear equations  ∈1 supp(A),   (b1 , b2) ∈ a  0 0 x −1 1 0 y = bb12 . The 4 · 3 · 4 choices for the RHS lead to 9 solutions: 0 −1 1 0

0 1

z

(x, y, z) =

c

(1, 1, 2), (2, 1, 1), (2, 2, 1),

(2, 2, 3), (3, 2, 2), (3, 3, 2),

(3, 3, 4), (4, 3, 3), (4, 4, 3)

2 If we used the Boolean semiring, then the query could be written equivalently using arithmetic predicates as follows: Q(W ) ← A(X) ∧ B(Y1 , Y2 ) ∧ C(Z) ∧ (X + Y1 + Y2 = Z) ∧ (W = 2X + 2Z).

5

We grouped the solutions by the value of 2x + 2z; the output JQK(2x + 2z) is the sum of their annotations. For example, in the first group 2x + 2z = 6, and JQK(6) = A(1)B(0, 1)C(2) + A(2)B(−1, 0)C(1) + A(2)B(0, −1)C(1) = 9 + 3 + 15 = 27. The complete answer is in Fig. 1. The Active Space. Fix a CSPQ query Q over Qd , and denote by S := span(Q). In our examples so far, S = Qd . In this case S ⊥ = {0} and the active space is V act = Qd /S ⊥ ≃ Qd . We could have defined the query’s semantics in Eq. (5) as a sum over the entire space Qd instead of a sum over V act . But when S ⊊ Qd , then summing over the entire space leads to an infinite result. Any two vectors v, v ′ ∈ Qd that satisfy [v]S ⊥ = [v ′ ]S ⊥ produce the same result, because ⟨Ai | v⟩ = ⟨Ai | v ′ ⟩ for all i = 1, m. Since each equivalence class [v]S ⊥ is infinite, the summation in Eq. (5) would add the same term infinitely many times. This is why we introduced the active space. Summing over the active space guarantees that each combination of tuples from R1 , . . . , Rm appears only once in the sum. We illustrate this with a simple example. Example 3.6. Consider the query Q() ← R(X + Y ) over Q2 , which just sums up all annotations of the tuples in R. Written formally, the atom is R((1, 1)), and P S := span(Q) = span({(1, 1)}) = {(z, z) | z ∈ Q} has dimension 1. Obviously, we cannot define JQK = x,y∈Q R(x + y), since this will add every tuple in R infinitely many times. The insight here is that two vectors v = (x, y) and v ′ = (x′ , y ′ ) represent the same tuple in R iff x + y = x′ + y ′ or, equivalently, iff ⟨(1, 1) | v⟩ = ⟨(1, 1) | v ′ ⟩, which we can also write as (1, 1) ⊥ (v − v ′ ), or [v]S ⊥ = [v ′ ]S ⊥ . By summing over equivalence classes [v]S ⊥ instead of over vectors v, Eq. (5) includes every tuple of R only once. Since [(x, y)]S ⊥ = [(xL+ y, 0)]S ⊥ , every equivalence class L has a canonical representative (z, 0), and we can also express JQK as [(z,0)]∈V act R(z + 0) = z∈Q R(z). This captures our intuition that, because span(Q) is 1-dimensional, the expression X + Y in the query should be substituted by a single variable Z and written as Q() ← R(Z). We allow span(Q) ⊊ Qd in order to evaluate a query via a sequence of subqueries. For example, consider the standard 2-path Boolean query Q() ← R(X, Y ) ∧ S(Y, Z), which, viewed a CSPQ is over the 3-dimensional space Q3 . We can compute Q in linear time using the following factorization: Q1 () ← R(X, Y ) ∧ Q2 (Y ), Q2 (Y ) ← S(Y, Z). While Q is defined over Q3 , the two subqueries have a span of dimension 2 and JQK = JQ1 K. We expand on this idea in Section 5. The Safety Condition. Intuitively, the requirement A0 ⊆ span(Q) in the definition of a CSQP (Def. 3.1) corresponds to the traditional safety condition for conjunctive queries: every variable in the head must occur in the body. For example, consider the unsafe query: Q(X, Y, Z) ← R(X, Y ) ∧ S(Y ). In vector notation the query is Q(e1 , e2 , e3 ) ← R(e1 , e2 ) ∧ S(e2 ), where e1 = (1, 0, 0), e2 = (0, 1, 0), e3 = (0, 0, 1). Here {e1 , e2 , e3 } ̸⊆ span(e1 , e2 ), reflecting the fact that the query is unsafe. However, the requirement is also technically important because, for elements [v] ∈ V act , the expression ⟨A0 | [v]⟩ N is only well-defined when A0 ⊆ span(Q). Convolution-free CSPQ. We say that a CSPQ Q(A0 ) ← i=1,m Ri (Ai ) over S Qd is convolution-free if i=1,m Ai = {e1 , . . . , ed }, where e1 = (1, 0, . . . , 0), . . . , ed = (0, 0, . . . , 1) are the canonical basis vectors in Qd . (There is no restriction on A0 .) When we replace the ej with variables Xj , then Q is simply a traditional SPQ; examples include matrix multiplication Q(X, Z) ← A(X, Y )⊗B(Y, Z), or any traditional conjunctive query, e.g. Q(Y ) ← R(X) ∧ S(X, Y ). Thus, CSPQs generalize SPQs. We illustrate with an example. Example 3.7. Consider the following CSPQ over Q3 , interpreted in the natural numbers N: Q() ←R(X, Y ) · S(Y, Z) · T (X, Z)

(6)

Written in vector notation, the first atom becomes R((1, 0, 0), (0, 1, 0)), and similarly for the other two atoms, thus, it is convolution-free. span(Q) = Q3 , and P V act = Q3 /{0} ≃ Q3 . The traditional semantics of SPQs equals the CSPQ semantics in Eq. (5): JQK = x,y,z∈Q R(x, y) · S(y, z) · T (x, z).

Invariance Under Substitutions. Variable substitution is a key operation in linear algebra that facilitates the analysis of an expression by converting it to a simpler, equivalent form. This will be a crucial tool throughout this paper, and we prove here that this operation is valid on CSPQs. Formally, a substitution for a CSPQ Q is an injective linear function φ : span(Q) → V ′ for some vector space V ′ . We write Qφ for the result of applying φ to Q as in the following lemma: N Lemma 3.8 (Variable Substitution). Let Q1 (A0 ) ← i=1,m Ri (Ai ) be a CSQP over V1 := Qd1 , and let φ : span(Q1 ) → V2 beNa substitution, where V2 := Qd2 . Define Bi := φ(Ai ) for i = 0, m, and consider the query Q2 (B0 ) ← i=1,m Ri (Bi ). Then Q1 , Q2 are equivalent: ∀D, JQ1 KD = JQ2 KD . 6

Proof Sketch. Denote S1 := span(Q1 ), S2 := span(Q2 ) and notice that φ : S1 → S2 is a bijection. Let V1act := V1 /S1⊥ , V2act := V2 /S2⊥ be the active spaces of Q1 , Q2 respectively. Then, there exists a bijection φ∗ : V2act → V1act s.t.3 : ⟨φ(a) | v2 ⟩ = ⟨a | φ∗ (v2 )⟩, ∀a ∈ S1 , ∀v2 ∈ V2act . For any x ∈ Q|A0 | O M O M JQ1 K(x) = RiD (⟨Ai | v1 ⟩) = RiD (⟨Ai | φ∗ (v2 )⟩) v1 ∈V1act : ⟨A0 |v1 ⟩=x i=1,m

v2 ∈V2act : ⟨A0 |φ∗ (v2 )⟩=x i=1,m

For i = 0, m, we have ⟨Ai | φ∗ (v2 )⟩ = ⟨Bi | v2 ⟩. Thus, JQ1 K(x) = JQ2 K(x) and JQ1 K = JQ2 K. Example 3.9. To showcase an application of Lemma 3.8, let us reconsider the CSPQ Q from Ex. 3.5: Q(2X + 2Z) ← A(X) · B(Y − X, Z − Y ) · C(Z). Perform the substitution φ given by: U = X, V = Y − X, W = Z − Y , and rewrite Q to Qφ (4U + 2V + 2W ) ← A(U ) · B(V, W ) · C(U + V + W ). Lemma 3.8 states that for any instances of A, B, C, the answers to Q are the same as to Qφ , i.e., JQK = JQφ K. To compute Qφ , it naturally suffices to iterate over values u, v, w, where u is in the support of A and (v, w) is in the support of B. We only need to keep tuples where u + v + w is in the support of C. For example, referring to the instances A, B, C in Fig. 1, it suffices to consider the following values to evaluate Qφ : (u, v, w) = (1, 0, 1), (2, −1, 0), (2, 0, −1), (2, 0, 1), (3, −1, 0), (3, 0, −1), (3, 0, 1), (4, −1, 0), (4, 0, −1) We grouped the tuples by the value of 4u + 2v + 2w. For each group we compute one output JQφ K(4u + 2v + 2w), as before. The result is the same as JQK depicted in Fig. 1.

4

Basic Algorithms

In this section, we describe two basic algorithms for evaluating a CSPQs. Our first result captures evaluation of CSPQs over dense tensors: Theorem 4.1 (Dense Evaluation). Let Q be a CSPQ and k = dim(span(Q)). Then, JQKD can be computed in time O(|adom(D)|k ). Our second result adapts Va worst-case optimal join (WCOJ) algorithm [32, 36, 31] from CQs to CSPQs. Recall that, if Q ← i=1,m Ri (Xi ) is a CQ and Y ⊆ var P(Q), then a fractional edge cover of Y is a tuple of weights w = (w1 , . . . , wm ) such that ∀Xj ∈ Y , i:Xj ∈Xi wi ≥ 1. The fractional edge P cover number is ρ∗ (Y ) = minw∈EC(Y ) i=1,m wi , where EC(Y ) is the set of fractional edge covers of ∗ Y . WCOJ algorithms compute JQKD in time O(|D|ρ (Q) ), where ρ∗ (Q) := ρ∗ (var (Q)). We begin by extending the definition of a fractional edge cover from CQs to CSPQs. N Definition 4.2. Let Q ← i=1,m Ri (Ai ) be a CSPQ. A fractional edge cover of a tuple of vectors C ⊆ span(Q) is a tuple of weights w = (w1 , . . . , wm ) where wi ∈ [0, 1], satisfying the following: !! ( ) [ \ X C ⊆ span span(Ai ) where I := I ⊆ {1, . . . , m} wi ≥ 1 . (7) I∈I

i∈I

i∈I

We denote the fractional edge cover number with ρ∗Q (C) := minw∈EC(C) i wi . When the query is clear from the context then we write simply ρ∗ (C), and denote ρ∗ := ρ∗ (Q) := ρ∗ (span(Q)). P

The classical fractional edge cover of a conjunctive query Q assigns weights to atoms so that every variable in var (Q) is covered by total weight at least one. We explain why, when restricted to convolutionfree queries, Definition 4.2 coincides with the classical one. Indeed, observe that a set of indices I belongs to the set I in Eq.(7) iff the set of atoms {Ri | i ∈ I} have in T a total weight ≥ 1. Since all vectors T A1 , . . . , Am are canonical basis vectors, the intersection span(A ) is the same as span( A i i ). i∈I i∈I

S T Condition span(Q) ⊆ span I∈I T i∈I span(Ai ) says “every canonical base vector ej (i.e. variable P Xj ) must be in some intersection i∈I Ai , i.e. must belong to a set of atoms Ri for which i wi ≥ 1”. This is the same T as saying that the variable Xj is covered by w. For a general CSPQ, for a set of atoms I, the intersection i∈I span(Ai ) consists of the linear combinations that all atoms in I can represent. The definition declares such a subspace available whenever the total weight of I is at least one, and asks these 3When both null spaces are S ⊥ = {0}, S ⊥ = {0} then φ∗ is simply the adjoint of φ (the transposed matrix). 1 2

7

subspaces to span the vectors being covered. Thus, ρ∗ is the minimum total weight needed to cover the vectors in span(Q). When the vectors in the tuples Ai are canonical basis vectors, these intersections are precisely the variables shared by the atoms in I, and the definition reduces to the usual fractional edge cover. In Lemma 4.11, we show how this generalizes the ρ∗ of a CQ. Our second result in this section is: ∗

Theorem 4.3 (Sparse Evaluation). Fix a CSPQ Q. JQKD can be computed in time O(|D|ρ (Q) ). In the rest of the section, we prove Theorems 4.1 and 4.3. The proofs rely on a reduction from the evaluation of a CSPQ to a traditional CQ. We start by considering a special case of a CSQP. S N Definition 4.4. A CSPQ Q ← i=1,m Ri (Ai ) is independent if {b1 , . . . , bk } = i=1,m Ai are linearly independent vectors. (Vectors bj are allowed to appear multiple times and we ignore the head.) Any convolution-free CSPQ (see Sec. 3) is an independent query. Conversely, if Q is independent, then we can obtain an equivalent convolution-free query by applying the substitution φ that maps b1 , . . . , bk to the canonical basis e1 , . . . , ek . This query, Qφ , when viewed as a SPQ with variables X1 , . . . , Xk , can be ∗ φ computed using a naive algorithm with runtime O(|adom(D)k |), or a WCOJ with runtime O(|D|ρ (Q ) ). Because JQK = JQφ K, we can evaluate Q in this runtime as well. In general, in order to evaluate a CSPQ we guard it with reducts. To that end, we call an S-relation P D : Qp → S Boolean if P D (x) = 0 or P D (x) = 1 for all x ∈ Qp ; with some abuse, we will also view P D as being interpreted in the Boolean semiring B. Fix an atom R(A). A reduct of R(A) is an atom P (C) where C is a tuple of linearly independent vectors s.t. C ⊆ span(A). Given an S-relation instance RD , we define a reduct of RD onto C as a Boolean S-relation instance satisfying: RD (⟨A | v⟩) ̸= 0 ⇒ P D (⟨C | v⟩) = 1, which implies RD (⟨A | v⟩) = RD (⟨A | v⟩) ⊗ P D (⟨C | v⟩), for all v ∈ Qd : in other words, adding the reduct P (C) does not change D the meaning of the atom R(A). A reduct P P can be computed in time O(|RD |) as follows. Represent each vector ci ∈ C as a linear combination ci = j λij aj of the vectors in A = (a1 , . . . , ar ). Then, P D can be P P computed by iterating over each tuple (u1 , . . . , ur ) ∈ supp(RD ) and inserting ( j λ1j uj , . . . , j λpj uj ) in supp(P D ); notice that |P D | ≤ |RD |. For example, if the atom is R(X + Y, Y, Z + W ) and the reduct is P (X, X − Y ) then supp(P D ) = {(u1 − u2 , u1 − 2u2 ) | (u1 , u2 , u3 ) ∈ supp(RD )}. Intuitively, one can think of reducts as being a generalization of projections. Given a CSPQ Q, we construct an independent (Def. 4.4) query G whose atoms are reducts of atoms from Q. We call G a reduct of Q and interpret it in the Boolean semiring, indicated by using ∧ instead of ⊗. However, we see JGK as a Boolean S-relation, i.e. with 0, 1 values. N V Definition 4.5. A reduct of Q ← i=1,m Ri (Ai ) is an independent CSPQ G(C0 ) ← j=1,n Pj (Cj ), where each Pj (Cj ) is a reduct of some atom Ri (Ai ). Observe that span(C0 ) ⊆ span(G) ⊆ span(Q). Adding G to Q does not affect its semantics: V N Lemma 4.6. N Let G(C0 ) ← j=1,n Pj (Cj ) be a reduct of Q(A0 ) ← i=1,m Ri (Ai ). Then Q is equivalent to Q′ (A0 ) ← i=1,m Ri (Ai ) ⊗ G(C0 ) in the following sense: for any instance D, if we instantiate the atom G(C0 ) in Q′ as the answer of G on D, GD := JGKD , then JQKD = JQ′ KD . The proof is immediate from the fact that adding a reduct does not change the meaning of the atom it is derived from. When span(C0 ) = span(Q), then we can compute JQK = JQ′ K by simply iterating over the tuples in JGK. In such a case, we call G a guard : Definition 4.7. Fix a CSPQ Q. An atom G(C0 ) of Q is a guard if span(Q) = span(C0 ). Lemma 4.8. If Q has a guard G(C0 ), then JQKD can be evaluated in time O(|GD |).

Proof Sketch. In the definition of JQKD given by Eq. (5), we can restrict the summation to vectors v ∈ V act = Qd /(span(Q))⊥ that satisfy JGK(⟨C0 | v⟩) ̸= 0. There are at most |GD | such vectors, because ⟨C0 | −⟩ : V act → Q|C0 | is injective, as (span(Q))⊥ = (span(C0 ))⊥ . Lemmas 4.6 and 4.8 lead to an algorithm to evaluate Q: Construct a reduct G of Q that acts as a guard. Evaluate the reduct traditionally, then leverage it to evaluate Q. We now prove Theorem 4.1.

8

Proof of Theorem 4.1. Choose S a basis b1 , . . . , bk of span(Q) such that each bj belongs to some tuple Ai : this is possible since span( i Ai ) = span(Q). For each bj ∈ Ai , let Pj (bj ) be a reduct of the atom D D R Vi (Ai ). Observe that this reduct has size |Pj | ≤ |adom(Ri )|. Form the reduct query G(b1 , . . . , bk ) ← j=1,k Pj (bj ). By applying the substitution bi 7→ ei , we transform it into an equivalent (by Lemma 3.8) traditional CQ Gφ , which is a cross product that can be computed in time O(adom(D)k ). The theorem then follows from Lemmas 4.6 and 4.8. Example 4.9. We reconsider the CSPQ Q from Ex. 3.5: Q(2X + 2Z) ← A(X) · B(Y − X, Z − Y ) · C(Z). A reduct of Q is the CSPQ G(X, Y − X, Z − Y ) ← A(X) · B(Y − X, Z − Y ) and, due to Lemma 4.6, Q is equivalent to Q′ (2X + 2Z) ← A(X) · B(Y − X, Z − Y ) · C(Z) · G(X, Y − X, Z − Y ) where G is a guard of Q′ . Since G is independent, we can use a variable substitution to transform it into a convolution-free CSPQ. Namely, we can use the substitution: U = X, V = Y − X, W = Z − Y . Thus, G can be evaluated in time O(|adom(D)|3 ). Using Lemma 4.8, we can also evaluate Q′ in time O(|adom(D)|3 ) and JQK = JQ′ K. Next, we prove Theorem 4.3. In order to evaluate JQKD , we construct, as before, a reduct G(C0 ) that acts as guard for Q and use Lemmas 4.6 and 4.8. This time we need to relate the fractional edge covering number ρ∗ of the CSPQ Q to the traditional ρ∗ of the CQ representing the reduct. Thus, the proof of the theorem relies on the careful analysis of ρ∗ . First, we show substitution invariance:

Lemma 4.10. If Q is a CSPQ, C ⊆ span(Q), and φ is a substitution, then ρ∗Q (C) = ρ∗Qφ (φ(C)). Proof. The lemma follows from Def. 4.2 and the fact that span(φ(Ai )) = φ(span(Ai )). Next, we prove that ρ∗ for convolution-free CSPQs coincides with ρ∗ for CQs: N V Lemma 4.11. Let Q ← i=1,m Ri (Ai ) be a convolution-free CSPQ, and let Q′ ← i=1,m Ri (Xi ) be the CQ obtained by replacing each ej with a variable Xj (we ignore the head variables in both queries). Then, for any subset of variables Xj1 , . . . , Xjk the following holds: ρ∗ (ej1 , . . . , ejk ) = ρ∗ (Xj1 , . . . , Xjk ). T Proof. For any I ⊆ {1, . . . , m} the vector space i∈I span(Ai ) is simply the vector space spanned by the canonical basis vectors ej for which ej ∈ Ai for all i ∈ I. Thus, for w to be a fractional edge cover of {ej1 , .P . . , ejk }, it has to be the case that for every ej ∈ {ej1 , . . . , ejk } there exists a I ⊆ {1, . . . , m} such that i∈I wi ≥ 1 and ej ∈ Ai for all i ∈ I. Therefore, w is also a traditional fractional edge cover of P ρ∗ (Xi1 , . . . , Xik ). Conversely, for a traditional fractional edge cover w, it holds that i:ej ∈Ai wi ≥ 1 for T any choice of Xj ∈ {Xi1 , . . . , Xik }. Thus, I := {i : ej ∈ Ai } ∈ I and ej ∈ i∈I span(Ai ). ∗

Thus, in order to evaluate Q in time O(|D|ρ ) it suffices to construct a guard G defined by a reduct G(C0 ) ← · · · with the same ρ∗ as Q, because, after substitution, the reduct is essentially a traditional CQ with the same ρ∗ . Next, we show how to construct such a reduct. N Lemma 4.12. V Fix a CSPQ Q ← i=1,m Ri (Ai ). For any tuple of vectors C ⊆ span(Q) there exists a reduct G(C) ← i=1,m Pi (Ci ) of Q such that ρ∗G (C) = ρ∗Q (C). Proof. Let w be an optimal fractional edge cover of C w.r.t.S Q, and P T denote by

I = {I ⊆ [m] | basis for the subspace span I∈I i∈I wi ≥ 1}. Let b1 , . . . , bk be aT i∈I span(Ai ) , such that, for each bj , there exists Ij ∈ I, bj ∈ i∈Ij span(Ai ). For each atom Ri (Ai ), define Ci the tuple of basis vectors bj that are in span(A V i ), i.e. Ci = span(Ai∗) ∩ {b1 , . .∗. , bk }, let Pi (Ci ) be a reduct of the atom Ri (Ai ), and define G ← i=1,m Pi (Ci ). To prove G (C) ≤ ρQ (C), we show that w is a valid fractional S ρT edge cover for G. We check that C ⊆ span( I∈I i∈I span(Ci )) by noting S T Tthat every basis vector bj is in the set I∈I i∈I span(Ci ): this holds because, by construction, bj ∈ i∈Ij span(Ai ), and, by the T definition of Ci , we also have bj ∈ i∈Ij span(Ci ). This proves ρ∗G (C) ≤ ρ∗Q (C), and equality follows as span(Ci ) ⊆ span(Ai ) for all i. We can now prove Theorem 4.3. S Proof of Theorem 4.3. Set C := i=1,m Ai , and use Lemma 4.12 to obtain a reduct G s.t. ρ∗ (Q) = ρ∗ (G) and G(C), viewed as an atom, is a guard for Q. We apply a substitution φ to obtain a convolution-free query Gφ with ρ∗ := ρ∗ (Gφ ) = ρ∗ (G) = ρ∗ (Q). We use a WCOJ algorithm to compute JGφ KD in time ∗ O(|D|ρ ), and observe that JGKD = JGφ KD (Lemma 3.8). Finally, we use Lemmas 4.6 and 4.8 to compute JQKD in the same time. 9

Example 4.13. Consider the following query over Q3 : Q(X, Y, Z) ← A(X, Y ) ⊗ B(Y, Z) ⊗ C(X + Y, Y + Z)

(8)

Theorem 4.1 leads to an algorithm with runtime O(|adom(D)|3 ). The weights w = (wA , wB , wC ) = (1, 1, 0) form a fractional edge cover of Q (all variables are in A, B), which leads to an algorithm with runtime O(|D|2 ). But we can do even better, by observing that w = ( 12 , 12 , 12 ) is also a fractional edge cover.4 Then, by Theorem 4.3, we can evaluate the query in time O(|D|3/2 ). We sketch the algorithm. We start by applying the substitution: U = X + Y, V = Y, W = Y + Z, and the query becomes Qφ (U − V, V, W − V ) ← A(U − V, V ) ⊗ B(V, W − V ) ⊗ C(U, W ). At this point we take the reduct of each atom onto the variables that are functionally determined by its attributes and obtain: G(U, V, W ) ← PA (U, V ) ∧ PB (V, W ) ∧ PC (U, W ). This query G can be evaluated in time O(|D|3/2 ) using Generic Join [32], then we can iterate over the (u, v, w) ∈ JGK answer tuples to compute JQφ K = JQK in the same time. Discussion. CSPQs are special cases of queries with general constraints discussed in FAQ-AI [17, 18, 38, 39]. Query (8) above is expressed in that formalism by replacing X + Y, Y + Z with new variables W, V , and adding four inequality conditions: Q ← A(X, Y ) ∧ B(Y, Z) ∧ C(W, V ) ∧ W ≤ X + Y ∧ W ≥ X + Y ∧ V ≤ Y + Z ∧ V ≥ Y + Z Previous techniques evaluate this query by starting from a tree decomposition that ensures that all variables of any constraint are included in two adjacent bags. In particular, two adjacent bags must contain X, Y, W , and similarly from Y, Z, V . The tree width is 2, leading to a runtime of O(|D|2 ); as we saw, our algorithm runs in time O(|D|3/2 ). At a high level, since CSPQs are a strict subset of the queries in FAQ-AI, they enable query evaluation techniques like Theorem 4.3 that are not possible in the general setting of FAQ-AI. For example, the conclusion section of [20] discusses the query Q ← R(X, Y ) ∧ S(Y, Z) ∧ X + Y = Z, observing that their current framework requires O(N 2 ) time to evaluate the query (where N = |R| + |S|). Expressed as a CSQP the query becomes Q ← R(X, Y ) ∧ S(Y, X + Y ), and its fractional edge cover is ρ∗ (Q) = 1, because w = (1, 0) is a fractional edge cover of Q. The algorithm implicit in the proof of Theorem 4.3 evaluates this query in time O(N ).

5

Tree Decompositions for CSPQ

Tree decompositions (TDs) speedup the evaluation of a traditional CQ by factorizing it and applying WCOJs to each factor [14, 31, 4]. In this section, we adapt the notion of TDs to CSPQs. In our new definition the bags are sets of vectors, and the connectedness condition (also called the running intersection property) incorporates the structure of the vector space.5 N Definition 5.1. Let Q(A0 ) ← i=1,m Ri (Ai ) be a CSPQ. A Convolution Tree Decomposition (CTD) of Q is a pair (T, χ) where T is a tree, and χ is a function that maps each node v ∈ V (T ) to a finite set of vectors χ(v) ⊆ span(Q) (called the bag of v) satisfying: 1. For every i = 0, m there exists a v ∈ V (T ) such that Ai ⊆ span χ(v). We choose one such v and call it the cover of Ai ; the root of T is the node r that covers A0 . 2. For each edge uv ∈ E(T ), span χ(Tu ) ∩ span χ(Tv ) = S span χ(u) ∩ span χ(v), where Tu , Tv are the subtrees obtained by removing the edge uv, χ(Tu ) := u′ ∈V (Tu ) χ(u′ ), eq. for χ(Tv ). A CTD generalizes TDs by replacing variables with vectors. In an ordinary tree decomposition, an atom is covered by a bag if all its variables occur in that bag; here, its argument vectors Ai must lie in the bag’s span. The running-intersection condition is generalized in the same way: every vector in the intersection of the spans of the two sides of an edge must lie in the spans of both adjacent bags. This 4We verify cond. (7): As {{A, B}, {B, C}, {C, A}} ⊆ I, it suffices to check that (span A ∩ span B) ∪ (span B ∩ span C) ∪ (span C ∩ span A) spans Q3 . We have span A = {(u, v, 0) | u, v}, span B = {(0, v, w) | v, w}, span C = {(u, u + w, w) | u, w} and the intersections are {(0, v, 0) | v}, {(0, w, w) | w}, {(u, u, 0) | u}: together, they span all of Q3 . 5We study query evaluation only under worst-case complexity, where the complexity depends only on the input size, not the output size. For that reason, we require all output variables to be part of a bag.

10

intersection is the interface through which the factorized computation passes messages. Any traditional TD can be viewed as a CTD by replacing each variable with its corresponding canonical basis vector. Under this identification, the coverage and running-intersection conditions are precisely those of traditional TDs. Example 5.2. Consider the following query: Q(X + Y ) ← A(X) ⊗ B(Y ) ⊗ C(Z − X − Y ) ⊗ D(Z). Clearly, this query can be solved in cubic time (e.g. using Theorem 4.1), and one can check that ρ∗ (Q) = 3, thus both algorithms in Sec. 4 require cubic time. However, we can solve this query in quadratic time, using the following CTD (T, χ): X +Y Z − X − Y, Z

X, Y

There are two nodes: the root χ(r) = {X, Y } covering A, B and a child χ(c) = {Z − X − Y, Z} covering C, D. We also show a basis for their intersection, X + Y . We can use this CTD to factorize Q into two subqueries: Qc (X + Y ) ← C(Z − X − Y ) ⊗ D(Z). and Qr (X + Y ) ← A(X) ⊗ B(Y ) ⊗ Qc (X + Y ) To show the correctness of this factorization, that is JQr K = JQK, we perform the variable substitution U = X, V = X + Y, W = Z and distribute: M M JQc K(v) = C(w − v) ⊗ D(w), JQK(v) = A(u) ⊗ B(v − u) ⊗ C(w − v) ⊗ D(w) = JQr K(v) w∈Q

u,w∈Q

These two subqueries Qc , Qr can be solved in quadratic time, so Q can be as well. In general, we use CTDs to factorize CSPQs, generalizing the way that traditional TDs are used to factorize SPQs. The key technical tool is the following lemma, which we prove in the appendix: N N Lemma 5.3 (Factorization Lemma). Let Q(A0 ) ← i=1,m Ri (Ai ) ⊗ j=1,n Sj (Bj ) be a CSPQ and consider the following two queries: O O Q1 (A0 ) ← Ri (Ai ) ⊗ Q2 (B0 ), Q2 (B0 ) ← Sj (Bj ) i=1,m

j=1,n

where B0 is a tuple of vectors s.t. span B0 =



span

S





i=0,m Ai ∩ span

S

 B . Then, on any j j=1,n

database D, we have JQKD = JQ1 KD , where the atom Q2 (B0 ) in Q1 is instantiated as JQ2 KD .

The lemma says that we can split the atoms of Q arbitrarily into R1 , R2 , . . . and S1 , S2 , . . ., evaluate first the subquery consisting of atoms Sj , then use that result together with the atoms Ri to get the final answer. The only condition is that the output vectors B0 must cover the intersection of the two subqueries. This is where we need to allow the span of a query to be a strict suspace of Qd : in general, both span(Q1 ) and span(Q2 ) may be strict subspace of Qd , even when span(Q) = Qd . We will apply Lemma 5.3 to fully factorize Q using a CTD (T, χ). Denote r its root, choose any child c, and let Tr , Tc be the subtrees after removing the edge rc. Denote by Ri (Ai ) the atoms coveredN by Tr , and by N Sj (Bj ) the atoms covered by Tc . Then we can write the query as Q(A0 ) ← i Ri (Ai ) ⊗ j Sj (Bj ) and apply Lemma 5.3, by choosing any basis B0 of span χ(c) ∩ span χ(r). We then recursively factorize the subqueries, Q1 , Q2 , using the fact that they have strictly smaller CTDs, namely Tc and Tr respectively. When the CTD becomes a single node v, then we are done. However, like for traditional CQ, this runs into slight technical complications when the bag χ(v) is larger than the span of the atoms covered by v. This problem is exacerbated by CSPQs. For example, a bag χ(v) = {X, Y } may cover an atom R(X) but no atom for the variable Y . The subquery at v would use fewer variables than mentioned in χ(v), violating the safety condition in Def. 3.1. This is resolved by shrinking bags’ spans to only the space required to 1) cover relations and 2) maintain connectedness. N Definition 0) ← i Ri (Ai ).SFor all v ∈ V (T ), define S 5.4. Let (T, χ) be a CTD of the CSPQ Q(A ζ(v) := i : Ai is covered by v Ai , and extend ζ to subtrees T ′ of T via ζ(T ′ ) := v∈V (T ′ ) ζ(v). We say that (T, χ) is a minimal CTD when it additionally satisfies the following: (3) For each v ∈ V (T ), we have (where Tu , Tv represent the two subtrees of T − uv) X span χ(v) = span ζ(v) + (span ζ(Tu ) ∩ span ζ(Tv )). u is adjacent to v

11

(9)

In any CTD, we have ζ(v) ⊆ χ(v), and, span ζ(Tu ) ∩ span ζ(Tv ) ⊆ span χ(Tu ) ∩ span χ(Tv ) ⊆ span χ(v) (by the connectedness condition). In a minimal CTD, χ(v) is only as large as needed to satisfy these two conditions. We note that any CTD can be converted into a minimal CTD: Lemma 5.5. Let (T, χ) be a CTD of Q. Then, there exists a minimal CTD (T, χ′ ) of Q where span χ′ (v) ⊆ span χ(v) for all v ∈ V (T ). For minimal CTDs, we can now give the full factorization (the proof is in the appendix). N Theorem 5.6 (Query Factorization). Let Q(A0 ) ← i Ri (Ai ) be a CSPQ and (T, χ) be a minimal CTD with root r. For each node v ∈ V (T ) we define the following subquery: O O Ri (Ai ) ⊗ Qc (B c ). (10) Qv (B v ) ← v covers Ri (Ai )

c∈child(v)

where B r := A0 , and for v ̸= r, B v is any basis of span χ(v) ∩ span χ(parent(v)). Then, JQK = JQr K.

Because (T, χ) is a minimal CTD, we have span χ(v) = span(Qv ) for all v ∈ V (T ). We call JQc K the message passed from the child c to the parent v.

6

Tree Decomposition Based Query Evaluation and Width Measures

In this section we show how to use CTDs to evaluate a CSPQ. While the basic idea is similar to evaluating traditional CQs using traditional TDs, CSPQ create a few new challenges. For example, the size of a message relation of arity k may exceed O(|adom(D)|k ). We describe three algorithms that tackle these challenges with runtimes characterized by three different width measures. Example 6.1. Throughout this section we will illustrate with the following running example. The following query generalizes the (k + 1)-SUM query to an interpretation in an arbitrary semiring: Q() ← A1 (X1 ) ⊗ · · · ⊗ Ak (Xk ) ⊗ B(X1 + X2 + · · · + Xk )

(11)

where |A1 |, . . . , |Ak |, |B| ≤ n. Recall that a fine-grained complexity assumption is that Q cannot be computed in time polynomially lower than O(n⌈(k+1)/2⌉ ) [1, 28]: none of our algorithms break this lower bound, but they generalize differently to arbitrary CSPQs. Consider the following CTD: X1 , X2

X1 + X2

X1 + X2 + X3 X1 + X2 , X3

X1 + X2 + X3 , X4

X1 + · · · + Xk−1 , Xk

There are k − 1 nodes, v1 , v2 , . . . , vk−1 , which cover {A1 , A2 }, {A3 }, . . . , {Ak−1 }, {Ak , B} respectively. Then, Theorem 5.6 leads to the following bottom-up (or left-to-right in our drawing) factorization: Qv1 (X1 + X2 ) ← A1 (X1 ) ⊗ A2 (X2 ),

Qvi (X1 + · · · + Xi+1 ) ← Ai+1 (Xi+1 ) ⊗ Qvi−1 (X1 + · · · + Xi ),

Qvk−1 () ← Ak (Xk ) ⊗ B(X1 + · · · + Xk ) ⊗ Qvk−2 (X1 + · · · + Xk−1 ) We can compute JQv1 K in time O(|A1 | · |A2 |) = O(n2 ), but JQv1 K can have size n2 . The message sizes increase in i, |JQvi K| ≤ ni+1 , leading to a complexity of O(nk ) for the naive bottom-up algorithm.

6.1

Evaluation Algorithm with respect to the Largest Integer

We start by examining the effect of the values in the active domain. In this section, we assume the active domain consists of integers; this is without generality, because we can multiply all rational numbers in the active domain with the least common multiple of their denominators, compute Q, then divide all domain values of the result by the same least common multiple. When adom(D) ⊆ Z, then we define n(D) := maxz∈adom(D) |z|. We show here that Q can be computed in time O(n(D)ctw(Q)+1 ), where ctw(Q) is the convolution tree width defined as follows:

12

Definition 6.2 (Convolution Treewidth). Let (T, χ) be a CTD of the CSPQ Q. The convolution treewidth of (T, χ), and of Q, are defined as ctw(T, χ) = max dim span χ(v) − 1, v∈V (T )

ctw(Q) = min ctw(T, χ). (T,χ)

Convolution treewidth measures a bag by the dimension of its span. The convolution treewidth is the maximum such dimension minus one; as with treewidth, this subtraction makes the runtime exponent ctw(Q) + 1. For integer-valued databases, intuitively, a k-dimensional bag has O(n(D)k ) possible values. Theorem 6.3. Let Q be a CSPQ and let D be a database with integer domain values, i.e., adom(D) ⊆ Z. Then JQKD can be computed in time O(n(D)ctw(Q)+1 ). Proof Sketch. Let (T, χ) be a width optimal CTD of Q. We evaluate Q bottom-up, using the Query Factorization Theorem 5.6, where each message Qv is computed using the dense algorithms given by Theorem 4.1. Consider the query Qv (B v ) shown in Eq. (10) and notice that (assume v = ̸ r here) we are allowed to pick the basis B v as we please. We pick the b ∈ B v to be integral linear combinations of the vectors in the body of Qv . Then, if n is the largest input domain value occurring in any supp(RiD ) or supp(JQc KD ), then the output values in supp(JQv KD ) are integers and of size O(n), because each such value is an integral linear combination of integers (the picked integral linear combination is query dependent and, thus, only affects the constant hidden by the big O notation). By Lemma 5.5 we can assume that (T, χ) is minimal, which implies dim(Qv ) = dim span χ(v), therefore, by induction along T , query (10) can be computed in time O(nctw(Q)+1 ) by Theorem 4.1. Example 6.4. Continuing Example 6.1, we notice that the convolution P treewidth is 1. Assume that adom(Ai ) ⊆ Z, let ni be the largest value of adom(Ai ), and set n := i ni . Then the largest value in adom(JQvi K) is n1 + . . . + ni , thus Q can be computed in time O(n2 ) = O(n(D)2 ).6

6.2

Evaluation Algorithm with respect to the Active Domain Size

Next, we examine an alternative method to compute each bag of a CTD in a runtime that depends only on the size of active domain of the input, and not on those of the increased active domain of the messages. The exponent is given as follows: N Definition 6.5. Fix a S CSPQ Q(A0 ) ← i=1,m Ri (Ai ) and let C0 ⊆ span(Q). A vector cover of C0 is a subset of vectors C ⊆ i Ai such that C0 ⊆ span(C). We denote with α(C0 ) := minC |C| the minimal size of a vector cover of C. Observe that dim span(C0 ) ≤ α(C0 ). A vector cover spans a set of vectors using body vectors. Its size can exceed dim span(C0 ): the body vectors that lie in span(C0 ) may not suffice to span C0 . A cover may therefore need vectors outside span(C0 ), so span(C) can be strictly larger than span(C0 ). This quantity captures how many body vectors are needed to cover the vectors in a bag. Definition 6.6 (Active Treewidth). Let (T, χ) be a CTD of the CSPQ Q. Then, the active treewidth of (T, χ) and Q are defined as atw(T, χ) = max α(χ(v)) − 1,

atw(Q) = min atw(T, χ).

v∈V (T )

(T,χ)

Active treewidth measures a bag by the minimum number of body vectors needed to span it. As with treewidth, we subtract one from the maximum bag size. Unlike convolution treewidth, it reflects the cost of constructing a guard from the input relations rather than enumerating values in the bag’s span. A vector cover of size k yields a reduct guard computable in time O(|adom(D)|k ), which explains the exponent atw(Q) + 1. Theorem 6.7. Let Q be a CSPQ. Then, JQK can be computed in time O(|adom(D)|atw(Q)+1 ).

6 Of course, this does not contradict the (k + 1)-SUM conjecture, because this runtime depends on the maximum value in the database instead of on the number of values |adom(D)| as in Example 6.1. In particular, if instead we choose the input relation Ai to have active domain adom(Ai ) = {j · ni−1 | j = 0, 1, . . . , n − 1}, then supp(JQvi K) = {0, . . . , ni+1 − 1} has size ni+1 , leading to a total runtime of O(nk ) = O(|adom(D)|k ).

13

Proof Sketch. Fix a CTD (T, χ) of Q. We combine the results of Sec. 4 and Sec. 5 to obtain this result. The idea is to first add reducts to Q such that after applying the Factorization Theorem 5.6 that all subqueries Qv are guarded. Fix a node v ∈ V (T ), denote C0v := χ(v), and let C = (b1 , . . . , bk ) be a vector cover of C0v of size k := α(C0v ). For each bj , let Ri (Ai ) be an V atom such that bj ∈ Ai . We compute the reducts Pj (bj ) of Ri (Ai ), and denote with Gv (C0v ) ← j=1,k Pj (bj ) a reduct of Q. By Theorem 4.1, JGv KD can be computed in time O(|adom(D)|α(χ(v)) ). By Lemma 4.6, we can add an atom Gv (C0v ) to Q without affecting the semantics. We repeat this process for all tree nodes v ∈ V (T ). Then, (T, χ) is still valid CTD of the modified query. We compute the query bottom-up on the tree, using the Factorization Theorem 5.6. Each query Qv can be computed in time O(|JGv K|) by Lemma 4.8, because it is guarded by Gv . Thus, the runtime is dominated by the time needed to compute reducts, which is O(|adom(D)|atw(Q)+1 ). Example 6.8. Continuing Example 6.1 consider the bag χ(vi ) = {X1 + · · · + Xi , Xi+1 }. There are two relevant vector covers for χ(vi ): either X1 , X2 , . . . , Xi+1 , or Xi+1 , Xi+2 , . . . , Xk , X1 + · · · + Xk . We choose the smallest cover for each and add reducts to the query (10). The reducts are: Gv1 (X1 , X2 ) ← A1 ∧ A2 ,

Gv2 ← A1 ∧ A2 ∧ A3 ,

vk−2

...

vk−1

(Xk−1 , X1 + · · · + Xk−2 ) ← Ak−1 ∧ Ak ∧ B, G (Xk , X1 + · · · + Xk ) ← Ak ∧ B N N The modified query is Q′ ← i Ai ⊗ B ⊗ v Gv and after factorization we have G

Q′v1 (X1 + X2 ) ← A1 ⊗ A2 ⊗ Gv1 , ′vk−1

Q

′vk−2

() ← Ak ⊗ B ⊗ Q

⊗G

Q′vi (X1 + · · · + Xi+1 ) ← Ai+1 ⊗ Q′vi−1 ⊗ Gvi ,

vk−1

This leads to an algorithm with runtime O(|adom(D)|⌈(k+1)/2⌉ ) where the dominating part is the processing of the node v⌈(k−1)/2⌉ and the evaluation of the reduct Gv⌈(k−1)/2⌉ . Note that this is precisely the optimal runtime for the (k + 1)-SUM often assumed. In general, ctw(Q) ≤ atw(Q), but the runtimes of Theorem 6.3 and 6.7 are incomparable, because the basis of the runtimes are ordered in the opposite direction: n(D) ≥ |adom(D)|. However, we notice that, if Q is a traditional CQ, then ctw(Q) = atw(Q) and both agree with the traditional treewidth of Q because every minimal CTD is equivalent to a traditional TD.

6.3

Evaluation Algorithm with respect to the Database Size

Lastly, we describe an algorithm that uses the same idea as employed in Sec. 6.2, but uses Theorem 4.3 to evaluate the reducts. Definition 6.9 (Fractional Convolution Hypertree Width). Let (T, χ) be a CTD of the CSPQ Q. Then, the fractional convolution hypertree width of (T, χ) and Q are defined as fcw(T, χ) = max ρ∗ (χ(v)), v∈V (T )

fcw(Q) = min fcw(T, χ) (T,χ)

Fractional convolution hypertree width measures each bag by the fractional edge cover number of its span rather than by its dimension. The resulting width captures the cost of constructing a sparse guard for each bag: the guard can be computed by the sparse algorithm, and the largest bag cost dominates the factorized evaluation. Thus, this is the CSPQ analogue of fractional hypertree width. Theorem 6.10. Let Q be a CSPQ. Then, JQK can be computed in time O(|D|fcw(Q) ). Proof Sketch. We proceed similar to in the proof of Theorem 6.7 but define the reducts differently. Let (T, χ) be a width optimal CTD.VFix a node v ∈ T (V ) and denote C0v := χ(v). By Lemma 4.12 we can construct a reduct Gv (C0v ) ← i=1,m Pi (Ci ) such that ρ∗Gv (C0v ) = ρ∗ (C0v ). We evaluate Gv in time ∗ O(|D|ρ (χ(v)) ) using Theorem 4.1. Then, we continue as in the proof of Theorem 6.7 verbatim. The total runtime is O(|D|fcw(Q) ) because it is dominated by the evaluation of the reducts. We sketch the algorithm on an example:

14

Example 6.11. Let Q(Y +Z) ← R1 (W +X, X +Y )⊗R2 (W, X)⊗R3 (X, Y )⊗R4 (Y, Z)⊗R5 (X +Y, Y +Z). Further, consider the following minimal CTD with width fcw = 23 : X, Y W, X, Y

X, Y, Z

To cover the left bag χ(c), we can use the fractional edge cover ( 12 , 12 , 12 , 0, 0) while we use (0, 0, 21 , 12 , 21 ) for the right bag χ(r). Then, to compute JQK, we would add the reducts Gc (W, X, Y ) ← R1 ∧ R2 ∧ R3 , Gr (X, Y, Z) ← R3 ∧ R4 ∧ R5 , N to Q. Then, Theorem 5.6 applied to Q′ ← i Ri ⊗ Gc ⊗ Gr gives us the guarded queries Qc (X, Y ) ← R1 ⊗ R2 ⊗ R3 ⊗ Gc ,

Qr (Y + Z) ← R4 ⊗ R5 ⊗ Qc ⊗ Gr .

Each of these four queries Gc , Gr , Qc , Qr can be solved in time O(|D|3/2 ) and, JQK = JQr K.

For traditional CQs Q, the value fcw(Q) coincides with the fractional tree width f htw(Q). Further, our width notions are invariant under variable substitutions. For any CSPQ Q and substitution φ: ctw(Q) = ctw(Qφ ),

7

atw(Q) = atw(Qφ ),

fcw(Q) = fcw(Qφ )

CSPQs over other Fields

Up to this point, we always considered databases and CSPQs where the underlying field of domain elements were the rationals Q. However, this was only relevant in Theorem 6.3 and was actually never used anywhere else. Thus, all other statements hold equally when Q is replaced by an arbitrary field F. However, one can also give an algorithm whose runtime has ctw(Q) + 1 as its exponent for fields with positive characteristic7 p > 0. The idea of the algorithm in Section 6.1 was to have a runtime of O(nctw(T,χ)+1 ) where n is an upper bound on the number of field elements that may appear in one of the relations in the body of the query Q or in one of the messages JQc K. With this in mind, let us denote the field elements used in Q by adom(Q) ⊆ F (i.e., the coefficients in A0 , . . . , Am ) and write adom(D, Q) := adom(D) ∪ adom(Q). All field elements used by the messages must be derived from adom(D, Q). Hence, if adom(D, Q) is contained in some finite subfield of F of size n, then also the messages will use only these n field elements: We denote with n(D, Q) the size of the smallest subfield containing adom(D, Q). Theorem 7.1. For fields with positive characteristic, Q can be evaluated in time O(n(D, Q)ctw(Q)+1 ).

8

Conclusion and Future Work

In this paper, we extended sum-product queries to allow linear expressions over variables, resulting in convolution sum-product queries (CSPQs). We then adapted worst-case optimal join algorithms to this setting. Further, we used convolution tree-decompositions to factorize CSPQs and presented three width measures that bound the complexity of CSPQ evaluation relative to different notions of input size. We then extended this to queries over arbitrary fields. Several directions suggest themselves for future work. A natural first step is to identify further problems that can be expressed directly as CSPQs and to study how the techniques developed here perform on them. Such examples could clarify which features of a problem are captured by the three width measures, and could suggest additional structural parameters or specialized evaluation methods. Exact-weight problems provide a particularly interesting test case for this program. The exact-weight subgraph problems studied in [1] can be expressed as CSPQs. However, our current algorithms do not always match the conditional lower bounds proven in [1] for these problems. Matching these bounds may require incorporating additional information, such as functional dependencies, into the evaluation framework and the definition of width. For example, the 4-path exact-weight problem in [1] asks whether a graph with n nodes and weighted edges has a path E(A, B), E(B, C), E(C, D) whose weights sum to exactly 0. Theorem 2 in [1] proves that, under 7 Recall, a field F has characteristic p > 0 when adding 1 p-times gives 0 while adding 1 less times does not give 0.

15

the k-SUM conjecture, this is not possible in time O(n3−ε ). It turns out to be difficult to model exact sum queries as either SPQs or CSQPs. For example, to write this query as an SPQ we need a semiring (Q, ⊕, ⊗, 0, 1) where ⊗ = + (because we need to add the three weights E(A, B) + E(B, C) + E(C, D)), but how should we define ⊕? We need an operator such that x1 ⊕ x2 ⊕ · · · distinguishes between the cases when 0 ∈ {x1 , x2 , . . .} and 0 ̸∈ {x1 , x2 , . . .}, and at the same time + (which is our ⊗) distributes over ⊕, i.e. (x1 ⊕ x2 ⊕ · · · ) + y = (x1 + y) ⊕ (x2 + y) ⊕ · · · . No such operator seems to exists. Another option for the 4-path query is to express it as a CSQP over the Boolean semiring, similarly to our 3SUM query: Q() ← E(A, B, X) ∧ E(B, C, Y ) ∧ E(C, D, −X − Y ), where the third argument of E carries the weight of the edge. Then, a valid Convolution Tree Decomposition is {A, B, C, X, Y } − {C, D, −X − Y }. However, to evaluate the “size” of the bag, we have to use the fact that the following functional dependencies hold: A, B → X, B, C → Y, C, D → −X − Y . In that case, we can assert that the bags have size 3 and the algorithm runs in time O(n3 ). This suggests that it may be possible to extend CTDs to evaluate this query in time O(n3 ), matching the lower bound in [1], but this requires new techniques like handling functional dependencies. We leave this for future work. On the algorithmic side, non-combinatorial techniques may further improve CSPQ evaluation over semirings such as the standard (+, ·) semiring and the Boolean (∨, ∧) semiring. Fast matrix multiplication and fast Fourier transforms are two examples of techniques that may apply, depending on the semiring and the structure of the query. A systematic characterization of when such techniques can be used for CSPQ evaluation would be valuable. Another direction is to develop a CSPQ analogue of (#)-submodular width. On the complexity-theoretic side, conditional lower bounds for CSPQs could be derived from conjectures such as (min, +)-convolution and k-SUM. Conversely, hardness conjectures for CSPQs might yield tighter lower bounds for restricted classes of SPQs. Finally, one could extend the algebraic foundations beyond linear algebra over fields. This may lead to query languages with non-linear expressions or with domain elements from non-field algebraic structures such as groups, together with new notions of decomposition and width suited to those settings.

References [1] A. Abboud and K. Lewi. Exact weight subgraphs and the k-sum conjecture. In F. V. Fomin, R. Freivalds, M. Z. Kwiatkowska, and D. Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, Lecture Notes in Computer Science, pages 1–12. Springer, 2013. [2] F. N. Afrati, C. Li, and P. Mitra. On containment of conjunctive queries with arithmetic comparisons. In E. Bertino, S. Christodoulakis, D. Plexousakis, V. Christophides, M. Koubarakis, K. Böhm, and E. Ferrari, editors, Advances in Database Technology - EDBT 2004, 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004, Proceedings, Lecture Notes in Computer Science, pages 459–476. Springer, 2004. [3] F. N. Afrati, C. Li, and P. Mitra. Rewriting queries using views in the presence of arithmetic comparisons. Theor. Comput. Sci., 368(1-2):88–123, 2006. [4] A. Atserias, M. Grohe, and D. Marx. Size bounds and query plans for relational joins. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 739–748. IEEE Computer Society, 2008. [5] R. Baghdadi, J. Ray, M. B. Romdhane, E. D. Sozzo, A. Akkas, Y. Zhang, P. Suriana, S. Kamil, and S. P. Amarasinghe. Tiramisu: A polyhedral compiler for expressing fast and portable code. In M. T. Kandemir, A. Jimborean, and T. Moseley, editors, IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2019, Washington, DC, USA, February 16-20, 2019, pages 193–205. IEEE, 2019. [6] K. Bringmann and E. Gorbachev. A fine-grained classification of subquadratic patterns for subgraph listing and friends. CoRR, abs/2404.04369, 2024. [7] N. R. Brisaboa, H. J. Hernández, J. R. Paramá, and M. R. Penabad. Containment of conjunctive queries with built-in predicates with variables and constants over any ordered domain. In W. Litwin,

16

T. Morzy, and G. Vossen, editors, Advances in Databases and Information Systems, Second East European Symposium, ADBIS’98, Poznan, Poland, September 7-10, 1998, Proceedings, Lecture Notes in Computer Science, pages 46–57. Springer, 1998. [8] T. Chen, T. Moreau, Z. Jiang, L. Zheng, E. Q. Yan, H. Shen, M. Cowan, L. Wang, Y. Hu, L. Ceze, C. Guestrin, and A. Krishnamurthy. TVM: an automated end-to-end optimizing compiler for deep learning. In A. C. Arpaci-Dusseau and G. Voelker, editors, 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2018, Carlsbad, CA, USA, October 8-10, 2018, pages 578–594. USENIX Association, 2018. [9] M. Cygan, M. Mucha, K. Wegrzycki, and M. Wlodarczyk. On problems equivalent to (min, +)convolution. ACM Trans. Algorithms, 15(1):14:1–14:25, 2019. [10] K. Datta, M. Murphy, V. Volkov, S. Williams, J. Carter, L. Oliker, D. A. Patterson, J. Shalf, and K. A. Yelick. Stencil computation optimization and auto-tuning on state-of-the-art multicore architectures. In Proceedings of the ACM/IEEE Conference on High Performance Computing, SC 2008, November 15-21, 2008, Austin, Texas, USA, page 4. IEEE/ACM, 2008. [11] P. Getreuer. Contour stencils for edge-adaptive image interpolation. In Visual Communications and Image Processing 2009, volume 7257, pages 394–406. SPIE, 2009. [12] G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci., 64(3):579–627, 2002. [13] T. J. Green, G. Karvounarakis, and V. Tannen. Provenance semirings. In L. Libkin, editor, Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 11-13, 2007, Beijing, China, pages 31–40. ACM, 2007. [14] M. Grohe and D. Marx. Constraint solving via fractional edge covers. ACM Trans. Algorithms, 11(1):4:1–4:20, 2014. [15] J. Holewinski, L. Pouchet, and P. Sadayappan. High-performance code generation for stencil computations on GPU architectures. In U. Banerjee, K. A. Gallivan, G. Bilardi, and M. Katevenis, editors, International Conference on Supercomputing, ICS’12, Venice, Italy, June 25-29, 2012, pages 311–320. ACM, 2012. [16] O. H. Ibarra and J. Su. A technique for proving decidability of containment and equivalence of linear constraint queries. J. Comput. Syst. Sci., 59(1):1–28, 1999. [17] M. A. Khamis, R. R. Curtin, B. Moseley, H. Q. Ngo, X. Nguyen, D. Olteanu, and M. Schleich. On functional aggregate queries with additive inequalities. In D. Suciu, S. Skritek, and C. Koch, editors, Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pages 414–431. ACM, 2019. [18] M. A. Khamis, R. R. Curtin, B. Moseley, H. Q. Ngo, X. Nguyen, D. Olteanu, and M. Schleich. Functional aggregate queries with additive inequalities. ACM Trans. Database Syst., 45(4):17:1–17:41, 2020. [19] M. A. Khamis, H. Q. Ngo, D. Olteanu, and D. Suciu. Boolean tensor decomposition for conjunctive queries with negation. In P. Barceló and M. Calautti, editors, 22nd International Conference on Database Theory, ICDT 2019, Lisbon, Portugal, March 26-28, 2019, LIPIcs, pages 21:1–21:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. [20] M. A. Khamis, H. Q. Ngo, and A. Rudra. FAQ: questions asked frequently. CoRR, abs/1504.04044, 2015. [21] A. Kiani and N. Shiri. Answering queries with arithmetic expressions in heterogeneous systems. In A. Hahn, S. Abels, and L. Haak, editors, Proceedings of the first international ACM workshop on Interoperability of Heterogeneous Information Systems (IHIS’05), CIKM Conference, Bremen, Germany, November 4, 2005, pages 17–24. ACM, 2005. 17

[22] A. Kiani and N. Shiri. Containment of conjunctive queries with arithmetic expressions. In R. Meersman, Z. Tari, M. Hacid, J. Mylopoulos, B. Pernici, Ö. Babaoglu, H. Jacobsen, J. P. Loyall, M. Kifer, and S. Spaccapietra, editors, On the Move to Meaningful Internet Systems 2005: CoopIS, DOA, and ODBASE, OTM Confederated International Conferences CoopIS, DOA, and ODBASE 2005, Agia Napa, Cyprus, October 31 - November 4, 2005, Proceedings, Part I, Lecture Notes in Computer Science, pages 439–452. Springer, 2005. [23] A. Kiani and N. Shiri. A framework for information integration with uncertainty. In F. F. R. Corchado, V. M. Larios-Rosillo, and H. Unger, editors, Advanced Distributed Systems: 5th International School and Symposium, ISSADS 2005, Guadalajara, Mexico, January 24-28, 2005, Revised Selected Papers, Lecture Notes in Computer Science, pages 194–206. Springer, 2005. [24] A. C. Klug. On conjunctive queries containing inequalities. J. ACM, 35(1):146–160, 1988. [25] P. Koutris, T. Milo, S. Roy, and D. Suciu. Answering conjunctive queries with inequalities. Theory Comput. Syst., 61(1):2–30, 2017. [26] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In P. L. Bartlett, F. C. N. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, pages 1106–1114, 2012. [27] G. M. Kuper, L. Libkin, and J. Paredaens, editors. Constraint Databases. Springer, 2000. [28] A. Lincoln, V. Vassilevska Williams, J. R. Wang, and R. R. Williams. Deterministic time-space trade-offs for k-sum. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, and D. Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, July 11-15, 2016, LIPIcs, pages 58:1–58:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. [29] F. Luporini, M. Louboutin, M. Lange, N. Kukreja, P. A. Witte, J. Hückelheim, C. Yount, P. H. J. Kelly, F. J. Herrmann, and G. J. Gorman. Architecture and performance of devito, a system for automated stencil computation. ACM Trans. Math. Softw., 46(1):6:1–6:28, 2020. [30] G. Moerkotte and T. Neumann. Dynamic programming strikes back. In J. T. Wang, editor, Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008, pages 539–552. ACM, 2008. [31] H. Q. Ngo, E. Porat, C. Ré, and A. Rudra. Worst-case optimal join algorithms: [extended abstract]. In M. Benedikt, M. Krötzsch, and M. Lenzerini, editors, Proceedings of the 31st ACM SIGMODSIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages 37–48. ACM, 2012. [32] H. Q. Ngo, C. Ré, and A. Rudra. Skew strikes back: new developments in the theory of join algorithms. SIGMOD Rec., 42(4):5–16, 2013. [33] J. Ragan-Kelley, C. Barnes, A. Adams, S. Paris, F. Durand, and S. P. Amarasinghe. Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines. In H. Boehm and C. Flanagan, editors, ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’13, Seattle, WA, USA, June 16-19, 2013, pages 519–530. ACM, 2013. [34] D. Srivastava. Subsumption and indexing in constraint query languages with linear arithmetic constraints. Ann. Math. Artif. Intell., 8(3-4):315–343, 1993. [35] S. Tavarageri, A. Heinecke, S. Avancha, B. Kaul, G. Goyal, and R. Upadrasta. Polydl: Polyhedral optimizations for creation of high-performance DL primitives. ACM Trans. Archit. Code Optim., 18(1):11:1–11:27, 2021.

18

[36] T. L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In N. Schweikardt, V. Christophides, and V. Leroy, editors, Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014, pages 96–106. OpenProceedings.org, 2014. [37] S. Verdoolaege, J. C. Juega, A. Cohen, J. I. Gómez, C. Tenllado, and F. Catthoor. Polyhedral parallel code generation for CUDA. ACM Trans. Archit. Code Optim., 9(4):54:1–54:23, 2013. [38] Q. Wang and K. Yi. Conjunctive queries with comparisons. SIGMOD Rec., 52(1):54–62, 2023. [39] Q. Wang and K. Yi. Conjunctive queries with comparisons. ACM Trans. Database Syst., 51(2):7:1– 7:37, 2026.

19

A

Full Proofs for Section 3

Here, we give the missing/complete proofs of the lemmas of Section 3 Lemma 3.3. JQKD is an S-relation (meaning: it is well-defined and has finite support). Proof. We have to show two things: 1) We have to show that the infinite sum on the right hand side of Equation (5) is well-defined, i.e., that it only consists of finitely many non-0 terms. 2) We have to N show that the support of JQK is finite. Fix a CSPQ Q(A0 ) ← i=1,m Ri (Ai ) over Qd with active space V act . To prove 1), let us fix a x ∈ Q|A0 | and assume towards a contradiction that infinitely many distinct u1 , · · · ∈ V act such that for all j O uj ∈ V act : x = ⟨A0 | uj ⟩, and Ri (⟨Ai | uj ⟩) ̸= 0. i=1,m

This implies that for any i, j combination also Ri (⟨Ai | uj ⟩) ̸= 0. However, the support of each Ri is finite. Thus, there must exist some uj1 and uj2 such that for all i ⟨Ai | uj1 ⟩ = ⟨Ai | uj2 ⟩. S S Consequently, ⟨a | uj1 − uj2 ⟩ = 0 for any a ∈ i=1,m Ai . I.e., uj1 − uj2 = 0 ∈ Qd /( i=1,m Ai )⊥ . Put differently, uj1 = uj2 , contradicting the assumption that uj1 and uj2 are distinct. Thus, JQK : Q|A0 | → S is well-defined. For 2) assume towards a contradiction that infinitely many distinct x1 , · · · ∈ Q|A0 | such that for all j JQK(xj ) ̸= 0.

Thus there are also u1 , · · · ∈ V act such that xj = ⟨A0 | uj ⟩,

and

∀i = 1, m : Ri (⟨Ai | uj ⟩) ̸= 0.

Again, the support of each Ri is finite. Thus, there must exist some uj1 and uj2 such that for all i ⟨Ai | uj1 ⟩ = ⟨Ai | uj2 ⟩. Then, also xj1 = ⟨A0 | uj1 ⟩ = ⟨A0 | uj2 ⟩ = xj2 This contradict the assumption that xj1 and xj2 are distinct. N Lemma 3.8 (Variable Substitution). Let Q1 (A0 ) ← i=1,m Ri (Ai ) be a CSQP over V1 := Qd1 , and let φ : span(Q1 ) → V2 beNa substitution, where V2 := Qd2 . Define Bi := φ(Ai ) for i = 0, m, and consider the query Q2 (B0 ) ← i=1,m Ri (Bi ). Then Q1 , Q2 are equivalent: ∀D, JQ1 KD = JQ2 KD . Proof. Denote S1 := span(Q1 ), S2 := span(Q2 ) and notice that S2 = φ(S1 ). Let V1act := V1 /S1⊥ , V2act := V2 /S2⊥ be the active spaces of Q1 , Q2 respectively. We claim that there exists a linear, injective function φ∗ : V2 /S2⊥ → V1 /S1⊥ with the following property:8 ∀v1 ∈ V1 ,

∀[u2 ] ∈ V2 /S2⊥ :

⟨φ(v1 ) | [u2 ]⟩ =⟨v1 | φ∗ ([u2 ])⟩

(12)

The claim suffices to prove the lemma, because φ∗ is also a bijection (since dim(V2 /S2⊥ ) = dim(V1 /S1⊥ ), because dim(Vi /Si⊥ ) = dim(Si ) for i = 1, 2, and dim(S2 ) = dim(φ(S1 )) = dim(S1 )); then ∀x ∈ Q|A0 | , M O JQ1 K(x) = RiD (⟨Ai | [v1 ]⟩) [v1 ]∈V1act : ⟨A0 |[v1 ]⟩=x

=

i

M

O

[v2 ]∈V2act : ⟨A0 |φ∗ ([v2 ])⟩=x

=

RiD (⟨Ai | φ∗ ([v2 ])⟩)

i

M

O

[v2 ]∈V2act : ⟨φ(A0 )|[v2 ]⟩=x

i

RiD (⟨φ(Ai ) | [v2 ]⟩)

8When both null spaces are S ⊥ = {0}, S ⊥ = {0} then φ∗ is the adjoint of φ (the transposed matrix). 1 2

20

=

M

O

[v2 ]∈V2act : ⟨B0 |[v2 ]⟩=x

i

RiD (⟨Bi | [v2 ]⟩)

= JQ2 K(x) It remains to prove the existence of φ∗ . Fix a vector v2 ∈ V2 , and consider the function f : S1 → Q, given by f (v1 ) := ⟨φ(v1 ) | [v2 ]⟩. Since this is a linear function, there exists a vector z ∈ V1 such that f (v1 ) = ⟨v1 | z⟩ for all v1 ∈ V1 . Define φ∗ ([v2 ]) := [z] ∈ V1 /S1 . The function φ∗ : V2act → V1act is well defined, because if ⟨v1 | [z]⟩ = ⟨v1 | [z ′ ]⟩ for all v1 ∈ S1 , then ⟨v1 | z − z ′ ⟩ = 0 for all v1 ∈ S1 , implying z − z ′ ∈ S1⊥ , hence [z] = [z ′ ]. This proves the existence of φ∗ satisfying (12); linearity of φ∗ follows immediately from the linearity of φ and of the dot product. It remains to prove that it is injective. If φ∗ ([v2 ]) = φ∗ ([v2′ ]) then ⟨φ(v1 ) | [v2 ]⟩ = ⟨φ(v1 ) | [v2′ ]⟩ for all v1 ∈ S1 , which, by definition, implies ⟨φ(v1 ) | v2 ⟩ = ⟨φ(v1 ) | v2′ ⟩, i.e. v2 − v2′ ∈ S2⊥ , hence [v2 ] = [v2′ ]. This proves the claim, and completes the proof of the lemma.

B

Full Proofs for Section 4

Before giving the missing proofs of Section 4, we formally state and proof that 1) we can evaluate convolution-free CSPQs using traditional conjunctive query evaluation algorithms and 2) we can compute a reduct P (C) of R(A) in linear time: N S Lemma B.1. Let Q(A0 ) ← N i=1,m Ri (Ai ) be a convolution-free CSPQ (that is, i=1,m Ai = {e1 , . . . , ed }). Further, let C(X1 , . . . , Xd ) ← i=1,m Ri (Ei ) be the full SPQ with the same body as Q but where ej is replaced by the corresponding variable Xj . Then, JQK can be computed in time O(|adom(D)|d ) and time ∗ O(|D|ρ (C) ) Proof. First notice that the active space of Q is V act = Qd /{e1 , . . . , ed }⊥ = Qd /{0}. Thus, clearly, there is a bijection between valuations v : {X1 , . . . , Xd } → Q and elements [(v1 , . . . , vd )] ∈ V act by equating vj = v(Xj ) for all j = 1, d. Furthermore, under this bijection O O Ri (⟨Ai | [(v1 , . . . , vd )]⟩) = Ri (v(Ei )) i=1,m

i=1,m

and the non-0 term are precisely the support of JCK. Thus, to evaluate Q is suffices to go over the (v1 , . . . , vd ) ∈ JCK group them by ⟨A0 | [(v1 , . . . , vd )]⟩ and aggregate via ⊕. That is, M O JQK(x) = Ri (⟨Ai | [(v1 , . . . , vd )]⟩). (v1 ,...,vd )∈JCK i=1,m

∗

As C can be evaluated in time O(|adom(D)|d ) and time O(|D|ρ (C) ), also Q can be evaluated in the same time frame. Lemma B.2. Let P (C) be a reduct of R(A). Then, we can compute a reduct P D , i.e., a Boolean S-relation P D such that ∀v ∈ Qd : RD (⟨A | v⟩) ̸= 0 ⇒ P D (⟨C | v⟩) = 1, in time O(|RD |). P Proof. Since C ⊆ span(A) we can represent each vector ci ∈ C as a linear combination ci = j=1,r λij aj of the vectors in A = (aP let us define P D by iterating over each tuple (u1 , . . . , ur ) ∈ 1 , . . . , ar ). Then, P D supp(R ) and setting ( j=1,r λ1j uj , . . . , j=1,r λpj uj ) 7→ 1 in P D . All other tuples Q|C| are not in supp(P D ). Then, clearly, |P D | ≤ |RD | and this process only takes time O(|RD |). Now lets d fix such that RD (⟨A | v⟩) ̸= 0. Then, ⟨A | v⟩ = (u1 , . . . , ur ) ∈ supp(RD ) and P a v ∈ Q be P ( j=1,r λ1j uj , . . . , j=1,r λpj uj ) 7→ 1 in P D . Further, notice that ⟨C | v⟩ = ⟨(c1 , . . . , cd ) | v⟩ = (⟨c1 | v⟩, . . . , ⟨cd | v⟩) 21

=(

X

λ1,j ⟨aj | v⟩, . . . ,

j=1,r

=(

X

X

λd,j ⟨aj | v⟩)

j=1,r

λ1,j uj , . . . ,

j=1,r

X

λd,j uj ).

j=1,r

Thus, P D (⟨C | v⟩) = 1 as required. V N Lemma 4.6. N Let G(C0 ) ← j=1,n Pj (Cj ) be a reduct of Q(A0 ) ← i=1,m Ri (Ai ). Then Q is equivalent to Q′ (A0 ) ← i=1,m Ri (Ai ) ⊗ G(C0 ) in the following sense: for any instance D, if we instantiate the atom G(C0 ) in Q′ as the answer of G on D, GD := JGKD , then JQKD = JQ′ KD . Proof. We only have to show for any v ∈ Qd that O O Ri (⟨Ai | v⟩) = Ri (⟨Ai | v⟩) ⊗ JGK(⟨C0 | v⟩). i=1,m

i=1,m

N To that end let us assume i=1,m Ri (⟨Ai | v⟩) ̸= 0 as equality otherwise trivially holds. Then, for every i = 1, m also Ri (⟨A | v⟩) ̸= 0 and due to the definition of a reduct for every j = 1, n we have i V Pj (⟨Cj | v⟩) = 1. Thus, j=1,m Pj (⟨Cj | [v]⟩) = 1 where [v] ∈ VGact and VGact is the active space of G. Thus, moreover, JGK(⟨C0 | [v]⟩) = JGK(⟨C0 | v⟩) = 1. I.e., O O O Ri (⟨Ai | v⟩) ⊗ JGK(⟨C0 | v⟩) = Ri (⟨Ai | v⟩) ⊗ 1 = Ri (⟨Ai | v⟩) i=1,m

i=1,m

i=1,m

as required. Lemma 4.8. If Q has a guard G(C0 ), then JQKD can be evaluated in time O(|GD |).

Proof. In the definition of JQKD given by Eq. (5), we can restrict the summation to vectors v ∈ V act = Qd /(span(Q))⊥ that satisfy G(⟨C0 | v⟩) ̸= 0. Further, notice that for any tuple of vectors I the map ⟨I | −⟩ : Qd /I ⊥ → Q|I| is injective. Thus, as span(C0 ) = span(Q), we have Qd /C0⊥ = V act and ⟨C0 | −⟩ : V act → Q|C0 | is injective. Computing the (partial) inverse map φ : Q|C0 | → V act is simple by applying basic linear algebra and expressable by a matrix. Thus, computing the v ∈ V act such that ⟨C0 | v⟩ = ̸ 0 is a matter of going over y ∈ supp(G) and applying φ(y). I.e., we can restrict the ≤ |G| many elements φ(supp(G)) ⊆ V act .

C

Full Proofs for Section 5

Here, we give the missing/complete proofs for Section 5 N N Lemma 5.3 (Factorization Lemma). Let Q(A0 ) ← i=1,m Ri (Ai ) ⊗ j=1,n Sj (Bj ) be a CSPQ and consider the following two queries: O O Q1 (A0 ) ← Ri (Ai ) ⊗ Q2 (B0 ), Q2 (B0 ) ← Sj (Bj ) i=1,m

where B0 is a tuple of vectors s.t. span B0 =

j=1,n



span

S

i=0,m Ai



  S ∩ span j=1,n Bj . Then, on any

database D, we have JQKD = JQ1 KD , where the atom Q2 (B0 ) in Q1 is instantiated as JQ2 KD . S Proof. First we show that Q1 is well-defined. That is, that S A0 ⊆ span S i=1,m Ai ∪ B0 . To that end, S take c ∈ A0 whichSwe write as c = a + b ∈ span i=1,m AS i ∪ j=1,n Bj ⊇ B0 where a ∈ span i=1,m Ai , b ∈ span j=1,n Bj . Thus, also, b = c − a ∈ span i=0,m Ai and consequently, b ∈ S span B0 . STherefore, c = aS+ b ∈ span i Ai ∪ B0 . For convenience we write S V1 := span(Q1 ) = span B0 ∪ i=1,m Ai = span i=0,m Ai , d1 := dim V1 , and V2 := span(Q2 ) = span j=1,n Bj , d2 = dim V2 , and V0 = span B0 , d0 = dim V0 . Notice that V0 = V1 ∩ V2 . Then, due to the Substitution Lemma 3.8, we can assume V1 = span{e1 , . . . , ed1 },

V0 = span{ed−d2 +1 , . . . , ed−d2 +d0 }, 22

V2 = span{ed−d2 +1 , . . . , ed }.

Note that d + d0 ≥ d1 + d2 . To achieve this form, we can start with a basis B0 of V0 = V1 ∩ V2 using the vectors B0 , then extend it with elements B1 from V1 to a basis B0 ∪ B1 of V1 , and then extend B0 again with elements B2 from V2 to a basis B0 ∪ B2 of V2 . I.e., in the end, span B0 = V0 = V1 ∩ V2 ,

span B0 ∪ B1 = V1 ,

B0 ∪ B2 = V2 .

O

O

Now, for x ∈ Q|A0 | we have JQK(x) =

M

Ri (⟨Ai | u⟩) ⊗

[u]∈Qd /{0} : ⟨A0 |u⟩=x i=1,m

Sj (⟨Bj | u⟩).

j=1,n

We can uniquely break up u into u = u1 + u0 + u2 where u1 ∈ span{e1 , . . . , ed−d2 },

u0 ∈ V0 ,

u2 ∈ span{ed−d2 +d0 +1 , . . . , ed }.

Thus, u1 + u0 ∈ V1 and u0 + u2 ∈ V2 . Note that ⟨Bj | u1 ⟩ = 0 and ⟨Ai | u2 ⟩ = 0 for any j = 1, n, i = 1, m, as well as ⟨A0 | u2 ⟩ = 0 and ⟨B0 | u1 ⟩ = 0 = ⟨B0 | u2 ⟩. Therefore, further, M O O JQK(x) = Ri (⟨Ai | u1 + u0 ⟩) ⊗ Sj (⟨Bj | u0 + u2 ⟩) u=u1 +u1 +u2 ∈Qd : ⟨A0 |u1 +u0 ⟩=x i=1,m

=

M

O

u1 +u0 : ⟨A0 |u1 +u0 ⟩=x

i

j=1,n

Ri (⟨Ai | u1 + u0 ⟩) ⊗

MO u2

Sj (⟨Bj | u0 + u2 ⟩).

j

Now let us consider a y ∈ Q|B0 | such that y = ⟨B0 | u0 ⟩ and compute O M JQ2 K(y) = Sj (⟨Bj | v⟩). v∈Qd /V2⊥ : ⟨B0 |v⟩=y

j

Note that we can equivalently write v ∈ Qd /V2⊥ as v = [v0 + v2 ]V2⊥ for some unique vectors v0 ∈ V0 , v2 ∈ span{ed−d2 +d0 +1 , . . . , ed }. Further, note that ⟨B0 | v0 + v2 ⟩ = ⟨B0 | v0 ⟩ = y and, thus, v0 = u0 . Hence, the only freedom is in varying v2 and MO JQ2 K(y) = Sj (⟨Bj | v0 + v2 ⟩). v2

Plugged into the previous equation M JQK(x) =

O

u1 +u0 : ⟨A0 |u1 +u0 ⟩=x

Further, as ⟨B0 | u1 ⟩ = 0 we get M JQK(x) =

u1 +u0 : ⟨A0 |u1 +u0 ⟩=x

j

O i

i

Ri (⟨Ai | u1 + u0 ⟩) ⊗ JQ2 K(⟨B0 | u0 ⟩).

Ri (⟨Ai | u1 + u0 ⟩) ⊗ JQ2 K(⟨B0 | u1 + u0 ⟩).

Then, as V1⊥ = span{ed−d2 +d0 +1 , . . . , ed }, we can equivalently sum over [u1 + u0 ] ∈ Qd /V1⊥ . I.e., M O JQK(x) = Ri (⟨Ai | [u1 + u0 ]⟩) ⊗ JQ2 K(⟨B0 | [u1 + u0 ]⟩) [u1 +u0 ]∈Qd /V1⊥ : ⟨A0 |[u1 +u0 ]⟩=x

i

= JQ1 K(x). This completes the proof. Lemma 5.5. Let (T, χ) be a CTD of Q. Then, there exists a minimal CTD (T, χ′ ) of Q where span χ′ (v) ⊆ span χ(v) for all v ∈ V (T ).

23

Proof. To prove this, we simply start from (T, χ) and then, pick χ′ (v) such that it is a basis of vector space on the right hand side of Equation (9). I.e., X span χ′ (v) = span ζ(v) + (span ζ(Tu ) ∩ span ζ(Tv )) u is adjacent to v

Then, we claim that (T, χ′ ) is a minimal CTD as required. To that end, first notice that for any v ∈ V (T ) and subtree T ′ of T span ζ(v) ⊆ span χ(v), span ζ(T ′ ) ⊆ span χ(T ′ ). Thus, for any edge uv in T we have span ζ(Tu ) ∩ span ζ(Tv ) ⊆ span χ(Tu ) ∩ span χ(Tv ) = span χ(u) ∩ span χ(v) ⊆ span χ(v). Putting these fact together, ensures that span χ′ (v) ⊆ span χ(v) for any v ∈ V (T ). Thus, it only remains to show that (T, χ′ ) is a minimal CTD of Q, i.e., properties (1)–(3) are satisfied. Properties (1), and (3) are satisfied by construction. For (1), notice that span ζ(v) ⊆ span χ′ (v). Hence, we are only left with property (2), the connectedness condition. To that end, let uv be an edge in T . We claim span χ′ (Tu ) = span ζ(Tu ),

span χ′ (Tv ) = span ζ(Tv ).

We only need to show “⊆” as “⊇” from the point-wise inclusion span ζ(v) ⊆ span χ′ (v). To the and, let T ′ = Tv (the same works for T ′ = Tu ). Then, to show that span χ′ (w) is contained in span ζ(T ′ ) for every w ∈ V (T ′ ), it suffices to show that all subspaces in the sum in Equation (9) also lie in span ζ(T ′ ). Clearly, span ζ(w) ⊆ span ζ(T ′ ). Then, for any edge e incident to w, one of the subtrees of T − e must be a subtree of T ′ as well. For this subtree T ′′ , span ζ(T ′′ ) ⊆ span ζ(T ′ ) as V (T ′′ ) ⊆ V (T ′ ). Consequently, span χ′ (w) ⊆ span ζ(T ′ ). As w ∈ V (T ′ ) was arbitrary, span χ′ (T ′ ) ⊆ span ζ(T ′ ). Now, by the construction of χ′ (u) and χ′ (v), we have span χ′ (Tu ) ∩ span χ′ (Tv ) = span ζ(Tu ) ∩ span ζ(Tv ) ⊆ span χ′ (u) ∩ span χ′ (v). Of course, the reverse inclusion holds trivially. Hence, we have shown property (2) of a CTD. Everything put together, we can assert that (T, χ′ ) is a minimal CTD of Q of the required form. Actually, in the proof we have even seen the following: Lemma C.1. Let (T, χ) be a minimal CTD of Q. Then, for any uv ∈ E, we have span χ(Tu ) = span ζ(Tu ) and span χ(Tv ) = span ζ(Tv ). Proof. Recall that in the proof of Lemma 5.5 we have shown this for χ′ . However, because here (T, χ) is already minimal, span χ′ (w) = span χ(w) for any w ∈ V (T ). N Theorem 5.6 (Query Factorization). Let Q(A0 ) ← i Ri (Ai ) be a CSPQ and (T, χ) be a minimal CTD with root r. For each node v ∈ V (T ) we define the following subquery: O O Qv (B v ) ← Ri (Ai ) ⊗ Qc (B c ). (10) v covers Ri (Ai )

c∈child(v)

where B r := A0 , and for v ̸= r, B v is any basis of span χ(v) ∩ span χ(parent(v)). Then, JQK = JQr K. Proof. We prove this by induction on the size of the CTD (T, χ). When T only consists of a single node r, then the statement trivially holds as B v = A0 and every body atom of Q is covered by r. Equally, Qv simply is of the same form as Q: O Qv (A0 ) ← Ri (Ai ) i

Now let the root r of T at least contain some child c. Further, let Tc , Tr be the two connected components of T − rc where c is the root of Tc and r is the root of Tr . Then, let Ic := {i = 1, m | Ri (Ai ) is covered by some v ∈ V (Tc )}, Ir := {i = 1, m | Ri (Ai ) is covered by some v ∈ V (Tr )}. 24

Then, let us apply the Factorization Lemma 5.3 to O O Ri (Ai ) Ri (Ai ) ⊗ Q(A0 ) ← i∈Ic

i∈Ir

where we use B0 = B c . We show that B0 = B c valid set of vectors. To that end, notice that due to Lemma C.1 [ [ (span A0 ∪ Ai ) ∩ (span Ai ) = span χ(Tr ) ∩ span χ(Tc ) i∈Ir

i∈Ic

= span χ(r) ∩ span χ(c) = span B c . Thus, we can apply the Factorization Lemma 5.3. That is, for O O Q1 (A0 ) ← Ri (Ai ) ⊗ Q2 (B c ), Q2 (B c ) ← Ri (Ai ) i∈Ir

i∈Ic

we have JQK = JQ1 K. Then, we claim that (Tc , χ) is a minimal CTD of Q2 while (Tr , χ) is a minimal CTD of Q1 where we use r ∈ V (Tr ) to cover S Q2 (B c ). First, notice S that due to Lemma C.1 for v ∈ V (Tr ) we have χ(v) ⊆ χ(Tr ) = ζ(Tr ) S = span A0 ∪ i∈Ir Ai = span B c ∪ i∈Ir Ai , and for v ∈ V (Tc ) we have χ(v) ⊆ χ(Tc ) = ζ(Tc ) = span i∈Ic Ai . Thus, (Tc , χ), (Tr , χ) are at least candidates for being CTDs. Then, property (1) is clearly satisfied. Further, for property (2), simply notice that for any edge uv ∈ Tc or uv ∈ Tr , the subtree Tu , Tv to consider are smaller than they would be in T . Hence, the “⊆” is easier to satisfy in Tc and Tr than in T . I.e., the “⊆” relation holds in Tc and Tr as it does in T . The “⊇” relation holds trivially. Consequently, (Tc , χ) and (Tr , χ) are in fact CTDs. Now, let us consider property (4). To that end, let ζc , ζr be the function ζ of Definition 5.4 for (Tc , χ) and (Tr , χ), respectively. Now, let vu ∈ T be an edge vu = ̸ rc where v is the parent of u. Let us assume that vu is in Tr and let us consider the two subtrees Tv , Tu of T − vu and the two subtrees Trv , Tru of Tr − vu. Then, we claim span ζ(Tv ) ∩ span ζ(Tu ) = span ζr (Trv ) ∩ span ζr (Tru ) First,Snotice that Tu = Tru and ζr (Tru ) = ζ(Tu ). For span ζr (Trv ), let us construct a basis of span i=1,m Ai = span ζ(Tr ) + span ζ(Tc ) in the following way (Due to Lemma C.1, the intersection is span B c ): We start with a basis Brc ⊆ B c that spans span B c , and extend it with elements Bc ⊆ span ζ(Tc ) to a basis Brc ∪ Bc of span ζ(Tc ). At the same time, we extend Brc with Brv ⊆ span ζr (Trv ) to a basis Brc ∪ Brv of span ζr (Trv ) and, further, with Br ⊆ span ζr (Tr ) to a basis Brc ∪ Brv ∪ Br of span ζr (Tr ). Then, span ζ(Tv ) ⊆ span(Brc ∪ Bc ∪ Brv ) while span ζ(Tu ) ⊆ span(Brc ∪ Brv ∪ Br ). Thus, span ζ(Tv ) ∩ span ζ(Tu ) ⊆ span(Brc ∪ Brv ). At the same time span ζ(Tv ) ∩ span(Brc ∪ Brv ) = span ζr (Trv ). Thus, span ζ(Tv ) ∩ span ζ(Tu ) = span ζ(Tv ) ∩ span(Brc ∪ Brv ) ∩ span ζ(Tu ) = span ζr (Trv ) ∩ span ζr (Tru ) as claimed. We never used the fact that r is the parent of c, hence, the analog statement holds for vu in Tc (simply switch the roles of r and c). Further, ζr (w) = ζ(w) for w ∈ V (Tr ), w ̸= r as well as ζc (w) = ζ(w) for w ∈ V (Tc ), w ̸= c. Thus, property (3) is verified for all but w = r or w = c as in Equation (9) we can simply replace all ζ with ζr (resp. ζc ) as well as Tu , Tv with Tru , Trv (resp. Tcu , Tcv ). For w = r or w = c we simply shift the term span B c = span ζ(Tr ) ∩ span ζ(Tc ) from the big sum to the left. That is, notice span ζ(w) + span B c = span ζr (w) (resp. span ζ(w) + span B c = span ζc (w)). All other terms are taken care of as before. Thus, we conclude that (Tc , χ), (Tr , χ) are in fact minimal CTDs. Thus, by induction, we assert that JQ2 K = JQc K. Further, let O Q′1 (A0 ) ← Ri (Ai ) ⊗ Qc (B c ). i∈Ir

25

Then, clearly, JQK = JQ1 K = JQ′1 K. Now we can apply the induction also to Q′1 and get Q′′1 of the form O O ′ ′ Q′′1 (A0 ) ← Ri (Ai ) ⊗ Qc (B c ) ⊗ Qc (B c ) c′ ∈child(v)

r covers Ri (Ai )

where c′ are the children of r in Tr , i.e., this excludes c. However, note that Q′′1 is syntactically the same as Qr . Thus, JQK = JQ′′1 K = JQr K.

D

Full Proofs for Section 6

In this section, we give the full proofs of Theorems 6.3, 6.7, and 6.10 but also prove informal statements that ctw(Q) = atw(Q) = tw(Q) for traditional SPQs Q, and that ctw(Q) = ctw(Qφ ), atw(Q) = atw(Qφ ), fcw(Q) = fcw(Qφ ) for CSPQs Q and substitutions φ. Theorem 6.3. Let Q be a CSPQ and let D be a database with integer domain values, i.e., adom(D) ⊆ Z. Then JQKD can be computed in time O(n(D)ctw(Q)+1 ). Proof Sketch. Due to Lemma 5.5, we can assume, w.l.o.g, that there exists a minimal CTD (T, χ) such that ctw(T, χ) = ctw(Q). We evaluate Q bottom-up, using the Query Factorization Theorem 5.6. We pick the B v bottom-up in the following way: Fix a v ∈ V (T ) where v is not the root of T and all the B c for children c of v have already been picked. Then, let D v = {d1 , . . . , dlv } be basis of span χ(v) consisting of vectors that appear in the body of Qv . Further, let bv1 , . . . , bvkv be a basis of span χ(v) ∩ span χ(parent(v)) Thus, we can express bv1 , . . . , bvkv as a linear combinations bv1 =

X

λ1,j dj ,

...,

j

bvkv =

X

λkv ,j dj .

j

Now, we can multiply all of the bv1 , . . . , bvkv with a big enough integer α ∈ Z such that all the factors αλi,j are also integers. Therefore, B v := (αbv1 , . . . , αbvkv ) is then a basis of span χ(v) ∩ span χ(parent(v)) where all basis elements are expressable as an integral combination of the vectors in D v . Hence, with the B v picked as above and when the supports of the relations in the body of Qv (including the messages) only use integers which are at most of size n, then, due to Lemma 3.8, also JQv K only contains integers and their size is bound by αlv · n. Therefore, for any v ∈ V (T ) (now v is allowed to be the root), the active domain of the relations in the body of Qv are integers and bounded by O(n(D)) as we can hide the factors αlv in the big O notation. Thus, due to Theorem 4.1, we can evaluate every Qv in time O(n(D)lv ) where maxv lv = ctw(Q) + 1. Thus, this algorithm runs in time O(n(D)ctw(Q)+1 ). Theorem 6.7. Let Q be a CSPQ. Then, JQK can be computed in time O(|adom(D)|atw(Q)+1 ). N Proof. Fix a width optimal minimal CTD (T, χ) of Q(A0 ) ← i=1,m Ri (Ai ). We combine the results of Sec. 4 and Sec. 5 to obtain this result. The idea is to first add reducts to Q such that after applying the Factorization Theorem 5.6 that all subqueries Qv are guarded. Fix a node v ∈ V (T ), denote C0v := χ(v), and let C = (b1 , . . . , bk ) be a a vector cover of C0v of size k := α(C0v ). For each bj , let Ri (AiV ) be an atom such that bj ∈ Ai . We compute the reducts Pj (bj ) of Ri (Ai ), and denote with Gv (C0v ) ← j=1,k Pj (bj ) a reduct of Q. By Theorem 4.1 JGv KD can be computed in time O(|adom(D)|α(χ(v)) ). By Lemma 4.6, we can add an atom Gv (C0v ) to Q without affecting the semantics. We repeat this process for all tree nodes v ∈ V (T ). The modified query is O O Qmod (A0 ) ← Ri (Ai ) ⊗ Gv (C0v ) i=1,m

v∈V (T )

Then, (T, χ) is still valid minimal CTD of the modified query where we cover the new atoms Gv (C0v ) each with the node v. We compute the query bottom-up on the tree T , using the Factorization Theorem 5.6. That is, the queries are of the form O O Qvmod (B v ) ← Ri (Ai ) ⊗ Qcmod (B c ) ⊗ Gv (C0v ) v covers Ri (Ai )

c∈child(v)

26

where span(Qvmod ) = span χ(v) = span(C0v ) by construction. Thus, each query Qvmod can be computed in time O(|JGv K|) by Lemma 4.8, because it is guarded by Gv . Thus, the runtime is dominated by the time needed to compute reducts, which is O(|adom(D)|atw(Q)+1 ). This completes the proof as for the root r of T we have JQrmod K = JQK.

Theorem 6.10. Let Q be a CSPQ. Then, JQK can be computed in time O(|D|fcw(Q) ).

Proof. We N proceed as in the proof of Theorem 6.7. Fix a width optimal minimal CTD (T, χ) of Q(A0 ) ← i=1,m Ri (Ai ). The idea is again to first add reducts to Q such that after applying the Factorization Theorem 5.6 that all subqueries Qv are guarded. Fix aVnode v ∈ V (T ) and denote C0v := χ(v). By Lemma 4.12 we can construct a reduct Gv (C0v ) ← i=1,m Pi (Ci ) of Q such that ∗ ρ∗Gv (C0v ) = ρ∗ (C0v ). We can evaluate Gv in time O(|D|ρ (χ(v)) ) using Theorem 4.1. By Lemma 4.6, we v v can add an atom G (C0 ) to Q without affecting the semantics. We repeat this process for all tree nodes v ∈ V (T ). The modified query is again O O Qmod (A0 ) ← Ri (Ai ) ⊗ Gv (C0v ) i=1,m

v∈V (T )

Then, (T, χ) is still valid minimal CTD of the modified query where we cover the new atoms Gv (C0v ) each with the node v. We compute the query bottom-up on the tree T , using the Factorization Theorem 5.6. That is, the queries are of the form O O Qvmod (B v ) ← Ri (Ai ) ⊗ Qcmod (B c ) ⊗ Gv (C0v ) v covers Ri (Ai )

c∈child(v)

where span(Qvmod ) = span χ(v) = span(C0v ) by construction. Thus, each query Qvmod can be computed in v v

time O(|JG K|) by Lemma 4.8, because it is guarded by G . Thus, the runtime is dominated by the time needed to compute reducts, which is O(|adom(D)|atw(Q)+1 ). This completes the proof as for the root r of T we have JQrmod K = JQK. N TheoremVD.1. Let Q(E0 ) ← i=1,m Ri (Ei ) be a convolution-free CSPQ with E0 ⊆ {e1 , . . . , ed } and C(X0 ) ← i=1,m Ri (Xi ) the CQ obtained by replacing the ej with simply variables Xj . Then, ctw(Q) = atw(Q) = tw(C),

and

fcw(Q) = fhw(C)

where tw(C) is the traditional treewidth of C (with a single bag covering all output variables) and fhw(C) is the traditional fractional treewidth of C (with a single bag covering all output variables). Proof. First notice that traditional tree decompositions can easily be interpreted as CTDs and the width of each bag seen as a CTD is the same as the width of the bag when seen a traditional tree decomposition (for atw note that a traditional bag is a vector cover of itself, and for fcw recall Lemma 4.11). Thus, it suffices to prove that minimal CTD (T, χ) are such that χ(v) = {ej1 , . . . , ejnv }. To that end, let (T, χ) be an arbitrary minimal CTD of Q. Then, for any v ∈ V (T ) we simply have [ ζ(v) = Ei = {ei1 , , . . . , eimv } Ri (Ei ) is covered by v

Thus, by looking at the RHS of Equation 9 we notice that span χ(v) = span{ej1 , . . . , ejnv } as all vector spaces in the sum are of the same form. Therefore, w.l.o.g, we can pick χ(v) = span{ej1 , . . . , ejnv } and (T, χ) can be seen as a traditional tree decomposition. This completes the proof. Theorem D.2. Let Q be a CSPQ and φ a substitution. Then, ctw(Q) = ctw(Qφ ),

atw(Q) = atw(Qφ ),

fcw(Q) = fcw(Qφ ).

Proof. We simply have to observe that substitutions do not affect the width notions. To that end, let (T, χ) be a CTD of the CSPQ Q. Then, let us define χφ : v 7→ φ(χ(v)). Notice that φ is a isomorphism from the span of Q to the image of φ. Thus, properties (1)–(3) of minimal tree decompositions are satisfied by (T, χ) and Q if and only if there are satisfied by (T, χφ ) and Qφ . Furthermore, 1) dim span χ(v) = dim span χφ (v) so ctw(Q) = ctw(Qφ ); 2) C is a vector cover of C0 with respect to Q if and only if φ(C) is a vector cover of φ(C0 ) with respect to Qφ so αQ (χ(v)) = αQφ (χφ (v)) and atw(Q) = atw(Qφ ); 3) we have already noted in Lemma 4.10 that ρ∗Q (χ(v)) = ρ∗Qφ (χφ (v)) so fcw(Q) = fcw(Qφ ). 27

E

Proofs for Section 7

For a field F with characteristic p > 0 and some field elements A ⊆ F, we write Fp (A) for the smallest subfield of F containing A. Before proving Theorem 7.1, we show that we can always ask for a tree decomposition such that the bags are made up of field elements from Fp (adom(Q)). Thus, essentially, we never have to go beyond Fp (adom(D, Q)) where |Fp (adom(D, Q))| = n(D, Q). Note that Fp (adom(D, Q)) is infinite when adom(D, Q) contains an non-algebraic element. In that case, we consider Theorem 7.1 to be trivially true. Lemma E.1. Let (T, χ) be a tree decomposition of the CSPQ Q over a field of characteristic p > 0. Then, there exists a minimal tree decomposition (T, χ′ ) of Q where χ′ (v) ⊆ Fp (adom(Q))d for all v ∈ V (T ) and ctw(T, χ′ ) ≤ ctw(T, χ). Proof. Due to Lemma 5.5, we know that there always exists a minimal tree decomposition (T, χ′ ). Note that span χ′ (v) ⊆ span χ(v) for each v ∈ V (T ) implies ctw(T, χ′ ) ≤ ctw(T, χ). Clearly, for every v ∈ V (T ) it does not matter which set of vectors χ′ (v) are picked, as long as they satisfy Equation (9) in Definition 5.4. Then, notice that each span ζ(v) is vector space with a basis in Fp (adom(Q))d . Thus, as this property is closed under taking intersections and sums, span χ(v) is a vector space with a basis in Fp (adom(Q))d . Thus, w.l.o.g., χ′ (v) ⊆ Fp (adom(Q))d for every v ∈ V (T ). Now, we can prove Theorem 7.1. Theorem 7.1. For fields with positive characteristic, Q can be evaluated in time O(n(D, Q)ctw(Q)+1 ). Proof. Due to Lemma E.1, we can assume w.l.o.g. that there is a minimal tree decomposition T, χ such that ctw(T, χ) = ctw(Q) and χ(v) ⊆ Fp (adom(Q))d for all v ∈ V (T ). Then, let us evaluate Q according to Theorem 5.6 via the subqueries Qv , v ∈ V (T ). As χ(v) ⊆ Fp (adom(Q))d , we can also pick B v ⊆ Fp (adom(Q))d . We show by induction that adom(JQv K) ⊆ Fp (adom(D, Q)). To that end, we perform a variable substitution according to Lemma 3.8 such that φ−1 (e1 ), . . . , φ−1 (ek ) appear in the body of Qv . Then, JQvφ K(⟨φ(B c ) | u⟩) ̸= 0 only if Ri (⟨φ(Ai ) | u⟩) ̸= 0 and JQc K(⟨φ(B c ) | u⟩) ̸= 0. Thus, as φ−1 (e1 ), . . . , φ−1 (ek ) appear somewhere in the body, we have u ∈ Fp (adom(D, Q))d . Notice that all vectors b ∈ B v are a Fp (adom(Q))-linear combination of φ−1 (e1 ), . . . , φ−1 (ek ). Then, also ⟨φ(b) | u⟩ ∈ Fp (adom(D, Q)). Consequently, adom(JQv K) ⊆ Fp (adom(D, Q)). Now we simply have to apply Theorem 4.1 to evaluate each of the subqueries Qv in time O(|Fp (adom(D, Q))|ctw(T,χ)+1 ) as required.

F

CSPQs and SPQs with Linear Equality Constraints

In this section we outline how CSPQs semantically capture SPQ with added linear equation constraints (SPQLEs). To that end, we give two ways CSPQs capture SPQLEs. The first version is very direct but adds relations while in the second version the relations used by the SPQLEs are exactly the same as the one used by the CSPQs. We begin by formally defining SPQLEs. Definition F.1. Let R1 (X1 ), . . . , Rm (Xm ) be atoms using the variables X = (X1 , . . . , Xd )T and let B ∈ Qn×d be a matrix. A sum-product query with linear equation constraints (SPQLEs) is an expression of the form: L(X0 ) ← R1 (X1 ) ⊗ · · · ⊗ Rm (Xm ), s.t. BX = 0 S We require the safety condition X0 ⊆ {X1 , . . . , Xd } = i=1,m X0 The answer of L over an S-database instance D is the S-relation9 : M O ∀x ∈ Q|X0 | : JLK(x) := Ri (v(Xi )) (13) v : X→Q, s.t. v(X0 )=x and Bv(X)=0 i=1,m

9 with BX

(resp. Bv(X)) we mean the matrix multiplication of the matrix B with the transposed vector X = (X1 , . . . , Xd )T (resp. v(X) = (v(X1 ), . . . , v(Xd ))T ).

28

Formally, in a SPQLE we group all  linearequation constraint in a single equation BX = 0. That −b1 −  ..  is B is a matrix with n rows B =  .  and we require that the n linear equation b1 v(X) = −bn − 0, . . . , bn v(X) = 0 hold of the valuations v used in the sum. Thus, to transform L into a CSPQ Q, we can simply add a Boolean relation 1 : Q → S with 1(0) = 1 and 1(λ) = 0 for λ ̸= 0. We show: Theorem F.2. Let 

L(X0 ) ← R1 (X1 ) ⊗ · · · ⊗ Rm (Xm ), s.t. BX = 0,

 −b1 −   where B =  ...  −bn −

be a SPQLE. Then, L is equivalent to the CSPQ Q(E0 ) ← R1 (E1 ) ⊗ · · · ⊗ Rm (Em ) ⊗ 1(b1 ) ⊗ · · · ⊗ 1(bn ) where the Ei are simply tuples of canonical basis vectors obtained from Xi by replacing the occurrences of the variable Xj with the vector ej . We means that over any database D we have JLKD = JQKD Proof. We simply compare the non-0 terms given in the Equation (13) with the non-0 terms given in the Equation (5) (the semantics for a CSPQ). To that end, notice that span(Q) = Qd and we associate the valuations v with the vectors [(v(X1 ), . . . , v(Xd ))] ∈ Qd /{0}. If v produces a non-0 term in Equation (13), then Bv(X) = 0. Thus, in particular, 0 = bj v(X) = ⟨bj | [(v(X1 ), . . . , v(Xd ))]⟩ Thus, for u := [(v(X1 ), . . . , v(Xd ))] O O O Ri (⟨Ei | u⟩) ⊗ 1(⟨bj | u⟩) = Ri (⟨Ei | u⟩) ⊗ 1 i=1,m

j=1,n

i=1,m

=

O

Ri (v(Xi ))

i=1,m

Moreover, v(X0 ) = ⟨E0 | u⟩. Conversely, if u := [(u1 , . . . , ud )] produces a non-0 term in Equation (5), then 1(⟨bj | u⟩) = 1 for every j = 1, n. Thus, Bv(X) = 0 for v : Xi 7→ ui and again O O O Ri (⟨Ei | u⟩) ⊗ 1(⟨bj | u⟩) = Ri (v(Xi )) i=1,m

j=1,n

i=1,m

Moreover, v(X0 ) = ⟨E0 | u⟩. However, we can even capture SPQLEs without needed the additional relation 1 and only use the relations R1 , . . . , Em . We show: Theorem F.3. Let L(X0 ) ← R1 (X1 ) ⊗ · · · ⊗ Rm (Xm ), s.t. BX = 0 be a SPQLE. Then, L is equivalent to the CSPQ Q(A0 ) ← R1 (A1 ) ⊗ · · · ⊗ Rm (Am ) for some tuples of vectors A0 , . . . , Am . We means that over and database D we have JLKD = JQKD Proof. We start by reducing B into reduced row echelon form. That is, recall that after permuting variables, there is a matrix   0 0 B′ = C Id−k such that Bv(X) = 0 if and only if B ′ v(X) = 0. Here Id−k is the d − k × d − k identity matrix and C ∈ Qk×d−k is an arbitrary matrix. Thus, we can partition the variables into X = (X1 , . . . , Xk , Xk+1 , . . . , Xd ) and the solutions to the equation B ′ X = 0 comes from picking valuations of X1 , . . . , Xk arbitrarily 29



 −ck+1 −   .. and determining the valuations for Xk+1 , . . . , Xd from B ′ . Let us write C =  . Then, in . −cd − A0 , . . . , Am let us replace X1 , . . . , Xk with e1 , . . . , ek ∈ Qk and Xk+1 , . . . , Xd with −ck+1 , . . . , −cd ∈ Qk . Notice that span(Q) = Qk due to the safety condition of SPQLEs and that for any valuations v such that Bv(X) = 0 and u := (v(X1 ), . . . , v(Xk )) we have ⟨e1 | u⟩ = v(X1 ), . . . , ⟨ek | u⟩ = v(X1 ),

⟨−ck+1 | u⟩ = v(Xk+1 ), . . . , ⟨−cd | u⟩ = v(Xd ).

We now compare the terms given in the Equation (13) with the terms given in the Equation (5) (the semantics for a CSPQ). We associate the valuations v such that Bv(X) = 0 with the vectors u = [(v(X1 ), . . . , v(Xk ))] ∈ Qk /{0}. Note that this is a bijection as the valuations for Xk+1 , . . . , Xd can be determined from the valuations for X1 , . . . , Xk via v(Xj ) = ⟨−cj | u⟩. Then starting from and u or v, we have O O Ri (⟨Ai | u⟩) = Ri (v(Xi )) i=1,m

i=1,m

Thus, JLK = JQK as also ⟨A0 | u⟩ = v(X0 ).

30

Related documents

• Filters in abstract aggregation with infinite sequences of signals#427317
• Research on a financial fraud identification model by fusing a convolutional neural network.#223094
• SparsePixels: Efficient Convolution for Sparse Data on FPGAs#629883
• SparsePixels: Efficient Convolution for Sparse Data on FPGAs#628021
• Supernetting: an Address Assignment and Aggregation Strategy#136682