Abstract
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 language | English |
|---|---|
| Title of host publication | Foundations of Information and Knowledge Systems : 8th International Symposium, FoIKS 2014, Bordeaux, France, March 3-7, 2014. Proceedings |
| Editors | Christoph Beierle, Carlo Meghini |
| Number of pages | 20 |
| Publisher | Springer |
| Publication date | 2014 |
| Pages | 361-380 |
| ISBN (Print) | 978-3-319-04938-0 |
| ISBN (Electronic) | 978-3-319-04939-7 |
| DOIs | |
| Publication status | Published - 2014 |
| Event | 8th International Symposium on the Foundations of Information and knowledge Systems - Bordeaux, France Duration: 3. Mar 2014 → 7. Mar 2014 Conference number: 8 |
Conference
| Conference | 8th International Symposium on the Foundations of Information and knowledge Systems |
|---|---|
| Number | 8 |
| Country/Territory | France |
| City | Bordeaux |
| Period | 03/03/2014 → 07/03/2014 |
| Series | Lecture Notes in Computer Science |
|---|---|
| Volume | 8367 |
| ISSN | 0302-9743 |