Neither Cover nor Pack: Distributed Worst-Case Optimality of Degree-2 Joins

The MPC model is well-established in the database theory community for studying distributed algorithms. The model takes a number $p$ as parameter, representing the number of available servers. Servers have no direct access to each other’s memory, but they are connected through a network and can communicate with each other via private (one-to-one) message-passing.

Algorithms in the MPC model are executed in rounds, with each round consisting of a local computation phase followed by a global communication phase. In the local computation phase, every server performs a computation over the data it has locally. During this phase, no messages are sent or received. In the communication phase, every server can send messages to other servers in the network. During this phase, no computation is performed by the servers. We refer to the number of messages (i.e., tuples) received by a server during the communication phase as the server’s load in that round.

In general, the cost of an MPC algorithm is measured in terms of maximum load and number of rounds. By maximum load, we mean the maximum load of any server during any of the algorithm’s rounds. Nonetheless, in this work we only consider constant-round algorithms, for which the maximum load naturally defines the asymptotic cost of the entire algorithm. Since our analysis is for constant-round algorithms, sometimes we do not explicitly mention it in our results.

A join algorithm in the MPC model computes a join query $q$ over a database instance $𝒟$ that is distributed over the $p$ servers correctly, when every tuple in the output of $q$ over $𝒟$ is computable (i.e., producible) by at least one of the servers in some round. In this paper, we focus on worst-case optimality. That is, we are interested in algorithms that optimize (i.e., minimize) the maximum load of the algorithm w.r.t. given cardinality constraints, rather than for the specific database instance over which the query is computed. The instance $𝒟$ is initially evenly (and arbitrarily) partitioned over the $p$ servers, hence requiring a linear load of $|𝒟|/p$ to read the input (with $|𝒟|$ being the number of tuples in $𝒟$). This linear load is essentially the best load one can hope for, but it is unrealistically low for most queries.

Several asymptotic lower and upper bounds for the join query evaluation problem in the MPC model are known. All the bounds relevant to this line of research, and hence to this paper, are of the form $|𝒟|/p^{1/\mathrm{\ell }}$, with $\mathrm{\ell }$ a number depending on the structure of the target query. The larger the value of $\mathrm{\ell }$, the higher the load is. In the context of lower bounds, we will often say the load is based on $\mathrm{\ell }$ to mean that it is bounded from below by $|𝒟|/p^{1/\mathrm{\ell }}$. Similarly, in the context of upper bounds, we say that the cost of an algorithm is based on $\mathrm{\ell }$ to mean that the load is bounded from above by $|𝒟|/p^{1/\mathrm{\ell }}$. Finally, it is noteworthy that the bounds are in terms of $|𝒟|$ (and not the number of bits) because we consider tuple-based algorithms, inline with other works.

Early work mostly focuses on single-round MPC algorithms [2, 3, 4, 10] and in this variant of the model (opposed to the multi-round variant) the worst-case load is now well-understood. An algorithm of particular importance in this context is HyperCube [2, 3], also called the shares algorithm. The HyperCube algorithm runs with a load of $|𝒟|/p^{1/\tau }$ where $\tau$ is the fractional vertex covering number (aka, fractional edge packing number) of the query (see Section 2). This load is worst-case optimal in the sense that its load matches a $|𝒟|/p^{1/\tau }$ lower bound [4] up to a polylog factor and with high probability when the input database is skew-free and with all relations having the same size. Skew-freeness means that the degrees of attribute values (and by extension, partial tuples over attributes) do not exceed certain threshold values that are defined by a parameterization of the run for HyperCube.

Without constraints on the database, the worst-case optimal load of single-round MPC algorithms is $|𝒟|/p^{1/\psi }$ and an algorithm exists that can achieve it w.h.p. and up to a polylog factor [10]. The number $\psi$ is the edge quasi-packing number and is equal to the maximum fractional vertex covering number of all residuals of the target query. A residual of a query $q$ is the query obtained after removing some attributes of $q$ (from all relations that have these attributes). Since every query is a residual of itself, it is immediate that $\tau \le \psi$ holds.

