On Constrained Open-World Probabilistic Databases
Tal Friedman Guy Van den Broeck


The phenomenology of beyond Horndeski gravity
    [
    Received January 31, 2019; accepted February 25, 2019
=========================================================




    Increasing amounts of available data have led to a heightened need for representing large-scale probabilistic knowledge bases. One approach is to use a probabilistic database, a model with strong assumptions that allow for efficiently answering many interesting queries. Recent work on open-world probabilistic databases strengthens the semantics of these probabilistic databases by discarding the assumption that any information not present in the data must be false. While intuitive, these semantics are not sufficiently precise to give reasonable answers to queries. We propose overcoming these issues by using constraints to restrict this open world. We provide an algorithm for one class of queries, and establish a basic hardness result for another. Finally, we propose an efficient and tight approximation for a large class of queries.





§ INTRODUCTION

An ubiquitous pursuit in the study of knowledge base representation is the search for a model that can represent uncertainty while simultaneously answering interesting queries efficiently. The key underlying challenge is that these goals are at odds with each other. Modelling uncertainty requires additional model complexity. At the same time, the ability to answer meaningful queries usually demands fewer model assumptions. Both of these properties are at odds with the key limiting factor of tractability: success in the first two goals is not nearly as impactful if it is not achieved efficiently. Unfortunately, probabilistic reasoning is often computationally hard, even on databases <cit.>.

One approach towards achieving this goal is to begin with a simple model such a probabilistic database (PDB) <cit.>. A PDB models uncertainty, but is inherently simple and makes very strong independence assumptions and closed-world assumptions allowing for tractability on a very large class of queries <cit.>. However, PDBs can fall short under non-ideal circumstances, as their semantics are brittle to incomplete knowledge bases <cit.>.

To bring PDBs closer to the desired goal, <cit.> propose open-world probabilistic databases (OpenPDB), wherein the semantics of a PDB are strengthened to relax the closed-world assumption. While OpenPDBs maintain a large class of tractable queries, their semantics are so relaxed these queries lose their precision: they model further uncertainty, but in exchange give less useful query answers.

In this work, we aim to overcome these querying challenges, while simultaneously maintaining the degree of uncertainty modeled by OpenPDBs. To achieve this, we propose further strengthening the semantics of OpenPDBs by constraining the mean probability allowed for a relation. These constraints work at the schematic level, meaning no additional per-item information is required. They are practically motivated by knowledge of summary statistics, of how many tuples we expect to be true. A theoretical analysis shows that, despite their simplicity, such constraints fundamentally change the difficulty landscape of queries, leading us to propose a general-purpose approximation scheme.

The rest of the paper is organized as follows: Section <ref> provides necessary background on relational logic and PDBs, as well as an introduction to OpenPDBs. Section <ref> motivates and introduces our construction for constraining OpenPDBs. Section <ref> analyses exact solutions subject to these constraints, providing a class of tractable queries along with an algorithm. It also shows that the problem is in general hard, even in some cases where standard PDB queries are tractable. Section <ref> investigates an efficient and provably bounded approximation scheme. Section <ref> discusses our findings, and summarizes interesting directions that we leave as open problems.




§ BACKGROUND
 

This section provides background and motivation for probabilistic databases and their open-world counterparts. 
Notation and definitions are adapted from <cit.>.



 §.§ Relational Logic and Databases

We now describe necessary background from function-free finite-domain first-order logic. An atom R(x_1,x_2,...,x_n) consists of a predicate R of arity n, together with n arguments. These arguments can either be constants or variables. A ground atom is an atom that contains no variables. A formula is a series of atoms combined with conjunctions () or disjunctions (), and with quantifiers ∀, ∃. A substitution [x/t] replaces all occurences of x by t in a formula .

A relational vocabulary σ is comprised of a set of predicates  and a domain . Using the Herbrand semantics <cit.>, the Herbrand base of σ is the set of all ground atoms possible given  and . A σ-interpretation ω is then an assignment of truth values to every element of the Herbrand base of σ. We say that ω models a formula  whenever ω satisfies . This is denoted by ω.




A reasonable starting point for the target knowledge base to construct would be to use a traditional relational database. Using the standard model-theoretic view <cit.>, a relational database for a vocabulary σ is a σ-interpretation ω. Less formally, a relational database consists of a series of relations, each of which corresponds to a predicate. Each relation consists of a series of rows, also called tuples, each of which corresponds to an atom of the predicate being true. Any atom not appearing as a row in the relation is considered to be false, following the closed-world assumption <cit.>. Figure <ref> shows an example database. 



 §.§ Probabilistic Databases





Despite the success of relational databases, their deterministic nature leads to a few shortcomings. A common way to gather a large knowledge base is to apply some sort of statistical model <cit.> which returns a probability value for potential tuples. Adapting the output of such a model to a relational database involves thresholding on the probability value, discarding valuable information along the way. A probabilistic database (PDB) circumvents this problem by assigning each tuple a probability.

    

 A (tuple-independent) probabilistic database  for a vocabulary σ is a finite set of tuples of the form ⟨t: p⟩ where t is a σ-atom and p∈ [0,1]. Furthermore, each t can appear at most once. 


Given such a collection of tuples and their probabilities, we are now going to define a distribution over relational databases. The semantics of this distribution are given by treating each tuple as an independent random variable.


  A probabilistic database  for vocabulary σ induces a probability distribution over σ-interpretations ω:
  
    P_(ω) = ∏_t ∈ω P_(t) ∏_t ∉ω (1-P_(t))
        where     P_(t) = 
          
          p    if ⟨ t:p ⟩∈
    
          0    otherwise



Notice this last statement is again making the closed-world assumption: any tuple that we have no information about is assigned probability zero. Figure <ref> shows an example PDB.





  
Probabilistic Queries
In relational databases, the fundamental task we are interested in solving is how to answer queries. The same is true for probabilistic databases, with the only difference being that we are now interested in probabilities over queries. In particular, we are interested in queries that are fully quantified - also known as Boolean queries. On a relational database, this corresponds to a query that has an answer of True or False.

For example, on the database given in Figure <ref>, we might ask if there is a scientist who is a coauthor:

    _1 = ∃ x. ∃ y. S(x) 𝐶𝑜𝐴(x,y)



If we instead asked this query of the probabilistic database in Figure <ref>, we would be computing the probability by summing over the worlds in which the query is true:

    P(_1) = ∑_ω_1 P_(ω)


Queries of this form that are a conjunction of atoms are called conjunctive queries. They are commonly shortened as:

    _1 = S(x), 𝐶𝑜𝐴(x,y).



A disjunction of conjunctive queries is known as a union of conjunctive queries (UCQ). UCQs have been shown to live in a dichotomy of efficient evaluation <cit.>: computing the probability of a UCQ is either polynomial in the size of the database, or it is #P-hard. This property can be checked through the syntax of a query, and we say that a UCQ is safe if it admits efficient evaluation. In the literature of probabilistic databases <cit.>, as well as throughout the rest of this paper, UCQs are the primary query object studied.













 §.§ Open-World Probabilistic Databases

In the context of automatically constructing a knowledge base, as is done in for example NELL <cit.> or Google's Knowledge Vault <cit.>, making the closed-world assumption is conceptually unreasonable. Conversely, it is also not feasible to include all possible tuples and their probabilities in the knowledge base. The resulting difficulty is that there are an enormous number of probabilistic facts that can be scraped from the internet, and by definition these tools will keep only those with the very highest probability. As a result, knowledge bases like NELL <cit.>, PaleoDeepDive <cit.>, and YAGO <cit.> consist almost entirely of probabilities above 0.95. This tells us that the knowledge base we are looking at is fundamentally incomplete. In response to this problem, <cit.> propose the notion of a completion for a probabilistic database.


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


Then, we can define the open world of possible databases in terms of the set of distributions induced by all completions.

  An open-world probabilistic database (OpenPDB) is a pair =(, λ),
  where  is a probabilistic database and λ∈ [0,1].  induces a set of probability distributions
 K_ such that a distribution P belongs to K_ iff P is induced by
 some λ-completion of probabilistic database . 





  
Open-World Queries
OpenPDBs specify a set of probability distributions rather than a single one, meaning that a given query produces a set of possible probabilities rather than a single one. We focus on computing the minimum and maximum possible probability values that can be achieved by completing the database. 

  The probability interval of a Boolean query  in OpenPDB  is
  K_()=[P_(), P_()], where
  
    P_()=min_P∈ K_P()       P_()=max_P∈ K_P()]



