Constant delay enumeration for conjunctive queries
Authors:
Open Access
- 24 February 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGLOG News
- Vol. 7 (1) , 4-33
Abstract
This paper is the tutorial we wish we had had available when starting our own research on constant delay enumeration for conjunctive queries. It provides precise statements and detailed, self-contained proofs of the fundamental results in this area.Keywords
This publication has 51 references indexed in Scilit:
- Size Bounds and Query Plans for Relational JoinsSIAM Journal on Computing, 2013
- First-order query evaluation on structures of bounded degreeLogical Methods in Computer Science, 2011
- Approximating fractional hypertree widthACM Transactions on Algorithms, 2010
- First-order queries on structures of bounded degree are computable with constant delayACM Transactions on Computational Logic, 2007
- Strong computational lower bounds via parameterized complexityJournal of Computer and System Sciences, 2006
- Fast sparse matrix multiplicationACM Transactions on Algorithms, 2005
- On the Complexity of Matrix ProductSIAM Journal on Computing, 2003
- Hypertree Decompositions and Tractable QueriesJournal of Computer and System Sciences, 2002
- On the Desirability of Acyclic Database SchemesJournal of the ACM, 1983
- Power of Natural SemijoinsSIAM Journal on Computing, 1981