When more than one round is allowed, the load can be significantly improved, below $\psi$, for some queries. A key advantage of the multi-round MPC model is that (residual) queries can be simplified by computing semi-joins (i.e., removing redundant relations) in one round with linear load, before proceeding with the actual join computation.

For the multi-round variant, a few results are known, and several questions are open. It is known that, for every query, the worst-case optimal load is at least $|𝒟|/p^{1/\rho }$, where the number $\rho$ is the fractional edge covering number (aka, fractional vertex packing number) of the query (see Section 2). This lower bound result was obtained in [10], and for some join queries this bound is tight. This is the case for Loomis-Whitney (LW) queries (which is a very specific family of queries with $\tau =\rho$) [10], all graph-like queries (i.e., join queries involving relations with at most two attributes) [10, 8, 12, 11, 9, 1] as well as for all join queries that are acyclic [5, 13, 1]. We remark that $\rho \le \psi$ holds for all queries, and hence, the one-round algorithm is already optimal in the multi-round setting for all queries with $\rho =\psi$.

For a while, it has been thought that $|𝒟|/p^{1/\rho }$ could be the worst-case optimal load in general, but this idea was recently debunked. In particular, it is shown in [5] that $|𝒟|/p^{1/\tau }$ is a tighter lower bound for a very specific fragment of semi-grids. This new lower bound directly shows that there are other queries for which the one-round algorithm based on $\psi$ is effectively worst-case optimal in the multi-round case. This is precisely the case for all degree-two queries with $\tau =\psi$ and with lower bound on the load based on $\tau$ such as boat queries (see Section 2 for the precise definition).

It is worth noting that the initial worst-case optimal multi-round algorithms proposed in the literature for LW, graph-like, or acyclic queries cannot straightforwardly be generalized to arbitrary join queries, and hence, the one-round worst-case load based on $\psi$ remains a reasonable generic upper bound in the multi-round setting as well.

In efforts to have a multi-round algorithm that works for arbitrary join queries, two algorithms of different nature have been proposed in the literature [11, 1]. We will refer to these as the $\varphi$-algorithm [11] (see below what $\varphi$ is) and the PAC algorithm [1],²²2For completeness, there is a map-reduce join algorithm that shares some similarities with the original PAC algorithm [7]. The algorithm allows the number of servers to grow as needed to achieve a specific load guarantee which suits the map-reduce model but not the MPC model. For this reason, we no longer mention that algorithm. respectively. It is worth noting that the load of the PAC algorithm depends on a parameter whose optimal value is non-trivial to compute.

The load of the $\varphi$-algorithm has a fixed upper bound of $|𝒟|/p^{1/\alpha \varphi /2}$ with $\alpha$ being the maximum arity of the relations in the query and $\varphi$ being a new query-related quantity called generalized vertex packing number. It was shown that $\varphi \ge \rho$ holds for every query as well as $\alpha \varphi \ge k$ where $k$ is the total number of attributes in the query.³³3The relationship of $\alpha \varphi \ge k$ follows from Lemma 3.1 and the discussion of Lemma 4.3 in [11]. The general upper bound can be shown to be worst-case optimal for graph-like queries and boat queries. However, this bound does not recover the worst-case optimality for acyclic queries nor for LW queries. Moreover, there is no clear relationship between $\psi$ and $\alpha \varphi /2$. In particular, some queries have , which means that for these queries the worst-case-optimal one-round algorithm guarantees a strictly better load than the multi-round $\varphi$-algorithm.

On the other hand, the PAC algorithm takes a parameter $𝗋$ called the spectrum which is a sequence of discrete values allowing for a more fine-grained definition of skew. Parameterized with a specific spectrum $𝗋$, the algorithm runs with load ${\gamma }_{𝗋}$ that is defined to be the best possible load of the most difficult subproblem. The more-fine grained the choice of $𝗋$, the tighter the load of the algorithm can be. It is shown that for any choice of spectrum $𝗋$, ${\gamma }_{𝗋}\le \psi$ holds and hence it runs with a load that is at most that of the one-round algorithm. This straightforwardly recovers the worst-case optimality for boat queries. It was also shown that with a choice of $𝗋=0,1/2,1$, the relationship ${\gamma }_{𝗋}=\rho$ holds for graph-like queries and for acyclic queries, which is worst-case optimal for both classes. The LW queries, on the other hand, are the only class of queries whose worst-case optimality was not recovered by the PAC algorithm, which is alluded to a non-tight load analysis of the algorithm.

