On the Enumeration Complexity of Unions of Conjunctive Queries
Carmeli, Nofar
Kröll, Markus
We study the enumeration complexity of Unions of Conjunctive Queries (UCQs). We aim to identify the UCQs that are tractable in the sense that the answer tuples can be enumerated with a linear preprocessing phase and a constant delay between every successive tuples. It has been established that, in the absence of self joins and under conventional complexity assumptions, the CQs that admit such an evaluation are precisely the free-connex ones. A union of tractable CQs is always tractable. We generalize the notion of free-connexity from CQs to UCQs, thus showing that some unions containing intractable CQs are, in fact, tractable. Interestingly, some unions consisting of only intractable CQs are tractable too. The question of a finding a full characterization of the tractability of UCQs remains open. Nevertheless, we prove that for several classes of queries, free-connexity fully captures the tractable UCQs.
 So, let's start by understanding our goal. The goal is to understand which unions of conjunctive queries can be answered with what can be seen as optimal fine-grained time guarantees. So, first of all, let's understand the queries that we're studying. This is a standard relational database that describes pods in this case. So we have a table for the tutorials and we have a table for the schedule, and we can ask this conjunctive query that joins these two tables and projects out the title. And this table gives us a list of speakers per day. Now, assume we have another table with the research talks, and we can ask a similar conjunctive query that joins the research talks with the schedule and gives us a list of speakers of the research talks per day. Or if we're interested in the union of all of these answers, we just want the speakers, then we can ask the union of conjunctive queries, and the answers to that are the union of the answers to individual conjunctive queries. So these are the queries we're studying, and we want to know how efficiently can we solve such queries because this is the class that we want to handle. So we should mention the settings. We're using settings similar to previous results we're extending. We are extending that's the RAM model so we can access lookup tables in constant time. We're talking in data complexity terms, so the query is considered of constant size. And now what's optimal time guarantees? We need to read the entire input before we know if there is a first answer or not. And we want to print all of the solutions. So we need constant time per answer. This is why we define by delay ceiling the class of all problems, all queries that can be answered with linear pre-processing time before the first answer and then constant delay between the answers. Now for this work, we focus on time complexity and we ignore space. So we want to know which queries are in this class delay ceiling. For conjunctive queries we already have a known answer, the queries that are in this class are exactly the queries that have a structure that is called free connex. And I'm going to explain what free connex means later. So Malcus and I worked with this dichotomy before and we extended it for when there are functional dependencies in the schema. And then we thought what would be the next interesting step and we decided to look into U CQs because it's an interesting class of queries. It's equivalent to positive rational algebra. So now we have our goal formalized so we can talk about it. We want to know which unions of conjunctive queries are in this class delay ceiling. So in this talk when I mean that a query is easy, I mean that it's in delay ceiling and when I say that it's hard, I mean that it's not in this class. Let's start with an overview of our work and then I'm going to go into some explanations in more details. So we have several cases of unions of conjunctive queries. The first case is that all queries are easy. And it's quite easy to show that if every query in the union is easy, then the entire union is easy. If every query is in delay ceiling, the entire union is in delay ceiling, so this case is always easy. Now it gets interesting where some query in the union is hard. If you just jot down the first query that comes into your mind when you think about a union of a hard query in an easy query, it will most likely be a hard union. But can this also be easy? So it can be easy for the simple fact that some unions that contain a hard query are equivalent to unions that don't contain a hard query. If you consider this example, the first query is hard and the second query is easy, but the first query is basically just like the second query with another constraint on R3. So every answer to the first query is also an answer to the second query and the entire union is just equivalent to the second query, which is easy. So the entire union is easy. So this is not that interesting to discuss these sort of cases, and it makes sense to say, okay, what happens with non-redundant unions? So it is sometimes easy, but what happens if you have a non-redundant union that contains a hard query? And this is where we were surprised to find out that some non-redundant unions that contain a hard query are, in fact, easy. And I'm going to show you such an example later in the talk. Okay. So we have queries, unions of a constructive query. We know that if they contain a hard query, they can be easy, they can be hard. And we realized some easy cases. We found structural property that tells us when it's easy, and now we want to know are all cases hard or are we still missing something? That's why we want to look at lower bounds. And the first place where we considered lower bounds is where we thought it would be easiest to show the lower bounds, a union that contains only hard queries. And we tried to show that the union that contains only hard queries is always hard. And we didn't manage to do this for all unions that contain all hard queries. We got stuck where we have queries that are equivalent up to a different projection. And later we realized that we couldn't show that it's always hard because that's not correct. So there exists unions of constructive queries where every query independently in the union in itself is hard, but the entire union is easy. And so if I have enough time, I'm going to show you an example for this too. So now let's go into the details. Why is a union of two easy queries always easy? So I'm going to, I'll just mention that there is a more elegant way of doing this than what I'm doing that doesn't use a lot of space, but I still want to show you the way that I'm going to show you because it builds up to the more complicated things that we will see later. So we don't even need to know how we answer each individual query. Assume you have two black boxes that give you the answer to the first query and the answer to the second query. Now you can combine this computation to get the answer to the union. You can alternate between the steps, one step that gives you an answer for the first query, then the second query, then the first query, then the second query, and so on. Now what are the problems when we do this? The first problem is that we can have duplicates. Here for example, you can see that A is both an answer for the first query and to the second query, and if we do what I just mentioned, you will get A twice. So one thing that you can do is to save a table with all of the answers that you've already seen. Whenever you see an answer, you check if it's there, and if it is there, you just ignore it and move on. Now what is the problem we have? Well, the delay is not always constant. So we have in the beginning this twice linear delay before we get the constant stream of answers, but also in the beginning we produce a lot of unique answers, and then for a long time we produce only answers that we've seen, the delay is not constant. So in this case, we can show that this gives us something that is just as good as constant delay answers because we can delay the answers that we see and still get linear pre-processing time and constant delay. So whenever we see an answer, we don't print it immediately, we put it in a queue of answers that are ready to be printed, and only after we finish an entire round of producing answers, we take something out of the queue and print it. Now I won't go through all of the details, but I think if you think about it for a while, you'll be convinced that whenever we access the queue, it's not empty, that it doesn't give us duplicates, and that we get linear pre-processing time and constant delay. So a union of easy queries is easy. Now what happens when there is a hard query? So first of all, I want to explain why our intuition didn't work, why is the union that contains a hard query is not necessarily hard. So I'm going to show you where the hardness proof fails, and for this we first need to understand the hardness proof of a single conjunctive query. So this is a conjunctive query that's hard, it's acyclic, but it's not free connex, and I know I didn't give you the definition yet, it will come later, but I'm telling you that this is a hard query. And so these are conditional lower bounds that we have, and we use the assumption that we cannot multiply two Boolean matrices in quadratic time. And what we do is we encode this matrix multiplication problem into our database, so in the first relation we put all of the indices of the ones in the first matrix, and in the second table here we put all of the indices of the ones in the second matrix. And this query computes exactly the indices of the ones in our answer, because for example we have one in index one two, due to these ones in indices one two and two two. So assume by contradiction that this query is easy, we can solve it with linear pre-processing time and constant delay. What's linear? Linear in the size of the input, so these tables here, and their size is bound by n squared. And we have constant delay per answer. How many answers can we have at most n squared? So if this query is hard, we can solve matrix multiplication in quadratic time, and we assume we cannot do that, so this query is hard. If it's easy, we can solve matrix multiplication, but we can't, so it's hard. Okay. Take away message from this slide. The cause for interactability is this path, what we call a free path here, where x and y appear in the same atom, and y and z appear in the same atom, but y is projected out. Y is not one of the free variables. And this is the hardness cause, because we're only allowed to use constant time per answer, not constant time per explanation of answer. And here for example, we have this answer one two for other reasons as well, but we're not, we don't have enough time to go over all of the explanations. Okay. Now what happens within a union? Now this is a union where the first query is hard, because we have this free path over here where the y is not free, and the second query, okay. So why is, so it is still hard, right? We can reduce matrix multiplication like before. So we can encode the matrix multiplication in R1 and R2 like before. We can give R3 some values that don't interfere with the reduction, and the answers to Q1 are exactly the matrix multiplication answers. Now the thing is that here, when we have a union, we don't just, if the union is easy, we don't get all of the answers to Q1 independently efficiently. We get all of the answers to Q1 union with the answer to Q2. And Q2 can have cubic, a cubic number of answers. So we can, using this union, compute matrix multiplication, but we do it too slow, and this doesn't contradict any assumption. So the hardness results do not hold within a union. Okay. So it's not necessarily hard. When is it easy? So for this, we need to understand the definition of free connex, but I don't have much time, so I'll just go over this briefly. Free connex is more specific than a cyclic. A cyclic queries have a joint tree. So it's a tree that describes the query. We have a node for every atom, and if we look at every variable independently, then we get a connected part. Free connex also have another condition that means that there is a subtree that contains exactly the free variables. This is more or less the definition because this query here is also free connex, but we don't exactly have the fourth property. We are also allowed to have subsets. So if we have a subset of existing nodes, so if we add another node with YZ, we do get our property. So bottom line, whenever we have such a graph that describes our query, we have an efficient algorithm to solve it. So what happens with this example that we've seen before? The two queries are evaluated over the same database instance, and since the second query is easy, we can use it to solve the easy query. Now here we have something that we call a body homomorphism because it's like a homomorphism where the variables of the second query map to the variables of the first query, but we ignore the head in the standard homomorphism definition. So the second query is easy, and A, B, and C are free variables. So the second query, after we compute it, gives us all possible combinations of assignments to A, B, and C. Now since we have this body homomorphism in the terminology of Q1, this means all possible assignments to X, Y, and Z. This gives us information about the join of R1 and R2. So we can say that Q2 provides these combinations to Q1, and we can use it when we want to compute Q1. So we can have stored this table of all of the answers to Q2, and we can access it as another atom to Q1. And now this query is free conics. So this almost gives us what we want. Now we know that we can have linear preprocessing time constant delay, and then we can have, again, linear preprocessing time constant delay, but it's not really preprocessing, it's in the middle of our computation. For this, we use a lemma that we like to call the cheaters lemma because it tells us how much we're allowed to cheat without actually cheating. So it tells us that if an enumeration problem can be solved with where the delay is usually constant but the constant number of times it's linear, and if there are almost no duplicates but every answer you can get at a constant number of times, then we can do something similar to what I showed in the case of easy queries and get a linear preprocessing constant delay algorithm with no duplicates. So this extends what we've seen for easy and easy case. Now using this cheaters lemma, this union is now easy. And we define when a union can become easy, when a union is easy, it's when every query of the union can become easy by adding variables that are provided by other queries in the union. Now I don't believe I have time to thoroughly explain the case of hard and hard query, so I'm just going to give you the intuition and if you want to hear more about it, we'll be happy to discuss it later. So what happens in a case of hard and hard queries? This is an example of two queries. As I said before, the cases that can be easy are when the two queries have isomorphic bodies. So it can be seen if you renamed the variables as just one query with different projections, one query with two heads. And these two queries are hard. The first query is hard because we have this free path here where y is not a free variable, but in the second query, this area is not hard because all of the variables are free. But in the second query, this part is hard because u and z are free, but w is projected out. So each query has a hard part that's easy in the other query. And the two queries can basically help each other. So I won't give you all of the details, but the idea is that you can find a subset of the answers to q2 that give you enough information to cover for the part that's hard in q1. And then you use this information to find all of the answers to q1. And then q1 gives you information that you can use for q2. Overall, this is an example. So you first ignore the complicated part of q2, and you just compute a subset. You imagine there's a subset of the free variables that is easy to compute. You get only a subset of the answers to q2. You use them to compute q1. And then you use q1 to compute all of the answers to q2 again, including the ones you've missed, including the ones you've already seen. And then we can use our Cheaters' Lema again to say that this can be done with linear pre-processing time and constant delay. So hard queries can also provide variables. And we have an exact characterization for some of the cases, for example, two hard queries. So to conclude, we've seen that unions that contain hard queries can be sometimes easy, even if they contain only hard queries. We formalize when queries can help each other or make each other easy within a union. And we've seen some lower bounds. And we don't have a complete characterization yet. In fact, the last section of our paper is full of examples of specific queries, like the one we have here, where we don't know if this specific query is easy or hard. So for future work, it will be interesting to reach a full characterization. It will also be interesting to inspect the space. Can we use less space and not store all of the answers that we've seen? Thank you. Thank you.
 So, let's start by understanding our goal.  The goal is to understand which unions of conjunctive queries can be answered with what  can be seen as optimal fine-grained time guarantees.  So, first of all, let's understand the queries that we're studying.  This is a standard relational database that describes pods in this case.  So we have a table for the tutorials and we have a table for the schedule, and we can  ask this conjunctive query that joins these two tables and projects out the title.  And this table gives us a list of speakers per day.  Now, assume we have another table with the research talks, and we can ask a similar conjunctive  query that joins the research talks with the schedule and gives us a list of speakers of  the research talks per day.  Or if we're interested in the union of all of these answers, we just want the speakers,  then we can ask the union of conjunctive queries, and the answers to that are the union of the  answers to individual conjunctive queries.  So these are the queries we're studying, and we want to know how efficiently can we solve  such queries because this is the class that we want to handle.  So we should mention the settings.  We're using settings similar to previous results we're extending.  We are extending that's the RAM model so we can access lookup tables in constant time.  We're talking in data complexity terms, so the query is considered of constant size.  And now what's optimal time guarantees?  We need to read the entire input before we know if there is a first answer or not.  And we want to print all of the solutions.  So we need constant time per answer.  This is why we define by delay ceiling the class of all problems, all queries that can  be answered with linear pre-processing time before the first answer and then constant  delay between the answers.  Now for this work, we focus on time complexity and we ignore space.  So we want to know which queries are in this class delay ceiling.  For conjunctive queries we already have a known answer, the queries that are in this  class are exactly the queries that have a structure that is called free connex.  And I'm going to explain what free connex means later.  So Malcus and I worked with this dichotomy before and we extended it for when there are  functional dependencies in the schema.  And then we thought what would be the next interesting step and we decided to look into  U CQs because it's an interesting class of queries.  It's equivalent to positive rational algebra.  So now we have our goal formalized so we can talk about it.  We want to know which unions of conjunctive queries are in this class delay ceiling.  So in this talk when I mean that a query is easy, I mean that it's in delay ceiling and  when I say that it's hard, I mean that it's not in this class.  Let's start with an overview of our work and then I'm going to go into some explanations  in more details.  So we have several cases of unions of conjunctive queries.  The first case is that all queries are easy.  And it's quite easy to show that if every query in the union is easy, then the entire  union is easy.  If every query is in delay ceiling, the entire union is in delay ceiling, so this case is  always easy.  Now it gets interesting where some query in the union is hard.  If you just jot down the first query that comes into your mind when you think about  a union of a hard query in an easy query, it will most likely be a hard union.  But can this also be easy?  So it can be easy for the simple fact that some unions that contain a hard query are  equivalent to unions that don't contain a hard query.  If you consider this example, the first query is hard and the second query is easy, but  the first query is basically just like the second query with another constraint on R3.  So every answer to the first query is also an answer to the second query and the entire  union is just equivalent to the second query, which is easy.  So the entire union is easy.  So this is not that interesting to discuss these sort of cases, and it makes sense to  say, okay, what happens with non-redundant unions?  So it is sometimes easy, but what happens if you have a non-redundant union that contains  a hard query?  And this is where we were surprised to find out that some non-redundant unions that contain  a hard query are, in fact, easy.  And I'm going to show you such an example later in the talk.  Okay.  So we have queries, unions of a constructive query.  We know that if they contain a hard query, they can be easy, they can be hard.  And we realized some easy cases.  We found structural property that tells us when it's easy, and now we want to know are  all cases hard or are we still missing something?  That's why we want to look at lower bounds.  And the first place where we considered lower bounds is where we thought it would be easiest  to show the lower bounds, a union that contains only hard queries.  And we tried to show that the union that contains only hard queries is always hard.  And we didn't manage to do this for all unions that contain all hard queries.  We got stuck where we have queries that are equivalent up to a different projection.  And later we realized that we couldn't show that it's always hard because that's not  correct.  So there exists unions of constructive queries where every query independently in the union  in itself is hard, but the entire union is easy.  And so if I have enough time, I'm going to show you an example for this too.  So now let's go into the details.  Why is a union of two easy queries always easy?  So I'm going to, I'll just mention that there is a more elegant way of doing this than what  I'm doing that doesn't use a lot of space, but I still want to show you the way that  I'm going to show you because it builds up to the more complicated things that we will  see later.  So we don't even need to know how we answer each individual query.  Assume you have two black boxes that give you the answer to the first query and the  answer to the second query.  Now you can combine this computation to get the answer to the union.  You can alternate between the steps, one step that gives you an answer for the first query,  then the second query, then the first query, then the second query, and so on.  Now what are the problems when we do this?  The first problem is that we can have duplicates.  Here for example, you can see that A is both an answer for the first query and to the second  query, and if we do what I just mentioned, you will get A twice.  So one thing that you can do is to save a table with all of the answers that you've already  seen.  Whenever you see an answer, you check if it's there, and if it is there, you just ignore  it and move on.  Now what is the problem we have?  Well, the delay is not always constant.  So we have in the beginning this twice linear delay before we get the constant stream of  answers, but also in the beginning we produce a lot of unique answers, and then for a long  time we produce only answers that we've seen, the delay is not constant.  So in this case, we can show that this gives us something that is just as good as constant  delay answers because we can delay the answers that we see and still get linear pre-processing  time and constant delay.  So whenever we see an answer, we don't print it immediately, we put it in a queue of answers  that are ready to be printed, and only after we finish an entire round of producing answers,  we take something out of the queue and print it.  Now I won't go through all of the details, but I think if you think about it for a while,  you'll be convinced that whenever we access the queue, it's not empty, that it doesn't  give us duplicates, and that we get linear pre-processing time and constant delay.  So a union of easy queries is easy.  Now what happens when there is a hard query?  So first of all, I want to explain why our intuition didn't work, why is the union that  contains a hard query is not necessarily hard.  So I'm going to show you where the hardness proof fails, and for this we first need to  understand the hardness proof of a single conjunctive query.  So this is a conjunctive query that's hard, it's acyclic, but it's not free connex, and  I know I didn't give you the definition yet, it will come later, but I'm telling you that  this is a hard query.  And so these are conditional lower bounds that we have, and we use the assumption that we  cannot multiply two Boolean matrices in quadratic time.  And what we do is we encode this matrix multiplication problem into our database, so in the first  relation we put all of the indices of the ones in the first matrix, and in the second  table here we put all of the indices of the ones in the second matrix.  And this query computes exactly the indices of the ones in our answer, because for example  we have one in index one two, due to these ones in indices one two and two two.  So assume by contradiction that this query is easy, we can solve it with linear pre-processing  time and constant delay.  What's linear?  Linear in the size of the input, so these tables here, and their size is bound by n squared.  And we have constant delay per answer.  How many answers can we have at most n squared?  So if this query is hard, we can solve matrix multiplication in quadratic time, and we assume  we cannot do that, so this query is hard.  If it's easy, we can solve matrix multiplication, but we can't, so it's hard.  Okay.  Take away message from this slide.  The cause for interactability is this path, what we call a free path here, where x and  y appear in the same atom, and y and z appear in the same atom, but y is projected out.  Y is not one of the free variables.  And this is the hardness cause, because we're only allowed to use constant time per answer,  not constant time per explanation of answer.  And here for example, we have this answer one two for other reasons as well, but we're  not, we don't have enough time to go over all of the explanations.  Okay.  Now what happens within a union?  Now this is a union where the first query is hard, because we have this free path over  here where the y is not free, and the second query, okay.  So why is, so it is still hard, right?  We can reduce matrix multiplication like before.  So we can encode the matrix multiplication in R1 and R2 like before.  We can give R3 some values that don't interfere with the reduction, and the answers to Q1  are exactly the matrix multiplication answers.  Now the thing is that here, when we have a union, we don't just, if the union is easy,  we don't get all of the answers to Q1 independently efficiently.  We get all of the answers to Q1 union with the answer to Q2.  And Q2 can have cubic, a cubic number of answers.  So we can, using this union, compute matrix multiplication, but we do it too slow, and  this doesn't contradict any assumption.  So the hardness results do not hold within a union.  Okay.  So it's not necessarily hard.  When is it easy?  So for this, we need to understand the definition of free connex, but I don't have much time,  so I'll just go over this briefly.  Free connex is more specific than a cyclic.  A cyclic queries have a joint tree.  So it's a tree that describes the query.  We have a node for every atom, and if we look at every variable independently, then we get  a connected part.  Free connex also have another condition that means that there is a subtree that contains  exactly the free variables.  This is more or less the definition because this query here is also free connex, but we  don't exactly have the fourth property.  We are also allowed to have subsets.  So if we have a subset of existing nodes, so if we add another node with YZ, we do get  our property.  So bottom line, whenever we have such a graph that describes our query, we have an efficient  algorithm to solve it.  So what happens with this example that we've seen before?  The two queries are evaluated over the same database instance, and since the second query  is easy, we can use it to solve the easy query.  Now here we have something that we call a body homomorphism because it's like a homomorphism  where the variables of the second query map to the variables of the first query, but we  ignore the head in the standard homomorphism definition.  So the second query is easy, and A, B, and C are free variables.  So the second query, after we compute it, gives us all possible combinations of assignments  to A, B, and C.  Now since we have this body homomorphism in the terminology of Q1, this means all possible  assignments to X, Y, and Z.  This gives us information about the join of R1 and R2.  So we can say that Q2 provides these combinations to Q1, and we can use it when we want to compute  Q1.  So we can have stored this table of all of the answers to Q2, and we can access it as  another atom to Q1.  And now this query is free conics.  So this almost gives us what we want.  Now we know that we can have linear preprocessing time constant delay, and then we can have,  again, linear preprocessing time constant delay, but it's not really preprocessing,  it's in the middle of our computation.  For this, we use a lemma that we like to call the cheaters lemma because it tells us how  much we're allowed to cheat without actually cheating.  So it tells us that if an enumeration problem can be solved with where the delay is usually  constant but the constant number of times it's linear, and if there are almost no duplicates  but every answer you can get at a constant number of times, then we can do something  similar to what I showed in the case of easy queries and get a linear preprocessing constant  delay algorithm with no duplicates.  So this extends what we've seen for easy and easy case.  Now using this cheaters lemma, this union is now easy.  And we define when a union can become easy, when a union is easy, it's when every query  of the union can become easy by adding variables that are provided by other queries in the  union.  Now I don't believe I have time to thoroughly explain the case of hard and hard query, so  I'm just going to give you the intuition and if you want to hear more about it, we'll  be happy to discuss it later.  So what happens in a case of hard and hard queries?  This is an example of two queries.  As I said before, the cases that can be easy are when the two queries have isomorphic bodies.  So it can be seen if you renamed the variables as just one query with different projections,  one query with two heads.  And these two queries are hard.  The first query is hard because we have this free path here where y is not a free variable,  but in the second query, this area is not hard because all of the variables are free.  But in the second query, this part is hard because u and z are free, but w is projected  out.  So each query has a hard part that's easy in the other query.  And the two queries can basically help each other.  So I won't give you all of the details, but the idea is that you can find a subset of  the answers to q2 that give you enough information to cover for the part that's hard in q1.  And then you use this information to find all of the answers to q1.  And then q1 gives you information that you can use for q2.  Overall, this is an example.  So you first ignore the complicated part of q2, and you just compute a subset.  You imagine there's a subset of the free variables that is easy to compute.  You get only a subset of the answers to q2.  You use them to compute q1.  And then you use q1 to compute all of the answers to q2 again, including the ones you've  missed, including the ones you've already seen.  And then we can use our Cheaters' Lema again to say that this can be done with linear pre-processing  time and constant delay.  So hard queries can also provide variables.  And we have an exact characterization for some of the cases, for example, two hard queries.  So to conclude, we've seen that unions that contain hard queries can be sometimes easy,  even if they contain only hard queries.  We formalize when queries can help each other or make each other easy within a union.  And we've seen some lower bounds.  And we don't have a complete characterization yet.  In fact, the last section of our paper is full of examples of specific queries, like  the one we have here, where we don't know if this specific query is easy or hard.  So for future work, it will be interesting to reach a full characterization.  It will also be interesting to inspect the space.  Can we use less space and not store all of the answers that we've seen?  Thank you.  Thank you.
Carmeli_Kroell_0_155.png Carmeli_Kroell_156_647.png Carmeli_Kroell_648_863.png Carmeli_Kroell_864_1187.png Carmeli_Kroell_1188_1931.png Carmeli_Kroell_1932_2075.png Carmeli_Kroell_2076_2123.png Carmeli_Kroell_2124_13307.png Carmeli_Kroell_13308_13655.png Carmeli_Kroell_13656_13847.png Carmeli_Kroell_13848_18407.png Carmeli_Kroell_18408_18575.png Carmeli_Kroell_18576_18623.png Carmeli_Kroell_18624_21839.png Carmeli_Kroell_21840_22223.png Carmeli_Kroell_22224_26003.png Carmeli_Kroell_26004_29063.png Carmeli_Kroell_29064_29225.png
So, let's start by understanding our goal. The goal is to understand which unions of conjunctive queries can be answered with what can be seen as optimal fine-grained time guarantees. So, first of all, let's understand the queries that we're studying. This is a standard relational database that describes pods in this case. So we have a table for the tutorials and we have a table for the schedule, and we can ask this conjunctive query that joins these two tables and projects out the title. And this table gives us a list of speakers per day. Now, assume we have another table with the research talks, and we can ask a similar conjunctive query that joins the research talks with the schedule and gives us a list of speakers of the research talks per day. Or if we're interested in the union of all of these answers, we just want the speakers, then we can ask the union of conjunctive queries, and the answers to that are the union of the answers to individual conjunctive queries. So these are the queries we're studying, and we want to know how efficiently can we solve such queries because this is the class that we want to handle. So we should mention the settings. We're using settings similar to previous results we're extending. We are extending that's the RAM model so we can access lookup tables in constant time. We're talking in data complexity terms, so the query is considered of constant size. And now what's optimal time guarantees? We need to read the entire input before we know if there is a first answer or not. And we want to print all of the solutions. So we need constant time per answer. This is why we define by delay ceiling the class of all problems, all queries that can be answered with linear pre-processing time before the first answer and then constant delay between the answers. Now for this work, we focus on time complexity and we ignore space. So we want to know which queries are in this class delay ceiling. For conjunctive queries we already have a known answer, the queries that are in this class are exactly the queries that have a structure that is called free connex. And I'm going to explain what free connex means later. So Malcus and I worked with this dichotomy before and we extended it for when there are functional dependencies in the schema. And then we thought what would be the next interesting step and we decided to look into U CQs because it's an interesting class of queries. It's equivalent to positive rational algebra. So now we have our goal formalized so we can talk about it. We want to know which unions of conjunctive queries are in this class delay ceiling. So in this talk when I mean that a query is easy, I mean that it's in delay ceiling and when I say that it's hard, I mean that it's not in this class. Let's start with an overview of our work and then I'm going to go into some explanations in more details. So we have several cases of unions of conjunctive queries. The first case is that all queries are easy. And it's quite easy to show that if every query in the union is easy, then the entire union is easy. If every query is in delay ceiling, the entire union is in delay ceiling, so this case is always easy. Now it gets interesting where some query in the union is hard. If you just jot down the first query that comes into your mind when you think about a union of a hard query in an easy query, it will most likely be a hard union. But can this also be easy? So it can be easy for the simple fact that some unions that contain a hard query are equivalent to unions that don't contain a hard query. If you consider this example, the first query is hard and the second query is easy, but the first query is basically just like the second query with another constraint on R3. So every answer to the first query is also an answer to the second query and the entire union is just equivalent to the second query, which is easy. So the entire union is easy. So this is not that interesting to discuss these sort of cases, and it makes sense to say, okay, what happens with non-redundant unions? So it is sometimes easy, but what happens if you have a non-redundant union that contains a hard query? And this is where we were surprised to find out that some non-redundant unions that contain a hard query are, in fact, easy. And I'm going to show you such an example later in the talk. Okay. So we have queries, unions of a constructive query. We know that if they contain a hard query, they can be easy, they can be hard. And we realized some easy cases. We found structural property that tells us when it's easy, and now we want to know are all cases hard or are we still missing something? That's why we want to look at lower bounds. And the first place where we considered lower bounds is where we thought it would be easiest to show the lower bounds, a union that contains only hard queries. And we tried to show that the union that contains only hard queries is always hard. And we didn't manage to do this for all unions that contain all hard queries. We got stuck where we have queries that are equivalent up to a different projection. And later we realized that we couldn't show that it's always hard because that's not correct. So there exists unions of constructive queries where every query independently in the union in itself is hard, but the entire union is easy. And so if I have enough time, I'm going to show you an example for this too. So now let's go into the details. Why is a union of two easy queries always easy? So I'm going to, I'll just mention that there is a more elegant way of doing this than what I'm doing that doesn't use a lot of space, but I still want to show you the way that I'm going to show you because it builds up to the more complicated things that we will see later. So we don't even need to know how we answer each individual query. Assume you have two black boxes that give you the answer to the first query and the answer to the second query. Now you can combine this computation to get the answer to the union. You can alternate between the steps, one step that gives you an answer for the first query, then the second query, then the first query, then the second query, and so on. Now what are the problems when we do this? The first problem is that we can have duplicates. Here for example, you can see that A is both an answer for the first query and to the second query, and if we do what I just mentioned, you will get A twice. So one thing that you can do is to save a table with all of the answers that you've already seen. Whenever you see an answer, you check if it's there, and if it is there, you just ignore it and move on. Now what is the problem we have? Well, the delay is not always constant. So we have in the beginning this twice linear delay before we get the constant stream of answers, but also in the beginning we produce a lot of unique answers, and then for a long time we produce only answers that we've seen, the delay is not constant. So in this case, we can show that this gives us something that is just as good as constant delay answers because we can delay the answers that we see and still get linear pre-processing time and constant delay. So whenever we see an answer, we don't print it immediately, we put it in a queue of answers that are ready to be printed, and only after we finish an entire round of producing answers, we take something out of the queue and print it. Now I won't go through all of the details, but I think if you think about it for a while, you'll be convinced that whenever we access the queue, it's not empty, that it doesn't give us duplicates, and that we get linear pre-processing time and constant delay. So a union of easy queries is easy. Now what happens when there is a hard query? So first of all, I want to explain why our intuition didn't work, why is the union that contains a hard query is not necessarily hard. So I'm going to show you where the hardness proof fails, and for this we first need to understand the hardness proof of a single conjunctive query. So this is a conjunctive query that's hard, it's acyclic, but it's not free connex, and I know I didn't give you the definition yet, it will come later, but I'm telling you that this is a hard query. And so these are conditional lower bounds that we have, and we use the assumption that we cannot multiply two Boolean matrices in quadratic time. And what we do is we encode this matrix multiplication problem into our database, so in the first relation we put all of the indices of the ones in the first matrix, and in the second table here we put all of the indices of the ones in the second matrix. And this query computes exactly the indices of the ones in our answer, because for example we have one in index one two, due to these ones in indices one two and two two. So assume by contradiction that this query is easy, we can solve it with linear pre-processing time and constant delay. What's linear? Linear in the size of the input, so these tables here, and their size is bound by n squared. And we have constant delay per answer. How many answers can we have at most n squared? So if this query is hard, we can solve matrix multiplication in quadratic time, and we assume we cannot do that, so this query is hard. If it's easy, we can solve matrix multiplication, but we can't, so it's hard. Okay. Take away message from this slide. The cause for interactability is this path, what we call a free path here, where x and y appear in the same atom, and y and z appear in the same atom, but y is projected out. Y is not one of the free variables. And this is the hardness cause, because we're only allowed to use constant time per answer, not constant time per explanation of answer. And here for example, we have this answer one two for other reasons as well, but we're not, we don't have enough time to go over all of the explanations. Okay. Now what happens within a union? Now this is a union where the first query is hard, because we have this free path over here where the y is not free, and the second query, okay. So why is, so it is still hard, right? We can reduce matrix multiplication like before. So we can encode the matrix multiplication in R1 and R2 like before. We can give R3 some values that don't interfere with the reduction, and the answers to Q1 are exactly the matrix multiplication answers. Now the thing is that here, when we have a union, we don't just, if the union is easy, we don't get all of the answers to Q1 independently efficiently. We get all of the answers to Q1 union with the answer to Q2. And Q2 can have cubic, a cubic number of answers. So we can, using this union, compute matrix multiplication, but we do it too slow, and this doesn't contradict any assumption. So the hardness results do not hold within a union. Okay. So it's not necessarily hard. When is it easy? So for this, we need to understand the definition of free connex, but I don't have much time, so I'll just go over this briefly. Free connex is more specific than a cyclic. A cyclic queries have a joint tree. So it's a tree that describes the query. We have a node for every atom, and if we look at every variable independently, then we get a connected part. Free connex also have another condition that means that there is a subtree that contains exactly the free variables. This is more or less the definition because this query here is also free connex, but we don't exactly have the fourth property. We are also allowed to have subsets. So if we have a subset of existing nodes, so if we add another node with YZ, we do get our property. So bottom line, whenever we have such a graph that describes our query, we have an efficient algorithm to solve it. So what happens with this example that we've seen before? The two queries are evaluated over the same database instance, and since the second query is easy, we can use it to solve the easy query. Now here we have something that we call a body homomorphism because it's like a homomorphism where the variables of the second query map to the variables of the first query, but we ignore the head in the standard homomorphism definition. So the second query is easy, and A, B, and C are free variables. So the second query, after we compute it, gives us all possible combinations of assignments to A, B, and C. Now since we have this body homomorphism in the terminology of Q1, this means all possible assignments to X, Y, and Z. This gives us information about the join of R1 and R2. So we can say that Q2 provides these combinations to Q1, and we can use it when we want to compute Q1. So we can have stored this table of all of the answers to Q2, and we can access it as another atom to Q1. And now this query is free conics. So this almost gives us what we want. Now we know that we can have linear preprocessing time constant delay, and then we can have, again, linear preprocessing time constant delay, but it's not really preprocessing, it's in the middle of our computation. For this, we use a lemma that we like to call the cheaters lemma because it tells us how much we're allowed to cheat without actually cheating. So it tells us that if an enumeration problem can be solved with where the delay is usually constant but the constant number of times it's linear, and if there are almost no duplicates but every answer you can get at a constant number of times, then we can do something similar to what I showed in the case of easy queries and get a linear preprocessing constant delay algorithm with no duplicates. So this extends what we've seen for easy and easy case. Now using this cheaters lemma, this union is now easy. And we define when a union can become easy, when a union is easy, it's when every query of the union can become easy by adding variables that are provided by other queries in the union. Now I don't believe I have time to thoroughly explain the case of hard and hard query, so I'm just going to give you the intuition and if you want to hear more about it, we'll be happy to discuss it later. So what happens in a case of hard and hard queries? This is an example of two queries. As I said before, the cases that can be easy are when the two queries have isomorphic bodies. So it can be seen if you renamed the variables as just one query with different projections, one query with two heads. And these two queries are hard. The first query is hard because we have this free path here where y is not a free variable, but in the second query, this area is not hard because all of the variables are free. But in the second query, this part is hard because u and z are free, but w is projected out. So each query has a hard part that's easy in the other query. And the two queries can basically help each other. So I won't give you all of the details, but the idea is that you can find a subset of the answers to q2 that give you enough information to cover for the part that's hard in q1. And then you use this information to find all of the answers to q1. And then q1 gives you information that you can use for q2. Overall, this is an example. So you first ignore the complicated part of q2, and you just compute a subset. You imagine there's a subset of the free variables that is easy to compute. You get only a subset of the answers to q2. You use them to compute q1. And then you use q1 to compute all of the answers to q2 again, including the ones you've missed, including the ones you've already seen. And then we can use our Cheaters' Lema again to say that this can be done with linear pre-processing time and constant delay. So hard queries can also provide variables. And we have an exact characterization for some of the cases, for example, two hard queries. So to conclude, we've seen that unions that contain hard queries can be sometimes easy, even if they contain only hard queries. We formalize when queries can help each other or make each other easy within a union. And we've seen some lower bounds. And we don't have a complete characterization yet. In fact, the last section of our paper is full of examples of specific queries, like the one we have here, where we don't know if this specific query is easy or hard. So for future work, it will be interesting to reach a full characterization. It will also be interesting to inspect the space. Can we use less space and not store all of the answers that we've seen? Thank you. Thank you.
answers to that are the union of the answers to answer and then constant delay between the the simple fact that some unions that contain a contain a hard query are, in fact, easy. And I'm going to show you such an example later in the tried to show that the union that contains only hard queries is always hard. And we didn't manage describes the query. We have a node for every enumeration problem can be solved with where the easy queries and get a linear preprocessing to reach a full characterization. It will also be