Open-World Probabilistic Databases: An Abridged Report

1 Introduction

Driven by the need to learn from vast amounts of text data, efforts throughout natural language processing, information extraction, databases and AI are coming together to build large-scale knowledge bases. Academic systems such as NELL [Mitchell et al., 2015], DeepDive [Sa et al., 2017], Freebase [Bollacker et al., 2008], and Yago [Hoffart et al., 2013] continuously crawl the web to extract relational information. Industry projects such as Microsoft's Probase [Wu et al., 2012], IBM's Watson [Ferrucci, 2012], or Google's Knowledge Vault [Dong et al., 2014] similarly learn structured data from text. These systems have already populated their databases with millions of entities and billions of tuples.

Such knowledge bases are inherently probabilistic. To go from the raw text to structured data, information extraction systems employ a sequence of statistical machine learning techniques, from part-of-speech tagging until relation extraction [Mintz et al., 2009]. For knowledge-base completion statistical relational learning algorithms make use of embeddings [Bordes et al., 2011; Socher et al., 2013] or probabilistic rules [Wang et al., 2013; De Raedt et al., 2015]. In

∗This is an abridged version of a paper that appeared as Ceylan et al. [2016] in the Proceedings of KR 2016.

Adnan Darwiche and Guy Van den Broeck

Computer Science Department University of California, Los Angeles {darwiche,guyvdb}@cs.ucla.edu

both settings, the output is a predicted fact with its probability. Thus, we need to define a probabilistic semantics for such knowledge bases. The most-basic model is that of tupleindependent probabilistic databases (PDBs) [Suciu et al., 2011], which indeed underlies many of these systems [Dong et al., 2014; Sa et al., 2017]. According to the PDB semantics, each database tuple is an independent Bernoulli random variable, and all other tuples have probability zero, enforcing a closed-world assumption (CWA) [Reiter, 1978].

This paper revisits the choice for the CWA in probabilistic knowledge bases. We observe that the CWA is violated in their deployment, which makes it problematic to reason, learn, or mine on top of these databases. We propose an alternative semantics for probabilistic knowledge bases to address these problems, based on the open-world assumption (OWA), which as opposed to the CWA, does not presume that the knowledge of a domain is complete. Our proposal of open-world probabilistic databases (OpenPDBs) builds on the theory of imprecise probabilities [Levi, 1980] in the sense that all tuples that are not in the knowledge base, called open tuples, take on probabilities from a default probability interval. All facts in the open world remain possible, formalized through lower and upper probabilities, which determines their contribution to the probability of possible worlds. This framework provides more meaningful answers, in terms of upper and lower bounds on the query probability.

Our open-world semantics is supported by a query evaluation algorithm for unions of conjunctive queries (UCQs). This class of queries, corresponding to monotone DNF, is particularly well-behaved and the focal point of database research. Perhaps the largest appeal of PDBs comes from a breakthrough dichotomy result by [Dalvi and Suciu, 2012], perfectly delineating which UCQs can be answered efficiently in the size of the PDB. Their algorithm runs in polynomial time for all efficient queries, called safe queries, and recognizes all others to be #P-hard. Our OpenPDB algorithm extends the PDB algorithm of [Dalvi and Suciu, 2012] and inherits its elegant properties: all safe queries run in polynomial time. When our algorithm fails, the query is #P-hard.

In general, both OpenPDBs and PDBs admit the same data complexity dichotomy between polynomial time and #P. Moreover, a careful analysis shows that both algorithms run in linear time in the number of (closed-world) tuples on a sorted database. Even though OpenPDBs model a polynomially larger set of random variables, these can be reasoned about as a whole, and there is no computational blow-up for openworld reasoning. Therefore, assuming that the database constants are sorted, both OpenPDBs and PDBs admit a stronger data complexity dichotomy between linear time and #P. The fact that safe PDB queries have linear-time data complexity on a sorted database is perhaps not technically surprising, but this has not been observed in the literature before. This observation is quite important practically though, particularly in the context of open-world probabilistic databases.

We focus on the corresponding decision problem of probabilistic query evaluation and thus on the complexity class PP [Gill, 1977], which can be seen as a decision version of #P. Our analysis entails that the complexity of open-world reasoning can go up significantly with negation. We identify a safe PDB query that becomes NP-complete and an unsafe PDB query that becomes NP PP -complete on OpenPDBs. We also consider query evaluation complexity in terms of the domain size, or equivalently, the size of the open world, keeping both the query and the database fixed. Here, complexities range from polynomial time to the unary alphabet class #P1.

2 Preliminaries