In general, computing the probability interval for some first-order  is not
tractable. As observed in <cit.>, however, the situation is different for UCQ queries, because they are monotone (they contain no negations). For UCQs, the upper and lower bounds are given respectively by the full completion
(where all unknown probabilities are λ), and the closed world
database. This is a direct result of the fact that OpenPDBs form a credal set: a closed convex set of probability measures, meaning that probability bounds always come from extreme points <cit.>.
Furthermore, <cit.> also provide an algorithm for efficiently computing this upper bound corresponding to a full completion, and show that it works whenever the UCQ is safe.



§ MEAN-CONSTRAINED COMPLETIONS


This section motivates the need to strengthen the OpenPDB semantics, and introduces our novel probabilistic data model.



 §.§ Motivation

The ability to perform efficient query evaluation provides an appealing case for OpenPDBs.
They give a more reasonable semantics, better matching their use, and for a large class of queries they come at no extra cost in comparison to traditional PDBs. 
However, in practice computing an upper bound in this
way tends to give results very close to 1. Intuitively, this makes sense: our upper bound comes from simultaneously assuming that every possible missing atom has some reasonable probability. While such a bound is easy to compute, it is too strong of a relaxation of the closed-world assumption.

The crux of this issue is that OpenPDBs consider every possible circumstance for unknown tuples: even ones that are clearly unreasonable. For example, suppose that a table in our database describes whether or not a person is a scientist. The OpenPDB model considers the possibility that every person it knows nothing about has a nontrivial probability of being a scientist - this will clearly return nonsensical query results as we know that fewer than 1% of the population are scientists.

