A More General Theory of Static Approximations for Conjunctive Queries

DOI10.4230/LIPIcs.ICDT.2018.7zbMath1489.68068arXiv1904.00934OpenAlexW2789288082MaRDI QIDQ3305350

Thomas Zeume, Miguel Romero, Pablo Barceló

Publication date: 6 August 2020

Full work available at URL: https://arxiv.org/abs/1904.00934

zbMATH Keywords

approximationsconjunctive querieshypertreewidthpebble games

Mathematics Subject Classification ID

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

Related Items (1)

Dynamic complexity of expansion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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 and constraint satisfaction
• Decidability Results for the Boundedness Problem
• 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
• Computer Science Logic

This page was built for publication: A More General Theory of Static Approximations for Conjunctive Queries