A remark on the complexity of consistent conjunctive query answering under primary key violations

DOI10.1016/J.IPL.2010.07.021MaRDI QIDQ1675764zbMATH OpenOpenAlexFDO

Authors Jef Wijsen

Publication date 3 November 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.07.021

zbMATH Keywords

consistent query answeringdatabase repairingdatabases

Mathematics Subject Classification ID

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

Recommendations

• Consistent query answering for self-join-free conjunctive queries under primary key constraints
• Consistent query answering for primary keys in Datalog
• A survey of the data complexity of consistent query answering under key constraints
• First-order under-approximations of consistent query answers
• A dichotomy in the complexity of counting database repairs

Cites work

• Elements of finite model theory.
• First-order query rewriting for inconsistent databases
• Minimal-change integrity maintenance using tuple deletions

Cited in

(8)

• Parameterized complexity of completeness reasoning for conjunctive queries
• On the data complexity of consistent query answering
• A dichotomy in the complexity of counting database repairs
• Consistent query answering for self-join-free conjunctive queries under primary key constraints
• Consistent query answering for primary keys in logspace
• A survey of the data complexity of consistent query answering under key constraints
• A simple algorithm for consistent query answering under primary keys
• A dichotomy in the complexity of consistent query answering for queries with two atoms

This page was built for publication: A remark on the complexity of consistent conjunctive query answering under primary key violations

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