Relational Logic. We focus on the function-free finitedomain fragment of first-order logic (FOL). An atom P(t1, . . . , tn) consists of predicate P/n of arity n followed by n arguments, which are either constants from a finite domain D = {a, b, . . . } or logical variables {x, y, . . . }. A ground atom does not contain logical variables. A literal is an atom or its negation. A formula combines atoms with logical connectives and quantifiers ∃ and ∀. A logical variable x is quantified if it is enclosed by a ∀x or ∃x. A free variable is one that is not quantified. We write φ(x, y) to denote that x, y are free in φ. A formula is monotone if it contains no negations. A substitution [x/t] replaces all occurrences of x by t in some formula Q, denoted Q[x/t].

A relational vocabulary σ consists of a set of predicates R and a domain D. We will make use of Herbrand semantics [Hinrichs and Genesereth, 2006], as is customary. The Herbrand base of σ is the set of all ground atoms that can be constructed from R and D. An σ-interpretation is a truthvalue assignment to all the atoms in the Herbrand base of σ, called σ-atoms. An interpretation ω is a model of formula Q when it satisfies Q, defined in the usual way. Satisfaction is denoted by ω ⊧σ Q. We omit σ when clear from context.

Databases and Queries. Following the standard modeltheoretic view [Abiteboul et al., 1995], a relational database for vocabulary σ is a σ-interpretation ω. Figure 1 depicts a relational database in terms of tables. Each table corresponds to a predicate and its rows correspond to ground atoms of that predicate, which are also called records or facts. These atoms are mapped to true, while ones not listed in these tables are mapped to false, according to the CWA [Reiter, 1978].

The fundamental task in databases is query answering. Given a formula Q(x, y, . . . ), the task is to find all substitutions (answers) [x/s, y/t, . . . ] such that ω ⊧ Q[x/s, y/t, . . . ]. Consider for example the query Q1(x, y) for spouses that starred in the same movie:

The database in Figure 1 yields [x/pitt, y/jolie] as the only answer. This formula is an existentially quantified conjunction of atoms, called a conjunctive query (CQ). We concentrate on Boolean conjunctive queries (BQs), which have no free variables. Answers to BQs are either true or false. For example, the BQ

returns true on the database in Figure 1. A Boolean union of conjunctive queries (UCQ) is a disjunction of BQs. We will denote the class of UCQs with negation on atoms by UC ˜Q.

Probabilistic Databases. The simplest probabilistic database model is the one based on the tuple-independence assumption as we adopt here [Suciu et al., 2011].

Definition 1. A probabilistic database (PDB) P for a vocabulary σ is a finite set of tuples of the form ⟨t ∶ p⟩ , where t is a σ-atom and p ∈ [0, 1]. Moreover, if ⟨t ∶ p⟩ ∈ P and ⟨t ∶ q⟩ ∈ P, then p = q.

Figure 2 shows an example PDB. The following semantics is based on the tuple-independence assumption mentioned earlier [Suciu et al., 2011].

Definition 2. A PDB P for vocabulary σ induces a unique probability distribution over σ-interpretations ω:

where

The choice of setting PP(t) = 0 for tuples missing from PDB P is a probabilistic version of the CWA.

Definition 3. The probability of a BQ Q w.r.t. a PDB P is

For example, considering the PDB in Figure 2 and the query Q2 defined earlier, we get PP(Q2) = 0.28.

3 Closed-World PDBs in Practice

As noted by Reiter [1978], CWA presumes a complete knowledge about the domain being represented. We now assess the adequacy of CWA for probabilistic knowledge bases.

Truncating and Space Blow-up. Knowledge completion systems continuously crawl the web, and discover new facts. Nevertheless, they retain only a small fraction of the discovered facts in their knowledge base and facts with a probability below some predefined threshold are simply discarded, which is clearly a misuse of the CWA. As only facts with high-probability are stored in their knowledge base, most of the automatically constructed PDBs are hardly probabilistic. Most tuples have a very high probability, placing PDBs into an almost crisp setting in practice. This mode of operation, however, is not an oversight, but a necessity. It is simply not possible to retain all facts in the knowledge base. Consider, for instance the Sibling relation over a domain of 7 billion people. Storing a single-precision probability for all Sibling facts would require 196 exabytes of memory; two orders of magnitude more than the estimated capacity available to Google [Munroe, 2015].