Based on the current literature, in this work we investigate the following questions:

1. 1)

   It is known that $\tau \ge \rho$ holds for all degree-two queries. Moreover, in case the database is already skew-free, the aforementioned optimal one-round load bound is based on $\tau$. Accordingly, the generic multi-round lower bound that is based on $\rho$ seems unreasonable. We thus investigate if the $\tau$-lower bound can be generalized to other degree-two queries.

2. 2)

   There is a believed conjecture in [5] that the worst-case load for any query is characterized by $\max \{\tau ,\rho \}$. Can we verify if this conjecture truly hold for all degree-two queries?

3. 3)

   We have a clear understanding of the load for the class of boat queries, which is a very restricted fragment of degree-two queries. Can we show any non-trivial upper bounds for subclasses of degree-two queries that structurally generalize the class of boat queries? And can any of the existing algorithms be used to achieve this?

To answer the third question, we consider two generalizations of the class of boat queries: semi-binary queries and grid queries. The two classes are, in a sense, complementary to each other, where, intuitively, the first limits the connectivity of the relations, while the other fully exploits this such that the diameter of any query is exactly two.⁴⁴4The diameter of a query is the maximum length of a shortest path connecting any two of its attributes. To better understand the rest of this section, we summarize the relationship between the aforementioned classes in the next depiction. See Section 2 for formal definitions.

Table 1 gives a summary of our worst-case load results in addition to the already known bounds. These complexity results and our other contributions are summarized as follows.

We motivate the framework with the following example.

We formulate this idea as follows:

Next, we apply the framework for the class of grid queries establishing a tighter lower bound for this class and we also apply it to the class of semi-grids. In the latter case, we rely on a new result on the worst-case load required to compute a Cartesian-product query.

For grid queries, it is known that $\tau \ge \rho$, and the $\tau$-based lower-bound framework of [5] applies. In this section, we improve on that lower bound for grid queries. Precisely:

Without loss of generality, we assume that $𝚛\ge 𝚌$, and hence, by Proposition 2, we know that $\tau =𝚛$ and $\rho =𝚌$ in this case. For grids with $𝚌\le 4$, the maximum between $\{𝚛,𝚛+𝚌-4\}$ is simply $𝚛=\tau$ which is the best-known bound. For this reason, we continue the argument for grids with $𝚌\ge 5$, which are the queries for which a tighter lower bound can be established.

The next proposition along with Theorem 6 completes the argument for Theorem 7. The idea of the construction is similar to obtaining the subquery $q_a^{\prime }$ from the query $q_a$ as per Example 3.

We now turn to the (full) class of semi-grids. It is known that every semi-grid query has $\tau \ge \rho$. Nonetheless, for some semi-grids, the best-known lower bound on the worst-case load is based on $\rho$ (query $q_c$ of Figure 1(c) is an example.) In the rest of this section, we show that the lower bound based on $\tau$ can be extended to all semi-grid queries if all semi-binary queries with some specific property have $\tau$ as a valid lower bound on the worst-case load.

The above theorem directly pinpoints to the simple fragment of degree-two queries that is most challenging within the class of semi-grids. In order to have a better understanding for this fragment, we give a rather simple (sufficient) condition for semi-binary queries $q$ with $\tau (q)=|\mathrm{𝖺𝗍𝗍𝗌}(q)|/2$ for which the $\tau$-based lower-bound argument applies. The condition is based on the absence of odd-like cycles from queries.

To establish Theorem 9, we relate the worst-case load of computing a Cartesian product between two queries to the worst-case load known for those queries in the following way.

By Proposition 3, Theorem 9 easily follows from the next proposition and Theorem 6.

