We now show:

######  Lemma D.4.

Let $C$ and $C^{\prime}$ be stitchable circuits with tree decompositions $T$
and $T^{\prime}$ with same skeleton (with witnessing bijection $\psi$). Assume
that for any $g\in C^{\prime}_{\mathsf{inp}}$ and bag $b$ of $T^{\prime}$ with
$g\in\operatorname{dom}(b)$, we have $g\in\operatorname{dom}(\psi^{-1}(b))$.
Then $T+T^{\prime}$ is a tree decomposition of $C\circ C^{\prime}$.

e consider $I_{C\circ C^{\prime}}$ and show that $T+T^{\prime}$ is a tree
decomposition of it:

  * •

Let $g$ be a gate of $C\circ C^{\prime}$. If $g$ is not a gate of $C\cap
C^{\prime}$, then its occurrences in $T+T^{\prime}$ are only its occurrences
in $T$ or in $T^{\prime}$, so that they form a connected subtree of
$T+T^{\prime}$ as they did in $T$ or $T^{\prime}$. If it is a gate of $C\cap
C^{\prime}$, then it is an input gate of $C^{\prime}$ because $C$ and
$C^{\prime}$ are stitchable, and by the hypothesis, its occurrences in
$T^{\prime}$ are a subset of its occurrences in $T$, so its occurrences in
$T+T^{\prime}$ are its occurrences in $T$, and they also form a connected
subtree.

  * •

Let $\mathbf{g}$ be a tuple occurring in a fact of $I_{C\circ C^{\prime}}$.
Clearly $\mathbf{g}$ occurs either in $I_{C}$ or in $I_{C^{\prime}}$, so that
it is covered by the bag $b_{\mathbf{g}}$ that covers all elements of
$\mathbf{g}$ in $T$ or in $T^{\prime}$.

Last, we conclude the proof of Theorem D.1:

et $k\in\mathbb{N}$, $q$ be the GSO sentence, and let $A$ be a
$\Gamma^{k}_{\sigma}$-bNTA that tests $q$ for treewidth $k$ according to
Theorem 4.1, which we lift to a $\overline{\Gamma^{k}_{\sigma}}$ in the same
way as in the proof of Theorem 4.2.

Construct in linear time in the input cc-instance $J=(I,C,\varphi)$ a tree
decomposition of $J$ of width $\leqslant k$, and a cc-encoding
$E^{\prime}=(E,C,T,\chi)$ of width $k$ of $J$, according to Lemma D.1,
satisfying the conditions of that lemma. Now, use Theorem 4.2 to compute an
arity-two provenance circuit $C^{\prime}$ of $A$ on $E$ and with a tree
decomposition $T^{\prime}$ whose width is constant in $I$. We further observe
from the proof of the proposition that $T^{\prime}$ that has same skeleton as
$E$ (and $T$), and that for any node $n\in E$, the input gate for this node is
in the bag corresponding to $n$ in $T^{\prime}$.

We then observe that $C^{\prime}$ and $C$ are stitchable circuits, and that
their tree decompositions $T^{\prime}$ and $T$ have same skeleton and satisfy
the conditions of Lemma D.4. We deduce from this lemma and Lemma D.3 that we
can construct in linear time the stitching $C^{\prime\prime}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=C\circ
C^{\prime}$ and a tree decomposition of it, whose width does not depend on
$J$. We now show that $C^{\prime\prime}$ satisfies the desired property,
namely, $\nu(C^{\prime\prime})$ is $1$ iff $\nu(J)\models q$. For any
valuation $\nu$ of $J_{\mathsf{inp}}$, we have $\nu(C\circ
C^{\prime})=\nu^{\prime}(C^{\prime})$, by Lemma D.2, where $\nu^{\prime}$ is
the valuation of $C^{\prime}_{\mathsf{inp}}$ obtained from $\nu(C)$. It is
clear by definition of $\nu(J)$ that a fact $F$ is present in $\nu(J)$ iff
$\varphi(F)$ is true in $\nu(C)$. We conclude using the fact that
$\nu^{\prime}$ is a provenance circuit: $\nu^{\prime}(C^{\prime})$ holds iff
$\\{F\in I\mid\varphi(F)\text{ true in }\nu(C)\\}\models q$.

#### Probability evaluation.

We now describe the consequences of Theorem D.1 in terms of probability
evaluation. Here is what we want to show:

######  Corollary D.1.

The problem of computing the probability of a fixed GSO sentence on bounded-
treewidth pcc-instances can be solved in ra-linear time data complexity.

To prove this corollary, we need the following definition and key result:

######  Definition D.6.

Let $C=(G,W,g_{0},\mu)$ be an (arity-two non-monotone) Boolean circuit and
$\pi$ be a _probabilistic valuation_ of $C$ associating each $g\in
C_{\mathsf{inp}}$ to a probability distribution $\pi_{g}$ on $\\{0,1\\}$, that
is, one rational $v_{0}=\pi_{g}(0)$ and one rational $v_{1}=\pi_{g}(1)$ such
that $v_{0}+v_{1}=1$. The _probability evaluation problem_ for $C$ and $\pi$
is to compute the probability distribution of $g_{0}$ under the product
distribution for the inputs (i.e., assuming independence), that is,
$\Pr\nolimits_{g_{0}}$ mapping $v\in\\{0,1\\}$ to

$\textstyle\sum_{\begin{subarray}{c}\nu\in\mathrm{Val}(C_{\mathsf{inp}})\\\
\nu(g_{0})=v\end{subarray}}\prod_{g\in C_{\mathsf{inp}}}\pi_{g}(\nu(g))$

where $\mathrm{Val}(C_{\mathsf{inp}})$ denotes the set of Boolean valuations
of $C_{\mathsf{inp}}$.

######  Theorem D.2.

Given a tree decomposition $T$ of width $k$ of an arity-two Boolean circuit
$C$, and given a probabilistic valuation $\pi$ of $C$, the probability
evaluation problem for $C$ and $\pi$ can be solved in time _ra-linear_ in
$2^{k}\left|T\right|+\left|\pi\right|+\left|C\right|$.

With the above theorem, we can prove Corollary D.1 as follows:

et $J=(I,C,\varphi,\pi)$ be a pcc-instance of treewidth $k$ and $q$ a query.
We use Theorem D.1 to construct in linear time a Boolean circuit $C^{\prime}$
of treewidth $k^{\prime}$ dependent only on $k$ and $q$, with distinguished
gate $g$. We build from $C^{\prime}$ a tree decomposition of width
$k^{\prime}$ in linear time. The probability that $q$ is true in $J$ is
$\Pr\nolimits_{g}(1)$. We conclude as Theorem D.2 states that this can be
computed in ra-linear time in $\left|C^{\prime}\right|+\left|\pi\right|$ for
fixed $k^{\prime}$.

We now prove Theorem D.2.

ix $T=(B,L,R,\operatorname{dom})$ a tree decomposition of a Boolean circuit
$C=(G,W,g_{0},\mu)$ (so that for any $b\in B$, $\operatorname{dom}(b)$ is a
set of gates of $G$). We define $E\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=L\cup
R$ and, for $g\in G$, $V(g)$ the value set of $g$. For $e=(b_{1},b_{2})\in E$,
we define $\operatorname{dom}(e)\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\operatorname{dom}(b_{1})\cap\operatorname{dom}(b_{2})$,
the shared elements between a bag and its parent. We assume an arbitrary order
$<$ over $G$ and see $\operatorname{dom}(b)$ as a tuple by ordering elements
of $\operatorname{dom}(b)$ with $<$ (this ordering taking constant time as the
size of bags is bounded by a constant). If
$\operatorname{dom}(b)=(g_{1},\dots,g_{m})$, we note $V(b)=\\{0,1\\}^{m}$ (and
similarly, for $e\in E$, $V(e)$ is the product over $\operatorname{dom}(e)$).
For every $g\in G$, let $\beta(g)\in B$ be an arbitrary bag containing $g$ and
all gates that are inputs of $g$, that is, all gates $g^{\prime}$ such that
$(g^{\prime},g,i)\in W$ for some $W$: such a bag exists by definition of the
tree decomposition of circuits (there is a fact in $I_{C}$ regrouping $g$ and
the $g^{\prime}$) and we can precompute such a function in linear time by a
traversal of $T$. In particular, if $g$ is an input gate, then $\beta(g)$ is
an arbitrary bag containing just $g$.

