Active integrity constraints

ABSTRACT

In this paper we deal with inconsistent databases and propose a logic framework that allows specifying sets of actions which should be performed to make databases consistent (repairs). The motivation of this work stems from the observation that in repairing a database it is natural to express among a set of update operations, the (preferred) actions which should be performed to repair the database. We introduce (conditioned) active integrity constraints, a simple and powerful form of active rules with declarative semantics, well suited for computing database repairs and consistent answers. We first consider a "prescriptive" semantics where the allowed actions are those specified by the constraints. Under such a semantics the existence of repairs and consistent answers is not guaranteed. Thus, we also investigate the class of universally quantified constraints under a different semantics where actions are interpreted as preference conditions on the set of possible repairs ("preferable" semantics). Under such a semantics every database with integrity constraints admits repairs and consistent answers. We show that (conditioned) active integrity constraints can be rewritten into disjunctive Datalog programs with classical negation and that (preferred) repairs can be derived through the computation of (preferred) disjunctive stable models. We study the complexity of computing repairs and consistent answers and show that active integrity constraints can also be used to express hard problems.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Alferes J. J., J. A. Leite, Pereira L. M., Przymusinska H., and Przymusinski T.C. Dynamic updates of non-monotonic knowledge bases. Journal Logic Programming, 45(1-3):43--70, 2000.
• 3: José Júlio Alferes , Luís Moniz Pereira , Halina Przymusinska , Teodor C. Przymusinski, LUPS---a language for updating logic programs, Artificial Intelligence, v.138 n.1-2, p.87-116, June 2002 [doi>10.1016/S0004-3702(02)00183-2]
• 4: Marcelo Arenas , Leopoldo Bertossi , Jan Chomicki, Consistent query answers in inconsistent databases, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.68-79, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303983]
• 5: Arenas M., Bertossi L., and Chomicki J. Specifying and querying database repairs using logic programs with exceptions. In Flexible Query-Answering Systems (FQAS), pages 27--41, 2000.
• 6: Baral C. and Zhang Y. On the semantics of knowledge update. In IJCAI Conference, pages 97--102, 2001.
• 7: Chitta C. Embedding revision programs in logic programming situation calculus. Journal of Logic Programming, 30(1):83--97, 1997.
• 8: François Bry, Query Answering in Information Systems with Integrity Constraints, Proceedings of the IFIP TC11 Working Group 11.5, First Working Conference on Integrity and Internal Control in Information Systems: Increasing the confidence in Information Systems, p.113-130, December 04-05, 1997
• 9: Gerhard Brewka , Thomas Eiter, Preferred answer sets for extended logic programs, Artificial Intelligence, v.109 n.1-2, p.297-356, April 1999 [doi>10.1016/S0004-3702(99)00015-6]
• 10: Jan Chomicki, Querying with Intrinsic Preferences, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.34-51, March 25-27, 2002
• 11: Jan Chomicki , Jorge Lobo , Shamim Naqvi, Conflict Resolution Using Logic Programming, IEEE Transactions on Knowledge and Data Engineering, v.15 n.1, p.244-249, January 2003
• 12: Thomas Eiter , Georg Gottlob , Heikki Mannila, Disjunctive datalog, ACM Transactions on Database Systems (TODS), v.22 n.3, p.364-418, Sept. 1997 [doi>10.1145/261124.261126]
• 13: Sergio Flesca , Sergio Greco, Declarative semantics for active rules, Theory and Practice of Logic Programming, v.1 n.1, p.43-69, January 2001 [doi>10.1017/S1471068400001009]
• 14: Gelfond M. and Lifschitz V. The stable model semantics for logic programming. In ICLP/SLP, pages 1070--1080, 1988.
• 15: Gelfond M. and Lifschitz V. Classical negation in logic programs and disjunctive databases. NGC, 9(3/4):365--385, 1991.
• 16: John Grant , V. s. Subrahmanian, Reasoning in Inconsistent Knowledge Bases, IEEE Transactions on Knowledge and Data Engineering, v.7 n.1, p.177-189, February 1995 [doi>10.1109/69.368510]
• 17: Gianluigi Greco , Sergio Greco , Ester Zumpano, A Logic Programming Approach to the Integration, Repairing and Querying of Inconsistent Databases, Proceedings of the 17th International Conference on Logic Programming, p.348-364, November 26-December 01, 2001
• 18: Paris C. Kanellakis, Elements of relational database theory, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 19: M. Kifer , A. Li, On the semantics of rule-based expert systems with uncertainty, Lecture notes in computer science on ICDT '88, p.102-117, October 1988, Bruges, Belgium
• 20: Kowalski R.A. and Sadri F. Logic programs with exceptions. NGC, 9(3/4):387--400, 1991.
• 21: Jinxin Lin, A semantics for reasoning consistently in the presence of inconsistency, Artificial Intelligence, v.86 n.1, p.75-95, Sept. 1996 [doi>10.1016/0004-3702(95)00100-X]
• 22: V. Wiktor Marek , Inna Pivkina , Miroslaw Truszczynski, Revision Programming = Logic Programming + Integrity Constraints, Proceedings of the 12th International Workshop on Computer Science Logic, p.73-89, August 24-28, 1998
• 23: Victor W. Marek , Mirosław Truszczyński, Revision programming, Theoretical Computer Science, v.190 n.2, p.241-277, Jan. 20, 1998 [doi>10.1016/S0304-3975(97)00092-3]
• 24: Chiaki Sakama , Katsumi Inoue, Prioritized logic programming and its application to commonsense reasoning, Artificial Intelligence, v.123 n.1-2, p.185-222, Oct. 2000 [doi>10.1016/S0004-3702(00)00054-0]
• 25: V. S. Subrahmanian, Amalgamating knowledge bases, ACM Transactions on Database Systems (TODS), v.19 n.2, p.291-331, June 1994 [doi>10.1145/176567.176571]
• 26: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 27: Jef Wijsen, Condensed Representation of Database Repairs for Consistent Query Answering, Proceedings of the 9th International Conference on Database Theory, p.378-393, January 08-10, 2003
• 28: Yan Zhang , Norman Y. Foo, Answer sets for prioritized logic programs, Proceedings of the 1997 international symposium on Logic programming, p.69-83, November 1997, Port Washington, New York, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics; Syntax

General Terms:
Algorithms, Languages, Theory

Keywords:
inconsistent database, integrity constraints, logic programming