Classifying integrity checking methods with regard to inconsistency tolerance

ABSTRACT

We define and examine six classes of methods for integrity checking: case-based, compositional, relevance-based, simplification-based, total-integrity-dependent, and measure-based ones. Each, except the penultimate, corresponds to a particular form of inconsistency tolerance. Inconsistency measures provide a new approach to integrity checking and inconsistency tolerance. For many methods, proofs or disproofs of their inconsistency tolerance become easier and more transparent by our classification. In general, a better understanding of inconsistency-tolerant integrity checking is achieved

REFERENCES

• 1: 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]
• 2: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 3: L. Bertossi, A. Hunter and T. Schaub. Inconsistency Tolerance. LNCS
• 4: François Bry , Hendrik Decker , Rainer Manthey, A Uniform Approach to Constraint Satisfaction and Constraint Satisfiability in Deductive Databases, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.488-505, March 14-18, 1988
• 5: Matilde Celma , Carlos Garcia , Laura Mota-Herranz , Hendrik Decker, Comparing and Synthesizing Integrity Checking Methods for Deductive Databases, Proceedings of the Tenth International Conference on Data Engineering, p.214-222, February 14-18, 1994
• 6: Upen S. Chakravarthy , John Grant , Jack Minker, Logic-based approach to semantic query optimization, ACM Transactions on Database Systems (TODS), v.15 n.2, p.162-207, June 1990 [doi>10.1145/78922.78924]
• 7: Henning Christiansen , Davide Martinenghi, On Simplification of Database Integrity Constraints, Fundamenta Informaticae, v.71 n.4, p.371-417, March 2006
• 8: A. de Keijzer and M. van Keulen. Proc. 2nd Workshop on Uncertainty in Databases, CTIT WP06-01, 2006.
• 9: H. Decker. Integrity enforcement on deductive databases. Proc. 1st EDS, 381.395. Benjamin/Cummings, 1987.
• 10: H. Decker. Inconsistency-tolerant knowledge assimilation. Proc. ICSOFT'07, 198--205, INSTICC Press, 2007.
• 11: H. Decker and D. Martinenghi. A relaxed approach to integrity and inconsistency in databases. Proc. 13th LPAR, LNCS vol. 4246, 287--301. Springer, 2006.
• 12: P. M. Dung , R. A. Kowalski , F. Toni, Dialectic proof procedures for assumption-based, admissible argumentation, Artificial Intelligence, v.170 n.2, p.114-159, February 2006 [doi>10.1016/j.artint.2005.07.002]
• 13: Jeffrey D. Ullman , Hector Garcia-Molina , Jennifer Widom, Database Systems: The Complete Book, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 14: John Grant , Anthony Hunter, Measuring inconsistency in knowledgebases, Journal of Intelligent Information Systems, v.27 n.2, p.159-184, September 2006 [doi>10.1007/s10844-006-2974-4]
• 15: Ashish Gupta , Yehoshua Sagiv , Jeffrey D. Ullman , Jennifer Widom, Constraint checking with partial information, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.45-55, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182597]
• 16: A. C. Kakas , A. Michael, Applications of abductive logic programming, Proceedings of the 1998 joint international conference and symposium on Logic programming, p.343-344, August 1998, Manchester, United Kingdom
• 17: Robert A. Kowalski , Francesca Toni , Gerhard Wetzel, Executing suspended logic programs, Fundamenta Informaticae, v.34 n.3, p.203-224, June 1, 1998
• 18: V. Küchenhoff. On the efficient computation of the difference between consecutive database states. In Deductive and Object-Oriented Databases, LNCS vol. 566, 478--502. Springer, 1991.
• 19: Sin Yeung Lee , Tok Wang Ling, Further Improvements on Integrity Constraint Checking for Stratifiable Deductive Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.495-505, September 03-06, 1996
• 20: J. W. Lloyd , E. A. Sonenberg , R. W. Topor, Integrity constraint checking in stratified databases, Journal of Logic Programming, v.4 n.4, p.331-343, December 1, 1987 [doi>10.1016/0743-1066(87)90009-4]
• 21: D. Martinenghi, H. Christiansen and H. Decker. Integrity checking and maintenance in relational and deductive databases and beyond. In Z. Ma (ed), Intelligent Databases: Technologies and Applications, 238--285. Idea Group, 2006.
• 22: J.-M. Nicolas. Logic for improving integrity checking in relational data bases. Acta Inform. 18:227--253, 1982.
• 23: Raghu Ramakrishnan, Database management systems, McGraw-Hill, Inc., New York, NY, 1997
• 24: Raymond Reiter, What should a database know?, Journal of Logic Programming, v.14 n.1-2, p.127-153, Oct., 1992 [doi>10.1016/0743-1066(92)90049-9]
• 25: F. Sadri , R. Kowalski, A theorem-proving approach to database integrity, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 26: Michael Stonebraker, Implementation of integrity constraints and views by query modification, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500091]
• 27: J. D. Ullman. What happened to theory anyway? http://infolab.stanford.edu/~ullman/pub/sigmod06.ppt, 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design

General Terms:
Reliability, Theory

Keywords:
inconsistency tolerance, integrity checking, integrity constraints