Conjunctive-query containment and constraint satisfaction
From MaRDI portal
Recommendations
Cites work
- 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
- 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?)
- 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 complexity of constraint satisfaction revisited
- The complexity of satisfiability problems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The decision problem for some classes of sentences without quantifiers
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- Tree clustering for constraint networks
Cited in
(only showing first 100 items - show all)- Some results on the containment and minimization of (in)equality queries
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Conjunctive query containment revisited
- A comparison of structural CSP decomposition methods
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- Conjunctive query containment over trees using schema information
- Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
- Dichotomies for classes of homomorphism problems involving unary functions
- The complexity of minimal satisfiability problems
- Generalization of ZYT-linearizability for bilinear datalog programs
- Testing bag-containment of conjunctive queries
- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- Efficiently enumerating minimal triangulations
- How hard is completeness reasoning for conjunctive queries?
- Fast and parallel decomposition of constraint satisfaction problems
- Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
- Dismantlability, connectedness, and mixing in relational structures
- Algorithms for propositional model counting
- Structural tractability of enumerating CSP solutions
- From tree-decompositions to clique-width terms
- On digraph coloring problems and treewidth duality
- Majority constraints have bounded pathwidth duality
- Counting solutions to CSP using generating polynomials
- A combinatorial characterization of resolution width
- Complexity of clausal constraints over chains
- Structural tractability of counting of solutions to conjunctive queries
- Backdoors to satisfaction
- Conjunctive visibly-pushdown path queries
- Many Facets of Dualities
- An upper bound for resolution size: characterization of tractable SAT instances
- On the complexity of the model checking problem
- Semantic acyclicity on graph databases
- A more general theory of static approximations for conjunctive queries
- Extension complexity, MSO logic, and treewidth
- On the containment problem for queries in conjunctive form with negation
- Algorithms for Propositional Model Counting
- A case for dynamic view management
- First-Order Model Checking Problems Parameterized by the Model
- On preservation under homomorphisms and unions of conjunctive queries
- Ontologies and Databases: The DL-Lite Approach
- Tree-Width for First Order Formulae
- Hyperconsistency width for constraint satisfaction: Algorithms and complexity results
- Tractable counting of the answers to conjunctive queries
- scientific article; zbMATH DE number 1253959 (Why is no real title available?)
- scientific article; zbMATH DE number 2080027 (Why is no real title available?)
- Colouring, constraint satisfaction, and complexity
- The parameterized space complexity of model-checking bounded variable first-order logic
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
- The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
- Sum-of-Products with Default Values: Algorithms and Complexity Results
- Dismantlability, Connectedness, and Mixing in Relational Structures
- scientific article; zbMATH DE number 7561704 (Why is no real title available?)
- The quantum monad on relational structures
- Schema mappings: a case of logical dynamics in database theory
- The power of linear programming for general-valued CSPs
- Parametrised complexity of satisfiability in temporal logic
- The complexity of general-valued CSPs
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- Database Theory - ICDT 2005
- Conjunctive query containment over trees
- On the finite controllability of conjunctive query answering in databases under open-world assumption
- Block-Sorted Quantified Conjunctive Queries
- Tractable structures for constraint satisfaction with truth tables
- Bounded Tree-Width and CSP-Related Problems
- On the complexity of existential positive queries
- TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
- Dualities for Constraint Satisfaction Problems
- A Logical Approach to Constraint Satisfaction
- Uniform Constraint Satisfaction Problems and Database Theory
- Decomposing Quantified Conjunctive (or Disjunctive) Formulas
- scientific article; zbMATH DE number 6729737 (Why is no real title available?)
- The product homomorphism problem and applications
- On the relationship between consistent query answering and constraint satisfaction problems
- The complexity of conservative valued CSPs
- On Horn Conjunctive Queries
- Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments
- On the descriptive complexity of temporal constraint satisfaction problems
- Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
- Conjunctive query containment with respect to views and constraints
- Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity
- Logical algorithmics: from theory to practice (invited talk)
- Logical algorithmics: from relational queries to Boolean reasoning (invited talk)
- Solving promise equations over monoids and groups
- Optimally rewriting formulas and database queries: a confluence of term rewriting, structural decomposition, and complexity
- On the expression complexity of equivalence and isomorphism of primitive positive formulas
- Hypertree decompositions and tractable queries
- Local consistency as a reduction between constraint satisfaction problems
- Solving promise equations over monoids and groups
- Recognizing frozen variables in constraint satisfaction problems
- The complexity of counting homomorphisms seen from the other side
- On the complexity of entailment in existential conjunctive first-order logic with atomic negation
- TreeTracker Join: simple, optimal, fast
- Algorithms and complexity of difference logic
- The theory of concatenation over finite models
- Smooth approximations and relational width collapses
- Optimally rewriting formulas and database queries: a confluence of term rewriting, structural decomposition, and complexity
- Satisfiability of commutative vs. non-commutative CSPs
- A more general theory of static approximations for conjunctive queries
- The complexity of constraint satisfaction games and QCSP
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)
