Integrity Checking in Deductive Databases.

@inproceedings{DBLP:conf/vldb/KowalskiSS87,
  author    = {Robert A. Kowalski and
               Fariba Sadri and
               Paul Soper},
  editor    = {Peter M. Stocker and
               William Kent and
               Peter Hammersley},
  title     = {Integrity Checking in Deductive Databases},
  booktitle = {VLDB'87, Proceedings of 13th International Conference on Very
               Large Data Bases, September 1-4, 1987, Brighton, England},
  publisher = {Morgan Kaufmann},
  year      = {1987},
  isbn      = {0-934613-46-X},
  pages     = {61-69},
  ee        = {db/conf/vldb/KowalskiSS87.html},
  crossref  = {DBLP:conf/vldb/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We describe the theory and implementation of a general theorem-proving technique for checking integrity of deductive databases recently proposed by Sadri and Kowalski. The method uses an extension of the SLDNF proof procedure and achieves the effect of the simplification algorithms of Nicolas, Lloyd, Topor et al, and Decker by reasoning forwards from the update and thus focusing on the relevant parts of the database and the relevant constraints.

Formalisation of the procedure using logic as metalanguage forms the basis of our implementation in Prolog. It is further shown that in the absence of implicit deletions a transformation of the database clauses and constraints allows the method to be implemented with efficiencies comparable to implementations of Prolog.

Copyright © 1987 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb7588 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[1]

Keith L. Clark: Negation as Failure. Logic and Data Bases 1977: 293-322 BibTeX

[2]

...

[3]

...

[4]

Robert A. Kowalski: A Proof Procedure Using Connection Graphs. J. ACM 22(4): 572-595(1975) BibTeX

[5]

...

[6]

John W. Lloyd: Foundations of Logic Programming, 1st Edition. Springer 1984, ISBN 3-540-13299-6
BibTeX

[7]

John W. Lloyd, Liz Sonenberg, Rodney W. Topor: Integrity Constraint Checking in Stratified Databases. J. Log. Program. 4(4): 331-343(1987) BibTeX

[8]

John W. Lloyd, Rodney W. Topor: A Basis for Deductive Database Systems. J. Log. Program. 2(2): 93-109(1985) BibTeX

[9]

John W. Lloyd, Rodney W. Topor: A Basis for Deductive Database Systems II. J. Log. Program. 3(1): 55-67(1986) BibTeX

[10]

Jean-Marie Nicolas: Logic for Improving Integrity Checking in Relational Data Bases. Acta Inf. 18: 227-253(1982) BibTeX

[11]

...

[12]

...

[13]

...

Referenced by

1. Haifeng Yu, Amin Vahdat: Efficient Numerical Error Bounding for Replicated Network Services. VLDB 2000: 123-133
2. Carlos A. Mareco, Leopoldo E. Bertossi: Specification and Implementation of Temporal Databases in a Bitemporal Event Calculus. ER (Workshops) 1999: 74-85
3. Véronique Benzaken, Xavier Schaefer: Static Management of Integrity in Object-Oriented Databases: Design and Implementation. EDBT 1998: 311-325
4. Sin Yeung Lee, Tok Wang Ling: Further Improvements on Integrity Constraint Checking for Stratifiable Deductive Databases. VLDB 1996: 495-505
5. Véronique Benzaken, Anne Doucet: Thémis: A Database Programming Language Handling Integrity Constraints. VLDB J. 4(3): 493-517(1995)
6. Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995)
7. Ashish Gupta, Sanjai Tiwari: Constraint Management On Distributed Design Databases. IEEE Data Eng. Bull. 17(2): 47-51(1994)
8. Bernhard Thalheim: State-Conditioned Semantics in Databases. ER 1994: 171-188
9. Christoph F. Eick, Paul Werstein: Rule-Based Consistency Enforcement for Knowledge-Based Systems. IEEE Trans. Knowl. Data Eng. 5(1): 52-64(1993)
10. Ashish Gupta, Jennifer Widom: Local Verification of Global Integrity Constraints in Distributed Databases. SIGMOD Conference 1993: 49-58
11. Véronique Benzaken, Anne Doucet: Thémis: a database programming language with integrity constraints. DBPL 1993: 243-262
12. Tok Wang Ling, Sin Yeung Lee: Improving Integrity Checking for Exists-Constraints. DASFAA 1993: 343-350
13. Guido Moerkotte, Peter C. Lockemann: Reactive Consistency Control In Deductive Databases. ACM Trans. Database Syst. 16(4): 670-702(1991)
14. Antoni Olivé: Integrity Constraints Checking In Deductive Databases. VLDB 1991: 513-523
15. Lois M. L. Delcambre, Billy B. L. Lim, Susan Darling Urban: Object-Centered Constraints. ICDE 1991: 368-377
16. Peter C. Lockemann, Guido Moerkotte: On the Notion of Concept. ER 1991: 349-370
17. Klaus Hülsmann, Gunter Saake: Representation of the Historical Information Necessary for Temporal Integrity Monitoring. EDBT 1990: 378-392
18. Antoni Olivé: On the design and implementation of information systems from deductive conceptual models. VLDB 1989: 3-11
19. Guido Moerkotte, Stefan Karl: Efficient Consistency Control in Deductive Databases. ICDT 1988: 118-128
20. François Bry, Hendrik Decker, Rainer Manthey: A Uniform Approach to Constraint Satisfaction and Constraint Satisfiability in Deductive Databases. EDBT 1988: 488-505