There exist two approaches for exact probabilistic inference of UCQs on tuple-independent databases. In the extensional approach, query evaluation is performed within a DBMS by exploiting the structure of the query. In the intensional approach, one rst builds a representation of the lineage of the query on the database, then computes the probability of the lineage. In this paper we propose a new technique to construct lineage representations as deterministic decomposable circuits in PTIME. The technique can apply to a class of UCQs that has been conjectured to separate the complexity of the two approaches. We test our technique experimentally, and show that it succeeds on all the queries of this class up to a certain size parameter, i.e., over 20 million queries.
Probabilistic databases [
Unfortunately, even for very simple queries, PQE(Q) can be intractable.
When Q is a union of conjunctive queries (UCQ), a dichotomy result is provided
by the work of Dalvi and Suciu [
A second approach to PQE is intensional query evaluation or grounded inference, and consists of two steps. First, compute a representation of the lineage of the query Q on the database D, which is a Boolean formula intuitively representing which tuples of D su ce to satisfy Q. Second, perform weighted model counting on the lineage to obtain the probability. To ensure that model counting is tractable, we use the structure of the query to represent the lineage in tractable formalisms from the eld of knowledge compilation, such as read once Boolean formulas, free or ordered binary decision diagrams (OBDDs, FBDDs), deterministic decomposable normal forms (d-DNNFs), decision decomposable normal forms (dec-DNNFs), deterministic decomposable circuits (d-Ds), etc. The main advantage of this approach compared to lifted inference is that the lineage can help explain the query answer. Moreover, having the lineage in a good knowledge compilation formalism can be useful for other applications: we could for instance change the tuples' probabilities and compute the new result easily, or compute the most probable state of the database that satis es the query.
What we call the q9 conjecture, formulated by Dalvi, Jha, and Suciu [
In this paper we focus on a class of queries (the H-queries) that was
conjectured in [
To do this analysis, we had to solve a task of independent interest, namely,
computing explicitly the list of all inequivalent monotone Boolean functions on
7 variables. This task had previously been undertaken by Caze, Humphries, and
Gutkin [
Paper structure We start our presentation with preliminaries in Section 2. We
then de ne the H-queries in Section 3 and review what is known about them.
In Section 4 we introduce our technique, and we experimentally demonstrate its
e ectiveness in Section 5. Our code and all the functions are available online [
We will consider in this work the most commonly used model for probabilistic databases: the tuple-independent model, where each tuple is annotated with a probability of being present or absent, assuming independence across tuples: De nition 1. A tuple-independent (TID) database is a pair (D; ) consisting of a relational instance D and a function mapping each tuple t 2 D to a rational probability (t) 2 [0; 1]. A TID instance (D; ) de nes a probability distribution Pr on D0 D, where Pr(D0) := Qt2D0 (t) Qt2DnD0 (1 (t)). Given a Boolean query Q, the probabilistic query evaluation problem for Q (PQE(Q)) asks, given as input a TID instance (D; ), the probability that Q is satis ed in the distribution Pr. That is, formally, Pr(Q; (D; )) := PD0 D s.t. D0j=Q Pr(D0).
Dalvi and Suciu [
By contrast, in the intentional approach, one rst computes a representation of the lineage Lin(Q; D) of the query Q on the instance D: De nition 2. The lineage of a Boolean query Q over D is a Boolean formula Lin(Q; D) on the tuples of D mapping each Boolean valuation : D ! f0; 1g to 1 or 0 depending on whether D satis es Q or not, where D := ft 2 D j (t) = 1g.
The lineage can be represented with any formalism that represents Boolean
functions (Boolean formulas, BDDs, Boolean circuits, etc), but the crucial idea
is to use a formalism that allows tractable probability computation. In this
work we will speci cally focus on deterministic decomposable circuits (d-Ds)
and deterministic decomposable normal forms [
De nition 3. Let C be a Boolean circuit (featuring and, or, not, and variable gates). An and-gate g of C is decomposable if for every two input gates g1 6= g2 of g we have Vars(g1) \ Vars(g2) = ;, where Vars(g) denotes the set of variable gates that have a directed path to g in C. We call C decomposable if each andgate is. An or-gate g of C is deterministic if there is no pair g1 6= g2 of input gates of g and valuation of the variables such that g1 and g2 both evaluate to 1 under . We call C deterministic if each or-gate is. A negation normal form (NNF) is a circuit in which the inputs of not-gates are always variable gates.
Probability computation is in linear time for d-Ds (hence, for d-DNNFs): to
compute the probability of a d-D, compute by a bottom-up pass the probability
of each gate, where and gates are evaluated using , or gates using +, and not
gates using 1 x. While there does not seem to be any interest in using d-DNNFs
rather that d-Ds for probabilistic databases, we are also interested by d-DNNFs
from a knowledge compilation point of view, as it is currently not known if
d-Ds are strictly more succinct than d-DNNFs. We write UCQ(d-DNNF) (resp.,
UCQ(d-D)) to denote the set of UCQs Q such that for any database instance D,
we can compute in polynomial time (in data complexity) a d-DNNF (resp., d-D)
representation of Lin(Q; D). For a study of the intensional approach using weaker
formalisms for Boolean functions (read once formulas, ordered and free binary
decision diagrams), see [
UCQ(d-DNNF)
UCQ(d-D)
UCQ(P) (1)
Dalvi, Jha, and Suciu [
The H-queries We de ne in this section the H-queries and review what is known about them. The building blocks of these queries are the queries hki, which were rst de ned in the work of Dalvi and Suciu to show the hardness of UCQs that are not safe: De nition 4. Let k 2 N, k 1. The queries hki for 0 i k are de ned by: { hk0 = 9x9y R(x) ^ S1(x; y); { hki = 9x9y Si(x; y) ^ Si+1(x; y) for 1 { hkk = 9x9y Sk(x; y) ^ T (y). i < k;
We de ne the H-queries to be combinations of queries hki, as in [
The query class Hk (resp., Hk+) is then the set of queries Qk when ranges over all Boolean functions (resp., monotone Boolean functions) on variables hki.
1 1
We nally de ne H (resp., H+) to be S Hk (resp., S Hk+). Observe that the
k=1 k=1
Example 1. Let k = 3, and 9 be the monotone Boolean function (2 _ 3) ^ (0 _
3) ^ (1 _ 3) ^ (0 _ 1 _ 2). Then Q39 represents the query q9 = (h32 _ h33) ^ (h30 _
+
h33) ^ (h31 _ h33) ^ (h30 _ h31 _ h32) 2 H3 , which is safe and was conjectured
in [
To study the H-queries, we need the following notions on Boolean functions: De nition 6. Let be a Boolean function on variables hki. We will always consider a valuation of hki simply as the set of variables that maps to 1. We write SAT( ) the set of satisfying valuations of . We say that depends on variable l 2 hki if there exists a valuation hki such that ( [flg) 6= ( nflg). We write DEP( ) hki for the set of variables on which depends. We call and Qk nondegenerate if DEP( ) = hki (and degenerate otherwise).
Then, if is degenerate (i.e., does not depend on all its k + 1 variables), Qk
is safe and is in UCQ(d-DNNF) (in fact, even in UCQ(OBDD)):
Proposition 1 (Theorem 3.12 of [
This is in contrast to when is nondegenerate. Indeed, Beame, Li, Roy, and
Suciu then show [
Let us rst see what the dichotomy theorem tells us about H-queries that are nondegenerate. We shall restrict our attention to monotone functions now, i.e., to queries in H+, because the dichotomy theorem applies only to UCQs, and Qk is not a UCQ when is not monotone. We need to de ne the CNF lattice of : De nition 7. Let be a monotone Boolean function on variables hki such that DEP( ) = hki, and let FCNF = C0 ^ : : : ^ Cn be the (unique) minimized CNF representing , where we see each clause simply as the set of variables that it contains. For s hni, we de ne ds := S Ci. Note that d; is ;, and that we can i2s have ds = ds0 for s 6= s0. The CNF lattice of is the lattice (L; ), where L is fds j s hnig, and where is reversed set inclusion. In particular, the top element 1^ of LCNF is ;, while its bottom element 0^ is hki (because depends on all the variables, hence each variable is in at least one clause).
Example 2. The Hasse diagram of the CNF lattice of 9 is shown in Figure 1 (ignore for now the values at the right inside the nodes). 1. If L(0^; ^1) 6= 0, then Qk is #P-hard. Hence, if P is di erent from #P, we have Qk 2= UCQ(d-D). 2. If L(0^; ^1) = 0, then Qk is PTIME. We do not know if Qk 2 UCQ(d-DNNF) or Qk 2 UCQ(d-D). But by what precedes, we know that Qk 2= UCQ(dec-DNNF) and Qk 2= UCQ(d-SDNNF).
Our goal is to investigate, when we are in the second case ( is monotone, nondegenerate and safe), for which functions we can build d-DNNFs or d-Ds. 4
In this section we present a technique to prove that some queries Qk 2 Hk are in UCQ(d-DNNF). This will in particular apply to the query q9 (which, we recall, was conjectured not to be in UCQ(d-D)). Our goal is to rewrite as 0 _: : : _ k, where the i are mutually exclusive ( i ^ j ? for i 6= j) and depend on strict subsets Si ( hki of hki. When such a rewriting exists, we say that is nice: De nition 8. Let be a Boolean function on variables hki. We call nice if there exist strict subsets Si of hki and mutually exclusive Boolean functions (not k necessarily monotone) i for 0 i k such that DEP( i) = Si and W i. i=0
Observe that allowing to have more (or less) than k + 1 functions i would not change the de nition of being nice. Also, note that if is degenerate, then is trivially nice.
Example 3. The function 9 is equivalent to the mutually exclusive disjunction 0 _ 1 _ 2 _ 3, where 0 0 ^ :2 ^ 3; 1 :1 ^ 2 ^ 3; 2 :0 ^ 1 ^ 3; and 3 0 ^ 1 ^ 2. Moreover for 0 i 3 we have DEP( i) ( h3i, hence 9 is nice. words, the following holds:
be a Boolean function on variables hki. If
Hence q9 2UCQ(d-DNNF). This result shows that, for all queries Qk where is nice, we can compute a d-DNNF representation of their lineage in PTIME, and hence compute their probability e ciently. We do not know to which queries this technique can be applied. Moreover also we have the following corollary: be a Boolean function on variables hki. If : is Corollary 1. Let k 2 N and nice, then Qk 2 UCQ(d-D). 5
We will call co-nice a function such that : is nice.
We have presented a technique that can be used to show that some queries are in UCQ(d-DNNF) or UCQ(d-D), but we have not characterized the queries to which it applies. In this section, we present our experiments that show that for all k 2 f1; : : : ; 6g, every nondegenerate monotone function for which Qk is safe is either nice or co-nice. Hence all the safe queries in Hk+ for k 2 f1; : : : ; 6g are in UCQ(d-D). This suggests that UCQ(d-D) = UCQ(P), or at least that any counterexample query in H+ must be in Hk+ for k 7.
We used a machine with 40 x86 64 CPUs of 2.6 GHz and 512 GB RAM.
The code was written in Python 2.7.12 and parallelized using Python's
multi+
processing library. We explain brie y how we generated all the functions in Hk
for k 2 f1; : : : ; 6g in Section 5.1, then explain how we tested niceness of these
functions in Section 5.2.
We started by generating the set R(k) of all monotone Boolean functions on
variables hki up to isomorphism, that is, up to renaming the variables. The
size of R(k) corresponds to the OEIS sequence A003182, which is only known
up to k = 6 (computed in [
To check if is nice, we build a CNF Nice( ) that expresses exactly that SAT( ) can be partitioned nicely, i.e., Nice( ) is satis able if and only if is nice. We can then use a SAT solver.
De nition 10. Let k 1 and be a Boolean function on hki. We de ne the CNF Nice( ) as follows. Its set of variables is fxl j 2 SAT( ) and l 2 hkig, where xl intuitively expresses that is put in box l. Its set of clauses is: 1. For each
k 2 SAT( ), the clause W xl , expressing the valuation l=0 must be put in at least one box; 2. For each 2 SAT( ) and l; l0 2 f0; : : : ; kg with l 6= l0, the clause :xl _ :xl0 , expressing that the valuation is in at most one box; 3. For each 2 SAT( ) and l 2 f0; : : : ; kg, then: (a) If Toggle( ; l) 2= SAT( ), the clause :xl ; (b) Else, the clause :xl _ xlToggle( ;l).
This ensures that the box l has a symmetry around l.
Proposition 3.
is nice i Nice( ) is satis able.
Now for each function in SND (k), we constructed the CNF formula Nice( ),
and used the SAT solver Glucose [
We give here one of the 2 functions that are in co-N (5), co N1 := 24 ^ 034 ^ 013 ^ 12 ^ 15 ^ 05 ^ 35 ^ 23 ^ 02 ^ 25 ^ 014 ^ 45 where we write, for instance, 014 to mean 0 _ 1 _ 4. Could co N1 separate UCQ(d-DNNF) from UCQ(d-D)? 6
We have introduced a new technique to construct deterministic decomposable
circuits for safe H-queries and have experimentally demonstrated its e ectiveness
on the rst 20 million such queries. We conjecture that this technique can build
d-Ds for all safe H-queries. We leave open many intriguing questions:
{ For the H-queries, can we use the DNF lattice instead of the CNF lattice to
decide if the query is safe [
We have put online our code, and the complete list of all the functions studied in Section 5.2, which we believe could be useful for people studying the H-queries. It can be used, for instance, to enter by hand a monotone Boolean function and check if Qk is safe of not, draw its CNF lattice, check if is nice, etc. Acknowledgements. We are grateful to Antoine Amarilli for careful proofreading of the article (and for the many discussions about the code), to Romain Caze for pointing out to us his code to generate monotone Boolean functions, and to Stephen Tamon for referring us to Romain Caze. The second author would like to acknowledge Guy van den Broeck for initial discussions on the q9 conjecture. The fact that q9 is expressible as a succinct d-D has been already known to him and has been mentioned in several of his presentations prior to this article. This work was partly funded by the Telecom ParisTech Research Chair on Big Data and Market Insights, and by the EPSRC platform grant DBOnto (L012138) that funded Mikael's research visit at Oxford.