From Example 3, note that $q_c^{\prime }$ is a subquery of the third form as in Proposition 3 with $q_1$ being a $4\times 2$ grid query (i.e., boat query) of $q_1\in \mathrm{𝖫𝖡}[\tau ]$ and $q_2$ being a query of $3$ singleton duplicated relations of $q_2\in \mathrm{𝖫𝖡}[\rho ]$ and $\tau (q)=7=\tau (q_1)+\rho (q_2)=4+3$. Thus, by Proposition 3, we can deduce $q_c$ of Figure 1(c) has the property $q_c\in \mathrm{𝖫𝖡}[\tau ]$. Thus,

In this work, we restrict ourselves to a particular form of spectrums that we define using what we call spectrum indicator. A spectrum indicator $𝗌$ is a positive integer. The spectrum defined by such a spectrum indicator $𝗌$ is the sequence $0/𝗌,1/𝗌,\mathrm{\dots },(𝗌-1)/𝗌,𝗌/𝗌$ of rationals (that is, $r_i=i/𝗌$ for $i\in {[𝗌]}_0$). Henceforth, when we write ${\gamma }_{𝗌}$ we naturally mean ${\gamma }_{𝗋}$ with $𝗋$ being the spectrum defined by the indicator $𝗌$.

Similar to all existing algorithms, the PAC algorithm relies on the technique of heavy-light decomposition in which (partial) tuples are labeled as heavy or light based on their degrees. Given an instance $𝒟$, the spectrum indicator $𝗌$ divides the range of degrees from $|𝒟|$ to $1$ into $𝗌+1$ discrete sequence of ranges: $\mathrm{𝗋𝗇𝗀}(0),\mathrm{\dots },\mathrm{𝗋𝗇𝗀}(𝗌)$ such that the degrees in $\mathrm{𝗋𝗇𝗀}(i)$ are lighter (i.e., lower) than degrees in $\mathrm{𝗋𝗇𝗀}(j)$ for all , in which case the degrees of $\mathrm{𝗋𝗇𝗀}(𝗌)$ are considered light while all the rest are considered different levels of heavy. Having these ranges, $𝒟$ is divided into complementary fragments $ℱ$ such that for every set $A$ of attributes from $\mathrm{𝗂𝗇𝗌}(q)$, all the $A$-tuples in $ℱ$ have similar degrees in $𝒟$ (i.e., within the same range).

Configurations provide all the degree information relevant to a particular fragment. A configuration $𝒞$ of a query $q$ and spectrum indicator $𝗌$ is a total mapping $𝒞:\mathrm{𝗂𝗇𝗌}(q)\to {[𝗌]}_0$. Note that the value assigned to a set $A$ of attributes by a configuration $𝒞$, say $𝒞(A)=i$, means that the degrees of all $A$-tuples in the corresponding fragment are in the $i$th range (that is, $\mathrm{𝗋𝗇𝗀}(i)$). In what follows, we will use $\mathrm{𝖿𝗋𝖺𝗀𝗆𝖾𝗇𝗍}(𝒞)$ to refer to the unique fragment $ℱ$ of $𝒟$ corresponding (i.e., defined by) the configuration $𝒞$.

We remark that not all mappings from $\mathrm{𝗂𝗇𝗌}(q)$ to ${[𝗌]}_0$ are equally meaningful. For this, we define the notion of valid configuration.

The first condition states that the degrees of tuples over a set of attributes cannot be lighter than any of its extensions. The second condition is a consequence of having instances defined as sets. Thus, it is straightforward to show that, for every invalid configuration $𝒞$, ${⟦q⟧}_{ℱ}=\mathrm{\varnothing }$ where $ℱ:=\mathrm{𝖿𝗋𝖺𝗀𝗆𝖾𝗇𝗍}(𝒞)$. Therefore, from now on, we only consider valid configurations.

