{'fraction_non_alphanumeric': 0.05019317769045339, 'fraction_numerical': 0.008618696958689694, 'mean_word_length': 3.865991805254278, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 34, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 28, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Tight Fine-Grained Bounds for Direct Access on Join Queries

We consider the task of lexicographic direct access to query answers. That is, we want to simulate an array containing the answers of a join query sorted in a lexicographic order chosen by the user. A recent dichotomy showed for which queries and orders this task can be done in polylogarithmic access time after quasilinear preprocessing, but this dichotomy does not tell us how much time is required in the cases classified as hard. We determine the preprocessing time needed to achieve polylogarithmic access time for all self-join free queries and all lexicographical orders. To this end, we propose a decomposition-based general algorithm for direct access on join queries. We then explore its optimality by proving lower bounds for the preprocessing time based on the hardness of a certain online Set-Disjointness problem, which shows that our algorithm's bounds are tight for all lexicographic orders on self-join free queries. Then, we prove the hardness of Set-Disjointness based on the Zero-Clique Conjecture which is an established conjecture from fine-grained complexity theory. We also show that similar techniques can be used to prove that, for enumerating answers to Loomis-Whitney joins, it is not possible to significantly improve upon trivially computing all answers at preprocessing. This, in turn, gives further evidence (based on the Zero-Clique Conjecture) to the enumeration hardness of self-join free cyclic joins with respect to linear preprocessing and constant delay.


INTRODUCTION
Algorithms for direct access allow to access answers to a query on a database essentially as if they are materialized and stored in an array: given an index ∈ N, the algorithm returns the th answer (or an out-of-bounds error) in very little time. To make this possible, the algorithm first runs a preprocessing on the database that then allows answering arbitrary access queries efficiently. As the number of answers to a database query may be orders-of-magnitude larger than the size of the database, the goal is to avoid materializing all the answers during preprocessing and only simulate the array. The direct access task (previously also called th answer and random access) was introduced by Bagan et al. [7]. They also mentioned that this task can be used for uniform sampling (by first counting and drawing a random index) or for enumerating all query answers (by consecutively accessing all indices). They devised an algorithm that runs in only linear preprocessing time and average constant time per access call for a large class of queries (first-order queries) on databases of bounded degree. Direct access algorithm were also considered for queries in monadic second order logic on databases of bounded treewidth [6]. To reason about general databases and still expect extremely efficient algorithms, another approach is to restrict the class of queries instead. Follow-up work gave linear preprocessing and logarithmic access algorithms for subclasses of conjunctive queries over general databases [9,13,17]. There, it was also explained how direct access can be used to sample without repetitions [13].
Though all of the algorithms we mentioned above simulate storing the answers in a lexicographic order (whether they state it or not), one shortcoming they have in common is that the specific lexicographic order cannot be chosen by the user (but rather it depends on the query structure). Allowing the user to specify the order is desirable because then direct access can be used for additional tasks that are sensitive to the order, such as median finding and boxplot computation. Progress in this direction was recently made by Carmeli et al. [12] who identified which combinations of a conjunctive query and a lexicographic order can be accessed with linear preprocessing time and logarithmic access time. They identified an easy-to-check substructure of the query, called disruptive trios, whose (non-)existence distinguishes the tractable cases (w.r.t. the time guarantees we mentioned) from the intractable ones. In particular, if we consider acyclic join queries, they suggested an algorithm that works for any lexicographic order that does not have disruptive trios with respect to the query. If the join query is also self-join free, they proved conditional lower bounds stating that for all other variable orders, direct access with polylogarithmic direct access requires superlinear time preprocessing. These hardness results assume the hardness of Boolean matrix multiplication. Given the known hardness of self-join free cyclic joins, if we also assume the hardness of hyperclique detection in hypergraphs, this gives a dichotomy for all self-join free join queries and lexicographic orders: they are tractable if and only if the query is acyclic with no disruptive trio with respect to the order.
What happens if the query and order we want to compute happen to fall on the intractable side of the dichotomy? This question was left open by previous work, and we aim to understand how much preprocessing is needed to achieve polylogarithmic access time for each combination of query and order. To this end, we introduce disruption-free decompositions of a query with respect to a variable order. These can be seen as hypertree decompositions of the queries, induced by the desired variable orders, that resolve incompatibilities between the order and the query. Practically, these decompositions specify which relations should be joined at preprocessing in order to achieve an equivalent acyclic join query with no disruptive trios. We can then run the known direct access algorithm from [12] with linear time preprocessing on the result of this preprocessing to get an algorithm for the query and order at hand with logarithmic access time. The cost of our preprocesing phase is therefore dominated by the time it takes to join the selected relations. We define the incompatibility number of a query and order and show that the preprocessing time of our solution is polynomial where the exponent is this number. Intuitively, the incompatibility number is 1 when the query is acyclic and the order is compatible, and it grows as the incompatibility between them grows.
Next, we aspire to know whether our solution can be improved. Though we can easily show that no other decomposition can be better than the specific decomposition we propose, we can still wonder whether a better algorithm can be achieved using an alternative technique. Thus, we set out to prove conditional lower bounds. Such lower bounds show hardness independently of a specific algorithmic technique, but instead they assume that some known problem cannot be solved significantly faster than by the state-ofthe art algorithms. We show that the incompatibility number corresponds in a sense to the number of leaves of the largest star query that can be embedded in our given query. We then prove lower bounds for queries that allow embedding stars through a reduction from online -Set-Disjointness. In this problem, we are given during preprocessing sets of subsets of the universe, and then we need to answer queries that specify one subset from each set and ask whether these subsets are disjoint. On a technical level, in case the query is acyclic, the link of these hardness results with the existence of disruptive trios is that the latter correspond exactly to the possibility to embed a star with two leaves.
Using known hardness results for 2-Set-Disjointness, our reduction shows that the acyclic hard cases in the known dichotomy need at least quadratic preprocessing, unless both the 3-SUM Conjecture and the APSP Conjecture fail. These are both central, wellestablished conjectures in fine-grained complexity theory, see e.g. the survey [24]. To have tighter lower bounds for the case that the incompatibility number is not 2, we show the hardness of -Set-Disjointness through a reduction from the Zero--Clique Conjecture. This conjecture postulates that deciding whether a given edgeweighted -node graph contains a -clique of total edge weight 0 has no algorithm running in time ( − ) for any > 0. For = 3 this conjecture is implied by the 3SUM Conjecture and the APSP Conjecture, so it is very believable. For > 3 the Zero--Clique Conjecture is a natural generalization of the case = 3, and it was recently used in several contexts [1,2,4,5,11,19]. Assuming the Zero--Clique Conjecture, we prove that the preprocessing time of our decomposition-based algorithm is (near-)optimal.
To conclude, our main result is as follows: a join query and an ordering of its variables with incompatibility number admit a lexicographic direct access algorithm with preprocessing time (| | ) and logarithmic access time. Moreover, if the query is self-join free and the Zero--Clique conjecture holds for all , there is no lexicographic direct access algorithm for this query and order with preprocessing time (| | − ) and polylogarithmic access time for any > 0.
As we develop our lower bound results, we notice that our techniques can also be used in the context of constant delay enumeration of query answers. We show that, assuming the Zero--Clique Conjecture, the preprocessing of any constant delay enumeration algorithm for the -variable Loomis-Whitney join is roughly at least (| | 1+1/( −1) ) which tightly matches the trivial algorithm in which the answers are materialzed during preprocessing using a worst-case optimal join algorithm [21][22][23]. From the lower bound for Loomis-Whitney joins, we then infer the hardness of other cyclic joins using a construction by Brault-Baron [9]. Specifically, we conclude that the self-join free join queries that allow constant delay enumeration after linear processing are exactly the acyclic ones, unless the Zero--Clique Conjecture fails for some . This dichotomy has been established based on the hardness of hyperclique detection in hypergraphs [9], see also [8], and we here give more evidence for this dichotomy by showing it also holds under a different complexity assumption.

PRELIMINARIES 2.1 Databases and Queries
A join query is an expression of the form ( ì ) :− 1 (ì 1 ), . . . , ℓ (ì ), where each is a relation symbol, ì 1 , . . . , ì are tuples of variables, and ì is a tuple of all variables in =1 ì . Each (ì ) is called an atom of . A query is called self-join free if no relation symbol appears in two different atoms. If the same relation symbol appears in two different atoms, = , then ì and ì must have the same arity. A conjunctive query is defined as a join query, with the exception that ì may contain any subset of the query variables. We say that the query variables that do not appear in ì are projected. Defined this way, join queries are simply conjunctive queries without projections.
The input to a query is a database which assigns every relation symbol in the query with a relation : a finite set of tuples of constants, each tuple having the same arity as ì . The size | | of is defined as the total number of tuples in all of its relations. An answer to a query over a database is determined by a mapping from the variables of to the constants of such that (ì ) ∈ for every atom (ì ) in . The answer is then ( ì ). The set of all answers to over is denoted ( ). A lexicographic order of a join query is specified by a permutation of the query variables. We assume databases come with an order on their constants. Then, defines an order over ( ): the order between two answers is the same as the order between their assignments to the first variable in on which their assignments differ.
We consider three types of tasks where the problem is defined by a query and the input is a database. Testing is the task where the user specifies a tuple of constants, and we need to determine whether this tuple is an answer to query over the database. Enumeration is the task of listing all query answers. We measure the efficiency of an enumeration algorithm with two parameters: the time before the first answer, which we call preprocessing, and the time between successive answers, which we call delay. Finally, directaccess in lexicographic order is a task defined by a query and an order where, after a preprocessing phase, the user can specify an index and expect the th answer in that order or an out-of-bounds error if there are less than answers. We call the time it takes to provide an answer given an index the access time.

Hypergraphs
A hypergraph = ( , ) consist of a finite set of vertices and a set of edges, i.e., subsets of . Given a set ⊆ , the hyper- ( ) we denote the set of neighbors of a vertex in , i.e., ( ) := { ∈ | ≠ , ∃ ∈ : , ∈ }. For ⊆ , we define ( ) := ∈ ( ) \ . In these notations we sometimes leave out the subscript when it is clear from the context.
A hypergraph is called acyclic if we can eliminate all of its vertices by applying the following two rules iteratively: • if there is an edge ∈ that is completely contained in another edge ′ ∈ , delete from , and • if there is a vertex ∈ that is contained in a single edge ∈ , delete from , i.e., delete from and . An order in which the vertices can be eliminated in the above procedure is called an elimination order for . Note that it might be possible to apply the above rules on several vertices or edges at the same moment. In that case, the order in which they are applied does not change the final result of the process.
A fractional edge cover of is defined as a mapping : → [0, 1] such that for every ∈ we have : ∈ ( ) ≥ 1. The weight of is defined as ( ) := ∈ ( ). The fractional edge cover number is * ( ) := min ( ) where the minimum is taken over all fractional edge covers of . We remark that * ( ) and an optimal fractional edge cover of can be computed efficiently by linear programming.
Every join query has an underlying hypergraph , where the vertices of correspond to the variables of and the edges of correspond to the variable scopes of the atoms of . We use and interchangably in our notation.

Known Algorithms
Here, we state some results that we will use in the remainder of this paper. All running time bounds are in the word-RAM model with (log( )) bit words and unit-cost operations. We use the following notions from [12]. Given a join query and a lexicographic order , a disruptive trio consists of three variables 1 , 2 , 3 such that 3 appears after 1 and 2 in , the variables 1 and 2 do not appear together in an atom of , but 3 shares (different) atoms with both 1 and 2 . T 1 ( [12]). If an acyclic join query and a lexicographic order have no disruptive trios, then lexicographic direct access for and can be solved with (| |) preprocessing and (log(| |)) access time.
A celebrated result by Atserias, Marx and Grohe [3] shows that join queries of fractional edge cover number , can, on any database , result in query results of size at most (| | ), and this bound is tight for every query for some databases. The upper bound is made algorithmic by so-called worst-case optimal join algorithms.

Fine-Grained Complexity
Fine-grained complexity theory aims to find the exact exponent of the best possible algorithm for any problem, see e.g. [24] for a recent survey. Since unconditional lower bounds of this form are currently far out of reach, fine-grained complexity provides conditional lower bounds that hold when assuming a conjecture about some central, well-studied problem. Some important reductions and algorithms in fine-grained complexity are randomized, i.e., algorithms are allowed to make random choices in their run and may return wrong results with a certain probability, see e.g. [20] for an introduction. Throughout the paper, when we write "randomized algorithm" we always mean a randomized algorithm with success probability at least 2/3. It is well-known that the success probability can be boosted to any 1 − by repeating the algorithm (log(1/ )) times and returning the majority result. In particular, we can assume to have success probability at least 1 − 1/ 10 , at the cost of only a factor (log( )). Our reductions typically worsen the success probability by some amount, but using boosting it can be improved back to 1 − 1/ 10 ; we do not make this explicit in our proofs.
We stress that randomization is only used in our hardness reductions, while all our algorithmic results are deterministic.
We will base our lower bounds on the following problem which is defined for every fixed constant ∈ N, ≥ 3.
We remark that by hashing techniques we can assume ≤ 10 . The following conjectures have been used in several places, see e.g. [1,2,4,5,11,19]. The first conjecture is for a fixed , the second postulates hardness for all .
. For no constant > 0 Zero--Clique has a randomized algorithm running in time ( − ).
. For every ≥ 3 the Zero--Clique Conjecture is true.
It is known that the Zero-3-Clique Conjecture, also called Zero-Triangle Conjecture, is implied by two other famous conjectures: the 3SUM Conjecture [25] and the APSP Conjecture [26]. Since we do not use these conjectures directly in this paper, we do not formulate them here and refer the interested reader to the survey [24].
We remark that instead of Zero--Clique some references work with the Exact-Weight--Clique problem, where we are additionally given a target weight and want to find a -clique of weight . Both problems are known to have the same time complexity up to constant factors, see e.g. [1].
A related problem is Min--Clique, where we are looking for the -clique of minimum weight. The Min--Clique Conjecture postulates that this problem also cannot be solved in time ( − ). It is known that the Min--Clique Conjecture implies the Zero--Clique Conjecture, see e.g. [1].

DIRECT-ACCESS ALGORITHM
In this section, we give an algorithm that, for every join query and desired lexicographic order, provides direct access to the query result on an input database. In particular, we propose to add new atoms to the query such that the resulting query has no disruptive trios with respect to the order. Then, any direct-access algorithm that assumes acyclicity and no disruptive-trios can be applied, provided we can compute a database for the new query that yields the same answers. We show that the new query is essentially a generalized hypertree decomposition of optimal fractional hypertree width out of all decompositions with the required properties. This shows that the suggested solution here is the best we can achieve using a decomposition, but it does not mean we cannot do better using a different method-the latter question is studied in the later sections of this paper.

Disruption-Free Decompositions
We describe a process that iteratively eliminates disruptive trios in a query by adding new atoms.

P
6. The disruption-free decomposition of a query is an acyclic super-hypergraph of the hypergraph of without any disruptive trios.

P
. Denote the hypergraph constructed by the procedure of Definition 4 by 0 . To show that 0 is acyclic, we claim that the reverse of is an elimination order. Consider a vertex that we would like to eliminate. By induction, all vertices that are after in the order have already been eliminated at this point. Note that all edges containing are contained in the edge that was added for in the construction of Definition 4. Also, contains at least , so it cannot have been eliminated before . Thus, all edges contaning except can be eliminated. Afterwards, we can eliminate . It follows that, as claimed, all vertices can be eliminated and is acyclic. If had a disruptive trio , , where is last in , then and would already be neighbors of when handling in the procedure of Definition 4, and so they would become neighbors and the disruptive trio would be fixed. So, has no disruptive trio.
It will be useful in the remainder of this section to have a noniterative definition of disruption-free decompositions. Let be the vertices in the connected component of in [ , . . . , ℓ ]. In particular, we have that ∈ .
which is exactly the edge that is added for 5 . The case for 4 is analogous.
For the induction step, we first show ⊆ ′ . Let ∈ . If = , we know that ∈ ′ by definition. Otherwise, < . If ∈ ( ), we have that ∈ ′ because ∈ . Otherwise, is a neighbor of in from Definition 4 because they were both neighbors of some in with > > . In this case, ∈ ( ) and we also conclude that ∈ ′ .
It is left to show the opposite direction. Let ∈ ′ . If = , ∈ by definition. Otherwise, ∈ ( ) with < . Then, when removing from , it is split to connected components, one of them containing a neighbor of . Consider the smallest variable in such a connected component. Then, this connected component is , and we have that , ∈ ( ) and , < . By induction, and both appear in . Thus is a neighbor of when creating , and so ∈ .

The Algorithm
The idea of our direct access algorithm is to use the disruption-free decomposition. More precisely, we define a new query ′ from such that the hypergraph of ′ is the disruption-free decomposition of . Then, given an input database for , we compute a new database ′ for ′ such that ( ) = ′ ( ′ ). Since ′ has no disruptive trio, we can then use the algorithm from [12] on ′ and ′ to allow direct access. A key component to making this approach efficient is the efficient computation of ′ . To measure its complexity, we introduce the following notion. Note that we assume that queries have at least one atom, so the incompatibility number of any query and any order is at least 1. The incompatibility number can also be seen as the fractional width of the disruption-free decomposition, and we can show that this decomposition has the minimum fractional width out of all decompositions with the properties we need, see Section 4 for details. We now show that the incompatibility number lets us state an upper bound for the computation of a database ′ with the properties claimed above.

T
10. Given a join query and an ordering of its variables with incompatibility number , lexicographic direct access with respect to can be achieved with (| | ) preprocessing and logarithmic access time.

P
. We construct ′ by adding for every edge an atom whose variables are those in . We compute a relation ′ as follows: let be a fractional edge cover of [ ] of weight . Let¯ 1 , . . . ,¯ be the edges of [ ] that have positive weight in . For every¯ there is an edge ′ of such that¯ = ′ ∩ . Let¯ (¯ ) be the projection to of the atom corresponding to ′ . Let * be the extension of that contains the corresponding projected relations for the¯ (¯ ). We set Then clearly for all tuples ì in ( ), the tuple we get by projecting ì to lies in ′ . As a consequence, we can construct ′ by adding all relations ′ to to get ( ) = ′ ( ′ ). Moreover, the hypergraph of ′ is the disruption-free decomposition of the hypergraph of , so we can apply the algorithm from [12] for direct access.
It remains to show that all ′ can be constructed in time (| | ).
To this end, consider the join query ( ) from before. By definition, its variable set is , and is a fractional edge cover of weight at most . Thus, we can use a worst-case optimal join algorithm from Theorem 2 to compute ′ in time (| | ).

DISRUPTION-FREE DECOMPOSITIONS AND FRACTIONAL HYPERTREE WIDTH
In this section, we will relate disruption-free decompositions to fractional hypertree decompositions and the incompatibility number to fractional width. Let = ( , ) be a hypergraph. A hypertree decomposition D of is defined to be an acylic hypergraph ( , ) such that for every edge ∈ there is a ∈ with ⊆ . 1 The sets ∈ are called the bags of the decomposition. The fractional width of D is defined as max * ( ). The fractional hypertree width of is defined to be the minimial fractional width of any hypertree decomposition of .
Note that, with this definition, the disruption-free decomposition of a query and an order is a hypertree decomposition of whose fractional width is the incompatibility number of and .

O
11. Let be a join query and let be an order of its variables. Then the incompatibility number of and is at least the fractional edge cover number of .
Of course there are other hypertree decompositions D of that we could have used for a direct access algorithm. The only property that we need is that D has no disruptive trio for . If this is the case, then inspection of the proof of Theorem 10 shows that we get an alternative algorithm whose preprocessing depends on the fractional width of D. We will see next that this approach cannot yield better running times than Theorem 10. To this end, we prove that any alternative decomposition contains the disruptionfree decomposition in a way.

L
12. Given a join query and an ordering of its variables , and let D be a hypertree decomposition of with no disruptive trio. Then, for every edge of the disruption-free decomposition of , there exists a bag of D such that ⊆ .

P
. Let be the hypergraph of . Assume by way of contradiction that there is an edge of the disruption-free decomposition ′ of that is not contained in any bag of D. Since D is a hypertree decomposition of , for every edge of , the decomposition contains, by definition, a bag such that ⊆ . Thus, the edge of ′ not contained in any bag of D must be of the form ∪ { } where consists of the preceding neighbors of at the moment of creation of the edge; here, when we say 'preceding', we mean the neighbors that come before in . Consider the non-covered edge with the largest . We show next that every pair of vertices in appears in a common bag in . It is known that acyclic graphs are conformal [10]; that is, any set of pairwise neighbors must be contained in an edge. Thus, D has a bag containing , which is a contradiction.
Since is the largest non-covered edge, we know that D contains, for all edges ′ that were present at the moment of creation of , a bag with ′ ⊆ . Thus, for every variable ′ in , there is a bag of that contains both and ′ . Now consider 1 , 2 ∈ . If 1 , 2 are not in a common bag ′ of D, then 1 , 2 , is a disruptive trio of D, which is a contradiction to the conditions of the lemma. So 1 , 2 must appear in a common bag. It follows that the vertices of are all pairwise neighbors in D as we wanted to show.
Since the fractional edge cover number is monotone with respect to set inclusion, we directly get that the disruption-free decomposition is optimal in the following sense.

C
13. Let be a join query and let be an order of its variables. The disruption-free decomposition of and has the minimal fractional width taken over all hypertree decompositions of that have no disruptive trio with respect to .
Note that in general finding a optimal fractional hypertree decomposition is known to be hard [15]. However, in our case, decompositions are only useful if they eliminate disruptive trios. If we restrict the decompositions in that way, it is much easier to find a good decomposition compared to the general case: since the optimal decomposition is induced by the order, we get it in polynomial time using the procedure of Definition 4.

SET-DISJOINTNESS-BASED HARDNESS FOR DIRECT ACCESS
In this section, we show lower bounds for lexicographically ranked direct access for all self-join free queries and all variable orders. We first reduce general direct access queries to the special case of star queries, which we introduce in Section 5.1. Then we show that lower bounds for direct access to star queries follow from lower bounds for -Set-Disjointness, see Section 5.3. Later, in Section 6, we prove a lower bound for -Set-Disjointness based on the Zero-Clique Conjecture.

From -Star Queries to Direct Access
A crucial role in our reduction is played by the -star query ★ : as well as its variant ★ in which variable is projected away: We will always denote their input database by ★ . We say that a variable order is bad for ★ if is the last variable in .
Let ( ì ) be a self-join-free join query and let = ( 1 , . . . , ℓ ) be an ordering of ì . Let be the incompatibility number of and and assume > 1. If there is an > 0 such that for all > 0 there is a direct access algorithm for and with preprocessing time (| | − ) and access time (| | ), then there is a ∈ N, > 2 and ′ > 0 such that for all ′ > 0 there is a direct access algorithm for ★ with respect to a bad ordering with preprocessing time (| ★ | − ′ ) and access time (| ★ | ′ ).
P . We will use the concept of fractional independent sets. A fractional independent set in a hypergraph = ( , ) is a mapping : → [0, 1] such that for every ∈ we have ∈ ( ) ≤ 1. The weight of is defined to be ( ) = ∈ ( ). The fractional independent set number of is defined as * ( ) := max ( ) where the maximum is taken over all fractional independent sets of . Using linear programming duality, we have for every graph and every vertex set that * ( [ ]) = * ( [ ]). We use the same notation on join queries, with the meaning of applying it to the underlying hypergraph.
We use the notation and as in Lemma 7. Let be such that = * ( [ ]) where is the hypergraph corresponding to .
Then, by what we said above, we know that there is a fractional independent set : Since is the solution of a linear program with integer coefficients and weights, all values ( ) are rational numbers. Let be the least common multiple of the denominators of { ( ) | ∈ }. Now define a new weight function ′ : → {0, . . . , } by ′ ( ) := ( ). Let := . We will show how to simulate random access to ★ by embedding it into . To this end, every ∈ takes ′ ( ) roles, that is we assign ′ ( ) many of the variables 1 , . . . , of ★ to . We do this in such a way that for all pairs , ′ ∈ , whenever a variable comes before ′ in , then for every role of and every role of ′ we have that < . Moreover, for every we have that there is a unique variable ∈ whose role is . Note that ∈ ′ ( ) = ∈ = = , so this distribution of roles is possible. Now add as an additional role the role for every ∈ . Note that when doing so, the variable can have both some roles and the role . We now construct a database for , given an input database ★ for ★ . For every variable , denote by dom ★ ( ) the active domain in ★ . We fix all variables of that have no role to a constant ⊥. To simplify the reasoning, we will in the remainder ignore these variables, so only the variables in ∪ remain. Let us first sketch the embedding of ★ : the role of is to encode the middle vertex and connect it to all . To this end, we encode the choice of a vertex into each node in . Since induces a connected hypergraph, we can ensure that this choice of vertex is consistent among all nodes in . Since has edges to all nodes in , we can encode all relations ( , ). This allows us to simulate the star query 1 ( 1 , ), ..., ( , ).
We now proceed with the technical details. For each variable ∈ ∪ we define the domain as follows: let 1 , . . . , be the roles of given in the order defined by . Then the domain of is We order dom( ) lexicographically. Intuitively, takes the values of all its roles. To define the relations of , consider two cases: if none of the variables in an atom ( 1 , . . . , ) of plays the role , the relation is simply dom( 1 ) ×. . .×dom( ). Otherwise, let 1 , . . . , , be the roles played by variables in ( 1 , . . . , ). Then we compute the sub- . Note that there is an injection : → dom( 1 ) × . . . × dom( ) that consists of "packing" the values for the different variables into the variables of according to the roles in the following sense: for every tuple ì , maps each variable with role set R to the tuple we get from ì by deleting the coordinates not in R. The relation is then simply ( ). Note that the construction gives a bijection between ( ) and ★ ( ★ ): in all tuples in ( ), all variables that have the role must take the same value on the corresponding coordinate by construction, because is connected. Moreover, for every atom ( , ) of ★ , there is an atom of containing (not necessarily different) variables and such that has the role and has the role . By construction it then follows that on the corresponding components the values and take values that are consistent with the relation ★ . This directly gives the desired bijection. Also, given an answer to , we can easily compute the corresponding answer to ★ by "unpacking", i.e., inverting . Hence, a direct access algorithm for gives a direct access algorithm for ★ . Moreover, by construction, the correct order is maintained by . It remains to analyze the running time of this algorithm. We first show that the constructed instance can be computed reasonably efficiently.

P
. We show first that for every atom its variables in total have at most roles different from . To see this, let 1 , . . . , be the variables of . Then the overall number of non--roles is where the inequality comes from the fact that is a fractional independent set. Now for atoms in which no variable has the role , the claim follows directly. For the other atoms, the computation time is essentially that of computing the join ( ★ ), which can be computed in time (| ★ | ), since it involves at most atoms.
It follows that the size of is at most (| ★ | ). If for some > 0 and all > 0 there is a direct access algorithm for and with preprocessing time (| | − ) and access time (| | ), then by running this algorithm on the constructed instance we get direct access to ★ with preprocessing time: where we used > 1 and thus < − ′ = − ′ for sufficiently small ′ > 0. For any desired ′ > 0, by setting := ′ / the access time of this algorithm is (| | ) = (| ★ | ) = (| ★ | ′ ). This finishes the proof.
The situation of Lemma 14 simplifies for acyclic queries.
C 15. Let ( ì ) be an acyclic self-join-free join query and an order of ì with incompatibility number > 1. Then is an integer, and if has a direct access algorithm with preprocessing time (| |) and access time (| |), then so has ★ .

P
. If is acyclic and = ( , ) is its hypergraph, then [ ] contains a (non-fractional) independent set of size * ( [ ]) for every ⊆ . This is because in acyclic hypergraphs the independent set number and the edge cover number coincide [14].

From Set-Disjointness to Projected Stars
We observe that the testing problem for the projected star query ★ is equivalent to the following problem: Definition 17. In the -Set-Disjointness problem, we are given an instance I consisting of a universe and families A 1 , . . . , A ⊆ 2 of subsets of . We denote the sets in family A by ,1 , . . . , , | A | . The task is to preprocess I into a data structure that can answer queries of the following form: Given indices 1 , . . . , , decide whether We denote the number of sets by := |A | and the input size by I := ∈A | |. We call | | the universe size.

HARDNESS OF SET DISJOINTNESS
In this section, we will show lower bounds for -Set Disjointness, as defined in Definition 17. In combination with the reductions from the previous section, this will give us lower bounds for direct access in Section 7. The main result of this section is the following.  [27] showed that the same hardness holds under the Zero-3-Clique Conjecture (and thus also under the APSP Conjecture).
This implies Theorem 19 for = 2. In particular, by combining our previous reductions, for ★ 2 with a bad order there is no algorithm with polylogarithmic access time and preprocessing (| | 2− ), assuming any of the three conjectures mentioned above.

Case > 2
In the following, we show how to rule out preprocessing time ( I − ) for -Set-Disjointness for any ≥ 2. To this end, we make use of the Zero-( +1)-Clique Conjecture. Our chain of reductions closely follows the proof of the case = 2 by Vassilevska Williams and Xu [27], but also uses additional ideas required for the generalization to larger .

-Set-Intersection
We start by proving a lower bound for the following problem of listing many elements in a set intersection.

Definition 22.
In the -Set-Intersection problem, we are given an instance I consisting of a universe and families A 1 , . . . , A ⊆ 2 of subsets of . We denote the sets in family A by ,1 , . . . , , | A | . The task is to preprocess I into a data structure that can answer queries of the following form: Given indices 1 , . . . , and a number , compute the set 1, 1 ∩ . . . ∩ , if it has size at most ; if it has size more than , then compute any elements of this set. We denote the number of sets by := |A | and the input size by I := ∈A | |. We call | | the universe size. The main result of this section shows that -Set-Intersection is hard in the following sense. Later we will use this result to show hardness for -Set-Disjointness. We prove Theorem 23 in the rest of this section.
Preparations. To start our reductions, first note that finding a zero--clique in a general graph is equivalent to finding a zero--clique in a complete -partite graph. This can be shown using a reduction that duplicates the nodes and the edges times, and replaces non-existing edges by edges of very large weight.
For our construction it will be convenient to assume that the edge weights lie in a finite field. Recall that in the Zero-( + 1)-Clique problem we can assume that all weights are integers between − and , for some constant that may depend on . We first compute a prime number between 10( + 1) 2 and 100( + 1) 2 by a standard algorithm: Pick a random number in that interval, check whether it is a prime, and repeat if it is not. By the prime number theorem, a random number in that interval is a prime with probability Θ(1/log( )). It follows that in expected time (polylog( )) we find a prime in that interval.
Having found the large prime , we consider all edge weights as given in the finite field F . Note that is bigger than the sum of weights of any ( + 1)-clique in , so the ( + 1)-cliques of weight 0 are the same over Z and F . Thus, in the remainder we assume all arithmetic to be done over F .
We now want to spread the edge weights evenly over F . To this end, define a new weight function ′ : → F by choosing independently and uniformly at random from F : • one value , • for all ∈ +1 and all ∈ [ − 1] a value .
We next split F into intervals of size ⌈ / ⌉ or ⌊ / ⌋, where is a constant that we will choose later. In the following, always denotes an interval resulting from this splitting of F . We denote by the set of all tuples ( 0 , . . . , ) of intervals in F such that 0 ∈ =0 . Note that there are only ( ) tuples in and they can be enumerated efficiently: given 0 , . . . , −1 , the set − −1 =0 can be covered by ( ) = (1) intervals , and these intervals can be computed efficiently.
The Reduction. With these preparations, we are now ready to present our reduction. For every weight interval tuple ( 0 , . . . , ) ∈ we construct an instance of -Set-Intersection as follows. For any ∈ [ ] we construct Moreover, we consider the queries We first run the preprocessing of -Set-Intersection on the instance I = (A 1 , . . . , A ) and then query each ∈ with parameter := ⌈100 · 3 1− ⌉. For each answer +1 returned by some query ( 1 , . . . , ) we check whether ( 1 , . . . , +1 ) is a zero-clique, and if it is then we return this zero-clique.
After repeating this construction for every weight interval tuple ( 0 , . . . , ) ∈ , if we never found a zero-clique, then we return 'no'.
Correctness. Let us show correctness of the reduction. Since we explicitly test for each query answer whether it is a zero-clique, if contains no zero-clique then our reduction returns 'no'. We next show that if there exists a zero-clique then our reduction returns a zero-clique with probability at least .99. To this end, we use the following claim. 2. Let ( 1 , . . . , +1 ) ∈ 1 × . . . × +1 be a zero-clique. Then, with probability at least .99, there are less than 100 · 3 1− vertices ∈ +1 such that ( 1 , . . . , , ) has the same weight interval tuple as ( 1 , . . . , +1 ) and ( 1 , . . . , , ) is not a zero-clique.
Running Time. It remains to analyze the running time and to set the parameter . To this end, assume that for some > 0 -Set-Intersection with | | = and = Θ( 1− /2 ) can be solved with preprocessing time ( +1− ) and query time ( ) for := 4 , as promised by the theorem statement. Note that our constructed instances have universe size | | = | +1 | ≤ , and = ( 1− ), so by setting := 2 the -Set-Intersection algorithm can be applied.

Unique--Set-Intersection
As the next step, we show hardness of -Set-Intersection for = 1, and even if we get the promise that there is a unique answer to a query. We formally define this problem as follows.  P . Let I be an instance of -Set-Intersection with families A 1 , . . . , A of total size = |A | over universe of size | | = , and let = Θ( 1− ) be the query size bound. For every ℓ ∈ {log( ), . . . , log( )} and every ∈ [100 ln( )] we create an instance I ℓ, by subsampling with probability 2 −ℓ , i.e., starting from I and keeping each element in the universe with probability 2 −ℓ and otherwise deleting it from all sets in A 1 , . . . , A .
Note that in expectation the number of surviving universe elements in I ℓ, is | | · 2 −ℓ ≤ / = ( ). By a basic Chernoff bound, the same also holds with high probability. Hence, we can use the assumed algorithm for Unique--Set-Intersection to preprocess all instances I ℓ, . Then, given a query we run the algorithm for Unique--Set-Intersection on all instances I ℓ, , filter out ⊥-answers and any other answers that do not lie in the true intersection, remove duplicates, and return up to of the remaining answers.
Let us analyze this algorithm. Since we filter out wrong answers, all answers we return are correct. It remains to show that with good probability we return enough answers. To this end, fix a query and assume that the instance I has > 0 answers for that query. Pick ℓ such that + ∈ [2 ℓ−1 , 2 ℓ ] and consider what happens in the queries on the instances I ℓ, . For every answer , consider the event E that is isolated by instance I ℓ, , that is, survives the subsampling, but none of the other − 1 solutions survive the subsampling. This event has probability Assume first that ≤ 2 , so the above probability is at least 1 6 ≥ 1 20 . Then the probability that event is not isolated in any instance I ℓ, over all ∈ [100 ln( )] is at most (1− 1 20 ) 100 ln( ) ≤ −5 (using the fact 1+ ≤ ). By a union bound over all ≤ | | = answers, with probability ≥ 1 − −4 each of the answers will be isolated in some instance I ℓ, , so the Unique--Set-Intersection algorithm will return each answer at least once. Hence, we see all answers and can correctly return min{ , } of them. Now consider the case > 2 . We want to understand how many instances I ℓ, we have to query to make it likely that we have seen at least answers as unique solutions. To this end, we model this problem as a coupon collector problem where the answers are coupons and we want to collect of them. In every round, we get a coupon if one of the answers is isolated, that is, event E happens. Since the events E are disjoint, in each round we get a coupon with probability at least In case we get a coupon, it is a uniformly random one. Since < /2, as long as we have seen less than distinct coupons, the probability that the next coupon is a fresh one is at least half. In combination with the bound on getting a coupon, in each round we find a coupon that we have not seen before with probability at least 1 20 . In particular, the probability of not getting a new coupon in 100 ln( ) rounds is at most (1 − 1 20 ) 100 ln( ) ≤ −5 . Taking the union bound over parts, over all ∈ [100 ln( )] we see at least distinct coupons with probability at least 1 − 5 ≥ 1 − 1 4 . Then we correctly return distinct answers.
In both cases, with high probability we return the correct answer.
To analyze the running time, note that we construct 100 ln( ) = ( ) instances I ℓ, , so the preprocessing takes time ( − ). Also, each query to an instance I ℓ, takes time ( ) and since we make ( ) of them, the total time of all queries is ( ). Finally, note that the different answers can easily be collected in, say, a binary search tree on which all operations are in time (ln( )) = (1), so the queries to I can overall be answered in time ( ).

-Set-Disjointness
Recall that the -Set-Disjointness problem is defined similarly as -Set-Intersection, except that a query should just decide whether the intersection 1, 1 ∩ . . . ∩ , is empty or not. Here an instance I is given by a universe set and families A 1 , . . . , A ⊆ 2 , where we write A = { ,1 , . . . , , | A | }. We again let = |A | and I = ∈A | |. We again measure preprocessing time and query time independently.

P .
We describe an algorithm for Unique--Set-Intersection, using an algorithm for -Set-Disjointness. Let I be an instance of Unique--Set-Intersection consisting of sets A 1 , . . . , A . Assume w.l.o.g. that the universe of A is [ ]. We create instances of -Set-Disjointness for each ∈ [ log( )], by removing every ∈ whose th bit is 0 from the universe and from all sets in A 1 , . . . , A . Call the resulting sets A . For each we then define the instance I to contain the sets A and the same queries as the original instance I. We run the preprocessing of the -Set-Disjointness algorithm on all of the instances I . Now, given a query , we ask the same query for each instance I , for all ∈ [ log( )]. Let 1 , . . . , log ( ) be the answers of these queries, and let ∈ [ ] be the number whose th bit is for every ∈ [ log( )]. We check if is an answer to the query on instance I, and if so we return it. Otherwise, we return ⊥.
It is clear that the algorithm satisfies the claimed time bounds, so it only remains to show correctness. So fix a query. Note that the algorithm either returns an element in the intersection of the sets given by the query or ⊥. If the instance does not have a unique answer, then by definition both of these answers are correct, so there is nothing to show. Now assume that there is a unique element in the intersection. For values of such that th bit of is 1, the element is still in the intersection of the respective sets in I , so the oracle answers 1. For values of such that th bit of is 0, is deleted from all sets and there is no other element in the intersection, so the oracle answers 0. Thus, we get the binary representation of from the oracle calls as desired.
So far we measured running times in terms of , the number of sets. Next we show how to obtain lower bounds in terms of the input size I = ∈A | |. L 28. For any constants , > 0, if there is an algorithm that solves -Set-Disjointness with preprocessing time ( − ) and query time ( I ), then for any constant 0 < ≤ 2 there is an algorithm that solves -Set-Disjointness on universe size | | = Θ( ) with preprocessing time ( − /2 ) and query time ( (1+ ) ).

P .
For every instance I of -Set-Disjointness on universe size | | = Θ( ), we have that I = ( 1+ ). Now on I, the assumed algorithm for -Set-Disjointness takes preprocessing time where we used ≤ 2 in the last step. Observing that the query time is ( I ) = ( (1+ ) ) completes the proof.
Finally we are ready to prove the main result of this section: the hardness of -Set-Disjointness for all ≥ 2 based on the Zero-( + 1)-Clique Conjecture.
. Almost all algorithms discussed in this proof are randomized; we omit this word for readability.
Assume that there is a constant > 0 such that for all > 0 there is an algorithm for -Set-Disjointness with preprocessing time ( − ) and query time ( I ).

TIGHT BOUNDS FOR DIRECT ACCESS
In this section, we formulate and prove the main result of this paper on direct access, showing that the incompatibility number determines the required preprocessing time.
T 29. Let be a self-join free join query, be an ordering of its variables, and be the incompatibility number of , . Then there is an algorithm that allows lexicographic direct access with respect to the order induced by with preprocessing time (| | ) and logarithmic access time.
Moreover, if there is a constant > 0 such that for all > 0 there is an algorithm allowing lexicographic direct access with respect to the order induced by with preprocessing time (| | − ) and access time (| | ), then the Zero-Clique Conjecture is false. The quantifiers on ′ and ′′ match Theorem 19, which implies that the Zero-( + 1)-Clique Conjecture is false, in particular the Zero-Clique Conjecture is false. It remains to prove the second part for = 1 (since we always have ≥ 1). To this end, note that for any non-empty we can construct a database ′ of size (1) such that has exactly one answer on ′ . We add dummy tuples to ′ that are guaranteed not to be part of any answer, obtaining an instance of much larger size and still with exactly one answer. Now we permute the relations of at random. Then any algorithm reading (| | 1− ) tuples of reads the tuples appearing in the one answer to only with probability (1). It follows that there exists a permutation of such that the algorithm fails. Hence, no algorithm can decide whether has at least one answer in time (| | 1− ). In particular, no direct access algorithm can have preprocessing time (| | 1− ) and access time (| | 1− ). Thus, for any > 0 and := 1 − there is no algorithm for direct access with preprocessing time (| | 1− ) and query time (| | ). This lower bound is unconditional, proving the second part for = 1.
Therefore, if for some , > 0 there was an algorithm with preprocessing time (| | − ) and access time (log(| |) ), then for every ′ > 0 there would also be an algorithm with preprocessing time (| | − ) and access time (| | ′ ). It follows that the lower bound in Theorem 29 implies the lower bound for polylogarithmic query time stated in the introduction. We remark that from Theorem 29 we can also get a lower bound for direct access for unconstrained lexicographic order based on fractional hypertree width [16]. Adapting the order to the query, we directly get the following corollary that essentially says that if we want any lexicographic order in the preprocessing for direct access, then the fractional hypertree width determines the exponent of the preprocessing time.
C 30. Let be a self-join free join query of fractional hypertree width . Then there is an ordering of the variables of such that there is an algorithm that allows lexicographic direct access with respect to the order induced by with preprocessing time (| | ) and logarithmic access time. Moreover, if there is an order and a constant > 0 such that for all > 0 there is an algorithm allowing lexicographic direct access with respect to the order induced by with preprocessing time (| | − ) and access time (| | ), then the Zero-Clique Conjecture is false.

LOWER BOUNDS FOR ENUMERATION OF CYCLIC JOINS
In this section we show another application of the Zero--Clique Conjecture. Specifically, we prove enumeration lower bounds for cyclic joins, assuming the hardness of Zero--Clique. These lower bounds reprove a dichotomy from [9] under a different complexity assumption. First, in Section 8.1 we prove a lower bound for a variation of -Set-Intersection. In Section 8.2 we prove hardness of enumerating Loomis-Whitney joins, and then we use a reduction from Loomis-Whitney joins to general cyclic joins in Section 8.3.

Hardness of Set-Intersection-Enumeration
We start by defining an offline variant of -Set-Intersection, in which we want to enumerate all elements of all queried intersections.
As usual for enumeration problems, we assume that any algorithm for -Set-Intersection-Enumeration works in two phases: in a first phase, we preprocess the input into an index data structure. In a second phase, we enumerate the answers one after the other, measuring the efficiency of the algorithm in the delay, i.e., the time between two consecutive answers.
As before, we denote the number of sets by := |A | and the input size by I := ∈A | |. We call | | the universe size. We prove the following analogue of Theorem 23.
We prove the above lemma in the rest of this section. So assume that -Set-Intersection-Enumeration on universe size | | = can be solved in preprocessing time ( +1− ) and delay ( ) for some > 0 and := 4 .
We closely follow the proof of Theorem 23, and we only describe the differences. We need an additional source of randomness in the new edge weights ′ , therefore for every ∈ 1 we pick a random ∈ F and we subtract from every edge weight ′ ( , ) for each ∈ +1 , and we add to every edge weight ′ ( , ) for each ∈ 2 . This does not change the weight of a clique ( 1 , . . . , +1 ) ∈ 1 × . . . × +1 . In more detail, we now choose uniformly and independently at random from F : • one value , • for all ∈ +1 and all ∈ [ − 1] a value , and • for each ∈ 1 a value . We then define the new weight function ′ by setting for any , ∈ [ + 1] and any ∈ and ∈ : With this minor modification of ′ , we follow the rest of the construction verbatim, in particular we pick the same parameter := appears as an answer to some query ∈ . Thus, by enumerating all answers we enumerate all zero-cliques. In particular, if there exists a zero-clique, then the algorithm will find one. Since we filter the results for zero-cliques, it also holds that if there is no zeroclique then the algorithm will return 'no'. This proves correctness. It remains to analyze the running time. In total over all | | = ( ) instances, we need preprocessing time ( +1− + ) = ( +1− /2 ) for our choice of = 2 . To analyze the total delay, consider the following claim. 3. With probability at least .99, the number of cliques = ( 1 , . . . , +1 ) ∈ 1 × . . . × +1 such that is no zero-clique and the weight interval tuple of lies in is bounded by ( +1− ).
Let us first finish the correctness proof, and later prove the claim. Each clique as in the claim is a "false positive", that is, an answer to our queries that does not correspond to a zero-clique. It follows that with probability at least .99, all our -Set-Intersection-Enumeration instances together enumerate ( +1− ) answers before seeing the first answer that corresponds to a zero-clique. The total query time is then bounded by ( +1− + ) = ( +1− /2 ) for our choice of = 2 and = 4 . Together with the preprocessing, this solves Zero-( + 1)-Clique in time ( +1− /2 ) + ( +1− /2 ) = ( +1− /2 ), which contradicts the Zero-( + 1)-Clique Conjecture.
Note that the time bound here only holds with probability .99. We can make the time bound hold deterministically, by aborting the algorithm after an appropriate time ( +1− /2 ). Then the running time is deterministic, and the algorithm still finds a zeroclique with probability at least .99. We can boost the success probability by repeating this algorithm.
It remains to prove the claim.
Since there are ( +1 ) choices for ( 1 , . . . , , ), it follows that the expected number of non-zero-cliques with a weight interval tuple in is ( +1− ). The claim now follows from an application of Markov's inequality.

Hardness of Loomis-Whitney Joins
In this section, we prove the hardness of enumerating answers to Loomis-Whitney joins based on the hardness results from the previous section. Loomis-Whitney joins are queries of the form where for each ∈ [ ], we have that¯ = 1 , . . . −1 , +1 . . . , . When = 3, 3 is simply the (colored) triangle query: 3 ( 1 , 2 ) Loomis-Whitney joins are thus generalizations of the triangle join where instead of 3 nodes in a graph where every 2 share an edge, we are looking for nodes in a hypergraph where every − 1 nodes share an edge. Loomis-Whitney joins are of special interest because, as we explain in Section 8.3, they are in a well-defined sense the obstructions to a query being acyclic.
There is a naive way of designing constant delay algorithms for Loomis-Whitney joins: one can materialize the query result during preprocessing and then simply read them from memory in the enumeration phase. This solution requires preprocessing time (| | 1+1/( −1) ) using the algorithm by Ngo et al. [22] for Loomis-Whitney joins or, since has fractional cover size 1 + 1/( − 1), any worst-case optimal join algorithm from Theorem 2 will give the same guarantees. In this section, we show that this naive approach is likely optimal for enumeration of Loomis-Whitney joins.

Hardness of Cyclic Joins
In this section, we describe the implication of hardness of Loomis-Whitney joins on the hardness of other cyclic joins, and derive an enumeration lower bound for self-join free cyclic joins based of Zero--Clique. A known characterizarion of cyclic hypergraphs is that they contain a chordless cycle or a non-conformal clique (i.e., a set of pairwise neighbors that are not contained in an edge). By considering a minimal non-conformal clique, Brault-Baron [9] used this property to claim that every cyclic query contains either a chordless cycle or a set of variables such that there is no atom that contains all of them, but for every subset of size − 1 there is such an atom. In other words, by removing all occurrences of some variables, and removing some atoms whose variables are contained in other atoms, we can obtain either a Loomis-Whitney join or a chordless cycle join. In case of a chordless cycle, we can always use it to solve a chordless cycle of length 3 (also called a triangle), which can be seen as a Loomis-Whitney join of size = 3. An exact reduction from an enumeration problem 1 to an enumeration problem 2 constructs an input 2 to 2 given an input 1 to 1 in linear time such that there is a bijection that can be computed in constant time from the answers to 2 over 2 to the answers of 1 over 1 . Note that enumeration in linear preprocessing time and constant delay is closed under exact reductions.
Stated in different words, Brault-Baron [9] essentially proved the following lemma: L 34. Let be a self-join free cyclic join. There exists ≥ 3 such that there is an exact reduction from to .
By combining Lemma 34 with Theorem 33, we conclude the enumeration hardness of cyclic joins based on the hardness of Zero--Clique: they have no enumeration algorithm with linear preprocessing time and constant delay.
T 35. Let be a self-join free cyclic join. Assuming the Zero-Clique Conjecture, there exists an > 0 such that there is no enumeration algorithm for with preprocessing time (| | 1+ ) and delay (| | ).

CONCLUSION
In this paper, we identified a parameter that we call the incompatibility number of a join query and an order of its variables. We proposed an algorithm for direct access to the answers of a join query in the lexicographic order induced by the variable order, using a reduction to the acyclic case without disruptive trios which had been studied in [12]. The exponent of the preprocessing phase of this algorithm is exactly the incompatibility number. We then complemented this upper bound by a matching lower bound that shows that the incompatibility number cannot be beaten as the exponent of the preprocessing in the case of self-join free join queries, assuming the Zero-Clique Conjecture from fine-grained complexity theory. With only a minor change to the proof of our directaccess lower bounds, we also showed lower bounds for enumeration. First, we showed that for Loomis-Whitney joins we cannot significantly improve upon a simple algorithm that computes all answers during preprocessing, assuming the Zero-Clique Conjecture. Then, under the same assumption, we showed that acyclic queries are the only self-join free join queries whose answers can be enumerated in constant delay after linear preprocessing. This gives further evidence to a dichotomy that was already shown using a different complexity hypothesis.
Let us close with several directions for future research. First, we feel that it would be interesting to understand the role of self-joins for direct access. Are there queries with self-joins where the runtime is better than that of our algorithm? Or can our lower bounds be shown also in this setting under reasonable assumptions? Similarly, what can be said about queries with projections? Finally, if we only require the answers to be ordered by some of the attributes, while the order of the other attributes is arbitrary, how does this change the complexity of direct access? On a more technical level, we have seen that the Zero-Clique Conjecture is tightly linked to -Set-Intersection and -Set-Disjointness, which can be seen as variants of a join query. Thus, it seems plausible that there are additional applications of the Zero-Clique Conjecture in database theory, and it would be interesting to further explore such connections.