PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Convergence of Iterative Methods for Datalogo

Simon Frisk, Sungjin Im, Paraschos Koutris, Benjamin Moseley, Hung Ngo, Kirk Pruhs, Hangdong Zhao

arXiv:2610.04062v1cs.DS

TL;DR

Bounding iterations to convergence matters to Datalog◦ theory and practice, but earlier bounds were not tight. The paper analyzes iterative evaluation over p-stable commutative semirings. It establishes linear convergence bounds and an optimal semiring-complexity upper bound for relaxation algorithms.

  • Problem

    Bounding iterations matters to Datalog◦ theory and practice, including detecting runaway computations; previous bounds were not tight.

    Source: §1.1 · p. 3, §1.3 · p. 3

  • Method

    The paper studies iterative evaluation, repeatedly applying Datalog◦ rules from additive-identity assignments, over p-stable commutative semirings.

    Source: §1.1 · p. 2, §1.3 · p. 3

  • Results

    Every linear Datalog◦ program converges within (2p+1)n iterations, every program within (2p+2)n, and O((p+1)mn) semiring complexity is optimal among relaxation algorithms.

    Source: §1.3 · pp. 3–4

  • Takeaways & Limitations

    Iteration bounds can help detect runaway Datalog◦ computations.

    Source: §1.1 · p. 3

    The convergence bounds concern p-stable semirings; extending convergence to approximate convergence over non-stable semirings remains an area of interest.

    Source: §7 · pp. 18–19

Abstract

from arXiv · show

$\mathsf{Datalog}^\circ$ has been introduced as an extension to Datalog that increases expressiveness, yet retains simple least fixpoint semantics and admits optimization techniques such as semi-na\"ive evaluation and demand transformation. $\mathsf{Datalog}^\circ$ accomplishes this by generalizing the {\em or} and {\em and} operators of Datalog to addition and multiplication over a semiring. Finding a (minimal) fixpoint of a $\mathsf{Datalog}^\circ$ program is equivalent to finding a solution to a system of polynomial equations over the underlying semiring. Solving these systems of polynomial equations is not only a fundamental problem in the theory of $\mathsf{Datalog}^\circ$, but also has many applications in computer science, such as in databases, program analysis, and optimization. This paper resolves a key open problem in the theory of $\mathsf{Datalog}^\circ$: we prove a tight upper bound on the number of steps until convergence of iterative methods for solving these polynomial equation systems over a commutative $p$-stable semiring. In particular, we show that the number of steps until convergence is $O((p+1)n)$ where $n$ is the output size of the $\mathsf{Datalog}^\circ$ program. As the number of steps until convergence is only a proxy for the runtime of $\mathsf{Datalog}^\circ$ evaluation, we also consider the number of semiring operations used and show that, for a natural class of algorithms, $O((p+1)mn)$ is a tight upper bound, where $m$ is the maximum number of semiring operations per iteration.

1 Introduction

The introduction frames Datalog◦ evaluation as iterative solution of semiring polynomial systems, then presents convergence and operation-count bounds that sharpen prior analyses.

1.1 Datalog◦and systems of polynomial equations over a semiring

  • Datalog◦ replaces Datalog’s or/and operators with semiring addition and multiplication, and its iterative evaluation corresponds to solving a grounded polynomial system.Evaluation starts IDB values at 0 and repeatedly applies rules until reaching a fixed point.Source: §1.1 · pp. 1–2
  • Iteration bounds matter for detecting runaway computations, while iteration count alone can misrepresent runtime.Binary-recursive transitive closure converges in exponentially fewer iterations than the linear formulation yet is not faster.Source: §1.1 · p. 3

1.2 Previous Results

  • Earlier general bounds were O((p+2)n), while prior nonlinear bounds also depended on input size and polynomial degree.Earlier linear bounds included O((p+1)n), with special-case bounds for tropical semirings.Source: §1.2 · p. 3

1.3 Our Contributions

  • Linear programs converge within (2p+1)n iterations and general programs within (2p+2)n over p-stable commutative semirings.Together with the lower bound (p+1)n−1, these results are tight within a factor of 2+ε.Source: §1.3 · pp. 3–4
  • O((p+1)mn) semiring operations is a tight upper bound for relaxation algorithms, where m is the maximum operations per iteration.The paper defines semiring complexity as the number of semiring operations used.Source: §1.3 · p. 4

1.4 Paper Organization

  • The paper outlines its background, absorption replacement analysis, linear and nonlinear upper bounds, and lower bounds.Some details, particularly proofs, are moved to appendices due to space limitations.Source: §1.4 · p. 4

