Document Open Access Logo

Grounded Fixpoints and Active Integrity Constraints

Author Luís Cruz-Filipe

PDF
Thumbnail PDF

File

OASIcs.ICLP.2016.11.pdf
  • Filesize: 423 kB
  • 14 pages

Document Identifiers

Author Details

Luís Cruz-Filipe

Cite As Get BibTex

Luís Cruz-Filipe. Grounded Fixpoints and Active Integrity Constraints. In Technical Communications of the 32nd International Conference on Logic Programming (ICLP 2016). Open Access Series in Informatics (OASIcs), Volume 52, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/OASIcs.ICLP.2016.11

Abstract

The formalism of active integrity constraints was introduced as a way to specify particular classes of integrity constraints over relational databases together with preferences on how to repair existing inconsistencies. The rule-based syntax of such integrity constraints also provides algorithms for finding such repairs that achieve the best asymptotic complexity.

However, the different semantics that have been proposed for these integrity constraints all exhibit some counter-intuitive examples. In this work, we look at active integrity constraints using ideas from algebraic fixpoint theory. We show how database repairs can be modeled as fixpoints of particular operators on databases, and study how the notion of grounded fixpoint induces a corresponding notion of grounded database repair that captures several natural intuitions, and in particular avoids the problems of previous alternative semantics.

In order to study grounded repairs in their full generality, we need to generalize the notion of grounded fixpoint to non-deterministic operators. We propose such a definition and illustrate its plausibility in the database context.

Subject Classification

Keywords
  • grounded fixpoints
  • active integrity constraints

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Serge Abiteboul. Updates, a new frontier. In Marc Gyssens, Jan Paredaens, and Dirk van Gucht, editors, ICDT, volume 326 of LNCS, pages 1-18. Springer, 1988. Google Scholar
  2. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison Wesley, 1995. Google Scholar
  3. Grigoris Antoniou. A tutorial on default logics. ACM Computing Surveys, 31(3):337-359, 1999. Google Scholar
  4. Catriel Beeri and Moshe Y. Vardi. The implication problem for data dependencies. In Colloquium on Automata, Languages and Programming, pages 73-85, London, UK, 1981. Springer. Google Scholar
  5. Bart Bogaerts, Joost Vennekens, and Marc Denecker. Grounded fixpoints and their applications in knowledge representation. Artif. Intell., 224:51-71, 2015. Google Scholar
  6. Luciano Caroprese, Sergio Greco, Cristina Sirangelo, and Ester Zumpano. Declarative semantics of production rules for integrity maintenance. In Sandro Etalle and Miroslaw Truszczynski, editors, ICLP, volume 4079 of LNCS, pages 26-40. Springer, 2006. Google Scholar
  7. Luciano Caroprese and Miroslaw Truszczynski. Active integrity constraints and revision programming. Theory Pract. Log. Program., 11(6):905-952, November 2011. Google Scholar
  8. Luís Cruz-Filipe. Optimizing computation of repairs from active integrity constraints. In Christoph Beierle and Carlo Meghini, editors, FoIKS, volume 8367 of LNCS, pages 361-380. Springer, 2014. Google Scholar
  9. Luís Cruz-Filipe, Patrícia Engrácia, Graça Gaspar, and Isabel Nunes. Computing repairs from active integrity constraints. In Hai Wang and Richard Banach, editors, TASE, pages 183-190. IEEE, July 2013. Google Scholar
  10. Luís Cruz-Filipe, Michael Franz, Artavazd Hakhverdyan, Marta Ludovico, Isabel Nunes, and Peter Schneider-Kamp. repAIrC: A tool for ensuring data consistency by means of active integrity constraints. In Ana L.N. Fred, Jan L.G. Dietz, David Aveiro, Kecheng Liu, and Joaquim Filipe, editors, KMIS, pages 17-26. SciTePress, 2015. Google Scholar
  11. Luís Cruz-Filipe, Isabel Nunes, and Peter Schneider-Kamp. Integrity constraints for general-purpose knowledge bases. In Marc Gyssens and Guillermo Ricardo Simari, editors, FoIKS, volume 9616 of LNCS, pages 235-254. Springer, 2016. Google Scholar
  12. Thomas Eiter and Georg Gottlob. On the complexity of propositional knowledge base revision, updates, and counterfactuals. Artif. Intell., 57(2-3):227-270, 1992. Google Scholar
  13. Melvin Fitting. Fixpoint semantics for logic programming: a survey. Theor. Comput. Sci., 278(1-2):25-51, 2002. Google Scholar
  14. Sergio Flesca, Sergio Greco, and Ester Zumpano. Active integrity constraints. In Eugenio Moggi and David Scott Warren, editors, PPDP, pages 98-107. ACM, 2004. Google Scholar
  15. Ahmed Guessoum. Abductive knowledge base updates for contextual reasoning. J. Intell. Inf. Syst., 11(1):41-67, 1998. Google Scholar
  16. Mohammed A. Khamsi, Vladik Kreinovich, and Driss Misane. A new method of proving the existence of answer sets for disjunctive logic programs. In Proceedings of the Workshop on Logic Programming with Incomplete Information, 1993. Google Scholar
  17. V. Wiktor Marek and Miroslav Truszczynski. Revision programming, database updates and integrity constraints. In Georg Gottlob and Moshe Y. Vardi, editors, ICDT, volume 893 of LNCS, pages 368-382. Springer, 1995. Google Scholar
  18. Enric Mayol and Ernest Teniente. Addressing efficiency issues during the process of integrity maintenance. In Trevor J.M. Bench-Capon, Giovanni Soda, and A Min Tjoa, editors, DEXA, volume 1677 of LNCS, pages 270-281. Springer, 1999. Google Scholar
  19. Shamim A. Naqvi and Ravi Krishnamurthy. Database updates in logic programming. In Chris Edmondson-Yurkanan and Mihalis Yannakakis, editors, PODS, pages 251-262. ACM, 1988. Google Scholar
  20. Teodor C. Przymusinski and Hudson Turner. Update by means of inference rules. J. Log. Program., 30(2):125-143, 1997. Google Scholar
  21. Raymond Reiter. A logic for default reasoning. Artificial Intelligence, 13:81-132, 1980. Google Scholar
  22. Ernest Teniente and Antoni Olivé. Updating knowledge bases while maintaining their consistency. VLDB J., 4(2):193-241, 1995. Google Scholar
  23. Jennifer Widom and Stefano Ceri, editors. Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann, 1996. Google Scholar
  24. Marianne Winslett. Updating Logical Databases. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1990. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact