{'fraction_non_alphanumeric': 0.042317542699163824, 'fraction_numerical': 0.00934547736562696, 'mean_word_length': 3.8820071209737517, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Complexity Analysis

Even though query evaluation is a fundamental task in databases, known classifications of conjunctive queries by their fine-grained complexity only apply to queries without self-joins. We study how self-joins affect enumeration complexity, with the aim of building upon the known results to achieve general classifications. We do this by examining the extension of two known dichotomies: one with respect to linear delay, and one with respect to constant delay after linear preprocessing. As this turns out to be an intricate investigation, this paper is structured as an example-driven discussion that initiates this analysis. We show enumeration algorithms that rely on self-joins to efficiently evaluate queries that otherwise cannot be answered with the same guarantees. Due to these additional tractable cases, the hardness proofs are more complex than the self-join-free case. We show how to harness a known tagging technique to prove hardness of queries with self-joins. Our study offers sufficient conditions and necessary conditions for tractability and settles the cases of queries of low arity and queries with cyclic cores. Nevertheless, many cases remain open.


INTRODUCTION
Query evaluation is one of the most central problems in database systems. This task asks to compute the set of solutions to a given query over a given database. When treating both the database and the query as input, query evaluation is NP-complete [6]. Here, we adopt the data complexity point of view: the complexity is analyzed with respect to the database size, while the query size (which is usually small) is considered constant. In this setting, query answering takes polynomial time. However, not all queries are equally hard as for some queries this polynomial is much smaller than for others. Ideally, we would like to understand, given any specific query, how fast this query can be evaluated. As the number of solutions may be much larger than the input, considering the delay between solutions and not just the total computation time can be meaningful: the user does not have to wait for the entire computation to be done before seeing some of the solutions. The ideal time guarantee we can hope to achieve is linear time before the first solution (required to read the input and determine whether a first solution exists) and constant time between successive solutions (required to print the output).
In this paper we focus on joins and sometimes projections, the basic building blocks of queries, expressed as conjunctive queries. We know that any acyclic query with a free-connex form can be answered with linear preprocessing and constant delay. For acyclic queries that are not free-connex, we do not have an algorithm with such guarantees, but we do have algorithms with linear delay (and linear preprocessing). At this point, it is natural to ask: Are freeconnex and acyclic queries the only ones for which such efficient algorithms exist or should we keep looking for efficient algorithms for additional queries?
To answer this question, we have conditional lower bounds showing that other queries cannot be answered within these time bounds unless there would be a significant breakthrough in well-studied problems. However, these hardness results were only proved for self-join-free conjunctive queries, queries in which each relation appears at most once. More specifically, if a self-join-free query is acyclic but not free-connex, then the set of all its solutions cannot be computed in time linear in the input and output sizes, assuming Boolean matrices cannot be multiplied in quadratic time [1]. Moreover, one cannot even produce a single solution to a self-joinfree cyclic query in linear time, assuming hypercliques cannot be detected in linear time [3]. The hardness results described in this introduction also assume the hardness of the two above mentioned algorithmic problems.
For years, database researchers were satisfied with these hardness results despite the limitation to self-join-free queries, as selfjoins are known to be problematic. We remark that in some contexts, e.g. graph databases, self-joins are very common. It was believed that the above characterization would extend to queries with self-joins and that this restriction is merely a limitation of our lower-bound tools. This extension was even claimed along with a proof sketch [3]. However, Berkholz, Gerhardt, and Schweikardt [2] recently refuted this claim by showing a cyclic query with selfjoins that can be evaluated efficiently. That is, we now know that queries with self-joins can be easier than self-join-free queries of the same form. Now that we have an example that shows it is possible, we would like to understand how, and in which cases, self-joins can be used to streamline query evaluation. Here, we initiate the complexity analysis for the evaluation of conjunctive queries with self-joins.
To illustrate the intricacies that arise with self-joins, consider the task of finding all occurrences of the following patterns in a node-colored directed graph (where the red circle denotes a red node). Note that these tasks can be phrased as conjunctive queries with self-joins, containing one binary relation describing the edges and one unary relation describing the red nodes. We will see that 1 , even though cyclic, can be enumerated with constant delay after a linear preprocessing time. Unlike the selfjoin-free case, adding a unary atom to a query may change its complexity: we will see that 2 can be answered with linear delay but not with constant delay (after only linear preprocessing). However, for 3 (that differs from 1 by the direction of one edge), we cannot even produce one solution in linear time. This again differs from the self-join-free case, in which the variable order in atoms cannot affect the complexity.
In this paper, we explore the effects of self-joins on query evaluation complexity from an enumeration point of view. The aim is to use known results for the self-join-free case to reason about general queries that may contain self-joins. We show enumeration algorithms that rely on self-joins to efficiently evaluate queries that otherwise cannot be answered with the same guarantees. Due to these additional tractable cases, the hardness proofs also require additional complications compared to the self-join-free case. We show how to harness a known tagging technique to prove hardness of queries with self-joins.
We discuss the difficulty in proving lower bounds for queries with self-joins in Section 3 and then define the tagging technique and explain the importance of endomorphism images for its analysis. Section 4 uses this technique to establish that self-joins do not change whether a query of arity two or less can be enumerated with constant delay. In Section 5, we show that queries with a cyclic "core" are hard in the sense that they cannot be answered with only linear preprocessing, even if they contain self-joins. As a result, we focus on queries with an acyclic core in the rest of the paper.
Next, we focus on full conjunctive queries, with no projection. In Section 6, we phrase a sufficient condition and a necessary condition for enumeration with linear delay, but we also give examples of cases where these conditions are not enough. In Section 7, we identify a class of cyclic queries that can be answered with constant delay (we call these mirror queries). We then provide an exampledriven discussion of how simple acyclic additions (unary atoms and spikes) to tractable queries can affect the complexity. We finish with a simple (single-cycle) query of unknown complexity. Missing details appear in the appendix.

PRELIMINARIES
A database is a finite relational structure consisting of a relational schema , a finite domain , and for each relational symbol of of arity , a subset of . A term (¯ ) where¯ ∈ is called a fact of .
In this paper, query always refers to a conjunctive query, i.e. a conjunction of atoms (¯ ), where ∈ and¯ is a tuple of variables of the appropriate arity, with some of the variables existentially quantified. The variables that are not quantified in are called the free variables of . The arity of a query is the number of its free variables. A Boolean/unary/binary query is a query of arity 0/1/2 respectively. A query is full if it contains no quantified variables, i.e. all the variables are free. A query has self-joins if it contains two atoms with the same relational symbol; otherwise, it is called selfjoin-free. For example, the query ( 1 , 2 )∧ ( 2 , 3 ) has self-joins while the query ( 1 , 2 ) ∧ ( 2 , 3 ) is self-join-free.
We will often specify full conjunctive queries using a colored hypergraph rather than a formula. Each node represents a variable of the query and is depicted by the number of the variable or a black dot when this number is not relevant. Each colored edge represents a binary atom, and each colored circle around a node represents a unary atom. The exact relation names are not depicted, but they are irrelevant to the complexity analysis. As an example, 2 of Figure 1 defines the query . We sometimes use a big circle to represent a relation of arity three or more (as in 6 of Figure 3). When we do so, the order of the variables in this relation is not important for the example.
A query is acyclic if it has a join tree. A join tree for the query is a tree such that the nodes of are the atoms of and, for each variable of , the nodes of whose atoms contain are connected in . An acyclic query is said to be free-connex if we obtain an acyclic query by adding to a new atom containing all the free variables of . As an example, the acyclic query is acyclic. In fact, it follows from the definition of free-connexity that full acyclic queries are always free-connex. Similarly, Boolean or unary acyclic queries are free-connex as well.
The solutions of a query over a database are denoted by ( ). They correspond to the set of tuples¯ such that: there exists an assignment of the elements of the domain of to the variables of making every atom of a fact of , and¯ is the assignment to the free variables of . When we specify a solution to a query, we assume the free variables are ordered according to their numbering. The output size is the number of tuples in the set ( ). Two queries and ′ are said to be equivalent if for every database , ( ) = ′ ( ).
An endomorphism of is a mapping from the variables of to the variables of that preserves the atoms of ; that is, if (¯ ) is an atom of and is an endomorphism of , then ( (¯ )) is also an atom of . An automorphism is an injective endomorphism. A query is said to be minimal 1 if any endomorphism of that is the identity on the free variables of is an automorphism of . Notice that every self-join-free query is minimal as the only endomorphism in such a query is the identity mapping. Any query has an equivalent minimal query, called the minimal form of in what follows.
The problems we consider are parameterized by a query and take as input a database . The evaluation problem computes the set of solutions ( ). The testing problem asks whether ( ) is empty. The enumeration problem is decomposed into two phases: the preprocessing phase computes a data structure that is used during the enumeration phase for outputting the solutions of ( ) one by one and with no repetition. The maximal time between two consecutive answers during enumeration is called the delay.
We use the RAM computation model with uniform addition and multiplication, and we adopt the data complexity point of view. That is, the constants hidden in the big notation may depend on the query but not the database. The input size, denoted || ||, corresponds to the size of a reasonable encoding of the database , linear in the number of database tuples. Note that an enumeration algorithm with linear preprocessing implies that the testing problem can be solved in linear time. A constant delay after linear preprocessing enumeration algorithm implies that the evaluation problem can be solved in linear input plus output time.
Many known enumeration algorithms for database queries conform to a strict definition of linear preprocessing and constant delay where the memory used during preprocessing is linear and the extra memory used after the preprocessing remains bounded by a constant [1,[7][8][9][10]. Our enumeration algorithms use the allowed time in the most general way, without memory restrictions. In particular, we assume we can test in constant time whether a given tuple is a fact of the database. It is not clear how to do this test without using perfect hashing, which requires polynomial memory in the size of the input database. The enumeration phases of our algorithms may also require a total memory of a similar size. This is required to store each produced solution (or parts of the solution), used later for producing more solutions. As this distinction is important, we will make it explicit when we use this extra memory. This is in particular the case in the proof of the Cheater's Lemma [5] that we use to eliminate duplicate answers.

L
1 ((C ' L ) [5]). Let be a conjunctive query. If there is an algorithm evaluating with linear preprocessing time and constant/linear delay, where the number of times each output is produced is bound by a constant, then there is an enumeration algorithm for that runs with linear preprocessing time and constant/linear delay, producing the solutions with no repetition. This new algorithm may use during the enumeration phase a memory of size (|| || | | ) over an input database .
As usual in this area, our lower bounds assume algorithmic conjectures, described next. A hypergraph is ( − 1)-uniform if every hyperedge is of size − 1. A -hyperclique is a set of nodes such that any subset of these nodes of size − 1 forms a hyperedge.
• BMM conjectures that two Boolean matrices and , represented as lists of their non-zero entries, cannot be multiplied in time ( ), where is the number of non-zero entries in , , and .

• H
conjectures that for all ≥ 3, it is not possible to determine the existence of a -hyperclique in a ( −1)uniform hypergraph with hyperedges in time ( ). • H conjectures that for all ≥ 3, it is not possible to determine the existence of a -hyperclique in a ( − 1)uniform hypergraph with nodes in time ( −1 ). Notice that H implies that we cannot detect a triangle in an undirected graph in linear time. H implies the sparse hypotheses H and BMM. We can now state the known results for query evaluation.
Let be a self-join-free conjunctive query. • If is cyclic, the testing problem cannot be solved in linear time, assuming H . • If is acyclic, the enumeration problem can be solved with linear delay and linear preprocessing. • If is acyclic but not free-connex, the evaluation problem cannot be solved in linear time in the input plus output sizes, assuming BMM.
• If is acyclic and free-connex, the enumeration problem can be solved with constant delay and linear preprocessing.
In the above theorem, the upper bounds also hold for queries with self-joins. The enumeration algorithms obtained in [1,3] use the strict definition of constant delay, where the total memory used during the enumeration phase only adds a constant to the memory used during the preprocessing phase.

PROVING HARDNESS WITH SELF-JOINS
Since we have a good understanding of the complexity of selfjoin-free queries, we are interested in comparing the complexity of general conjunctive queries to self-join-free queries with the same shape. More formally, we associate a self-join-free query ′ to any query by giving distinct names to all relation symbols. As an example, the self-join-free query associated to . Notice that this modification does not affect properties such as acyclicity or free-connexity.
Going from a query to its associated self-join-free query ′ can only make the evaluation task harder. This folklore proposition holds since ′ can be used to compute , and it implies that the upper bounds of Theorem 2 also hold for queries with self-joins. 3. For any conjunctive query , its associated selfjoin-free query ′ is at least as hard as for the evaluation problem, the testing problem, and the enumeration problem.
When trying to show the other direction, reducing the self-joinfree query to its initial query with self-joins, we need more care. Let us now explain why the lower bounds of Theorem 2 only apply to self-join-free queries.
. Theorem 2 proves that the ability to determine whether ′ 1 has answers in linear time would imply finding triangles in an undirected graph in linear time, which is conjectured to be impossible. The reduction works as follows: for every edge ( , ) of the input graph with < , 2 we add to the database the facts: 1 ( , ), 2 ( , ), 3 ( , ), and 4 ( , ). With this construction, every answer to ′ 1 is of the form ( , , , ) such that ( , , ) is a triangle. If we try to use the same technique to prove the hardness of 1 , we encounter the problem that we cannot assign different atoms with different relations. In particular, if we add to the database the facts ( , ) and ( , ) for every edge ( , ) of the graph, the query 1 will also have solutions corresponding to 2-paths (where every atom maps to the edge relation and 2 and 4 map to the same value). Thus, we do not get that the query has a solution iff the graph has a triangle.
To prove the hard cases, we need a technique that allows us to assign different relations to different atoms despite the self-joins. For this reason, we will use variations of the tagging technique described below that aims to assign different variables with different domains by concatenating the variable names to the domain values.
Tagging technique. 3 Let be a minimal conjunctive query and ′ be its associated self-join-free query. Let ′ be a database for ′ . We construct a database for as follows. Let 1 (¯ ) be an atom of ′ associated to the atom (¯ ) of , where is of arity . For every fact 1 (¯ ) of ′ , we add to the fact ( 1 , 1 , . . . , , ).
With this construction, every element of the domain of is of the form , . We refer to as the data part and to as the tag. Let us now inspect ( ). Every solution ( 1 , 1 , . . . , , ) in ( ) is witnessed by an assignment associating an element of to every variable of . As above, can be split into two parts: a data map associating to whenever ( ) = , and a tagging map associating to in the same cases. The data part of the solution of is ( 1 , · · · , ). Notice that every solution to ′ ( ′ ) appears as a data part of a solution of ( ) with an identity tagging map. For the converse direction, consider a solution of ( ). There are two cases.
(1) If the tagging map is an automorphism, then the data map contains a solution of ′ ( ′ ) as follows. Consider the mapping ′ defined by ′ ( ) = ( −1 ( )). It clearly witnesses a solution of ( ) with an identity tagging map whose data part then belongs to ′ ( ′ ). (2) If the tagging map is not an automorphism, the data part of the solution may then not correspond to a solution in ′ ( ′ ).
If is minimal and the tagging map is the identity on the free variables, then must be an automorphism. Thus, when using the tagging technique, solutions with the identity tagging map are the ones we wish to return in order to answer ′ , and we need to ensure that there are not too many interfering solutions of the other cases.
We will see that if the query is of low arity, then the number of extra solutions remains small and so they be ignored without incurring a high cost. For full queries, other solutions of the first case are not a problem: As we are given the assignment to all variables as part of a solution, we can compute ′ and an answer to ′ given any such solution to . Every solution to ′ will be obtained a constant number of times this way, once for each automorphism, and these duplicates can be eliminated using the Cheater's Lemma. Solutions of the second case are the ones we need to beware of. For this technique to result in a useful reduction, we need to limit the number of these extra solutions, and this cannot always be achieved. We summarize the discussion above into the following lemma.
Let ′ be the self-join-free query associated with a minimal conjunctive query , and let be the database for constructed using the tagging technique from a database ′ for ′ . Then, ′ ( ′ ) is precisely the data parts of those solutions to ( ) in which every free variable is assigned itself as a tag. Moreover, if is full, then each solution to ( ) tagged by an automorphism can be translated in constant time to a solution of ′ ( ′ ) such that each solution of ′ ( ′ ) is obtained a constant number of times.
The following is an example of the tagging technique and how it can fail to prove hardness due to extra solutions. Later in the paper, we will see how this difficulty can be circumvented in some cases so that the tagging technique works. Example 6. Consider ′ 1 and 1 from Example 4. Notice that 1 has two automorphisms: the identity and the one that switches 2 and 4 . It also has two other endomorphisms: the one that maps 2 and 4 to 2 , and the one that maps them both to 4 . Consider the database ′ consisting of the four facts 1 ( , ), 2 ( , ), 3  , 2 ). In other words, these answers contain two copies of the initial solution ( , , , ), one per automorphism of 1 . However,

QUERIES OF LOW ARITY
We use the tagging from the previous section to show that selfjoins do not affect the tractable cases for constant delay enumeration of conjunctive queries with few free variables.
For Boolean and unary queries, the number of solutions is at most linear in the database size. If we could compute the entire solution set in linear time then constant delay enumeration easily follows. This situation is characterized by the following result. P . If is cyclic then its associated self-join-free query ′ is also cyclic and therefore hard by theorem 2. We reduce the evaluation of ′ to the evaluation of using the tagging technique and extract the solutions to ′ as in lemma 5. As is at most unary, it has a linear number of solutions, and so we can ignore the extra solutions at a low cost.
We remark that, while Theorem 7 implies that cyclic unary queries cannot be enumerated with constant delay, it does not imply the same for linear delay. In fact, the cyclic unary query 4 ( ) defined as ∃ ( , ) ∧ ( , ) ∧ ( , ) ∧ ( , ) ∧ ( ) can be enumerated with linear delay. It remains open to characterize the unary queries with respect to linear delay.
We show a similar result to that of Theorem 7 for binary queries using the non-sparse version of the hypothesis. 8. Let be a minimal binary conjunctive query. If is not acyclic free-connex, then there is no linear preprocessing and constant delay enumeration algorithm for answering , assuming H .

P
. Let be a minimal binary query and ′ be its associated self-join-free query. Assume that is cyclic. In the selfjoin-free case, a known construction [3] encodes the hyperclique detection problem into solving any cyclic query over a database with domain values, where is the number of vertices in the hypergraph. Hence, a solution to ′ cannot be computed in linear time, assuming H . Using the tagging technique, the number of extra solutions to ( ) is bounded by ( 2 ). So, for any ≥ 3, the time necessary to ignore the unwanted solutions falls within the allowed time of ( −1 ) for testing the existence of a -hyperclique. The acyclic non-free-connex case is similar.

QUERIES WITH A CYCLIC CORE
Given a conjunctive query with free variables¯ , let be the minimal form of the Boolean query ∃¯ . We denote by the core of the query constructed from by removing all quantifications. Notice that the core of is a full query that may not be equivalent to . Notice also that an acyclic query has an acyclic core but the converse is not necessarily true: the core of the cyclic query 1 of Figure 1 is acyclic. Observe that a query has a solution iff its core has a solution. Hence the following result is an immediate consequence of Theorem 7.

T 9.
It is possible to test in linear time whether a conjunctive query has a solution iff it has an acyclic core, assuming H .
Example 10. Consider the full conjunctive query 3 depicted by Figure 1. The core of the query is the query itself and is therefore cyclic. It follows from Theorem 9 that the query is hard, i.e. we cannot test whether it has a solution in linear time.

FULL CONJUNCTIVE QUERIES AND LINEAR DELAY
Assuming H , acyclic self-join-free queries can be enumerated with linear delay (after linear preprocessing) while cyclic self-join-free queries cannot. We now ask how self-joins affect this classification. Following proposition 3 and Theorem 9, it remains to handle cyclic queries with an acyclic core. In this section, we begin this investigation by considering only full queries of this form. We start with a simple example showing that some cyclic queries with self-joins can be enumerated with linear delay.
Example 11. Consider the full query 2 of Figure 1. It can be enumerated with linear delay as follows. We enumerate the solutions of the core of 2 , depicted by 1 2 3 . As the core is acyclic and free-connex, by Theorem 2, this can be done with constant delay after linear preprocessing. For each solution ( , , ) of the core, we try all elements of the database and test, in constant time, whether is connected to and as specified by 2 . If it is, we output the solution ( , , , ). Remark that any solution ( , , ) to the core gives rise to a solution ( , , , ) to 2 . Thus, at least one solution to 2 is printed for each solution to the core, and so the delay is at most linear.

Sufficient condition
We now present a sufficient condition for enumeration with linear delay that builds on two key concepts: image and untangling.
Consider an endomorphism of a full query . The full query consisting of all atoms ( ( ì )) such that ( ì ) is an atom of is called an image of . Figure 2 depicts examples of images. By definition, the core of is an image. Another trivial image is the query itself.  Figure 2: The query 5 and its images. We depict images in dark and the corresponding endomorphisms in dotted gray. Self-loops are not depicted for readability.
The key property of images is that any solution to the image yields a solution to the full query: Simply instantiate any variable of the query by the value of its image. As an example, for the query The restriction of a conjunctive query to a set of its variables , denoted | , is the query obtained from the self-join-free query associated to by removing all variables not in from its atoms. Notice that the arities of the relations may change. An untangling of is a sequence of images 0 , . . . , of such that: 0 = , is acyclic, and for all 0 ≤ < : +1 is an image of and the restriction of to its variables that do not appear in +1 is acyclic.
Example 12. Consider the queries 6 and 7 depicted in fig. 3. They have the same acyclic core, namely the ternary relation and the three binary relations forming a triangle inside of it. The figure shows an untangling for 6 and illustrates why there is no such untangling for 7 . Another example of a query that can be untangled is given in fig. 9 in the appendix.
T 13. Any full conjunctive query that has an untangling can be enumerated with linear delay (after linear preprocessing time).

P
. Let 0 , 1 , · · · , be an untangling of . The proof goes by induction on . If = 0, then the query is acyclic and can be enumerated with linear delay by Theorem 2. If > 0, consider the image 1 . Let ′ be the restriction of to its variables not in 1 . By construction, ′ is acyclic and can be enumerated with linear delay. By induction, 1 can be enumerated with linear delay. We show that can then be enumerated with linear delay as well.
On an input database , the enumeration of works as follows. We start the enumeration for 1 . For each solution¯ to 1 , as witnessed by a mapping from the variables of 1 to the elements of , we compute in linear time a database ′ over the schema of ′ as follows. By definition, each atom ′ (¯ ) of ′ is computed from an atom (¯ ) of by removing all variables in 1 . We filter ( ì ) to only keep the tuples that "agree" with ì , and then we project the result to only keep the columns corresponding to ì . More formally,  Figure 3: The query 6 (the circle depicts a ternary relation) followed by an acyclic image and the result of the corresponding restriction, making the sequence 6 , an untangling of 6 . By Theorem 13, 6 can be enumerated with linear delay. The sequence 7 , is not an untangling of 7 because the resulting query is cyclic. In fact, 7 cannot be untangled and we show in Example 14 that its enumeration is hard.
let ì be the variables of¯ occurring in 1 and ì those not occurring in 1 . Then, ′ ( ′ ) consists of all the tuples (ì ) such that is a mapping from¯ to a tuple of with ( ì ) = ( ì ). We then start the enumeration for ′ on ′ . Every solution to ′ can be combined with¯ to form a solution to , and the algorithm outputs all solutions with no repetitions. Since 1 is an image, each yields at least one solution to ′ , and we get linear delay.

Necessary condition
We provide a condition identifying full queries that cannot be enumerated with linear delay, assuming H . We essentially reduce H to the computation of a constant number of solutions to the query in linear time. The construction is illustrated in the next example.
Example 14. Consider again the query 7 , depicted in Figure 3. We show that we cannot produce 3 solutions to 7 in linear time unless we can test in ( ) time whether a graph with edges contains a triangle (which is not possible assuming H ). Given an input graph , we construct a database as follows. For every edge ( , ) of with < , we add to the facts ( , 6 , , 8  A case analysis on the tagging map, displayed in Figure 4, shows that the data part of each solution to 7 contains either the elements with ⊥ or we can extract from it a triangle of . As there are only a constant number of solutions of the first kind, any linear delay algorithm will test the existence of a triangle of in linear time.
Theorem 15 builds upon the idea underlined in Example 14, and provides a necessary condition for linear delay tractability. An endomorphism of a query is said to be idempotent if it is the identity Figure 4: Illustrations of solutions to 7 obtained by the core tagging map, the tagging that maps the right side to the left, and the identity tagging map.
on its image. As an example, in Figure 3 the endomorphism witnessing is idempotent while the one for is not.
T 15. Let be a full conjunctive query. If contains a set of variables such that the restriction | is cyclic, and all its endomorphisms are idempotent and have an image containing either all the variables in or none of them, then cannot be enumerated with linear delay (and linear preprocessing), assuming H .

P
. We show that the enumeration for is at least as hard as the enumeration for | , using a construction that assigns the constant ⊥ to the extra variables and a case analysis according to the endomorphism producing each answer. The idempotency and the fact that each image that contains a variable of contains all variables of guarantee that each answer that contains a non-constant value corresponds to an answer to | .

Other cases
The conditions from Section 6.1 and Section 6.2 do not cover all queries. We conclude this section with an example-driven illustration of the difficulty in achieving a full classification for full queries. We first give one example of a query that can be enumerated with linear delay but cannot be untangled. We next give an example of a query that cannot be enumerated with linear delay but does not fulfill the condition of Theorem 15. Finally, we specify a third query for which the complexity we do not yet know.  Example 16. Consider the query 8 of Figure 5. The core of the query is the ternary atom and the triangle within it and is therefore acyclic. The query cannot be untangled because the core is the only acyclic image and the result of the associated restriction yields a query with a cyclic core. The reader can also verify that the condition of theorem 15 is not met. Nevertheless, 8 cannot be enumerated with linear delay unless we can find a triangle in a graph in time linear in the number of its edges, a special case of H . The proof idea is that we encode the triangles of the graph into both query triangles that are not covered by a ternary relation and assign constants to all other variables. Except for one solution, all solutions over this encoding identify triangles in the input graph, though they do not all originate in the same query triangle. The details can be found in the appendix.
Example 17. Consider the query 9 depicted in Figure 5. Its core is a self-loop and is acyclic. One can verify that this query cannot be untangled. However, its solutions can be efficiently enumerated as follows. For each edge ( , ) of the database, we maintain two lists: the list of self-loops such that ( , ) and ( , ) are edges, and a similar list of self-loops where ( , ) and ( , ) are edges. The algorithm goes through all self-loops , and for each such self-loop, we consider all edges ( , ). If the triple ( , , ) satisfies any of the two patterns, we add to the corresponding list for ( , ). In addition, if ( , , ) satisfies the first pattern, then for each ′ in the second list for ( , ), we output the solution ( , , , ′ ). Similarly, if ( , , ) satisfies the second pattern, then for each ′ in the first list for ( , ), we output the solution ( ′ , , , ) (unless ′ = = = for avoiding duplicates). It can be easily verified that all solutions are printed and that no solution is printed twice. Moreover, as every self-loop results in a solution ( , , , ), the algorithm exhibits linear delay. It is worth noting that, as before, the memory this algorithm uses may be linear in the output size (which may be larger than linear in the database size).
Example 18. Finally, consider the query 10 of Figure 5. It cannot be untangled. The ideas used in example 17 can no longer be used as the middle part is now a path of length two and there may be more than a linear number of those. The idea from Example 16 does not work either because similarly encoding triangles yields a linear number of non-triangle solutions. Whether 10 can be enumerated with linear delay remains open.

FULL CONJUNCTIVE QUERIES AND CONSTANT DELAY
In this section, we aim to distinguish the queries that can be enumerated with constant delay after a linear time preprocessing from those where this is not possible. As in the previous section, all our queries will be full cyclic queries with an acyclic core.

Mirror queries
We start by showing that some cyclic queries can be solved with constant delay following linear preprocessing due to self-joins. This happens when half of the query can be seen as a reflection of the other half, as demonstrated in the following example.
Example 19. The cyclic query 1 of Figure 1 can be enumerated with constant delay as we describe next. First notice that the core of 1 , depicted by 1 2 3, is acyclic and free-connex, and so by Theorem 2, can be enumerated with constant delay after linear preprocessing time. We will maintain a table, initialized as empty, that on entry a pair ( , ) returns a list of elements such that ( , , ) is a solution to . The enumeration of 1 works as follows. We perform the preprocessing necessary for , start its enumeration, and for every solution ( , , ) we do the following. First, we output the solution ( , , , ). Then, for every ′ that is given by the table for the entry ( , ), we output the solutions ( , , , ′ ) and ( , ′ , , ). Finally, we add to the table entry ( , ). We get that the delay is constant, and every result is printed once. example 19 puts forward the following sufficient condition. We call a query a mirror if it has an acyclic image such that the remaining atoms form a query isomorphic to , where the isomorphism is the identity on the variables shared between the image and the remaining atoms. P 20. Any full mirror conjunctive query can be enumerated with constant delay after a linear preprocessing time.
As in example 19, in the proof of proposition 20 we use during the enumeration a memory linear in the output size (which may not be linear in the input size).

The effect of unary atoms
In contrast to the self-join-free case, we show that unary atoms can affect query complexity. Intuitively, when adding a unary atom to one of the sides of a mirror query, the solutions to this side no longer form all possible solutions to the other side, and so the algorithm we proposed for mirror queries fails. The following example differs from the previous one only by the addition of a unary atom.
Example 21. Consider again the query 2 depicted in Figure 1. We have seen in Example 11 that it can be enumerated with linear delay. It turns out that it cannot be enumerated with linear preprocessing and constant delay unless we can test in linear time whether a graph contains a triangle, contradicting H . Given a graph with edges, we construct a database as follows. For every edge ( , ) of with < , we add to the facts ( , 1 , , 2 ), ( , 2 , , 3 ), ( , 1 , , 4 ), and ( , 4 , , 3 ), together with the fact Red( , 2 ). By considering all endomorphisms of 2 , as we explained when introducing the tagging technique, we get that a solution in ( ) is either obtained by the identity automorphism and so it is of the form ( , 1 , , 2 , , 3 , , 4 ) for a triangle ( , , ) in , or it is obtained by the endomorphism that maps 4 to 2 and so it is of the form ( , 1 , , 2 , , 3 , , 2 ) for an edge ( , ) in . As there are at most solutions of the latter kind, any constant delay enumeration of in would be able to test in ( ) whether has a triangle.
This added difficulty is caused by any structure that breaks the symmetry between the two sides. As an example, we could replace the unary atom in 2 by a directed path of length 2 starting in 2 and still obtain the hardness with a similar proof.

The effect of "spikes"
While introducing unary atoms can make queries harder, we will now see that introducing "dangling" binary atoms may make queries easier. Consider the query 5 of Figure 2 together with the three queries depicted in Figure 6. Notice that all four agree on the central loop and have the same acyclic core 1 2 3 . They can be untangled and therefore enumerated with linear delay due to Theorem 13. We prove in the sequel that 11 and 12 can even be enumerated with constant delay, while 5 and 13 cannot without a major computational breakthrough.  Removing the unary atom from 5 results in a mirror query that can be enumerated with constant delay according to Proposition 20. This unary atom renders 5 difficult, and the proof (in the appendix) is similar to that of Example 21. The spikes of 11 make it so that all cycle edges appear in an acyclic image. This can be used to devise an efficient algorithm as we explain next. We go through all edges outgoing from and all edges incoming to to get a solution to 11 in constant delay. Altogether, we get a constant delay algorithm that outputs all solutions to 11 , possibly 3 times. We remove the duplicates using the Cheater's Lemma.
We show next that 12 can also be efficiently solved even though it does not have acyclic images covering all edges of the main loop.
Example 23. The query 12 can be enumerated with constant delay using its images depicted in fig. 8. The idea is that we enumerate the solutions to the small image, and for every such assignment, we have a way to efficiently find all solutions that extend it. We first find all of its extensions to the top image and print the solutions implied by these. While we do this, we store the possible assignments to 7 . Then, we do the same with the left image and store the possible assignments to 6 . Next, We go over all pairs of value for 6 and value for 7 and check whether there is an edge between them. If there is an edge, we have found a non-trivial assignment to the cycle, and we can enumerate all possible spike assignments to get all solutions to the full query. The crux of this proof is that we can show that the number of pairs of values we need to check is bounded by the number of "simple" solutions we find using the two images. Thus, the "simple" solutions provide enough time to perform this computation while still achieving constant delay.
The tractability that the spikes of 12 introduce does not stem from the mere number of spikes. We next give evidence of the difficulty of enumerating the answers to the query 13 , which differs from 12 only by the direction of one edge.
Example 24. We can show that efficient enumeration for 13 would imply a breakthrough in algorithms for triangle detection in unbalanced tripartite graphs, contradicting the following hypothesis. The Vertex-Unbalanced Triangle Detection (VUTD) hypothesis 5 assumes that, for every constant ∈ (0, 1], it is not possible to test the existence of a triangle in a tripartite graph with vertex sets | | = and | | = | | = Θ( ) in time ( 1+ ). We encode triangle finding with tagging in the query like before, with two additional tricks. To handle the two spikes leaving 5 , the value tagged by 5 corresponds to an edge between and . The same idea cannot be applied to 8 as it would result in an image that contains vertices of the three parts that do not correspond to a triangle. The spike leaving 8 makes one of the images correspond to two edges between and . Here, we rely on the fact that our input graph is unbalanced to claim that there are at not too many solutions of this kind.

An open problem
The techniques developed above for constant delay algorithms or hardness proofs fail on the full query 14 depicted below, and its classification is left for future work. Note that 14 is not a mirror, even though it consists of only one cycle and it has an acyclic image.

CONCLUSION
We have initiated the study of the fine-grained complexity of conjunctive queries with self-joins. We have seen that queries with low arity can be enumerated with constant delay iff their associated self-join-free query can. We do not know whether this property remains true with linear delay enumeration. There are several ways in which the complexity analysis is more complicated for queries with self-joins. In particular, the complexity may change with the reordering of variables inside an atom, with the addition of unary atoms, or with the addition of binary atoms where only one of their variables appears in the rest of the query (called "spikes" above).
Despite showing several ways in which self-joins can be used in algorithms for queries that are otherwise hard, as well as showing ways to prove the hardness of queries with self-joins, determining the complexity of some queries (see Example 18 and Section 7.4) is left open. Most of our results concern full conjunctive queries and going beyond this would require significant additional work.
A DETAILS OMITTED FROM SECTION 3 P 3. For any conjunctive query , its associated self-join-free query ′ is at least as hard as for the evaluation problem, the testing problem, and the enumeration problem.

P
. Given a database for we compute a database ′ for ′ such that the answers of over can be reconstructed from the answers of ′ over ′ . The database ′ is constructed from by duplicating each relation as many times as its number of occurrences in , one for each new symbol used in ′ as a replacement of . The reduction can be done in linear time, and ( ) = ′ ( ′ ).
Let be a minimal conjunctive query of arity at most one. Then, its solutions can be computed in linear time iff it is acyclic, assuming H . 6 P . If is acyclic, since it is Boolean or unary, it is free-connex, and so it can be answered with constant delay after linear preprocessing time by Theorem 2. This finds all solutions in linear time. Assume now that is cyclic.
To show that is hard, we use a reduction based on the tagging technique. Let ′ be the self-join-free query associated to . As ′ is cyclic, its set of solutions cannot be computed in linear time by Theorem 2, assuming H . Let ′ be a database for ′ and let be the database constructed from ′ using the tagging technique.
If is Boolean, since it is also minimal, every endomorphism is an automorphism, so by Lemma 5, ( ) is true iff ′ ( ′ ) is true too. Otherwise, is unary, and let be the free variable of . From Lemma 5, we get that ′ ( ′ ) = { | , ∈ ( )}. As is unary, the total size of ( ) is linear in the size of and so also in the size of ′ . Hence, if we could compute all the solutions ( ) in linear time, we could compute all the solutions to ′ ( ′ ) at the same time simply by ignoring the solutions in ( ) that are not tagged by .
Missing details for 4 . The enumeration of 4 in linear delay can be done as follows. We first precompute the set of all elements such that ( ) is a fact of the database and has incoming and outgoing edges. Notice that this is an acyclic property and therefore can be computed in linear time. Notice also that any element of is a solution to . For every element of we do the following. First, we consider all edges ( , ). If ( , ) is an edge, then we store in a temporary table . Next, we start a new scan of all edges ( , ). If ( , ) is an edge and ∈ , then we can safely output . For each ∈ , at least one solution is printed, namely , and the delay between checking two elements of is linear.
Let be a minimal binary conjunctive query. If is not acyclic free-connex, then there is no linear preprocessing and constant delay enumeration algorithm for answering , assuming H .

P
. Let be a minimal binary query, and let ′ be its associated self-join-free query. Assume is acyclic but not free-connex. See the paper body for the proof in the cyclic case. We use the following conjecture which is implied by H . BMM conjectures that two × Boolean matrices and cannot be multiplied in time ( 2 ). We show that we cannot compute ( ) in time linear in the input and output sizes, assuming BMM. To see this, we need to recall how the same result was shown in the self-join-free case. Given two × matrices, there is a construction that encodes their multiplication task into any acyclic non-free-connex query using domain values [1]. If the query could be solved in time linear in the input and output sizes, this construction would multiply the matrices in ( 2 ) time. We use the same construction to define a database ′ for ′ . Using the tagging technique to produce from ′ , ( ) contains ′ ( ′ ) and possibly additional answers. But, as the query is binary, the size of ( ) is at most ( 2 ). Hence, if we could compute ( ) in linear time, we would compute ′ ( ′ ) with an overhead of no more than ( 2 ) by ignoring the unwanted solutions, contradicting BMM.
It is possible to test in linear time whether a conjunctive query has a solution iff it has an acyclic core, assuming H .

P
. Let be a conjunctive query with free variables¯ , and let be the Boolean version of the core of . Notice that has a solution iff has a solution. If is acyclic, then we can test whether it has a solution in linear time using the Yannakakis algorithm [11]. Otherwise, is a minimal cyclic Boolean query. By Theorem 7, cannot be tested in linear time assuming H . Hence, one cannot test in linear time whether has a solution.

D DETAILS OMITTED FROM SECTION 6
T 15. Let be a full conjunctive query. If contains a set of variables such that the restriction | is cyclic, and all its endomorphisms are idempotent and have an image containing either all the variables in or none of them, then cannot be enumerated with linear delay (and linear preprocessing), assuming H .

P
. According to Theorem 2, the testing problem for | cannot be solved in linear time since it is cyclic and self-join free, assuming H . In particular, it cannot be enumerated in linear delay. According to the following Lemma 25, this implies the same for . L 25. Let be a full conjunctive query whose endomorphisms are all idempotent, and let be a set of variables of such that every image of contains either all of or none of them. Then, is at least as hard for enumeration as | .

P
L 25. Let ′ be a database for | . We construct a database for as follows. Consider an atom ( ì ) of , and let ′ ( ì ) be its restriction in | . For every fact ′ ( ì ), we construct the tuple ì from ì by inserting ⊥ in all positions of ì that do not contain variables of . We then insert to the fact (¯ ) with = , . Notice that, by construction, the elements of are pairs of the form , such that is either ⊥ or an element of ′ and is a variable of . Moreover, whenever ∈ then is an element of ′ .
Consider now an answer¯ of on . Let be the mapping witnessing the fact that¯ is a solution. As in the tagging technique, we perform a case analysis depending on the endomorphism of induced by . If the image of does not intersect with , then the data part of contains only the elements ⊥ and, as there is only a constant number of such solutions, we can safely ignore them. Otherwise, by our assumption, the image of must contain , and is the identity on . This implies that for any variable ∈ , ( ) is of the form , where is an element of ′ . We claim that the mapping ′ defined by ′ ( ) = whenever ∈ and ( ) = ( , ) witnesses a solution of | on ′ . For all ′ ( ì ) in | , consider ( ì ). Let ì be the variables of occurring in . Since ( ì ) ∈ and is idempotent, we have that ( ì ) is a tuple of ′ tagged by ì . Hence, our construction "filters enough", and the data part gives a solution of | . Notice also that all solutions to | can be obtained this way. Hence, the enumeration of will enumerate all the solutions to | .
Missing details in example 16. The condition of theorem 15 is not met because any set of variables containing a cycle must contain the variable 5 ; if it also contains 7 and 8 then the image 1 , · · · , 6 intersects with in 5 but does not contain 7 . The case where contains 4 and 6 is symmetric.
The query 8 cannot be enumerated with linear delay unless we can find a triangle in a graph in time linear in the number of its edges, a special case of H . To show this, We use the tagging technique as follows. Given an input graph , we construct in linear time the following database . To each edge ( , ) with < , we add to the facts ( , 4 , , 5 ), ( , 5 , , 6 ), ( , 6 , , 4 ), ( , 5 , , 8 ), ( , 8 , , 7 ), ( , 7 , , 5 ). We also add to the facts ( ⊥, 1 , , 4 ) and ( ⊥, 1 , , 7 ). Finally we also add the facts ( ⊥, 1 , ⊥, 2 ), ( ⊥, 2 , ⊥, 3 ), ( ⊥, 3 , ⊥, 1 ) and ( ⊥, 1 , ⊥, 2 , ⊥, 3 ). Consider now a solution to over . Due to the tagging technique, the solution induces an endomorphism of (the tagging map). Let be the corresponding image. If is any image but the core, the solution to induces a triangle of . If is the core, then the data part of the solution only contains ⊥, and there is only one such solution. Hence, if we can enumerate the solutions to the query with linear delay and linear preprocessing, then we can detect in linear time the presence of a triangle in . P . We essentially do as in example 19. Let be the acyclic image witnessing the mirror, and let¯ be the shared variables (that is, variables that appear in and also in atoms of the query that are not in ). Assume the free variables are ordered such that¯ appear first, then the other image variables, and then the remaining variables. We will maintain a table that upon entry¯ returns a list of tuples¯ such that¯ ¯ forms a solution to . As is full and acyclic, it can be enumerated with constant delay after a linear preprocessing time. We perform the preprocessing of and start its enumeration. For every solution¯ ¯ to , we do the following. First, we output the solution¯ ¯ ¯ . Then, for every ′ given by the table for¯ , we output the solutions¯ ¯ ¯ ′ and¯ ¯ ′¯ . Finally, we add¯ to the table with entry¯ . Notice that the delay is constant, and all solutions are printed with no repetition.
Missing details for the query 5 . The query 5 of fig. 6 cannot be enumerated with constant delay assuming the hardness of triangle detection as conjectured in H . Let be a graph. We construct the following database . For every node of , we add the following facts to : ( , 1 , , 2 ), ( , 2 , , 3 ), ( , 4 , , 3 ), ( , 5 , , 4 ), ( , 1 , , 8 ), and ( , 2 ). For every edge ( , ) of with < , we add the following facts to : ( , 5 , , 6 ), ( , 6 , , 7 ), ( , 8 , , 7 ). Consider now a solution in 5 ( ). It induces an endomorphism of 5 as explained in Section 3. We do a case analysis depending on the image of this endomorphism. If is the core, then the data part of the solution involves only one node of . The same holds if involves only the left part of 5 : the variables from 1 to 5 . If involves the top part of 5 , the variables 1 , 2 , 3 , 8 , 7 , then the data part of the solution corresponds to an edge of . The data part of all the remaining images induces a triangle in . Hence, the data part of all the solutions in 5 ( ) contain a triangle of except for a number of solutions linear in the size of . Hence, a constant delay enumeration algorithm for 5 with linear preprocessing would induce a linear test of whether contains a triangle.
The reader may verify that the encoding used to prove the hardness of 5 does not work for 11 as the spikes make bigger images. With this encoding, there would be one solution per path of distance two in , and so the triangles might be detected only after quadratic time, which does not contradict H .
Missing details for the query 12 of example 23. We first enumerate the solutions of the "small" image, depicted in fig. 8. For each such solution ( , , , , ), we do the following.
We compute all possible assignments to 7 while producing some solutions to 12 using the top image as follows. We refer to the subquery induced by 7 , 8 , 14 as the top complement. We enumerate the solutions to the top complement in which 8 maps to . For each such solution ( , , ), we insert the value to the set 7 ( ). Notice that ( , , , , , , , ) is a solution for the top image. We then output the solution to 12 derived from this solution using the mapping of the top image. This is the solution ( , , , , , , , , , , , , , ).
We continue similarly with the left image as follows. We refer to the subquery induced by 4 , 5 , 6 , 11 , 12 as the left complement. We enumerate the solutions to the left complement in which 4 maps to . For each such solution ( , , , ℎ, ), we insert the value to the set 6 ( ), and we insert the value to the set 5 ( , ). Notice that ( , , , , , , , , ℎ, ) is a solution for the left image. We then output the solution to 12 derived from this solution using the mapping of the left image. This is the solution ( , , , , , , , , , , ℎ, , , ).
Next, for each value in 6 ( ) and each value in 7 ( ) we check whether there is an edge ( , ) in our database. If there is, for each value in 5 ( , ), we have found a solution ( , , , , , , , ) to the query induced by the cycle. We enumerate all possible spike assignments to get all solutions to the full query. More specifically, for each 1 with an edge ( , 1 ), for each 2 with an edge ( 2 , ), for each 3 with an edge ( 3 , ), for each 4 with an edge ( , 4 ), for each 5 with an edge ( , 5 ), and for each 6 with an edge ( , 6 ), we print the solution ( , , , , , , , , 1 , 2 , 3 , 4 , 5 , 6 ) to 12 .
The process described in the last paragraph finds every solution to 12 exactly once. The previous two paragraphs find some of the solutions to 12 , where the process described in each paragraph alone does not yield duplicate solutions. Overall, we find all solutions to 12 , and every solution is obtained at most 3 times.
Let us now discuss the time complexity. Each time we enumerate something in our algorithm, it is acyclic and can be done with linear preprocessing and constant delay. The "danger" is that we need to go over all pairs of a value in 6 ( ) and a value in 7 ( ) and check whether they share an edge. In the worst case, if this check always fails, we can get a step of quadratic delay, which is a problem if we want linear preprocessing and constant delay. However, we will show later that the number of such pairs is bounded by the number of solutions we print before these checks, using the top and left images. Overall, we get that, for all , the time from the beginning of the execution until printing the th solution is linear in the input size plus . A general version of the Cheater's Lemma [5,Lemma 7] relies on this to deduce that our algorithm can be tweaked into working with linear preprocessing and constant delay with no duplicates, by withholding some of the solutions before printing them.
Missing details for the query 13 of example 24. Let be an unbalanced tripartite graph. We construct the following database . For each node ∈ , we add to the facts ( , 1 , , 2 ), ( , 2 , , 3 ), ( , 4 , , 3 ), ( , 1 , , 8 ), and ( , 2 ). For each edge ( , ) ∈ × of , we add to the facts ( ( , ), 5 , , 4 ) and ( ( , ), 5 , , 6 ). For each edge ( , ) ∈ × of , we add to the fact ( ( , 6 , , 7 ). Finally for each edge ( , ) ∈ × of , we add to the fact ( , 8 , , 7 ). Consider now a solution in 13 ( ). We perform a case analysis according to the tagging map, as explained in section 3, see Figure 11. The only images that contain 5 or 6 and also 7 come from the endomorphisms which are the identity on the main loop, and so a solution with this tagging detects a triangle of . Images that do not contain 5 , 6 , or 7 result in solutions whose data part is a single node ∈ . For images that contain 5 and possibly also 6 but not 7 , the data part is an edge ( , ) between and . For the image that contains 7 and not 5 , the data part is a triple ( , , ′ ) corresponding to two edges between and . As and are small vertex sets, there cannot be too many solutions of the latter kind. Altogether the number of solutions that do not provide a triangle of is in ( 1+ ). Hence, a constant delay algorithm after linear preprocessing time will identify a triangle in in time ( 1+ ).  Figure 11: Data parts of solutions in Example 24 with a tagging map that: is the identity on the main loop (left), has 5 in its image but not 7 (center), and has 7 in its image but not 5 (right).
Notice that, for the construction of Example 24, it is important that the bottom-left spike points outwards. Otherwise, as in 12 , the left image may produce triplets of the form ( , 1 , 2 ) corresponding to two edges between and , and there may be 1+2 of them, which is too many for solving the VUTD problem in the desired time.