We associate to every bag $b\in B$ (resp., every edge $e\in E$) a _potential
function_ $\Phi^{b}:V(b)\to\mathbb{Q}^{+}$ (resp.,
$\Phi^{e}:V(e)\to\mathbb{Q}^{+}$), where $\mathbb{Q}^{+}$ denotes the
nonnegative rational numbers, initialized to the constant $1$ function. We
will store for each bag and each edge the full table of values of $\Phi^{e}$,
i.e., at most $2^{k}$ values, each of which has size bounded by
$\left|\pi\right|$.

The functions $\pi_{g}$ for $g\in C_{\mathsf{inp}}$ are mappings from $V(g)$
to $\mathbb{R}^{+}$. For a bag $b\in B$ with $g\in\operatorname{dom}(b)$, we
define $\pi_{g}^{b}$ as the function that maps every tuple $\mathbf{d}\in
V(b)$ to $\pi_{g}(d^{\prime})$ where $d^{\prime}$ is the value assigned to $g$
in $\mathbf{d}$.

For $g$ a non-input gate, let $\kappa(g)$ be the tuple formed of $g$ and all
gates with a wire to $g$, ordered by $<$. Let $f\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\mu(g)$
be the function of $g$, in $\\{\neg,\vee,\wedge,0,1\\}$. We see $f$ as a
subrelation $R_{g}$ of $V(\kappa(t))$ (the table of values of the function,
with columns reordered by applying $<$ on $g$), that is, a set of
$(\mathrm{arity}(f)+1)$-tuples which represents the graph of the function.

We update the potential function by the following steps, where the product of
two functions $f$ and $f^{\prime}$ which have same domain $D$ denotes
pointwise multiplication, that is, $(f\times f^{\prime})(x)=f(x)\times
f^{\prime}(x)$ for all $x\in D$:

  1. 1.

For every $g\in C_{\mathsf{inp}}$, we set $\Phi^{\beta(g)}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\Phi^{\beta(g)}\times\pi_{g}^{\beta(g)}$.

  2. 2.

For every $g\in G\backslash C_{\mathsf{inp}}$, we set
$\Phi^{\beta(g)}(\mathbf{d})\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=0$
if the projection of $\mathbf{d}$ onto $\kappa(g)$ is not in $R_{g}$, we leave
$\Phi^{\beta(g)}(t)$ unchanged otherwise.

Note that we have now initialized the potential functions in a way which
exactly corresponds to that of [huang1996inference], for a straightforward
interpretation of our circuit with probabilistic inputs as a special case of a
belief network where all non-root nodes are deterministic (i.e., have a
conditional distribution with values in $\\{0,1\\}$).

We now apply as is the Global Propagation steps described in Section 5.3 of
[huang1996inference]: if we choose the root of the tree decomposition as the
root cluster $\mathbf{X}$, this consists in propagating potentials from the
leaves of the tree decomposition up to the root, then from the root down to
the leaves of the tree. This process is linear in $\left|T\right|$ and, at
every bag of $T$, requires a number of arithmetic operations linear in
$2^{k}$.

As shown in [lauritzen1988local, huang1996inference], at the end of the
process, the desired probability distribution $\Pr\nolimits_{g}$ for gate $g$
can be obtained by marginalizing $\Phi^{\beta(g)}$:

$\Pr\nolimits_{g}(d^{\prime})=\sum_{\makebox[0.0pt]{$\scriptstyle\begin{subarray}{c}\mathbf{d}\in
V(\beta(g))\\\ d_{k}=d^{\prime}\end{subarray}$}}\Phi^{\beta(g)}(\mathbf{d})$

where $k$ is the position of $g$ in $\operatorname{dom}(\beta(g))$.

The whole process is linear in $\left|T\right|\times
2^{k}+\left|C\right|+\left|\pi\right|$ under fixed-cost arithmetic; under
real-cost arithmetic, belief propagation requires multiplying and summing
linearly many times $O(\left|T\right|\times 2^{k})$ probability values, each
of size bounded by $\left|\pi\right|$, which is polynomial-time in
$\left|T\right|$, $2^{k}$, $\left|\pi\right|$.

#### Consequences for pc-instances.

We define existing the formalism of _(p)c-instances_ [suciu2011probabilistic],
which is analogous to (p)cc-instances, but annotates facts with propositional
formulae rather than circuits:

######  Definition D.7 ([huang2009maybms, green2006models]).

A _c-instance_ $J$ is a relational instance where each tuple is labeled with a
propositional formula of variables (or _events_) from a fixed set $X$. For a
valuation $\nu$ of $X$ mapping each variable to $\\{0,1\\}$, the possible
world $\nu(J)$ is obtained by retaining exactly the tuples whose annotation
evaluates to $1$ under $\nu$; $\llbracket J\rrbracket$ is the set of all these
possible worlds. Observe that different valuations may yield the same possible
world.

A _pc-instance_ $J=(J^{\prime},\pi)$ is defined as a c-instance $J^{\prime}$
and a _probabilistic valuation_ $\pi:X\to[0,1]$ for the variables used in
$J^{\prime}$. Like all probabilities in this paper, the values of $\pi$ are
rationals. The probability distribution $\llbracket J\rrbracket$ defined by
$J$ has universe $\llbracket J^{\prime}\rrbracket$ and probability measure
$\Pr\nolimits_{J}(I)\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\sum_{\begin{subarray}{c}\nu\mid\nu(J^{\prime})=I\end{subarray}}\Pr\nolimits_{J}(\nu)$
with the product distribution on valuations:

$\textstyle\Pr\nolimits_{J}(\nu)\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\prod_{\begin{subarray}{c}x\in
X\\\ \nu(x)=1\end{subarray}}\pi(x)\>\prod_{\begin{subarray}{c}x\in X\\\
\nu(x)=0\end{subarray}}(1-\pi(x)).$

We define a notion of treewidth for them:

######  Definition D.8.

Let $\sigma^{\mathrm{o}}=\sigma\cup\\{\mathrm{Occ},\mathrm{Cooc}\\}$, where
$\mathrm{Occ}$ and $\mathrm{Cooc}$ have arity two. From a pc-instance $J$, we
define the _relational encoding_ $I_{J}$ of $J$ as the
$\sigma^{\mathrm{o}}$-instance where each event $e$ of $J$ is encoded to a
fresh $a_{e}\in\operatorname{dom}(J)$, and where we add a fact
$\mathrm{Occ}(a,a_{e})$ in $I_{J}$ whenever $a\in\operatorname{dom}(J)$ is
used in a fact annotated by a formula involving $e$, and
$\mathrm{Cooc}(a_{e},a_{f})$ whenever events $e$ and $f$ co-occur in the
formula of some fact.

The _treewidth_ $0pt(J)$ of a (p)c-instance $J$ is $0pt(I_{J})$.

This notion of treewidth, through event (co-)occurrences, can be connected to
treewidth for (p)cc-instances, to ensure tractability of query evaluation on
(p)c-instances of bounded treewidth in that sense. A technicality is that we
must first rewrite annotations of the bounded-treewidth (p)c-instance to bound
their size by a constant; but we can show:

######  Proposition D.1.

For any fixed $k$, given a (p)c-instance $J$ of width $\leqslant k$, we can
compute in linear time a (p)cc-instance $J$ which is equivalent (has the same
possible worlds with the same probabilities) and has treewidth depending only
on $k$.

e first justify that we can compute in linear time from $J$ (p)c-instance
$J^{\prime}$ with the same events such that for any valuation $\nu$, we have
$\nu(J)=\nu(J^{\prime})$ (and
$\Pr\nolimits_{J}(\nu)=\Pr\nolimits_{J^{\prime}}(\nu)$), and the annotations
of $J^{\prime}$ have size depending only on $k$.

Indeed, we observe that by our assumption that $0pt(J)\leqslant k$, for any
formula $F$ in an annotation, the number of distinct events occurring in $F$
is at most $k$. Indeed, there is a $\mathrm{Cooc}$ clique between these events
in $I_{J}$, so that as $0pt(I_{J})\leqslant k$ (by Lemma 1 of
[gavril1974intersection]) there must be less than $k$ of them.

Now, we observe that any formula in $J$ can be rewritten, in linear time in
this formula for fixed $k$, to an equivalent formula whose size depends only
on $k$. Indeed, for every valuation of the input events, which means at most
$2^{k}$ valuations by the above, we can evaluate the formula in linear time;
then we can rewrite the formula to the disjunction of all valuations that
satisfy it, each valuation being tested as the conjunction of the right events
and negation of events. So this overall process produces in linear time an
equivalent (p)c-instance $J^{\prime}$ where the annotation size depends only
on $k$. So we can assume without loss of generality that the size of the
annotations of $J$ is bounded by a constant.

Consider now the (p)c-instance $J$, its relational encoding $I_{J}$, and a
tree decomposition $T$ of $I_{J}$. We build a tree decomposition $T^{\prime}$
of a relational encoding $I_{J}$ of a cc-instance $J^{\prime}=(I,C,\varphi)$
designed to be equivalent to $J$. Start by adding to $C$ the input gates,
which correspond to the events of $J$.

Now, consider each fact $F=R(\mathbf{a})$ of $J$. Let $\mathbf{e}$ be the set
of events used in the annotation $A_{F}$ of $F$. Note that every pair of
$S=\mathbf{a}\sqcup\mathbf{e}$ co-occurs in some fact of $I_{J}$: the elements
of $\mathbf{a}$ co-occur within $F$, the elements of $\mathbf{e}$ co-occur in
a $\mathrm{Cooc}$ fact, and any pair of elements from $\mathbf{a}$ and
$\mathbf{e}$ co-occur in some $\mathrm{Occ}$ fact. Hence, by Lemma 1 of
[gavril1974intersection], there is a bag $b_{F}\in T$ such that
$S\subseteq\operatorname{dom}(b)$.

Let $C_{F}$ be a circuit representation of the Boolean function $A_{F}$ on
$E$, whose size depends only on $k$. Add $C_{F}$ to $C$, add $F$ to $I$, and
set $\varphi(F)$ to be the distinguished node of $C_{F}$. We have thus built
$J^{\prime}$, which by construction is equivalent to $J$.

We now build $T^{\prime}$ by making it a copy of $T$. Now, for each fact $F$,
considering its bag $b_{F}$, and $b_{F}^{\prime}$ the corresponding bag in
$T^{\prime}$, we add all elements of $C_{F}$ to $b_{F}^{\prime}$. This
decomposition clearly covers all facts of $I_{J^{\prime}}$, and event
occurrences form subtrees because they do in $T$ and the elements that we
added to $T^{\prime}$ are always in a single bag only. Last, it is clear that
the bag size depends only on $k$, as the size of the $C_{F}$ added to the bags
depends only on $k$, and at most $k$ of them are added to each bag (because
there are at most $k$ elements per bag).

We have not talked about probabilities, but clearly if $J$ is a pc-instance
the probabilities of the inputs of the pcc-instance $J^{\prime}$ should be
defined analogously.

We can now combine the above with Theorem D.1, and deduce the tractability of
query evaluation on bounded-treewidth pc-instances.

######  Theorem D.3.

For bounded-treewidth pc-instances, the probability query evaluation problem
for Boolean MSO queries can be solved in ra-linear time data complexity.

he result is an immediate consequence of Proposition D.1 and Theorem D.1 as
long as we show that, for any fixed $k\in\mathbb{N}^{*}$, and for every
(p)c-instance $J$ of width $\leqslant k$, one can compute in linear time a
(p)c-instance $J^{\prime}$ with the same events such that for any valuation
$\nu$, we have $\nu(J)=\nu(J^{\prime})$ (and
$\Pr\nolimits_{J}(\nu)=\Pr\nolimits_{J^{\prime}}(\nu)$), and the annotations
of $J^{\prime}$ have size depending only on $k$.

Fix $k$ and $J$. We observe that by our assumption that $0pt(J)\leqslant k$,
for any formula $\Phi$ in an annotation, the number $p_{\Phi}$ of distinct
events occurring in $\Phi$ is at most $k$. Indeed, there is a $\mathrm{Cooc}$
clique between these events in $I_{J}$ and each of them is connected by the
$\mathrm{Occ}$ relation to domain elements of the fact $F$ annotated by $\Phi$
(there is at least one), so we have in total a $(p_{\Phi}+1)$-clique. By Lemma
1 of [gavril1974intersection], any tree decomposition must have one node
containing all these $p_{\Phi}+1$ elements, and therefore $p_{\Phi}\leqslant
k$.

Now, we observe that any formula in $J$ can be rewritten, in linear time in
this formula for fixed $k$, to an equivalent formula whose size depends only
on $k$. Indeed, for every valuation of the input events, which means at most
$2^{k}$ valuations by the above, we can evaluate the formula in linear time;
then we can rewrite the formula to the disjunction of all valuations that
satisfy it, each valuation being tested as a conjunction of at most $k$
literals. So this overall process produces in linear time an equivalent
(p)c-instance where the annotation size depends only on $k$.

###  D.2 Probabilistic XML

We will first prove the result on scopes (Proposition 6.1) and then prove the
result on local models (Theorem 6.1).

#### XML and instances.

We first describe XML documents and their connections to relational models.

######  Definition D.9.

An _XML document_ with _label set_ $\Lambda$ (or _$\Lambda$ -document_) is an
_unranked_ $\Lambda$-tree.

######  Definition D.10.

A $\mathsf{PrXML}$-tree $T$ is an _unranked_ $\Lambda$-tree, for a fixed
alphabet $\Lambda$ of _labels_ , augmented with a set of Boolean events
$\mathcal{E}$ where each event $e_{x}$ has a probability $0\leqslant
p_{x}\leqslant 1$, and where each edge of the tree is labeled by a
propositional formula over $\mathcal{E}$.

We see $T$ as defining a probability distribution over $\Lambda$-trees in the
following fashion: for every valuation $\nu$ over $\mathcal{E}$, the possible
world $\nu(T)$ is obtained by removing all edges whose annotation evaluates to
false under $\nu$, and all their descendent nodes and edges. The probability
of a $\Lambda$-tree $T^{\prime}$ according to $T$ is the sum of the
probability of all valuations $\nu$ such that $\nu(T)=T^{\prime}$, where the
probability of a valuation is defined assuming that the events in
$\mathcal{E}$ are drawn independently with their indicated probability.

######  Definition D.11.

To perform _query evaluation_ on a $\mathsf{PrXML}$ document is to determine,
for a fixed query over $\Lambda$-trees, given an input $\mathsf{PrXML}$
document $T$, what is the total probability of its possible worlds that
satisfy $q$; we study its _data complexity_ , i.e., its complexity as a
function of $T$.

We always assume that the label set $\Lambda$ is fixed (not provided as
input). As XML documents are unranked, it is often more convenient to
manipulate their binary left-child-right-sibling representation:

######  Definition D.12.

The _left-child-right-sibling_ (LCRS) representation of an unranked rooted
ordered $\Lambda$-tree $T$ is the following $\Lambda$-tree $T^{\prime}$: a
node $n$ whose children are the ordered sequence of siblings
$n_{1},\ldots,n_{k}$ is encoded as the node $n$ with $L(n)=n_{1}$,
$R(n_{1})=n_{2}$, …, $R(n_{k-1})=n_{k}$; we complete by nodes labeled
$\bot\notin\Lambda$ to make the tree full.

We now define how XML documents can be encoded to the relational setting.

######  Definition D.13.

Given a $\Lambda$-document $D$, let $\sigma_{\Lambda}$ be the relational
signature with two binary predicates $\mathit{FC}$ and $\mathit{NS}$ (for
“first child” and “next sibling”), and unary predicates $P_{\lambda}$ for
every $\lambda\in\Lambda$. The _relational encoding_ $I_{D}$ of $D$ is
the-$\sigma_{\Lambda}$ instance with
$\operatorname{dom}(I_{D})=\operatorname{dom}(D)$, such that:

  * •

for any consecutive siblings $(n,n^{\prime})$, $\mathit{NS}(n,n^{\prime})$
holds;

  * •

for every pair $(n,n^{\prime})$ of a node $n\in D$ and its first child
$n^{\prime}\in D$ following sibling order, $\mathit{FC}(n,n^{\prime})$ holds;

  * •

for every node $n\in D$, the fact $P_{\lambda(n)}(n)$ holds.

######  Lemma D.5.

The relational encoding $I_{D}$ of an XML document $D$ has treewidth $1$ and
can be computed in linear time.

mmediate: the relational encoding is clearly computable in linear time and
there is a width-1 tree decomposition of the relational encoding that has same
skeleton as the LCRS representation of the XML document.

Importantly, the language of MSO queries on XML documents [neven2002query],
which we now define formally, can be easily translated to queries on the
relational encoding:

######  Definition D.14.

An _MSO query_ on XML documents is a MSO formula where first-order variables
refer to nodes and where atoms are $\lambda(x)$ ($x$ has label $\lambda$),
$x\rightarrow y$ ($x$ is the parent of $y$), and $x<y$ ($x$ and $y$ are
siblings and $x$ comes before $y$).

######  Lemma D.6.

For any MSO query $q$ on $\Lambda$-documents, one can compute in linear time
an MSO query $q^{\prime}$ on $\sigma_{\Lambda}$ such that for any
$\Lambda$-document $D$, $D\models q$ iff $I_{D}\models q^{\prime}$.

e add a constant overhead to $q$ by defining the predicates $\lambda(x)$ for
$\lambda\in\Lambda$ as $P_{\lambda}(x)$, the predicate $x<y$ to be the
transitive closure of $\mathit{NS}$ ($\neg(x=y)\wedge\forall S(x\in
S\wedge(\forall zz^{\prime}(z\in S\wedge\mathit{NS}(z,z^{\prime}))\Rightarrow
z^{\prime}\in S)\Rightarrow y\in S)$), and the predicate $x\rightarrow y$ to
be $\exists z,\mathit{FC}(x,z)\wedge(z=y\vee z<y)$. It is clear that the
semantics of those atoms on $I_{D}$ match that of the corresponding atoms on
$D$, so that a straightforward structural induction on the formula shows that
$q^{\prime}$ satisfies the desired properties.

######  Definition D.15.

Given label set $\Lambda$, we say that an XML document $D$ on
$\Lambda\sqcup\\{\bot,\det\\}$ is a _sparse representation_ of an XML document
$D^{\prime}$ on $\Lambda$ if the root is labeled with an element of $\Lambda$,
and the XML document obtained from $D$ by removing every $\bot$ node and their
descendants, and replacing every $\det$ node by the collection of its
children, in order, is exactly $D^{\prime}$.

We say that a $\sigma_{\Lambda\sqcup\\{\det\\}}$ instance $I$ is a _weak
relational encoding_ of an XML document $D$ with label set $\Lambda$ if there
exists a sparse representation $D^{\prime}$ of $D$ such that $I$ is the
relational encoding of $D^{\prime}$ except that $P_{\bot}$ facts are not
written.

######  Proposition D.2.

For any MSO query $q$ on XML documents with (fixed) label set $\Lambda$, one
can compute in linear time an MSO query $q^{\prime}$ on $\sigma_{\Lambda}$
such that for any XML document $D$ on label set $\Lambda$, if $D\models q$
then $I\models q^{\prime}$ for any weak relational encoding $I$ of $D$; and
conversely if $D\not\models q$ then $I\not\models q^{\prime}$ for any weak
relational encoding $I$ of $D$.

e show that, for any MSO query $q$ on XML documents with (fixed) label set
$\Lambda$, one can compute in linear time an MSO query $q^{\prime}$ on
documents with label in $\Lambda\sqcup\\{\bot,\det\\}$ such that for any XML
document $D$ on label set $\Lambda$, if $D\models q$ then $D^{\prime}\models
q^{\prime}$ for any sparse representation $D^{\prime}$ of $D$; and conversely
if $D\not\models q$ then $D^{\prime}\not\models q^{\prime}$ for any sparse
representation $D^{\prime}$ of $D$. The result then follows by Lemma D.6.

We call _regular_ the nodes with label in $\Lambda$. Consider a document $D$
and sparse representation $D^{\prime}$ of $D$ with a mapping $f$ from $D$ to
$D^{\prime}$ witnessing that $D^{\prime}$ is a sparse representation of $D$.
Let us consider a node $n\in D$ with children $n_{1},\ldots,n_{k}$ in order,
and determine what is the relationship between $f(n)$ and the $f(n_{i})$ in
$D^{\prime}$.

It is straightforward to observe that $f(n)$ is regular and the $f(n_{i})$ are
topmost regular descendants of $f(n)$ in $D^{\prime}$; and for $i<j$, there is
some node $n^{\prime}$ in $D^{\prime}$ (intuitively, their lowest common
ancestor, which is a descendant of $f(n)$, possibly $f(n)$ itself) such that
$n^{\prime}$ is both an ancestor of $f(n_{i})$ and $f(n_{j})$, $n^{\prime}$ is
a descendant of $f(n)$, and $n^{\prime}$ has two children $n_{1}^{\prime}$ and
$n_{2}^{\prime}$ such that $f(n_{i})$ is a descendant of $n_{1}^{\prime}$
(maybe they are equal), $f(n_{j})$ is a descendant of $n_{2}^{\prime}$ (maybe
they are equal), and $n_{1}^{\prime}<n_{2}^{\prime}$ in $D^{\prime}$. Note
that $n^{\prime}$, $n_{1}^{\prime}$ and $n_{2}^{\prime}$ are not necessarily
regular nodes of $D$ but can be $\det$ nodes. In addition, no $\bot$ node can
be traversed in any of the ancestor–descendant chains discussed in this
paragraph.

It is now clear that we can have MSO predicates $\rightarrow^{\prime}$ and
$<^{\prime}$ in $D^{\prime}$ following these informal definitions (and not
depending on $D$ or $D^{\prime}$), defined from predicates $\rightarrow$, $<$
and $\lambda(\cdot)$ on $D^{\prime}$, such that for every $D$ and sparse
encoding $D^{\prime}$ of $D$, for every nodes $n,n^{\prime}\in D$, we have
$n\rightarrow n^{\prime}$ in $D$ iff $f(n)\rightarrow f(n^{\prime})$ in
$D^{\prime}$ (which should only hold between regular nodes, so nodes in the
image of $f$), and likewise for $<$. Last, it is clear that the predicates
$\lambda(\cdot)$ of $D$ can be encoded directly to the same predicates in
$D^{\prime}$.

#### Probabilistic XML.

We formally introduce probabilistic XML. We start by
$\mathsf{PrXML}^{\mathsf{fie}}$, i.e., $\mathsf{PrXML}$ with events.

######  Definition D.16.