Note that the value for $𝗌$ is assumed to be fixed beforehand. The PAC algorithm then runs in parallel on all the fragments and hence the load of the algorithm is determined by the most difficult fragment. That is, ${\gamma }_{𝗌}:={\max }_{ℱ}\mathrm{𝖼𝗈𝗌𝗍}(ℱ)$. For a particular fragment $ℱ$, this $\mathrm{𝖼𝗈𝗌𝗍}$ measure intuitively means that there is a way with which the algorithm runs over the fragment $ℱ$ with load $\widetilde{𝒪}\left(|𝒟|/p^{1/{\gamma }_{𝗌}}\right)$ using at most $p^{\mathrm{𝖼𝗈𝗌𝗍}(ℱ)/{\gamma }_{𝗌}}\le p$ servers.

Naturally, the query $q$ can be computed over a fragment $ℱ$ in various ways (i.e., parameterization), each is referred to as a solution. In that case, the load of computing $q$ over $ℱ$ is simply determined by the most efficient solution where $\mathrm{𝖼𝗈𝗌𝗍}(ℱ):={\min }_{𝒮}\mathrm{𝖼𝗈𝗌𝗍}(𝒮)$ with $𝒮$ here ranging over compatible solutions only. Before we explain what solutions are, and what compatible means, we define some additional concepts. Henceforth, for a fragment $ℱ$ of $𝒟$ corresponding to a configuration $𝒞$, we define

• $\mathrm{■}$

  $\mathrm{𝗅𝗂𝗀𝗁𝗍}(ℱ)$ to denote the set of all sets $A\in \mathrm{𝗂𝗇𝗌}(q)$ such that $A$ is light in $ℱ$ (i.e., $𝒞(A)=𝗌$);

• $\mathrm{■}$

  $\mathrm{𝗁𝖾𝖺𝗏𝗒}(ℱ)$ to refer to the set of $\mathrm{𝗂𝗇𝗌}(q)\setminus \mathrm{𝗅𝗂𝗀𝗁𝗍}(ℱ)$; i.e., all the heavy sets of attributes; and

• $\mathrm{■}$

  $\mathrm{𝗁𝖾𝖺𝗏𝗒}\text{-}\mathrm{𝗋𝖾𝗅}(ℱ):=\{R\in \mathrm{𝗋𝖾𝗅𝗌}(q)\mid \forall 𝐚\in {\mathrm{𝗌𝖼𝗁}}_q(R):\{𝐚\}\in \mathrm{𝗁𝖾𝖺𝗏𝗒}(ℱ)\}$.

To define what $𝒮$ is, it is more intuitive to introduce its components from the computation of $q$ over a fragment $ℱ$. Thereto, to compute ${⟦q⟧}_{ℱ}$, the following phases will be followed:

Broadcast phase:

broadcast all relations in $\mathrm{𝗁𝖾𝖺𝗏𝗒}\text{-}\mathrm{𝗋𝖾𝗅}(ℱ)$ to all servers. Now, the query $q$ can be simplified to the query $q^{\prime }:={\mathrm{𝗌𝗎𝖻}}_q({ℛ}_{ℱ},\mathrm{\varnothing })$ with ${ℛ}_{ℱ}$ being the relations of $\mathrm{𝗁𝖾𝖺𝗏𝗒}\text{-}\mathrm{𝗋𝖾𝗅}(ℱ)$.

Decomposing phase:

choose a subset $\mathscr{H}$ from $\mathrm{𝗁𝖾𝖺𝗏𝗒}(ℱ)$ such that the sets of $\mathscr{H}$ are pairwise disjoint and choose a subset $\mathscr{H}{}_{}{}^{\prime }\subseteq \mathscr{H}$. For each set $A\in \mathscr{H}{}^{\prime }$, choose a set $B_A\in \mathrm{𝗅𝗂𝗀𝗁𝗍}(ℱ)$ of attributes with $A⊊B_A$. Henceforth, we use the terms of patches and anchors to mean the sets $𝒫:=\mathscr{H}\setminus \mathscr{H}{}^{\prime }$ and $𝒜:=\{(B_A,A)\mid A\in \mathscr{H}{}_{}{}^{\prime }\}$, respectively. Let ${ℛ}_{𝒜}$ be the set ${\bigcup }_{A\in {\mathscr{H}}^{\prime }}{\mathrm{𝗋𝖾𝗅𝗌}}_{q^{\prime }}(B_A)$ of relations from $\mathrm{𝗋𝖾𝗅𝗌}(q)$ and $ℛ$ be the union ${ℛ}_{ℱ}\cup {ℛ}_{𝒜}$.

