LTCI, Télécom Paris, Institut Polytechnique de Paris,
Francehttps://orcid.org/0000-0002-7977-4441 Technion – Israel Institute of
Technology Antoine Amarilli and Benny Kimelfeld [500]Theory of computation
Database query processing and optimization (theory)

# Uniform Reliability of Self-Join-Free Conjunctive Queries

Antoine Amarilli  Benny Kimelfeld

###### Abstract

The _reliability_ of a Boolean Conjunctive Query (CQ) over a tuple-independent
probabilistic database is the probability that the CQ is satisfied when the
tuples of the database are sampled one by one, independently, with their
associated probability. For queries without self-joins (repeated relation
symbols), the data complexity of this problem is fully characterized in a
known dichotomy: reliability can be computed in polynomial time for
_hierarchical_ queries, and is #P-hard for non-hierarchical queries.
Hierarchical queries also characterize the tractability of queries for other
tasks: having read-once lineage formulas, supporting insertion/deletion
updates to the database in constant time, and having a tractable computation
of tuples’ Shapley and Banzhaf values.

In this work, we investigate a fundamental counting problem for CQs without
self-joins: how many sets of facts from the input database satisfy the query?
This is a simpler, _uniform_ variant of the query reliability problem, where
the probability of every tuple is required to be $1/2$. Of course, for
hierarchical queries, uniform reliability is in polynomial time, like the
reliability problem. However, it is an open question whether being
hierarchical is necessary for the uniform reliability problem to be in
polynomial time. In fact, the complexity of the problem has been unknown even
for the simplest non-hierarchical CQs without self-joins.

We solve this open question by showing that uniform reliability is #P-complete
for every non-hierarchical CQ without self-joins. Hence, we establish that
being hierarchical also characterizes the tractability of unweighted counting
of the satisfying tuple subsets. We also consider the generalization to query
reliability where all tuples _of the same relation_ have the same probability,
and give preliminary results on the complexity of this problem.

###### keywords:

Hierarchical conjunctive queries, query reliability, tuple-independent
database, counting problems, #P-hardness

##  1 Introduction

_Probabilistic databases_ [DBLP:series/synthesis/2011Suciu] extend the usual
model of relational databases by allowing database facts to be uncertain, in
order to model noisy and imprecise data. The evaluation of a Boolean query $Q$
over a probabilistic database $D$ is then the task of computing the
probability that $Q$ is true under the probability distribution over possible
worlds given by $D$. This computational task has been considered by Grädel,
Gurevich and Hirsch [DBLP:conf/pods/GradelGH98] as a special case of computing
the _reliability_ of a query in a model which is nowadays known as _Tuple-
Independent probabilistic Databases_ (TIDs) [DBLP:series/synthesis/2011Suciu,
dalvi2007efficient]. In a TID, every fact is associated with a probability of
being true, and the truth of every fact is an independent random event. While
the TID model is rather weak, query evaluation over TIDs can also be used for
probabilistic inference over models with correlations among facts, such as
Markov Logic Networks [DBLP:journals/pvldb/GribkoffS16,
DBLP:journals/pvldb/JhaS12]. Hence, studying the complexity of query
evaluation on TIDs is the first step towards understanding which forms of
probabilistic data can be tractably queried.

To this end, Grädel et al. [DBLP:conf/pods/GradelGH98] showed the first
Boolean Conjunctive Query (referred to simply as a _CQ_ hereafter) for which
query evaluation is #P-hard on TIDs. Later, Dalvi and Suciu
[dalvi2007efficient] established a dichotomy on the complexity of evaluating
CQs without self-joins (i.e., without repeated relation symbols) over TIDs: if
the CQ is _safe_ (or _hierarchical_ [DBLP:journals/cacm/DalviRS09,
DBLP:series/synthesis/2011Suciu] as we explain next), the problem is solvable
in polynomial time; otherwise, the problem is #P-hard. (This result was later
extended to the class of all CQs and unions of CQs [dalvi2012dichotomy].)

This class of _hierarchical_ CQs is defined by requiring that, for every two
variables $x$ and $y$, the sets of query atoms that feature $x$ must contain,
be contained in, or be disjoint from, the set of atoms that feature $y$.
Interestingly, this class of hierarchical queries was then found to
characterize the tractability boundary of other query evaluation tasks for CQs
without self-joins, over databases without probabilities (and under
conventional complexity assumptions). Olteanu and Huang
[DBLP:conf/sum/OlteanuH08] showed that a query is hierarchical if and only if,
for every database, the _lineage_ of the query is a read-once formula.
Livshits et al. [DBLP:journals/corr/abs-1904-08679] proved that the
hierarchical CQs are precisely the ones for which we can compute various
notions of _responsibility_ of a database fact, such as the _Shapley value_
and the _causal effect_ [DBLP:conf/tapp/SalimiBSB16] (that we refer to later
on in this section). Berkholz, Keppeler and Schweikardt
[DBLP:conf/pods/BerkholzKS17] showed that the hierarchical CQs are precisely
the ones for which we can use an auxiliary data structure to update the query
answer in constant time in response to the insertion or deletion of a tuple.

In this paper, we show that the property of being hierarchical also captures
the complexity of a fundamental counting problem for CQs without self-joins:
_how many sets of facts from the input database satisfy the query?_ This
problem, which we refer to as _uniform reliability_ , is equivalent to query
evalutaion over a TID where the probability of _every_ fact is equal to $1/2$.
In particular, it follows from the aforementioned dichotomy that this problem
can be solved in polynomial time for every self-join-free hierarchical CQ $Q$.
Yet, if $Q$ is not hierarchical, it does not necessarily mean that $Q$ is
intractable already in this uniform setting. Indeed, it was not known whether
enforcing uniformity makes query evaluation on TIDs easier, and the complexity
of uniform reliability was already open for the simplest case of a non-
hierarchical CQ:
$Q_{1}\mathrel{{:}{\text{-}}}\mathsf{R}(x),\mathsf{S}(x,y),\mathsf{T}(y)$.
Indeed, the proofs of #P-hardness of Dalvi and Suciu [dalvi2007efficient]
require TIDs with probabilities different from $1/2$: they crucially use facts
with probability $1$ (i.e., a mix of certain and uncertain facts), already in
the case of $Q_{1}$. Here, we address this problem and show that the dichotomy
is also true for the uniform reliability problem. In particular, uniform
reliability is #P-complete for every non-hierarchical CQ without self-joins
(and solvable in polynomial time for every hierarchical CQ without self-
joins).

While uniform reliability is a basic combinatorial problem on CQs, and a
natural restricted case of query answering on TIDs, it also has a direct
application to quantify the impact (or responsibility) of a fact $f$ on the
result of a CQ $Q$ over ordinary (non-probabilistic) databases. One notion of
tuple impact is the aforementioned _causal effect_ , defined as the difference
between two quantities: the probability of $Q$ conditioning on the existence
of $f$, minus the probability of $Q$ conditioning on the absence of $f$
[DBLP:conf/tapp/SalimiBSB16]. This causal effect was recently shown
[DBLP:journals/corr/abs-1904-08679] to be the same as the _Banzhaf power
index_ , studied in the context of wealth distribution in cooperative game
theory [10.2307/3689345] and applied, for instance, to voting in the New York
State Courts [Grofman1979]. One notion of causal effect (with so-called
_endogenous_ facts) is defined by viewing the ordinary database as a TID where
the probability of every fact is $1/2$. Therefore, computing the causal effect
amounts to solving two variations of uniform reliability, corresponding to the
two quantities. In fact, it is easy to see that all of our results apply to
each of these two variations.

Our investigation can be viewed as a first step towards the study of problems
that lie in between uniform reliability and probabilistic query answering over
TIDs. For instance, a natural variant is when the probability of each tuple of
the database is the same, but not necessarily $1/2$. This problem can arise,
e.g., in scenarios of network reliability, where all connections are equally
important and have the same independent probability of failure. A more general
case is when the probabilities for every relation are the same, but different
relations may be associated with different probabilities. This corresponds to
data integration scenarios where every relation is a resource with a different
level of trust (e.g., enterprise data vs. Web data vs. noisy sensor data). In
this paper, we formalize this generalization and ask which combinations of CQs
and probability assignments make the problem intractable. We do not completely
answer this question, but propose preliminary results for the query $Q_{1}$
mentioned earlier: we show that some combinations of probabilities can be
easily proved hard using our main result, while others can be proved hard with
other techniques.

Uniform reliability also relates to the computation of a tuple’s _Shapley
value_ [shapley53], which has also been used in cooperative game theory and
applied to many use cases [roth1988shapley]. Livshits et al.
[DBLP:journals/corr/abs-1904-08679] have also shown that computing a tuple’s
Shapley value can be reduced to a generalized variant of uniform reliability.
Specifically, for CQs, computing the Shapley value (again for _endogenous_
facts) amounts to calculating the number of subinstances that satisfy $Q$
_and_ have precisely $m$ tuples (for a given number $m$). This generalization
of uniform reliability is tractable for every hierarchical CQ without self-
joins [DBLP:journals/corr/abs-1904-08679]. Clearly, our results here imply
that this generalization is intractable for every non-hierarchical CQ without
self-joins, allowing us to conclude that the complexity dichotomy also applies
to this generalization.

#### Related work.

As we already explained, our work is closely related to existing literature on
query evaluation over probabilistic databases, and also has connections and
possible applications to problems in computational social choice. In addition
to these, our work relates to rewriting techniques used in the case of DNF
formulas to reduce weighted model counting to unweighted model counting
[chakraborty2015weighted]. Nevertheless, the results and techniques for this
problem are not directly applicable to ours, since model counting for CQs
translates to DNFs of a very specific shape (namely, those that can be
obtained as the lineage of the query).

Another superficially related problem is that of _symmetric model counting_
[beame2015symmetric]. This is a variant of uniform reliability where each
relation consists of _all possible tuples_ over the corresponding domain, and
so each fact carries the same weight: these assumptions are often helpful to
make model counting tractable. However, our problem is very different: we do
not deal with symmetric databases, but rather with arbitrary databases where
all facts of the database (_not_ all possible facts over the domain) have the
same uniform probability of $1/2$. As we show, this weaker assumption does not
suffice to make uniform reliability tractable.

There is a closer connection to existing dichotomy results on counting
_database repairs_ [DBLP:journals/jcss/MaslowskiW13,
DBLP:conf/icdt/MaslowskiW14]. In this setting, the input database may violate
the primary key constraints of the relations, and a repair is obtained by
selecting one fact from every collection of conflicting facts (i.e., distinct
facts that agree on the key): the _repair counting problem_ asks how many such
repairs satisfy a given CQ. In particular, it can easily be shown that for a
CQ $Q$, there is a reduction from the uniform reliability of $Q$ to repair
counting of another CQ $Q^{\prime}$. Yet, this reduction can only explain
cases of tractability (namely, where $Q$ is hierarchical) which, as explained
earlier, are already known. We do not see how to design a reduction in the
other direction, from repair counting to uniform reliability, in order to show
our hardness result.

