Hypertree decompositions and tractable queries
From MaRDI portal
Publication:696962
DOI10.1006/JCSS.2001.1809zbMATH Open1052.68025OpenAlexW2033325972WikidataQ59259717 ScholiaQ59259717MaRDI QIDQ696962FDOQ696962
Authors: 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
Recommendations
Cites Work
- Title not available (Why is that?)
- The well-founded semantics for general logic programs
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Closure properties of constraints
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- On Determining Tree Query Membership Of A Distributed Query
- Tree queries
- Computing LOGCFL certificates
Cited In (80)
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- A negative conjunctive query is easy if and only if it is beta-acyclic
- A Logical Approach to Constraint Satisfaction
- Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT
- When is the evaluation of conjunctive queries tractable?
- 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
- 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
- Title not available (Why is that?)
- 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
- Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width
- On Sparse Discretization for Graphical Games
- Some characterizations of \(\gamma \) and \(\beta \)-acyclicity of hypergraphs
- Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm
- A backtracking-based algorithm for hypertree decomposition
- 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
- Semantic acyclicity on graph databases
- Structural tractability of enumerating CSP solutions
- Domain permutation reduction for constraint satisfaction problems
- Coalition structure generation: a survey
- Hypertree width and related hypergraph invariants
- Graph-Theoretic Concepts in Computer Science
- 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
- Title not available (Why is that?)
- Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
- Algorithms for Propositional Model Counting
- Computational complexity of auditing finite attributes in statistical databases
- Generalized hypertree decompositions: NP-hardness and tractable variants
- Query evaluation via tree-decompositions
- Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons
- On the power of structural decompositions of graph-based representations of constraint problems
- Between tree patterns and conjunctive queries: is there tractability beyond acyclicity?
- Combined tractability of query evaluation via tree automata and cycluits
- Regularizing conjunctive features for classification
- Fast and parallel decomposition of constraint satisfaction problems
- D-FLAT: declarative problem solving using tree decompositions and answer-set programming
- Title not available (Why is that?)
- Tree-Width for First Order Formulae
- Linear Programs with Conjunctive Database Queries
- CSP beyond tractable constraint languages
- Large hypertree width for sparse random hypergraphs
- Hyperconsistency width for constraint satisfaction: Algorithms and complexity results
- Computing a partition function of a generalized pattern-based energy over a semiring
- Balanced queries: divide and conquer
- Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
- Schema mappings: a case of logical dynamics in database theory
- Title not available (Why is that?)
- Answering conjunctive queries with inequalities
- Complexity Analysis of Generalized and Fractional Hypertree Decompositions
- Evaluating Datalog via tree automata and cycluits
- Tree projections: Game characterization and computational aspects
- Fast parallel hypertree decompositions in logarithmic recursion depth
- Computing optimal hypertree decompositions with SAT
- Decomposing Quantified Conjunctive (or Disjunctive) Formulas
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)