In order to consider a restricted subset of completions representing reasonable situations, we propose directly incorporating these summary statistics. Specifically, we place constraints on the overall probability of a relation across the entire population. In the scientist example, our model only considers completions in which the total probability mass of people being scientists totals less than 1%. This allows us to include more information at the schema level, without having more information about each individual.









To illustrate the effect this has, consider a schema in which we have 3 relations: 𝐿𝑖𝐿𝐴(x) denoting whether one lives in Los Angeles, 𝐿𝑖𝑆𝑝𝑟(x) denoting whether one lives in Springfield, and S(x) denoting whether one is a scientist. Using a vocabulary of 500 people where each person is present in at most one relation, Table <ref> shows the resulting upper probability bound under different model assumptions, where the constrained open-world restricts at most 50% of mass on 𝐿𝑖𝐿𝐴, 5% on S, and 0.5% on 𝐿𝑖𝑆𝑝𝑟. In particular, notice how extreme the difference is in upper bound with and without constraints being imposed. The closed-world probability of both of these queries is always 0, as each person in our database only has a known probability for at most one relation. It is clear that of these three options, the constrained open-world is the most reasonable – the rest of this section formalizes this idea and investigates the resulting properties.





 §.§ Formalization

We begin here by defining mean based constraints, before examining some
immediate observations about the structure of the resulting constrained
database.


  
Suppose we have a PDB , and let 𝑇𝑢𝑝(R) ⊆ be the set of probabilistic tuples in relation R. Let p̅ be a probability threshold. 
Then a mean tuple probability constraint (MTP constraint) φ is a linear constraint of the form

    p̅ > 1/|𝑇𝑢𝑝(R)|∑_⟨ t:p ⟩∈𝑇𝑢𝑝(R) p







  We say that a λ-completion is φ-constrained if the
  λ-completed database satisfies MTP φ. If it satisfies all of
  Φ=(φ_1, φ_2, ..., φ_n), then we say it is Φ-constrained.


Being φ-constrained is not a property of OpenPDBs, but of their PDB completions. Hence, we are interested in the subset of completions
that satisfy this property.


 An OpenPDB =(, λ) together with MTP constraints Φ induces a
 set of probability distributions K_^Φ , where distribution P belongs
 to K_^Φ iff P is induced by some Φ-constrained
 λ-completion of .


Much like with standard OpenPDBs, for a Boolean query  we are
interested in computing bounds on P().


 The probability interval of a Boolean query  in OpenPDB  with MTP
 constraints Φ is ()=[P_^Φ(),
 P_^Φ()], where
 
    P_^Φ()=min_P∈P()       P_^Φ()=max_P∈P()]






 §.§ Completion Properties


A necessary property of OpenPDBs for efficient query evaluation is that they are credal – this is what allows us to consider only a finite subset of possible completions. MTP-constrained OpenPDBs maintain this property.[Proofs of all theorems and lemmas are given in the appendix]


  
  Suppose we have an OpenPDB  together with MTP constraints Φ. Then
  the induced set of probability distributions  is credal.


This property allows us to examine only a finite subset of configurations when
looking at potential completions, since query probability bounds of a credal set are always achieved at points of extrema <cit.>. Next, we would like to characterize these points
of extrema, by showing that the number of tuples not on their own individual
boundaries (that is, 0 or λ) is given by the number of MTP constraints.


  
    Suppose we have an OpenPDB =(, λ) with MTP constraints Φ, and a
  UCQ Q. If ' is a Φ-constrained λ-completion satisfying ()=[P_(),P_'()], there exist
  completed tuples
  ⊆' ∖ with || ≤ |Φ| such that
  
    ∀ ⟨ t:p⟩∈   :   p ∈ [0,λ],  and 
    ∀ ⟨ t:p⟩∈(' ∖) ∖   :   p ∈{0,λ}.


That is, our upper bound is given by a
completion that has at most |Φ| added tuples with probability not exactly
0 or λ. Intuitively, each MTP constraint contributes a single non-boundary tuple, which can be thought of as the “leftover” probability mass once the rest has been assigned in full.

This insight allows us to treat MTP query evaluation as a combinatorial optimization problem for the rest of this paper. Thus, we only consider the case where achieving the mean tuple probability exactly leaves us with every individual tuple at its boundary. To see that we can do this, we observe that Theorem <ref> leaves a single tuple per MTP constraint not necessarily on the boundary. But this tuple can always be forced to be on the boundary by very slightly increasing the mean  p̅ of the constraint, as follows.


Suppose we have an OpenPDB =(, λ) with MTP constraints Φ, and a UCQ . 
Suppose further that each relation in  has at most 1 constraint in Φ, and that each constraint allows adding open-world probability mass exactly divisible by λ.  
Then if ' is a Φ-constrained λ-completion of  with ()=[P_(),P_'()], we have

    ∀⟨ t : p ⟩∈' ∖:   p ∈{0,λ}.



