PaperlayerView exact revision on arXiv

Source-linked AI summary

Convolution Sum-Product Queries

Kyle Deeds, Timo Camillo Merkl, Dan Suciu

arXiv:2609.03672v2cs.DB

TL;DR

Query evaluation for linear-expression workloads matters in applications such as matrix processing and in queries related to 3SUM and MinConv. This paper introduces CSPQs and evaluation algorithms combining linear algebra with worst-case optimal joins and factorized tree decompositions. It reports AGM-style bounds, three width measures for factorized evaluation, and a ρ*(Q)=3/2 example yielding O(|D|^3/2).

  • Problem

    Prior query-evaluation approaches treat linear expressions as separate predicates, while the paper identifies practical linear-index workloads and theoretical queries such as 3SUM and MinConv.

    Source: §1 · p. 1

  • Method

    The paper makes linear expressions first-class in CSPQs and adapts worst-case optimal joins and tree-decomposition factorization using linear-algebra techniques.

    Source: §1 · pp. 2–3, §8 · p. 15

  • Results

    ρ*(Q)=3/2 yields O(|D|^3/2) for an illustrated query; the algorithms also provide AGM-style bounds and factorized evaluation characterized by three width measures.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    CSPQs encompass linear-expression workloads including matrix convolution used in image-processing tasks and queries expressing 3SUM and MinConv conjectures.

    Source: §1 · pp. 1–2

    For exact-weight subgraph problems, the current algorithms do not always match the conditional lower bounds; matching them may require functional dependencies in the framework and width definition.

    Source: §8 · p. 15

Abstract

from arXiv · show

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

CSPQs make linear expressions first-class parts of sum-product queries, targeting workloads such as matrix convolution and queries expressing fine-grained complexity conjectures. The paper develops evaluation algorithms using linear algebra, worst-case optimal joins, and tree-decomposition-style factorization.

1 Introduction

  • Linear expressions occur in matrix convolution workloads and can express queries associated with 3SUM and MinConv conjectures.Matrix convolution is described as a key image-processing operation; 3SUM and MinConv are given as theoretical motivations.Source: §1 · pp. 1–2
  • CSPQs extend sum-product queries with linear expressions directly in query atoms, treating those expressions as first-class citizens.The paper also presents CSPQ tree decompositions that induce query factorizations.Source: §1 · pp. 2–3
  • For dense databases, evaluation takes O(|adom(D)|^k); for sparse databases, an algorithm runs in O(|D|^ρ*(Q)).The dense algorithm is suited to dense tensors; ρ*(Q) generalizes the fractional edge-cover number.Source: §1 · p. 2
  • Quotient spaces ensure CSPQs have well-defined semantics, addressing cases such as an otherwise infinite sum over values of R(X + Y).The introduction also states that CSPQs capture sum-product queries with added linear equality constraints.Source: §1 · pp. 2–3
  • ρ*(Q)=3/2, so the illustrated query over A, B, and C runs in O(|D|^3/2).Here |D| is the number of tuples in A, B, and C.Source: §1 · p. 2
  • The paper adapts worst-case optimal joins and extends tree decompositions; three width parameters characterize factorized evaluation across input-density regimes.The join algorithms achieve AGM-style bounds.Source: §1 · p. 3

2 Background

The background establishes the paper’s semiring database and query notation, then introduces the linear-algebra language used throughout.

2 Background

  • A relation is a function from tuples over Q to a commutative semiring, with finite support represented as tuple-annotation pairs.The support contains tuples mapped to nonzero values; its size is denoted |R_D|.Source: §2 · p. 3
  • An SPQ is built from relation atoms, head variables, and a safety condition; its answer sums semiring values over valuations.A valuation maps query variables to domain values and atoms to relation values.Source: §2 · p. 3
  • The linear-algebra notation uses spans, quotient spaces, dot products, and orthogonal subspaces over a rational vector space.The computational model assumes fixed queries and constant-time semiring and classical arithmetic operations.Source: §2 · p. 4

3 Convolution Sum-Product Queries

CSPQs extend sum-product queries by placing linear combinations directly in relation atoms. The section defines their semantics over an active space and establishes that substitutions preserve query answers.