The query $q^{\prime }$ is decomposed into a set $𝒬$ of subqueries: for each anchor $(B_A,A)\in 𝒜$, the relations of ${\mathrm{𝗋𝖾𝗅𝗌}}_{q^{\prime }}(B_A)$ make one subquery; all the remaining relations in $q^{\prime }$ make one last subquery, which is ${\mathrm{𝗌𝗎𝖻}}_{q^{\prime }}({ℛ}_{𝒜},\mathrm{\varnothing })={\mathrm{𝗌𝗎𝖻}}_q(ℛ,\mathrm{\varnothing })$ in this case.

Partitioning phase:

for each tuple $𝒉$ in $ℱ$ over $\mathrm{𝖾𝗅𝖾𝗆}(\mathscr{H})$, we assign a group of $p_{𝒉}$ servers to compute the residual query of $q^{\prime }$, obtained by removing the attributes from $\mathrm{𝖾𝗅𝖾𝗆}(\mathscr{H})$, over the sub-fragment ${ℱ}_{[𝒉]}$. Let $q^{\prime \prime }:=q_{}^{\prime }{}_{\mathrm{𝖾𝗅𝖾𝗆}(\mathscr{H})}{}^{}={\mathrm{𝗌𝗎𝖻}}_q({ℛ}_{ℱ},\mathrm{𝖾𝗅𝖾𝗆}(\mathscr{H}))$.

Semi-join phase:

over each group of $p_{𝒉}$ servers, we apply semi-joins to simplify the query $q^{\prime \prime }$ from all the redundancies to obtain the query $q^{\prime \prime \prime }:=\lfloor q^{\prime \prime }\rfloor =\lfloor {\mathrm{𝗌𝗎𝖻}}_q({ℛ}_{ℱ},\mathrm{𝖾𝗅𝖾𝗆}(\mathscr{H}))\rfloor$.

Final join phase:

over each group of $p_{𝒉}$ servers, we compute the join of all relations of $q^{\prime \prime \prime }$ over the instance $\lfloor {ℱ}_{[𝒉]}\rfloor$. In this phase, the remaining relations in $q^{\prime \prime \prime }$ relevant for each subquery of $𝒬$ are handled separately. In which case, the relations of the subquery ${\mathrm{𝗌𝗎𝖻}}_{q^{\prime \prime \prime }}({ℛ}_{𝒜},\mathrm{\varnothing })$ are joined using HyperCube algorithm parameterized by a weight assignment $f$. Henceforth, we use $q_f$ to refer to the subquery ${\mathrm{𝗌𝗎𝖻}}_{q^{\prime \prime \prime }}({ℛ}_{𝒜},\mathrm{\varnothing })$.

With this procedure in mind, $𝒮$ is defined as $𝒮:=(𝒫,𝒜,f)$ [1]. For each such solution $𝒮$, the $\mathrm{𝖼𝗈𝗌𝗍}$ is defined as

We remark that the load induced by some choices of $𝒮$ cannot be bounded, as there are conditions that $f$ needs to satisfy to have a compatible solution. According to [1], a solution $𝒮$ to a fragment $ℱ$ corresponding to a configuration $𝒞\in {\mathrm{𝖼𝗈𝗇𝖿}}_{𝗌}(q)$ is said to be compatible if $f$ is a frac. vertex cover for $q_f$ of weight $\ge 1$ with $f(A)\le 𝒞(A)/𝗌$ for every heavy set $A$.⁷⁷7The condition of $f(A)\le 𝒞(A)/𝗌$ for all heavy sets $A$ guarantees that applying HyperCube with the shares of $f$ to the attributes make the relations skew-free. The following has been shown to compatible solutions (from which Theorem 14 directly follows):