Our investigation into the algorithmic properties of MTP query evaluation will be focused on constraining a single relation, subject to a single combinatorial budget constraint. 
 
 

§ EXACT MTP QUERY EVALUATION
 
 With Section <ref> formalizing MTP constraints and showing that computing upper bounds subject to MTP constraints is a combinatorial problem of choosing which λ-probability tuples to add in the completion, we now investigate exact solutions.
 
 

 §.§ An Algorithm for Inversion-Free Queries

 We begin by describing a class of queries which admits poly-time evaluation subject to an MTP constraint. We first need to define some syntactic properties of queries.
 

 Let  be a conjunctive query, and let at(x) denote the set of relations containing variable x. We say that  is hierarchical if for any x,y, we have either at(x) ⊆ at(y), at(y) ⊆ at(x), or at(x) ∩ at(y) = ∅. 
 

Intuitively, a conjunctive query being hierarchical indicates that it can either be separated into independent parts (the at(x) ∩ at(y) = ∅ case), or there is some variable that appears in every atom. This simple syntactic property is the basis for determining whether query evaluation on a conjunctive query can be done in polynomial time <cit.>. We can further expand on this definition in the context of UCQs.


 A UCQ  is inversion-free if each of its conjuncts is hierarchical, and they all share the same hierarchy.[See <cit.> for a more detailed definition.] If  is not inversion-free, we say that it has an inversion.


This query class remains tractable under MTP constraints.


   For any inversion-free query , evaluating the probability P_^Φ() subject to an MTP constraint is in PTIME.


In order to prove Theorem <ref>, we provide a polytime algorithm for MTP query evaluation on inversion-free queries. As with OpenPDBs, our algorithm depends on Algorithm <ref>, the standard lifted inference algorithm for PDBs. Algorithm <ref> proceeds in steps recursively processing  to compute query probabilities in polynomial time for safe queries <cit.>. Further details of the algorithm including the necessary preprocessing steps and notation can be found in <cit.> and <cit.>.



 

We now present an algorithm for doing exact MTP query evaluation on inversion-free queries. For brevity, we present the binary case; the general case follows similarly and can be found in appendix. Suppose that we have a probabilistic database , a domain T of constants denoted c, a query , and an MTP constraint on relation R(x, y) allowing us to add exactly B tuples with probability λ. Suppose that  immediately reaches Step 5 of Algorithm <ref> (other steps will be discussed later), implying that x and y are unique variables in the query. We let A(c_x,c_y,b) denote the upper query probability of (x/c_x, y/c_y) subject to an MTP constraint allowing budget b on the relevant portion of R. That is, A tells us the highest probability we can achieve for a partial assignment given a fixed budget. Observe that we can compute all entries of A using a slight modification of Algorithm <ref> where we compute probabilities with and without each added tuple. 
This will take time polynomial in |T|.

Next, we impose an ordering c_1, …, c_|T| on the domain. Then we let D(j, c_y, b) denote the upper query probability of

    ⋁_c ∈{c_1, … c_j}(x/c, y/c_y)

with a budget of b on the relevant portions of R. Then D(|T|, c_y, b) considers all possible substitutions in our first index, meaning we have effectively removed a variable. Doing this repeatedly would allow us to perform exact MTP query evaluation. However, D is non-trivial to compute, and cannot be done by simply modifying Algorithm <ref>. Instead, we observe the following recurrence:

    D(j+1, y/c_y, b)  = 
           max_k ∈{1,…,b} 1 - D(j, y/c_y, b-k) · A(x/c_j+1, y/c_y, k).


