## 3 A Single Traversal DP Algorithm
#### An Algorithm on the Semi-Incidence Graph
According to Algorithm 2 and since \(u\) is derived from \(u^{\prime}\), we have \(r\in\sigma^{\prime}\) Similarly, for any \(\langle C^{\prime},\rho^{\prime}\rangle\in\mathcal{C}^{\prime}\), \(r\in\rho^{\prime}\). Since \(u^{\prime}\) is a local partial solution, there exists a partial solution \(\hat{u}^{\prime}\) of \(t^{\prime}\), satisfying the conditions of Definition 5. Then, \(\hat{u}^{\prime}\) is also a partial solution for node \(t\), since it satisfies all conditions of Definitions 3 and 4. Finally, note that \(u=(\hat{u}^{\prime})^{t}\) since the projection of \(\hat{u}^{\prime}\) to the bag \(\chi(t)\) is \(u\) itself. In consequence, the tuple \(u\) is a local partial solution. For \(a\in\mathrm{at}_{t^{\prime}}\setminus\mathrm{at}_{t}\) as well as for introduce nodes, we can analogously check the lemma. Next, assume that \(t\) is a join node. Therefore, let \(u^{\prime}\) and \(u^{\prime\prime}\) be local partial solutions for \(t^{\prime},t^{\prime\prime}\in N\), respectively, and \(u\) be a tuple for node \(t\in N\) such that \(u\) can be derived using both \(u^{\prime}\) and \(u^{\prime\prime}\) in accordance with the \(\mathbb{SINC}\) algorithm. Since \(u^{\prime}\) and \(u^{\prime\prime}\) are local partial solutions, there exists partial solution \(\hat{u}^{\prime}=(\hat{M}^{\prime},\hat{\sigma}^{\prime},\hat{C}^{\prime})\) for node \(t^{\prime}\) and partial solution \(\hat{u}^{\prime\prime}=(\hat{M}^{\prime\prime},\hat{\sigma}^{\prime\prime}, \hat{C}^{\prime\prime})\) for node \(t^{\prime\prime}\). Using these two partial solutions, we can construct \(\hat{u}=(\hat{M}^{\prime}\cup\hat{M}^{\prime\prime},\hat{\sigma}^{\prime}\) via \(\hat{\sigma}^{\prime\prime},\hat{C}^{\prime}\bowtie\hat{C}^{\prime\prime})\) where \(\bowtie(\cdot,\cdot)\) is defined in accordance with Algorithm 2 as follows:

\[\hat{C}^{\prime}\bowtie\hat{C}^{\prime\prime} := \{(\hat{C}^{\prime}\cup\hat{\sigma}^{\prime\prime},\hat{\sigma}^{ \prime\prime})\mid(\hat{C}^{\prime},\hat{\sigma}^{\prime})\in\hat{C}^{\prime},(\hat{C}^{\prime\prime},\hat{\sigma}^{\prime\prime})\in\hat{C}^{\prime\prime}, \hat{C}^{\prime}\cap\mathrm{at}_{t}=\hat{C}^{\prime\prime}\cap\mathrm{at}_{t}\}\cup\] \[\{(\hat{C}^{\prime}\cup\hat{M}^{\prime\prime},\hat{\sigma}^{ \prime\prime})\mid(\hat{C}^{\prime},\hat{\sigma}^{\prime})\in\hat{C}^{\prime},\hat{C}^{\prime}\cap\mathrm{at}_{t}=\hat{M}^{\prime\prime}\cap\mathrm{at}_{t}\}\cup\] \[\{(\hat{M}^{\prime}\cup\hat{C}^{\prime\prime},\hat{\sigma}^{ \prime\prime})\mid(\hat{C}^{\prime\prime},\hat{\sigma}^{\prime\prime})\in\hat{C} ^{\prime\prime},\hat{M}^{\prime}\cap\mathrm{at}_{t}=\hat{C}^{\prime\prime}\cap \mathrm{at}_{t}\}.\]

Then, we check all conditions of Definitions 3 and 4 in order to verify that \(\hat{u}\) is a partial solution for \(t\). Moreover, the projection \(\hat{u}^{\prime}\) of \(\hat{u}\) to the bag \(\chi(t)\) is exactly \(u\) by construction and hence, \(u=\hat{u}^{t}\) is a local partial solution. Since we have provided arguments for each node type, we established soundness in terms of the statement of the lemma. **Lemma 2** (Completeness). : _Let \(P\) be a program, \(\mathcal{T}=(T,\chi)\) where \(T=(N,\cdot,\cdot)\) be a tree decomposition of the semi-incidence graph \(S(P)\) and \(t\in N\) be a node. Given a local partial solution \(u\) of table \(t\), either \(t\) is a leaf node, or there exists a local partial solution \(u^{\prime}\) of child table \(\tau^{\prime}\) (or local partial solution \(u^{\prime}\) of table \(\tau^{\prime}\) and local partial solution \(u^{\prime\prime}\) of table \(\tau^{\prime\prime}\)) such that \(u\) can be constructed by \(u^{\prime}\) (or \(u^{\prime}\) and \(u^{\prime\prime}\), respectively) and using table algorithm \(\mathbb{SINC}\)._

Proof. : Let \(t\in N\) be a removal node and \(r\in P_{t^{\prime}}\setminus P_{t}\) with child node \(t^{\prime}\in N\). We show that there exists a tuple \(u^{\prime}\) in table \(\tau_{t^{\prime}}\) for node \(t^{\prime}\) such that \(u\) can be constructed usingby \(\mathbb{SINC}\) (Algorithm 2).