Distinguishing Queries. Since the CWA is violated in most PDBs, several query answering issues become apparent. Consider, for instance, the queries Q1(pitt, jolie) and Q2. The former query entails the latter, leading us to expect that P(Q2) > P(Q1(pitt, jolie)) in an open-world setting. However, P(Q2) = P(Q1(pitt, jolie)) = 0.28 in the PDB of Figure 2. For another example, consider the queries Q1(w smith, j smith) and Q1(thornton, aniston). The former is supported by two facts in the PDB of Figure 2, while the latter is supported by none, which should make it less likely. However, both evaluate to the probability 0. Taking these observations to the extreme, the query Inmovie(x, y) ∧ ¬Inmovie(x, y) is unsatisfiable, yet it evaluates to the same probability as the satisfiable query Q1(thornton, aniston). These counterintuitive results are not synthetic, but also observed in real-world data.

Knowledge-Base Completion and Mining. The CWA permeates higher-level tasks that one is usually interested in performing on probabilistic databases. For example, a natural approach to knowledge-base completion learns a probabilistic model from training data. Consider, for example, a probabilistic rule [Wang et al., 2013; De Raedt et al., 2015]

To evaluate the quality of this rule for predicting the Costars relation, the standard approach would be to quantify the conditional likelihood of the rule based on training data [Sutton and McCallum, 2011]:

The rule predicts P(Costars(w smith, j smith)) = 0, due to the CWA, since one fact is missing from the knowledge base. Hence, the rule gets a likelihood score of zero, regardless of its performance on other tuples in the training data. Another high-level task is to mine frequent patterns in the knowledge base; for example to find the pattern Q1(x, y) and report it to the data miner. Again, due to the CWA, the frequencies of these patterns will be underestimated [Gal´arraga et al., 2013].

4 Open-World Probabilistic Databases

Our proposal for open-world probabilistic databases is based on the assumption that facts not appearing in a probabilistic database have probabilities in the interval [0,λ], for some threshold probability λ. This is formalized through a credal set [Levi, 1980], which is a set of probability distributions.

Definition 4. An open probabilistic database is a pair G = (P, λ), where P is a probabilistic database and λ ∈ [0, 1].

The semantics of an open probabilistic database (OpenPDB) is based on completing probabilistic databases.

Definition 5. A λ-completion of probabilistic database P is another probabilistic database obtained as follows. For each atom t that does not appear in P, we add tuple ⟨t ∶ p⟩ to P for some p ∈ [0, λ].

While a closed probabilistic database induces a unique probability distribution, an open probabilistic database induces a set of probability distributions.

Definition 6. An open probabilistic database G = (P, λ) induces a set of probability distributions KG such that distribution P belongs to KG iff P is induced by some λ-completion of probabilistic database P.

Note that the set of distributions KG is credal and represents the semantics of OpenPDB G. Intuitively, an OpenPDB represents all possible ways to extend a PDB with new tuples from the open world, with the restriction that the probability of these unknown tuples can never be larger than λ. Thus, query evaluation for OpenPDB yields interval-based answers.

Definition 7. The probability interval of a Boolean query Q in OpenPDB G is KG(Q) = [PG (Q), PG(Q)], where

Reiter [1978] introduced the open-world assumption as the opposite of the CWA. Under the OWA, a set of tuples no longer corresponds to a single interpretation. Instead, a database corresponds to the set of interpretations that extend it. A similar effect is achieved by OpenPDBs: a set of probabilistic tuples no longer corresponds to a single distribution. Instead, a probabilistic database corresponds to the set of distributions that extend it. In restricting the probabilities of open tuples to lie in [0, λ], OpenPDBs follow a rich literature on interval-based probabilities [Halpern, 2003], credal networks [Cozman, 2000] and default reasoning [Reiter, 1980].

5 OpenPDBs in Practice

We now discuss some implications of the open-world setting. Consider the queries Q1 and Q2 again. We have already noted that Q1(pitt, jolie) entails Q2, leading us to expect that P(Q2) > P(Q1(pitt, jolie)) assuming our knowledge is not complete. This is indeed the case for OpenPDBs (for upper probabilities) since there are many worlds with non-zero probability that entail Q2 but not Q1(pitt, jolie). We have also observed that an unsatisfiable query is in some cases as likely as a satisfiable one in the closed world. In the open-world setting, the upper probability of a satisfiable query will be greater than the upper probability of an unsatisfiable query. In fact, any unsatisfiable query will still have a zero upper probability in OpenPDBs. For some real-world examples, based on NELL, we refer the reader to [Ceylan et al., 2016].