Intuitively, this recurrence says that since the tuples from each fixed constant are all independent, we do not need to store which budget configuration on the first j constants got us our optimal solution. Thus, when we add the j+1th constant, we just need to check each possible value we could assign to our new constant, and see which gives the overall highest probability. This recurrence can be implemented efficiently, yielding a dynamic programming algorithm that runs in time polynomial in the domain size and budget.

 Finally, we would like to generalize this algorithm beyond assuming that  immediately reaches Step 5 of Algorithm <ref>. Looking at other cases, we see that Steps 0 and 1 have no effect on this recurrence, and Steps 2 and 4 correspond to multiplicative factors. For a query that reaches Step 3 (inclusion-exclusion), we need to construct such A and D for each term in the inclusion-exclusion sum, and follow the analogous recurrence. Notice that the modified algorithm would only work in the case where we can always pick a common variable for all sub-queries to do dynamic programming on – that is, when the query is inversion-free, as was our assumption.







 
 
 

 §.§ Queries with Inversion
 
We now show that allowing for inversions in safe queries can cause MTP query evaluation to become NP-hard. Interestingly, this means that MTP constraints fundamentally change the difficulty landscape of query evaluation.

To show this, we investigate the following UCQ query.
 
    M_0 = ∃ x∃ y∃ z    (R(x,y,z) U(x) )
                    (R(x,y,z)  V(y)) 
       (R(x,y,z)  W(z) )
                    (U(x) V(y) )
       (U(x) W(z) )
                    (V(y) W(z))


A key observation here is that the query M_0 is a safe UCQ. That is, if we ignore constraints and evaluate it subject to the closed- or open-world semantics, computing the probability of the query would be polynomial in the size of the database. We now show that this is not the case for open-world query evaluation subject to a single MTP constraint on R.


Evaluating the upper query probability bound P_^Φ(M_0)  subject to an MTP constraint Φ on R is NP-hard.


The full proof of Theorem <ref> can be found in appendix, showing a reduction from the NP-complete 3-dimensional matching problem to computing P_^Φ(M_0) with an MTP constraint on R. It uses the following intuitive correspondence.


  Let X, Y, Z be finite disjoint sets representing nodes, and let T⊆ X × Y × Z be the set of available hyperedges. Then M⊆ T is a matching if for any distinct triples (x_1,y_1,z_1) ∈ M, (x_2, y_2,z_2) ∈ M, we have that x_1  x_2, y_1  y_2, z_1  z_2. The 3-dimensional matching decision problem is to determine for a given X, Y, Z, T and positive integer k if there exists a matching M with |M| ≥ k.

 
 The set of available tuples for R will correspond to all edges in T. Our MTP constraint forces a decision on which subset of T to take and include in the λ-completion. 
 
 However, if we simply queried to maximize P(R(x,y,z)), this completion need not correspond to a matching. Instead, we have the conjunct R(x,y,z) U(x) which is maximized when each tuple chosen from R has a different x value. Similar conjuncts for y and z ensure that the query is maximized when using distinct y and z values. Putting all of these together ensures that the query probability is maximized when the subset of tuples chosen to complete R form a matching.

 Finally, the last part of the query (U(x)  V(y))  (U(x)  W(z))  (V(y)  W(z)) ensures that inference on M_0 is tractable, but it is unaffected by the choice of tuples in R.


 










































§ APPROXIMATE MTP QUERY EVALUATION
 
With Section <ref> answering definitively that a general-purpose algorithm for evaluating MTP query bounds is unlikely to exist, even when restricted to safe queries, an approximation is the logical next step. We now restrict our discussion to situations where we constrain a single relation, and dig deeper into the properties of MTP constraints to show their submodular structure. We then exploit this property to achieve efficient bounds with guarantees.




 §.§ On the Submodularity of Adding Tuples
 
To formally define and prove the submodular structure of the problem, we analyze query evaluation as a set function on adding tuples. 
We begin with a few relevant definitions.



   Suppose that we have an OpenPDB , with an MTP constraint φ  on a single relation
   R, and we let  be the set of possible tuples we can add to R.
   Then the set query probability function S_, :
   2^→ [0,1] is defined as
   
    S_,(X) = P_∪{⟨ t:λ⟩ | t ∈ X}().

   
 

Intuitively, this function describes the probability of the query as a function of which
open tuples have been added.
It provides a way to reason about the combinatorial properties of this optimization problem.  
Observe that S_,(∅) is the closed-world probability of the query, while S_,() is the open-world probability.

We want to show that S_, is a submodular set function.

A submodular set function is a function f: 2^Ω→ℝ
such that for every X⊆ Y ⊆Ω, and every x
∈Ω∖ Y, we have that f(X∪{x}) - f(X) ≥ f(Y ∪{x})
- f(Y).  




The set query probability function S_, is submodular for any tuple
independent probabilistic database  and UCQ query  without self-joins.


This gives us the desired submodularity property, which we can exploit to build efficient approximation algorithms.
 


 §.§ From Submodularity to Approximation