3 Convolution Sum-Product Queries

  • A convolution atom R(A) applies a relation to linear combinations represented by vectors, making those expressions part of the query atoms.For example, R(X + 2Y, 2X + Z) is represented by vectors (1, 2, 0) and (2, 0, 1).Source: §3 · p. 4
  • CSPQ semantics sum products over the active space, a quotient that avoids counting equivalent valuations repeatedly.Summing over all vectors instead could count the same relation-tuple combination infinitely many times when span(Q) is a strict subspace.Source: §3 · pp. 4, 6
  • Every CSPQ has a well-defined answer with finite support, because only finitely many active-space valuations can contribute nonzero terms.The finite supports of the input relations bound the possible combinations contributing to the sum.Source: §3 · p. 5
  • The example evaluates a query by grouping contributing tuples by 2x + 2z and summing their annotations for each output value.For the group with output 6, the annotations sum to 27.Source: §3 · pp. 5–6
  • Applying an injective linear substitution to a CSPQ preserves its answer, allowing an equivalent representation with simpler expressions.The example rewrites the query using U = X, V = Y − X, and W = Z − Y while retaining the same result.Source: §3 · pp. 6–7

4 Basic Algorithms

The section gives dense and sparse evaluation bounds for CSPQs, adapting worst-case optimal joins through reducts that guard the query. These bounds also yield improvements over general constraint-query techniques in examples.

4 Basic Algorithms

  • O(|adom(D)|^k) time evaluates a CSPQ on dense inputs, where k is the dimension of the query span.The dense algorithm constructs a guard from a basis of the query span and evaluates the resulting independent query.Source: §4 · pp. 7, 9
  • O(|D|^ρ∗(Q)) time evaluates a CSPQ using a sparse-data bound based on its fractional edge-cover measure.The algorithm builds a guard reduct, substitutes it into a convolution-free query, and evaluates it with a worst-case optimal join.Source: §4 · pp. 8–9
  • Reducts act as guards by restricting evaluation to tuples that preserve the original query’s meaning, enabling evaluation through their guarded answers.A guard spans the query’s full span, and the query can then be evaluated in time proportional to the guard’s output size.Source: §4 · p. 8
  • O(|D|^3/2) time evaluates the example query, compared with O(|D|^2) using the cited general-constraint tree-decomposition technique.The paper also describes an example evaluated in O(|D|^3/2) using a fractional edge cover of weight 3/2.Source: §4 · p. 10

5 Tree Decompositions for CSPQ

The section generalizes tree decompositions by using vector spaces in place of variables and uses these decompositions to factorize CSPQs. The factorized execution passes messages across shared subspaces and can improve the example query’s runtime.

5 Tree Decompositions for CSPQ

  • A Convolution Tree Decomposition assigns vector bags to tree nodes, covering atom spans and preserving intersections between the two sides of each edge.Traditional tree decompositions fit this framework by replacing each variable with its canonical basis vector.Source: §5 · pp. 10–11
  • The example query falls from cubic time under the Section 4 algorithms to quadratic time using a CTD and its two subqueries.The two subqueries can each be solved in quadratic time.Source: §5 · p. 11
  • CTDs factorize a CSPQ into subqueries whose outputs pass across shared vector-space interfaces, and recursively factorizing those subqueries yields the full query.The interface is a basis for the intersection of the adjacent bags’ spans.Source: §5 · pp. 11–12
  • Any CTD can be converted to a minimal CTD whose bag spans are contained in the original bag spans.Minimality keeps each bag span only as large as needed to cover relations and maintain connectedness.Source: §5 · p. 12

6 Tree Decomposition Based Query Evaluation and Width Measures

Convolution tree decompositions (CTDs) support factorized CSPQ evaluation, but message relations can grow beyond the active-domain bound for a bag’s arity. The section gives three algorithms with width measures tailored to integer-value magnitude, active-domain size, and database size. [p053]

6 Tree Decomposition Based Query Evaluation and Width Measures

  • Three width measures yield CTD-based runtimes tied respectively to integer-value magnitude, active-domain size, and database size.The three measures address different input-density regimes.Source: §6 · p. 12, §6.1 · p. 12, §6.2 · p. 14
  • Naive bottom-up evaluation can take O(n^k) time because message sizes grow with each bag, reaching as much as n^(i+1).Even when a message is computed in O(n^2), its size can be n^2.Source: §6 · p. 12

6.1 Evaluation Algorithm with respect to the Largest Integer

  • For integer-valued databases, CSPQs can be evaluated in O(n(D)^(ctw(Q)+1)) time, where n(D) is the largest absolute domain value.Rational values can be scaled to integers by clearing denominators and rescaled after evaluation.Source: §6.1 · pp. 12–13

