Hypertree decompositions and tractable queries
From MaRDI portal
Publication:696962
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
Related Items
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