2 Preliminaries

The preliminaries connect Datalog◦ evaluation to polynomial systems and use grammars, graphs, and absorption to represent and analyze iterative derivations. These representations provide the concepts needed to define convergence and prove bounds.

2.1 Multisets

  • A multiset records objects with multiplicity; multiset union takes maximum counts, while sum and difference respectively add and subtract counts.The text distinguishes multiset union from multiset sum.Source: §2.1 · p. 4

2.2 Semirings

  • A semiring combines commutative addition with multiplication, and p-stability requires each element’s finite power sum through p to equal the sum through p+1.Stability is motivated by the fact that programs over non-stable semirings may not always converge.Source: §2.2 · pp. 4–5

2.3 Datalog◦and Polynomial Systems

  • A grounding represents a Datalog◦ program as a polynomial map over the semiring, and iteration converges when successive evaluations from zero agree.The number of grounded IDBs is the output size n.Source: §2.3 · p. 5

2.4 Datalog◦and context-free languages

  • Each polynomial component can be represented by a context-free grammar whose derivation-tree yield is the product of its leaves; iterating to depth q sums yields from trees of depth at most q.The grammar’s start symbol corresponds to an output grounded IDB.Source: §2.4 · pp. 5–6

2.5 Linear Datalog◦

  • Linear programs have at most one variable per monomial, allowing their grammars to become labeled transition graphs whose walks correspond to derivation trees.A rule with a variable gives an edge to that variable; a rule without one gives an edge to a sink.Source: §2.5 · p. 6

2.6 Nonlinear Datalog◦

  • For nonlinear analysis, compatible trees preserve the original tree’s structure and yield while labeling edges with semiring values and replacing leaves with a sink.Variable-to-variable edges receive the multiplicative identity; terminal-edge labels retain their semiring values.Source: §2.6 · p. 7

2.7 Proving Convergence with Absorption

  • The convergence proof seeks a set of shallower derivation trees that absorbs a deeper tree, using repeated removable copies and p-stability to establish absorption.Prior work constructs p+1 trees by deleting increasing numbers of repeated subtree occurrences.Source: §2.7 · pp. 7–8

3 Absorption Replacement Process

The absorption replacement process uses properties of p-stable commutative semirings to replace deep derivation trees with shallower ones. Squeeze, parallel absorption, and transitivity support the replacement argument.

Absorption Replacement Process

  • The absorption replacement process repeatedly replaces a deep tree with a collection of trees that collectively absorb it.The process begins with the original tree as the sole member of the maintained set.Source: §3 · pp. 8–9
  • The Squeeze Lemma states that if x = x ⊕ y ⊕ z, then x = x ⊕ y in a p-stable commutative semiring.A related corollary says that the sum of two nonzero elements cannot be zero.Source: §3 · p. 8
  • In a p-stable commutative semiring, a product of degree greater than p is absorbed by a sum of products using at most p multiplicands.This is the Parallel Absorption Lemma.Source: §3 · p. 8
  • Absorption is transitive when an absorbed element is replaced by a collection that absorbs it, allowing successive replacements to preserve absorption.The lemma states this for multisets A and B and their specified combination C.Source: §3 · p. 9

4 Upper Bounds for Linear Datalogo Programs

For linear Datalog◦ programs, the paper bounds convergence using absorption replacements organized by path-loop decompositions. The resulting walks are short enough to establish the stated iteration bound.

4 Upper Bounds for Linear Datalogo Programs

  • Linear Datalog◦ programs with n IDB tuples over a p-stable commutative semiring converge in at most (2p + 1)n iterations.The bound follows because each vertex in the resulting walks is visited at most 2p + 1 times.Source: §4 · p. 9, §4.2 · p. 12

4.1 Preliminary Definitions

  • A loop tree organizes a walk’s loops hierarchically around its path, and each loop’s depth is the same across all possible loop trees for that decomposition.The vertex partition separates path vertices from vertices introduced at successive loop levels.Source: §4.1 · pp. 9–10

4.2 The Linear Absorption Replacement Process

  • The replacement process builds absorbing walks from a deep walk’s path-loop decomposition, using cases that remove or reselect loop subtrees.The replacement walks collectively absorb the original walk, and the process terminates because their loop-count sequences are lexicographically smaller.Source: §4.2 · pp. 10–11
  • Although replacement walks need not initially be shorter, termination yields walks with at most 2p + 1 visits per vertex, hence at most (2p + 1)n edges.The lexicographic decrease in loop-level cardinalities ensures termination.Source: §4.2 · p. 12

