[Back]

M. Kröll, N. Carmeli:
"On the Enumeration Complexity of Unions of Conjunctive Queries";
Talk: SIGMOD/PODS 2019 - 38th Symposium on Principles of Database Systems 2019, Amsterdam, Niederlande; 2019-06-30 - 2019-07-05; in: "Proceedings of the 38th {ACM} {SIGMOD-SIGACT-SIGAI} Symposium on Principles of Database Systems, {PODS} 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019", ACM, (2019), ISBN: 978-1-4503-6227-6; 134 - 148.

We study the enumeration complexity of Unions of Conjunctive Queries (UCQs). We aim to identify the UCQs that are tractable in the sense that the answer tuples can be enumerated with a linear preprocessing phase and a constant delay between every successive tuples. It has been established that, in the absence of self joins and under conventional complexity assumptions, the CQs that admit such an evaluation are precisely the free-connex ones. A union of tractable CQs is always tractable. We generalize the notion of free-connexity from CQs to UCQs, thus showing that some unions containing intractable CQs are, in fact, tractable. Interestingly, some unions consisting of only intractable CQs are tractable too. The question of a finding a full characterization of the tractability of UCQs remains open. Nevertheless, we prove that for several classes of queries, free-connexity fully captures the tractable UCQs.

http://dx.doi.org/10.1145/3294052.3319700

Project Head Reinhard Pichler:
HyperTrac