The Bayesian learning paradigm is a popular view on machine learning, where the learner maintains beliefs about the world as a probability distribution, and updates these beliefs based on data, to obtain a posterior distribution. In the context of knowledge base completion systems, we observe the following. Given a PDB at time t, such systems gather data D t to obtain a new model Pt+1 P (.) = PtP (. ∣Dt ). Systems continuously add facts f, that is, set Pt+1 P (f) > 0, whereas previously PtP (f) = 0; an impossible induction for Bayesian learning. This problem is resolved by the open database semantics. Now, facts are not a priori impossible, and adding them does not conflict with the prior beliefs.

6 Query Evaluation in OpenPDBs

OpenPDBs model an infinite set of PDBs, and thus, it may seem like an unsurmountable task to efficiently compute intervals KG(Q). Fortunately, the problem is simplified by a strong property of credal sets as we employ them here: probability bounds always come from extreme points [Cozman, 2000]. For OpenPDBs, this means the following.

Definition 8. An extreme distribution P ∈ KG is a distribution where P(t) = PG(t) or P(t) = PG (t) for all tuples t.

Proposition 9. For any OpenPDB G and a query Q, there exist extreme distributions P, P ∈ KG such that P(Q) = PG (Q), and P(Q) = PG(Q).

Thus, for query answering, it suffices to consider a finite set of distributions, which can be represented by λ-completions where the open-world tuples have an extreme probability. As for PDBs, query answering in OpenPDBs is computationally challenging. We first define the decision problem of interest. Definition 10. Given an OPDB G, query Q and probability p, the upper (resp., lower) probabilistic query evaluation prob-

lem is to decide whether PG(Q) ≥ p (resp., PG (Q) < p).

Proposition 9 suggests a naive query answering algorithm: generate all extreme distributions P, compute P(Q), and report the minimum and maximum. This procedure will terminate in time exponential in the number of open-world tuples. For UCQs, however, the monotonicity of the queries allows us to further simplify query evaluation. We can choose the minimal (resp., maximal) bound for every tuple, which minimizes (resp., maximizes) the probability of the UCQ.

Theorem 11. Given OpenPDB G = (P, λ) and UCQ Q, let P ′ = P ∪ {⟨t ∶ λ⟩ ∣ t is an open tuple} be a λ-completion. Then, KG(Q) = [PP(Q), PP ′ (Q)].

Theorem 11 shows that we can reduce OpenPDB query evaluation to query evaluation on PDBs with only a polynomial blow-up in the data size. Unfortunately, this can be impractical for PDBs with a large domain. A more goal-oriented algorithm, described next, avoids this blow-up.

7 Overview of the Results and Outlook

Lifted Inference. OpenPDBs is supported with an efficient lifted inference algorithm LiftRO, which is an adaptation of the LiftR algorithm presented in Gribkoff et al. [2014]. This algorithm assumes that the database is sorted and the query is ranked as in [Dalvi and Suciu, 2012] and can compute the probability of a query in time linear in the size of the data. The main difference between LiftRO and LiftR is in the treatment of the open tuples. Although OpenPDBs model a polynomially larger set of random variables, due to the symmetries, these can be reasoned about as a whole, and there is no computational blow-up for open-world reasoning.

Data Complexity. Our key complexity results are illustrated in Figure 3. Briefly, the decision problem of UCQ query evaluation either has linear time data complexity or is PP-complete on a sorted database, depending on the query. This implies a dichotomy between polynomial time and PP. Moreover, these complexities are the same for PDBs and OpenPDBs. For queries with negation, some safe PDBs queries can remain safe, and some can become NP-complete on OpenPDBs. Some UC ˜Qs that are PP-complete on PDBs can remain PP-complete, and some can become NP PP -complete. Domain Complexity. The domain complexity of OpenPDB query evaluation is the complexity for a fixed query and database, as a function of the size of the domain D. Beame et al. [2015] study this complexity in the context of a task called weighted first-order model counting. This task is reducible to OpenPDB query evaluation when the database is empty. We refer to Beame et al. [2015] for full details, but note that there exists an FO3 query and set of probabilistic tuples with #P1-

complete domain complexity on OpenPDBs.

Outlook. A key challenge is to restrict the open world to exclude spurious possible worlds, and thus limit the probability mass of open tuples. One way of restricting the models is to pose constraints on the probability distributions. Another approach is to use an explicit formalism for restricting the models such as ontological rules [Borgwardt et al., 2017].

Acknowledgements

We thank Lakshay Rastogi for his help. This work is partially supported by NSF grants #IIS-1514253, #IIS-1657613, #IIS1633857, ONR grant #N00014-15-1-2339, and DARPA XAI grant #N66001-17-2-4032. ˙Ismail ˙Ilkan Ceylan is supported by the DFG (GRK 1907). This research was conducted when he was a visiting student at UCLA.