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.
Lecture Notes in Computer Science: 8th International Symposium, Foiks 2014, Bordeaux, France, March 3-7, 2014. Proceedings, 2014, p. 361-380
Main Research Area:
Lecture Notes in Computer Science
8th International Symposium on the Foundations of Information and knowledge SystemsFoundations of Information and Knowledge Systems, 2014