Query evaluation via tree-decompositions
From MaRDI portal
Publication:3455547
DOI10.1145/602220.602222zbMath1326.68123OpenAlexW2046652577MaRDI QIDQ3455547
Jörg Flum, Markus Frick, Martin Grohe
Publication date: 7 December 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/602220.602222
Related Items
Some aspects of the database resilience, Structural tractability of counting of solutions to conjunctive queries, Marshals, monotone marshals, and hypertree-width, The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems, Computing Tree Decompositions, An existential locality theorem, Computing crossing numbers in quadratic time, Provenance Circuits for Trees and Treelike Instances, Semantic Acyclicity on Graph Databases, Answering conjunctive queries with inequalities, Weighted hypertree decompositions and optimal query plans, Connecting Width and Structure in Knowledge Compilation (Extended Version), Tractable counting of the answers to conjunctive queries, Recognizable languages of arrows and cospans, The complexity of weighted counting for acyclic conjunctive queries, Parameterised counting in logspace, Courcelle's theorem -- a game-theoretic approach, Obtaining a Planar Graph by Vertex Deletion, Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments, Conjunctive query containment over trees using schema information, Unnamed Item, Constraint satisfaction with succinctly specified relations, Compact representation for answer sets of \(n\)-ary regular queries, Unnamed Item, Unnamed Item, Practical algorithms for MSO model-checking on tree-decomposable graphs, First-Order Model-Checking in Random Graphs and Complex Networks, Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms, SOME MODEL THEORY OF GUARDED NEGATION, On the complexity of existential positive queries, List H-coloring a graph by removing few vertices, A Practical Approach to Courcelle's Theorem, Decomposing Quantified Conjunctive (or Disjunctive) Formulas, Bounded treewidth as a key to tractability of knowledge representation and reasoning, Guarded Negation, Compact Representation for Answer Sets of n-ary Regular Queries, An Experimental Study of the Treewidth of Real-World Graph Data, Tree-Width for First Order Formulae, Evaluating Datalog via tree automata and cycluits, HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results, Enumeration complexity of conjunctive queries with functional dependencies, Uniform Constraint Satisfaction Problems and Database Theory, Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits, On the expressive power of monadic least fixed point logic
