Probabilistic Databases with an Infinite Open-World Assumption
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Grohe, Martin
Lindner, Peter
Probabilistic databases (PDBs) introduce uncertainty into relational databases by specifying probabilities for several possible instances. Traditionally, they are finite probability spaces over database instances. Such finite PDBs inherently make a closed-world assumption: non-occurring facts are assumed to be impossible, rather than just unlikely. As convincingly argued by Ceylan et al. (KR '16), this results in implausibilities and clashes with intuition. An open-world assumption, where facts not explicitly listed may have a small positive probability can yield more reasonable results. The corresponding open-world model of Ceylan et al., however, assumes that all entities in the PDB come from a fixed finite universe. In this work, we take one further step and propose a model of truly open-world PDBs with an infinite universe. This is natural when we consider entities from typical domains such as integers, real numbers, or strings. While the probability space might become infinitely large, all instances of a PDB remain finite. We provide a sound mathematical framework for infinite PDBs generalizing the existing theory of finite PDBs. Our main results are concerned with countable, tuple-independent PDBs; we present a generic construction showing that such PDBs exist in the infinite and provide a characterization of their existence. This construction can be used to give an open-world semantics to finite PDBs. The construction can also be extended to so-called block-independent-disjoint probabilistic databases. Algorithmic questions are not the focus of this paper, but we show how query evaluation algorithms can be lifted from finite PDBs to perform approximate evaluation (with an arbitrarily small additive approximation error) in countably infinite tuple-independent PDBs.
 I will talk about probabilistic databases with an infinite open world assumption. And this is joint work with Martin Grohe at the Aviteha-Aachen University. So kind of the running example for this talk will be this table where we can think of it as a list of persons that we have in our database somehow with their name and their gender and their height. And well, in the application I am talking about, we are confronted with various types of uncertainty and of course various types of uncertain domains. And as you might see and maybe many of these domains that naturally occur are typically infinite. For example, we have three types of domains here. We have the domain of strings. For the name of the persons, we have some categorical data like the gender and we have the height, which might be a positive integer or perhaps more fitting a real number. So, and there is also another kind of uncertainty here, which is there might be tuples existing in the table that I have not listed here. So there might be additional information that we are missing. And what I claim is that the custom model of probabilistic databases that has been used in theory so far, the very general one, does not capture these issues very well. So what I will do is introduce a more broad model. And to do so, let me first fix some database schema and some universe to work with. And also, let me tell you, I'm considering set semantics here and a database in the end would just be a collection of facts. And I will denote facts by such a blackboard F letter. So this is the set of facts over the schema and this universe. And an example of such effect is the statement that Peter is male of height 185. And as I said, a database instance is now a finite subset of such sets. So for example, this collection of two facts is a database instance. And when it comes to probabilistic databases, one does not consider a single database instance alone, but a collection of database instances. So this is this blackboard D here. It's a set of database instances over the set of facts. And this is commonly referred to as a set of possible worlds. And so in the general model, in the common model, the set of possible worlds is usually finite. If we move now to an infinite context where the attributes might not only be from overcountable domains, but also of uncountable domains, we additionally need a suitable sigma algebra on this set of database instances. But I will not go into the details that emerge from the problems with measureability of events in sigma algebras here. And so for the moment, we can stick to thinking of possible worlds and construct probabilistic databases as probability distributions over such sets of possible worlds. So a probabilistic database in this sense is simply a probability space whose sample space, the blackboard D, is a set of possible worlds. And we have a probability measure on that. Now, we will distinguish such probabilistic databases being finite or countable or uncountable if the corresponding sample space is. So in particular, when I say an infinite probabilistic database, I still mean that every database instance within the set of possible worlds is a finite object, but they are just infinitely many options. And for the following, there are a few events that are quite important. So the first thing would be for every individual fact F, the marginal event that the fact F is contained in an instance that is drawn at random from the probabilistic database. And I will denote this by this calligraphic D with subscript F. And this straightforward generalization to sets, so script D with subscript capital F is the event that at least one fact of F is contained in a randomly drawn database instance. Now, when it comes to finite probabilistic databases, a very common model of representing probabilistic databases uses independence assumptions. And in the case of finite probabilistic databases, the finite tuple independence assumptions simply asserts that all occurrences of tuples in the probabilistic database are stochastically independent. So this would mean that the probability of any intersection of such marginal events can be calculated as a product of the individual marginal probabilities. And for that reason, we can represent finite tuple independent probabilistic databases by such tables where we annotate each row of the table with a probability. And the probability of a single instance is then given as the probability over those tuples being contained in the database instance times the counter probabilities of those tuples that are not contained in the database instance. And well, what I want to do now is to broaden that notion to a more general context. So a probabilistic database, not necessarily a finite one, will be called tuple independent if all the collections F of this joint sets of facts are independent. So as a formula, you can see it here, but colloquially spoken, it means that whenever I take a collection of this joint sub databases of my database, then these will be independent. And again, I can calculate these probabilities by multiplying probabilities of smaller events. To compare, this was the definition for finite tuple independence, which basically asserts that all rows of the table are independent. And the message is that these two definitions actually coincide whenever we have a countable probabilistic databases. So now let me tell you why I'm interested in these kind of probabilistic databases. And the reason for this is what is known as the closed world assumption. So we have again this tuple independent probabilistic database, the example from before. And the following has been noted three years in the past. So I quote, the closed world assumption of probabilistic databases that facts not in the database have probability zero, clearly conflicts with their everyday use. So this means every information that is not present in this representation system is perceived as an impossible event in the probability space. So for example, we have here a probability of zero that there are two females. We have a probability of zero that they are more than four people in the database, and so on. And of course, this conflicts with our intuition as soon as we add new facts to the database or want to obtain generally meaningful pre-reanswers. And the authors of the paper, I quote, actually introduced a model of open world probabilistic databases, which is called open PDBs. But this model is still restricted to a finite context. So in particular, a priori, they have an upper bound on the number of tuples in such a probabilistic database. And well, what we wanted to do is to have a model at hand that would allow our probabilistic databases to grow arbitrarily large. And the basic idea behind what we are doing is still the same. So we have our original probabilistic database and want to obtain a completion. And by completion, I mean we take the original probabilistic data and add a model for those facts that have not been specified before. And well, we don't want to do this in an arbitrary way. So of course, we want to preserve somehow the original information that was already there in the probabilistic data to begin with. And as for the model for unspecified facts, we are talking about big probability spaces here, infinite ones. So we want to use independence assumptions to keep these probabilities basis simple. A more formal definition of this concept would be that a completion of a probabilistic database is another probabilistic database, delta prime, with the property that the new sample space we take is now the set of all instances over the set of facts. So every possible world that we can build from our schema and our universe will be contained in the new sample space. And the new probability measure satisfies this preservation condition that whenever we condition the probability measure on the set of old instances, we actually have the old probability measure. So this is the idea behind completing probabilistic database towards the open world assumption. And of course, also the closed world assumption somehow falls into this framework by just thinking of the completion where every new fact gets the probability zero. But of course, we have a lot of options there. Now, when it comes to these infinite kind of independence assumptions and probabilistic databases, it is naturally to ask whether they even exist. And in particular, in the finite case, what is very nice is that any collection of facts and probabilities associated to those facts will span a tuple independent probabilistic database. And it is not clear at all whether the same holds for an infinite setting. So the first thing is what about the set of facts being countably infinite? And here we obtain this characterization theorem. So whenever the set of facts is countable, then the following two conditions are equivalent. Indeed, a tuple independent probabilistic database is spanned from our fact probabilities if and only if these fact probabilities form a conversion series. So under the hood, the reason behind this is for our products to converge and our definition to actually span a probability space. So everything I have told you to this point has also a natural extension to an infinite block independent disjoint model, where we would chop up the data into different blocks and have the independence assumption between the blocks. But mutually exclusive choices within the blocks. So there is also a natural extension of this model. And even one direction of this theorem can be, it does hold in the other direction for the uncountable setting. But of course, in the uncountable setting, we cannot span the database from starting with fact probabilities. Since in an uncountable probability space, every single marginal probability would be zero. So towards the application of this, the previous theorem, this characterization theorem, actually tells us that we are able to specify a model of countable tuple independent completions of probabilistic databases, which we hope to use to obtain open world answers to queries. And in particular, while we have that model, it is not clear whether this actually helps something. So is it at all possible to compute query answers in such a model? And indeed, we can for every positive epsilon compute an additive approximation to query answers. So I mean we can approximate the probability of Boolean queries, but we can also approximate the marginal probability of answers in the query result. Now, and so far, this is only a very naive way to, in doing so, by using a finite evaluation method. And this can be, the precision can be achieved by cutting off the tail of the distribution at the appropriate place. Now, one might wonder why we opted for additive approximations here, and the simple reason is that multiplicative approximations cannot be computed in this kind of context. So a countable tuple independent model is too expressive for allowing multiplicative approximation. We can actually reduce it to the emptiness problem. And well, so let me conclude. What I have presented to you is our first step towards a general notion of infinite probabilistic databases. In particular, we wanted to broaden the notions that there are for various independence assumptions, so tuple independence and the block independent disjoint model. And what we want this to do is to serve as a general proposal for open-world query evaluation of probabilistic databases. So, of course, there are a lot of things to be done. So the first thing that we wonder about is a sensible semantics for the uncountable case. So in the uncountable setting, a lot of things get nasty very quickly. So for example, we have the sigma algebra that we need to worry about, and it is not even clear how to have a sensible notion of query semantics. So what we would want to have is a query to map probabilistic databases to probabilistic databases. And for such mappings to have any meaning, these mappings have to be measurable with respect to the sigma algebra that we use for the instance base. Otherwise, we have no sensible notion of a probability being attached to sets of possible worlds. And the other question is, of course, how do we compactly represent such kind of probabilistic databases in order to be able to perform tractable query evaluation? And, well, the approach we are thinking of here is to take a finite model of probabilistic databases as for the original probabilistic database and to carry out the completion in some kind of a probabilistic programming language. So, and of course, one might wonder whether it is in this context helpful to think of uncountable independence assumptions as well. So, these points that I just mentioned are what we are working on right now, and we actually solved the problem of the uncountable query semantics, which is currently under review, and, well, the other things are work in progress. So, thank you very much. Thank you.
 I will talk about probabilistic databases with an infinite open world assumption.  And this is joint work with Martin Grohe at the Aviteha-Aachen University.  So kind of the running example for this talk will be this table where we can think of it  as a list of persons that we have in our database somehow with their name and their gender and their height.  And well, in the application I am talking about, we are confronted with various types of uncertainty  and of course various types of uncertain domains.  And as you might see and maybe many of these domains that naturally occur are typically infinite.  For example, we have three types of domains here.  We have the domain of strings.  For the name of the persons, we have some categorical data like the gender and we have the height,  which might be a positive integer or perhaps more fitting a real number.  So, and there is also another kind of uncertainty here, which is there might be tuples existing in the table  that I have not listed here.  So there might be additional information that we are missing.  And what I claim is that the custom model of probabilistic databases that has been used in theory so far,  the very general one, does not capture these issues very well.  So what I will do is introduce a more broad model.  And to do so, let me first fix some database schema and some universe to work with.  And also, let me tell you, I'm considering set semantics here and a database in the end would just be a collection of facts.  And I will denote facts by such a blackboard F letter.  So this is the set of facts over the schema and this universe.  And an example of such effect is the statement that Peter is male of height 185.  And as I said, a database instance is now a finite subset of such sets.  So for example, this collection of two facts is a database instance.  And when it comes to probabilistic databases, one does not consider a single database instance alone, but a collection of database instances.  So this is this blackboard D here.  It's a set of database instances over the set of facts.  And this is commonly referred to as a set of possible worlds.  And so in the general model, in the common model, the set of possible worlds is usually finite.  If we move now to an infinite context where the attributes might not only be from overcountable domains,  but also of uncountable domains, we additionally need a suitable sigma algebra on this set of database instances.  But I will not go into the details that emerge from the problems with measureability of events in sigma algebras here.  And so for the moment, we can stick to thinking of possible worlds and construct probabilistic databases as probability distributions over such sets of possible worlds.  So a probabilistic database in this sense is simply a probability space whose sample space, the blackboard D, is a set of possible worlds.  And we have a probability measure on that.  Now, we will distinguish such probabilistic databases being finite or countable or uncountable if the corresponding sample space is.  So in particular, when I say an infinite probabilistic database, I still mean that every database instance within the set of possible worlds is a finite object,  but they are just infinitely many options.  And for the following, there are a few events that are quite important.  So the first thing would be for every individual fact F, the marginal event that the fact F is contained in an instance that is drawn at random  from the probabilistic database.  And I will denote this by this calligraphic D with subscript F.  And this straightforward generalization to sets, so script D with subscript capital F is the event that at least one fact of F is contained in a randomly drawn database instance.  Now, when it comes to finite probabilistic databases, a very common model of representing probabilistic databases uses independence assumptions.  And in the case of finite probabilistic databases, the finite tuple independence assumptions simply asserts that all occurrences of tuples in the probabilistic database are stochastically independent.  So this would mean that the probability of any intersection of such marginal events can be calculated as a product of the individual marginal probabilities.  And for that reason, we can represent finite tuple independent probabilistic databases by such tables where we annotate each row of the table with a probability.  And the probability of a single instance is then given as the probability over those tuples being contained in the database instance times the counter probabilities of those tuples that are not contained in the database instance.  And well, what I want to do now is to broaden that notion to a more general context.  So a probabilistic database, not necessarily a finite one, will be called tuple independent if all the collections F of this joint sets of facts are independent.  So as a formula, you can see it here, but colloquially spoken, it means that whenever I take a collection of this joint sub databases of my database, then these will be independent.  And again, I can calculate these probabilities by multiplying probabilities of smaller events.  To compare, this was the definition for finite tuple independence, which basically asserts that all rows of the table are independent.  And the message is that these two definitions actually coincide whenever we have a countable probabilistic databases.  So now let me tell you why I'm interested in these kind of probabilistic databases.  And the reason for this is what is known as the closed world assumption.  So we have again this tuple independent probabilistic database, the example from before.  And the following has been noted three years in the past.  So I quote, the closed world assumption of probabilistic databases that facts not in the database have probability zero, clearly conflicts with their everyday use.  So this means every information that is not present in this representation system is perceived as an impossible event in the probability space.  So for example, we have here a probability of zero that there are two females.  We have a probability of zero that they are more than four people in the database, and so on.  And of course, this conflicts with our intuition as soon as we add new facts to the database or want to obtain generally meaningful pre-reanswers.  And the authors of the paper, I quote, actually introduced a model of open world probabilistic databases, which is called open PDBs.  But this model is still restricted to a finite context.  So in particular, a priori, they have an upper bound on the number of tuples in such a probabilistic database.  And well, what we wanted to do is to have a model at hand that would allow our probabilistic databases to grow arbitrarily large.  And the basic idea behind what we are doing is still the same.  So we have our original probabilistic database and want to obtain a completion.  And by completion, I mean we take the original probabilistic data and add a model for those facts that have not been specified before.  And well, we don't want to do this in an arbitrary way.  So of course, we want to preserve somehow the original information that was already there in the probabilistic data to begin with.  And as for the model for unspecified facts, we are talking about big probability spaces here, infinite ones.  So we want to use independence assumptions to keep these probabilities basis simple.  A more formal definition of this concept would be that a completion of a probabilistic database is another probabilistic database, delta prime,  with the property that the new sample space we take is now the set of all instances over the set of facts.  So every possible world that we can build from our schema and our universe will be contained in the new sample space.  And the new probability measure satisfies this preservation condition that whenever we condition the probability measure on the set of old instances,  we actually have the old probability measure.  So this is the idea behind completing probabilistic database towards the open world assumption.  And of course, also the closed world assumption somehow falls into this framework by just thinking of the completion where every new fact gets the probability zero.  But of course, we have a lot of options there.  Now, when it comes to these infinite kind of independence assumptions and probabilistic databases,  it is naturally to ask whether they even exist.  And in particular, in the finite case, what is very nice is that any collection of facts and probabilities associated to those facts  will span a tuple independent probabilistic database.  And it is not clear at all whether the same holds for an infinite setting.  So the first thing is what about the set of facts being countably infinite?  And here we obtain this characterization theorem.  So whenever the set of facts is countable, then the following two conditions are equivalent.  Indeed, a tuple independent probabilistic database is spanned from our fact probabilities if and only if these fact probabilities form a conversion series.  So under the hood, the reason behind this is for our products to converge and our definition to actually span a probability space.  So everything I have told you to this point has also a natural extension to an infinite block independent disjoint model,  where we would chop up the data into different blocks and have the independence assumption between the blocks.  But mutually exclusive choices within the blocks.  So there is also a natural extension of this model.  And even one direction of this theorem can be, it does hold in the other direction for the uncountable setting.  But of course, in the uncountable setting, we cannot span the database from starting with fact probabilities.  Since in an uncountable probability space, every single marginal probability would be zero.  So towards the application of this, the previous theorem, this characterization theorem,  actually tells us that we are able to specify a model of countable tuple independent completions of probabilistic databases,  which we hope to use to obtain open world answers to queries.  And in particular, while we have that model, it is not clear whether this actually helps something.  So is it at all possible to compute query answers in such a model?  And indeed, we can for every positive epsilon compute an additive approximation to query answers.  So I mean we can approximate the probability of Boolean queries,  but we can also approximate the marginal probability of answers in the query result.  Now, and so far, this is only a very naive way to, in doing so, by using a finite evaluation method.  And this can be, the precision can be achieved by cutting off the tail of the distribution at the appropriate place.  Now, one might wonder why we opted for additive approximations here,  and the simple reason is that multiplicative approximations cannot be computed in this kind of context.  So a countable tuple independent model is too expressive for allowing multiplicative approximation.  We can actually reduce it to the emptiness problem.  And well, so let me conclude.  What I have presented to you is our first step towards a general notion of infinite probabilistic databases.  In particular, we wanted to broaden the notions that there are for various independence assumptions,  so tuple independence and the block independent disjoint model.  And what we want this to do is to serve as a general proposal for open-world query evaluation of probabilistic databases.  So, of course, there are a lot of things to be done.  So the first thing that we wonder about is a sensible semantics for the uncountable case.  So in the uncountable setting, a lot of things get nasty very quickly.  So for example, we have the sigma algebra that we need to worry about,  and it is not even clear how to have a sensible notion of query semantics.  So what we would want to have is a query to map probabilistic databases to probabilistic databases.  And for such mappings to have any meaning, these mappings have to be measurable with respect to the sigma algebra  that we use for the instance base.  Otherwise, we have no sensible notion of a probability being attached to sets of possible worlds.  And the other question is, of course, how do we compactly represent such kind of probabilistic databases  in order to be able to perform tractable query evaluation?  And, well, the approach we are thinking of here is to take a finite model of probabilistic databases  as for the original probabilistic database and to carry out the completion  in some kind of a probabilistic programming language.  So, and of course, one might wonder whether it is in this context helpful to think of uncountable independence assumptions as well.  So, these points that I just mentioned are what we are working on right now,  and we actually solved the problem of the uncountable query semantics, which is currently under review,  and, well, the other things are work in progress.  So, thank you very much.  Thank you.
Grohe_Lindner_0_155.png Grohe_Lindner_156_227.png Grohe_Lindner_228_275.png Grohe_Lindner_276_323.png Grohe_Lindner_324_515.png Grohe_Lindner_516_2579.png Grohe_Lindner_2580_2975.png Grohe_Lindner_2976_5039.png Grohe_Lindner_5040_5087.png Grohe_Lindner_5088_5591.png Grohe_Lindner_5592_7115.png Grohe_Lindner_7116_8051.png Grohe_Lindner_8052_8735.png Grohe_Lindner_8736_13343.png Grohe_Lindner_13344_13895.png Grohe_Lindner_13896_15491.png Grohe_Lindner_15492_16367.png Grohe_Lindner_16368_18431.png Grohe_Lindner_18432_18503.png Grohe_Lindner_18504_18983.png Grohe_Lindner_18984_21035.png Grohe_Lindner_21036_24551.png Grohe_Lindner_24552_24599.png Grohe_Lindner_24600_24766.png