2014 · 43 citations · 45 references
ComputingComputer ScienceComputer SystemsAlgorithmsDatabasesTheory Of ComputationAlgorithm AnalysisAlgorithmic ComplexityComplexity TheoryComputational ComplexityQuery ProcessingTime ComplexityBounded Search TreesComplexityComplexity AnalysisJoin AlgorithmsQuery ComplexitySearch Complexity AnalysisWorst-case BoundsWorst-case Complexity
We describe a new algorithm, Minesweeper, that is able to satisfy stronger runtime guarantees than previous join algorithms (colloquially ``beyond worst-case'' guarantees) for data in indexed search trees. Our first contribution is developing a framework to measure this stronger notion of complexity, which we call "certificate complexity," that extends notions of Barbay et al. and Demaine et al.; a certificate is a set of propositional formulae that certifies that the output is correct. This notion captures a natural class of join algorithms. In addition, the certificate allows us to define a strictly stronger notion of runtime complexity than traditional worst-case guarantees. Our second contribution is to develop a dichotomy theorem for the certificate-based notion of complexity. Roughly, we show that Minesweeper evaluates $\beta$-acyclic queries in time linear in the certificate plus the output size, while for any $\beta$-cyclic query, there is some instance that takes superlinear time in the certificate (and for which the output is no larger than the certificate size). We also extend our certificate-complexity analysis to queries with bounded treewidth and the triangle query. We present empirical results that certificates can be much smaller than the input size, which suggests that ideas in minesweeper might lead to faster algorithms in practice.
45
Optimal implementation of conjunctive queries in relational data bases
Ashok K. Chandra, Philip M. Merlin · 1977 · 1.2K citations · Full text
The complexity of relational query languages (Extended Abstract)
Moshe Y. Vardi · 1982 · 1.2K citations
Computing, Computer Science, Algebra +16
Optimal aggregation algorithms for middleware
Ronald Fagin, Amnon Lotem, Moni Naor · Journal of Computer and System Sciences · 2003 · 941 citations
On the Desirability of Acyclic Database Schemes
Catriel Beeri, Ronald Fagin, David Maier et al. · Journal of the ACM · 1983 · 817 citations · Full text