  Datalogo is an extension of Datalog, where instead of a program being a
collection of union of conjunctive queries over the standard Boolean semiring,
a program may now be a collection of sum-sum-product queries over an arbitrary
commutative partially ordered pre-semiring. Datalogo is more powerful than
Datalog in that its additional algebraic structure alows for supporting
recursion with aggregation. At the same time, Datalogo retains the syntactic
and semantic simplicity of Datalog: Datalogo has declarative least fixpoint
semantics. The least fixpoint can be found via the na\"ive evaluation algorithm
that repeatedly applies the immediate sequence opeator until no further change
is possible.
  It was shown that, when the underlying semiring is $p$-stable, then the naive
evaluation of any Datalogo program over the semiring converges in a finite
number of steps. However, the upper bounds on the rate of convergence were
exponential in the number of ground IDB atoms.
  This paper establishes polynomial upper bounds on the convergence rate of the
na\"ive algorithm on {\bf linear} Datalogo programs, which is quite common in
practice. In particular, the main result of this paper is that the convergence
rate of linear Datalogo programs under any $p$-stable semiring is $O(pn^3)$.
Furthermore, we show a matching lower bound by constructing a $p$-stable
semiring and a linear Datalogo program that requires $\Omega(pn^3)$ iterations
for the na\"ive iteration algorithm to converge. Next, we study the convergence
rate in terms of the number of elements in the semiring for linear Datalogo
programs. When $L$ is the number of elements, the convergence rate is bounded
by $O(pn \log L)$. This significantly improves the convergence rate for small
$L$. We show a nearly matching lower bound as well.
