Query evaluation via tree-decompositions

No abstract is available for this paper.

• Publication year

  2001

• Venue

  JACM

• Publication date

  2001-01-04

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/602220.602222
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The complexity of first-order and monadic second-order logic revisited

  2002cited by this paper
• Datalog LITE: a deductive query language with linear time model checking

  2002influential reference
• Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width

  2001cited by this paper
• When is the evaluation of conjunctive queries tractable?

  2001cited by this paper
• The complexity of acyclic conjunctive queries

  2001cited by this paper
• Easy instances for model checking

  2001cited by this paper
• A Comparison of Structural CSP Decomposition Methods

  1999cited by this paper
• Descriptive Complexity

  1999cited by this paper
• Datalog LITE: Temporal versus deductive reasoning in verification

  1998influential reference
• Parameterized Complexity

  1998cited by this paper
• Conjunctive-query containment and constraint satisfaction

  1998cited by this paper
• The complexity of acyclic conjunctive queries

  1998cited by this paper
• Hypertree decompositions and tractable queries

  1998influential reference
• Conjunctive query containment revisited

  1997influential reference
• Embeddings and minors

  1996cited by this paper
• Finite model theory

  1995cited by this paper
• On the complexity of bounded-variable queries (extended abstract)

  1995influential reference
• Foundations of Databases

  1994cited by this paper
• The Monadic Second order Logic of Graphs VI: on Several Representations of Graphs By Relational Structures

  1994cited by this paper
• Model theory and computer science: an appetizer

  1993influential reference
• Monotone monadic SNP and constraint satisfaction

  1993cited by this paper
• A linear time algorithm for finding tree-decompositions of small treewidth

  1993influential reference
• Graph Rewriting: An Algebraic and Logic Approach

  1991cited by this paper
• The Monadic Second-Order Logic of Graphs V: On Closing the Gap Between Definability and Recognizability

  1991cited by this paper
• Easy Problems for Tree-Decomposable Graphs

  1991cited by this paper
• Monadic Second-Order Evaluations on Tree-Decomposable Graphs

  1991cited by this paper
• Machine models and simulations

  1991cited by this paper
• Algorithms from P to NP

  1991cited by this paper
• Counting Classes: Thresholds, Parity, Mods, and Fewness

  1990cited by this paper
• Machine Models and Simulation

  1990cited by this paper
• On Finite Model Theory

  1990cited by this paper
• Complexity of finding embeddings in a k -tree

  1987influential reference
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

  1984cited by this paper
• The complexity of relational query languages (Extended Abstract)

  1982influential reference
• Algorithms for Acyclic Database Schemes

  1981cited by this paper
• The complexity of decision problems in automata theory and logic

  1974cited by this paper
• The Design and Analysis of Computer Algorithms

  1974cited by this paper

• Query Optimization for Database-Returning Queries

  2025cites this paper
• Optimal Oblivious Algorithms for Multi-way Joins

  2025cites this paper
• Various Properties of Various Ultrafilters, Various Graph Width Parameters, and Various Connectivity Systems

  2024cites this paper
• Parameterizing the quantification of CMSO: model checking on minor-closed graph classes

  2024influential citation
• Intermediate Relation Size Bounds for Select-Project-Join Query Plans: Asymptotically Tight Characterizations

  2024cites this paper
• Enumeration of Minimal Hitting Sets Parameterized by Treewidth

  2024cites this paper
• Evaluating Datalog over Semirings: A Grounding-based Approach

  2024cites this paper
• Intermediate Relation Size Bounds for Select-Project-Join-Union Query Plans

  2024cites this paper
• Enhancing Datalog Reasoning with Hypertree Decompositions

  2023cites this paper
• From Width-Based Model Checking to Width-Based Automated Theorem Proving

  2022cites this paper
• The Programming of Algebra

  2022cites this paper
• Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration

  2022cites this paper
• Saturation-Based Boolean Conjunctive Query Answering and Rewriting for the Guarded Quantification Fragments

  2022cites this paper
• Some Aspects of the Database Resilience

  2021cites this paper
• Computing Tree Decompositions

  2020cites this paper
• On Supergraphs Satisfying CMSO Properties

  2020cites this paper
• L O ] 3 J an 2 02 0 On Supergraphs Satisfying CMSO Properties ∗

  2020cites this paper
• Redundancy-Free Computation for Graph Neural Networks

  2020cites this paper
• Answering (Unions of) Join Queries using Random Access and Random-Order Enumeration

  2020cites this paper
• First-Order Model-Checking in Random Graphs and Complex Networks

  2020cites this paper
• On the Expressivity of ASK Queries in SPARQL

  2020cites this paper
• Answering Queries Using Views: Second Edition

  2019cites this paper
• Learning Concepts Definable in First-Order Logic with Counting

  2019cites this paper
• Parameterised Counting in Logspace

  2019cites this paper
• Answering Queries Using Views, Second Edition

  2019cites this paper
• Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration

  2019cites this paper
• An Experimental Study of the Treewidth of Real-World Graph Data (Extended Version)

  2019cites this paper
• Redundancy-Free Computation Graphs for Graph Neural Networks

  2019cites this paper
• Guarded Constraint Models Define Treewidth Preserving Reductions

  2019cites this paper
• Model-Checking on Ordered Structures

  2018cites this paper
• On the Enumeration Complexity of Unions of Conjunctive Queries

  2018cites this paper
• Combined Complexity of Probabilistic Query Evaluation

  2018influential citation
• Evaluating Datalog via Tree Automata and Cycluits

  2018influential citation
• Constraint satisfaction problems: complexity and algorithms

  2018cites this paper
