Optimizing Computation of Repairs from Active Integrity Constraints

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

222 Downloads (Pure)


Active integrity constraints (AICs) are a form of integrity constraints for databases that not only identify inconsistencies, but also suggest how these can be overcome. The semantics for AICs defines different types of repairs, but deciding whether an inconsistent database can be repaired and finding possible repairs is a NP- or Σ2p-complete problem, depending on the type of repairs one has in mind. In this paper, we introduce two different relations on AICs: an equivalence relation of independence, allowing the search to be parallelized among the equivalence classes, and a precedence relation, inducing a stratification that allows repairs to be built progressively. Although these relations have no impact on the worst-case scenario, they can make significant difference in the practical computation of repairs for inconsistent databases.
Original languageEnglish
Title of host publicationFoundations of Information and Knowledge Systems : 8th International Symposium, FoIKS 2014, Bordeaux, France, March 3-7, 2014. Proceedings
EditorsChristoph Beierle, Carlo Meghini
Number of pages20
Publication date2014
ISBN (Print)978-3-319-04938-0
ISBN (Electronic)978-3-319-04939-7
Publication statusPublished - 2014
Event8th International Symposium on the Foundations of Information and knowledge Systems - Bordeaux, France
Duration: 3. Mar 20147. Mar 2014
Conference number: 8


Conference8th International Symposium on the Foundations of Information and knowledge Systems
SeriesLecture Notes in Computer Science


Dive into the research topics of 'Optimizing Computation of Repairs from Active Integrity Constraints'. Together they form a unique fingerprint.

Cite this