The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
From MaRDI portal
Publication:5283239
Recommendations
- Automata, Languages and Programming
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Local consistency and SAT-solvers
- Locally consistent constraint satisfaction problems
- Graph-Theoretic Concepts in Computer Science
- Local Consistency in Weighted CSPs and Inference in Max-SAT
- On the relationship between consistent query answering and constraint satisfaction problems
Cites work
- scientific article; zbMATH DE number 1142309 (Why is no real title available?)
- scientific article; zbMATH DE number 839556 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A Proof Procedure for Data Dependencies
- A comparison of structural CSP decomposition methods
- A unified theory of structural tractability for constraint satisfaction problems
- Acyclic Hypergraph Projections
- Alternation
- Approximating fractional hypertree width
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- Conjunctive-query containment and constraint satisfaction
- Connected Treewidth and Connected Graph Searching
- Degrees of acyclicity for hypergraphs and relational database schemes
- Efficient core computation in data exchange
- Enumerating homomorphisms
- Generalized hypertree decompositions: NP-hardness and tractable variants
- Graph minors. III. Planar tree-width
- Graph searching and a min-max theorem for tree-width
- Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
- Hybrid tractability of valued constraint problems
- Hypertree decompositions and tractable queries
- Hypertree width and related hypergraph invariants
- Marshals, monotone marshals, and hypertree-width
- On the Desirability of Acyclic Database Schemes
- On the Power of k-Consistency
- On the finite controllability of conjunctive query answering in databases under open-world assumption
- Power of Natural Semijoins
- Query evaluation via tree-decompositions
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Semantic acyclicity on graph databases
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Structural tractability of enumerating CSP solutions
- Syntactic Characterization of Tree Database Schemas
- Testing containment of conjunctive queries under functional and inclusion dependencies
- The complexity of acyclic conjunctive queries
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The tree projection theorem and relational query processing
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
- Tree clustering for constraint networks
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- Tree-Related Widths of Graphs and Hypergraphs
- Tree-size bounded alternation
- Undirected connectivity in log-space
- Uniform Constraint Satisfaction Problems and Database Theory
- Weighted hypertree decompositions and optimal query plans
- Width functions for hypertree decompositions
Cited in
(5)- 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
- A Theory of Local Set Queries
- Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
- Solving projected model counting by utilizing treewidth and its limits
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)
