Integrity Checking for Multiple Updates.

@inproceedings{DBLP:conf/sigmod/HsuI85,
  author    = {Arding Hsu and
               Tomasz Imielinski},
  editor    = {Shamkant B. Navathe},
  title     = {Integrity Checking for Multiple Updates},
  booktitle = {Proceedings of the 1985 ACM SIGMOD International Conference on
               Management of Data, Austin, Texas, May 28-31, 1985},
  publisher = {ACM Press},
  year      = {1985},
  pages     = {152-168},
  ee        = {http://doi.acm.org/10.1145/318898.318914, db/conf/sigmod/HsuI85.html},
  crossref  = {DBLP:conf/sigmod/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper we generalize methods for fast checking of integrity constraints to deal with multiple (multlple-tuple and multiple-range) updates. This enables us to consider practically important cases when updates are neither restricted to single range(relatlon) nor to single tuple and could be grouped in possibly complex transactions.

We provide simplification method for arbitrary transactions, and also for arbitrary constraints expressed in prenex normal form in relational tuple calculus with no restrictions on the number of variables ranging over the same relation. Based on the prefix of a constraint, our simplifcation algorithms transform the constraint into an AND-OR combination of simpler constraints which are easier to check. The analysis of certain patterns in the prefixes of constraints enables us to conclude when for a given type of updates no simplication is possible at all and when a significant improvement can be achieved. In effect we can recommend this method as as fast tool for a possibly preliminary but fast simplification of a constraint when not much of the structure of atransaction(update) is known. In case further simplification is needed, one must look for methods requiring more information about updates and constraints.

Copyright © 1985 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

• 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/smod7592 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

Online Edition: ACM Digital Library

References

[Bernstein et al. 80]

Philip A. Bernstein, Barbara T. Blaustein, Edmund M. Clarke: Fast Maintenance of Semantic Integrity Assertions Using Redundant Aggregate Data. VLDB 1980: 126-136 BibTeX

[Blaustein 81]

...

[Buneman & Clemons 79]

Peter Buneman, Eric K. Clemons: Efficient Monitoring Relational Databases. ACM Trans. Database Syst. 4(3): 368-382(1979) BibTeX

[Eswaran 75]

Kapali P. Eswaran, Donald D. Chamberlin: Functional Specifications of Subsystem for Database Integrity. VLDB 1975: 48-68 BibTeX

[Fagin 80]

Ronald Fagin: Horn Clauses and Database Dependencies (Extended Abstract). STOC 1980: 123-134 BibTeX

[Hammer & Sarin 78]

Michael Hammer, Sunil K. Sarin: Efficient Monitoring of Database Assertions (Abstract). SIGMOD Conference 1978: 159 BibTeX

[Henschen 84]

Lawrence J. Henschen, William McCune, Shamim A. Naqvi: Compiling Constraint-Checking Programs from First-Order Formulas. Advances in Data Base Theory 1982: 145-169 BibTeX

[Koenig & Paige 81]

Shaye Koenig, Robert Paige: A Transformational Framework for the Automatic Control of Derived Data. VLDB 1981: 306-318 BibTeX

[lafue 79]

...

[Nicolas 78]

Jean-Marie Nicolas, Kioumars Yazdanian: Integrity Checking in Deductive Data Bases. Logic and Data Bases 1977: 325-344 BibTeX

[Nicolas 79]

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

[Stonebraker 75]

Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 BibTeX

Referenced by

1. Naci Ishakbeyoglu, Z. Meral Özsoyoglu: Maintenance of Implication Integrity Constraints Under Updates to Constraints. VLDB J. 7(2): 67-78(1998)
2. Véronique Benzaken, Xavier Schaefer: Static Management of Integrity in Object-Oriented Databases: Design and Implementation. EDBT 1998: 311-325
3. Michael Benedikt, Timothy Griffin, Leonid Libkin: Verifiable Properties of Database Transactions. PODS 1996: 117-127
4. Véronique Benzaken, Anne Doucet: Thémis: A Database Programming Language Handling Integrity Constraints. VLDB J. 4(3): 493-517(1995)
5. Jan Chomicki: Efficient Checking of Temporal Integrity Constraints Using Bounded History Encoding. ACM Trans. Database Syst. 20(2): 149-186(1995)
6. Wen-Chi Hou, Zhongyang Zhang: Enhancing Database Correctness: a Statistical Approach. SIGMOD Conference 1995: 223-232
7. Timothy Griffin, Howard Trickey: Integrity Maintenance in A Telecommunications Switch. IEEE Data Eng. Bull. 17(2): 43-46(1994)
8. Xiaolei Qian: The Deductive Synthesis of Database Transactions. ACM Trans. Database Syst. 18(4): 626-677(1993)
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. Paul W. P. J. Grefen: Combining Theory and Practice in Integrity Control: A Declarative Approach to the Specification of a Transaction Modification Subsystem. VLDB 1993: 581-591
11. Michael Gertz, Udo W. Lipeck: Deriving Integrity Maintaining Triggers from Transition Graphs. ICDE 1993: 22-29
12. Véronique Benzaken, Anne Doucet: Thémis: a database programming language with integrity constraints. DBPL 1993: 243-262
13. Subhasish Mazumdar: Optimizing Distributed Integrity Constraints. DASFAA 1993: 327-334
14. Tok Wang Ling, Sin Yeung Lee: Improving Integrity Checking for Exists-Constraints. DASFAA 1993: 343-350
15. H. V. Jagadish, Xiaolei Qian: Integrity Maintenance in Object-Oriented Databases. VLDB 1992: 469-480
16. Uwe Hohenstein, Klaus Hülsmann: A Language for Specifying Static and Dynamic Integrity Constraints. ER 1991: 389-416
17. Stefano Ceri, Jennifer Widom: Deriving Production Rules for Constraint Maintainance. VLDB 1990: 566-577
18. Jean Philippe Lagrange: A Knowledge-Based System and an ER Query Language for Accessing Relational Databases. ER 1990: 157-170
19. Klaus Hülsmann, Gunter Saake: Representation of the Historical Information Necessary for Temporal Integrity Monitoring. EDBT 1990: 378-392
20. Tim Sheard, David W. Stemple: Automatic Verification of Database Transaction Safety. ACM Trans. Database Syst. 14(3): 322-368(1989)
21. Tore Risch: Monitoring Database Objects. VLDB 1989: 445-453
22. Arding Hsu, Tomasz Imielinski: View Maintenance for Multiple Updates. DASFAA 1989: 233-239
23. Marco A. Casanova, Luiz Tucherman, Antonio L. Furtado: Enforcing Inclusion Dependencies and Referencial Integrity. VLDB 1988: 38-49
24. Xiaolei Qian: An Effective Method for Integrity Constraint Simplification. ICDE 1988: 338-345
25. Lawrence Chung, Daniel Rios-Zertuche, Brian A. Nixon, John Mylopoulos: Process Management and Assertion Enforcement for a Semantic Data Model. EDBT 1988: 469-487
26. Xiaolei Qian, Douglas R. Smith: Integrity Constraint Reformulation for Efficient Validation. VLDB 1987: 417-425
27. David W. Stemple, Subhasish Mazumdar, Tim Sheard: On the Modes and Meaning of Feedback to Transaction Designers. SIGMOD Conference 1987: 374-386