Hypertree decompositions and tractable queries
From MaRDI portal
Publication:696962
DOI10.1006/JCSS.2001.1809zbMATH Open1052.68025OpenAlexW2033325972WikidataQ59259717 ScholiaQ59259717MaRDI QIDQ696962
Georg Gottlob, N. 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
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The well-founded semantics for general logic programs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Closure properties of constraints
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Decomposing constraint satisfaction problems using database techniques
- A comparison of structural CSP decomposition methods
- Conjunctive-query containment and constraint satisfaction
- Graph minors. II. Algorithmic aspects of tree-width
- Alternation
- On the Desirability of Acyclic Database Schemes
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A simplied universal relation assumption and its properties
- The complexity of acyclic conjunctive queries
- Tree clustering for constraint networks
- A sufficient condition for backtrack-bounded search
- Power of Natural Semijoins
- Degrees of acyclicity for hypergraphs and relational database schemes
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- The Hardest Context-Free Language
- Constraint satisfaction from a deductive viewpoint
- Tree-size bounded alternation
- A complexity theory based on Boolean algebra
- On Determining Tree Query Membership Of A Distributed Query
- Tree queries
- Computing LOGCFL certificates
Cited In (68)
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- Solving Graph Problems via Potential Maximal Cliques
- A Logical Approach to Constraint Satisfaction
- Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT
- Structural tractability of counting of solutions to conjunctive queries
- Structural decompositions for problems with global constraints
- Tractability in constraint satisfaction problems: a survey
- Satisfiability of acyclic and almost acyclic CNF formulas
- Tractable counting of the answers to conjunctive queries
- The complexity of weighted counting for acyclic conjunctive queries
- Recognizing frozen variables in constraint satisfaction problems
- Uniform Constraint Satisfaction Problems and Database Theory
- Dynamic Management of Heuristics for Solving Structured CSPs
- Tractable structures for constraint satisfaction with truth tables
- Connectivity and equilibrium in random games
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- A More General Theory of Static Approximations for Conjunctive Queries
- Large hypertree width for sparse random hypergraphs
- Backdoors into heterogeneous classes of SAT and CSP
- Constraint satisfaction with bounded treewidth revisited
- Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
- A unified theory of structural tractability for constraint satisfaction problems
- Tree Projections: Game Characterization and Computational Aspects
- Computing hypergraph width measures exactly
- Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
- A comparison of structural CSP decomposition methods
- HyperBench
- Weighted hypertree decompositions and optimal query plans
- On Sparse Discretization for Graphical Games
- Some characterizations of \(\gamma \) and \(\beta \)-acyclicity of hypergraphs
- Constraint satisfaction with succinctly specified relations
- Algorithms for propositional model counting
- Generic local computation
- Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs
- Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- On minimal constraint networks
- Structural tractability of enumerating CSP solutions
- Domain permutation reduction for constraint satisfaction problems
- Coalition structure generation: a survey
- Hypertree width and related hypergraph invariants
- D-FLAT: Declarative problem solving using tree decompositions and answer-set programming
- Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
- Efficiently enumerating minimal triangulations
- A more general theory of static approximations for conjunctive queries
- Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
- Answering conjunctive queries with inequalities
- Algorithms for Propositional Model Counting
- Evaluating Datalog via tree automata and cycluits
- Computational complexity of auditing finite attributes in statistical databases
- Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons
- On the power of structural decompositions of graph-based representations of constraint problems
- Semantic Acyclicity on Graph Databases
- Regularizing conjunctive features for classification
- Fast and parallel decomposition of constraint satisfaction problems
- Decomposing Quantified Conjunctive (or Disjunctive) Formulas
- Title not available (Why is that?)
- Tree-Width for First Order Formulae
- Linear Programs with Conjunctive Database Queries
- Schema Mappings: A Case of Logical Dynamics in Database Theory
- CSP beyond tractable constraint languages
- Computing a partition function of a generalized pattern-based energy over a semiring
- Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
- Title not available (Why is that?)
- HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results
- Complexity Analysis of Generalized and Fractional Hypertree Decompositions
- Fast parallel hypertree decompositions in logarithmic recursion depth
- Computing optimal hypertree decompositions with SAT
This page was built for publication: Hypertree decompositions and tractable queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q696962)
