The Complexity of Counting Problems Over Incomplete Databases

DOI10.1145/3461642MaRDI QIDQ5056349zbMATH OpenOpenAlexWikidataFDO

Authors Marcelo Arenas, Pablo Barceló, Mikaël Monet

Publication date 8 December 2022

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

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

zbMATH Keywords

counting complexityincomplete databasesclosed-world assumptionfully polynomial-time randomized approximation scheme (FPRAS)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)

Recommendations

• A dichotomy in the complexity of counting database repairs
• The complexity of evaluating relational queries
• scientific article; zbMATH DE number 18538
• scientific article; zbMATH DE number 3850496
• A trichotomy in the complexity of counting answers to conjunctive queries

Cited in

(5)

• Parameterized complexity of completeness reasoning for conjunctive queries
• Consistent query answering for self-join-free conjunctive queries under primary key constraints
• The complexity of evaluating relational queries
• An epistemic approach to model uncertainty in data-graphs
• Uniform Reliability of Self-Join-Free Conjunctive Queries

This page was built for publication: The Complexity of Counting Problems Over Incomplete Databases

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