Given the knowledge that the probability of a safe query without self-joins is submodular in the completion of a single relation, we are now tasked with using this to construct an efficient approximation.
Since we further know the probability is also monotone as we have restricted our language to UCQs, <cit.> tells us that we
can get a 1-1/e approximation using a simple greedy algorithm. The final requirement to achieve the approximation described in <cit.> is that our set function must have the property that f(∅)=0. This can be achieved in a straightforward manner as follows.


   In the context of the set query probability function of Definition <ref>, the normalized set query probability function S'_, :
   2^→ [0,1] is defined as
   
    S'_,(X) = P_∪{⟨ t:λ⟩ | t ∈ X}() - P_().

 
 
 
 Any normalized set query probability function S'_, is monotone, submodular, and satifies S'_,(∅) = 0.
 

By simply normalizing the set query probability function, we can now directly apply the greedy approximation described in <cit.>. We slightly modify Algorithm <ref> to efficiently compute the next best tuple to add based on the current database, and add it. This is repeated until adding another tuple would violate the MTP constraint. Finally, we say that P_𝐺𝑟𝑒𝑒𝑑𝑦() is the approximation given by this greedy algorithm and recall that the true upper bound is P_^Φ(). We observe that P_𝐺𝑟𝑒𝑒𝑑𝑦() ≤P_^Φ(). Furthermore, <cit.> tells us the following:

    P_𝐺𝑟𝑒𝑒𝑑𝑦() - P_() ≥ (1-1/e)(P_^Φ() - P_())


Combining these and multiplying through gives us the following upper and lower bound on the desired probability.

    P_𝐺𝑟𝑒𝑒𝑑𝑦() ≤P_^Φ() ≤e· P_𝐺𝑟𝑒𝑒𝑑𝑦() - P_()/e-1


It should be noted that depending on the query and database, it is possible for this upper bound to exceed 1.



§ DISCUSSION, FUTURE & RELATED WORK
 


We propose the novel problem of constraining open-world probabilistic databases at the schema level, without having any additional ground information over individuals. We introduced a formal mechanism for doing this, by limiting the mean tuple probability allowed in any given completion, and then sought to compute bounds subject to these constraints. We now discuss remaining open problems and related work.

Section <ref> showed that there exists a query that is NP-hard to compute exactly, and also presented a tractable algorithm for a class of inversion-free queries. The question remains how hard the other queries are - in particular, is the algorithm presented complete. Is there a complexity dichotomy, that is, a set of syntactic properties that determine the hardness of a query subject to MTP constraints.
Questions of this form are a central object of study in probabilistic databases. 
It has been explored for conjunctive queries <cit.>, UCQs <cit.>, and a more general class of queries with negation <cit.>.

The central goal of our work is to find stronger semantics based on OpenPDBs, while still maintaining their desirable tractability. This notion of achieving a powerful semantics while maintaining tractability is a common topic of study. <cit.> study this problem by using a probabilistic interpretation of logic programs to define a model, leading to powerful semantics but a more limited scope of tractability <cit.>. The description logics <cit.> is a knowledge representation formalism that can be used as the basis for a semantics. This is implemented in a probabilistic setting in, for example, probabilistic ontologies <cit.>, probabilistic description logics <cit.>, probabilistic description logic programs <cit.>, or the bayesian description logics <cit.>.

Probabilistic databases in particular are of interest due to their simplicity and practicality. Foundational work defines a few types of probabilistic semantics, and provides efficient algorithms as well as when they can be applied <cit.>. These algorithms along with practical improvements are implemented as industrial level systems such as MystiQ <cit.>, SPROUT <cit.>, MayBMS <cit.>, and Trio which implements the closely related Uncertainty-Lineage Databases <cit.>. Problems outside of simple query evaluation are also points of interest for PDBs, for example the most probable database <cit.>, or of ranking the top-k results <cit.>. In the context of OpenPDBs in particular, <cit.> study the notion of an infinite open world, using techniques from analysis to explore when this is feasible.







§ ACKNOWLEDGEMENTS

The authors thank Yitao Liang and YooJung Choi for helpful feedback. This work is partially supported by NSF grants #IIS1657613, #IIS-1633857, #CCF-1837129, DARPA XAI grant
#N66001-17-2-4032, NEC Research and a gift from Intel.


named










