Efficient Monitoring of Database Assertions (Abstract).

@inproceedings{DBLP:conf/sigmod/HammerS78,
  author    = {Michael Hammer and
               Sunil K. Sarin},
  editor    = {Eugene I. Lowenthal and
               Nell B. Dale},
  title     = {Efficient Monitoring of Database Assertions (Abstract)},
  booktitle = {Proceedings of the 1978 ACM SIGMOD International Conference on
               Management of Data, Austin, Texas, May 31 - June 2, 1978},
  publisher = {ACM},
  year      = {1978},
  pages     = {159},
  ee        = {http://doi.acm.org/10.1145/509252.509290, db/conf/sigmod/HammerS78.html},
  crossref  = {DBLP:conf/sigmod/78},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A principal impediment to the use of declarative assertions for monitoring the state of a dynamic database is the high cost of conventional implementation techniques for such a facility. This paper presents a means of efficiently detecting violations of assertions caused by updates to a database. Our technique is based on the premise that the structure of updates to a database can generally be anticipated, and that an analysis of the potential effect that an update may have on an assertion can enable the assertion to be efficiently tested when the update is performed.

This analysis is performed by a compile-time assertion processor; for each type of update operation defined on the database, the assertion processor synthesizes a procedure that will be used to evaluate a set of given assertions whenever an operation of the given type is performed on the database. For each assertion and operation, the assertion processor performs a detailed logical analysis, called perturbation analysis, of the effect that the operation may have on the assertion. Perturbation analysis identifies conditions that can be efficiently tested at run-time (when an operation of the given type is performed) and that minimize the extent to which the assertion must be fully reevaluated; the identified conditions also enable the assertion to be tested before the update is actually performed, thereby avoiding the need for expensive back-out procedures in the case that the assertion is found to be violated. Based on this analysis, the assertion processor generates a set of alternative efficient means of determining whether or not execution of the operation causes the assertion to be violated. A database transaction processor, which estimates the performance cost of each of the alternatives in the context of the physical representation and access methods or the database, can then be used to identify the least expensive means of testing the assertion.

This work has been done in the particular context of semantic integrity assertions, but it readily extends to related problems of database monitoring. The efficiency of testing that can be achieved through the use of our assertion processing technique is comparable with that attainable through the use of hand-coded procedures. The technique therefore supports all the advantages of the declarative approach to database assertion-monitoring, while retaining the level of efficiency that is usually associated with procedural methods.

Copyright © 1978 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

Referenced by

1. Harumi A. Kuno, Elke A. Rundensteiner: Incremental Maintenance of Materialized Object-Oriented Views in MultiView: Strategies and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 10(5): 768-792(1998)
2. Jennifer Widom, Stefano Ceri (Eds.): Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996, ISBN 1-55860-304-2
   Contents
3. Wen-Chi Hou, Zhongyang Zhang: Enhancing Database Correctness: a Statistical Approach. SIGMOD Conference 1995: 223-232
4. Michael Siegel, Edward Sciore, Sharon C. Salveter: A Method for Automatic Rule Derivation to Support Semantic Query Optimization. ACM Trans. Database Syst. 17(4): 563-600(1992)
5. Rafael Alonso, Daniel Barbará, Hector Garcia-Molina: Data Caching Issues in an Information Retrieval System. ACM Trans. Database Syst. 15(3): 359-384(1990)
6. Jean Philippe Lagrange: A Knowledge-Based System and an ER Query Language for Accessing Relational Databases. ER 1990: 157-170
7. José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. ACM Trans. Database Syst. 14(3): 369-400(1989)
8. Donald Cohen: Compiling Complex Database Transition Triggers. SIGMOD Conference 1989: 225-234
9. Marco A. Casanova, Luiz Tucherman, Antonio L. Furtado: Enforcing Inclusion Dependencies and Referencial Integrity. VLDB 1988: 38-49
10. Xiaolei Qian: An Effective Method for Integrity Constraint Simplification. ICDE 1988: 338-345
11. Lawrence Chung, Daniel Rios-Zertuche, Brian A. Nixon, John Mylopoulos: Process Management and Assertion Enforcement for a Semantic Data Model. EDBT 1988: 469-487
12. José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. VLDB 1986: 457-466
13. José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71
14. Arding Hsu, Tomasz Imielinski: Integrity Checking for Multiple Updates. SIGMOD Conference 1985: 152-168
15. Eric Simon, Patrick Valduriez: Design and Implementation of an Extendible Integrity Subsystem. SIGMOD Conference 1984: 9-17
16. David W. Stemple, Tim Sheard: Specification and Verification of Abstract Database Types. PODS 1984: 248-257
17. Arvola Chan, Umeshwar Dayal, Stephen Fox, Daniel R. Ries: Supporting a Semantic Data Model in a Distributed Database System. VLDB 1983: 354-363
18. Gilles M. E. Lafue: Semantic Integrity Dependencies and Delayed Integrity Checking. VLDB 1982: 292-299
19. Philip A. Bernstein, Barbara T. Blaustein: Fast Methods for Testing Quantified Relational Calculus Assertions. SIGMOD Conference 1982: 39-50
20. Y. C. Hong, Stanley Y. W. Su: Associative Hardware and Software Techniques for Integrity Control. ACM Trans. Database Syst. 6(3): 416-440(1981)
21. Shaye Koenig, Robert Paige: A Transformational Framework for the Automatic Control of Derived Data. VLDB 1981: 306-318
22. Gerald A. Wilson: A Conceptual Model for Semantic Integrity Checking. VLDB 1980: 111-125
23. Philip A. Bernstein, Barbara T. Blaustein, Edmund M. Clarke: Fast Maintenance of Semantic Integrity Assertions Using Redundant Aggregate Data. VLDB 1980: 126-136
24. Won Kim: Relational Database Systems. ACM Comput. Surv. 11(3): 187-211(1979)
25. Rubens N. Melo: Monitoring Integrity Constraints in a CODASYL-Like DBMS. VLDB 1979: 209-218
26. Dushan Z. Badal, Gerald J. Popek: Cost and Performance Analysis of Semantic Integrity Validation Methods. SIGMOD Conference 1979: 109-115