Conjunctive-query containment and constraint satisfaction
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 3819693 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1262783 (Why is no real title available?)
- scientific article; zbMATH DE number 1142299 (Why is no real title available?)
- scientific article; zbMATH DE number 1151381 (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
- Conjunctive query containment revisited
- Constraint satisfaction from a deductive viewpoint
- Decomposing a relation into a tree of binary relations
- Decomposing constraint satisfaction problems using database techniques
- Horn clause queries and generalizations
- Infinitary logics and 0-1 laws
- Information integration using logical views
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Maximal Sublattices of Finite Distributive Lattices. II
- Monotone monadic SNP and constraint satisfaction
- Networks of constraints: Fundamental properties and applications to picture processing
- Node-Deletion Problems on Bipartite Graphs
- On the algebraic structure of combinatorial problems
- On the complexity of H-coloring
- On the expressive power of Datalog: tools and a case study.
- Structure identification in relational data
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- The complexity of constraint satisfaction revisited
- The complexity of satisfiability problems
- The decision problem for some classes of sentences without quantifiers
- Tree clustering for constraint networks
Cited in
(95)- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- Parametrised complexity of satisfiability in temporal logic
- Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
- scientific article; zbMATH DE number 1253959 (Why is no real title available?)
- Decomposing Quantified Conjunctive (or Disjunctive) Formulas
- The complexity of minimal satisfiability problems
- Generalization of ZYT-linearizability for bilinear datalog programs
- Many Facets of Dualities
- Dismantlability, Connectedness, and Mixing in Relational Structures
- A Logical Approach to Constraint Satisfaction
- On the expression complexity of equivalence and isomorphism of primitive positive formulas
- Dismantlability, connectedness, and mixing in relational structures
- On the descriptive complexity of temporal constraint satisfaction problems
- Structural tractability of counting of solutions to conjunctive queries
- Tractable counting of the answers to conjunctive queries
- Conjunctive query evaluation by search-tree revisited
- Tree-Width for First Order Formulae
- Colouring, constraint satisfaction, and complexity
- Recognizing frozen variables in constraint satisfaction problems
- Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments
- Conjunctive query containment over trees
- On the finite controllability of conjunctive query answering in databases under open-world assumption
- The power of linear programming for general-valued CSPs
- Tractable structures for constraint satisfaction with truth tables
- On preservation under homomorphisms and unions of conjunctive queries
- The quantum monad on relational structures
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
- Dualities for Constraint Satisfaction Problems
- Uniform Constraint Satisfaction Problems and Database Theory
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Hypertree decompositions and tractable queries
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- The complexity of counting homomorphisms seen from the other side
- The complexity of conservative valued CSPs
- On the complexity of entailment in existential conjunctive first-order logic with atomic negation
- Constraint satisfaction with bounded treewidth revisited
- scientific article; zbMATH DE number 6729737 (Why is no real title available?)
- Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
- A unified theory of structural tractability for constraint satisfaction problems
- How hard is completeness reasoning for conjunctive queries?
- On the complexity of the model checking problem
- The parameterized space complexity of model-checking bounded variable first-order logic
- An upper bound for resolution size: characterization of tractable SAT instances
- Hyperconsistency width for constraint satisfaction: Algorithms and complexity results
- The product homomorphism problem and applications
- Backdoors to satisfaction
- A comparison of structural CSP decomposition methods
- Some results on the containment and minimization of (in)equality queries
- scientific article; zbMATH DE number 2080027 (Why is no real title available?)
- Conjunctive visibly-pushdown path queries
- Weighted hypertree decompositions and optimal query plans
- On the relationship between consistent query answering and constraint satisfaction problems
- On the containment problem for queries in conjunctive form with negation
- Complexity of clausal constraints over chains
- Majority constraints have bounded pathwidth duality
- Database Theory - ICDT 2005
- Testing bag-containment of conjunctive queries
- The complexity of general-valued CSPs
- Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
- Algorithms for propositional model counting
- Block-Sorted Quantified Conjunctive Queries
- A case for dynamic view management
- A combinatorial characterization of resolution width
- Conjunctive query containment over trees using schema information
- The complexity of constraint satisfaction games and QCSP
- A new line of attack on the dichotomy conjecture
- Combined-semantics equivalence of conjunctive queries: decidability and tractability results
- Schema mappings: a case of logical dynamics in database theory
- From tree-decompositions to clique-width terms
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- Structural tractability of enumerating CSP solutions
- Semantic acyclicity on graph databases
- On the complexity of existential positive queries
- Counting solutions to CSP using generating polynomials
- Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
- Ontologies and Databases: The DL-Lite Approach
- Efficiently enumerating minimal triangulations
- A more general theory of static approximations for conjunctive queries
- Bounded Tree-Width and CSP-Related Problems
- A more general theory of static approximations for conjunctive queries
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- scientific article; zbMATH DE number 7561704 (Why is no real title available?)
- Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
- Algorithms for Propositional Model Counting
- Dichotomies for classes of homomorphism problems involving unary functions
- First-Order Model Checking Problems Parameterized by the Model
- Computational complexity of auditing finite attributes in statistical databases
- Extension complexity, MSO logic, and treewidth
- On Horn Conjunctive Queries
- The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
- On the power of structural decompositions of graph-based representations of constraint problems
- Sum-of-Products with Default Values: Algorithms and Complexity Results
- On digraph coloring problems and treewidth duality
- Fast and parallel decomposition of constraint satisfaction problems
This page was built for publication: Conjunctive-query containment and constraint satisfaction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1591157)
