The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
From MaRDI portal
Publication:5283239
DOI10.1137/16M1090272zbMATH Open1371.68061OpenAlexW2731670349MaRDI QIDQ5283239FDOQ5283239
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
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph searching and a min-max theorem for tree-width
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Undirected connectivity in log-space
- Testing containment of conjunctive queries under functional and inclusion dependencies
- 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
- 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
- Efficient core computation in data exchange
- Constraint solving via fractional edge covers
- Alternation
- 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
- A unified theory of structural tractability for constraint satisfaction problems
- On the Desirability of Acyclic Database Schemes
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A Proof Procedure for Data Dependencies
- The complexity of acyclic conjunctive queries
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- Graph minors. III. Planar tree-width
- Tree clustering for constraint networks
- Power of Natural Semijoins
- On the Power of k-Consistency
- Degrees of acyclicity for hypergraphs and relational database schemes
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Syntactic Characterization of Tree Database Schemas
- Marshals, monotone marshals, and hypertree-width
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- Acyclic Hypergraph Projections
- Uniform Constraint Satisfaction Problems and Database Theory
- Tree-Related Widths of Graphs and Hypergraphs
- Tree-size bounded alternation
- Semantic Acyclicity on Graph Databases
- The tree projection theorem and relational query processing
- Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
- Weighted hypertree decompositions and optimal query plans
Cited In (5)
- A Theory of Local Set Queries
- Solving projected model counting by utilizing treewidth and its limits
- Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
- A more general theory of static approximations for conjunctive queries
- Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
Recommendations
- Local consistency and SAT-solvers 👍 👎
- Constraint Satisfaction Problems Solvable by Local Consistency Methods 👍 👎
- Local Consistency in Weighted CSPs and Inference in Max-SAT 👍 👎
- Graph-Theoretic Concepts in Computer Science 👍 👎
- On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems 👍 👎
- Locally consistent constraint satisfaction problems 👍 👎
- Automata, Languages and Programming 👍 👎
This page was built for publication: The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283239)