A $\mathsf{PrXML}^{\mathsf{fie}}$ probabilistic XML document
$D=(D^{\prime},\pi)$ is a $(\Lambda\sqcup\\{\mathsf{fie}\\})$-document
$D^{\prime}$ where edges from $\mathsf{fie}$ nodes to their children are
labeled with a propositional formula over some set of Boolean events $X$, and
a probabilistic valuation $\pi$ mapping each $e\in X$ used in $D$ to an
independent probability $\pi(e)\in[0,1]$ of being true.

The semantics $\llbracket D\rrbracket$ of $D$ is obtained by extending $\pi$
to a probability distribution on valuations $\nu$ of $X$ as usual, and
defining $\nu(D)$ for $\nu$ to be $D^{\prime}$ where all $\mathsf{fie}$ nodes
are replaced by the collection of their children with edge annotation $\Phi$
such that $\nu(\Phi)=1$ (the others, and their descendants, are discarded). We
require the root to have label in $\Lambda$.

We will prove Proposition 6.1 via an encoding of
$\mathsf{PrXML}^{\mathsf{fie}}$ to pc-instances:

######  Definition D.17.

The _pc-encoding_ of a $\mathsf{PrXML}^{\mathsf{fie}}$ document
$D=(D^{\prime},\pi)$ in $\Lambda\sqcup\\{\mathsf{fie}\\}$ is the pc-instance
$J_{D}=(J^{\prime}_{D},\pi^{\prime})$ with same events, $\pi^{\prime}=\pi$,
and where the c-instance $J^{\prime}_{D}$ is the relational encoding of
$D^{\prime}$ with the following annotations. $\mathit{NS}$\- and
$\mathit{FC}$-facts are annotated with $1$. $P_{\lambda}(n)$-facts are
annotated with the annotation $\Phi$ of the edge from the parent of $n$ to
$n$, if $\Phi$ exists, with $1$ otherwise.

######  Proposition D.3.

For any MSO query $q$ on $\Lambda$-documents, one can compute in linear time
an MSO query $q^{\prime}$ on $\sigma_{\Lambda}$ such that for any
$\mathsf{PrXML}^{\mathsf{fie}}$ XML document $D$, for any valuation $\nu$ of
$D$, letting $\nu^{\prime}$ be the corresponding valuation of $J_{D}$, we have
that $\nu(D)\models q$ iff $\nu^{\prime}(J_{D})\models q^{\prime}$.

e prove that for any valuation $\nu$ of $D$, letting $\nu^{\prime}$ be the
corresponding valuation of $J_{D}$, we have that $\nu^{\prime}(J_{D})$ is a
weak encoding of $\nu(D)$ (we see $P_{\mathsf{fie}}$ facts in
$\nu^{\prime}(J_{D})$ as if they were $P_{\det}$ facts). The result then
follows by Proposition D.2.

We first show that for any valuation $\nu$ of $D$ and corresponding valuation
$\nu^{\prime}$ of $J_{D}$, for every $\lambda\in\Lambda$, $n$ is a node of
$\nu^{\prime}(J_{D})$ that is retained in the XML document
$\nu^{\prime}(J_{D})$ is a sparse representation of iff $n$ is a node which is
retained in $\nu(D)$, with same labels. Indeed, for the forward implication,
observe that any fact $P_{\lambda}(n)$ is created for node $n$ with label
$\lambda$ in $n$, and it is retained if and only if all its regular ancestors
are retained and the annotation of its parent edge in $\nu(D)$ evaluates to
$1$; conversely, if $n$ has label $\lambda$ in $D$ then a fact
$P_{\lambda}(n)$ was created in $I$ and if $n$ is retained in $\nu(D)$ then
all the conditions on edges in the chain from $n$ to the root evaluate to $1$
so $P_{\lambda}(n)$ does hold and $n$ is retained in $\nu^{\prime}(J_{D})$.

We further know that by construction relations $\mathit{FC}$ and $\mathit{NS}$
correspond to the first-child and next-sibling relations in $D$ no matter the
valuation.

So we deduce that $J_{D}$ is the relational encoding of the XML document
obtained from $D$ by replacing all nodes not kept in $\nu(D)$ by $\bot$ nodes,
and removing all edge annotations.

Observe that in this definition of pc-encoding, it is _not_ the case that the
possible worlds of $J_{D}$ are the relational encodings of the possible worlds
of $D$. For instance, the $\mathsf{fie}$ nodes are retained as is, and
$\mathit{FC}$\- and $\mathit{NS}$-facts are always retained even if the
corresponding nodes are dropped. The following example shows that it would not
be reasonable to ensure such a strong property:

######  Example D.1.

Consider an $\mathsf{fie}$ node with $k$ children $n_{1},\ldots,n_{k}$, all
annotated with independent events with probability $1/2$. In a straightforward
attempt to encode this node and its descendants to a pc-instance $J$ (or even
to a pcc-instance $J$), we would create one domain element $e_{i}$ for each of
the $n_{i}$. But then we would need to account for the fact that, as any pair
$n_{i},n_{j}$ may be retained individually, the fact
$\mathit{NS}(e_{i},e_{j})$ would need to occur in a possible world of $J$, and
thus would also occur in $J$. So this naïve attempt to ensure that the
possible worlds of $J$ are exactly the relational encodings of the possible
worlds of $D$ leads to a pcc-instance of quadratic size and linear treewidth.

#### Tractability for $\mathsf{PrXML}^{\mathsf{fie}}$.

Of course we cannot hope that the pc-encoding of a
$\mathsf{PrXML}^{\mathsf{fie}}$ document always has constant treewidth for it
is known that for $\mathsf{PrXML}^{\mathsf{fie}}$, evaluating MSO queries is
almost always $\\#P$-hard ([kimelfeld2008query], Theorem 5.2). A first notion
of tractability for a $\mathsf{PrXML}^{\mathsf{fie}}$ document $D$ is the
treewidth (following Definition D.8) of the pc-encoding of $D$. Indeed,
Proposition D.3 and Theorem D.3 imply the following:

######  Corollary D.2.

For $\mathsf{PrXML}^{\mathsf{fie}}$ documents with bounded-treewidth pc-
encoding, the MSO probabilistic query evaluation problem can be solved in ra-
linear time data complexity.

The condition on event scopes is a simpler sufficient condition for
tractability. We give its formal definition:

######  Definition D.18.

Consider a $\mathsf{PrXML}^{\mathsf{fie}}$ document $D$ with event set $X$ and
its LCRS representation $D^{\prime}$. We say that an event $e\in X$ _occurs_
in a node $n$ of $D^{\prime}$ if $e$ occurs in the annotation of the edge from
the parent of $n$ to $n$. For every $e\in X$, let $D^{\prime}_{e}$ be the
smallest connected subtree of $D^{\prime}$ that covers all nodes where $e$
occurs. The _event scope_ $S(n)$ of a node $n\in D^{\prime}$ is $\\{e\in X\mid
n\in D^{\prime}_{e}\\}$. The _event scope width_ of $D$ is
$w_{\mathrm{s}}(D)\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\max_{n\in
D}\left|S(n)\right|$.

We are now ready to prove the result on XML element scopes:

######  Proposition D.4.

For any $\mathsf{PrXML}^{\mathsf{fie}}$ document $D$, we have
$0pt(J_{D})\leqslant w_{\mathrm{s}}(D)+1$.

e show how to build a tree decomposition of the relational encoding of $J_{D}$
from the event scopes. Consider the tree decomposition $T$ of $I_{D}$ that is
isomorphic to a LCRS encoding $D^{\prime}$ of $D$: the root node of
$D^{\prime}$ is coded to an empty bag, and each node $n$ of the LCRS encoding
with parent $n^{\prime}$ is coded to $\\{n^{\prime},n\\}$.

We now add to $T$, for each bag $b$ corresponding to a node $n$, the events of
$S(n)$. It is clear that $T$ is of the prescribed width and that the
occurrences of all nodes and events are connected subtrees.

