Conjunctive-query containment and constraint satisfaction

DOI10.1006/jcss.2000.1713zbMath0963.68059OpenAlexW4254380579WikidataQ56168970 ScholiaQ56168970MaRDI QIDQ1591157

Publication date: 19 December 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2000.1713

zbMATH Keywords

conjunctive-query containment

Mathematics Subject Classification ID

Database theory (68P15)

Related Items

Structural tractability of counting of solutions to conjunctive queries, 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, Dichotomies for classes of homomorphism problems involving unary functions, The complexity of minimal satisfiability problems, Generalization of ZYT-linearizability for bilinear datalog programs, The complexity of constraint satisfaction games and QCSP, On the Complexity of the Model Checking Problem, Constraint satisfaction with bounded treewidth revisited, Backdoors to Satisfaction, Semantic Acyclicity on Graph Databases, Sum-of-Products with Default Values: Algorithms and Complexity Results, Conjunctive query evaluation by search-tree revisited, Unnamed Item, Weighted hypertree decompositions and optimal query plans, Towards a dichotomy theorem for the counting constraint satisfaction problem, Maximum $H$-colourable subdigraphs and constraint optimization with arbitrary weights, A More General Theory of Static Approximations for Conjunctive Queries, Tractable counting of the answers to conjunctive queries, From tree-decompositions to clique-width terms, Conjunctive Visibly-Pushdown Path Queries, The complexity of approximating bounded-degree Boolean $\#$CSP, Algorithms for Propositional Model Counting, Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, Unnamed Item, A new line of attack on the dichotomy conjecture, A case for dynamic view management, First-Order Model Checking Problems Parameterized by the Model, Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width., Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments, On digraph coloring problems and treewidth duality, Majority constraints have bounded pathwidth duality, Conjunctive query containment over trees using schema information, Structural parameters for scheduling with assignment restrictions, Many Facets of Dualities, Generic expression hardness results for primitive positive formula comparison, Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems, Unnamed Item, An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances, Colouring, constraint satisfaction, and complexity, Counting solutions to CSP using generating polynomials, Dismantlability, connectedness, and mixing in relational structures, Bounded Tree-Width and CSP-Related Problems, A unified theory of structural tractability for constraint satisfaction problems, Computational complexity of auditing finite attributes in statistical databases, Efficiently enumerating minimal triangulations, Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms, On the complexity of existential positive queries, A combinatorial characterization of resolution width, On the expression complexity of equivalence and isomorphism of primitive positive formulas, Complexity of clausal constraints over chains, Conjunctive query containment over trees, Tractable structures for constraint satisfaction with truth tables, Hypertree decompositions and tractable queries, On the power of structural decompositions of graph-based representations of constraint problems, Recognizing frozen variables in constraint satisfaction problems, The complexity of counting homomorphisms seen from the other side, Decomposing Quantified Conjunctive (or Disjunctive) Formulas, Algorithms for propositional model counting, On the complexity of entailment in existential conjunctive first-order logic with atomic negation, Unnamed Item, Unnamed Item, Dismantlability, Connectedness, and Mixing in Relational Structures, Ontologies and Databases: The DL-Lite Approach, Tree-Width for First Order Formulae, TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS, HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results, A more general theory of static approximations for conjunctive queries, Fast and parallel decomposition of constraint satisfaction problems, Dualities for Constraint Satisfaction Problems, A Logical Approach to Constraint Satisfaction, Uniform Constraint Satisfaction Problems and Database Theory, Schema Mappings: A Case of Logical Dynamics in Database Theory, The Power of Linear Programming for General-Valued CSPs, A comparison of structural CSP decomposition methods, Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2, Unnamed Item, Structural tractability of enumerating CSP solutions, Fixed-parameter complexity in AI and nonmonotonic reasoning, Myhill-Nerode Methods for Hypergraphs, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side

Cites Work