Benchmarking Approximate Consistent Query Answering

Marco Calautti, Marco Console, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Consistent query answering (CQA) aims to deliver meaningful answers when queries are evaluated over inconsistent databases. Such answers must be certainly true in all repairs, which are consistent databases whose difference from the inconsistent one is somehow minimal. Although CQA provides a clean framework for querying inconsistent databases, it is arguably more informative to compute the percentage of repairs in which a candidate answer is true, instead of simply saying that is true in all repairs, or is false in at least one repair. It should not be surprising, though, that computing this percentage is computationally hard. On the other hand, for practically relevant settings such as conjunctive queries and primary keys, there are data-efficient randomized approximation schemes for approximating this percentage. Our goal is to perform a thorough experimental evaluation and comparison of those approximation schemes. Our analysis provides new insights on which technique is indicated depending on key characteristics of the input.
Original languageEnglish
Title of host publicationProceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
PublisherACM Association for Computing Machinery
Number of pages14
ISBN (Electronic)9781450383813
Publication statusPublished - 20 Jun 2021
EventACM SIGMOD/PODS International Conference on Management Data - Virtual, Xi'an, China
Duration: 20 Jun 202125 Jun 2021


ConferenceACM SIGMOD/PODS International Conference on Management Data
Abbreviated titleSIGMOD/PODS 2021
Internet address

Keywords / Materials (for Non-textual outputs)

  • Inconsistent data
  • primary keys
  • conjunctive queries
  • consistent query answering
  • efficient approximations


Dive into the research topics of 'Benchmarking Approximate Consistent Query Answering'. Together they form a unique fingerprint.

Cite this