6.2 Evaluation Algorithm with respect to the Active Domain Size

  • Active treewidth gives an O(|adom(D)|^(atw(Q)+1)) runtime by measuring the minimum number of body vectors needed to span each bag.This vector cover yields a guard computed from input relations.Source: §6.2 · pp. 13–14
  • For the generalized (k + 1)-SUM example, the active-domain algorithm runs in O(|adom(D)|^ceil((k+1)/2)), the commonly assumed optimal runtime.The result does not contradict the conjectured lower bound when the runtime instead depends on the largest input value.Source: §6.2 · pp. 13–14
  • For traditional conjunctive queries, convolution treewidth and active treewidth both equal traditional treewidth.The fractional convolution hypertree width also coincides with fractional hypertree width, and the width notions are invariant under variable substitutions.Source: §6.2 · p. 14, §6.3 · p. 15

6.3 Evaluation Algorithm with respect to the Database Size

  • Fractional convolution hypertree width measures each bag by the fractional edge-cover number of its span and gives an O(|D|^fcw(Q)) runtime.For traditional conjunctive queries, this width coincides with fractional hypertree width.Source: §6.3 · pp. 14–15

7 CSPQs over other Fields

Most results established over the rationals also hold over arbitrary fields; for positive-characteristic fields, the paper gives a runtime bound using the smallest subfield containing the database and query elements. [p011]

7 CSPQs over other Fields

  • Apart from Theorem 6.3, the paper’s statements over the rationals hold when Q is replaced by an arbitrary field.The passage says the rational-field assumption was relevant only to Theorem 6.3.Source: §7 · p. 15
  • For fields of positive characteristic, CSPQ evaluation takes O(n(D,Q)^(ctw(Q)+1)) time.Here n(D,Q) is the size of the smallest subfield containing the field elements used in the database and query.Source: §7 · p. 15

8 Conclusion and Future Work

The paper introduces CSPQs and evaluation methods based on worst-case optimal joins and CTDs, with three width measures for different input-size notions. It identifies limits for exact-weight problems and outlines further algorithmic and complexity-theoretic directions. [p014]

8 Conclusion and Future Work

  • The paper extends sum-product queries with linear expressions and adapts worst-case optimal joins and CTDs, defining three width measures for evaluation complexity.The measures relate complexity to different notions of input size.Source: §8 · p. 15
  • The authors propose testing CSPQs on further problems to clarify what the three width measures capture and whether additional structural parameters or specialized algorithms are needed.Source: §8 · p. 15
  • Current algorithms do not always match conditional lower bounds for exact-weight subgraph problems, and matching them may require incorporating functional dependencies.The paper leaves this extension for future work.Source: §8 · pp. 15–16
  • They also identify fast matrix multiplication and fast Fourier transforms as possible non-combinatorial techniques, depending on the semiring and query structure.They call for a systematic characterization of when such techniques apply.Source: §8 · p. 16
  • Conditional lower bounds for CSPQs could follow from conjectures such as (min, +)-convolution and k-SUM, while CSPQ hardness conjectures could sharpen lower bounds for restricted SPQs.Source: §8 · p. 16
  • The paper also points to extending the algebraic foundations beyond fields and linear expressions, potentially toward groups and nonlinear expressions.Such settings would call for new decomposition and width notions.Source: §8 · p. 16

A Full Proofs for Section 3

The appendix supplies proofs for Section 3, including the well-definedness and finite support of CSPQ answers and a substitution argument using quotient spaces. [p025]

A Full Proofs for Section 3

  • The appendix proves that a CSPQ answer is well-defined and has finite support.The proof addresses both finiteness of nonzero terms in the defining sum and finiteness of the answer’s support.Source: A Full Proofs for Section 3 · p. 20
  • Finite support of the input relations ensures that distinct active vectors cannot yield infinitely many nonzero terms in the answer.Source: A Full Proofs for Section 3 · p. 20
  • For a substitution, the proof constructs an induced map between quotient spaces and establishes its injectivity through the corresponding orthogonal-complement condition.Source: A Full Proofs for Section 3 · pp. 20–21

B Full Proofs for Section 4

The proofs establish reductions and evaluation bounds for convolution-free and guarded CSPQs. They also relate CSPQ evaluation to traditional conjunctive-query and sum-product-query algorithms.