We now argue that it is a tree decomposition of the relational encoding of
$J_{D}$, but this is easily seen: it covers all $\mathit{NS}$\- and
$\mathit{FC}$\- facts represented in $J_{D}$, and covers all occurrences and
co-occurrences by construction of the scopes.

This implies Proposition 6.1 because of Corollary D.2.

#### Tractability of $\mathsf{PrXML}^{\mathsf{mux,ind}}$.

We now introduce the definitions and proofs for the local model,
$\mathsf{PrXML}^{\mathsf{mux,ind}}$.

######  Definition D.19.

A $\mathsf{PrXML}^{\mathsf{mux,ind}}$ probabilistic document is an XML
document $D$ over $\Lambda\sqcup\\{\mathsf{ind},\mathsf{mux}\\}$, where edges
from $\mathsf{ind}$ and $\mathsf{mux}$ nodes to their children are labeled
with a probability in $[0,1]$, the annotations of outgoing edges of every
$\mathsf{mux}$ node summing to $\leqslant 1$.

The semantics $\llbracket D\rrbracket$ of $D$ is obtained as follows: for
every $\mathsf{ind}$ node, decide to keep or discard each child according to
the indicated probability, and replace the node by the (possibly empty)
collection of its kept children; for every $\mathsf{mux}$ node, choose one
child node to keep according to the indicated probabilities (possibly keep no
node if they sum to $<1$), and replace the $\mathsf{mux}$ node by the chosen
child (or remove it if no child was chosen). All probabilistic choices are
performed independently. When a node is not kept, its descendants are also
discarded. We require the root to have label in $\Lambda$.

Observe that in $\mathsf{PrXML}^{\mathsf{mux,ind}}$ all probabilistic choices
are “local”, in a similar fashion to the tuple-independent (TID) and BID
probabilistic relational formalisms. As we show later, this helps ensure the
tractability of query evaluation.

We use Corollary D.2 to show the tractability of query evaluation on the
$\mathsf{PrXML}^{\mathsf{mux,ind}}$ local model, which was already proven in
[cohen2009running]. We first rewrite input documents to a simpler form:

######  Definition D.20.

Two $\mathsf{PrXML}^{\mathsf{mux,ind}}$ documents $D_{1}$ and $D_{2}$ are
equivalent if for every XML document $D$,
$\Pr\nolimits_{D_{1}}(D)=\Pr\nolimits_{D_{2}}(D)$.

######  Definition D.21.

We say that a $\mathsf{PrXML}^{\mathsf{mux,ind}}$ is in _binary form_ if it is
a full binary tree, and the sum of the outgoing probabilities of every
$\mathsf{mux}$ node is equal to $1$.

The following definition is needed to ensure linear time execution for
technical reasons:

######  Definition D.22.

A $\mathsf{PrXML}^{\mathsf{mux,ind}}$ document is _normalized_ if for every
$\mathsf{mux}$ nodes, the rational probabilities that annotate its child nodes
all share the same denominator.

######  Lemma D.7.

From any normalized $\mathsf{PrXML}^{\mathsf{mux,ind}}$ document $D$, we can
compute in linear time in $D$ an equivalent
$\mathsf{PrXML}^{\mathsf{mux,ind}}$ document $D^{\prime}$ which is in binary
form.

n this proof, for brevity, we use $\det$ nodes to refer to $\mathsf{ind}$
nodes whose child edges are all annotated with probability $1$.

First, rewrite $\mathsf{mux}$ nodes whose outgoing probabilities sum up to
$<1$ by adding a $\det$ child for them with the remaining probability. This
operation is in linear time because the corresponding number has same
denominator as other children of the $\mathsf{mux}$ node (as the document is
normalized), and the numerator is smaller than the denominator.

Next, use $\det$ nodes to rewrite the children of regular and $\mathsf{ind}$
nodes to a chain so that all regular and $\mathsf{ind}$ nodes have at most $2$
children. This only causes a constant-factor blowup of the document.

Next, rewrite $\mathsf{mux}$ nodes with more than two children to a hierarchy
of $\mathsf{mux}$ nodes in the obvious way: considering a $\mathsf{mux}$ node
$n$ with $k$ children $n_{1},\ldots,n_{k}$ and probabilities
$p_{1},\ldots,p_{k}$ summing to $1$, we replace $n$ by a hierarchy
$n_{1}^{\prime},\ldots,n_{k-1}^{\prime}$ of $\mathsf{mux}$ nodes: the children
of each $n_{i}^{\prime}$ is $n_{i}$ with probability
$\frac{p_{i}}{\sum_{j<i}p_{j}}$ and $n_{i+1}^{\prime}$ with probability
$1-\frac{p_{i}}{\sum_{j<i}p_{j}}$; except for $n_{k-1}^{\prime}$ whose
children are $n_{k-1}$ and $n_{k}$ (with the same probabilities). This
operation can be performed in linear time as the denominators of the fractions
simplify (by the assumption that the document is normalized), and the sum
operations work on operands and results which are smaller than the numerator.

Now, replace $\mathsf{mux}$ nodes with $<2$ children by $\mathsf{ind}$ nodes
(the probabilities are unchanged).

Last, add $\det$ children to nodes so that the degree of every node is either
$2$ or $0$.

This process can be performed in linear time and that the resulting document
is in binary form; equivalence has been maintained through all steps.

Now, we can show:

######  Proposition D.5.

For any $\mathsf{PrXML}^{\mathsf{mux,ind}}$ document $D$ in binary form, one
can compute in linear time an equivalent $\mathsf{PrXML}^{\mathsf{fie}}$
document whose scopes have size $\leqslant 1$.

or every $\mathsf{ind}$ node $n$ with two children $n_{1}$ and $n_{2}$ with
probabilities $p_{1}$ and $p_{2}$, introduce two fresh events
$e_{n}^{\mathsf{ind},1}$ and $e_{n}^{\mathsf{ind},2}$ with probabilities
$p_{1}$ and $p_{2}$, and replace $n$ by a $\mathsf{fie}$ node so that its
first and second outgoing edges are annotated with $e_{n}^{\mathsf{ind},1}$
and $e_{n}^{\mathsf{ind},2}$.

Likewise, for every $\mathsf{mux}$ node $n$ with two children $n_{1}$ and
$n_{2}$ with probabilities $p$ and $1-p$, introduce a fresh event
$e_{n}^{\mathsf{mux}}$ with probability $p$ and replace $n$ by a
$\mathsf{fie}$ node so that its first and second outgoing edges are annotated
with $e_{n}^{\mathsf{mux}}$ and $\neg e_{n}^{\mathsf{mux}}$.

It is immediate that the resulting document $D^{\prime}$ is equivalent to $D$.
Now, consider the scope of any node of this document. Only one event occurs in
this node, and the only events that occur more than one time in the document
occur exactly twice, on the edges of two direct sibling nodes, so they never
occur in the scope of any other node. Hence all scopes in $D$ have size
$\leqslant 1$.

From this, given that $\mathsf{PrXML}^{\mathsf{mux,ind}}$ document can be
normalized in ra-linear time, we deduce the tractability of MSO query
evaluation on $\mathsf{PrXML}^{\mathsf{mux,ind}}$, as claimed in the main
text: relaxtheoremrp[6.1 relaxcohen2009running]relaxrelaxtheoremrp

###  D.3 BID instances

Following [barbara1992management, re2007materialized], we define:

######  Definition D.23.

A _BID instance_ $I$ is a relational instance with each relation partitioned
into _key_ and _value_ positions. For each valuation of the key positions, all
matching facts (that form a _block_) are mutually exclusive, each has a
probability $>0$ and the probabilities of the block sum to $\leqslant 1$. The
semantics is to keep, independently between blocks, one fact at random in each
block, according to the indicated probabilities (or possibly no fact if
probabilities sum to $<1$).

