A more general theory of static approximations for conjunctive queries

DOI10.1007/s00224-019-09924-0zbMath1446.68051OpenAlexW2944076341MaRDI QIDQ778535

Thomas Zeume, Pablo Barceló, Miguel Romero

Publication date: 2 July 2020

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8602/

zbMATH Keywords

approximationsconjunctive queriesexistential pebble gamehypertreewidth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Data exchange: semantics and query answering
• The core of a graph
• Hypertree decompositions and tractable queries
• On the expressive power of Datalog: tools and a case study.
• On the complexity of database queries
• Conjunctive query containment revisited
• Conjunctive-query containment and constraint satisfaction
• Complexity of tree homomorphisms
• Taming the Infinite Chase: Query Answering under Expressive Relational Constraints
• Decidability Results for the Boundedness Problem
• Undecidable optimization problems for database logic programs
• Semantic Acyclicity on Graph Databases
• Efficient Approximations of Conjunctive Queries
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• Constraint solving via fractional edge covers
• A normal form for relational databases that is based on domains and keys
• The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
• Computer Science Logic
• Querying the Guarded Fragment

This page was built for publication: A more general theory of static approximations for conjunctive queries