The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
From MaRDI portal
Publication:5283239
DOI10.1137/16M1090272zbMath1371.68061OpenAlexW2731670349MaRDI QIDQ5283239
Francesco Scarcello, Gianluigi Greco
Publication date: 21 July 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1090272
Related Items
Solving projected model counting by utilizing treewidth and its limits, Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms, Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value, A more general theory of static approximations for conjunctive queries
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- Enumerating homomorphisms
- On the finite controllability of conjunctive query answering in databases under open-world assumption
- Hybrid tractability of valued constraint problems
- Hypertree decompositions and tractable queries
- Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
- Graph minors. III. Planar tree-width
- Weighted hypertree decompositions and optimal query plans
- A unified theory of structural tractability for constraint satisfaction problems
- Testing containment of conjunctive queries under functional and inclusion dependencies
- The tree projection theorem and relational query processing
- Tree clustering for constraint networks
- Tree-size bounded alternation
- Graph searching and a min-max theorem for tree-width
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- A comparison of structural CSP decomposition methods
- Conjunctive-query containment and constraint satisfaction
- Structural tractability of enumerating CSP solutions
- Hypertree width and related hypergraph invariants
- Approximating fractional hypertree width
- On the Desirability of Acyclic Database Schemes
- Degrees of acyclicity for hypergraphs and relational database schemes
- Syntactic Characterization of Tree Database Schemas
- Marshals, monotone marshals, and hypertree-width
- Semantic Acyclicity on Graph Databases
- The complexity of acyclic conjunctive queries
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Generalized hypertree decompositions: NP-hardness and tractable variants
- Query evaluation via tree-decompositions
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- Connected Treewidth and Connected Graph Searching
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Efficient core computation in data exchange
- Constraint solving via fractional edge covers
- Undirected connectivity in log-space
- Tree-Related Widths of Graphs and Hypergraphs
- A Proof Procedure for Data Dependencies
- Power of Natural Semijoins
- Alternation
- Acyclic Hypergraph Projections
- Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
- On the Power of k-Consistency
- Uniform Constraint Satisfaction Problems and Database Theory
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