To ensure ra-linear time complexity, we assume that BID instances are given
with facts regrouped per blocks; otherwise our bounds are PTIME as we first
need to sort the facts.

######  Definition D.24.

We define the _treewidth_ $0pt(I)$ of a BID instance $I$ as that of the
underlying relational instance, forgetting about the probabilities.

We show the tractability of MSO query evaluation on BID through Theorem D.1
and Corollary D.1, using the following result:

######  Lemma D.8.

For any fixed $k\in\mathbb{N}^{*}$, given a BID instance $J$ with
$0pt(J)\leqslant k$, we can compute in ra-linear time an equivalent pcc-
instance $J^{\prime}$ where $0pt(J^{\prime})$ depends only on $k$.

However, the proof of this result is non-trivial. By an encoding to pc-
instances, it is straightforward to show the result if we assume that the size
of each block is bounded by a constant. But otherwise, we need to build a
decision circuit for which value to pick for each key; we do so in a tree-like
fashion following a decomposition of the BID instance.

ix $k$ and $J$. First, compute in linear time a tree decomposition $T$ of $J$
of width $0pt(J)\leqslant k$.

Without loss of generality, we can assume that probabilities within each block
of $J$ are rationals with the same denominator (if this is not the case, we
normalize these probabilities in ra-linear time).

As in the proof of Lemma B.1, we can assume that every fact of $J$ has been
assigned to a bag of $T$ where it is covered (i.e., $F=R(\mathbf{a})$ with
$\mathbf{a}\subseteq\operatorname{dom}(b)$ for $b$ the covering bag).
Actually, still in the spirit of the proof of Lemma B.1, we can modify the
decomposition $T$ by copying nodes to create chains, so that we can assume
that at most one fact is assigned to each bag. This preprocessing can be
performed in linear time. For every fact $F$ of $J$ we let $\beta(F)$ be the
bag of $T$ to which fact $F$ was assigned.

We compute the pcc-instance $J^{\prime}=(J,C,\varphi)$ by building $C$ and
$\varphi$ and a tree decomposition $T^{\prime}$ for $J^{\prime}$ with same
skeleton as $T$, which is initialized as a copy of $T$. We add the gates of
$C$ to $T^{\prime}$ to turn it into a tree decomposition of $J^{\prime}$.

Let $\mathcal{B}$ be the set of blocks: a key $\mathbf{a}\in\mathcal{B}$ is a
pair of a relation symbol and a tuple that is a key in $J$ for that relation.
We write $J_{\mathbf{a}}$ to refer to $J$ restricted to the facts of block
$\mathbf{a}$; and $\left|I_{\mathbf{a}}\right|$ is the size (_not_ the number
of facts!) of this part of the instance (the size of both the facts and the
associated probabilities). It is then clear that
$\sum_{\mathbf{a}\in\mathcal{B}}\left|I_{\mathbf{a}}\right|=\left|J\right|$,
the size of the original instance.

Now, for every $\mathbf{a}\in\mathcal{B}$, consider the subset of bags
$T_{\mathbf{a}}$ of $T$ that cover $\mathbf{a}$; it is a connected subtree, as
it is the intersection for every element $a\in\mathbf{a}$ of the occurrence
subtree $T_{k}$ of this element, which are connected subtrees, and it is not
empty because the elements of $\mathbf{a}$ must occur together in some fact of
$J$ so they also do in some bag of $T$. What is more, we can precompute in
linear time the roots of all the $T_{\mathbf{a}}$ (by the same precomputation
as in the proof of Lemma B.1). It is also clear that
$\sum_{\mathbf{a}\in\mathcal{B}}\left|T_{\mathbf{a}}\right|$ is of size linear
in $\left|J\right|$, as, for fixed $\sigma$ and $k$, each bag of $T$ can only
occur in a constant number of $T_{\mathbf{a}}$.

So we prove the result in the following way: for each
$\mathbf{a}\in\mathcal{B}$, we compute in time
$O(\left|I_{\mathbf{a}}\right|+\left|T_{\mathbf{a}}\right|)$ a circuit
$C_{\mathbf{a}}$ to annotate the facts of $I_{\mathbf{a}}$ in $J^{\prime}$,
and we add the gates of $C_{\mathbf{a}}$ to $T^{\prime}$ to obtain a tree
decomposition of $J^{\prime}$ so far, making sure that we add only a constant
number of gates to each bag, and only to bags that are in $T_{\mathbf{a}}$. If
we can manage this for every $\mathbf{a}\in\mathcal{B}$, then the result
follows, as we can process the blocks in $J$ in order (as they are provided);
our final pcc-instance has width that is still constant (for each bag of $T$
can only occur in a constant number of $T_{\mathbf{a}}$); and by the arguments
about the sizes of the sums, the overall running time of the algorithm is
linear in $J$.

So in what follows we fix $\mathbf{a}\in\mathcal{B}$ and describe the
construction of $C_{\mathbf{a}}$ and the associated decomposition.

Using our preprocessed table to find the root of $T_{\mathbf{a}}$, we can
label its nodes by going over it top-down, in time linear in $T_{\mathbf{a}}$.
We now notice that for every fact $F=R(\mathbf{a},\mathbf{v})$ of
$I_{\mathbf{a}}$, the bag $\beta(F)$ covers $F$ so it must be in
$T_{\mathbf{a}}$. We write $\beta_{\mathbf{a}}$ for the restriction of the
function $\beta$ to the facts of $I_{\mathbf{a}}$.

We now say that a bag $b\in T_{\mathbf{a}}$ is an _interesting bag_ either if
it is in the image of $f_{\mathbf{a}}$ or if it is a lowest common ancestor of
some subset of bags that are in the image of $f_{\mathbf{a}}$. We now observe
that the number of interesting bags of $T_{\mathbf{a}}$ is linear in the
number of facts of $I_{\mathbf{a}}$; indeed, the interesting bags form the
internal nodes and leaves of a binary tree whose leaves must all be in the
image of $\beta_{\mathbf{a}}$, so the number of leaves is at most the number
of facts of $I_{\mathbf{a}}$, so the total number of nodes in the tree is
linear in the number of leaves.

We now define a weight function $\mathrm{w}$ on $T_{\mathbf{a}}$ by
$\mathrm{w}(b)=\pi(F)$ (the probability of $F$) for $F\in I_{\mathbf{a}}$ and
$\beta_{\mathbf{a}}(F)=b$, if any such $F$ exists; $\mathrm{w}(b)=0$
otherwise. We define bottom-up a cumulative weight function
$\mathrm{w}^{\prime}$ on $T_{\mathbf{a}}$ as $\mathrm{w}(b)$, plus
$\mathrm{w}^{\prime}(L(b))$ if $L(b)\in T_{\mathbf{a}}$, plus
$\mathrm{w}^{\prime}(R(b))$ if $R(b)\in T_{\mathbf{a}}$. For notational
convenience we also extend $\mathrm{w}^{\prime}$ to anything by saying that
$\mathrm{w}^{\prime}(b)=0$ if $b\notin T_{\mathbf{a}}$ or $b$ does not exist.

Observe now that for a non-interesting bag $b$, $\mathrm{w}(b)$ and
$\mathrm{w}^{\prime}(b)$ can be represented either as $0$ or as a pointer to
some $\mathrm{w}(b^{\prime})$ or $\mathrm{w}^{\prime}(b^{\prime})$ for an
interesting bag $b^{\prime}$. Indeed, if $b$ is non-interesting then we must
have $\mathrm{w}(b)=0$. Now we show that if $b$ has a topmost interesting
descendant $b^{\prime}$ then it is unique: indeed, the lowest common ancestor
of two interesting descendants of $b$ is a descendant of $b$ and it is also
interesting, so there is a unique topmost one. Now this means that either
$b^{\prime}$ does not exist and $\mathrm{w}^{\prime}(b)=0$, or it does exist
and all descendants of $b$ that are in the image of $\beta_{\mathbf{a}}$ are
descendants of $b^{\prime}$, so that
$\mathrm{w}^{\prime}(b)=\mathrm{w}^{\prime}(b^{\prime})$ and we can just make
$\mathrm{w}^{\prime}(b)$ a pointer to $\mathrm{w}^{\prime}(b^{\prime})$.

