Hypertree decompositions and tractable queries

DOI10.1006/jcss.2001.1809zbMath1052.68025OpenAlexW2033325972WikidataQ59259717 ScholiaQ59259717MaRDI QIDQ696962

Georg Gottlob, Nicola Leone, Francesco Scarcello

Publication date: 12 September 2002

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

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

zbMATH Keywords

decision problems on conjunctive queries

Mathematics Subject Classification ID

Database theory (68P15)

Related Items (65)

Structural tractability of counting of solutions to conjunctive queries ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Structural decompositions for problems with global constraints ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Constraint satisfaction with bounded treewidth revisited ⋮ Semantic Acyclicity on Graph Databases ⋮ Domain permutation reduction for constraint satisfaction problems ⋮ On minimal constraint networks ⋮ Answering conjunctive queries with inequalities ⋮ Regularizing conjunctive features for classification ⋮ Weighted hypertree decompositions and optimal query plans ⋮ Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights ⋮ Satisfiability of acyclic and almost acyclic CNF formulas ⋮ A More General Theory of Static Approximations for Conjunctive Queries ⋮ Tractable counting of the answers to conjunctive queries ⋮ Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs ⋮ Tree projections and structural decomposition methods: minimality and game-theoretic characterization ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ Algorithms for Propositional Model Counting ⋮ HyperBench ⋮ Computing optimal hypertree decompositions with SAT ⋮ Generic local computation ⋮ Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width. ⋮ Coalition structure generation: a survey ⋮ Linear Programs with Conjunctive Database Queries ⋮ CSP beyond tractable constraint languages ⋮ Computing a partition function of a generalized pattern-based energy over a semiring ⋮ Computing hypergraph width measures exactly ⋮ Dynamic Management of Heuristics for Solving Structured CSPs ⋮ Constraint satisfaction with succinctly specified relations ⋮ Some characterizations of \(\gamma \) and \(\beta \)-acyclicity of hypergraphs ⋮ On Sparse Discretization for Graphical Games ⋮ Solving Graph Problems via Potential Maximal Cliques ⋮ A unified theory of structural tractability for constraint satisfaction problems ⋮ Computational complexity of auditing finite attributes in statistical databases ⋮ Hypertree width and related hypergraph invariants ⋮ Efficiently enumerating minimal triangulations ⋮ Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms ⋮ D-FLAT: Declarative problem solving using tree decompositions and answer-set programming ⋮ Tractable structures for constraint satisfaction with truth tables ⋮ On the power of structural decompositions of graph-based representations of constraint problems ⋮ Connectivity and equilibrium in random games ⋮ Recognizing frozen variables in constraint satisfaction problems ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ Algorithms for propositional model counting ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ Backdoors into heterogeneous classes of SAT and CSP ⋮ Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value ⋮ Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints ⋮ Tree-Width for First Order Formulae ⋮ Evaluating Datalog via tree automata and cycluits ⋮ HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results ⋮ Tree Projections: Game Characterization and Computational Aspects ⋮ A more general theory of static approximations for conjunctive queries ⋮ Fast and parallel decomposition of 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 ⋮ A comparison of structural CSP decomposition methods ⋮ Structural tractability of enumerating CSP solutions ⋮ Large hypertree width for sparse random hypergraphs ⋮ Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Constraint satisfaction from a deductive viewpoint
• Tree clustering for constraint networks
• Tree-size bounded alternation
• Decomposing constraint satisfaction problems using database techniques
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• A comparison of structural CSP decomposition methods
• Conjunctive-query containment and constraint satisfaction
• On the Desirability of Acyclic Database Schemes
• Degrees of acyclicity for hypergraphs and relational database schemes
• The complexity of acyclic conjunctive queries
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• On Determining Tree Query Membership Of A Distributed Query
• Graph minors. II. Algorithmic aspects of tree-width
• A complexity theory based on Boolean algebra
• A sufficient condition for backtrack-bounded search
• Power of Natural Semijoins
• Alternation
• A simplied universal relation assumption and its properties
• Tree queries
• The well-founded semantics for general logic programs
• Closure properties of constraints
• The Hardest Context-Free Language
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Computing LOGCFL certificates

This page was built for publication: Hypertree decompositions and tractable queries