Distribution Constraints
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.
Geck, Gaetano
Neven, Frank
Schwentick, Thomas
This paper introduces a declarative framework to specify and reason about distributions of data over computing nodes in a distributed setting. More specifically, it proposes distribution constraints which are tuple and equality generating dependencies (tgds and egds) extended with node variables ranging over computing nodes. In particular, they can express co-partitioning constraints and constraints about range-based data distributions by using comparison atoms. The main technical contribution is the study of the implication problem of distribution constraints. While implication is undecidable in general, relevant fragments of so-called data-full constraints are exhibited for which the corresponding implication problems are complete for EXPTIME, PSPACE and NP. These results yield bounds on deciding parallel-correctness for conjunctive queries in the presence of distribution constraints.
 Welcome to our talk on distribution constraints, the chase for distributed data. A joint work with Frank Neven and Thomas Schventik. The research presented in this talk is motivated by the desire to model properties of relational data in a distributed setting. While in the non-distributed setting you have a single machine, some input data from which you compute some output, in the distributed setting you have a number of machines, each responsible for some part of the input and producing a part of the output, such that these parts are equivalent to the output in the standard model. What is crucial here in terms of correctness and efficiency is the placement, the distribution of the original input. For some simple operations like selections, projections or map-reduce operations, this is rather easy and possibly a simple petition. For other operations, like the evaluation of joints however, more elaborated distribution patterns are needed usually. In the last decade, several works have studied the possibility of worst case optimal distributed evaluation for certain query classes, or have considered, more generally, the question of parallel correctness. Our approach is to study formalism, that is a combination of the well-known tuple generating and equality generating dependencies, with comparison atoms and, more importantly, with node variables. We call that formalism distribution constraints, and we have studied the complexity of its implication problem. So, before turning to distribution constraints, let us quickly recap what TGDs, EGDs and the implication problems are about. Tuple generating dependencies are rules of a form like this. They correspond to first-order formulas that conditionally require the existence of facts. TGDs are called full, if every variable in the head also appears in the body of the rule. Otherwise, they are non-full, which corresponds to the existential quantification of head variants. Equality generating dependencies are rules that conditionally require the equality of values, and also correspond to a certain type of first-order formula. For the implication problem, we are given a set sigma of dependencies and a single dependency tau, and ask whether sigma implies tau, that is, whether every database that satisfies every dependency in sigma also satisfies tau. A powerful algorithmic tool to decide implication is the chase procedure, which we will reconsider again later. Let's turn now to distribution constraints and start with an example. Consider a network of three servers with four facts. Such a set of instances can be modeled as a single annotated instance. Here, the annotation describes the responsible node. Annotations like these have already been used in WebDunlock, studied a few years ago. It is important here to note that each relation is extended by a single attribute, and that this attribute has a different type than the other attributes, and hence does not interfere with them. A distribution TGD may look like this. This DTGD refers to nodes kappa and lambda, and requires that each aspect with the value matching the first of an r-fact is located on the same server as the r-fact. Hence, in this network it is not satisfied, because s1 is missing on node A, while it is satisfied in the slightly different network. This DTGD in particular specifies a co-partitioning of s with respect to r, and thus ensures the correct distributed computation of some joint queries. On the other hand, a distribution EGD as the following requires that r-facts with the same value in the second component are located on the same server, and hence violated in this network, but satisfied in this one, where both r-facts are located on node C. Apart from the already mentioned co-partitionings, and specializations like hierarchical partitionings, a number of other common distribution schemes can be modeled by distribution constraints, in particular range-partitionings and hash-partitionings, including hypercube distributions. Furthermore, distribution constraints allow to model certain instances of the parallel correctness problem for conjunctive queries. For a more detailed description of these aspects, we refer to the paper. This brings us to our main results. As mentioned, we have studied the complexity of the implication problem for distribution constraints. We have identified different fragments that are either NP, PSP, or EXP time complete. Indeed, NP completeness gets pi2 completeness if comparisons are allowed, but let's ignore that here. Notably, our results correspond to results for fragments of classical TGDs and EGDs by a simple translation of annotations. While the allowable bounds for NP and PSP are rather easy, for EXP time, where they cover full fragments, they are a little bit more involved. The upper bounds all rely on the chase procedure. Now, for EXP time, this bound is comparatively simple, but getting to a lower bound like PSP or even NP requires a closer look on the chase. So, if all upper bounds rely on the chase, what causes the different complexities? To decide the implication of tau by sigma via the chase, we roughly proceed as follows. We start with the database derived from tau, then check whether it satisfies sigma, and, if not, patch the database yielding a new one. Then, this process repeats by checking satisfaction of sigma, patching the database, and so on. The possible problems with this approach are, the unbounded arity may lead to large databases and long sequences. Indeed, even for full TGDs, implication is EXP time hard then, as was already shown in the 80s. Even worse, for non-full TGDs, the process is not guaranteed to terminate. In the literature, several fragments have been studied in an attempt to locate the exact boundaries of decidability or complexity. Prominent examples include syntactic restrictions like asicclicity, stickiness, guardedness and wardedness. Now, in our paper, we require the arity to be bounded. Unfortunately, this alone does not help too much. Databases still may get large due to non-full DTGDs. Thus, we require DTGDs to be dataful, that is, to allow existential quantification only for node variables. This gives us an EXP time up about immediately, because no redundant node instances will be created, and each node's instance is of polynomial size. To lower the complexity even further, we apply additional restrictions, namely by bounding the context. The context is a simple concept for node variables. It is a set of data variables that occur together with a node variable and some atom. Notably, this property is defined on the granularity of a single constraint. This is different from some of the restrictions mentioned before, that may depend on the interaction between several constraints within a set. In this example, the context of kappa comprises u, x and y, and has size 3. While the context of lambda comprises x and z, and has size 2. Whenever there is an a priori bound on the size of the context, a node variable has bounded context. Over simplified, our results can be summarized as follows. The implication problem is EXP time complete, if at least two unbounded node variables may occur in the body of a DTGD. It is p-space complete, if at most one unbounded variable may occur in both the body and the head of a DTGD. And it is NP-complete, if unbounded variables may occur only either in the head or in the body of a DTGD. You can find the details, including distributed equality generating dependencies in the paper. Let us note here only a few things. Each row in this table represents a type of distribution constraint, where each box stands for a node variable. Node variables that have to be bounded are marked yellow, the white ones may be unbounded. The first two lines in this table refer to the NP case of the oversimplification. Lines G1 and G2 both refer to DTGDs with an existentially quantified node variable in the head. In G1, this node variable has bounded context. In G2, all other node variables have bounded context. While a standard CH sequence for such constraints can still have exponential size, even when thearity of relations is bounded, we have shown that most of these steps are irrelevant for the implication problem. Indeed, an exponentially long CH sequence can be reduced to a polynomial one after a normalization process. As indicated in the table, this is still possible when some types of other DTGDs and some types of DEGDs are admitted. Other extensions, such as alone DTGDs of type G3, where both in the body and in the head an unbounded node variable occurs, lead to a PSPACed implication problem. So, to conclude, our paper introduces distribution constraints, demonstrates the ability to model common distribution patterns and extends the study on the complexity of the chase. By considering a rather simple syntactic restriction that is orthogonal to other restrictions like aseclicity, stickiness, guardedness, or their weak variants considered before. Thanks.
 Welcome to our talk on distribution constraints, the chase for distributed data.  A joint work with Frank Neven and Thomas Schventik.  The research presented in this talk is motivated by the desire to model properties of relational data in a distributed setting.  While in the non-distributed setting you have a single machine, some input data from which you compute some output,  in the distributed setting you have a number of machines, each responsible for some part of the input and producing a part of the output,  such that these parts are equivalent to the output in the standard model.  What is crucial here in terms of correctness and efficiency is the placement, the distribution of the original input.  For some simple operations like selections, projections or map-reduce operations, this is rather easy and possibly a simple petition.  For other operations, like the evaluation of joints however, more elaborated distribution patterns are needed usually.  In the last decade, several works have studied the possibility of worst case optimal distributed evaluation for certain query classes,  or have considered, more generally, the question of parallel correctness.  Our approach is to study formalism, that is a combination of the well-known tuple generating and equality generating dependencies,  with comparison atoms and, more importantly, with node variables.  We call that formalism distribution constraints, and we have studied the complexity of its implication problem.  So, before turning to distribution constraints, let us quickly recap what TGDs, EGDs and the implication problems are about.  Tuple generating dependencies are rules of a form like this.  They correspond to first-order formulas that conditionally require the existence of facts.  TGDs are called full, if every variable in the head also appears in the body of the rule.  Otherwise, they are non-full, which corresponds to the existential quantification of head variants.  Equality generating dependencies are rules that conditionally require the equality of values, and also correspond to a certain type of first-order formula.  For the implication problem, we are given a set sigma of dependencies and a single dependency tau, and ask whether sigma implies tau,  that is, whether every database that satisfies every dependency in sigma also satisfies tau.  A powerful algorithmic tool to decide implication is the chase procedure, which we will reconsider again later.  Let's turn now to distribution constraints and start with an example.  Consider a network of three servers with four facts.  Such a set of instances can be modeled as a single annotated instance.  Here, the annotation describes the responsible node.  Annotations like these have already been used in WebDunlock, studied a few years ago.  It is important here to note that each relation is extended by a single attribute,  and that this attribute has a different type than the other attributes, and hence does not interfere with them.  A distribution TGD may look like this.  This DTGD refers to nodes kappa and lambda, and requires that each aspect with the value matching the first of an r-fact is located on the same server as the r-fact.  Hence, in this network it is not satisfied, because s1 is missing on node A, while it is satisfied in the slightly different network.  This DTGD in particular specifies a co-partitioning of s with respect to r, and thus ensures the correct distributed computation of some joint queries.  On the other hand, a distribution EGD as the following requires that r-facts with the same value in the second component are located on the same server,  and hence violated in this network, but satisfied in this one, where both r-facts are located on node C.  Apart from the already mentioned co-partitionings, and specializations like hierarchical partitionings,  a number of other common distribution schemes can be modeled by distribution constraints,  in particular range-partitionings and hash-partitionings, including hypercube distributions.  Furthermore, distribution constraints allow to model certain instances of the parallel correctness problem for conjunctive queries.  For a more detailed description of these aspects, we refer to the paper. This brings us to our main results.  As mentioned, we have studied the complexity of the implication problem for distribution constraints.  We have identified different fragments that are either NP, PSP, or EXP time complete.  Indeed, NP completeness gets pi2 completeness if comparisons are allowed, but let's ignore that here.  Notably, our results correspond to results for fragments of classical TGDs and EGDs by a simple translation of annotations.  While the allowable bounds for NP and PSP are rather easy, for EXP time, where they cover full fragments, they are a little bit more involved.  The upper bounds all rely on the chase procedure.  Now, for EXP time, this bound is comparatively simple, but getting to a lower bound like PSP or even NP requires a closer look on the chase.  So, if all upper bounds rely on the chase, what causes the different complexities?  To decide the implication of tau by sigma via the chase, we roughly proceed as follows.  We start with the database derived from tau, then check whether it satisfies sigma, and, if not, patch the database yielding a new one.  Then, this process repeats by checking satisfaction of sigma, patching the database, and so on.  The possible problems with this approach are, the unbounded arity may lead to large databases and long sequences.  Indeed, even for full TGDs, implication is EXP time hard then, as was already shown in the 80s.  Even worse, for non-full TGDs, the process is not guaranteed to terminate.  In the literature, several fragments have been studied in an attempt to locate the exact boundaries of decidability or complexity.  Prominent examples include syntactic restrictions like asicclicity, stickiness, guardedness and wardedness.  Now, in our paper, we require the arity to be bounded.  Unfortunately, this alone does not help too much. Databases still may get large due to non-full DTGDs.  Thus, we require DTGDs to be dataful, that is, to allow existential quantification only for node variables.  This gives us an EXP time up about immediately, because no redundant node instances will be created,  and each node's instance is of polynomial size.  To lower the complexity even further, we apply additional restrictions, namely by bounding the context.  The context is a simple concept for node variables.  It is a set of data variables that occur together with a node variable and some atom.  Notably, this property is defined on the granularity of a single constraint.  This is different from some of the restrictions mentioned before,  that may depend on the interaction between several constraints within a set.  In this example, the context of kappa comprises u, x and y, and has size 3.  While the context of lambda comprises x and z, and has size 2.  Whenever there is an a priori bound on the size of the context, a node variable has bounded context.  Over simplified, our results can be summarized as follows.  The implication problem is EXP time complete, if at least two unbounded node variables may occur in the body of a DTGD.  It is p-space complete, if at most one unbounded variable may occur in both the body and the head of a DTGD.  And it is NP-complete, if unbounded variables may occur only either in the head or in the body of a DTGD.  You can find the details, including distributed equality generating dependencies in the paper.  Let us note here only a few things.  Each row in this table represents a type of distribution constraint, where each box stands for a node variable.  Node variables that have to be bounded are marked yellow, the white ones may be unbounded.  The first two lines in this table refer to the NP case of the oversimplification.  Lines G1 and G2 both refer to DTGDs with an existentially quantified node variable in the head.  In G1, this node variable has bounded context.  In G2, all other node variables have bounded context.  While a standard CH sequence for such constraints can still have exponential size, even when thearity of relations is bounded,  we have shown that most of these steps are irrelevant for the implication problem.  Indeed, an exponentially long CH sequence can be reduced to a polynomial one after a normalization process.  As indicated in the table, this is still possible when some types of other DTGDs and some types of DEGDs are admitted.  Other extensions, such as alone DTGDs of type G3, where both in the body and in the head an unbounded node variable occurs,  lead to a PSPACed implication problem.  So, to conclude, our paper introduces distribution constraints, demonstrates the ability to model common distribution patterns  and extends the study on the complexity of the chase.  By considering a rather simple syntactic restriction that is orthogonal to other restrictions like  aseclicity, stickiness, guardedness, or their weak variants considered before.  Thanks.
GeckNevenSchwentick_0_203.png GeckNevenSchwentick_204_419.png GeckNevenSchwentick_420_1703.png GeckNevenSchwentick_1704_2183.png GeckNevenSchwentick_2184_2399.png GeckNevenSchwentick_2400_3707.png GeckNevenSchwentick_3708_3791.png GeckNevenSchwentick_3792_4535.png GeckNevenSchwentick_4536_6575.png GeckNevenSchwentick_6576_6647.png GeckNevenSchwentick_6648_10655.png GeckNevenSchwentick_10656_11183.png GeckNevenSchwentick_11184_14507.png GeckNevenSchwentick_14508_14591.png GeckNevenSchwentick_14592_15292.png