§ PROOFS OF THEOREMS, LEMMAS, AND PROPOSITIONS



 §.§ Proof of Proposition <ref>


  To prove this, we need to show that  is both closed and convex.
  
  Due to the way our constraints are defined, we know that =K_∩ K^Φ, where K^Φ is the set of all completions satisfying Φ (but
  not necessarily having all tuple probabilities ≤λ). We already know
  that K_ is credal, and thus closed and convex. K^Φ is a half-space,
  which we also know is closed and convex. The intersection of closed spaces is closed, and the intersection of convex spaces is convex, so  is credal.




 §.§ Proof of Theorem <ref>



  Since  is credal, we are interested here in determining the point of
  extrema of , as this will tell us precisely which completions can
  represent boundaries.

  Consider the construction of the set , and suppose that there are d possible open-world tuples, meaning that ⊆ℝ^d. As we observed in the proof of Theorem <ref>, = K_∩ K^Φ, where K^Φ is the set of all completions satisfying Φ. We now make three key observations about these sets:
  
      
  * Each individual possible open-world tuple is described by the intersection of 2 half-spaces: that is, the tuple on dimension i is described by x_i ≥ 0 and x_i ≤λ. K_ is the intersection of all 2d of these half-spaces.
      
  * For any individual open-world tuple, the boundaries of the two half-spaces that describe it cannot intersect each other.
      
  * An MTP constraint is a linear constraint, and thus can be described by a single half-space. So K^Φ is described by the intersection of these |Φ| half-spaces.
  
  
  Observations 1 and 3, together with Lemma <ref> tells us that any point of extrema of  must be given by the intersection of the boundaries of at least d of the half-spaces that form . Observation 3 tells us that at most |Φ| of these half-spaces come from MTP constraints, leaving the boundaries of at least d-|Φ| half-spaces which come from K_. Finally, observation 2 tells us that each of these d-|Φ| half-spaces is describing a different open world tuple. But this means we must have at least d-|Φ| tuples which lie on the boundary of one of their defining half-spaces: they must be either 0 or λ. 
  






 §.§ Proof of Theorem <ref>

Before we present the formal proof, we state and prove 2 Lemmas we will need.
 
 
 
    Suppose we have two completions P_1 and P_2 of R, which only differ on a single triple, that is P_1 = P_0 ∪{x_1, y_1, z_1} and P_2 = P_0 ∪{x_2, y_2, z_2}. Further suppose that y_1=y_2, z_1=z_2, and that P_0 contains no triples with x-value x_1, but does contain at least 1 triple with x-value x_2. Then P_1(M_0) > P_2(M_0).
 
 
   We will apply a similar technique here to the one used to prove Theorem <ref>, where we directly examine Δ, the logical formula found by grounding M_0. Since M_0 is a union of conjunctive queries, Δ must be a DNF. Each conjunct either does not contain R, in which case it does not vary with the choice of completion, or it contains it exactly once. Any conjunct containing an atom of R not assigned probability by a completion is logically false.
   
   In order to prove that P_1(M_0) > P_2(M_0), let us compare the ground atoms that result from each. It is clear that the only spot on which they differ is on conjuncts involving R(x_1,y_1,z_1) or R(x_2,y_1,z_1). Any conjuncts involving one of these and V or W will also have an identical effect on the probability of the query, since the completions are identical over y and z.
   
   Finally this means we need to compare the term R(x_1,y_1,z_1),U(x_1) with the term R(x_2,y_1,z_1),U(x_2). Observe that we know P_0 contains triples with x-value x_2, which means the term only contributes new probability mass when U(x_2) is true and none of the other triples involving x_2 are true. However, P_0 does not contain any triples with x-value x_1, so the term R(x_1,y_1,z_1),U(x_1) contributes the maximum probability possible. Thus, for any choice of probabilities on U such that U(x_2)<1, we have that P_1(M_0) > P_2(M_0).
 
 
 
 
 The upper bound P(M_0) is maximized if and only if P is a completion formed by a matching of size k, where k is the maximum number of tuples with probability λ that can be added to R in M_0.
 
  
   Observe that if we begin with a completion given by a matching, we can repeatedly apply Lemma <ref> to arrive at any completion. Thus a completion given by a matching must have higher probability than any completion not given by a matching.
 


Finally, we are ready to present the proof of Theorem <ref>.
 
 
 Suppose we are given an instance of a 3-dimensional matching problem X,Y,Z,T and an integer k. Let U(x), V(y), W(z) be 0.8 wherever x ∈ X, y ∈ Y, or z ∈ Z respectively, and 0 everywhere else. Additionally, let R(x,y,z) be unknown for any (x,y,z) ∈ T, and 0 otherwise. Finally, we place an MTP constraint on R ensuring that at most k tuples can be added, and let λ = 0.8. Then Lemma <ref> tells us that M_0 evaluated on this database will be maximized if and only if the completion used corresponds to a matching of size k. We determine this probability P_max using a standard probabilistic database query algorithm, and fixing R to have entries 0.8 for some disjoint set of triples.
 
 Finally, we use our oracle for MTP constrained query evaluation to check P(M_0) with the database we constructed from the matching problem. We compare the upper bound given by the oracle, and if it is equal to P_max, Lemma <ref> tells us that a matching of size k does exist. Similarly, if the upper bound given by the oracle is lower than P_max, Lemma <ref> tells us a matching of size k does not exist.
 
 


 



  
  If S ⊆ℝ^n is a set formed by the intersection of k<n
  half-spaces, S has no points of extrema. 



  Written as a set of linear equalities, the solution clearly must have at least
  1 degree of freedom. This indicates that for any potential extrema point x,
  one can move in either direction along this degree of freedom to construct an
  open line intersecting x, but entirely contained in S.





 §.§ Proof of Theorem <ref>


