--- title: "Most Probable Explanations for Probabilistic Database Queries" authors: - "İsmail İlkan Ceylan" - "Stefan Borgwardt" - "Thomas Lukasiewicz" doi: "10.24963/ijcai.2017/132" url: "https://ijcai.org/proceedings/2017/132" pdf: "https://ijcai.org/proceedings/2017/0132.pdf" venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence" year: 2017 pages: "950-956" track: "Main track" keywords: - "Knowledge Representation, Reasoning, and Logic: Description Logics and Ontologies" - "Knowledge Representation, Reasoning, and Logic: Computational Complexity of Reasoning" - "Uncertainty in AI: Exact Probabilistic Inference" - "Uncertainty in AI: Relational Inference" --- # Most Probable Explanations for Probabilistic Database Queries İsmail İlkan Ceylan, Stefan Borgwardt, Thomas Lukasiewicz *Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 950-956. DOI: [10.24963/ijcai.2017/132](https://doi.org/10.24963/ijcai.2017/132) ## Abstract Forming the foundations of large-scale knowledge bases, probabilistic databases have been widely studied in the literature. In particular, probabilistic query evaluation has been investigated intensively as a central inference mechanism. However, despite its power, query evaluation alone cannot extract all the relevant information encompassed in large-scale knowledge bases. To exploit this potential, we study two inference tasks; namely finding the most probable database and the most probable hypothesis for a given query. As natural counterparts of most probable explanations (MPE) and maximum a posteriori hypotheses (MAP) in probabilistic graphical models, they can be used in a variety of applications that involve prediction or diagnosis tasks. We investigate these problems relative to a variety of query languages, ranging from conjunctive queries to ontology-mediated queries, and provide a detailed complexity analysis. ## Full text ## 1 Introduction Research on building large-scale probabilistic knowledge bases (PKBs) has resulted in a number of systems including NELL [Mitchell et al., 2015], Yago [Hoffart et al., 2013], DeepDive [Shin et al., 2015], and Google's Knowledge Vault [Dong et al., 2014]. They have been used in a wide range of areas to automatically build structured knowledge bases. Most of them are based on the long tradition and foundations of probabilistic databases (PDBs) [Imieliski and Lipski, 1984; Suciu et al., 2011], which define probability distributions over sets of classical databases. Probabilistic query evaluation is the key inference task underpinning these systems. However, PKBs encompass rich, structured knowledge, for which alternative inference mechanisms beyond probabilistic query evaluation are needed. Inspired by the maximal posterior probability computations in Probabilistic Graphical Models (PGMs) [Pearl, 1988; Koller and Friedman, 2009], we investigate the problem of finding most probable explanations for probabilistic queries to exploit the potential of such large databases to their full extent. Computing the maximal posterior probability of a distinguished set of variables, given evidence about another set of ## Thomas Lukasiewicz Department of Computer Science University of Oxford, UK thomas.lukasiewicz@cs.ox.ac.uk variables, is one of the key computational problems in PGMs. In its general form, this problem is studied under the name of maximum a posteriori hypothesis 1 (MAP), where the hypothesis refers to an instantiation of a set of distinguished variables. The most probable explanation (MPE) is a special case of MAP, where the distinguished variables and the evidence variables cover all variables in the model. Maximal posterior probability computations have also been lifted to relational probabilistic models such as Markov Logic Networks (MLNs) [Richardson and Domingos, 2006]. Both MPE and MAP translate to probabilistic databases in a natural way through the rich structure of queries. The most probable database problem (analogous to MPE), first proposed in [Gribkoff et al., 2014], is the problem of determining the (classical) database with the largest probability that satisfies a given query. Intuitively, the query defines constraints on the data, and the goal is to find the most probable database that satisfies these constraints. We also introduce a more intricate notion, called most probable hypothesis, which only asks for partial databases satisfying the query (analogous to MAP). The most probable hypothesis contains only tuples that contribute to the satisfaction condition of the query, which allows to more precisely pinpoint the most likely explanations of the query. We study the computational complexity of the corresponding decision problems, denoted by MPD and MPH, respectively, for a variety of query languages. Our results provide detailed insights about the nature of these problems. We show that the data complexity of both problems is lower for existential queries than for universal queries. As expected, MPH usually has a higher complexity than MPD. We extend our results towards ontology-mediated queries (OMQs), which enrich the well-known class of unions of conjunctive queries with the power of ontological rules based on Datalog± (also called existential rules) [Baget et al., 2011; Cal`ı et al., 2013]. This follows the tradition of ontologybased data access [Poggi et al., 2008], which allows us to query PDBs in a more advanced manner. For OMQs, our analysis shows that the computational complexity of these problems can change significantly w.r.t. the ontology languages under consideration and the complexity-theoretic assumptions employed. Our results provide tight complexity bounds for all Datalog± languages known in the literature. Detailed proofs of all results can be found at https://lat.inf. tu-dresden.de/research/papers.html. 1 There exist other variants of these inference tasks [Kwisthout, 2011], and there are different naming conventions across communities; here, we use the terminology from the Bayesian Network (BN) literature [Darwiche, 2009]. ## 2 Background andMotivation We recall the basics of classical query languages and databases and briefly describe the tuple-independent PDB model. ## 2.1 Queries and Databases We consider a relational vocabulary consisting of finite sets R of predicates, C of constants, and V of variables. A term is a constant or a variable. An atom is of the form P(s1, . . . , sn), where P is an n-ary predicate, and s1, . . . , sn are terms. A tuple is an atom without variables. A conjunctive query (CQ) is an existentially quantified formula ∃xφ, where φ is a conjunction of atoms, written as a comma-separated list. A union of conjunctive queries (UCQ) is a disjunction of CQs. If φ is an arbitrary Boolean combination of atoms, then we call ∃xφ an existential query (∃Q), and ∀xφ a universal query (∀Q). A first-order query (FOQ) is an arbitrary first-order formula. A query is Boolean if it has no free variables. A database is a finite set of tuples. The central problem studied for databases is query evaluation: Finding all answers to a query Q over a database D, which are assignments of the free variables in Q to constants such that the resulting first-order formula is satisfied in D in the usual sense. In the following, we consider only Boolean queries Q, and focus on the associated decision problem, i.e., deciding whether Q is satisfied in D, denoted as usual by D ⊧ Q. ## 2.2 Probabilistic Databases The most elementary probabilistic database model is based on the tuple-independence assumption. We adopt this model and refer to [Suciu et al., 2011] for details and alternatives. A probabilistic database induces a set of classical databases (called worlds), each associated with a probability value. Formally, a probabilistic database (PDB) P is a finite set of probabilistic tuples of the form ⟨t ∶ p⟩ , where t is a tuple and p ∈ [0, 1], and, whenever ⟨t ∶ p⟩, ⟨t ∶ q⟩ ∈ P, then p = q. A PDB P assigns to every tuple t the probability p if ⟨t ∶ p⟩ ∈ P, and otherwise the probability 0. Since we usually consider a single, fixed PDB, we denote this probability assignment simply by P. We concentrate on the well-known possible worlds semantics. Under the tuple-independence assumption, P induces the following unique probability distribution over classical databases D: By the worlds induced by P we refer to those databases D with P(D) > 0. Query evaluation is also enriched by probabilistic information. More formally, the probability of a Boolean query Q w.r.t. P is P(Q) ∶= ∑D⊧Q P(D). Example 1. Consider the PDB Pv given in Figure 1 and the conjunctive query Figure 1: The PDB Pv, where each table represents a predicate and each row is a probabilistic tuple. | Vegetarian - alice | Vegetarian - 0.7 | FriendOf - alice | FriendOf - bob | 0.7 | |----------------------|--------------------|--------------------|------------------|-------| | bob | 0.9 | alice | chris | 0.8 | | chris | 0.6 | bob | chris | 0.1 | | Eats | Eats | Meat | Meat | | | bob | spinach | 0.7 | shrimp | 0.7 | | chris | mussels | 0.8 | mussels | 0.9 | | alice | broccoli | 0.2 | seahorse | 0.3 | through which we can ask the probability of vegetarians being friends with vegetarians. In the given PDB, alice, bob, and chris are all vegetarians and friends with each other (with some probability). The query is a special case of Q1 which asks whether bob has vegetarian friends. Its probability can be computed as P(Q′1 ) = 0.9 ⋅ 0.1 ⋅ 0.6 = 0.054. ∎ This task is known as probabilistic query evaluation, and it has been studied extensively in PDBs. In a celebrated result by [Dalvi and Suciu, 2012], it has been shown that UCQs exhibit a data complexity dichotomy between P and #P for probabilistic query evaluation. However, while dealing with large-scale knowledge bases, alternative inference mechanisms are needed. Consider again our running example, and suppose that we have observed that Q′1 is true and would like to learn what best explains this observation w.r.t. the PDB Pv. We revisit this example after providing a principled approach for dealing with such tasks. ## 3 Most Probable Explanations We investigate the problem of finding most probable explanations for probabilistic database queries under two different semantics. Finding the most probable database is to determine the world with the largest probability that satisfies a given query, as formalized by [Gribkoff et al., 2014]: Definition 2. The most probable database for a query Q over a PDB P is where D ranges over all worlds induced by P. Intuitively, a PDB defines a probability distribution over exponentially many classical databases, and the most probable database is the element in this collection that has the highest probability while still satisfying the query. This can be seen as the best instantiation of a probabilistic model, and hence analogous to MPE in BNs [Darwiche, 2009]. Example 3. Consider again the PDB Pv and the query which defines the constraints of being a vegetarian, which is violated by the tuples Veg(chris), Eats(chris, mussels) and Meat(mussels). Hence, the most probable database for Q2 cannot contain all three of them. It is easy to see that Veg(chris) is removed, as it has the lowest probability. Thus, the most probable database (in this case unique) contains all tuples of Pv that have a probability above 0.5, except for Veg(chris). Suppose that we have observed Q′1 , and we are interested in finding an explanation for this observation under the constraint of Q2, which is specified by Q3 = Q′1 ∧Q2. In this case, the most probable database must contain the tuples Veg(chris) and FriendOf(bob, chris), whereas Eats(chris, mussels) is omitted. ∎ Finding the most probable database is important, as it identifies the most likely state of a PDB relative to a query. However, it has certain limitations, which are analogous to the limitations of MPE in PGMs [Koller and Friedman, 2009]. Most importantly, one is always forced to choose a complete database although the query usually affects only a subset of the tuples. In other words, it is usually not the case that the whole database is responsible for the goal query to be satisfied. To be able to more precisely pinpoint the explanations of a query, we introduce the following more intricate notion. Definition 4. The most probable hypothesis for a query Q over a PDB P is where H ranges over sets of tuples t and negated tuples ¬t such that t occurs in P, and ⊧ denotes the open-world entailment relation, i.e., H ⊧ Q holds iff all worlds induced by P that satisfy H also satisfy Q. The sum inside the maximization evaluates to the product of the probabilities of the (negated) tuples in H, and hence we denote it by P(H). Note that each D ⊧ H must satisfy Q, and thus the most probable database is a special case of the most probable hypothesis that has to contain all tuples from P. In contrast, the most probable hypothesis contains tuples only if they contribute to the satisfaction of the query. Example 5. The most probable hypothesis H for Q3 consists of Veg(bob), Veg(chris), FriendOf(bob, chris), and ¬Eats(chris, mussels), which yields a probability of P(H) = 0.9 ⋅ 0.6 ⋅ 0.1 ⋅ (1 - 0.8) = 0.0108. Since the most probable hypothesis contains less tuples, it is more informative than the most probable database for Q3. ∎ Whereas the most probable database represents full knowledge about all facts, which corresponds to the common closed-world assumption for (probabilistic) databases, the most probable hypothesis may leave tuples of P unresolved, which can be seen as a kind of open-world assumption (although the tuples that do not occur in P are still false). ## Complexity Results We formulate the decision problems MPD and MPH and investigate their computational complexity (see Table 1). We assume familiarity with computational complexity theory, and the distinction between data and combined complexity. Definition 6. Let Q be a query, P a PDB, and p ∈ (0, 1] a threshold. We denote by MPD (resp., MPH) the problem of deciding whether there exists a database D (resp., hypothesis H) that satisfies Q with P(D) ≥ p (resp., P(H) ≥ p). Our first result concerns the well-known class of UCQs, and we observe that both MPD and MPH remain in polynomial time in the data complexity and in NP for the combined complexity. Theorem 7. MPD and MPH for UCQs can be decided in polynomial time in the data complexity and are NP-complete in the combined complexity. Intuitively, polynomial-time data complexity is ensured by the fact that UCQs are monotone queries: as a simple algorithm for MPD, consider all matches (of which there are polynomially many) of a given UCQ, and extend each match with all (negated) tuples from the PDB that have a probability greater than 0.5. This results in (polynomially many) classical databases, one of which is the most probable database. The polynomial data complexity result for MPH follows from similar arguments. This result may seem immediate, as UCQs are monotone queries, but for MPD we can show an even stronger result that applies to all existential queries, even if negations in front of query atoms are allowed. For MPH, we show an additional hardness in the combined complexity. Theorem 8. MPD for ∃Q can be decided in polynomial time in the data complexity and is NP-complete in the combined complexity. MPH for ∃Q can be decided in ΣP 2 in the data complexity and is ΣP 3 -complete in the combined complexity. Determining the precise data complexity of MPH for ∃Q is left as an open problem. For universally quantified queries, MPD becomes harder even in the data complexity. Given the rich structure of the query, it becomes possible to encode non-deterministic choices over all possible databases. It is important to note that a similar hardness result was also obtained in [Gribkoff et al., 2014] (although on a different query). Theorem 9. MPD for ∀Q is NP-complete in the data complexity. We observe a similar phenomenon for MPH, where the increase in the complexity is even more dramatic. Theorem 10. MPH for ∀Q is ΣP 2 -complete in the data complexity. Note that also MPE and MAP differ in terms of computational complexity: in BNs, the former is NP-complete [Shimony, 1994; Littman, 1999] and the latter NP PP -complete [Park and Darwiche, 2004a]. Differently, MPH remains in ΣP 2 ⊆ NP PP , since computing the probability of the hypothesis can be done in polynomial time due to the tupleindependence assumption. As we will examine later, allowing ontological rules to induce correlations on the tuples results in different complexities, which are more comparable to PGMs, which can express conditional dependencies between their variables. Our final result for this section concerns the combined complexity of both problems for ∀Q. Theorem 11. MPD and MPH for ∀Q are ΣP 2 -complete in the combined complexity. If we consider arbitrary FOQs, it is easy to show that the data complexity remains the same as for ∀Qs, and the combined complexity is still PSPACE, as for classical databases. Moreover, all our combined complexity results for PDBs hold even in the case where the arity of the predicates is bounded by some constant, commonly known as the bounded-arity (ba) combined complexity (see Table 1). The reason is that our hardness results use only predicates of a bounded arity. ## 4 Most Probable Explanations for OMQs We now study the problems in the presence of ontological rules, which add deductive power to PDBs. The benefits of using of ontologies for large-scale PKB completion are well known [Jung and Lutz, 2012; Borgwardt et al., 2017]. From a broader perspective, extending tuple-independent PDBs with logical rules is an old idea, aiming to induce correlations on a logical level, and thus to relax the tuple independence, resulting in very powerful formalisms [Poole, 1993; 1997]. In the remainder of this paper, we restrict ourselves to UCQs, but in exchange consider additional knowledge encoded through an ontology. In the simplest case, we can formulate negative constraints (NCs) like which imposes the same constraints as Q2. NCs are a special case of denial constraints over databases [Staworko and Chomicki, 2010]. We also allow to formulate more general ontological knowledge in the form of tuple-generating dependencies (TGDs). For instance, the first-order formulas are TGDs stating that the friend relation is symmetric and that every vegetarian knows another vegetarian. In particular, TGDs can express the well-known inclusion dependencies and join dependencies from database theory. Taking all parts together, we are talking about ontology-mediated queries, which are UCQs in combination with a so-called Datalog± ontology, i.e., a finite set of NCs and TGDs [Cal`ı et al., 2012]. We will pay particular attention to the case where only NCs are allowed, as this is closest to the constraints over PDBs that we described in the previous examples, and it gives us a baseline for the computational complexity. More formally, an NC ν is an FO formula ∀xϕ(x) → bot, where ϕ(x) is a conjunction of atoms, called the body of ν, and bot is the truth constant false. A TGD σ is an FO formula ∀x ϕ(x) → ∃y P(x, y), where ϕ(x) is a conjunction of atoms, called the body of σ, and P(x, y) is an atom, called the head of σ. A (Datalog± ) program (or ontology) Σ is a finite set of NCs and TGDs. 2 An ontology-mediated query (OMQ) (Q, Σ) consists of a program Σ and a Boolean UCQ Q. For the semantics, we extend the vocabulary by an infinite set N of nulls. An instance I is a possibly infinite set of tuples that may additionally contain nulls; it satisfies a TGD or NC σ if I ⊧ σ, where ⊧ denotes standard FO entailment. I satisfies a program Σ, written I ⊧ Σ, if I satisfies each formula in Σ. The set mods(D,Σ) of models of a database D relative to a program Σ is {I ∣ I ⊇ D and I ⊧ Σ}. A database D is consistent w.r.t. Σ if mods(D,Σ) is non-empty. The OMQ (Q,Σ) 2 We omit the universal quantifiers in TGDs and NCs, and use commas (instead of ∧) for conjoining atoms for ease of presentation. is entailed by D, denoted D ⊧ (Q,Σ), if I ⊧ Q holds for all I ∈ mods(D,Σ). Observe that consistency of D w.r.t. Σ can thus be written as D ⊭ (bot, Σ), or equivalently, D ⊭ (Qbot, Σ+ ), where Qbot is the UCQ obtained from the disjunction of the bodies of all NCs in Σ, and Σ+ contains all TGDs of Σ. The probability of an OMQ over a PDB is defined as usual, by summing up over the consistent worlds that entail the query. In general, the entailment problem is undecidable [Beeri and Vardi, 1981], which motivated syntactic fragments of TGDs (but not the NCs) [Cal`ı et al., 2012; Baget et al., 2011; Kr¨otzsch and Rudolph, 2011; Cal`ı et al., 2013; Fagin et al., 2005]. We focus on only a few of these classes here (see Table 1). If there are no TGDs at all, i.e., Σ+ = ∅, then we denote the query language by OMQNC. One of the most important classes, guarded programs (OMQG) allow only such TGDs that have a body atom (the guard) that contains all body variables. In the special case of linear programs (OMQL), the body may consist of only one atom. In frontierguarded programs (OMQFG), only the frontier variables, i.e., those shared by the body and the head, need to be guarded. We pay particular attention to the class of guarded and full programs (OMQGF), which does not allow existentially quantified variables, and is one of the least expressive Datalog± - based query languages with a P-complete data complexity. At the upper end of the expressivity spectrum, we observe classes like weakly guarded (OMQWG) programs, whose data complexity is already EXP-complete. From a theoretical perspective, the class of acyclic programs (OMQA), which do not allow cyclic dependencies between predicates, is of interest, because it has a non-deterministic combined complexity, which leads to a different behavior. A key paradigm in OMQ answering is the FO-rewritability of queries: an OMQ (Q,Σ) is FO-rewritable if there exists a Boolean UCQ QΣ such that, for all consistent databases D, it holds that D ⊧ (Q,Σ) iff D ⊧ QΣ. Intuitively, the rewritten query QΣ can be answered directly over the database, without referring to the Datalog± program. A class OMQX is FO-rewritable if all its OMQs are FO-rewritable; in this case, the OMQ entailment problem for OMQX has a data complexity of AC0 . Of the classes mentioned above, only OMQNC, OMQL, and OMQA have this property. In addition to data complexity, ba-combined complexity, and combined complexity, for OMQs we also consider the fixed-program (fp) combined complexity, where the Datalog± program is viewed as fixed, but both (P)DB and query are considered to be part of the input. The ba-combined complexity is of interest for Description Logics [Baader et al., 2003], some of which can be considered to be Datalog± languages with arity at most 2. ## 4.1 Most Probable Databases for OMQs For ontology-mediated queries, models are restricted to those that are consistent with the ontology. In other words, the constraints are considered separately from the (existential) query; thus, the definitions of MPD and MPH have to be adapted accordingly. The main difference is that we now consider only the consistent worlds induced by the PDB, and thus maximize only over consistent worlds. Table 1: Complexity results for MPD and MPH for a wide range of queries: all listed results are original contributions of this paper except the data complexity for ∀Q. This latter result has been strengthened towards the weaker representation OMQNC. | Query Languages | Most Probable Database - data | Most Probable Database - fp-comb. | Most Probable Database - ba-comb. | Most Probable Database - comb. | Most Probable Hypothesis - data | Most Probable Hypothesis - fp-comb. | Most Probable Hypothesis - ba-comb. | Most Probable Hypothesis - comb. | |-------------------|---------------------------------|-------------------------------------|-------------------------------------|----------------------------------|-----------------------------------|---------------------------------------|---------------------------------------|------------------------------------| | UCQ | in P | - | NP | NP | in P | - | NP | NP | | ∃Q | in P | - | NP | NP | in ΣP 2 | - | ΣP 3 | ΣP 3 | | ∀Q | NP | - | ΣP 2 | ΣP 2 | ΣP 2 | - | ΣP 2 | ΣP 2 | | FOQ | NP | - | PSPACE | PSPACE | ΣP 2 | - | PSPACE | PSPACE | | OMQNC | NP | NP | ΣP 2 | ΣP 2 | PP | NP PP | NP PP | NP PP | | OMQL | NP | NP | ΣP 2 | PSPACE | PP | NP PP | NP PP | PSPACE | | OMQA | NP | NP | P NE | P NE | PP | NP PP | P NE | P NE | | OMQGF | NP | NP | ΣP 2 | EXP | NP PP | NP PP | NP PP | EXP | | OMQG | NP | NP | EXP | 2EXP | NP PP | NP PP | EXP | 2EXP | | OMQFG | NP | NP | 2EXP | 2EXP | NP PP | NP PP | 2EXP | 2EXP | | OMQWG | EXP | EXP | EXP | 2EXP | EXP | EXP | EXP | 2EXP | Definition 12. The most probable database for an OMQ (Q, Σ) over a PDB P is As before, we consider the decision problem MPD, which checks for the existence of a world D as above that exceeds a given probability threshold p. Our complexity results for this problem are summarized in the lower left part of Table 1. A naive approach to solve MPD is to guess the database D, and then check that it entails the given OMQ, does not entail the query (Qbot,Σ+ ), and exceeds the probability threshold. Since the probability can be computed in polynomial time, the problem can be decided by an NP Turing machine using an oracle to check OMQ entailment. Theorem 13. If entailment for OMQX is in a complexity class C, then MPD for OMQX is in NPC (under the same complexity assumptions). By a reduction from 3-colorability, we show that MPD is NP-hard already in the data complexity, even if we only use NCs, i.e., the query and the positive program Σ+ are empty. This strengthens our previous result about ∀Qs, since NCs can be expressed by universal queries, but are not allowed to use negated atoms. Theorem 14. MPD for OMQNC is NP-hard in the data complexity, even for Q = ⊺. We show a matching upper bound even in the fp-combined complexity, by reconsidering the approach from Theorem 13. Since here the query (Qbot, Σ+ ) is fixed, for the non-entailment check, we can refer to the data complexity of OMQ entailment. Assuming that this is possible in P, and further that the fp-combined complexity does not exceed NP, then the whole test can be done by a single non-deterministic Turing machine in polynomial time. This insight yields an upper bound of NP for most of the classes we consider. Theorem 15. If entailment for OMQX is in NP in the fpcombined complexity and in P in the data complexity, then MPD for OMQX is in NP in the fp-combined complexity. Under ba-combined complexity assumptions, we observe an increase in complexity, which intuitively comes from the fact that the query (Qbot,Σ+ ) is not fixed anymore. Theorem 16. MPD for OMQNC is ΣP 2 -hard in ba-combined complexity, even for Q = ⊺. We obtain a matching upper bound from Theorem 13 if C = NP. Most of the remaining hardness results follow from the complexity of classical OMQ entailment, since an OMQ (Q,Σ) is entailed by a consistent database D iff the most probable database w.r.t. {⟨t ∶ 1⟩ ∣ t ∈ D} has probability 1. In combination with Theorem 13, this yields tight complexity results for large deterministic classes like PSPACE or EXP. This leaves open only the case of OMQA, for which entailment is NEXP-complete in the (ba-)combined complexity, which yields an upper bound of NP NEXP = P NEXP = P NE due to Theorem 13 and results from [Hemachandra, 1989]. We show that this bound is tight, using a reduction from a P NEXP - complete version of the tiling problem [F¨urer, 1983]. Theorem 17. MPH for OMQA is P NE -hard in the bacombined complexity. ## 4.2 Most Probable Hypotheses for OMQs Similarly to MPD, we have to update the definition of MPH to take into account only consistent worlds. Definition 18. The most probable hypothesis for an OMQ (Q, Σ) over a PDB P is where H is a set of (non-probabilistic) tuples t occurring in P. Since we consider only monotone queries (i.e., UCQs), we do not have to include negated tuples in the hypothesis. To solve MPH, one can guess a hypothesis, and then check whether it entails the query, and whether the probability mass of its consistent extensions exceeds the given threshold. The latter part can be done by a PP Turing machine with an oracle for OMQ entailment (by normalizing the probability of the worlds such that the threshold is exactly 0.5). The oracle can be used also for the initial entailment check. Theorem 19. If entailment for OMQX is in a complexity class C, then MPH for OMQX is in NP PPC (under the same complexity assumptions). For any C ⊆ PH, this yields NP PP PH = NP P PP = NP PP as an upper bound, due to a result from [Toda, 1989]. Except for PP, all other upper bounds in the lower right part of Table 1 also follow from this observation. For C = NEXP, the whole PP NEXP computation can be done by an NEXP oracle, and hence we again obtain NP NEXP = P NE in this case. On the other hand, we can transfer most of the lower bounds from MPD by a simple reduction. Theorem 20. If MPD for OMQX is hard for a complexity class C, then MPH for OMQX is also hard for C (under any complexity measure except for the data complexity). We now discuss the more interesting cases below PSPACE. For FO-rewritable classes of OMQs, we obtain a data complexity of only PP. This is due to the fact that TGDs can be compiled into the query, and the observation of Theorem 8 that existential queries can be processed using polynomially many steps. Nevertheless, in each step, we have to compute a non-trivial sum over the consistent worlds, which can be done in PP. Finally, the polynomially many PP checks can be compiled into a single PP operation [Beigel et al., 1995]. Theorem 21. If entailment for OMQX is in AC0 in the data complexity, then MPH for OMQX is PP-complete in the data complexity. To frame this result, we show NP PP -hardness both for OMQGF (the prototypical non-FO-rewritable class) in the data complexity, and for OMQNC in the fp-combined complexity. We use two similar reductions from a problem in the polynomial-time counting hierarchy [Wagner, 1986]. In the first one, we rely on the power of guarded and full TGDs; in the second, we use a non-fixed query and a careful choice of probabilities to simulate the effect of these TGDs. Theorem 22. MPH is NP PP -hard for OMQGF in the data complexity, and for OMQNC in the fp-combined complexity. We also observe a dichotomy in the data complexity of MPH, which follows from the dichotomy for probabilistic query evaluation [Dalvi and Suciu, 2012]. Note that the PPhardness holds only under Turing reductions. Lemma 23 (Dichotomy). For FO-rewritable classes OMQX, MPH is either in P or PP-hard in the data complexity. Our results apply to all decidable Datalog± languages from the literature, due to the generic nature of our theorems and the known complexity results for OMQ entailment [Cal`ı et al., 2012; Baget et al., 2011; Kr¨otzsch and Rudolph, 2011; Cal`ı et al., 2013]. For example, full sets of TGDs (F) behave like OMQGF, and linear full (LF) and acyclic full (AF) sets of TGDs exhibit the same complexities as OMQL. ## 5 RelatedWork Our work is inspired by the maximal posterior probability computations in PGMs [Pearl, 1988; Koller and Friedman, 2009]. It is well-known that they are a form of abduction, which clearly also applies to the problems studied here. Maximal posterior probability computations are central in PGMs and in statistical relational learning. However, analogous problems have not been studied in depth in the context of PDBs. To our knowledge, the only work in this direction is on most probable databases [Gribkoff et al., 2014], which we use as a starting point. Probabilistic query evaluation has been investigated in depth in the literature [Imieliski and Lipski, 1984; Suciu et al., 2011]. In fact, it is known to be either in P or #P-hard for UCQs in the data complexity [Dalvi and Suciu, 2012]. Extensions of PDBs with ontological rules, in particular with Datalog± , are also well-covered in the literature [Gottlob et al., 2013; Borgwardt et al., 2017]. The focus of these works is on probabilistic query answering. Most of our data complexity results are covered by the classes NP, ΣP 2 , PP, and NP PP . Though intractable, they are at the core of many important problems, which motivated a body of work tailored towards scalable algorithms for these classes. There is an immediate connection between MPE and weighted MAX-SAT [Sang et al., 2007]. Similarly, advances in knowledge compilation [Park and Darwiche, 2004b; Pipatsrisawat and Darwiche, 2009] and approximate model counting [Chakraborty et al., 2016; Fremont et al., 2017] are tailored to achieve optimal, scalable algorithms for problems in classes such as PP and NP PP . Both MPD and MPH can be cast into their propositional variants using the lineage representation of queries, which gives immediate access to such algorithms. However, there is need for future work in this direction, as grounding is not an optimal way of handling these problems; performing inference directly on FO-structures is known to be more efficient. ## 6 Summary and Outlook We studied two inference tasks for PDBs; namely finding the most probable database and the most probable hypothesis for a given query. The focus of this paper was to determine the precise complexity of these problems, and we provided a detailed analysis for these problems relative to a variety of query languages, ranging from conjunctive queries to ontologymediated queries. The main focus of future work is on the one hand to extend these results to other classes (such as equality generating dependencies) and on the other hand to obtain even more refined results (such as classification results). ## Acknowledgments This work was supported by DFG in the CRC 912 (HAEC), GRK 1907 (RoSI), and the project BA 1122/19-1 (GoAsQ), and by the UK EPSRC grants EP/J008346/1, EP/L012138/1, EP/M025268/1, and by The Alan Turing Institute under the EPSRC grant EP/N510129/1. ## References 1. [Baader et al., 2003] Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, edit- ors. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, 2003. 2. [Baget et al., 2011] Jean-Franc ¸ois Baget, Marie-Laure Mugnier, Sebastian Rudolph, and Michaël Thomazo. Walking the com- plexity lines for generalized guarded existential rules. In Proc. IJCAI, 2011. 3. [Beeri and Vardi, 1981] Catriel Beeri and Moshe Y. Vardi. The im- plication problem for data dependencies. In Proc. ICALP, 1981. 4. [Beigel et al., 1995] Richard Beigel, Nick Reingold, and Daniel Spielman. PP is closed under intersection. JCSS, 50(2):191-202, 1995. 5. [Borgwardt et al., 2017] Stefan Borgwardt, İsmail İlkan Ceylan, and Thomas Lukasiewicz. Ontology-mediated queries for prob- abilistic databases. In Proc. AAAI, 2017. 6. [Calì et al., 2012] Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. A general Datalog-based framework for tractable query answering over ontologies. JWS, 14:57-83, 2012. 7. [Calì et al., 2013] Andrea Calì, Georg Gottlob, and Michael Kifer. Taming the infinite chase: Query answering under expressive re- lational constraints. JAIR, 48:115-174, 2013. 8. [Chakraborty et al., 2016] Supratik Chakraborty, Kuldeep S. Meel, and Moshe Y. Vardi. Algorithmic improvements in approximate counting for probabilistic inference: From linear to logarithmic SAT calls. In Proc. IJCAI, 2016. 9. [Dalvi and Suciu, 2012] Nilesh Dalvi and Dan Suciu. The dicho- tomy of probabilistic inference for unions of conjunctive queries. J. ACM, 59(6):1-87, 2012. 10. [Darwiche, 2009] Adnan Darwiche. Modeling and Reasoning with Bayesian Networks. Cambridge University Press, 2009. 11. [Dong et al., 2014] Xin Luna Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Ni Lao, Kevin Patrick Murphy, Thomas Strohmann, Shaohua Sun, and Wei Zhang. Knowledge Vault: A web-scale approach to probabilistic knowledge fusion. In Proc. SIGKDD, 2014. 12. [Fagin et al., 2005] Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, and Lucian Popa. Data exchange: Semantics and query answering. TCS, 336(1):89-124, 2005. 13. [Fremont et al., 2017] Daniel Fremont, Markus Rabe, and Sanjit Seshia. Maximum model counting. In Proc. AAAI, 2017. 14. [Fürer, 1983] Martin Fürer. The computational complexity of the unconstrained limited domino problem (with implications for lo- gical decision problems). In Logic and Machines, 1983. 15. [Gottlob et al., 2013] Georg Gottlob, Thomas Lukasiewicz, Maria Vanina Martinez, and Gerardo I. Simari. Query answering under probabilistic uncertainty in Datalog+/-ontologies. AMAI, 69(1):37-72, 2013. 16. [Gribkoff et al., 2014] Eric Gribkoff, Guy Van den Broeck, and Dan Suciu. The most probable database problem. In Proc. BUDA, 2014. 17. [Hemachandra, 1989] Lane A. Hemachandra. The strong exponen- tial hierarchy collapses. JCSS, 39(3):299-322, 1989. 18. [Hoffart et al., 2013] Johannes Hoffart, Fabian M. Suchanek, Klaus Berberich, and Gerhard Weikum. YAGO2: A spatially and tem- porally enhanced knowledge base from Wikipedia. AIJ, 194:28- 61, 2013. 19. [Imieliski and Lipski, 1984] Tomasz Imieliski and Witold Lipski. Incomplete information in relational databases. J. ACM, 31(4):761-791, 1984. 20. [Jung and Lutz, 2012] Jean Christoph Jung and Carsten Lutz. Ontology-based access to probabilistic data with OWL QL. In Proc. ISWC, 2012. 21. [Koller and Friedman, 2009] Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009. 22. [Krötzsch and Rudolph, 2011] Markus Krötzsch and Sebastian Rudolph. Extending decidable existential rules by joining acyc- licity and guardedness. In Proc. IJCAI, 2011. 23. [Kwisthout, 2011] Johan Kwisthout. Most probable explanations in Bayesian networks: Complexity and tractability. IJAR, 52(9):1452-1469, 2011. 24. [Littman, 1999] Michael L. Littman. Initial experiments in stochastic satisfiability. In Proc. AAAI, 1999. 25. [Mitchell et al., 2015] Tom Mitchell, William Cohen, Estevam Hruschka, Partha Talukdar, Justin Betteridge, Andrew Carlson, Bhavana Dalvi Mishra, Matthew Gardner, Bryan Kisiel, Jayant Krishnamurthy, Ni Lao, Kathryn Mazaitis, Thahir Mohamed, Ndapa Nakashole, Emmanouil Platanios, Alan Ritter, Mehdi Samadi, Burr Settles, Richard Wang, Derry Wijaya, Abhinav Gupta, Xinlei Chen, Abulhair Saparov, Malcolm Greaves, and Joel Welling. Never-ending learning. In Proc. AAAI, 2015. 26. [Park and Darwiche, 2004a] James D. Park and Adnan Darwiche. Complexity results and approximation strategies for MAP ex- planations. JAIR, 21(1):101-133, 2004. 27. [Park and Darwiche, 2004b] James D. Park and Adnan Darwiche. A differential semantics for jointree algorithms. AIJ, 156(2):197- 216, 2004. 28. [Pearl, 1988] Judea Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988. 29. [Pipatsrisawat and Darwiche, 2009] Knot Pipatsrisawat and Adnan Darwiche. A new d-DNNF-based bound computation algorithm for functional E-MAJSAT. In Proc. IJCAI, 2009. 30. [Poggi et al., 2008] Antonella Poggi, Domenico Lembo, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Ric- cardo Rosati. Linking data to ontologies. JDS, 10:133-173, 2008. 31. [Poole, 1993] David Poole. Probabilistic Horn abduction and Bayesian networks. AIJ, 64(1):81-129, 1993. 32. [Poole, 1997] David Poole. The independent choice logic for mod- elling multiple agents under uncertainty. AIJ, 94(1):7-56, 1997. 33. [Richardson and Domingos, 2006] Matthew Richardson and Pedro Domingos. Markov logic networks. ML, 62(1):107-136, 2006. 34. [Sang et al., 2007] Tian Sang, Paul Beame, and Henry Kautz. A dynamic approach to MPE and weighted MAX-SAT. In Proc. IJCAI, 2007. 35. [Shimony, 1994] Eyal Solomon Shimony. Finding MAPs for belief networks is NP-hard. AIJ, 68(2):399-410, 1994. 36. [Shin et al., 2015] Jaeho Shin, Sen Wu, Feiran Wang, Christopher De Sa, Ce Zhang, and Christopher Ré. Incremental knowledge base construction using DeepDive. In Proc. VLDB, 2015. 37. [Staworko and Chomicki, 2010] Sławomir Staworko and Jan Chomicki. Consistent query answers in the presence of universal constraints. Inf. Syst., 35(1):1-22, 2010. 38. [Suciu et al., 2011] Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch. Probabilistic Databases. Morgan & Claypool, 2011. 39. [Toda, 1989] Seinosuke Toda. On the computational power of PP and ⊕P. In Proc. SFCS, 1989. 40. [Wagner, 1986] Klaus W. Wagner. The complexity of combinat- orial problems with succinct input representation. Acta Inf., 23(3):325-356, 1986.