Résumé
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.