Without directly computing probabilities, let us inspect Δ, the logical
formula we get by grounding .  is a union of conjunctive
queries, and thus Δ is a very large disjunction of conjuncts. Each conjunct can
contain our constrained relation R at most once due to the query not having self-joins, and any one of these conjuncts
containing an atom of R not assigned any probability is logically false.

Next, to show that S_, is submodular, let X ⊆ Y
⊆, and let x ∈∖ Y be given. We assign names
to the following subformulas of Δ


  – α (β) is the disjunction of all conjuncts of Δ which are not logically false due to missing R_B tuples
  in X (Y)

  – γ is the disjunction of all conjuncts of Δ containing
  the tuple x




Additionally, since X ⊆ Y, we
also know that α⇒β.  Now, we make a few observations relating
these quantities with our desired values for submodularity:


  – S_, (X) = P(α)

  – S_, (Y) = P(β)

  – S_, (X ∪{x}) = P(αγ)

  – S_, (Y ∪{x}) = P(βγ)


Finally, we have the following:

    S_, (X ∪{x}) - S_, (X)    = P(αγ) - P(α) 
       = P(αγ) 
       ≥ P(βγ) 
       = P(βγ) - P(β) 
       = S_, (Y ∪{x}) - S_, (Y)



 



§ GENERAL ALGORITHM FOR INVERSION-FREE QUERIES

We now present an algorithm for doing exact MTP query evaluation on inversion-free queries. Suppose that we have a probabilistic database , a domain T of constants denoted c, a query , and an MTP constraint on relation R(x_1, x_2, …, x_r) allowing us to add B tuples. For any I ⊆{1,…,r}, we let A(x_i_1/c_i_1, x_i_2/c_i_2,…, x_i_|I|/c_i_|I|, b) denote the upper query probability of (x_i_1/c_i_1, x_i_2/c_i_2,…, x_i_|I|/c_i_|I|) subject to an MTP constraint allowing budget b on the relevant portion of R. That is, A tells us the highest probability we can achieve for a partial assignment given a fixed budget. Observe that we can compute all entries of A using a slight modification of Algorithm <ref>. This will take time polynomial in |T|.

Next, we impose an ordering c_1, c_2, …, c_|T| on the domain. For any I ⊆{1,…,r}, we let D(j, x_i_2/c_i_2,…, x_i_|I|/c_i_|I|, b) denote the upper query probability of

    ⋁_c ∈{c_1, … c_j}(x_i_1/c, x_i_2/c_i_2,…, x_i_|I|/c_i_|I|)


with a budget of b on the relevant portions of R. Then D(|T|, x_i_2/c_i_2,…, x_i_|I|/c_i_|I|, b) considers all possible substitutions in our first index, meaning we no longer need to worry about it. Doing this repeatedly would allow us to perform exact MTP query evaluation. However, D is non-trivial to compute, and cannot be done by simply modifying Algorithm <ref>. Instead, we observe the following recurrence:

    D   (j+1, x_i_2/c_i_2,…, x_i_|I|/c_i_|I|, b) 
       = 
        max_k ∈{1,…,b} 1 - D(j, x_i_2/c_i_2,…, x_i_|I|/c_i_|I|, b-k) 
    ·    A(x_i_1/c_j+1, x_i_2/c_i_2,…, x_i_|I|/c_i_|I|, k)


Intuitively, this recurrence is saying that since the tuples from each fixed constant are independent of each other, we can add a new constant to our vocabulary by simply considering all combinations of budget assignments. This recurrence can be implemented efficiently, yielding a dynamic programming algorithm that runs in time polynomial in the domain size and budget.

The keen reader will now observe that the above definition and recurrence only make sense if  immediately reaches Step 5 of Algorithm <ref>. While this is true, we see that Steps 0 and 1 have no effect on this recurrence, and Steps 2 and 4 correspond to multiplicative factors. For a query that reaches Step 3: inclusion-exclusion, we indeed need to construct such matrices for each sub-query. Notice that the modified algorithm would only work in the case where we can always pick a common x_i for all sub-queries to do dynamic programming on - that is, when the query is inversion-free.

 
