We showed in~\Cref{sec:hard} that a runtime of $\bigO{\qruntime{\optquery{\query},\tupset,\bound}}$ cannot be acheived for~\Cref{prob:bag-pdb-poly-expected}. In light of this, we desire to produce an approximation algorithm that runs in time $\bigO{\qruntime{\optquery{\query},\tupset,\bound}}$. We do this by showing the result via circuits,
such that our $1\pm\epsilon$ approximation algorithm for this problem runs in $\bigO{\abs{\circuit}}$ for a very broad class of circuits, (thus solving~\Cref{prob:intro-stmt}); see the discussion after \Cref{lem:val-ub} for more.
\abbrCTIDB lineage polynomials and general \abbrBIDB lineage polynomials in practice. %, where for the latter we note that a $1$-\abbrTIDB is equivalently a \abbrBIDB (blocks are size $1$).
Our experimental results (see~\Cref{app:subsec:experiment}), which use queries from the PDBench benchmark~\cite{pdbench} support the notion that our bounds hold for general \abbrBIDB in practice.
We now introduce definitions related to circuits and polynomials that we will need to state our upper bound results. First, we introduce the expansion $\expansion{\circuit}$ of circuit $\circuit$ which
For a circuit $\circuit$, we define $\expansion{\circuit}$ as a list of tuples $(\monom, \coef)$, where $\monom$ is a set of variables and $\coef\in\domN$.
Later on, we will denote the monomial composed of the variables in $\monom$ as $\encMon$. As an example of $\expansion{\circuit}$, consider $\circuit$ illustrated in \Cref{fig:circuit}. $\expansion{\circuit}$ is then $[(X, 2), (XY, -1), (XY, 4), (Y, -2)]$. This helps us redefine $\rpoly$ (see \Cref{eq:tilde-Q-bi}) in a way that makes our algorithm more transparent.
{\em positive circuit}, denoted $\abs{\circuit}$, is obtained from $\circuit$ as follows. For each leaf node $\ell$ of $\circuit$ where $\ell.\type$ is $\tnum$, update $\ell.\vari{value}$ to $|\ell.\vari{value}|$.
\begin{Definition}[$\degree(\cdot)$]\label{def:degree}\footnote{Note that the degree of $\polyf(\abs{\circuit})$ is always upper bounded by $\degree(\circuit)$ and the latter can be strictly larger (e.g. consider the case when $\circuit$ multiplies two copies of the constant $1$-- here we have $\deg(\circuit)=1$ but degree of $\polyf(\abs{\circuit})$ is $0$).}
\begin{Definition}[$\multc{\cdot}{\cdot}$]\footnote{We note that when doing arithmetic operations on the RAM model for input of size $N$, we have that $\multc{O(\log{N})}{O(\log{N})}=O(1)$.}
%More generally we have $\multc{N}{O(\log{N})}=O(N\log{N}\log\log{N})$.}
In a RAM model of word size of $W$-bits, $\multc{M}{W}$ denotes the complexity of multiplying two integers represented with $M$-bits. (For input of size $N$, we make the standard assumption $W=O(\log{N})$.)
Let $\isInd{\cdot}$ be a boolean function returning true if monomial $\encMon$ is composed of independent variables and false otherwise; further, let $\indicator{\theta}$ also be a boolean function returning true if $\theta$ evaluates to true.
Given the above, the algorithm is a sampling based algorithm for the above sum: we sample (via \sampmon) $(\monom,\coef)\in\expansion{\circuit}$ with probability proportional
to $\abs{\coef}$ and compute $\vari{Y}=\indicator{\isInd{\encMon}}
and computing the average of $\vari{Y}$ gives us our final estimate.
We illustrate \sampmon (\Cref{alg:sample}), using the circuit $\circuit$ in \Cref{fig:circuit}. As a pre-processing step, \onepass (\Cref{alg:one-pass-iter}) recursively (for each sub-circuit) computes $\abs{\circuit}\inparen{1,\ldots, 1}$ in the obvious manner.
The \textcolor{gray}{gray} values in~\Cref{fig:circuit} represent the value $\abs{\circuit'}\inparen{1,\ldots, 1}$ for each sub-circuit $\circuit'$ rooted at the corresponding node. E.g. in the bottom right $\circmult$ (\textcolor{blue}{blue}) gate, the value is $1\times1=1$ (where the left child has $Y\gets1$ and the right child has $\abs{-1}=1$).
%The probability of sampling the left child of the red gate is then the computed sum of its left child divided by the red gate's computed sum, $\frac{1}{3}$.% = \abs{\circuit_\linput}\inparen{1,\ldots, 1} + \abs{\circuit_\rinput}\inparen{1,\ldots, 1}$, the sum of its children's values.
% visits each gate \circuit exactly once, computing $\abs{\circuit}\inparen{1,\ldots, 1}$. %for each gate \circuit.
%If we consider the leftmost source gates, \onepass computes $\abs{\circuit}\inparen{1,\ldots,1} = 1$ for $\circuit.\val = X$ and $\abs{\circuit}\inparen{1,\ldots, 1} = 2$ for $\circuit.\val = 2$. For the leftmost $\circmult$ gate, \onepass computes $\abs{\circuit}\inparen{1,\ldots, 1} = 2\circmult 1$, i.e. $\abs{\circuit_\linput}\inparen{1,\ldots, 1} \times \abs{\circuit_\rinput}\inparen{1,\ldots, 1}$ for children $\circuit_\linput$ and $\circuit_\rinput$. A level higher, the leftmost $\circplus$ gate recursively adds the values of its two children deriving $\abs{\circuit}\inparen{1,\ldots, 1} = 2 \circplus 1$, while using the expression $\frac{\abs{\circuit_i}\inparen{1,\ldots, 1}}{\abs{\circuit}\inparen{1,\ldots, 1}}$ for $i\in\inset{\linput, \rinput}$ to simultaneously compute the weights $\frac{1}{3}$ and $\frac{2}{3}$ for its children. The final sum value is then computed in similar fashion. % yielding $\abs{\circuit}\inparen{1,\ldots, 1} = 3 \circmult 3 = 9$.
%Given the computed values of \onepass, \sampmon picks a sampling path by traversing both children of a $\circmult$ gate and randomly choosing a child from a $\circplus$ gate according to the weight $\frac{\abs{\circuit_i}\inparen{1,\ldots, 1}}{\abs{\circuit}\inparen{1,\ldots, 1}}$ for $i\in\inset{\linput, \rinput}$.
We now consider a partial run of \sampmon that samples $\inparen{XY, -1}$ in~\Cref{fig:circuit}. It recursively traverses \emph{both} children of the sink $\circmult$ gate. For the \textcolor{red}{red} and \textcolor{green}{green} children, which are both $\circplus$ gates, we randomly choose one of their children. Specifically \sampmon then randomly picks the right child of the \textcolor{green}{green}$\circplus$ gate (i.e the \textcolor{blue}{blue}$\circmult$ gate that represents $-Y$ and is computed by recursing on both children of the \textcolor{blue}{blue}$\circmult$ gate) with probability of $\frac{1}{3}$ (where the numerator and denominator are the values computed by \onepass for the \textcolor{blue}{blue}$\circmult$ and \textcolor{green}{green}$\circplus$ gates respectively). Similarly at the left \textcolor{red}{red}$\circplus$ gate we sample the left child (representing $X$ and is computed by recursing to the leaf node $X$) with probability $\frac{1}{3}$. Note that the probability for choosing $\inparen{XY, -1}$ overall is $\frac{1}{3}\cdot\frac{1}{3}=\frac{1}{9}$, which is indeed the ratio of the coefficient of $\inparen{XY, -1}$ to the sum of all coefficients in $\abs{\circuit}$, as needed. %For the recursive call on the red gate, $\inparen{X, 1}$ is returned, while the purple gate recursively visits both children of the sampled $\circmult$ gate, returning $\inparen{Y, 1}$. %Multiplying $-1 \circmult XY$, concludes the random sampling of monomial $-XY$. Suppose \sampmon also randomly samples $X$ and $-Y$ from $\rpoly$ in a call to \approxq. To estimate $\rpoly\inparen{\vct{\prob}}$, \approxq computes $\prob_X - \prob_X\prob_Y - \prob_Y$ and scales the accumulation accordingly.
%such that a source gate \circuit has $\abs{\circuit}\inparen{1,\ldots, 1} = \circuit.\val$ when \circuit.\type $=$ \num and $\abs{\circuit}\inparen{1,\ldots,1} = 1$ otherwise. For every gate \circuit, \onepass computes $\abs{\circuit}\inparen{1,\ldots, 1}$ as seen in the lighter font of~\Cref{fig:circuit}. \onepass further weights each child $\circuit_i$ for $i\in\inset{\linput, \rinput}$, by the expression $\frac{\abs{\circuit_i}\inparen{1,\ldots, 1}}{\abs{\circuit}\inparen{1,\ldots, 1}}$. These weight are the basis for the sampling performed by \sampmon.
Let \circuit be an arbitrary \emph{\abbrOneBIDB} circuit, define $\poly(\vct{X})=\polyf(\circuit)$, let $k=\degree(\circuit)$, and let $\gamma=\gamma(\circuit)$. Further let it be the case that $\prob_i\ge\prob_0$ for all $i\in[\numvar]$. Then for all $\epsilon'>0$, an estimate $\mathcal{E}$ of $\rpoly(\prob_1,\ldots, \prob_\numvar)$
In particular, if $\prob_0>0$ and $\gamma<1$ are absolute constants then the above runtime simplifies to $$O_k\left(\left(\frac1{\inparen{\error'}^2}\cdot\size(\circuit)\cdot\log{\frac{1}{\conf}}\right)\cdot\multc{\log\left(\abs{\circuit}(1,\ldots, 1)\right)}{\log\left(\size(\circuit)\right)}\right).$$
Next, by \Cref{prop:circuit-depth} and \Cref{lem:circ-model-runtime} for any $\raPlus$ query $\query$, there exists a circuit $\circuit^*$ for $\apolyqdt$ such that $\depth(\circuit^*)\le O_{|Q|}(\log{n})$ and $\size(\circuit^*)\le O_k\inparen{\qruntime{\query, \tupset, \bound}}$. Then, we note that \Cref{prop:ctidb-reduct} gives us an equivalent $\circuit$ from $\circuit^*$ with essentially the same size/depth and has $\gamma(\circuit)\le1-c^{-\Omega(k)}$ (\Cref{lem:ctidb-gamma}). Finally, we argue (using the fact $\circuit$ has low depth) that $\abs{\circuit}(1,\dots,1)\le\size(\circuit)^{O_k(1)}$ (\Cref{lem:val-ub}).
%Next, we note that the above result %along with \Cref{lem:ctidb-gamma}
The above sequence of arguments results in the following result (which answers \Cref{prob:big-o-joint-steps} in the affirmative):
\begin{Corollary}
\label{cor:approx-algo-punchline-ctidb}
Let $\query$ be an $\raPlus$ query and $\pdb$ be a \abbrCTIDB with $p_0>0$, where $p_0$ as in \Cref{cor:approx-algo-const-p}, is an absolute constant. Let $\poly(\vct{X})=\apolyqdt$ for any result tuple $\tup$ with $\deg(\poly)=k$. Then one can compute an approximation satisfying \Cref{eq:approx-algo-bound-main} in time $O_{k,|Q|,\error',\conf,\bound}\inparen{\qruntime{\optquery{\query}, \tupset, \bound}}$ (given $\query,\tupset$ and $\prob_{\tup, j}$ for each $\tup\in\tupset,~j\in\pbox{\bound}$ that defines $\bpd$).
If we want to approximate the expected multiplicities of all $Z=O(n^k)$ result tuples $\tup$ simultaneously, we just need to run the above result with $\conf$ replaced by $\frac\conf Z$, which increases the runtime by a factor of $O_k(\log{n})$.
%%%% Commenting out he details below-- also copied over into the appendix
\iffalse
Further, we can also argue the following result.%, recalling from~\Cref{sec:intro} for \abbrCTIDB $\pdb = \inparen{\worlds, \bpd}$, where $\tupset$ is the set of possible tuples across all possible worlds of $\pdb$.
Given $\raPlus$ query $\query$ and \abbrCTIDB$\pdb$, let \circuit be the circuit computed by $\query\inparen{\tupset}$. Then, for the reduced \abbrOneBIDB$\pdb'$ there exists an equivalent circuit \circuit' obtained from $\query\inparen{\tupset'}$, such that $\gamma\inparen{\circuit'}\leq1-\bound^{-\inparen{k-1}}$ with $\size\inparen{\circuit'}\leq\size\inparen{\circuit}+\bigO{\numvar\bound}$
We briefly connect the runtime in \Cref{eq:approx-algo-runtime} to the algorithm outline earlier (where we ignore the dependence on $\multc{\cdot}{\cdot}$, which is needed to handle the cost of arithmetic operations over integers). The $\size(\circuit)$ comes from the time taken to run \onepass once (\onepass essentially computes $\abs{\circuit}(1,\ldots, 1)$ using the natural circuit evaluation algorithm on $\circuit$). We make $\frac{\log{\frac{1}{\conf}}}{\inparen{\error'}^2\cdot(1-\gamma)^2\cdot\prob_0^{2k}}$ many calls to \sampmon (each of which essentially traces $O(k)$ random sink to source paths in $\circuit$ all of which by definition have length at most $\depth(\circuit)$).
Note that the above implies that with the assumption $\prob_0>0$ and $\gamma<1$ are absolute constants from \Cref{cor:approx-algo-const-p}, then the runtime there simplifies to $O_k\left(\frac1{\inparen{\error'}^2}\cdot\size(\circuit)^2\cdot\log{\frac{1}{\conf}}\right)$ for general circuits $\circuit$. If $\circuit$ is a tree, then the runtime simplifies to $O_k\left(\frac1{\inparen{\error'}^2}\cdot\size(\circuit)\cdot\log{\frac{1}{\conf}}\right)$, which then answers \Cref{prob:intro-stmt} with yes for such circuits.
Finally, note that by \Cref{prop:circuit-depth} and \Cref{lem:circ-model-runtime} for any $\raPlus$ query $\query$, there exists a circuit $\circuit^*$ for $\apolyqdt$\textcolor{red}{CHANGE} such that $\depth(\circuit^*)\le O_{|Q|}(\log{n})$ and $\size(\circuit)\le O_k\inparen{\qruntime{\query, \tupset, \bound}}$. Using this along with \Cref{lem:val-ub}, \Cref{cor:approx-algo-const-p} and the fact that $n\le\qruntime{\query, \tupset, \bound}$, we have the following corollary:
Let $\query$ be an $\raPlus$ query and $\pdb$ be a \emph{\abbrOneBIDB} with $p_0>0$ and $\gamma<1$, where $p_0,\gamma$ as in \Cref{cor:approx-algo-const-p}, are absolute constants. Let $\poly(\vct{X})=\apolyqdt$\textcolor{red}{CHANGE} for any result tuple $\tup$ with $\deg(\poly)=k$. Then one can compute an approximation satisfying \Cref{eq:approx-algo-bound-main} in time $O_{k,|Q|,\error',\conf}\inparen{\qruntime{\optquery{\query}, \tupset, \bound}}$ (given $\query,\tupset$ and $p_i$ for each $i\in[n]$ that defines $\pd$).
Let $\query$ be an $\raPlus$ query and $\pdb$ be a \abbrCTIDB with $p_0>0$, where $p_0$ as in \Cref{cor:approx-algo-const-p}, is an absolute constant. Let $\poly(\vct{X})=\apolyqdt$\textcolor{red}{CHANGE}for any result tuple $\tup$ with $\deg(\poly)=k$. Then one can compute an approximation satisfying \Cref{eq:approx-algo-bound-main} in time $O_{k,|Q|,\error',\conf,\bound}\inparen{\qruntime{\optquery{\query}, \tupset, \bound}}$ (given $\query,\tupset$ and $\prob_{\tup, j}$ for each $\tup\in\tupset,~j\in\pbox{\bound}$ that defines $\bpd$).