On the complexity of database queries
From MaRDI portal
Publication:1307689
DOI10.1006/jcss.1999.1626zbMath0939.68024OpenAlexW2048685245MaRDI QIDQ1307689
Mihalis Yannakakis, Christos H. Papadimitriou
Publication date: 9 November 1999
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1999.1626
Related Items (30)
An algorithm for handling many relational calculus queries efficiently. ⋮ On finding short resolution refutations and small unsatisfiable subsets ⋮ Unnamed Item ⋮ Constraint satisfaction with bounded treewidth revisited ⋮ Strong computational lower bounds via parameterized complexity ⋮ The complexity of tree automata and XPath on grammar-compressed trees ⋮ Unnamed Item ⋮ Conjunctive query evaluation by search-tree revisited ⋮ A More General Theory of Static Approximations for Conjunctive Queries ⋮ Computing thejth solution of a first-order query ⋮ Generic expression hardness results for primitive positive formula comparison ⋮ Some characterizations of \(\gamma \) and \(\beta \)-acyclicity of hypergraphs ⋮ On the expression complexity of equivalence and isomorphism of primitive positive formulas ⋮ Machine-based methods in parameterized complexity theory ⋮ A parametric analysis of the state-explosion problem in model checking ⋮ On the computational hardness based on linear fpt-reductions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The hardness of resilience for nested aggregation query ⋮ Characterizing tractability of simple well-designed pattern trees with projection ⋮ Unnamed Item ⋮ Semantic Acyclicity for Conjunctive Queries: Approximations and Constraints ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ Parameterized Complexity ⋮ Enumeration complexity of conjunctive queries with functional dependencies ⋮ A more general theory of static approximations for conjunctive queries ⋮ Transducing Markov sequences ⋮ Unnamed Item ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On limited nondeterminism and the complexity of the V-C dimension
- Graph minors. XIII: The disjoint paths problem
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- On conjunctive queries containing inequalities
- Nondeterminism within $P^ * $
- Color-coding
- Fixed-Parameter Tractability and Completeness I: Basic Results
This page was built for publication: On the complexity of database queries
