Name
Abstract | ||
|---|---|---|
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.
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.1145/3294052.3319700 | Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems |
Keywords | Field | DocType |
complexity, constant delay, enumeration, unions of conjunctive queries | Discrete mathematics,Joins,Conjunctive query,Computer science,Tuple,Enumeration,Theoretical computer science,Preprocessor | Journal |
Volume | Issue | ISSN |
abs/1812.03831 | 2 | 0362-5915 |
ISBN | Citations | PageRank |
978-1-4503-6227-6 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nofar Carmeli | 1 | 6 | 4.84 |
| Markus Kröll | 2 | 4 | 1.86 |