• Liens entre largeur et structure en compilation de connaissances

  2018cites this paper
• Graph Amalgamation Under Logical Constraints

  2018cites this paper
• On the Enumeration Complexity of Unions of Conjunctive Queries

  2018cites this paper
• SOME MODEL THEORY OF GUARDED NEGATION

  2018cites this paper
• Une étude expérimentale de la largeur d ’ arbre de données graphe du monde réel

  2018cites this paper
• Recognizable languages of arrows and cospans

  2018cites this paper
• The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems

  2017influential citation
• Model-checking for successor-invariant first-order formulas on graph classes of bounded expansion

  2017cites this paper
• Enumeration on Trees under Relabelings

  2017influential citation
• Enumeration Complexity of Conjunctive Queries with Functional Dependencies

  2017cites this paper
• Containment for Rule-Based Ontology-Mediated Queries

  2017cites this paper
• Current Trends and New Perspectives for First-Order Model Checking (Invited Talk)

  2017cites this paper
• On the Complexity of Enumerating the Extensions of Abstract Argumentation Frameworks

  2017cites this paper
• Connecting Width and Structure in Knowledge Compilation

  2017cites this paper
• Logic, Languages, and Rules for Web Data Extraction and Reasoning over Data

  2017cites this paper
• Optimizing Tree Decompositions in MSO

  2017influential citation
• Static analysis of monadic datalog on finite labeled trees

  2017cites this paper
• Tree Projections and Constraint Optimization Problems: Fixed-Parameter Tractability and Parallel Algorithms

  2017cites this paper
• Local Structure Theorems for Erdős-Rényi Graphs and Their Algorithmic Applications

  2017cites this paper
• Answering Queries Using Views

  2017cites this paper
• Leveraging the structure of uncertain data

  2016influential citation
• What do Shannon information inequalities , submodular width , and disjunctive datalog have to do with one another ?

  2016cites this paper
• Tractable Lineages on Treelike Instances: Limits and Extensions

  2016cites this paper
• On the Enumeration of Tree Decompositions

  2016cites this paper
• Parallel Evaluation of Multi-Semi-Joins

  2016influential citation
• Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles)

  2016cites this paper
• Lignages efficaces sur les instances quasi-arborescentes : Limites et extensions

  2016cites this paper
• Implementing Courcelle's Theorem in a declarative framework for dynamic programming

  2016cites this paper
• Conjunctive query containment over trees using schema information

  2016influential citation
• Probabilistic Evaluation of Expressive Queries on Bounded-Treewidth Instances

  2016cites this paper
• Nowhere dense classes of graphs (characterisations and algorithmic meta-theorems) (Nowhere Dense Klassen von Graphen) (Charakterisierungen und algorithmische Meta-Sätze)

  2016cites this paper
• What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?

  2016cites this paper
• Combined Tractability of Query Evaluation via Tree Automata and Cycluits (Extended Version)

  2016cites this paper
• Circuits de provenance pour les arbres et les instances quasi-arborescentes

  2015cites this paper
• Provenance Circuits for Trees and Treelike Instances

  2015cites this paper
• The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space

  2015cites this paper
• Explorer Efficient Approximations of Conjunctive Queries

  2015influential citation
• RDFox: A Highly-Scalable RDF Store

  2015cites this paper
• Structurally Tractable Uncertain Data

  2015cites this paper
• Practical algorithms for MSO model-checking on tree-decomposable graphs

  2014influential citation
• Joins via Geometric Resolutions: Worst-case and Beyond

  2014influential citation
• Tractable Query Answering Under Probabilistic Constraints

  2014cites this paper
• Computer Science - Theory and Applications

  2014cites this paper
• Answering under Probabilistic Constraints

  2014cites this paper
• Principles of Guarded Structural Indexing

  2014cites this paper
• Counting solutions to conjunctive queries: structural and hybrid tractability

  2014cites this paper
• Answering Conjunctive Queries with Inequalities

  2014cites this paper
• Algorithmic Meta Theorems for Sparse Graph Classes

  2014cites this paper
• Probabilities and Provenance via Tree Decompositions

  2014cites this paper
• Hypergraph Acyclicity Revisited

  2014cites this paper
• Graph Automata and Their Application to the Verification of Dynamic Systems

  2014cites this paper
• On Model-theoretic Approaches to Monadic Second-Order Logic Evaluation

  2014influential citation
• Parallel-Correctness and Transferability for Conjunctive Queries

  2014cites this paper
• STRUCTURAL PARAMETERIZATIONS OF LANGUAGE RESTRICTED CONSTRAINT SATISFACTION PROBLEMS

  2013cites this paper
• Beyond worst-case analysis for joins with minesweeper

  2013cites this paper
• Removing the Haystack to Find the Needle(s): Minesweeper, an adaptive join algorithm

  2013cites this paper
• Parameterized Enumeration of Neighbour Strings and Kemeny Aggregations

  2013cites this paper
• Towards Instance Optimal Join Algorithms for Data in Indexes

  2013cites this paper
• Model Checking for Successor-Invariant First-Order Logic on Minor-Closed Graph Classes

  2013cites this paper
• Query Evaluation With Constant Delay

  2013cites this paper
• Declarative Dynamic Programming as an Alternative Realization of Courcelle's Theorem

  2013cites this paper
• Rewriting XPath Queries using View Intersections: Tractability versus Completeness

  2013cites this paper
• Semantic acyclicity on graph databases

  2013cites this paper
• List H-Coloring a Graph by Removing Few Vertices

  2013cites this paper
• Parameterized top-K algorithms

  2013cites this paper
• Fixed-parameter tractability of the graph isomorphism and canonization problems

  2013cites this paper