A more general theory of static approximations for conjunctive queries

DOI10.1007/S00224-019-09924-0MaRDI QIDQ778535zbMATH OpenOpenAlexFDO

Authors Pablo Barceló, Miguel Romero, Thomas Zeume

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

conjunctive queriesapproximationsexistential pebble gamehypertreewidth

Mathematics Subject Classification ID

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

Recommendations

• A more general theory of static approximations for conjunctive queries
• Efficient Approximations of Conjunctive Queries
• Theory and Applications of Satisfiability Testing
• scientific article; zbMATH DE number 1951561
• The complexity of acyclic conjunctive queries
• Complexity of Default Logic on Generalized Conjunctive Queries
• Optimization of a subclass of conjunctive queries
• scientific article; zbMATH DE number 219223
• scientific article; zbMATH DE number 3974350
• Semantic acyclicity for conjunctive queries: approximations and constraints

Cites work

• scientific article; zbMATH DE number 1936671 (Why is no real title available?)
• scientific article; zbMATH DE number 1953121 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• A normal form for relational databases that is based on domains and keys
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• Complexity of tree homomorphisms
• Computer Science Logic
• Conjunctive query containment revisited
• Conjunctive-query containment and constraint satisfaction
• Data exchange: semantics and query answering
• Decidability results for the boundedness problem
• Efficient Approximations of Conjunctive Queries
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Hypertree decompositions and tractable queries
• On the complexity of database queries
• On the expressive power of Datalog: tools and a case study.
• Querying the Guarded Fragment
• Semantic acyclicity on graph databases
• Taming the infinite chase: query answering under expressive relational constraints
• The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
• The core of a graph
• Undecidable optimization problems for database logic programs

Cited in

(7)

• A more general theory of static approximations for conjunctive queries
• Semantic acyclicity for conjunctive queries: approximations and constraints
• Answering conjunctive queries with inequalities
• The complexity of reverse engineering problems for conjunctive queries
• Theory and Applications of Satisfiability Testing
• Efficient Approximations of Conjunctive Queries
• Semantic Optimization of Conjunctive Queries

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q778535)