B Full Proofs for Section 4

  • Convolution-free CSPQs can be evaluated using traditional conjunctive-query algorithms, and a reduct of a relation can be computed in linear time.The reduct is Boolean and includes the projected tuples corresponding to the original relation's support.Source: B Full Proofs for Section 4 · p. 21
  • Evaluating the associated full sum-product query within the stated active-domain or database-size bound also evaluates Q within that bound.The supplied proof gives O(|adom(D)|^d) and O(|D|^ρ*(C)) for C, then transfers those bounds to Q.Source: B Full Proofs for Section 4 · p. 21
  • Replacing a guard atom with its evaluated answer preserves the query's semantics on every database instance.The proof equates the original query with the query containing the guard's evaluated relation.Source: B Full Proofs for Section 4 · p. 22
  • A guarded CSPQ Q can be evaluated in time O(|G_D|), where G guards the query.The proof restricts evaluation to active vectors corresponding to the support of G.Source: B Full Proofs for Section 4 · p. 22

C Full Proofs for Section 5

The proofs establish structural properties of minimal convolution tree decompositions and use them to factor a CSPQ into node subqueries. The root subquery yields the original query result.

C Full Proofs for Section 5

  • Every CTD can be reduced to a minimal CTD whose bag spans are contained in the original bag spans.The proof constructs each new bag from a basis of the corresponding required vector space.Source: C Full Proofs for Section 5 · pp. 23–24
  • For each edge of a minimal CTD, the span of either side's bags equals the span of its ζ vectors.This characterizes the subspaces used to prove the decomposition's minimality.Source: C Full Proofs for Section 5 · p. 24
  • Defining node subqueries with A0 at the root and shared-span bases elsewhere gives JQK = JQrK.For non-root nodes, Bv is a basis of the intersection between the node and parent bag spans.Source: C Full Proofs for Section 5 · p. 24
  • The factorization proof splits the tree at an edge and applies induction to the resulting subqueries.The proof verifies that the two resulting subtrees remain minimal CTDs before applying induction.Source: C Full Proofs for Section 5 · pp. 24–25

D Full Proofs for Section 6

The proofs establish CSPQ evaluation bounds using three width measures and show that these measures are invariant under substitutions. For traditional SPQs, the CSPQ treewidth measure agrees with traditional treewidth.

D Full Proofs for Section 6

  • For traditional SPQs, ctw, atw, and tw coincide, and traditional tree decompositions provide the corresponding CSPQ decompositions.The proof reduces minimal CTD bags to spans of ordinary variables.Source: D Full Proofs for Section 6 · pp. 26–27
  • O(n(D)^ctw(Q)+1) evaluates a CSPQ when database domain values are integers.The proof chooses integral bases for separator spaces so intermediate active-domain values stay bounded by O(n(D)).Source: D Full Proofs for Section 6 · p. 26
  • O(|adom(D)|^atw(Q)+1) evaluates a CSPQ.The proof adds reduct guards at tree-decomposition nodes and evaluates the resulting guarded subqueries bottom-up.Source: D Full Proofs for Section 6 · p. 26
  • O(|D|^fcw(Q) evaluates a CSPQ.The theorem states the relation-size bound for the fractional cover width.Source: D Full Proofs for Section 6 · p. 27
  • Substitutions preserve ctw, atw, and fcw for CSPQs.The proof uses an isomorphism on the query span to preserve bag dimensions and vector-cover widths.Source: D Full Proofs for Section 6 · p. 27

E Proofs for Section 7

For fields of positive characteristic, the proof bounds evaluation by the size of a subfield generated from the database and query values. It constructs decompositions whose bags lie in that subfield.

E Proofs for Section 7

  • A decomposition can be chosen with bags in Fp(adom(Q))^d without increasing ctw.The proof uses closure of the relevant vector spaces under intersections and sums.Source: E Proofs for Section 7 · p. 28
  • O(n(D, Q)^ctw(Q)+1) evaluates CSPQs over fields with positive characteristic.Here n(D, Q) is the size of the generated subfield when it is finite; the proof treats the infinite-subfield case as trivial.Source: E Proofs for Section 7 · p. 28
  • The proof evaluates decomposition subqueries over the generated subfield Fp(adom(D, Q)).It establishes that each subquery's active domain lies in that subfield before applying the evaluation bound.Source: E Proofs for Section 7 · p. 28

F CSPQs and SPQs with Linear Equality Constraints

The section shows that CSPQs can express sum-product queries with linear equality constraints in two ways: one adds a Boolean relation, while the other uses only the original relations.

F CSPQs and SPQs with Linear Equality Constraints

Loading 2609.03672v2…