5 Upper Bounds for General Datalogo Programs

The absorption replacement process transforms deep derivation trees into shallow trees that absorb them, yielding a convergence bound for general Datalog◦. It combines a path-tree decomposition, canonicalization by wedge pushes, and linear absorption applied along paths.

5.1 Path Tree

  • The path tree L(T) organizes a derivation tree into a hierarchy of paths, allowing the linear absorption procedure to be used as a black box.Each path-tree node corresponds to a node-to-leaf path in the derivation tree.Source: §5.1 · pp. 12–13

5.2 Canonical Tree Transformation

  • Canonicalization repeatedly pushes movable wedges onto higher left-most paths, making the tree more left-deep without changing its yield or semiring value.The procedure terminates because each wedge push strictly increases a lexicographic vector.Source: §5.2 · pp. 13–14

5.3 Application of the Linear Absorption Replacement Process to Derivation Trees

  • Applying LinAbsorb to a path produces absorbing replacement paths, which are lifted to trees by duplicating or deleting the subtrees associated with each affected edge.The resulting trees are compatible.Source: §5.3 · p. 14

5.4 Absorption Replacement Process

  • Each absorption step applies LinAbsorb to a path-node and produces shallower derivation trees representing shorter proofs for the same output tuple.The process chooses path-nodes in order of increasing depth and yields paths of length at most (2p+1)n.Source: §5.4 · p. 14, §5.5 · p. 15

5.5 Analysis of Replacement Process

  • The analysis bounds repeated occurrences of a node along a root-to-leaf path, limiting the final tree depth to (2p+2)n.At termination, the first path-node containing a node has at most 2p+1 appearances, and later path-nodes are structurally constrained.Source: §5.5 · p. 15
  • The resulting absorbing trees have depth at most (2p+2)n, giving naïve evaluation a convergence bound of 2(p+1)n iterations.The absorption replacement process terminates.Source: §5.5 · p. 15

6 Lower Bounds

The paper proves lower bounds for relaxation algorithms that compute semiring fixpoints of linear equations. Edge schedules must cover the walks that contribute to the solution, yielding tight cubic bounds on cliques and Ω(nm(p+1)) bounds for a family of sparse instances over p-stable semirings.

6.1 Relaxation Algorithms

  • Naïve evaluation of the linear system uses 2(2p+1)mn semiring operations, based on its iteration bound and at most 2m operations per iteration.Source: §6.1 · p. 16
  • Relaxation algorithms update one variable along a chosen graph edge, and a correct edge schedule must include every walk contributing to the fixpoint.For each vertex, its value is the sum of yields of walks ending there that are covered by the schedule.Source: §6.1 · p. 16

6.2.1 Intuition of Lower Bound.

  • The lower-bound construction assigns a unique color to each Hamiltonian path, so propagating each color requires traversing that path's edges in order.The color semiring is 0-stable and uses one color per path in the directed clique.Source: §6.2.2 · p. 17, §6.2.1 · p. 17

6.2.2 Lower Bound Analysis

  • On a clique with a 0-stable color semiring, every correct edge schedule has length greater than n^3, matching naïve evaluation's Θ(n^3) operations.The lower bound follows from requiring coverage of all Hamiltonian paths.Source: §6.2.1 · p. 17, §6.2.2 · p. 18

6.3 General Lower Bounds

  • For any constant α≥1, a family of color-semiring instances with Θ(n) nodes and m=Θ(n^(1+1/α)) edges requires schedules of length Ω(mn).Source: §6.3 · p. 18
  • For p-stable semirings, some instances with Θ(n) nodes and m=Θ(n^(1+1/α)) edges require edge schedules of length Ω(nm(p+1)).This holds for constant integer α≥1 when p≤(1/φ)n^(1/α)/2^(α−1), for a constant φ∈(0,1).Source: §6.3 · p. 18

7 Conclusion

The conclusion identifies open problems in the scope of fixpoint evaluation, including tighter iteration bounds and runtime guarantees for Newton-like methods. It also points to approximate convergence for non-stable semirings such as the reals.

7 Conclusion

  • An exact iteration bound of (p+1)n−1 remains an open target, while the stated gap is a factor of (2+ε).Source: §7 · p. 18
  • Bounding the runtime and iteration count of Newton-like methods remains open.Source: §7 · p. 18
  • Approximate convergence for non-stable semirings such as the reals is identified as an area of interest.The conclusion notes their use in numerical optimization, including gradient descent.Source: §7 · pp. 18–19

