Efficient Approximations of Conjunctive Queries

DOI10.1137/130911731MaRDI QIDQ3190694zbMATH OpenOpenAlexFDO

Authors Pablo Barceló, Miguel Romero, Leonid Libkin

Publication date 18 September 2014

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10533/135310

zbMATH Keywords

approximationconjunctive queriesgraphshomomorphismshypergraphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Hypergraphs (05C65) Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A more general theory of static approximations for conjunctive queries
• A more general theory of static approximations for conjunctive queries
• Optimization of a subclass of conjunctive queries
• scientific article; zbMATH DE number 219223
• Optimization of quasiconjunctive queries
• Theory and Applications of Satisfiability Testing
• scientific article; zbMATH DE number 1951561
• The complexity of acyclic conjunctive queries
• Size and treewidth bounds for conjunctive queries

Cited in

(28)

• Optimization of quasiconjunctive queries
• Can datalog be approximated?
• Models of approximation in databases
• Efficient and optimal query answering on independent schemes
• MCS Extraction with Sublinear Oracle Queries
• Semantic acyclicity for conjunctive queries: approximations and constraints
• Querying priced information in databases, the conjunctive case
• Semantic acyclicity on graph databases
• A more general theory of static approximations for conjunctive queries
• scientific article; zbMATH DE number 4058873 (Why is no real title available?)
• Efficient bottom-up computation of queries on stratified databases
• scientific article; zbMATH DE number 1953136 (Why is no real title available?)
• scientific article; zbMATH DE number 2086973 (Why is no real title available?)
• Size bounds for factorised representations of query results
• Database Theory - ICDT 2005
• Block-Sorted Quantified Conjunctive Queries
• Size and treewidth bounds for conjunctive queries
• Theory and Applications of Satisfiability Testing
• scientific article; zbMATH DE number 7650999 (Why is no real title available?)
• Verification, Model Checking, and Abstract Interpretation
• LATIN 2004: Theoretical Informatics
• When is approximate counting for conjunctive queries tractable?
• Answer Counting under Guarded TGDs
• Semantic tree-width and path-width of conjunctive regular path queries
• Querying incomplete data: complexity and tractability via Datalog and first-order rewritings
• Query repairs
• An adaptive mixed relation decomposition algorithm for conjunctive retrieval queries
• A more general theory of static approximations for conjunctive queries

This page was built for publication: Efficient Approximations of Conjunctive Queries

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