The complexity of acyclic conjunctive queries

DOI10.1145/382780.382783zbMath1323.68250OpenAlexW2004485491WikidataQ59259727 ScholiaQ59259727MaRDI QIDQ3196620

Nicola Leone, Georg Gottlob, Francesco Scarcello

Publication date: 30 October 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/382780.382783

zbMATH Keywords

database theoryparallel algorithmconstraintCSPconstraint satisfaction problemLOGCFLconjunctive querybounded treewidthacyclic hypergraphquery containmentsubsumptionhingedegree of cyclicitytree queryjoin tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (32)

The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ The arithmetic complexity of tensor contraction ⋮ On the complexity of constrained Nash equilibria in graphical games ⋮ Semantic Acyclicity on Graph Databases ⋮ Conjunctive query evaluation by search-tree revisited ⋮ Weighted hypertree decompositions and optimal query plans ⋮ Tractable counting of the answers to conjunctive queries ⋮ The dynamic complexity of acyclic hypergraph homomorphisms ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ Equivalence between hypergraph convexities ⋮ Generic local computation ⋮ Cops and robber on oriented graphs with respect to push operation ⋮ Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width. ⋮ Complexity results for answer set programming with bounded predicate arities and implications ⋮ Rewriting with Acyclic Queries: Mind Your Head ⋮ Computing thejth solution of a first-order query ⋮ Open-world probabilistic databases: semantics, algorithms, complexity ⋮ Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms ⋮ Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems ⋮ Hypertree decompositions and tractable queries ⋮ Approximability of clausal constraints ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ Unnamed Item ⋮ On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay ⋮ Computing LOGCFL certificates ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ A Logical Approach to Constraint Satisfaction ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ Prediction-hardness of acyclic conjunctive queries ⋮ Large hypertree width for sparse random hypergraphs ⋮ Fixed-parameter complexity in AI and nonmonotonic reasoning

This page was built for publication: The complexity of acyclic conjunctive queries