When is the evaluation of conjunctive queries tractable?
From MaRDI portal
Publication:5176024
DOI10.1145/380752.380867zbMath1323.68251OpenAlexW2027519504MaRDI QIDQ5176024
Luc Segoufin, Martin Grohe, Thomas Schwentick
Publication date: 27 February 2015
Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01984895/file/CQ-PTIME.pdf
Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Some aspects of the database resilience, Structural tractability of counting of solutions to conjunctive queries, Describing parameterized complexity classes, Unnamed Item, Counting Small Induced Subgraphs Satisfying Monotone Properties, Unnamed Item, Weighted hypertree decompositions and optimal query plans, Towards a dichotomy theorem for the counting constraint satisfaction problem, The complexity of weighted counting for acyclic conjunctive queries, PTAS for Sparse General-valued CSPs, Fixed Structure Complexity, The challenges of unbounded treewidth in parameterised subgraph counting problems, Tree-width and the monadic quantifier hierarchy., Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width., Counting Small Induced Subgraphs with Hereditary Properties, Parameterized Counting and Cayley Graph Expanders, Foundations of graph path query languages. Course notes for the reasoning web summer school 2021, Extended formulation for CSP that is compact for instances of bounded treewidth, Computing hypergraph width measures exactly, Quantified Constraints in Twenty Seventeen, The price of query rewriting in ontology-based data access, On the complexity of existential positive queries, Foundations of semantic web databases, Tractable structures for constraint satisfaction with truth tables, The complexity of counting homomorphisms seen from the other side, Decomposing Quantified Conjunctive (or Disjunctive) Formulas, A parametric analysis of the state-explosion problem in model checking, Unnamed Item, Unnamed Item, Unnamed Item, Characterizing tractability of simple well-designed pattern trees with projection, Parameterised complexity of model checking and satisfiability in propositional dependence logic, An Experimental Study of the Treewidth of Real-World Graph Data, Counting Answers to Existential Questions, Counting edge-injective homomorphisms and matchings on restricted graph classes, A Logical Approach to Constraint Satisfaction, Uniform Constraint Satisfaction Problems and Database Theory, Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2, Structural tractability of enumerating CSP solutions
Cites Work