A Missing Proofs from Preliminaries

The proof uses p-stability of 1 to equate two semiring sums, reducing the multiplicity from p+2 terms to p+1.

A Missing Proofs from Preliminaries

B Absorption Replacement Process

The absorption replacement process relies on algebraic properties of p-stable commutative semirings to replace terms with collections that absorb them. The section establishes the squeeze, parallel absorption, and transitivity facts used by that process.

B Absorption Replacement Process

C Background and Intuition for the Linear Case

The section revisits the cubic bound and purported lower bound from, then explains why p-stability permits shorter replacements even when a walk has no repeated square term. It extends that intuition to general instances using related subtrees in the loop tree.

C Background and Intuition for the Linear Case

  • The earlier O((p+1)n^3) analysis from sought repeated copies of a cycle in a path-loop decomposition to absorb long walks into shorter ones.It decomposed a walk into a simple path and a multiset of loops, finding p+2 copies of a cycle.Source: C Background and Intuition for the… · p. 21
  • The purported Ω((p+1)n^3) lower bound from is incorrect; on its example graphs, convergence takes O((p+1)n) steps for every commutative p-stable semiring.The authors state that this example illustrates the stable-semiring feature underlying their analysis.Source: C Background and Intuition for the… · p. 21
  • On the example graph, two cycles with non-identity labels can jointly be absorbed using 1-stability even when the walk contains no square term.The graph has identity-labeled base edges and distinct non-identity labels on added edges; terms with at least p+1 multipliers can be collectively absorbed by exponentially many smaller terms.Source: C Background and Intuition for the… · p. 22
  • For general instances, subtrees in the loop tree with equal height and a shared vertex play the role of the example's simple cycles.The section identifies this as the insight behind extending the example's absorption argument.Source: C Background and Intuition for the… · p. 22

D Convergence Analysis for the Linear Case

The linear absorption replacement process terminates and leaves only short walks. Its analysis uses a decreasing order on loop decompositions and bounds the size and depth of intermediate loop collections.

D Convergence Analysis for the Linear Case

  • Intermediate loop decompositions contain at most p(p+1)|L| loops, and loop depth never decreases during replacement.Loops are drawn from the original decomposition, and each replacement can multiply the number of copies of a loop by at most p.Source: D Convergence Analysis for the Linear… · pp. 22–23
  • The absorption replacement process terminates because each replacement strictly decreases the loop-decomposition order, so replacement paths cannot revisit a walk.The process graph's paths are simple; their lengths are bounded using the loop-count and loop-tree-depth bounds.Source: D Convergence Analysis for the Linear… · p. 23
  • Every walk in the final collection has length at most (2p+1)n.The bound follows by limiting the number of loops intersecting a vertex at adjacent levels, which bounds its incident edges.Source: D Convergence Analysis for the Linear… · pp. 22–23

E Ancillary Observations for Linear Datalog◦

The paper lifts linear absorption to general derivation trees by representing trees as path trees, transforming them into canonical form, and applying path absorption while carrying attached subtrees along. The process preserves yields and produces shallow trees that collectively absorb the original tree.

E Ancillary Observations for Linear Datalog◦

  • Replacement walks retain the original walk's ending vertex, and final walks have in-degree and out-degree at most 2p+1 per vertex.Consequently, each vertex occurs at most 2p+1 times in a final walk.Source: E Ancillary Observations for Linear… · p. 24

F Upper Bounds for General Datalogo Programs

  • The general-tree proof constructs shallow trees that collectively absorb an arbitrary deep derivation tree, reducing the analysis to the linear case.It uses a path tree, canonical transformation, and linear absorption as a black box.Source: F Upper Bounds for General Datalogo… · p. 24

F.1 Path Tree

  • The path tree represents a derivation tree hierarchically through selected ancestor-to-descendant paths, enabling linear absorption to be applied to paths.Its nodes correspond to node-to-leaf paths; the recursive construction uses left-most root-to-leaf paths.Source: §F.1 · pp. 24–25

F.2 Canonical Tree Transformation

  • Canonical transformation repeatedly pushes movable wedges toward higher left-most paths, terminates, and preserves the tree's yield.The resulting canonical trees also satisfy restrictions on repeated vertices and disjoint path segments in descendant path-nodes.Source: §F.2 · pp. 25–27

F.3 Application of the Linear Absorption Replacement Process to Derivation Trees

  • When linear absorption duplicates or deletes a path edge, its attached child subtrees are duplicated or deleted with it, producing compatible trees.This is how absorbed paths are lifted back into derivation trees.Source: §F.3 · p. 27