Now this justifies that we can compute $\mathrm{w}$ and $\mathrm{w}^{\prime}$
bottom-up in linear time in
$\left|T_{\mathbf{a}}\right|+\left|I_{\mathbf{a}}\right|$: observe that we are
working on rationals with the same denominator, so the sums that we perform
are sums of integers, whose size always remains less than the common
denominator; as there is a number of interesting bags which is linear in the
number of facts of $I_{\mathbf{a}}$, and those are the only nodes for which a
value (whose size is that of the probabilities in $I_{\mathbf{a}}$) actually
needs to be computed and written, the computation is performed in time
$O(\left|T_{\mathbf{a}}\right|+\left|I_{\mathbf{a}}\right|)$ overall.

We now justify that we can encode $T_{\mathbf{a}}$ to a circuit with the
correct probabilities. For each bag $b\in T_{\mathbf{a}}$, we create a gate
$g_{b}^{\mathrm{i}}$; for the root bag $b$ it is an input gate with
probability $\mathrm{w}^{\prime}(b)$; for other bags it is a gate whose value
is defined by the parent bag. Intuitively, $g_{b}^{\mathrm{i}}$ describes
whether to choose a fact from $F_{\mathbf{a}}$ within the subtree rooted at
$b$.

For every interesting bag $b$, writing $\mathrm{w}^{\prime}(b)=k^{\prime}/d$
and $\mathrm{w}(b)=k/d$ with $d$ the common denominator, create one input gate
$g_{b}^{\mathrm{h}}$ with probability
$\frac{1}{\mathrm{w}^{\prime}(b)}\mathrm{w}(b)=k/k^{\prime}$, and one gate
$g_{b}^{\mathrm{h}\wedge}$ which is the AND of $g_{b}^{\mathrm{h}}$ and
$g_{b}^{\mathrm{i}}$. Intuitively, this gate describes whether to generate the
fact assigned at this node, if any. If there is such a fact, set its image by
$\varphi$ to be $g_{b}^{\mathrm{h}\wedge}$. Now if
$\mathrm{w}^{\prime}(b)>\mathrm{w}(b)$ (intuitively: there is still the
possibility to generate fact at child nodes), we create one input gate
$g_{b}^{\leftrightarrow}$ which has probability
$\frac{1}{\mathrm{w}^{\prime}(b)-\mathrm{w}(b)}\mathrm{w}^{\prime}(L(b))$.
Once again, this probability simplifies to a rational whose numerator and
denominator are $<d$. We create a gate $g_{b}^{\text{L}}$ to be
$g_{b}^{\mathrm{i}}\wedge\neg g_{b}^{\mathrm{h}}\wedge
g_{b}^{\leftrightarrow}$ (creating a constant number of intermediate gates as
necessary), and $g_{b}^{\text{R}}$ to be $g_{b}^{\mathrm{i}}\wedge\neg
g_{b}^{\mathrm{h}}\wedge\neg g_{b}^{\leftrightarrow}$, setting them to be
$g_{L(b)}^{\mathrm{i}}$ and $g_{R(b)}^{\mathrm{i}}$ where applicable (i.e., if
$L(b)$ and $R(b)$ exist and are in $T_{\mathbf{a}}$).

By contrast, non-interesting bags $b$ just set $g_{L(b)}^{\mathrm{i}}$ and
$g_{R(b)}^{\mathrm{i}}$ (where applicable) to be $g_{b}^{\mathrm{i}}$, with no
input gates.

We now observe that by construction the resulting circuit has a tree
decomposition that is compatible with $T$, so that we can add its events to
$T^{\prime}$ and only add constant width to the nodes of $T_{\mathbf{a}}$ as
required. It is also easy to see that the circuit gives the correct
distribution on the facts of $F_{\mathbf{a}}$, with the following invariant:
for any bag $b\in T_{\mathbf{a}}$, the probability that $g^{\mathrm{i}}_{b}$
is $1$ is $\mathrm{w}^{\prime}(b)$, and $g^{\mathrm{h}\wedge}_{b}$,
$g^{\text{L}}_{b}$ and $g^{\text{R}}_{b}$ are either all $0$ if
$g^{\mathrm{i}}_{b}$ is $0$ or, if $g^{\mathrm{i}}_{b}$ is $1$, exactly one is
true and they respectively have marginal probabilities $\mathrm{w}(b)$,
$\mathrm{w}^{\prime}(L(b))$, and $\mathrm{w}^{\prime}(R(b))$. Now the circuit
construction is once again in time
$O(\left|I_{\mathbf{a}}\right|+\left|T_{\mathbf{a}}\right|)$, noting that
interesting nodes are the only nodes where numbers need to be computed and
written; and we have performed the entire computation in time
$O(\left|I_{\mathbf{a}}\right|+\left|T_{\mathbf{a}}\right|)$, so the overall
result is proven.

Combining Lemma D.8 and Theorem D.1, we can conclude:
relaxtheoremrp[6.2]relaxrelaxtheoremrp

###  D.4 Counting

relaxtheoremrp[6.3 relaxarnborg1991easy]relaxrelaxtheoremrp relaxoldproof Let
$k\in\mathbb{N}$. Let $q(\mathbf{x})$ be the MSO query. We rewrite it to the
following query:
$q^{\prime}:\exists\mathbf{x}\bigwedge_{x\in\mathbf{x}}P_{x}(x)\wedge
q(\mathbf{x})$, where the $P_{x}$ are fresh unary predicates. Consider an
input instance $I$ of width $\leqslant k$, and expand it to a BID instance
$I^{\prime}$ by setting existing relations to be trivial BID tables (i.e., all
attributes of the relation are keys, and all facts have probability $1$) and
adding tables $P_{x}$ for every $x\in\mathbf{x}$ with one attribute, with the
empty set as key, and with facts $P_{x}(a)$ for all
$a\in\operatorname{dom}(I)$, with probability
$1/\left|\operatorname{dom}(I)\right|$. This rewriting can clearly be
performed in ra-linear time, and if $I$ has treewidth $\leqslant k$ then so
does $I^{\prime}$. Intuitively, the possible worlds of $I^{\prime}$ are all
the possible ways of extending $I$ with facts $P_{x}(a)$ for $x\in\mathbf{x}$
and $a\in\operatorname{dom}(I)$, with only one fact $P_{x}(a)$ for every
$x\in\mathbf{x}$, and each possible world has probability
$1/\left|\operatorname{dom}(I)\right|^{\left|\mathbf{x}\right|}$.

We now make the immediate observation that for every such possible world
$I^{\prime}_{\mathbf{a}}$ of $I^{\prime}$ indexed by the
$a_{x}\in\operatorname{dom}(I)$ for $x\in\mathbf{x}$, where we add the facts
$P_{x}(a_{x})$ for $x\in\mathbf{x}$, we have $I^{\prime}_{\mathbf{a}}\models
q^{\prime}$ iff $I\models q(\mathbf{a})$. Hence, the number of matches of $q$
in $I$ is the number of possible worlds of $I^{\prime}$ where $q^{\prime}$
holds, that is, the probability of $q^{\prime}$ on $I^{\prime}$ multiplied by
$M\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\left|\operatorname{dom}(I)\right|^{\left|\mathbf{x}\right|}$.

We conclude by Theorem 6.2 that we can compute this probability in ra-linear
time in $I^{\prime}$, that is, in $I$, and we compute the count from the
probability by multiplying by $M$ in ra-linear time, proving the result.
relaxoldproof

## REFERENCES FOR THE APPENDIX