A Dichotomy for Homomorphism_Closed Queries on Probalistic Graphs
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.
Amarilli, Antoine
Ceylan, Ismail Ilkan
We study the problem of probabilistic query evaluation (PQE) over probabilistic graphs, namely, tuple-independent probabilistic databases (TIDs) on signatures of arity two. Our focus is the class of queries that is closed under homomorphisms, or equivalently, the infinite unions of conjunctive queries, denoted UCQ∞. Our main result states that all unbounded queries in UCQ∞ are #P-hard for PQE. As bounded queries in UCQ∞ are already classified by the dichotomy of Dalvi and Suciu, our results and theirs imply a complete dichotomy on PQE for UCQ∞ queries over probabilistic graphs. This dichotomy covers in particular all fragments in UCQ∞ such as negation-free (disjunctive) Datalog, regular path queries, and a large class of ontology-mediated queries on arity-two signatures. Our result is shown by reducing from counting the valuations of positive partitioned 2-DNF formulae (#PP2DNF) for some queries, or from the source-to-target reliability problem in an undirected graph (#U-ST-CON) for other queries, depending on properties of minimal models.
 Hello everyone, I'm Antoine and I'll leave you from Telecom Paris and this is joint work with Isnaud Elkins-Salem from University of Oxford. This is a talk about managing data which I will assume to be represented as a labeled graph. So if you're used to the representation of data as a relational database with tables like this, I am simply going to put the domain of the database as vertices of the graph and draw each fact as an edge in the graph labeled by the relation from which it comes. I am assuming all relations to have IET2, which I will do throughout the entire talk. I am specifically interested in representing data which is uncertain so we are not sure about what is the correct state of the data. The model that I use for this is called Tuple Independent Databases. It is a very simple model where we simply assume that every fact of the database, so every edge of the graph carries a probability of existence. All the facts are assumed to be independent so every fact is present or absent with the given probability independently from the others. What I call the possible world is a possible state of the data. So it is a subset of facts of the Tuple Independent Database and every possible world has a probability which we can compute using the probabilities of the TID. So here it works out to be 0.03% for that specific possible world where it kept the solid edges and I discarded the dashed edges. In general the probability of a possible world is computed like this. So we can see a Tuple Independent Database as a concise representation of an exponentially sized collection of possible worlds and a probability distribution over them. So this is the model that I am working with to represent uncertain data. Let me now talk about evaluating queries over such data. But first let me define queries over non probabilistic graphs. So for me a query is always Boolean and it is simply a function that takes as input a graph and returns either yes or no. So some well-known query classes are conjunctive queries that ask can I find a match of some pattern? A match here is a homomorphism from the pattern to the graph. It may not be injective so we could identify several vertices of the pattern to the same element of the graph. We also have unions of conjunctive queries. These are simply a disjunction of refining many conjunctive queries. And in this work we study a more general class of homomorphism closed queries. So a query is closed under homomorphisms if it has the following property. Given a graph that satisfies the query, every graph to which that graph has a homomorphism must also satisfy the query. So to get some intuition about this very general class, this is a class that generally utilizes CQs and UCQs but also covers some other languages such as regular path queries, data log and so on. What is not allowed in this formalism would be inequalities between variables or negation. And another way to see homomorphism closed queries is to see them as an infinite union of CQs. So at this junction of our infinitely many CQs and in this case we will call a query bounded if it is a finite union of CQs. So it is actually equivalence to UCQ and other homomorphism closed queries are called unbounded if they are not equivalence to UCQ. And of course this class allows for very weird queries, thus asking if there is a path in the graph whose length is a prime number. This is a perfectly valid infinite union of CQs, so a homomorphism closed query. So this is the query languages that I will be studying. Let me now talk about the task that we're interested in on probabilistic data, which is called probabilistic query evaluation or PQE. So for this we fix a query, for instance the CQ here, and the input to this problem is a table independent database. And what we want to compute is the total probability of the worlds of this database that satisfy the query. We want to know intuitively what is the probability that the query is true in the distribution represented by this TID. So formally we just consider all of the possible worlds and we sum over them when they satisfy the query. So this is of course a very inefficient way to do things. So we are interested more generally in figuring out what is the complexity of this problem, PQE of Q for the fixed query Q, depending on the query Q which we fixed. So this is something that has been studied already in previous work, in particular the dichotomy by Dalvian Suthu shows that for unions of conductive queries, some UCQs are safe and enjoy tractable probabilistic query evaluation and all other UCQs are unsafe and this PQE task is sharply hard for them. So in this dichotomy for instance, the UCQ with two atoms like this is safe, but if I add a third atom then it becomes unsafe. If we're interested in more expressive queries, there has been some work by filling an old TANU about negation, but to my knowledge there is no work about recursive queries. So for instance, evaluating RPQs data log over probabilistic data. The only exception that I'm aware of is the work by Jung and Lutz about ontology mediated query answering. This is a somewhat different task of figuring out whether a query is logically implied by the logical constraints of an ontology and they show interactability in the probabilistic setting for some languages of O and Q, which imply the interactability of some class of recursive queries. So in this work, we studied this problem in full generality for all homomorphism closed queries and we were able to show the following dichotomy. Given a query closed on the homomorphisms, either it is equivalent to a safe UCQ, namely it is bounded and the UCQ to which it is equivalent is safe according to Davi and Sucu. In this case, PQE is in P time and in all other cases, probabilistic query evaluation is sharply hard. So this generalizes the result of human looks that I mentioned before and covers languages such as RPQs, C-RPQs, C2-RPQs, data log, etc. If you want an example, you could think of this regular path query that asks if there is a path from a red edge to a blue edge using only green edges. It is easy to see that this is not equivalent to UCQ because it is an infinite disjunction of CQs that are not homomorphically equivalent. And so our result implies that the probabilistic query evaluation for this query is sharply hard and actually the same holds for any RPQ except the ones that turn out to be equivalent to a safe UCQ. So a natural question would be given a query, what's the complexity of deciding which case of the dichotomy applies? We do not study this because it would depend on how queries are represented since we are studying this very large class of homomorphism closed queries, which is only defined semantically and not syntactically. We would have to restrict to a syntactically defined fragment for this to make sense and we haven't studied this. So this is the results that we have shown and let me tell you a few words about how to prove this. Of course, the difficult part is to show that given a query closed on a homomorphism, if it is unbounded, then probabilistic query evaluation is sharply hard. This is the difficult part because for bounded such queries, there are equivalents to UCQs and so they are classified already by the Dalvian suture dichotomy. So the idea of the proof is to find specific patterns of instances where the query is true and becomes false, which we can use to do a hardness proof because, currently, we do not know anything about our query except that it is closed in the homomorphisms unbounded. So an interesting kind of pattern to use for hardness proof is a tight pattern and this is an instance that satisfies the query and has a path of three distinguished edges like this such that whenever we take the middle edge and we replace it by two edges to disconnect the red edge and the blue edge, then this violates the query. The query is no longer true when the instance is modified like this. If we can find something like this, it will turn out to be useful to show hardness and we can actually show that any query closed in the homomorphisms, which is unbounded, must have such a pattern. The intuition is that unbounded queries must have infinitely many minimal models, so they must have arbitrarily large minimal models. And so we can simply take a very large minimal model and perform this transformation on edges randomly and argue that there must be a point at which the query stops being true, otherwise it would contradict the minimality of the large model that we started with. So we can show this and get a tight pattern. Now let me explain to you how we can use this to show hardness. The idea is to reduce from probabilistic re-evaluation for this specific unsafe CQ, Q0, asking for a path of n3. And we will study this PQE problem for Q0 on a specific class of instances which is sufficient to show hardness by looking at how the hardness of PQE for Q0 is shown. It suffices to consider instances where we have red edges to the left with probability 1 half, blue edges to the right with probability 1 half, and green edges from the left to the right with probability 1. Given such an instance, we can code it as an instance for our problem simply by taking the same structure and using the tight pattern, creating copies of the red, blue, and green edges. And the intuition is that all possible worlds at the left that have a path matching Q0 will give us a possible world in the right where we have a match of the tight pattern, and so the query is true because the tight pattern has a homomorphism to the possible world. Conversely, if we take to the left a possible world where we do not have a match of Q0, then the possible world that we get at the right does not have a match of the tight pattern. And so we would like to argue that it does not satisfy the query so that the reduction is complete. There is, however, a subtlety here, namely, not only do we need to know that disconnecting the green edge will violate the query, but we need more specifically to know that going back and forth on green edges will not make the query true. Because if you look at the possible worlds that we have at the right, there is no path going from a red edge to a blue edge directly via a green edge, but of course there could be paths going from red to blue by going back and forth on green edges. So we would need to argue that these cannot satisfy the query. If indeed these violate the query, then the possible worlds to the right has a homomorphism to this pattern that does not respect the query. And so the query is also wrong there, and so we can argue that the reduction is complete. So we need to fix the proof because all that we know is that we have a tight pattern, but we do not know the status of this weird back and forth pattern that we have. So the idea is going to be to study the specific pattern of going back and forth. So this is the same pattern just drawn in a different way. And to actually consider more iterations of this, so all the possible number of times that we could go back and forth on green edges between a red edge and a blue edge. I call this the iterates of the type pattern. And now we will distinguish two cases. The first case is when there is some number of back and forth iterations that will make the query false. So eventually going back and forth makes the query false. In this case, we could use the previous proof that I have shown to you, and it can be made to work. The second case is when all of these iterates satisfy the query. So going from a red edge to a blue edge by any number of back and forth on the green edge makes the query true, but disconnecting the green edge breaks the query. This could happen because we are looking at queries that could be recursive queries testing for unbounded paths of this form. So in this case, let's call this an iterable pattern and let's show hardness with a different reduction, so reducing from a different problem. So how to use these iterable patterns to show hardness? The idea is going to be to reduce from the source to target connectivity problem on undirected graphs. So this is a sharp, hard problem where the input is an undirected graph with a distinguished source vertex S and target vertex T, and all edges of the graph have probability one-half. And what we want to compute is the probability that there is a path from the source to the target in the probability distribution represented by this graph. We can code this using our iterable pattern by replacing every edge of the graph by a back and forth path of length two with green edges, giving probability one-half to one of these edges arbitrarily, and giving probability one to the red and blue edges of the iterable pattern. And then if we keep a possible world of the undirected graph with a path from S to T, then to the right, the corresponding possible world will have an occurrence of the iterable pattern with some path of arbitrary length going back and forth on green edges between the red edge and the blue edge, which ensures that the query is true. Conversely, a possible world of the graph to the left that does not have a path from S to T can be seen to give possible world to the right that has a homomorphism to the result of disconnecting the green edge. This can be shown following a cut between S and T in the possible world of the graph. So this is the basic idea of the reduction. I'm not going into details. The real proof is a bit more complicated than this. Okay. So to summarize, we have shown that probabilistic query evaluation is intractable for any query closing homomorphisms unless it is equivalent to a safe ECQ. So this implies that they got to me over all of the homomorphism close queries and implies intractability for many query languages unless the queries are equivalent to a safe ECQ. So there are open problems that remain. One frustrating problem is that the proof only applies to graphs and not to databases of arbitrary RIT. I would think that the same result would work no matter the RIT, but we would need a somewhat different definition of the instance transformations that we do. I do not know how to make this work currently. The other question is, if all probabilities have to be one-half, so we study unweighted probabilistic query evaluation, do we still get hardness? So with Benny Kimmelfeld, we recently showed that this was the case for non-herarchical self-joint-free CQ. So there we already had hardness even when we were studying this unweighted context. And maybe these techniques also adapt to our work, but for the queries of Dalvi and Sucu, we would not know how to apply these techniques, so this is still open. That's all I had to say. Thanks a lot for listening.
 Hello everyone, I'm Antoine and I'll leave you from Telecom Paris and this is joint work  with Isnaud Elkins-Salem from University of Oxford.  This is a talk about managing data which I will assume to be represented as a labeled  graph.  So if you're used to the representation of data as a relational database with tables  like this, I am simply going to put the domain of the database as vertices of the graph and  draw each fact as an edge in the graph labeled by the relation from which it comes.  I am assuming all relations to have IET2, which I will do throughout the entire talk.  I am specifically interested in representing data which is uncertain so we are not sure  about what is the correct state of the data.  The model that I use for this is called Tuple Independent Databases.  It is a very simple model where we simply assume that every fact of the database, so  every edge of the graph carries a probability of existence.  All the facts are assumed to be independent so every fact is present or absent with the  given probability independently from the others.  What I call the possible world is a possible state of the data.  So it is a subset of facts of the Tuple Independent Database and every possible world has a probability  which we can compute using the probabilities of the TID.  So here it works out to be 0.03% for that specific possible world where it kept the  solid edges and I discarded the dashed edges.  In general the probability of a possible world is computed like this.  So we can see a Tuple Independent Database as a concise representation of an exponentially  sized collection of possible worlds and a probability distribution over them.  So this is the model that I am working with to represent uncertain data.  Let me now talk about evaluating queries over such data.  But first let me define queries over non probabilistic graphs.  So for me a query is always Boolean and it is simply a function that takes as input a  graph and returns either yes or no.  So some well-known query classes are conjunctive queries that ask can I find a match of some  pattern?  A match here is a homomorphism from the pattern to the graph.  It may not be injective so we could identify several vertices of the pattern to the same  element of the graph.  We also have unions of conjunctive queries.  These are simply a disjunction of refining many conjunctive queries.  And in this work we study a more general class of homomorphism closed queries.  So a query is closed under homomorphisms if it has the following property.  Given a graph that satisfies the query, every graph to which that graph has a homomorphism  must also satisfy the query.  So to get some intuition about this very general class, this is a class that generally  utilizes CQs and UCQs but also covers some other languages such as regular path queries,  data log and so on.  What is not allowed in this formalism would be inequalities between variables or negation.  And another way to see homomorphism closed queries is to see them as an infinite union  of CQs.  So at this junction of our infinitely many CQs and in this case we will call a query  bounded if it is a finite union of CQs.  So it is actually equivalence to UCQ and other homomorphism closed queries are called  unbounded if they are not equivalence to UCQ.  And of course this class allows for very weird queries, thus asking if there is a path in  the graph whose length is a prime number.  This is a perfectly valid infinite union of CQs, so a homomorphism closed query.  So this is the query languages that I will be studying.  Let me now talk about the task that we're interested in on probabilistic data, which  is called probabilistic query evaluation or PQE.  So for this we fix a query, for instance the CQ here, and the input to this problem is  a table independent database.  And what we want to compute is the total probability of the worlds of this database that satisfy  the query.  We want to know intuitively what is the probability that the query is true in the distribution  represented by this TID.  So formally we just consider all of the possible worlds and we sum over them when they satisfy  the query.  So this is of course a very inefficient way to do things.  So we are interested more generally in figuring out what is the complexity of this problem,  PQE of Q for the fixed query Q, depending on the query Q which we fixed.  So this is something that has been studied already in previous work, in particular the  dichotomy by Dalvian Suthu shows that for unions of conductive queries, some UCQs are  safe and enjoy tractable probabilistic query evaluation and all other UCQs are unsafe and  this PQE task is sharply hard for them.  So in this dichotomy for instance, the UCQ with two atoms like this is safe, but if I  add a third atom then it becomes unsafe.  If we're interested in more expressive queries, there has been some work by filling an old  TANU about negation, but to my knowledge there is no work about recursive queries.  So for instance, evaluating RPQs data log over probabilistic data.  The only exception that I'm aware of is the work by Jung and Lutz about ontology mediated  query answering.  This is a somewhat different task of figuring out whether a query is logically implied by  the logical constraints of an ontology and they show interactability in the probabilistic  setting for some languages of O and Q, which imply the interactability of some class of  recursive queries.  So in this work, we studied this problem in full generality for all homomorphism closed  queries and we were able to show the following dichotomy.  Given a query closed on the homomorphisms, either it is equivalent to a safe UCQ, namely  it is bounded and the UCQ to which it is equivalent is safe according to Davi and Sucu.  In this case, PQE is in P time and in all other cases, probabilistic query evaluation  is sharply hard.  So this generalizes the result of human looks that I mentioned before and covers languages  such as RPQs, C-RPQs, C2-RPQs, data log, etc.  If you want an example, you could think of this regular path query that asks if there  is a path from a red edge to a blue edge using only green edges.  It is easy to see that this is not equivalent to UCQ because it is an infinite disjunction  of CQs that are not homomorphically equivalent.  And so our result implies that the probabilistic query evaluation for this query is sharply  hard and actually the same holds for any RPQ except the ones that turn out to be equivalent  to a safe UCQ.  So a natural question would be given a query, what's the complexity of deciding which case  of the dichotomy applies?  We do not study this because it would depend on how queries are represented since we are  studying this very large class of homomorphism closed queries, which is only defined semantically  and not syntactically.  We would have to restrict to a syntactically defined fragment for this to make sense and  we haven't studied this.  So this is the results that we have shown and let me tell you a few words about how  to prove this.  Of course, the difficult part is to show that given a query closed on a homomorphism, if  it is unbounded, then probabilistic query evaluation is sharply hard.  This is the difficult part because for bounded such queries, there are equivalents to UCQs  and so they are classified already by the Dalvian suture dichotomy.  So the idea of the proof is to find specific patterns of instances where the query is true  and becomes false, which we can use to do a hardness proof because, currently, we do  not know anything about our query except that it is closed in the homomorphisms unbounded.  So an interesting kind of pattern to use for hardness proof is a tight pattern and this  is an instance that satisfies the query and has a path of three distinguished edges like  this such that whenever we take the middle edge and we replace it by two edges to disconnect  the red edge and the blue edge, then this violates the query.  The query is no longer true when the instance is modified like this.  If we can find something like this, it will turn out to be useful to show hardness and  we can actually show that any query closed in the homomorphisms, which is unbounded,  must have such a pattern.  The intuition is that unbounded queries must have infinitely many minimal models, so they  must have arbitrarily large minimal models.  And so we can simply take a very large minimal model and perform this transformation on edges  randomly and argue that there must be a point at which the query stops being true, otherwise  it would contradict the minimality of the large model that we started with.  So we can show this and get a tight pattern.  Now let me explain to you how we can use this to show hardness.  The idea is to reduce from probabilistic re-evaluation for this specific unsafe CQ, Q0, asking for  a path of n3.  And we will study this PQE problem for Q0 on a specific class of instances which is  sufficient to show hardness by looking at how the hardness of PQE for Q0 is shown.  It suffices to consider instances where we have red edges to the left with probability  1 half, blue edges to the right with probability 1 half, and green edges from the left to the  right with probability 1.  Given such an instance, we can code it as an instance for our problem simply by taking  the same structure and using the tight pattern, creating copies of the red, blue, and green  edges.  And the intuition is that all possible worlds at the left that have a path matching Q0 will  give us a possible world in the right where we have a match of the tight pattern, and  so the query is true because the tight pattern has a homomorphism to the possible world.  Conversely, if we take to the left a possible world where we do not have a match of Q0,  then the possible world that we get at the right does not have a match of the tight pattern.  And so we would like to argue that it does not satisfy the query so that the reduction  is complete.  There is, however, a subtlety here, namely, not only do we need to know that disconnecting  the green edge will violate the query, but we need more specifically to know that going  back and forth on green edges will not make the query true.  Because if you look at the possible worlds that we have at the right, there is no path  going from a red edge to a blue edge directly via a green edge, but of course there could  be paths going from red to blue by going back and forth on green edges.  So we would need to argue that these cannot satisfy the query.  If indeed these violate the query, then the possible worlds to the right has a homomorphism  to this pattern that does not respect the query.  And so the query is also wrong there, and so we can argue that the reduction is complete.  So we need to fix the proof because all that we know is that we have a tight pattern, but  we do not know the status of this weird back and forth pattern that we have.  So the idea is going to be to study the specific pattern of going back and forth.  So this is the same pattern just drawn in a different way.  And to actually consider more iterations of this, so all the possible number of times  that we could go back and forth on green edges between a red edge and a blue edge.  I call this the iterates of the type pattern.  And now we will distinguish two cases.  The first case is when there is some number of back and forth iterations that will make  the query false.  So eventually going back and forth makes the query false.  In this case, we could use the previous proof that I have shown to you, and it can be made  to work.  The second case is when all of these iterates satisfy the query.  So going from a red edge to a blue edge by any number of back and forth on the green  edge makes the query true, but disconnecting the green edge breaks the query.  This could happen because we are looking at queries that could be recursive queries testing  for unbounded paths of this form.  So in this case, let's call this an iterable pattern and let's show hardness with a different  reduction, so reducing from a different problem.  So how to use these iterable patterns to show hardness?  The idea is going to be to reduce from the source to target connectivity problem on undirected  graphs.  So this is a sharp, hard problem where the input is an undirected graph with a distinguished  source vertex S and target vertex T, and all edges of the graph have probability one-half.  And what we want to compute is the probability that there is a path from the source to the  target in the probability distribution represented by this graph.  We can code this using our iterable pattern by replacing every edge of the graph by a  back and forth path of length two with green edges, giving probability one-half to one  of these edges arbitrarily, and giving probability one to the red and blue edges of the iterable  pattern.  And then if we keep a possible world of the undirected graph with a path from S to T,  then to the right, the corresponding possible world will have an occurrence of the iterable  pattern with some path of arbitrary length going back and forth on green edges between  the red edge and the blue edge, which ensures that the query is true.  Conversely, a possible world of the graph to the left that does not have a path from  S to T can be seen to give possible world to the right that has a homomorphism to the  result of disconnecting the green edge.  This can be shown following a cut between S and T in the possible world of the graph.  So this is the basic idea of the reduction.  I'm not going into details.  The real proof is a bit more complicated than this.  Okay.  So to summarize, we have shown that probabilistic query evaluation is intractable for any query  closing homomorphisms unless it is equivalent to a safe ECQ.  So this implies that they got to me over all of the homomorphism close queries and implies  intractability for many query languages unless the queries are equivalent to a safe ECQ.  So there are open problems that remain.  One frustrating problem is that the proof only applies to graphs and not to databases  of arbitrary RIT.  I would think that the same result would work no matter the RIT, but we would need a somewhat  different definition of the instance transformations that we do.  I do not know how to make this work currently.  The other question is, if all probabilities have to be one-half, so we study unweighted  probabilistic query evaluation, do we still get hardness?  So with Benny Kimmelfeld, we recently showed that this was the case for non-herarchical  self-joint-free CQ.  So there we already had hardness even when we were studying this unweighted context.  And maybe these techniques also adapt to our work, but for the queries of Dalvi and Sucu,  we would not know how to apply these techniques, so this is still open.  That's all I had to say.  Thanks a lot for listening.
AmarilliCeylan_0_179.png AmarilliCeylan_180_371.png AmarilliCeylan_372_1199.png AmarilliCeylan_1200_2795.png AmarilliCeylan_2796_3539.png AmarilliCeylan_3540_5471.png AmarilliCeylan_5472_6263.png AmarilliCeylan_6264_6791.png AmarilliCeylan_6792_8507.png AmarilliCeylan_8508_10823.png AmarilliCeylan_10824_10883.png AmarilliCeylan_10884_12491.png AmarilliCeylan_12492_13319.png AmarilliCeylan_13320_16595.png AmarilliCeylan_16596_16703.png AmarilliCeylan_16704_16775.png AmarilliCeylan_16776_18503.png AmarilliCeylan_18504_18587.png AmarilliCeylan_18588_20759.png AmarilliCeylan_20760_22558.png