F.4 Absorption Replacement Process

  • Each absorption step selects a lowest-depth path-node whose corresponding path exceeds n(2p+1) edges, then applies linear absorption to that path.The replacement paths are used to produce a collection of trees from the original tree.Source: §F.4 · p. 27

F.5 Analysis of Replacement Process

The absorption replacement process terminates and bounds the depth of resulting derivation trees, supporting the convergence bound for general Datalog◦. The surrounding lower-bound material introduces relaxation schedules and combinatorial tools for analyzing them.

F.5 Analysis of Replacement Process

  • The absorption replacement process terminates, and its calls to LinAbsorb proceed in increasing path-node depth without increasing path-tree depth.Each call modifies subtrees hanging off its input path.Source: §F.5 · p. 28
  • The replacement process yields trees of depth at most n(2p+2), establishing a convergence time of 2(p+1)n for naive evaluation.The depth bound follows when the linear absorption procedure generates walks of length at most (2p+1)n.Source: §F.5 · pp. 28, 30
  • The resulting-tree invariant limits each node to at most 2p+2 occurrences on any root-to-leaf path.At most two path-nodes contain the node along the corresponding path-tree path; their occurrence bounds are 2p+1 and 1.Source: §F.5 · pp. 28, 30

G Lower Bounds

  • The lower-bound section extends schedule-length bounds to computation graphs with arbitrary edge count m using recursively defined sparse graphs.It proceeds from helper lemmas to 0-stable sparse graphs and then to general p-stable semirings.Source: G Lower Bounds · p. 30

G.1 Why Relaxation Algorithms?

  • Relaxation algorithms update one variable at a time, while naive and semi-naive evaluation can update multiple variables simultaneously.The paper's relaxation-algorithm definition is limited to linear Datalog◦; general programs would require monomial-at-a-time relaxation.Source: §G.1 · p. 30

G.2 Helpful Preliminary Lemmas

  • Lemma G.1 converts a schedule bound for covering a fraction of sequences into a bound for covering repeated copies of those sequences.For q repetitions and coverage fraction θq, the schedule length is at least q·L(θq/q).Source: §G.2 · pp. 30–31

G.3 Lower Bounds for 0-Stable Sparse Graphs

Recursively defined cliques provide sparse 0-stable instances with long required schedules. The lower-bound construction extends the schedule argument to p-stable semirings by requiring repeated traversals.

G.3 Lower Bounds for 0-Stable Sparse Graphs

  • Recursive cliques are built hierarchically from groups of k child groups, and increasing α makes the graph sparser.The (k,1)-recursive clique is the standard k-clique.Source: §G.3 · pp. 31, 33
  • For every constant integer α≥1, a family of instances with Θ(n) nodes and m = Θ(n^(1+1/α)) edges requires any correct edge schedule over the color semiring to have length Ω(mn).Source: §G.3 · p. 35

G.4 Lower Bound for p-stable Semirings

  • The p-stable lower-bound construction requires every critical configuration to be visited at least p times, adding a factor p to the bound.A tuple-valued semiring tracks each configuration's count up to the cap p.Source: §G.4 · p. 35

G.4.1 Worst-Case Semirings.

  • The capped tropical semiring S_p is p-stable but not (p−1)-stable for p>0.Its values are capped at p, and S_0 is isomorphic to the Boolean semiring.Source: §G.4.1 · p. 35

G.4.2 The Lower Bound Instance.

The lower-bound instance encodes paths with colors in a tuple-valued semiring. Correct schedules must repeat each required Hamiltonian cycle p+1 times, yielding a lower bound that scales with p and the graph size.

G.4.2 The Lower Bound Instance.

  • A correct schedule must cover every required Hamiltonian cycle p+1 times, except for its last edge.The tuple-valued instance assigns coordinates to path colors and vertices; the target vertex values must reach p at the relevant coordinates.Source: §G.4.2 · p. 36
  • For p≤(1/φ)n^(1/α)/2^(α−1), some p-stable instances with Θ(n) nodes and m=Θ(n^(1+1/α)) edges require schedules of length Ω(nm(p+1)).The result holds for each constant integer α≥1.Source: §G.4.2 · p. 37
  • The lower-bound proof combines the required repeated path coverage with the sparse-graph schedule bound.It applies Lemma G.1 with q=p+1 and the recursive-clique path family.Source: §G.4.2 · p. 37
Loading 2610.04062v1…