A negative conjunctive query is easy if and only if it is beta-acyclic

DOI10.4230/LIPICS.CSL.2012.137MaRDI QIDQ4649543zbMATH OpenFDO

Authors Johann Brault-Baron

Publication date 22 November 2012

zbMATH Keywords

conjunctive queryhypergraphdata complexityDavis-Putnam procedurebeta-acyclicity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Database theory (68P15) Decidability of theories and sets of sentences (03B25)

Recommendations

• The complexity of acyclic conjunctive queries
• Hypertree decompositions and tractable queries
• Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• Conjunctive query containment revisited

Cited in

(4)

• Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT
• Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
• Boolean tensor decomposition for conjunctive queries with negation
• Enumerating answers to first-order queries over databases of low degree

This page was built for publication: A negative conjunctive query is easy if and only if it is beta-acyclic

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