Finally, our work relates to the study of the Constraint Satisfaction Problem
(CSP). However, there are two key differences. First, we study query
evaluation in terms of homomorphisms _from_ a fixed CQ, whereas the standard
CSP phrasing talks about homomorphisms _to_ a given template. Second, the
standard counting variant of CSP (namely, #CSP), for which Bulatov has proved
a dichotomy [DBLP:journals/jacm/Bulatov13], is about counting _the number of
homomorphisms_ , whereas we count _the number of subinstances_ for which a
homomorphism exists. For these reasons, it is not clear how results on CSP and
#CSP can be helpful towards our main result.

#### Organization.

We give preliminaries in Section 2. In Section 3, we formally state the
studied problem and main result, that is, the dichotomy on the complexity of
uniform reliability for CQs without self-joins. We prove this result in
Sections 4–6. We discuss a generalization to arbitrary uniform probabilities
in Section 7, and conclude in Section 8.

##  2 Preliminaries

We begin with some preliminary definitions and notation that we use throughout
the paper.

#### Databases.

A (relational) _schema_ $\mathbf{S}$ is a collection of _relation symbols_
with each relation symbol $\rho$ in $\mathbf{S}$ having an associated arity.
We assume a countably infinite set $\mathsf{Const}$ of _constants_ that are
used as database values. A _fact_ over $\mathbf{S}$ is an expression of the
form $\rho(c_{1},\dots,c_{k})$ where $\rho$ is a relation symbol of
$\mathbf{S}$, where $k$ is the arity of $\rho$, and where $c_{1},\dots,c_{k}$
are values of $\mathsf{Const}$. An _instance_ $I$ over $\mathbf{S}$ is a
finite set of facts. In particular, we say that an instance $J$ is a
_subinstance_ of an instance $I$ if we have $J\subseteq I$.

#### Conjunctive queries.

This paper focuses on queries in the form of a Boolean Conjunctive Query,
which we refer to simply as a _CQ_. Formally, a CQ $Q$ over the schema
$\mathbf{S}$ is a relational query definable by a first-order formula of the
form $\exists\vec{x}\theta(\vec{x})$ where $\theta$ is a conjunction of atomic
formulas. Equivalently, a CQ is a formula of the form
$Q\mathrel{{:}{\text{-}}}\rho_{1}(\vec{\tau}_{1}),\dots,\rho_{n}(\vec{\tau}_{m})$
where each $\rho_{i}(\vec{\tau}_{i})$ is an _atom_ of $Q$, formed of a
relation symbol of $\mathbf{S}$ and of a tuple $\vec{\tau}_{i}$ of
(existentially quantified) variables and constants, with the same arity as
$\rho_{i}$. In the context of a CQ $Q$, we omit the schema $\mathbf{S}$ and
implicitly assume that $\mathbf{S}$ consists of the relation symbols that
occur in $Q$ (with the arities that they have in $Q$); in that case, we may
also refer to an instance $I$ over $\mathbf{S}$ as an instance _over $Q$_. We
write $I\models Q$ to state that the instance $I$ satisfies $Q$.

A _self-join_ in a CQ $Q$ is a pair of distinct atoms over the same relation
symbol. For example, in
$Q\mathrel{{:}{\text{-}}}\mathsf{R}(x,y),\mathsf{S}(x),\mathsf{R}(y,z)$, the
first and third atoms constitute a self-join. Our analysis in this paper is
restricted to CQs _without self-joins_ , that we also call _self-join-free_.

Let $Q$ be a CQ. For each variable $x$ of $Q$, we denote by
$\mathrm{atoms}(x)$ the set of atoms $\rho_{i}(\vec{\tau}_{i})$ of $Q$ where
$x$ occurs. We say that $Q$ is _hierarchical_ [dalvi2007efficient] if for all
variables $x$ and $x^{\prime}$ one of the following three relations hold:
$\mathrm{atoms}(x)\subseteq\mathrm{atoms}(x^{\prime})$,
$\mathrm{atoms}(x^{\prime})\subseteq\mathrm{atoms}(x)$, or
$\mathrm{atoms}(x)\cap\mathrm{atoms}(x^{\prime})=\emptyset$. The simplest non-
hierarchical CQ is $Q_{1}$ (see introduction):

$Q_{1}\mathrel{{:}{\text{-}}}\mathsf{R}(x),\mathsf{S}(x,y),\mathsf{T}(y)$ (1)

#### Probabilistic query evaluation.

The problem of _probabilistic query evaluation_ over tuple-independent
databases [DBLP:series/synthesis/2011Suciu] is defined as follows.

######  Definition 2.1.

The problem of _probabilistic query evaluation_ (or PQE) for a CQ $Q$, denoted
$\mathsf{PQE}(Q)$, is that of computing, given an instance $I$ over $Q$ and an
assignment $\pi:I\rightarrow[0,1]$ of a probability $\pi(f)$ to every fact
$f$, the probability that $Q$ is true, namely:

We again study the _data complexity_ of this problem, and we assume that the
probabilities of the instance $I$ are rational numbers represented by their
integer numerator and denominator.

PQE was first studied by Grädel, Gurevich and Hirsch
[DBLP:conf/pods/GradelGH98] as _query reliability_ (which they also generalize
beyond Boolean queries). They showed a Boolean CQ $Q$ with self-joins such
that the reliability of $Q$ is #P-hard to compute. Dalvi and Suciu
[dalvi2007efficient, dalvi2012dichotomy] then studied the PQE problem,
culminating in their dichotomy for the complexity of PQE on unions of
conjunctive queries with self-joins [dalvi2012dichotomy]. In this paper, we
only consider their earlier study of CQs without self-joins
[dalvi2007efficient]. They characterize, under conventional complexity
assumptions, the self-join-free CQs where PQE is solvable in PTIME. They state
the result in terms of safe query plans (“safe CQs”), but the term
“hierarchical” was adopted in later publications
[DBLP:journals/cacm/DalviRS09, DBLP:series/synthesis/2011Suciu]:

######  Theorem 2.2.

 _[ dalvi2007efficient]_ Let $Q$ be a CQ without self-joins. If $Q$ is
hierarchical, then $\mathsf{PQE}(Q)$ is solvable in polynomial time.
Otherwise, $\mathsf{PQE}(Q)$ is #P-hard.

Here, #P is the complexity class of problems that count witnesses of an NP-
relation (e.g., satisfying assignments of a logical formula, vertex covers of
a graph). A function $F$ is #P-hard if every function in #P has a PTIME
_Turing reduction_ (or _Cook reduction_) to $F$.

#### Uniform reliability.

We focus on the uniform variant of the reliability of a query, or PQE, where
the probability of every fact is $1/2$. This problem is the same as counting
the subinstances that satisfy the query (up to division/multiplication by
$2^{n}$ where $n$ is the number of facts in the database). More formally, let
$Q$ be a CQ and let $I$ be an instance. We denote by
$\mathrm{Mod}(Q,I)\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\mathord{\\{J\subseteq
I\mid J\models Q\\}}$. the set of all subinstances $J$ of $I$ that satisfy
$Q$.

######  Definition 2.3.

The problem of _uniform reliability_ for a CQ $Q$, denoted $\mathsf{UR}(Q)$,
is that of determining, given an instance $I$ over $Q$, how many subinstances
of $I$ satisfy $Q$. In other words, $\mathsf{UR}(Q)$ is the problem of
computing $\left|{\mathrm{Mod}(Q,I)}\right|$, given $I$. We study the _data
complexity_ of this problem, i.e., $Q$ is fixed and the complexity is a
function of the input $I$.

##  3 Problem Statement and Main Result

Let $Q$ be a CQ without self-joins. It follows from Theorem 2.2 that, if $Q$
is hierarchical, then $\mathsf{UR}(Q)$ is solvable in polynomial time. Indeed,
there is a straightforward reduction from $\mathsf{UR}(Q)$ to
$\mathsf{PQE}(Q)$: given an instance $I$ for $Q$, let $\pi:I\rightarrow[0,1]$
be the function that assigns to every fact of $I$ the probability
$\pi(f)=0.5$. Then we have $[\left|{\mathrm{Mod}(Q,I)}\right|=2^{|I|}\times$
because every subset of $Q$ has the same probability, namely $2^{-|I|}$.

However, the other direction is not evident. If $Q$ is non-hierarchical, we
know that $\mathsf{PQE}(Q)$ is #P-hard, but we do not know whether the same is
true of $\mathsf{UR}(Q)$. Indeed, this does not follow from Theorem 2.2 (as
uniform reliability is a restriction of PQE), and it does not follow from the
proof of the theorem either. Specifically, the reduction that Dalvi and Suciu
[dalvi2007efficient] used to show hardness consists of two steps.

  1. 1.

Proving that $\mathsf{PQE}(Q_{1})$ is #P-hard (where $Q_{1}$ is defined in
(1)).

  2. 2.

Constructing a Turing reduction from $\mathsf{PQE}(Q_{1})$ to
$\mathsf{PQE}(Q)$ for every non-hierarchical CQ $Q$ without self-joins.

In both steps, the constructed instances $I$ consist of facts with two
probabilities: $0.5$ and $1$ (i.e., _certain facts_). If all facts had
probability $0.5$, then we would get a reduction to our $\mathsf{UR}(Q)$
problem. However, the proof crucially relies on certain facts, and we do not
see how to modify it to give probability $0.5$ to all facts. This is true for
both steps. Even for the first step, the complexity of $\mathsf{UR}(Q_{1})$
has been unknown so far. For the second step, it is not at all clear how to
reduce from $\mathsf{UR}(Q_{1})$ to $\mathsf{UR}(Q)$, even if
$\mathsf{UR}(Q_{1})$ is proved to be #P-hard.

In this paper, we resolve the question and prove that $\mathsf{UR}(Q)$ is
#P-complete whenever $Q$ is a non-hierarchical CQ without self-joins. Hence,
we establish that the dichotomy of Theorem 2.2 also holds for uniform
reliability. Our main result is:

######  Theorem 3.1.

Let $Q$ be a CQ without self-joins. If $Q$ is hierarchical, then
$\mathsf{UR}(Q)$ is solvable in polynomial time. Otherwise, $\mathsf{UR}(Q)$
is #P-complete.

As we explained, the tractability for hierarchical queries follows from
Theorem 2.2, and the membership in #P is straightforward. Thus, our technical
contribution is to show:

######  Theorem 3.2.

Let $Q$ be a non-hierarchical CQ without self-joins. Then $\mathsf{UR}(Q)$ is
#P-hard.

A preliminary observation is that this claim follows from the hardness of a
specific family of non-hierarchical self-join-free CQs. We call them the
_$Q_{r,s,t}$ -queries_, and they have the following form for some natural
numbers $r,s,t>0$:

$Q_{r,s,t}\mathrel{{:}{\text{-}}}\mathsf{R}_{1}(x),\dots,\mathsf{R}_{r}(x),\mathsf{S}_{1}(x,y),\dots,\mathsf{S}_{s}(x,y),\mathsf{T}_{1}(y),\dots,\mathsf{T}_{t}(y)$
(2)

Note that $Q_{1,1,1}$ is the same as $Q_{1}$ (Equation (1)). We can show for
non-hierarchical queries $Q$ that $\mathsf{UR}(Q)$ has a reduction from
$\mathsf{UR}(Q_{r,s,t})$ for some $r,s,t>0$. Formally:

######  Proposition 3.3.

prp:reducerst Let $Q$ be a non-hierarchical CQ without self-joins. We can
compute natural numbers $r,s,t>0$ such that there is a Turing reduction from
$\mathsf{UR}(Q_{r,s,t})$ to $\mathsf{UR}(Q)$.

###### Proof sketch.

As $Q$ is non-hierarchical, we can find two variables $x$ and $y$ such that
the sets $\mathrm{atoms}(x)$ and $\mathrm{atoms}(y)$ intersect and are
incomparable. We take
$r\colonequals\left|{\mathrm{atoms}(x)\setminus\mathrm{atoms}(y)}\right|$,
$s\colonequals\left|{\mathrm{atoms}(x)\cap\mathrm{atoms}(y)}\right|$, and
$t\colonequals\left|{\mathrm{atoms}(y)\setminus\mathrm{atoms}(x)}\right|$. We
then reduce from an instance of $\mathsf{UR}(Q_{r,s,t})$ to an instance of
$\mathsf{UR}(Q)$ by replacing all facts to facts of the relations of
$\mathrm{atoms}(x)\cup\mathrm{atoms}(y)$ (using some common fresh element for
the positions of the variables that are not $x$ or $y$), and creating one
“extra fact” for each atom not in $\mathrm{atoms}(x)\cup\mathrm{atoms}(y)$.
The correctness of the Turing reduction relies on the self-join-freeness of
$Q$. ∎

We give the complete proof of Proposition LABEL:prp:reducerst in the technical
appendix. Thanks to this proposition, it suffices to show hardness for the
$Q_{r,s,t}$-queries, namely:

######  Theorem 3.4.

For all $r,s,t>0$, the problem $\mathsf{UR}(Q_{r,s,t})$ is #P-hard.

This implies in particular that $\mathsf{UR}(Q_{1})$ is #P-hard. We prove this
theorem in Section 4–6, and then investigate a generalization in Section 7.

##  4 Defining the Main Reduction

In this section and the two next ones, we fix $r,s,t>0$, and show the
#P-hardness of $\mathsf{UR}(Q_{r,s,t})$ (Theorem 3.4). We reduce from the
#P-hard problem of counting the number of independent sets of a bipartite
graph. The input to this problem is a bipartite graph $G=(R\cup T,S)$ where
$S\subseteq R\times T$, and the goal is to calculate the number $P$ of
_independent-set pairs_ $(R^{\prime},T^{\prime})$ with $R^{\prime}\subseteq R$
and $T^{\prime}\subseteq T$, that is, pairs such that $R^{\prime}\times
T^{\prime}$ is disjoint from $S$. This problem is the same as computing the
complement of the number of satisfying assignments of a monotone partitioned
2-DNF formula, so it is indeed #P-hard [provan1983complexity].

Let us fix $G=(R\cup T,S)$ as the input to the problem. Our proof consists of
three parts. First, in the present section, we introduce several graph gadgets
and use them to build the various instances of $\mathsf{UR}(Q_{r,s,t})$ to
which we reduce. Second, in Section 5, we explain how to obtain a linear
equation system that connects the number $P$ of independent-set pairs of $G$
to the results of $\mathsf{UR}(Q_{r,s,t})$ on our instances. Last, in Section
6, we argue that the matrix of this system is invertible, so we can recover
$P$ and conclude the reduction, showing Theorem 3.4.

#### Defining the Gadgets.

We define the gadgets that we will use in the reduction as building block for
our instances of $\mathsf{UR}(Q_{r,s,t})$. Recall that $\mathsf{R}_{i}$,
$\mathsf{S}_{i}$, and $\mathsf{T}_{i}$ are the relations that define
$Q_{r,s,t}$ (see Equation (2)). For all $i$, we collectively refer to a fact
over $\mathsf{R}_{i}$, $\mathsf{S}_{i}$ and $\mathsf{T}_{i}$ as an
$\mathsf{R}_{*}$-fact, an $\mathsf{S}_{*}$-fact, and a $\mathsf{T}_{*}$-fact,
respectively. There are two types of gadgets.

  * •

The _$(a,b)$ -gadget_ is an instance with two elements $a$ and $b$, and the
following facts:

$\mathsf{R}_{1}(a),\ldots,\mathsf{R}_{r}(a),\qquad\mathsf{S}_{1}(a,b),\ldots,\mathsf{S}_{s}(a,b),\qquad\mathsf{T}_{1}(b),\ldots,\mathsf{T}_{t}(b)$

We denote by $\lambda_{\mathsf{R}}$ its number of possible worlds that violate
$Q$ when we fix the $\mathsf{R}_{*}$-facts on $a$ to be present. We easily
compute: $\lambda_{\mathsf{R}}=2^{s+t}-1$. Similarly, we denote by
$\lambda_{\mathsf{T}}$ the number of possible worlds that violate $Q$ when we
fix the $\mathsf{T}_{*}$-facts on $b$ to be present. We have:
$\lambda_{\mathsf{T}}=2^{s+r}-1$. Last, we denote by
${\bar{\lambda}}_{\mathsf{T}}=2^{s+r}$ the number of possible worlds when we
fix the $\mathsf{T}_{*}$-facts to be absent (all these possible worlds violate
$Q$), and denote by ${\bar{\lambda}}_{\mathsf{R}}=2^{s+t}$ the number of
possible worlds when we fix the $\mathsf{R}_{*}$-facts to be absent (again,
all violate $Q$).

  * •

The _$(a,b,c,d)$ -gadget_ is an instance with elements $a$, $b$, $c$, and $d$,
and the following facts:

$\displaystyle\mathsf{R}_{1}(a),\ldots,\mathsf{R}_{r}(a),\leavevmode\nobreak\
\leavevmode\nobreak\ $
$\displaystyle\mathsf{S}_{1}(a,b),\ldots,\mathsf{S}_{s}(a,b),\quad\leavevmode\nobreak\
\leavevmode\nobreak\ $
$\displaystyle\mathsf{T}_{1}(b),\ldots,\mathsf{T}_{t}(b),\quad\leavevmode\nobreak\
\leavevmode\nobreak\
\mathsf{S}_{1}(c,b),\ldots,\allowbreak\mathsf{S}_{s}(c,b),$
$\displaystyle\mathsf{R}_{1}(c),\ldots,\mathsf{R}_{r}(c),\leavevmode\nobreak\
\leavevmode\nobreak\ $
$\displaystyle\mathsf{S}_{1}(c,d),\ldots,\mathsf{S}_{s}(c,d),\quad\leavevmode\nobreak\
\leavevmode\nobreak\ $
$\displaystyle\mathsf{T}_{1}(d),\ldots,\mathsf{T}_{t}(d).$

as illustrated here:

$a$$b$$c$$d$$\mathsf{S}_{1},\ldots,\mathsf{S}_{s}$$\mathsf{S}_{1},\ldots,\mathsf{S}_{s}$$\mathsf{S}_{1},\ldots,\mathsf{S}_{s}$$\mathsf{R}_{1},\ldots,\mathsf{R}_{r}$$\mathsf{T}_{1},\ldots,\mathsf{T}_{t}$$\mathsf{R}_{1},\ldots,\mathsf{R}_{r}$$\mathsf{T}_{1},\ldots,\mathsf{T}_{t}$

We denote by $\gamma$ its number of possible worlds that violate $Q$ where we
fix the $\mathsf{R}_{*}$-facts on $a$ and the $\mathsf{T}_{*}$-facts on $d$ to
be present. We denote by $\delta_{\mathsf{R}}$ its number of possible worlds
that violate $Q$ when we fix the $\mathsf{R}_{*}$-facts on $a$ to be present
and the $\mathsf{T}_{*}$-facts on $d$ to be absent, and symmetrically denote
by $\delta_{\mathsf{T}}$ its number of possible worlds that violate $Q$ when
fixing the $\mathsf{R}_{*}$-facts on $a$ to be absent and the
$\mathsf{T}_{*}$-facts on $d$ to be present. Last, we denote by
$\delta_{\bot}$ its number of possible worlds that violate $Q$ when we fix the
$\mathsf{R}_{*}$-facts on $a$ and the $\mathsf{T}_{*}$-facts on $d$ to be
absent. We will study the quantities $\gamma$, $\delta_{\mathsf{R}}$,
$\delta_{\mathsf{T}}$, $\delta_{\bot}$ in two lemmas in Section 6.

#### Defining the Reduction.

Having defined the various gadgets that we will use, let us describe the
instances that we construct from our input bipartite graph $G=(R\cup T,S)$. We
illustrate this on Figure 1 in Appendix Uniform Reliability of Self-Join-Free
Conjunctive Queries. The _vertices_ of $G$ are the elements of $R$ and $T$,
and its _edges_ are the pairs in $S$.

Let us now write $m\colonequals|S|$, and define the following large (but
polynomial) values. We will use them as parameters when building the various
$\mathsf{UR}$ instances to which we will reduce.

$M_{1}\colonequals 4ms+1\quad\leavevmode\nobreak\ \leavevmode\nobreak\
M_{2}\colonequals M_{1}+2m(t+s)M_{1}+1\quad\leavevmode\nobreak\
\leavevmode\nobreak\ M_{3}\colonequals
M_{1}+M_{2}+\left|{R}\right|(t+s)M_{2}+1$

Fix
$M\colonequals(\left|{R}\right|+1)\times(\left|{T}\right|+1)\times(m+1)^{3}$,
the number of instances to which we will reduce. Now, for each $0\leq p<M$, we
construct the instance $D_{p}$ on the schema $Q_{r,s,t}$, featuring:

  * •

One element $u$ for each vertex $u\in R$ of $G$, with all the facts
$\mathsf{R}_{1}(u),\ldots,\mathsf{R}_{r}(u)$

  * •

One element $w$ for each vertex $w\in T$ of $G$, with all the facts
$\mathsf{T}_{1}(w),\ldots,\mathsf{T}_{t}(w)$

  * •

For every edge $(u,w)\in S$ of $G$, create:

    * –

$p$ copies of the $(u,*,*,w)$-gadget connecting $u$ and $w$ (using fresh
elements for $b$ and $c$ in each copy, as denoted by the $*$’s).

    * –

$M_{1}\times p$ copies of the $(u,*)$-gadget (using a fresh element for $b$ in
each copy).

  * •

For each element $u\in R$, create $M_{2}\times p$ copies of the
$(u,*)$-gadget.

  * •

For each element $w\in T$, create $M_{3}\times p$ copies of the
$(*,w)$-gadget.

It is clear that this construction is in polynomial time in the input $G$ for
each $0\leq p<M$, because the values $M_{1},M_{2},M_{3}$ are polynomial, so
the construction is in polynomial-time overall because $M$ is polynomial.

For each $0\leq p<M$, we denote by $N_{p}$ the number of subinstances of
$D_{p}$ that violate $Q_{r,s,t}$. Each of these values can be computed in
polynomial time using our oracle for $\mathsf{UR}(Q_{r,s,t})$: for $0\leq
p<M$, we build $D_{p}$, call the oracle to obtain the number
$\left|{\mathrm{Mod}(Q_{r,s,t},D_{p})}\right|$ of subinstances that satisfy
$Q_{r,s,t}$, and compute: $N_{p}\colonequals
2^{\left|{D_{p}}\right|}-\left|{\mathrm{Mod}(Q_{r,s,t},D_{p})}\right|$.

Hence, in our reduction, given the input bipartite graph $G$, we have
constructed the instances $D_{p}$ and used our oracle to compute the number
$N_{p}$ of subinstances of each $D_{p}$ that violate $Q_{r,s,t}$, for each
$0\leq p<M$, and this process is in PTIME. In the next section, we explain how
we can use a linear equation system to recover from the numbers $N_{p}$ the
answer to our original problem on $G=(R\cup T,S)$, i.e., the number $P$ of
independent-set pairs of $G$.

##  5 Obtaining the Equation System

To define the linear equation system, it will be helpful to introduce some
parameters about subsets of vertices of the bipartite graph. For any
$R^{\prime}\subseteq R$ and $T^{\prime}\subseteq T$, we write the following:

  * •

$\mathrm{c}(R^{\prime},T^{\prime})$ to denote the number of edges of $S$ that
are _contained_ in $R^{\prime}\times T^{\prime}$, that is, they have both
endpoints in $R^{\prime}\cup T^{\prime}$. Formally,
$\mathrm{c}(R^{\prime},T^{\prime})\colonequals\left|{(R^{\prime}\times
T^{\prime})\cap S}\right|$.

  * •

$\mathrm{d}(R^{\prime},T^{\prime})$ to denote the number of edges of $S$ that
are _dangling from $R^{\prime}$_, that is, they have one endpoint in
$R^{\prime}$ and the other in $T\setminus T^{\prime}$. Formally,
$\mathrm{d}(R^{\prime},T^{\prime})\colonequals\left|{(R^{\prime}\times(T\setminus
T^{\prime}))\cap S}\right|$.

  * •

$\mathrm{d}^{\prime}(R^{\prime},T^{\prime})$ to denote the number of edges of
$S$ that are _dangling from $T^{\prime}$_, that is, they have one endpoint in
$R\setminus R^{\prime}$ and the other in $T^{\prime}$. Formally,
$\mathrm{d}^{\prime}(R^{\prime},T^{\prime})\colonequals\left|{((R\setminus
R^{\prime})\times T^{\prime})\cap S}\right|$.

  * •

$\mathrm{e}(R^{\prime},T^{\prime})$ to denote the number of edges of $S$ that
are _excluded_ from $R^{\prime}\cup T^{\prime}$, that is, they have no
endpoint in $R^{\prime}\cup T^{\prime}$. Formally,
$\mathrm{e}(R^{\prime},T^{\prime})\colonequals\left|{S\setminus(R^{\prime}\times
T^{\prime})}\right|$.

It is immediate by definition that, for any $R^{\prime}$ and $T^{\prime}$,
every edge of $S$ is either contained in $R^{\prime}\times T^{\prime}$,
dangling from $R^{\prime}$, dangling from $T^{\prime}$, or excluded from
$R^{\prime}\cup T^{\prime}$. Hence, we clearly have
$\mathrm{c}(R^{\prime},T^{\prime})+\mathrm{d}(R^{\prime},T^{\prime})+\mathrm{d}^{\prime}(R^{\prime},T^{\prime})+\mathrm{e}(R^{\prime},T^{\prime})=m$.

Observe that a pair $(R^{\prime},T^{\prime})$ is an independent-set pair of
$G$ iff $\mathrm{c}(R^{\prime},T^{\prime})=0$. Thus, our goal is to compute
the following, on the input $G$ to the reduction:

$P=|\\{(R^{\prime},T^{\prime})\mid R^{\prime}\subseteq
R,\,\,T^{\prime}\subseteq
T,\,\,\mathrm{c}(R^{\prime},T^{\prime})=0\\}|=\sum_{R^{\prime}\subseteq
R,\leavevmode\nobreak\ T^{\prime}\subseteq T,\leavevmode\nobreak\
\mathrm{c}(R^{\prime},T^{\prime})=0}\hskip-35.00005pt1$ (3)

Let us define the variables on the input graph $G$ that we will use to express
$P$, and that we will recover from the values $N_{p}$.

#### Picking Variables.

Our goal is to construct a linear equation system relating the quantity that
we wish to compute, namely $P$, and the quantities provided by our oracle,
namely $N_{p}$ for $0\leq p<M$. Instead of using $P$ directly, we will
construct a system connecting $N_{p}$ to quantities on $G$ that we now define,
from which we will be able to recover $P$. We call these quantities
_variables_ because they are unknown and our goal in the reduction is to
compute them from the $N_{p}$ to recover $P$.

Let us introduce, for each $0\leq i\leq\left|{R}\right|$, for each $0\leq
j\leq\left|{T}\right|$, for each $0\leq c,d,d^{\prime}\leq m$, the variable
$X_{i,j,c,d,d^{\prime}}$, that stands for the number of pairs
$(R^{\prime},T^{\prime})$ with $\left|{R^{\prime}}\right|=i$, with
$\left|{T^{\prime}}\right|=j$, and with $\mathrm{c}$\- and $\mathrm{d}$\- and
$\mathrm{d}^{\prime}$-values exactly as indicated. (We do not need
$\mathrm{e}$ as a parameter here because it is determined from $\mathrm{c}$,
$\mathrm{d}$, $\mathrm{d}^{\prime}$.) Formally:

$\displaystyle
X_{i,j,c,d,d^{\prime}}\colonequals|\\{(R^{\prime},T^{\prime})\mid$
$\displaystyle R^{\prime}\subseteq R\,,\,T^{\prime}\subseteq
T\,,\,\left|{R^{\prime}}\right|=i\,,\,\left|{T^{\prime}}\right|=j,$
$\displaystyle\mathrm{c}(R^{\prime},T^{\prime})=c\,,\,\mathrm{d}(R^{\prime},T^{\prime})=d\,,\,\mathrm{d}^{\prime}(R^{\prime},T^{\prime})=d^{\prime}\\}|$

And for technical reasons, let us define, for all $i,j,c,d,d^{\prime}$,
another variable:

$Y_{i,j,c,d,d^{\prime}}\colonequals(2^{r}-1)^{\left|{R}\right|-i}\times(2^{t}-1)^{\left|{T}\right|-j}\times
X_{i,j,c,d,d^{\prime}}$

The quantities $Y_{i,j,c,d,d^{\prime}}$ are the ones that we will actually use
in the equation system.

#### Getting our Answer from the Variables.

Let us now explain why we can compute our desired value $P$ (the number of
independent-set pairs of $G$) from the variables $Y_{i,j,c,d,d^{\prime}}$.
Refer back to Equation (3), and let us split this sum according to the values
of the parameters $i=\left|{R^{\prime}}\right|$,
$j=\left|{T^{\prime}}\right|$, and $\mathrm{d}(R^{\prime},T^{\prime})$,
$\mathrm{d}^{\prime}(R^{\prime},T^{\prime})$. Using our variables
$X_{i,j,c,d,d^{\prime}}$, this gives:

$P=\sum_{0\leq i\leq\left|{R}\right|}\sum_{0\leq
j\leq\left|{T}\right|}\sum_{0\leq d,d^{\prime}\leq m}X_{i,j,0,d,d^{\prime}}$

We can insert the variables $Y_{i,j,c,d,d^{\prime}}$ instead of
$X_{i,j,c,d,d^{\prime}}$ in the above, obtaining:

$P=\sum_{0\leq i\leq\left|{R}\right|}\sum_{0\leq
j\leq\left|{T}\right|}\sum_{0\leq d,d^{\prime}\leq
m}\frac{Y_{i,j,0,d,d^{\prime}}}{(2^{r}-1)^{\left|{R}\right|-i}\times(2^{t}-1)^{\left|{T}\right|-j}}$

This equation justifies that, to compute the quantity $P$ that we are
interested in, it suffices to compute the value of the variables
$Y_{i,j,0,d,d^{\prime}}$ for all $0\leq i\leq\left|{R}\right|$, $0\leq
j\leq\left|{T}\right|$, and $0\leq d,d^{\prime}\leq m$. If we can compute all
these quantities in polynomial time, then we can use the equation above to
compute $P$ in polynomial time, completing the reduction.

#### Designing the Equation System.

We will now design a linear equation system that connects the quantities
$N_{p}$ for $0\leq p<M$ computed by our oracle to the quantities
$Y_{i,j,c,d,d^{\prime}}$ for all $0\leq i\leq\left|{R}\right|$, $0\leq
j\leq\left|{T}\right|$, $0\leq c,d,d^{\prime}\leq m$ that we wish to compute.
To do so, write the vector $\vec{N}=(N_{0},\ldots,N_{M-1})$, and the vector
$\vec{Y}=(Y_{0,0,0,0,0},\ldots,Y_{\left|{R}\right|,\left|{T}\right|,m,m,m})$.
We will describe an $M$-by-$M$ matrix $A$ so that we have the equation
$\vec{N}=A\vec{Y}$. We will later justify that the matrix $A$ is invertible,
so that we can compute $\vec{Y}$ from $\vec{N}$ and conclude the proof.

To define the matrix $A$, let us consider arbitrary subsets
$R^{\prime}\subseteq R$ and $T^{\prime}\subseteq T$, and an arbitrary $0\leq
p<M$, and let us denote by $\mathcal{D}_{p}(R^{\prime},T^{\prime})$ the set of
subinstances of $D_{p}$ where the set of vertices of $R$ on which we have kept
_all_ $\mathsf{R}_{*}$-facts is precisely $R^{\prime}$, and where the set of
vertices on which we have kept _all_ $\mathsf{T}_{*}$-facts is precisely
$T^{\prime}$. In other words, an instance $I^{\prime}\subseteq D_{p}$ is in
$\mathcal{D}_{p}(R^{\prime},T^{\prime})$ if _(a)_ $I^{\prime}$ contains all
$\mathsf{R}_{*}$-facts on elements of $R^{\prime}$ and all
$\mathsf{T}_{*}$-facts on elements of $T^{\prime}$, _and (b)_ for each vertex
in $R\setminus R^{\prime}$, there is at least one $\mathsf{R}_{*}$-fact
missing from $I^{\prime}$, and for each vertex in $T\setminus T^{\prime}$,
there is at least one $\mathsf{T}_{*}$-fact missing from $I^{\prime}$. It is
clear that the $\mathcal{D}_{p}(R^{\prime},T^{\prime})$ form a partition of
the subinstances of $D_{p}$, so that:

$N_{p}=\sum_{R^{\prime}\subseteq R,T^{\prime}\subseteq
T}\left|{\\{I^{\prime}\in\mathcal{D}_{p}(R^{\prime},T^{\prime})\mid
I^{\prime}\not\models Q_{r,s,t}\\}}\right|$ (4)

Let us now study the number in the above sum for each $R^{\prime},T^{\prime}$,
that is, the number of instances in $\mathcal{D}_{p}(R^{\prime},T^{\prime})$
that violate the query. We can show the following by accounting over all
gadgets in the construction (and the complete proof is in the Appendix):

######  Claim 3.

clm:countmodels For any $0\leq p<M$, for any choice of $R^{\prime}$ and
$T^{\prime}$, writing $i\colonequals\left|{R^{\prime}}\right|$,
$j\colonequals\left|{T^{\prime}}\right|$,
$c\colonequals\mathrm{c}(R^{\prime},T^{\prime})$,
$d\colonequals\mathrm{d}(R^{\prime},T^{\prime})$,
$d^{\prime}\colonequals\mathrm{d}^{\prime}(R^{\prime},T^{\prime})$,
$e\colonequals\mathrm{e}(R^{\prime},T^{\prime})=m-c-d-d^{\prime}$, we have:

$\left|{\\{I^{\prime}\in\mathcal{D}_{p}(R^{\prime},T^{\prime})\mid
I^{\prime}\not\models
Q_{r,s,t}\\}}\right|=(2^{r}-1)^{\left|{R}\right|-i}\times(2^{t}-1)^{\left|{T}\right|-j}\times\alpha(i,j,c,d,d^{\prime})^{p}$

Where $\alpha(i,j,c,d,d^{\prime})$ is defined as the following quantity:

$\gamma^{c}\times\delta_{\mathsf{R}}^{d}\times\delta_{\mathsf{T}}^{d^{\prime}}\times\delta_{\bot}^{e}\times\lambda_{\mathsf{R}}^{M_{1}(c+d)+M_{2}i}\times\lambda_{\mathsf{T}}^{M_{3}j}\times{\bar{\lambda}}_{\mathsf{R}}^{M_{1}(d^{\prime}+e)+M_{2}(\left|{R}\right|-i)}\times{\bar{\lambda}}_{\mathsf{T}}^{M_{3}(\left|{T}\right|-j)}.$

######  Proof 5.1.

To show this, we notice that, on any possible world of
$\mathcal{D}_{p}(R^{\prime},T^{\prime})$, we can determine if the query is
true simply by looking at each gadget (and at the facts on the $u$ or the
$w$), as every match of the query can only use facts from a single gadget
(plus possibly facts on the $u$ or the $w$).

Thus, we have the following, where we use the numbers of possible worlds
$\lambda_{\mathsf{R}}$, ${\bar{\lambda}}_{\mathsf{R}}$,
$\lambda_{\mathsf{T}}$, ${\bar{\lambda}}_{\mathsf{T}}$, $\delta_{\mathsf{R}}$,
$\delta_{\mathsf{T}}$ and $\delta_{\bot}$ defined in Section 4:

  * •

We have no choice on the $\mathsf{R}_{*}$-facts of $R^{\prime}$ (we must keep
them all)

  * •

We have no choice on the $\mathsf{T}_{*}$-facts of $T^{\prime}$ (same
reasoning)

  * •

We have $2^{r}-1$ possibilities for each element of $R\setminus R^{\prime}$
(for each of them, we cannot keep all its $\mathsf{R}_{*}$-facts)

  * •

We have $2^{t}-1$ possibilities for each element of $T\setminus T^{\prime}$
(same reasoning)

  * •

For each edge $e=(u,w)\in S$:

    * –

If $e$ in contained in $R^{\prime},T^{\prime}$:

      * *

For the $(u,*)$-gadgets, we have $\lambda_{\mathsf{R}}^{M_{1}\times p}$
possibilities

      * *

For the $(u,*,*,w)$ gadgets connecting $u$ and $w$, we have $\gamma^{p}$
possibilities

    * –

If $e$ is dangling from $R^{\prime}$:

      * *

For the $(u,*)$-gadgets, we have $\lambda_{\mathsf{R}}^{M_{1}\times p}$
possibilities

      * *

For the $(u,*,*,w)$ gadget connecting $u$ and $w$, we have
$\delta_{\mathsf{R}}^{p}$ possibilities

    * –

If $e$ is dangling from $T^{\prime}$:

      * *

For the $(u,*)$-gadgets, we have ${\bar{\lambda}}_{\mathsf{R}}^{M_{1}\times
p}$ possibilities

      * *

For the $(u,*,*,w)$ gadgets connecting $u$ and $w$, we have
$\delta_{\mathsf{T}}^{p}$ possibilities

    * –

If $e$ is exterior to $R^{\prime},T^{\prime}$:

      * *

For the $(u,*)$-gadget, we have ${\bar{\lambda}}_{\mathsf{R}}^{M_{1}\times p}$
possibilities

      * *

For the $(u,*,*,w)$ gadgets connecting $u$ and $w$, we have
$\delta_{\bot}^{p}$ possibilities

  * •

For each $u\in R^{\prime}$, we have $\lambda_{\mathsf{R}}^{M_{2}\times p}$
possibilities for the $(u,*)$-gadgets

  * •

For each $u\in R\setminus R^{\prime}$, we have
${\bar{\lambda}}_{\mathsf{R}}^{M_{2}\times p}$ possibilities for the
$(u,*)$-gadgets

  * •

For each $w\in T^{\prime}$, we have $\lambda_{\mathsf{T}}^{M_{3}\times p}$
possibilities for the $(*,w)$-gadgets

  * •

For each $w\in T\setminus T^{\prime}$, we have
${\bar{\lambda}}_{\mathsf{T}}^{M_{3}\times p}$ possibilities for the
$(*,w)$-gadgets

Thus, with $i=\left|{R^{\prime}}\right|$, $j=\left|{T^{\prime}}\right|$,
$c=\mathrm{c}(R^{\prime},T^{\prime})$, $d=\mathrm{d}(R^{\prime},T^{\prime})$,
$d^{\prime}=\mathrm{d}^{\prime}(R^{\prime},T^{\prime})$,
$e=\mathrm{e}(R^{\prime},T^{\prime})$, we have:

$\displaystyle\left|{\\{D\in\mathcal{D}_{p}(R^{\prime},T^{\prime})\mid
D\not\models
Q_{r,s,t}\\}}\right|=(2^{r}-1)^{\left|{R}\right|-i}\times(2^{t}-1)^{\left|{T}\right|-j}\times\gamma^{cp}\times\delta_{\mathsf{R}}^{dp}\times\delta_{\mathsf{T}}^{d^{\prime}p}\times\delta_{\bot}^{ep}$
$\displaystyle\quad\times\lambda_{\mathsf{R}}^{(M_{1}(c+d)+M_{2}i)p}\times\lambda_{\mathsf{T}}^{M_{3}jp}\times{\bar{\lambda}}_{\mathsf{R}}^{(M_{1}(d^{\prime}+e)+M_{2}(\left|{R}\right|-i))p}\times{\bar{\lambda}}_{\mathsf{T}}^{M_{3}(\left|{T}\right|-j)p}$

This leads directly to the claimed result.

Let us inject this value in Equation (4). Note that this value only depends on
the cardinalities of $R^{\prime}$ and $T^{\prime}$ and the values of
$\mathrm{c},\mathrm{d},\mathrm{d}^{\prime},\mathrm{e}$, but not on the
specific choice of $R^{\prime}$ and $T^{\prime}$. Thus, splitting the sum
accordingly, we can obtain the following:

######  Claim 4.

For any $0\leq p<M$, we have that:

$N_{p}=\sum_{0\leq i\leq\left|{R}\right|}\,\sum_{0\leq
j\leq\left|{T}\right|}\,\sum_{0\leq c,d,d^{\prime}\leq
m}Y_{i,j,c,d,d^{\prime}}\times\alpha(i,j,c,d,d^{\prime})^{p}$

######  Proof 5.2.

Injecting the equality from Claim LABEL:clm:countmodels into Equation (4)
(from the main text), and splitting the sum, we get:

$N_{p}=\sum_{\begin{subarray}{c}0\leq i\leq\left|{R}\right|\\\ 0\leq
j\leq\left|{T}\right|\\\ 0\leq c,d,d^{\prime}\leq
m\end{subarray}}\sum_{\begin{subarray}{c}R^{\prime}\subseteq R\\\
T^{\prime}\subseteq T\\\
\left|{R^{\prime}}\right|=i,\left|{T^{\prime}}\right|=j\\\
\mathrm{c}(R^{\prime},T^{\prime})=c\\\
\mathrm{d}(R^{\prime},T^{\prime})=d,\mathrm{d}^{\prime}(R^{\prime},T^{\prime})=d^{\prime}\end{subarray}}(2^{r}-1)^{\left|{R}\right|-i}\times(2^{t}-1)^{\left|{T}\right|-j}\times\alpha(i,j,c,d,d^{\prime})^{p}$

The inner sum does not depend on $R^{\prime}$ and $T^{\prime}$, so let us
introduce the variables $X_{i,j,c,d,d^{\prime}}$:

$N_{p}=\sum_{\begin{subarray}{c}0\leq i\leq\left|{R}\right|\\\ 0\leq
j\leq\left|{T}\right|\\\ 0\leq c,d,d^{\prime}\leq
m\end{subarray}}X_{i,j,c,d,d^{\prime}}\times(2^{r}-1)^{\left|{R}\right|-i}\times(2^{t}-1)^{\left|{T}\right|-j}\times\alpha(i,j,c,d,d^{\prime})^{p}$

Note that we can now use instead the variables $Y_{i,j,c,d,d^{\prime}}$ to
eliminate the remaining factors, so that we get the promised equality.

This equation can be expressed as a matrix equation $\vec{N}=A\vec{Y}$, with
$A$ the $M$-by-$M$ matrix whose cells contain
$\alpha(i,j,c,d,d^{\prime})^{p}$. This matrix relates the vector $\vec{N}$
computed from our oracle calls and the variables $\vec{Y}$ that we wish to
determine to solve our problem on the graph $G$. It only remains to show that
$A$ is an invertible matrix, so that we can compute its inverse $A^{-1}$ in
polynomial time, use it to recover $\vec{Y}$ from $\vec{N}$, and from there
recover $P$ as we have argued, concluding the reduction. Now, $A$ is clearly a
Vandermonde matrix, so we need just argue that its coefficients
$\alpha(i,j,c,d,d^{\prime})$ are different: we do this in the next section.

##  6 Showing that the Matrix is Invertible

In this section, we conclude our proof of Theorem 3.4 by showing the
following:

######  Claim 5.

For all $(i,j,c,d,d^{\prime})\neq(i_{2},j_{2},c_{2},d_{2},d^{\prime}_{2})$
with $0\leq i,i_{2}\leq\left|{R}\right|$, $0\leq j,j_{2}\leq\left|{T}\right|$,
$0\leq c,c_{2},d,d_{2},d^{\prime},d^{\prime}_{2}\leq m$, we have
$\alpha(i,j,c,d,d^{\prime})\neq\alpha(i_{2},j_{2},c_{2},d_{2},d_{2}^{\prime})$.

This implies that the Vandermonde matrix $A$ is invertible, and concludes the
definition of the reduction and the proof of Theorem 3.4.

#### A Closer Look at $\gamma$, $\delta_{\mathsf{R}}$, $\delta_{\mathsf{T}}$
and $\delta_{\bot}$.

To show our claim, we will need to look deeper in the definition of $\alpha$,
which involves $\gamma$, $\delta_{\mathsf{R}}$, $\delta_{\mathsf{T}}$ and
$\delta_{\bot}$. Remember that these are the number of possible worlds of the
gadgets defined in Section 4. To show invertibility of the matrix, we will
first need to understand what is the exponent of the number $2$ in the
decomposition of these numbers as a product of primes. This is abstracted away
in the following lemma, which is proved in the Appendix simply by computing
explicitly the numbers of possible worlds:

######  Lemma 6.1.

lem:parity The number $\gamma$ is odd, and we have, for some odd quantities
$\delta_{\mathsf{R}}^{\prime}$, $\delta_{\mathsf{T}}^{\prime}$,
$\delta_{\bot}^{\prime}$:

$\delta_{\mathsf{R}}=2^{s}\times\delta_{\mathsf{R}}^{\prime}\quad\quad\delta_{\mathsf{T}}=2^{s}\times\delta_{\mathsf{T}}^{\prime}\quad\quad\delta_{\bot}=(2^{s})^{2}\times\delta_{\bot}^{\prime}$

######  Proof 6.2.

To show the lemma, we will work out exactly what the quantities $\gamma$,
$\delta_{\mathsf{R}}$, $\delta_{\mathsf{T}}$ and $\delta_{\bot}$ are. This
will also be useful in the proof of Lemma LABEL:lem:diseq. In this proof, the
reader should refer back to the definition of the gadgets in Section 4.

#### Computing $\gamma$.

We first do a case disjunction on $b$. There are $2^{t}-1$ cases where some
$\mathsf{T}_{*}$-facts on $b$ are missing, and $1$ case where they are all
present. Second, we do a case disjunction on $c$. There are $2^{r}-1$ cases
where some $\mathsf{R}_{*}$-facts on $c$ are missing, and $1$ case where they
are all present. We then study these four cases:

  * •

When there are both $\mathsf{T}_{*}$-facts missing on $b$ and
$\mathsf{R}_{*}$-facts missing on $c$, we know that there can be no matches of
the query, so there are $(2^{s})^{3}$ possible worlds.

  * •

When there are $\mathsf{T}_{*}$-facts missing on $b$ but no
$\mathsf{R}_{*}$-facts missing on $c$, there must be an $\mathsf{S}_{*}$-fact
missing on $(c,d)$ to avoid creating a match of the query, which gives
$2^{s}-1$ possibilities, and there are $(2^{s})^{2}$ possibilities for the
other $\mathsf{S}_{*}$-facts.

  * •

When there are no $\mathsf{T}_{*}$-facts missing on $b$ but
$\mathsf{R}_{*}$-facts missing on $c$, there must be an $\mathsf{S}_{*}$-fact
missing on $(a,b)$ to avoid creating a match of the query, which gives
$2^{s}-1$ possibilities, and there are again $(2^{s})^{2}$ possibilities for
the other $\mathsf{S}_{*}$-facts.

  * •

When there are no $\mathsf{T}_{*}$-facts missing on $b$ and no
$\mathsf{R}_{*}$-facts missing on $c$, there must be an $\mathsf{S}_{*}$-fact
missing on each of $(a,b)$, $(c,b)$, and $(c,d)$ to avoid creating a match of
the query, giving $(2^{s}-1)^{3}$ possibilities.

So we have:

$\gamma=(2^{t}-1)\times\left((2^{r}-1)\times(2^{s})^{3}+(2^{s})^{2}\times(2^{s}-1)\right)+((2^{r}-1)\times(2^{s})^{2}\times(2^{s}-1)+(2^{s}-1)^{3})$

Notice that this quantity is odd.

#### Computing $\delta_{\mathsf{R}}$.

We define the following, with the $2^{s}$ factor accounting for all
possibilities for the $\mathsf{S}_{*}$-facts on $(c,d)$:

$\delta_{\mathsf{R}}=2^{s}\times\delta_{\mathsf{R}}^{\prime}$

We then do a case disjunction on $b$: there are $2^{t}-1$ cases where some
$\mathsf{T}_{*}$-facts on $b$ are missing, and $1$ case where they are all
present.

  * •

In the first case, there can never be a match of the query for all
possibilities of $\mathsf{R}_{*}$-facts on $c$ and $\mathsf{S}_{*}$-facts on
$(a,b)$ and $(c,b)$, giving $2^{r}\times(2^{s})^{2}$ possibilities.

  * •

In the second case, we do a case disjunction on $c$:

    * –

In the $2^{r}-1$ cases where some $\mathsf{R}_{*}$-facts on $c$ are missing,
there must be an $\mathsf{S}_{*}$-fact missing on $(a,b)$ to avoid creating a
match of the query, but all possibilities of $\mathsf{S}_{*}$-facts on $(c,b)$
are possible, giving $(2^{s}-1)\times 2^{s}$ possibilities.

    * –

In the $1$ case where all $\mathsf{R}_{*}$-facts on $c$ are present, there
must be $\mathsf{S}_{*}$-facts missing both on $(a,b)$ and $(c,b)$ to avoid
creating a match of the query, so $(2^{s}-1)^{2}$ possibilities.

So we have:

$\delta_{\mathsf{R}}^{\prime}=(2^{t}-1)\times
2^{r}\times(2^{s})^{2}+((2^{r}-1)\times(2^{s}-1)\times(2^{s})+(2^{s}-1)^{2})$

The latter quantity is odd.

#### Computing $\delta_{\mathsf{T}}$.

By symmetry between $r$ and $t$ from the above, we define:

$\delta_{\mathsf{T}}=2^{s}\times\delta_{\mathsf{T}}^{\prime}$

where

$\delta_{\mathsf{T}}^{\prime}=(2^{r}-1)\times
2^{t}\times(2^{s})^{2}+((2^{t}-1)\times(2^{s}-1)\times(2^{s})+(2^{s}-1)^{2})$

which is again odd.

#### Computing $\delta_{\bot}$.

Clearly, by considering all possible states of $\mathsf{S}_{*}$-facts on
$(a,b)$ and $(c,d)$, we can define $\delta_{\bot}^{\prime}$ by:

$\delta_{\bot}=(2^{s})^{2}\times\delta_{\bot}^{\prime}$

Then, the only possible world of the remaining facts where we obtain a match
of the query is when we keep all $\mathsf{T}_{*}$-facts on $b$, all
$\mathsf{R}_{*}$-facts on $c$, and all $\mathsf{S}_{*}$-facts on $(b,c)$.
Thus, we have:

$\delta_{\bot}^{\prime}=2^{r+s+t}-1$

and this quantity is odd.

Second, we will need the following lemma on these quantities:

######  Lemma 6.3.

lem:diseq For all $r,s,t\geq 1$, we have:
$\delta_{\mathsf{R}}\times\delta_{\mathsf{T}}\neq\gamma\times\delta_{\bot}$.

###### Proof sketch.

We do a case disjunction on the possible worlds accounted in
$\delta_{\mathsf{R}}\times\delta_{\mathsf{T}}$ and those accounted in
$\gamma\times\delta_{\bot}$, picking an order on the nodes that simplifies the
comparison between the two case disjunctions. By focusing on the cases where
the number of possible worlds is different, we can explicitly compute the
difference between these two quantities and show that it is non-zero,
specifically it is $(2^{s})^{3}\times(2^{r}-1)\times(2^{t}-1)$. (We suspect
that there may be a more elegant proof avoiding the need for this case
disjunction.) ∎

######  Proof 6.4.

Let us consider, on the one hand, a pair of an $(a,t,u,d)$-gadget and of an
$(a,v,w,d)$-trimmed-gadget (where we rename the vertices and abbreviate the
lists of relations). Note that the nodes with question marks are those on
which we will do a case disjunction later:

$a$$\bm{t}$$\bm{u}$$d$$\mathsf{S}$$\mathsf{S}$$\mathsf{S}$$\mathsf{R}$$\bm{\mathsf{T}}$?$\bm{\mathsf{R}}$?$\mathsf{T}$$a$$\bm{v}$$\bm{w}$$d$$\mathsf{S}$$\mathsf{S}$$\mathsf{S}$$\bm{\mathsf{T}}$?$\bm{\mathsf{R}}$?

On the other hand, we consider a pair of an $(a,t,w,d)$-left-gadget and of a
$(a,v,u,d)$-right-gadget. Note that, to facilitate the subsequent analysis, we
order differently the vertex names:

$a$$\bm{t}$$\bm{w}$$d$$\mathsf{S}$$\mathsf{S}$$\mathsf{S}$$\mathsf{R}$$\bm{\mathsf{T}}$?$\bm{\mathsf{R}}$?$a$$\bm{v}$$\bm{u}$$d$$\mathsf{S}$$\mathsf{S}$$\mathsf{S}$$\bm{\mathsf{T}}$?$\bm{\mathsf{R}}$?$\mathsf{T}$

Let us consider all Boolean functions from $(t,u,v,w)$ to $\\{0,1\\}^{4}$
indicating, for each vertex, whether we keep all facts ($\mathsf{R}_{*}$-facts
or $\mathsf{T}_{*}$-facts) at that vertex, or discard at least one of them.
For each $4$-tuple $(x_{1},x_{2},x_{3},x_{4})$ of Boolean values, we will call
an $\mathsf{S}$-edge _constrained_ if we must not keep all its facts
(otherwise we create a match of the query), and unconstrained otherwise. And
let us see how many constrained edges there are for the pair consisting of the
$(a,t,u,d)$-gadget and the $(a,v,w,d)$-trimmed-gadget, and for the pair
consisting of the $(a,t,w,d)$-left-gadget and of a $(a,v,u,d)$-right-gadget,
written #ce and #dd’ respectively.

Table 1: Case disjunction on the number of possible worlds. The first column specifies on which vertices we keep all facts and on which we do not, in the order $t,u,v,w$. The next two columns indicate the number of constrained edges in the first pair ($(a,t,u,d)$-gadget and $(a,v,w,d)$-trimmed gadget), with a justification indicating which edges these are. The last two columns indicate the same information for the second pair ($(a,t,w,d)$-left-gadget and $(a,v,u,d)$-right gadget). Tuple | C1 |  Justification | C2 |  Justification
---|---|---|---|---
0000 | 0 |  none | 0 |  none
0001 | 0 |  none | 0 |  none
0010 | 0 |  none | 0 |  none
0100 | 1 |  edge after $u$ | 1 |  edge after $u$
1000 | 1 |  edge before $t$ | 1 |  edge before $t$
0011 | 1 |  edge between $v$ and $w$ | 0 |  none
0101 | 1 |  edge after $u$ | 1 |  edge after $u$
1001 | 1 |  edge before $t$ | 2 |  edge before $t$ and between $t$ and $w$
0110 | 1 |  edge after $u$ | 2 |  edge after $u$ and between $u$ and $v$
1010 | 1 |  edge before $t$ | 1 |  edge before $t$
1100 | 3 |  all edges on the $(a,t,u,d)$-gadget | 2 |  edge before $t$ and after $u$
0111 | 2 |  edge after $u$ and between $v$ and $w$ | 2 |  edge after $u$ and between $v$ and $u$
1011 | 2 |  edge before $t$ and between $v$ and $w$ | 2 |  edge before $t$ and between $t$ and $w$
1101 | 3 |  all edges on the $(a,t,u,d)$-gadget | 3 |  edges before $t$, between $t$ and $w$, and after $u$
1110 | 3 |  all edges on the $(a,t,u,d)$-gadget | 3 |  edges before $t$, between $v$ and $u$, and after $u$
1111 | 4 |  all edges on the $(a,t,u,d)$-gadget and middle edge of the $(a,v,w,d)$-trimmed-gadget | 4 |  two left edges of the $(a,t,w,d)$-left-gadget and two right edges of the $(a,v,u,d)$-right-gadget

The case disjunction is given as Table 1. The four rows with discrepancies are
highlighted in bold. Note that, for each of them, the 4-tuple has one 0 and
one 1 at the odd positions, and at the even positions. This means that the
coefficients of the corresponding possible worlds is always $1\times
1\times(2^{r}-1)\times(2^{t}-1)$. We can also take out a common factor
$(2^{s})^{3}$. Thus, let us define
$\kappa\colonequals(2^{r}-1)\times(2^{t}-1)\times(2^{s})^{3}$. We obtain the
following:

$\delta_{\mathsf{R}}\times\delta_{\mathsf{T}}-\gamma\times\delta_{\bot}=\kappa\times\left((2^{s})^{3}+3\times(2^{s})^{1}(2^{s}-1)^{2}-3\times(2^{s})^{2}\times(2^{s}-1)-(2^{s})^{0}\times(2^{s}-1)^{3}\right)$

So let us consider the relevant polynomial:

$\Pi(X)\colonequals X^{3}+3X(X-1)^{2}-3X^{2}(X-1)-(X-1)^{3}$

Numerical evaluation shows that this polynomial is actually the constant $1$.
Thus, we have
$\delta_{\mathsf{R}}\times\delta_{\mathsf{T}}-\gamma\times\delta_{\bot}=\kappa$,
and in particular
$\gamma\times\delta_{\bot}\neq\delta_{\mathsf{R}}\times\delta_{\mathsf{T}}$,
the desired result. This concludes the proof of Lemma LABEL:lem:diseq.

We can now use the previous lemmas to show Claim 5. Fix $i,j,c,d,d^{\prime}$
and $i_{2},j_{2},c_{2},d_{2},d^{\prime}_{2}$. As usual, we denote $e=m-c-
d-d^{\prime}$ and $e_{2}=m-c_{2}-d_{2}-d^{\prime}_{2}$. By contraposition, we
show that if
$\alpha(i,j,c,d,d^{\prime})=\alpha(i_{2},j_{2},c_{2},d_{2},d_{2}^{\prime})$
then the parameters are equal.

#### Equality on $i$ and $j$, and Two Equations for $c,d,d^{\prime}$.

Let us rewrite the definition of $\alpha$ using Lemma LABEL:lem:parity and
injecting the definition of ${\bar{\lambda}}_{\mathsf{R}}$ and
${\bar{\lambda}}_{\mathsf{T}}$ from Section 4:

$\displaystyle\alpha(i,j,c,d,d^{\prime})$
$\displaystyle=\gamma^{c}\times(2^{s})^{d}(\delta_{\mathsf{R}}^{\prime})^{d}\times(2^{s})^{d^{\prime}}(\delta_{\mathsf{T}}^{\prime})^{d^{\prime}}\times(2^{2s})^{e}{\delta_{\bot}^{\prime}}^{e}$
$\displaystyle\quad\times\lambda_{\mathsf{R}}^{M_{1}(c+d)+M_{2}i}\times\lambda_{\mathsf{T}}^{M_{3}j}\times(2^{t+s})^{M_{1}(d^{\prime}+e)+M_{2}(\left|{R}\right|-i)}\times(2^{r+s})^{M_{3}(\left|{T}\right|-j)}$

Recall that, by Lemma LABEL:lem:parity, the quantities $\gamma$,
$\delta_{\mathsf{R}}^{\prime}$, $\delta_{\mathsf{T}}^{\prime}$ and
$\delta_{\bot}^{\prime}$ are odd, and the quantities $\lambda_{\mathsf{R}}$
and $\lambda_{\mathsf{T}}$ as defined in Section 4 are odd. We get a similar
equation for $\alpha(i_{2},j_{2},c_{2},d_{2},d_{2}^{\prime})$. From the
integer equality
$\alpha(i,j,c,d,d^{\prime})=\alpha(i_{2},j_{2},c_{2},d_{2},d_{2}^{\prime})$,
the coefficients of two in the prime number decomposition of these numbers
must also be equal. This yields:

$\displaystyle\phantom{=\leavevmode\nobreak\
}\,s(d\phantom{{}_{2}}+d^{\prime}_{\phantom{2}}+2e\phantom{{}_{2}})+(t+s)\times(M_{1}(d^{\prime}_{\phantom{2}}+e\phantom{{}_{2}}))+(t+s)\times
M_{2}(\left|{R}\right|-i\phantom{{}_{2}})+(r+s)\times
M_{3}(\left|{T}\right|-j\phantom{{}_{2}})$
$\displaystyle=s(d_{2}+d_{2}^{\prime}+2e_{2})+(t+s)\times(M_{1}(d_{2}^{\prime}+e_{2}))+(t+s)\times
M_{2}(\left|{R}\right|-i_{2})+(r+s)\times M_{3}(\left|{T}\right|-j_{2})$

We now use the fact that, as $d,d^{\prime},e\leq m$, we have
$s(d+d^{\prime}+2e)\leq 4ms$. By definition of $M_{1}$, we have
$s(d+d^{\prime}+2e)<M_{1}$. We also have $d^{\prime}+e\leq 2m$, so that (using
the previous inequality) we have
$s(d+d^{\prime}+2e)+(t+s)\times(M_{1}(d^{\prime}+e))<M_{2}$ by definition of
$M_{2}$. Last, we have $\left|{R}\right|-i\leq\left|{R}\right|$, so that
(using the two previous inequalities) we have
$s(d+d^{\prime}+2e)+(t+s)\times(M_{1}(d^{\prime}+e))+(t+s)\times
M_{2}\times(\left|{R}\right|-i)<M_{3}$ by the definition of $M_{3}$. Similar
inequalities hold for the right-hand-side of the above equation. Thus, we can
reason about the quotient of the equation by $M_{3}$, about the quotient by
$M_{2}$ of its remainder modulo $M_{3}$, about the quotient by $M_{1}$ of the
remainder modulo $M_{2}$ of the remainder modulo $M_{3}$, and about the
remainder modulo $M_{1}$ of the remainder modulo $M_{2}$ of the remainder
modulo $M_{3}$. This gives us four equations (where we also simplify by the
constant factors $s$, $t+s$, $r+s$):

$d+d^{\prime}+2e=d_{2}+d^{\prime}_{2}+2e_{2}\quad\leavevmode\nobreak\
\leavevmode\nobreak\
d^{\prime}+e=d^{\prime}_{2}+e_{2}\quad\leavevmode\nobreak\
\leavevmode\nobreak\
\left|{R}\right|-i=\left|{R}\right|-i_{2}\quad\leavevmode\nobreak\
\leavevmode\nobreak\ \left|{T}\right|-j=\left|{T}\right|-j_{2}$

The last two equations imply that $i=i_{2}$ and $j=j_{2}$, so we have shown
that two quantities are equal, out of the five that define $\alpha$. The two
first equations imply $d^{\prime}+e=d^{\prime}_{2}+e_{2}$ (second equation),
and $d+e=d_{2}+e_{2}$ (subtracting the second equation from the first
equation). Rewriting $e=m-c-d-d^{\prime}$, rewriting $e_{2}$ likewise, and
simplifying, we get:

$c+d=c_{2}+d_{2}\quad\quad c+d^{\prime}=c_{2}+d^{\prime}_{2}$

These two equations do not suffice to justify that
$(c,d,d^{\prime})=(c_{2},d_{2},d^{\prime}_{2})$, so more reasoning is needed
to get one additional equation and argue that these quantities must be equal.

#### Getting the Last Equation.

Let us write the equality
$\alpha(i,j,c,d,d^{\prime})=\alpha(i_{2},j_{2},c_{2},d_{2},d_{2}^{\prime})$
and simplify all the (non-zero) values now known to be equal thanks to
$i=i_{2}$, $j=j_{2}$:

$\gamma^{c}\cdot(\delta_{\mathsf{R}})^{d}\cdot(\delta_{\mathsf{T}})^{d^{\prime}}\cdot(\delta_{\bot})^{e}\cdot\lambda_{\mathsf{R}}^{M_{1}(c+d)}\cdot{\bar{\lambda}}_{\mathsf{R}}^{M_{1}(d^{\prime}+e)}=\gamma^{c_{2}}\cdot(\delta_{\mathsf{R}})^{d_{2}}\cdot(\delta_{\mathsf{T}})^{d_{2}^{\prime}}\cdot(\delta_{\bot})^{e_{2}}\cdot\lambda_{\mathsf{R}}^{M_{1}(c_{2}+d_{2})}\cdot{\bar{\lambda}}_{\mathsf{R}}^{M_{1}(d_{2}^{\prime}+e_{2})}$

The previously shown equations also imply that the $\lambda_{\mathsf{R}}$ and
${\bar{\lambda}}_{\mathsf{R}}$ factors simplify, so we get:

$\gamma^{c-c_{2}}\times(\delta_{\mathsf{R}})^{d-d_{2}}\times(\delta_{\mathsf{T}})^{d^{\prime}-d^{\prime}_{2}}\times(\delta_{\bot})^{e-e_{2}}=1$

The equation $c+d=c_{2}+d_{2}$ (shown above) implies that $c-c_{2}=d_{2}-d$,
and subtracting that equation from $c+d^{\prime}=c_{2}+d^{\prime}_{2}$ (shown
above) gives $d^{\prime}-d=d^{\prime}_{2}-d_{2}$, so that
$d^{\prime}-d^{\prime}_{2}=d-d_{2}$. As we know $d+e=d_{2}+e_{2}$ (above), we
have $e-e_{2}=d_{2}-d$. Substituting all this, we have:

$(\gamma\times\delta_{\bot})^{d_{2}-d}=(\delta_{\mathsf{R}}\times\delta_{\mathsf{T}})^{d_{2}-d}$

Now, by Lemma LABEL:lem:diseq, we have
$\gamma\times\delta_{\bot}\neq\delta_{\mathsf{R}}\times\delta_{\mathsf{T}}$.
Thus, this equation implies that $d=d_{2}$. In combination with the equations
that we showed above, this completely specifies the system: from
$c+d=c_{2}+d_{2}$ we get $c=c_{2}$, and from
$c+d^{\prime}=c_{2}+d^{\prime}_{2}$ we get $d^{\prime}=d^{\prime}_{2}$. Thus,
we have $(c,d,d^{\prime},i,j)=(c_{2},d_{2},d_{2}^{\prime},i_{2},j_{2})$. This
establishes Claim 5 and shows that all coefficients
$\alpha(c,d,d^{\prime},i,j)$ of the Vandermonde matrix $A$ are different, so
it is invertible. This concludes the proof of Theorem 3.4, and hence of our
main result (Theorems 3.1 and 3.2).

##  7 Extending to Uniform Probabilities

Having proved our main result (Theorem 3.1), we now turn to a natural variant
of the probabilistic query evaluation problem: what if, instead of imposing
that all probabilities are $1/2$ (which amounts to uniform reliability), we
impose that all tuples of the same relation have the same probability? Let us
formally define this variant:

######  Definition 7.1.

Let $Q$ be a CQ without self-joins, and let $\varphi$ be a function mapping
each relation symbol $\mathsf{R}$ of $Q$ to a rational number
$0<\varphi(\mathsf{R})\leq 1$. The problem $\mathsf{PQE}_{\varphi}(Q)$ is the
problem $\mathsf{PQE}(Q)$ on input instances $I$ over $Q$ whose probability
function $\pi:I\to[0,1]$ is defined by $\varphi$, i.e., for every fact $f\in
I$, we have $\pi(f)=\varphi(\mathsf{R})$ for $\mathsf{R}$ the relation symbol
of $f$.

In this section, we will focus on this problem for the hard query
$Q_{1}:\mathsf{R}(x),\mathsf{S}(x,y),\mathsf{T}(y)$ from Equation 1, and write
the problem directly as $\mathsf{PQE}_{r,s,t}(Q_{1})$ where $0<r,s,t\leq 1$
are the respective images of $\mathsf{R}$, $\mathsf{S}$ and $\mathsf{T}$ by
$\varphi$. In this language, the uniform-reliability problem for $Q_{1}$ is
(up to renormalization) the problem
$\mathsf{PQE}_{\frac{1}{2},\frac{1}{2},\frac{1}{2}}(Q_{1})$, which we have
shown to be #P-hard in Theorem 3.1 because $Q_{1}$ is non-hierarchical. The
usual #P-hardness proof for $\mathsf{PQE}(Q_{1})$, where we reduce from the
problem of counting the satisfying assignment of a monotone partitioned DNF
formula, is actually a hardness proof for
$\mathsf{PQE}_{\frac{1}{2},1,\frac{1}{2}}(Q_{1})$. The natural question is
whether hardness can be shown for other values of $r$, $s$, and $t$.

Let us first observe that we can use our main result to show hardness of some
cases via an easy reduction. This illustrates how our hardness result on
uniform reliability (Theorem 3.2) can be used naturally to show hardness of
different problems:

######  Corollary 7.2.

cor:power2 $\mathsf{PQE}_{2^{-r},2^{-s},2^{-t}}(Q_{1})$ is #P-hard for all
natural numbers $r,s,t>0$.

###### Proof sketch.

We can reduce from uniform reliability for $Q_{r,s,t}$ (Equation (2) in
Section 3) to this PQE variant by merging together facts
$\mathsf{R}_{1}(a),\ldots,\mathsf{R}_{r}(a)$ into one fact $\mathsf{R}(a)$
having probability $2^{-r}$, and doing the analogous rewriting for the other
relations. ∎

######  Proof 7.3.

Consider the query $Q_{i,j,k}$, following the form of Equation 2. We have
shown in Theorem 3.4 that uniform reliability for $Q_{i,j,k}$ is #P-hard. Now,
observe that this problem naturally reduces to the PQE variant that we
consider. Indeed, consider an input instance $I$ to $\mathsf{UR}{Q_{i,j,k}}$.
We call an element $a$ of $I$ _useless for $\mathsf{R}_{*}$_ if some
$\mathsf{R}_{*}$-fact does not hold on $a$, we define $a$ being _useless for
$\mathsf{T}_{*}$_ analogously, and we call a pair $(a,b)$ of $I$ _useless for
$\mathsf{S}_{*}$_ if some $\mathsf{S}_{*}$-fact does not hold about the pair.
We call an $\mathsf{R}_{*}$-fact _useless_ if it holds about an element that
is useless for $\mathsf{R}_{*}$, and extend this definition to
$\mathsf{T}_{*}$-facts and to $\mathsf{S}_{*}$-facts (for element pairs). It
is easy to observe that no match of $Q_{i,j,k}$ on $I$ can involve a useless
fact. Indeed, when a match of the query involves a fact $f$ of the form
$\mathsf{R}_{*}(a)$, then the match witnesses that all other
$\mathsf{R}_{*}$-facts hold on $a$, so that $a$ is not useless for
$\mathsf{R}_{*}$, and $f$ is not useless. The same reasoning applies to
$\mathsf{S}_{*}$-facts and $\mathsf{T}_{*}$-facts.

Hence, let us compute in linear time the subinstance of $I^{\prime}$ where we
only keep the facts that are not useless: this is doable in polynomial time.
Now, any subset of $I$ is defined by picking a subset $J^{\prime}$ of
$I^{\prime}$ and a subset $J^{\prime\prime}$ of $I\setminus I^{\prime}$.
Further, as $I\setminus I^{\prime}$ only consists of useless facts, it is
clear that if some subset $J^{\prime}$ does not satisfy $Q_{i,j,k}$ then
$J\colonequals J^{\prime}\cup(I\setminus I^{\prime})$ still does not, because
the facts added in $I\setminus I^{\prime}$ cannot be part of a query match in
$I$, hence in $J$. All this reasoning shows that the answer to
$\mathsf{UR}(Q_{i,j,k})$ on $I$ is the answer to the same problem on
$I^{\prime}$, multiplied by the number of possible choices for
$J^{\prime\prime}$, that is, $2^{\left|{I\setminus I^{\prime}}\right|}$. So it
suffices to reduce the uniform reliability problem on $I^{\prime}$ to our PQE
problem to conclude to hardness of that PQE problem.

Now, we can rewrite $I^{\prime}$ in linear time to $I^{\prime\prime}$ by
replacing the set of $\mathsf{R}_{*}$-facts on every element $a$ where they
exist by a single $\mathsf{R}$-fact, and doing the same for
$\mathsf{T}_{*}$-facts and for $\mathsf{S}_{*}$-facts (on element pairs). As
we have removed useless facts, all facts of $I^{\prime}$ are thus taken into
account in the rewriting. Now, define the probability assignment $\pi$ on
$I^{\prime\prime}$ by mapping the $\mathsf{R}$, $\mathsf{S}$, and
$\mathsf{T}$-facts to $2^{-i}$, $2^{-j}$, and $2^{-k}$ respectively. This
means that $(I^{\prime\prime},\pi)$ is an instance to the
$\mathsf{PQE}_{2^{-i},2^{-j},2^{-k}}(Q_{1})$ problem that we are reducing to.
Now, there is an obvious correspondence from the subsets of $I^{\prime}$ to
the possible worlds of $I^{\prime\prime}$, defined by removing the useless
facts and converting to the signature $\mathsf{R}$, $\mathsf{S}$, $\mathsf{T}$
as we did in the reduction; and the number of preimages of each possible world
of $I^{\prime\prime}$ is exactly equal to its probability according to $\pi$,
up to renormalization by a constant factor of
$2^{-\left|{I^{\prime}}\right|}$. Thus, the answer to the problem
$\mathsf{UR}(Q_{i,j,k})$ on $I^{\prime}$ is exactly the answer to the problem
$\mathsf{PQE}_{2^{-i},2^{-j},2^{-k}}(Q_{1})$ on $I^{\prime\prime}$ up to
renormalization. This concludes the proof.

However, this does not completely classify the complexity of
$\mathsf{PQE}_{r,s,t}(Q_{1})$ for arbitrary values of $r$, $s$, $t$.
Conversely, it is easy to observe that $\mathsf{PQE}_{r,s,1}(Q_{1})$ and
$\mathsf{PQE}_{1,s,t}(Q_{1})$ can be solved in polynomial time:

######  Proposition 7.4.

prp:prob1 $\mathsf{PQE}_{r,s,1}(Q_{1})$ and $\mathsf{PQE}_{1,s,t}(Q_{1})$ are
in PTIME for all $0<r,s,t\leq 1$.

###### Proof sketch.

When the $\mathsf{R}$-facts have probability $1$, we can rewrite $Q_{1}$ to
$\mathsf{S}(x,y),\mathsf{T}(y)$ which is hierarchical, hence safe (Theorem
2.2). The other case is symmetric. ∎

######  Proof 7.5.

We only give the argument for $\mathsf{PQE}_{r,s,1}(Q_{1})$: the argument for
the other problem is analogous. Let $(I,\pi)$ be an input instance. First
remove all facts $\mathsf{S}(a,b)$ from $I$ where $I$ does not contain the
fact $T(b)$: this clearly does not change the answer to the problem as such
facts can never be part of a match to the query. Let
$(I^{\prime},\pi^{\prime})$ be the result of this process, with $\pi^{\prime}$
being the restriction of $\pi$ to $I^{\prime}$. Now, observe that every match
of the query $Q_{1}^{\prime}:\mathsf{R}(x),\mathsf{S}(x,y)$ in $I$ translates
to a match of the query $Q_{1}$ on the same choice of $x,y$; and conversely it
is obvious that any match of $Q_{1}$ translates to a match of
$Q_{1}^{\prime}$. Hence, every possible world of $(I,\pi)$ has a match of
$Q_{1}$ iff it has a match of $Q_{1}^{\prime}$. This implies that we can solve
$\mathsf{PQE}_{r,s,1}(Q_{1})$ on $I^{\prime}$, hence on $I$, by solving
$\mathsf{PQE}(Q_{1}^{\prime})$, and this is tractable by Dalvi and Suciu’s
result (Theorem 2.2) because $Q_{1}^{\prime}$ is a hierarchical self-join-free
CQ.

We conjecture that these are the only tractable cases. Specifically, we
conjecture the following generalization of the #P-hardness of
$\mathsf{UR}(Q_{1})$:

######  Conjecture 7.6.

$\mathsf{PQE}_{r,s,t}(Q_{1})$ is #P-hard for all $0<r,s,t\leq 1$ with $r<1$
and $t<1$.

We leave this for future work, but can prove Conjecture 7.6 in the case of
$s=1$. Formally:

######  Theorem 7.7.

thm:hardproba $\mathsf{PQE}_{r,1,t}(Q_{1})$ is #P-hard for every $0<r<1$ and
$0<t<1$.

###### Proof sketch.

Like in the previous section, we reduce from the problem of counting the
independent sets of a bipartite graph. We do a simpler coding using simpler
gadgets, and like before we that the number of independent sets (parameterized
by their number of vertices to the left and right) can be connected to the
answer to the uniform reliability problem on a family of instances with
different gadget instantiations. To argue that the matrix of the equation
system is invertible, we notice that it is the Kronecker product of two
invertible Vandermonde matrices. For space reasons, the full proof is deferred
to the appendix. ∎

##  8 Conclusion

While query evaluation over TIDs has been studied for over a decade, the basic
case of a uniform distribution, namely uniform reliability, had been left
open. We have settled this open question for the class of CQs without self-
joins, and shown that being hierarchical fully characterizes the computational
complexity of counting satisfying database subsets. We have also embarked on
the investigation of the more general variant of CQ evaluation over TIDs with
uniform probabilities. We have shown intractability for some combinations of
probabilities by a straightforward reduction from uniform reliability, and
shown hardness for others using different proof techniques. In future work, we
plan to investigate whether and how the proof of our main result can be
simplified, with the goal of showing hardness for all combinations of uniform
probabilities not known to be tractable, at least for the query $Q_{1}$
(Conjecture 7.6). Another question is whether our results could extend to CQs
and UCQs with self-joins to match the known dichotomy for non-uniform
probabilities [dalvi2012dichotomy].

#### Acknowledgments.

The authors are very grateful to Kuldeep S. Meel and Dan Suciu for insightful
discussions on the topic of this paper.

## References

  * [1] Paul Beame, Guy Van den Broeck, Eric Gribkoff, and Dan Suciu.  Symmetric weighted first-order model counting.  In PODS, pages 313–328. ACM, 2015.
  * [2] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering conjunctive queries under updates.  In PODS, pages 303–318. ACM, 2017.
  * [3] Andrei A. Bulatov.  The complexity of the counting constraint satisfaction problem.  J. ACM, 60(5):34:1–34:41, 2013.
  * [4] Supratik Chakraborty, Dror Fried, Kuldeep S Meel, and Moshe Y Vardi.  From weighted to unweighted model counting.  In IJCAI, 2015.
  * [5] Nilesh Dalvi and Dan Suciu.  Efficient query evaluation on probabilistic databases.  VLDB Journal, 16(4):523–544, 2007.
  * [6] Nilesh Dalvi and Dan Suciu.  The dichotomy of probabilistic inference for unions of conjunctive queries.  J. ACM, 59(6), 2012.
  * [7] Nilesh N. Dalvi, Christopher Ré, and Dan Suciu.  Probabilistic databases: Diamonds in the dirt.  Commun. ACM, 52(7):86–94, 2009.
  * [8] Pradeep Dubey and Lloyd S. Shapley.  Mathematical properties of the Banzhaf power index.  Mathematics of Operations Research, 4(2):99–131, 1979.
  * [9] Erich Grädel, Yuri Gurevich, and Colin Hirsch.  The complexity of query reliability.  In PODS, pages 227–234. ACM Press, 1998.
  * [10] Eric Gribkoff and Dan Suciu.  SlimShot: In-database probabilistic inference for knowledge bases.  PVLDB, 9(7):552–563, 2016.
  * [11] B. Grofman and H. Scarrow.  Iannucci and Its Aftermath: The Application of the Banzhaf Index to Weighted Voting in the State of New York, pages 168–183.  Physica-Verlag HD, Heidelberg, 1979.
  * [12] Harold V Henderson, Friedrich Pukelsheim, and Shayle R Searle.  On the history of the Kronecker product.  Linear and Multilinear Algebra, 14(2):113–120, 1983.
  * [13] Abhay Kumar Jha and Dan Suciu.  Probabilistic databases with MarkoViews.  PVLDB, 5(11):1160–1171, 2012.
  * [14] Ester Livshits, Leopoldo E. Bertossi, Benny Kimelfeld, and Moshe Sebag.  The Shapley value of tuples in query answering.  CoRR, abs/1904.08679, 2019.  URL: http://arxiv.org/abs/1904.08679, arXiv:1904.08679.
  * [15] Dany Maslowski and Jef Wijsen.  A dichotomy in the complexity of counting database repairs.  J. Comput. Syst. Sci., 79(6):958–983, 2013.
  * [16] Dany Maslowski and Jef Wijsen.  Counting database repairs that satisfy conjunctive queries with self-joins.  In ICDT, pages 155–164. OpenProceedings.org, 2014.
  * [17] Dan Olteanu and Jiewen Huang.  Using OBDDs for efficient query evaluation on probabilistic databases.  In SUM, volume 5291 of Lecture Notes in Computer Science, pages 326–340. Springer, 2008.
  * [18] J. Scott Provan and Michael O. Ball.  The complexity of counting cuts and of computing the probability that a graph is connected.  SIAM Journal on Computing, 12(4), 1983.
  * [19] Alvin E Roth.  The Shapley value: Essays in honor of Lloyd S. Shapley.  Cambridge University Press, 1988.
  * [20] Babak Salimi, Leopoldo E. Bertossi, Dan Suciu, and Guy Van den Broeck.  Quantifying causal effects on query answering in databases.  In TAPP, 2016.
  * [21] L.S. Shapley.  Stochastic games.  Proceedings of the National Academy of Sciences of the United States of America, 39:1095–1100, 1953.
  * [22] Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch.  Probabilistic Databases.  Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011.

relax

###### Proof.

relax∎

relax__relax In this appendix, we show Proposition LABEL:prp:reducerst. Recall
its statement: __relaxaxp@propositionrp
[3.3]__relaxaxp@fw@ri__relax__relax__relaxaxp@propositionrp

The crucial claim to show the result is the following lemma:

######  Lemma .1.

Let
$Q\mathrel{{:}{\text{-}}}\rho_{1}(\vec{\tau}_{1}),\dots,\rho_{n}(\vec{\tau}_{m})$
be a non-hierarchical CQ without self-joins, and let $x$ and $y$ be two
variables of $Q$ such that $\mathrm{atoms}(x)$ and $\mathrm{atoms}(y)$ have a
nonempty intersection and none contains the other. Let $Q^{\prime}$ be the
self-join-free CQ obtained from $Q$ by:

  * •

Replacing every $\rho_{i}(\vec{\tau}_{i})$ that contains $x$ and not $y$ with
a new atom $\rho^{\prime}_{i}(x)$;

  * •

Replacing every $\rho_{i}(\vec{\tau}_{i})$ that contains $y$ and not $x$ with
a new atom $\rho^{\prime}_{i}(y)$;

  * •

Replacing every $\rho_{i}(\vec{\tau}_{i})$ that contains both $x$ and $y$ with
a new atom $\rho^{\prime}_{i}(x,y)$;

  * •

Removing every $\rho_{i}(\vec{\tau}_{i})$ that contains neither $x$ nor $y$.

There is a Turing reduction from $\mathsf{UR}(Q^{\prime})$ to
$\mathsf{UR}(Q)$.

By definition of hierarchical queries (and as stated in [dalvi2007efficient,
Theorem 5.2] about unsafe queries), when $Q$ in the lemma above is non-
hierarchical, then we can find two variables $x$ and $y$ such that the CQ
$Q^{\prime}$ defined in the lemma has at least one atom of each of the three
types. What is more, up to renaming the relations, the query $Q^{\prime}$
defined in the lemma is a query of the form $Q_{r,s,t}$, with
$r\colonequals\left|{\mathrm{atoms}(x)\setminus\mathrm{atoms}(y)}\right|$,
$s\colonequals\left|{\mathrm{atoms}(x)\cap\mathrm{atoms}(y)}\right|$, and
$t\colonequals\left|{\mathrm{atoms}(y)\setminus\mathrm{atoms}(x)}\right|$. So
all that remains is to prove the lemma:

######  Proof .2.

The Turing reduction constructs an instance $I$ of $Q$ from an instance
$I^{\prime}$ of $Q^{\prime}$, as follows. Starting with an empty $I$, pick
some arbitrary constant value $c$, and add facts to $I$ in the following
manner.

  * •

For every atom $\rho^{\prime}_{i}(x)$ of $Q^{\prime}$ and fact
$\rho^{\prime}_{i}(a)$ of $I^{\prime}$, add to $I$ the fact that is obtained
from $\rho_{i}(\vec{\tau}_{i})$ by replacing every occurrence of $x$ with $a$
and every other variable with $c$.

  * •

Similarly, for every atom $\rho^{\prime}_{i}(y)$ of $Q^{\prime}$ and fact
$\rho^{\prime}_{i}(b)$ of $I^{\prime}$, add to $I$ the fact that is obtained
from $\rho_{i}(\vec{\tau}_{i})$ by replacing $y$ with $b$ and every other
variable with $c$.

  * •

For every atom $\rho^{\prime}_{i}(x,y)$ of $Q^{\prime}$ and fact
$\rho^{\prime}_{i}(a,b)$ of $I^{\prime}$, add to $I$ the fact that is obtained
from $\rho_{i}(\vec{\tau}_{i})$ by replacing every occurrence of $x$ with $a$,
every occurrence of $y$ with $b$, and every other variable with $c$.

  * •

For every atom $\rho_{i}(\vec{\tau}_{i})$ of $Q$ that contains neither $x$ nor
$y$, add to $I$ the fact that is obtained from $\rho_{i}(\vec{\tau}_{i})$ by
replacing every variable with $c$.

This completes the reduction.

Observe that every fact of $I^{\prime}$ gives rise to a unique fact of $I$.
Moreover, every fact of $I$ is created from exactly one fact of $I^{\prime}$,
except in the fourth bullet point above. Now, observe that whenever a possible
world of $I$ is missing one of the facts created in the fourth bullet point,
then it can never satisfy $Q$ as it does not have any facts of the
corresponding relation symbol. Thus, there is a bijection between
$\mathrm{Mod}(Q^{\prime},I^{\prime})$ and $\mathrm{Mod}(Q,I)$: every
$J^{\prime}\subseteq I^{\prime}$ is mapped to the subset $J$ that consists of
the facts that correspond to the facts of $J^{\prime}$, in addition to all the
facts created in the fourth bullet point. In particular,
$|\mathrm{Mod}(Q,I)|=|\mathrm{Mod}(Q^{\prime},I^{\prime})|$. This completes
the proof.

$T$$T^{\prime}$$R^{\prime}$$R$$u$$w$$S$

Figure 1:  Example of the bipartite graph $G=(R\cup T,S)$ and an independent
set $(R^{\prime},T^{\prime})$

__relaxaxp@claimrp [3]__relaxaxp@fw@rii__relax__relax__relaxaxp@claimrp

__relaxaxp@claimrp [4]__relaxaxp@fw@riii__relax__relax__relaxaxp@claimrp

In the proofs of this section, we will frequently use the gadgets defined in
Section 4, and to simplify the presentation we also give names to some
variants of these gadgets:

  * •

The _$(a,b,c,d)$ -left-gadget_ is like the $(a,b,c,d)$-gadget of Section 4,
but there are no $\mathsf{T}_{*}$-facts on $d$. Note that the quantity
$\delta_{\mathsf{R}}$ introduced in Section 4 is its number of possible worlds
that violate $Q$ where we fix the $\mathsf{R}_{*}$-facts on $a$.

  * •

The _$(a,b,c,d)$ -right-gadget_ is like the $(a,b,c,d)$-gadget but there are
no $\mathsf{R}_{*}$-facts on $a$. The quantity $\delta_{\mathsf{T}}$ is its
number of possible worlds that violate $Q$ where we fix the
$\mathsf{T}_{*}$-facts on $d$.

  * •

Lastly, the _$(a,b,c,d)$ -trimmed-gadget_ is like the $(a,b,c,d)$-gadget but
with no $\mathsf{R}_{*}$-facts on $a$ and no $\mathsf{T}_{*}$-facts on $d$.
The quantity $\delta_{\bot}$ is its number of possible worlds that violate
$Q$.

We now give the proofs that were omitted in the main text: __relaxaxp@lemmarp
[6.1]__relaxaxp@fw@riv__relax__relax__relaxaxp@lemmarp

__relaxaxp@lemmarp [6.3]__relaxaxp@fw@rv__relax__relax__relaxaxp@lemmarp

###  .1 Proofs of Corollary LABEL:cor:power2 and Proposition LABEL:prp:prob1

We first give the full proofs for the comparatively easy Corollary
LABEL:cor:power2 and Proposition LABEL:prp:prob1. __relaxaxp@corollaryrp
[7.2]__relaxaxp@fw@rvi__relax__relax__relaxaxp@corollaryrp

__relaxaxp@propositionrp
[7.4]__relaxaxp@fw@rvii__relax__relax__relaxaxp@propositionrp

###  .2 Proof of Theorem LABEL:thm:hardproba

We then prove the more challenging Theorem LABEL:thm:hardproba:
__relaxaxp@theoremrp
[7.7]__relaxaxp@fw@rviii__relax__relax__relaxaxp@theoremrp

We prove this theorem in the rest of the appendix. Similarly to Section 4, we
show a reduction from the problem of counting independent sets in a bipartite
graph. Recall that the input consists of a bipartite graph $G=(R\cup T,S)$,
and the goal is to calculate the number of independent-set pairs
$(R^{\prime},T^{\prime})$ with $R^{\prime}\subseteq R$ and
$T^{\prime}\subseteq T$ such that $R^{\prime}\times T^{\prime}$ is disjoint
from $S$ (as illustrated in Figure 1).

We denote by $P$ the number of independent-set pairs $(R^{\prime},T^{\prime})$
of $G$ (which we wish to compute), and we introduce variables $X_{i,j}$ for
$0\leq i\leq\left|{R}\right|$ and $0\leq j\leq\left|{T}\right|$ denoting the
number of such pairs where $\left|{R^{\prime}}\right|=i$ and
$\left|{T^{\prime}}\right|=j$. Hence:

$P=\sum_{0\leq i\leq\left|{R}\right|}\sum_{0\leq
j\leq\left|{T}\right|}X_{i,j}$

In our reduction, we will compute all of the $X_{i,j}$ using our oracle for
$\mathsf{PQE}_{r,1,t}(Q_{1})$, via a translation into a system of linear
equations where we will argue that the matrix is invertible.

We intuitively code our bipartite graph $G$ into an instance over $Q_{1}$ by
viewing the $\mathsf{R}$-facts as the left vertices, the $\mathsf{T}$-facts as
the right vertices, and the $\mathsf{S}$-facts as edges. However, as in the
previous section, we will reduce to multiple instances on $Q_{1}$ built in a
slightly different fashion. To define them, for any $0\leq
c\leq\left|{R}\right|$ and $0\leq d\leq\left|{T}\right|$, we denote by
$I_{c,d}$ the instance of $Q_{1}$ that encodes the bipartite graph $G$ in this
manner but where we additionally connect each left vertex $u\in R$ (resp.,
right vertex $w\in T$) to $c$ (resp., $d$) fresh vertices. Formally, we define
$I_{c,d}$ as follows. The domain of $I$ is $R\cup T\cup\\{w_{u,k}\mid u\in
R,1\leq k\leq c\\}\cup\\{u_{w,k}\mid w\in T,1\leq k\leq d\\}$, and the facts
are:

  * •

The facts that encode $G=(R\cup T,S)$:

    * –

$\mathsf{R}(u)$ for all $u\in R$,

    * –

$\mathsf{T}(w)$ for all $w\in T$,

    * –

$\mathsf{S}(u,w)$ for all $(u,w)\in S$.

  * •

The facts for the fresh vertices:

    * –

$\mathsf{T}(w_{u,k})$ and $\mathsf{S}(u,w_{u,k})$ for all $u\in R$ and
$k=1,\dots,c$,

    * –

$\mathsf{R}(u_{w,k})$ and $\mathsf{S}(u_{w,k},w)$ for all $w\in T$ and
$k=1,\dots,d$.

Let $\pi$ be the probability assignment given in Definition 7.1, that makes
$\mathsf{S}$-facts certain (probability 1) and gives $\mathsf{R}$-facts and
$\mathsf{T}$-facts probability $r$ and $t$ respectively. The possible worlds
of $(I_{c,d},\pi)$ with nonzero probability then consist of all of the
$\mathsf{S}$-facts, and some of the $\mathsf{R}$-facts and $\mathsf{T}$-facts.
If a possible world violates $Q_{1}$, then we call it an _independent
subinstance_. Hence, an independent subinstance is one such that no
$\mathsf{R}$-fact and $\mathsf{T}$-fact can join via an $\mathsf{S}$-fact. We
denote by $\Pi_{c,d}$ the probability of violating $Q_{1}$ on $I_{c,d}$, that
is, the sum of the probabilities of all independent subinstances of $I_{c,d}$.

We can compute the probability $\Pi_{c,d}$ similarly to the previous section
by partitioning the independent subinstances of $I_{c,d}$ based on the choice
of subsets $R^{\prime}\subseteq R$ and $T^{\prime}\subseteq T$ for which we
kept the $\mathsf{R}$-facts and $\mathsf{T}$-facts of the form $\mathsf{R}(u)$
or $\mathsf{T}(w)$. We can then note the total probability of the independent
subinstances for a choice of $R^{\prime}$ and $T^{\prime}$ only depend on the
cardinalities $i=\left|{R^{\prime}}\right|$ and $j=\left|{T^{\prime}}\right|$.
This allows us to use our variables $X_{i,j}$ capturing the number of choices
of $R^{\prime}$ and $T^{\prime}$ for a given choice of cardinalities. We can
then show:

######  Claim 6.

For any $0\leq c\leq\left|{R}\right|$ and $0\leq d\leq\left|{T}\right|$, we
have:

$\Pi_{c,d}=(1-r)^{\left|{R}\right|}\times(1-t)^{\left|{T}\right|}\times\sum_{\begin{subarray}{c}0\leq
i\leq\left|{R}\right|\\\ 0\leq
j\leq\left|{T}\right|\end{subarray}}X_{i,j}\times\left(\frac{r}{1-r}\times(1-t)^{c}\right)^{i}\times\left(\frac{t}{1-t}\times(1-r)^{d}\right)^{j}$

######  Proof .3.

Let us formally prove the result by considering a choice $R^{\prime}\subseteq
R$ and $T^{\prime}\subseteq T$, and computing the total probability of the
independent subinstances where we have kept the facts $\mathsf{R}(u)$ exactly
when $u\in R^{\prime}$, and we have kept the facts $\mathsf{T}(w)$ exactly
when $w\in T^{\prime}$.

  * •

First, we account for the probability of making the choice described by
$(R^{\prime},T^{\prime})$, namely, keeping the facts $\mathsf{R}(u)$ for $u\in
R^{\prime}$ and the facts $\mathsf{T}(w)$ for $w\in T^{\prime}$, and
discarding the facts $\mathsf{R}(u)$ for $u\in R\setminus R^{\prime}$ and
$\mathsf{T}(w)$ for $w\in T\setminus T^{\prime}$. This probability is

$r^{\left|{R^{\prime}}\right|}\times
t^{\left|{T^{\prime}}\right|}\times(1-r)^{\left|{R}\right|-\left|{R^{\prime}}\right|}\times(1-t)^{\left|{T}\right|-\left|{T^{\prime}}\right|}\,.$

  * •

The $\mathsf{S}$-facts have probability $1$, so they only contribute a factor
of $1$.

  * •

For each fact $\mathsf{T}(w_{u,k})$, where $u\notin R^{\prime}$, there is no
constraint (as we can keep this fact or not without creating a query match) so
the probability factor is $1$.

  * •

We need to discard each fact $\mathsf{T}(w_{u,k})$ where $u\in R^{\prime}$, or
otherwise we create a query match. This is done with probability $1-t$. Thus,
the overall factor of these facts is

$(1-t)^{\left|{R^{\prime}}\right|\times c}\,.$

  * •

A similar reasoning applies to the $\mathsf{R}$-facts that, in total, provide
the factor

$(1-r)^{\left|{T^{\prime}}\right|\times d}\,.$

Thus, we have the following expression for $\Pi_{c,d}$:

$\Pi_{c,d}=\hskip-10.00002pt\sum_{\begin{subarray}{c}R^{\prime}\subseteq
R,T^{\prime}\subseteq T\\\ (R^{\prime}\times T^{\prime})\cap
S=\emptyset\end{subarray}}\hskip-10.00002ptr^{\left|{R^{\prime}}\right|}\times
t^{\left|{T^{\prime}}\right|}\times(1-r)^{\left|{R}\right|-\left|{R^{\prime}}\right|}\times(1-t)^{\left|{T}\right|-\left|{T^{\prime}}\right|}\times(1-t)^{\left|{R^{\prime}}\right|\times
c}\times(1-r)^{\left|{T^{\prime}}\right|\times d}$

Let us split the sum based on the cardinalities of $R^{\prime}$ and
$T^{\prime}$, and let us factor out common factors. We get:

$\displaystyle\Pi_{c,d}$
$\displaystyle=(1-r)^{\left|{R}\right|}\times(1-t)^{\left|{T}\right|}$
$\displaystyle\times\sum_{\begin{subarray}{c}0\leq i\leq\left|{R}\right|\\\
0\leq
j\leq\left|{T}\right|\end{subarray}}\sum_{\begin{subarray}{c}R^{\prime}\subseteq
R,T^{\prime}\subseteq T\\\ (R^{\prime}\times T^{\prime})\cap S=\emptyset\\\
\left|{R^{\prime}}\right|=i,\left|{T^{\prime}}\right|=j\end{subarray}}\left(\frac{r}{1-r}\right)^{\left|{R^{\prime}}\right|}\times\left(\frac{t}{1-t}\right)^{\left|{T^{\prime}}\right|}\times(1-t)^{\left|{R^{\prime}}\right|\times
c}\times(1-r)^{\left|{T^{\prime}}\right|\times d}$

The inner expression only depends on the cardinalities $i$ and $j$ of
$R^{\prime}$ and $T^{\prime}$, so we can introduce the variables $X_{i,j}$ and
obtain:

$\Pi_{c,d}=(1-r)^{\left|{R}\right|}\times(1-t)^{\left|{T}\right|}\times\sum_{\begin{subarray}{c}0\leq
i\leq\left|{R}\right|\\\ 0\leq
j\leq\left|{T}\right|\end{subarray}}X_{i,j}\times\left(\frac{r}{1-r}\right)^{i}\times\left(\frac{t}{1-t}\right)^{j}\times(1-t)^{i\times
c}\times(1-r)^{j\times d}$

We get to the claimed equality by rearranging factors under the exponents $i$
and $j$.

Let us define $\sigma\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=(\left|{R}\right|+1)\times(\left|{T}\right|+1)$,
and let us consider two vectors of length $\sigma$:

  * •

$\vec{X}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=(X_{0,0},\ldots,X_{0,\left|{T}\right|},X_{1,0},\ldots,X_{1,\left|{T}\right|},\ldots,X_{\left|{R}\right|,0},\ldots,X_{\left|{R}\right|,\left|{T}\right|})$

  * •

$\vec{\Pi}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=(\Pi_{0,0},\ldots,\Pi_{0,\left|{T}\right|},\Pi_{1,0},\ldots,\Pi_{1,\left|{T}\right|},\ldots,\Pi_{\left|{R}\right|,0},\ldots,\Pi_{\left|{R}\right|,\left|{T}\right|})$

Let us consider the $\sigma\times\sigma$ square matrix $M$, with rows and
columns indexed by the pairs
$(0,0),\ldots,(0,\left|{T}\right|),\ldots,(\left|{R}\right|,0),\ldots,(\left|{R}\right|,\left|{T}\right|)$,
and where the cell at the column $(i,j)$ and row $(c,d)$ for $0\leq
c,i\leq\left|{R}\right|$ and $0\leq d,j\leq\left|{T}\right|$ has coefficient:

$M_{(c,d),(i,j)}=\left(\frac{r}{1-r}\times(1-t)^{c}\right)^{i}\times\left(\frac{t}{1-t}\times(1-r)^{d}\right)^{j}$

We can rewrite our previous equation as:

$\vec{\Pi}=(1-r)^{\left|{R}\right|}\times(1-t)^{\left|{T}\right|}\times
M\times\vec{X}$

So, all that remains is to prove that $M$ is invertible. Indeed, this
completes the reduction: given the bipartite graph $G$, we build in polynomial
time the instances $I_{c,d}$ for $0\leq c\leq\left|{R}\right|$ and $0\leq
d\leq\left|{T}\right|$, we invoke our oracle for $\mathsf{PQE}(Q_{1})$ on them
to compute $\vec{\Pi}$, we compute the inverse of $M$ in polynomial time, we
apply it and obtain $\vec{X}$ by dividing by
$(1-r)^{\left|{R}\right|}\times(1-t)^{\left|{T}\right|}$ (non-zero as
$r,t<1$), and we sum the $X_{i,j}$ to obtain the quantity $P$ on $G$ that we
needed.

We can now show that $M$ is invertible, because:

######  Claim 7.

The matrix $M$ is the Kronecker product111See, e.g., Henderson, Pukelsheim,
and Searle [henderson1983history] for the details and history of the Kronecker
product. of two invertible Vandermonde matrices $M^{\prime}$ and
$M^{\prime\prime}$.

######  Proof .4.

Let us denote for brevity:

$\displaystyle\alpha_{c}$
$\displaystyle\colonequals\frac{r}{1-r}\times(1-t)^{c}$
$\displaystyle\beta_{d}$
$\displaystyle\colonequals\frac{t}{1-t}\times(1-r)^{d}$

We can rewrite the definition of the cells of $M$ as:

$M_{(c,d),(i,j)}=(\alpha_{c})^{i}\times(\beta_{d})^{j}$

Now consider the $(\left|{R}\right|+1)\times(\left|{R}\right|+1)$-matrix:

$M^{\prime}=\begin{bmatrix}(\alpha_{0})^{0}&(\alpha_{0})^{1}&\dots&(\alpha_{0})^{\left|{R}\right|}\\\
(\alpha_{1})^{0}&(\alpha_{1})^{1}&\dots&(\alpha_{1})^{\left|{R}\right|}\\\
\vdots&\vdots&\ddots&\vdots\\\
(\alpha_{\left|{R}\right|})^{0}&(\alpha_{\left|{R}\right|})^{1}&\dots&(\alpha_{\left|{R}\right|})^{\left|{R}\right|}\end{bmatrix}$

This matrix is a Vandermonde matrix and it is invertible, because for any two
indices $c^{\prime}\neq c^{\prime\prime}$ we clearly have
$\alpha_{c^{\prime}}\neq\alpha_{c^{\prime\prime}}$.

And consider the $(\left|{T}\right|+1)\times(\left|{T}\right|+1)$-matrix:

$M^{\prime\prime}=\begin{bmatrix}(\beta_{0})^{0}&(\beta_{0})^{1}&\dots&(\beta_{0})^{\left|{T}\right|}\\\
(\beta_{1})^{0}&(\beta_{1})^{1}&\dots&(\beta_{1})^{\left|{T}\right|}\\\
\vdots&\vdots&\ddots&\vdots\\\
(\beta_{\left|{T}\right|})^{0}&(\beta_{\left|{T}\right|})^{1}&\dots&(\beta_{\left|{T}\right|})^{\left|{T}\right|}\end{bmatrix}$

Analogously to $M^{\prime}$, the matrix $M^{\prime\prime}$ is also an
invertible Vandermonde matrix.

Now, the Kronecker product of $M^{\prime}$ and $M^{\prime\prime}$ is by
definition the $\sigma\times\sigma$-matrix with the following blockwise
definition:

$M^{\prime}\otimes
M^{\prime\prime}=\begin{bmatrix}(\alpha_{0})^{0}M^{\prime\prime}&(\alpha_{0})^{1}M^{\prime\prime}&\dots&(\alpha_{0})^{\left|{R}\right|}M^{\prime\prime}\\\
(\alpha_{1})^{0}M^{\prime\prime}&(\alpha_{1})^{1}M^{\prime\prime}&\dots&(\alpha_{1})^{\left|{R}\right|}M^{\prime\prime}\\\
\vdots&\vdots&\ddots&\vdots\\\
(\alpha_{\left|{R}\right|})^{0}M^{\prime\prime}&(\alpha_{\left|{R}\right|})^{1}M^{\prime\prime}&\dots&(\alpha_{\left|{R}\right|})^{\left|{R}\right|}M^{\prime\prime}\end{bmatrix}$

We claim that $M^{\prime}\otimes M^{\prime\prime}=M$. Indeed, consider the
cell of $M^{\prime}\otimes M^{\prime\prime}$ at the $(c,d)$’th row (or, more
precisely, row number $c\times(\left|{T}\right|+1)+d$) and the $(i,j)$’th
column (or, more precisely, column number $i\times(\left|{T}\right|+1)+j$) for
$0\leq c,i\leq\left|{R}\right|$ and $0\leq d,j\leq\left|{T}\right|$. As the
size of $M^{\prime\prime}$ is
$(\left|{T}\right|+1)\times(\left|{T}\right|+1)$, the coordinates $c$ and $i$
identify which block of $M^{\prime}\otimes M^{\prime\prime}$ we are at
(namely, the block in row $c$ and column $i$), and the coordinates $d$ and $j$
identify where we are within that block (row $d$ and column $j$). So, in the
cell at row $(c,d)$ and column $(i,j)$, we find $(\alpha_{c})^{i}$ (the
coefficient of the block) multiplied by the content of $M^{\prime\prime}$ at
cell $(d,j)$, that is, $(\beta_{d})^{j}$. This is the same element that $M$
has at row $(c,d)$ and column $(i,j)$, so indeed $M=M^{\prime}\otimes
M^{\prime\prime}$.

This justifies that $M$ is also invertible, because the Kronecker product of
two invertible matrices is invertible. This concludes the proof of Theorem
LABEL:thm:hardproba.