The requirement that $f$ has to be a fractional vertex cover for $q_f$ is not necessary and it can be made tighter in some cases. Thereto, for a given configuration $𝒞\in {\mathrm{𝖼𝗈𝗇𝖿}}_{𝗌}(q)$ and an $A$-tuple $𝒕$, we define the size-reduction induced by $𝐭$, denoted ${\mathrm{\Delta }}_{𝒞,𝒕}$, to be the size reduction of $q$ with, for every $R\in \mathrm{𝗋𝖾𝗅𝗌}(q)$, ${\mathrm{\Delta }}_{𝒞,𝒕}(R):=𝒞(A_R)/𝗌$ such that $A_R$ is the set $A\cap {\mathrm{𝗌𝖼𝗁}}_q(R)$.

We now observe and claim that after the partitioning phase in the aforementioned procedure, there exists some value $\lambda$ such that the (sub)fragment ${ℱ}_{[𝒉]}$ is compatible with the size reduction ${\mathrm{\Delta }}_{𝒞,𝒉}$ and $\lambda$. We formulate and prove this claim in the full version. Nonetheless, this observation allows us to obtain a tighter analysis in some cases. Thereto, we say that a solution $𝒮:=(𝒫,𝒜,f)$ to $ℱ$ corresponding to a configuration $𝒞$ is said to be reduced if $f$ is an edge-weighted frac. vertex cover for $q_f$ and the size reduction ${\mathrm{\Delta }}_{𝒞,𝒉}$, of weight $\ge 1$ and, with $f(A)+{\mathrm{\Delta }}_{𝒞,𝒉}(R)\le 𝒞(A)/𝗌$ for every heavy set $A$ and every $R\in {\mathrm{𝗋𝖾𝗅𝗌}}_{q_f}(A)$. We show:

Finally remark that all compatible solutions are reduced but not all reduced solutions are compatible. Since Theorem 18 is analogous to Theorem 17, we obtain that $\mathrm{𝖼𝗈𝗌𝗍}(ℱ)$ in some cases is strictly less compared to considering compatible solutions only. For instance, this will be essential in establishing the (optimal) upper bound of some grid queries in the following section.

For all degree-two queries $q$, we set $\mathrm{\ell }=k/2$ where $k=|\mathrm{𝖺𝗍𝗍𝗌}(q)|$ and we choose $𝗌=2$. We next show

Thereto, let $𝒞$ be an arbitrary configuration from ${\mathrm{𝖼𝗈𝗇𝖿}}_{𝗌}(q)$ and let $ℱ$ be the corresponding fragment to $𝒞$. The image of $𝒞$ in this case is $\subseteq \{0,1,2\}$ where $0$ corresponds to heavy, $1$ corresponds to semi-heavy, and $2$ corresponds to light.

Notice that we only consider relations of $q$ with at least one attribute $𝐚$ with $𝒞(\{𝐚\})=𝗌=2$. All other relations are going to be broadcast in the first phase of the algorithm.

An attribute $𝐚$ is called isolated if it is light and all its adjacent attributes are individually heavy. We use $ℐ$ to refer to set of all isolated attributes. Now, we differentiate between:

• $\mathrm{■}$

  case 1: every non-broadcastable relation contains an isolated attribute.

• $\mathrm{■}$

  case 2: there are non-broadcastable relations without isolated attributes.

For case 1, we choose a solution $𝒮$ for $ℱ$ with empty sets for $𝒫$ and $𝒜$ and with a weight mapping $f$ such that $f(𝐚)=1$ for every light attribute (i.e., all the $ℐ$ attributes) and $f(𝐚)=0$ for every other attribute. It is easy to see that $𝒮$ is a compatible solution.

Observe that, in this case, $\mathrm{𝖼𝗈𝗌𝗍}(𝒮)=\mathrm{𝖼𝗈𝗌𝗍}(f)=|ℐ|$. To complete the argument for this case, we need to show that $|ℐ|\le k/2$, which follows from the next lemma and the fact that no two attributes of $ℐ$ can be adjacent by definition.

As for case 2, take $ℛ$ to be the set of all pairs of adjacent attributes $(𝐚,𝐛)$ such that $𝐚\in ℐ$. We call this set $ℛ$ as anchor candidates. Now, choose a subset ${ℛ}^{\prime }$ of $ℛ$ of pairwise disjoint pairs such that it covers all the $ℐ$ attributes. That is, every isolated attribute $𝐚$ is contained in exactly one pair of ${ℛ}^{\prime }$. Observe that such set ${ℛ}^{\prime }$ must exist by the following lemma :

We construct the set of anchors from ${ℛ}^{\prime }$ as follows. Take $𝒜:=\{(\{𝐚,𝐛\},\{𝐛\})\mid (𝐚,𝐛)\in {ℛ}^{\prime }\}$. Obviously, $\{𝐚,𝐛\}$ is light and $𝐛$ is not, as desired. Moreover, notice that $\mathrm{𝖼𝗈𝗌𝗍}(𝒜)=|{ℛ}^{\prime }|=|ℐ|$ and the set of attributes in $𝒜$ is of size $2\ast |ℐ|$.

Now, take $𝒫$ to be the set $\{\{𝐚\}\mid 𝐚\text{ is heavy and does not appear in }𝒜\}$. Observe that, since each set of attributes in $𝒫$ is heavy, we have $\mathrm{𝖼𝗈𝗌𝗍}(𝒫)=|𝒫|/2$ and the set of attributes in $𝒫$ is of size $|𝒫|$.

Finally, take $f$ to be the weight mapping with $f(𝐚)=1/2$ for every remaining attribute that is either semi-heavy or light but non-isolated. It is easy to see that $\mathrm{𝖼𝗈𝗌𝗍}(f)$ is equal to half the attributes it assigns weight to. Hence, overall, each attribute contributes to the solution with a cost of at most $1/2$. Thus, $\mathrm{𝖼𝗈𝗌𝗍}(𝒫)+\mathrm{𝖼𝗈𝗌𝗍}(𝒜)+\mathrm{𝖼𝗈𝗌𝗍}(f)\le k/2$ follows from the disjointness of the different components. We argue in the full version that $𝒮$ is indeed a compatible solution. The previous discussion and Theorem 15 directly entails:

As a direct consequence of the previous theorem and Theorem 10, we obtain:

In this part, we show the following main result:

Without loss of generality, we assume that $𝚛\ge 𝚌$. Hence, by Proposition 2, the upper bound in the statement can be equivalently expressed as $\widetilde{𝒪}\left(|𝒟|/p^{1/\max \{𝚛,𝚛+𝚌-3\}}\right)$ instead. To establish Theorem 24, we set $\mathrm{\ell }=\max \{𝚛,𝚛+𝚌-3\}$. We continue our analysis by distinguishing two cases based on grid dimensions.

First, consider the case of grids with $𝚌=2$. This is precisely the case when $q$ is a boat query. By Lemma 2 and Theorem 15, we obtain the desired result by setting $𝗌=1$ since $\mathrm{\ell }=\max \{𝚛,𝚛+𝚌-3\}=𝚛=\tau =\psi$.

Now, consider grids with $𝚌\ge 3$. We observe that in this case, it would be sufficient to only consider fragments for which a solution with a fractional vertex cover alone cannot trivially solve the query with the desired load. For this, we define in Appendix A.2 the notion of a difficult fragment of a grid query. In the full version, we give the specific arguments for $𝚛=3$ and $𝚛\ge 4$ separately to finalize the proof of Theorem 24, where we use different values for the spectrum indicator, and moreover, we utilize completely different solution strategies to solve the difficult fragments. As for $𝚛=3$, we use a spectrum defined by the indicator $𝗌=6$, and we utilize multiple solution strategies in which case none uses anchors. On the other hand, for $𝚛\ge 4$, we find that a spectrum indicator of $𝗌=1$ is sufficient to obtain the upper bound we claim, and all solution strategies, we use, involve anchors.

As a result of Theorem 7 and Theorem 24, we directly obtain: