Integrity Constraint Reformulation for Efficient Validation.

Xiaolei Qian, Douglas R. Smith: Integrity Constraint Reformulation for Efficient Validation. VLDB 1987: 417-425

@inproceedings{DBLP:conf/vldb/QianS87,
  author    = {Xiaolei Qian and
               Douglas R. Smith},
  editor    = {Peter M. Stocker and
               William Kent and
               Peter Hammersley},
  title     = {Integrity Constraint Reformulation for Efficient Validation},
  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     = {417-425},
  ee        = {db/conf/vldb/QianS87.html},
  crossref  = {DBLP:conf/vldb/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Constraint validation has been difficult to implement efficiently. The major reason for this difficulty lies in the state-dependent nature of integrity constraints and the requirement of both high-level specification and efficient runtime enforcement. In this paper, we propose a constraint reformulation approach to efficient constraint validation. We also demonstrate how this knowledge-based constraint reformulation can be naturally accomplished in the general framework of problem reformulation with the technique of antecedent derivation. We formalize the reformulation of an integrity constraint as a tree-search process where the search space is the set of all semantic-equivalent alternatives of the original constraint. We also develop control strategies and meta-level rules for carrying out the search efficiently. The major contribution of this work is a new promising approach to efficient constraint validation and a general framework to accomplish it.

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

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" 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/vldb7588 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" 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 DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Peter M. Stocker, William Kent, Peter Hammersley (Eds.): VLDB'87, Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England. Morgan Kaufmann 1987, ISBN 0-934613-46-X
Contents

References

[1]: Dushan Z. Badal, Gerald J. Popek: Cost and Performance Analysis of Semantic Integrity Validation Methods. SIGMOD Conference 1979: 109-115
[2]: Philip A. Bernstein, Barbara T. Blaustein, Edmund M. Clarke: Fast Maintenance of Semantic Integrity Assertions Using Redundant Aggregate Data. VLDB 1980: 126-136
[3]: ...
[4]: Antonio L. Furtado, Clesio Saraiva dos Santos, José Mauro Volkmer de Castilho: Dynamic modelling of a simple existence constraint. Inf. Syst. 6(1): 73-80(1981)
[5]: Michael Hammer, Stanley B. Zdonik: Knowledge-Based Query Processing. VLDB 1980: 137-147
[6]: Arding Hsu, Tomasz Imielinski: Integrity Checking for Multiple Updates. SIGMOD Conference 1985: 152-168
[7]: ...
[8]: ...
[9]: Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517
[10]: Gilles M. E. Lafue: Semantic Integrity Dependencies and Delayed Integrity Checking. VLDB 1982: 292-299
[11]: Matthew Morgenstern: The Role of Constraints in Databases, Expert Systems, and Knowledge Representation. Expert Database Workshop 1984: 351-368
[12]: Jean-Marie Nicolas: Logic for Improving Integrity Checking in Relational Data Bases. Acta Inf. 18: 227-253(1982)
[13]: Jean-Marie Nicolas, Kioumars Yazdanian: Integrity Checking in Deductive Data Bases. Logic and Data Bases 1977: 325-344
[14]: Robert Paige: Applications of Finite Differencing to Database Integrity Control and Query/Transaction Optimization. Advances in Data Base Theory 1982: 171-209
[15]: ...
[16]: Xiaolei Qian, Gio Wiederhold: Knowledge-based Integrity Constraint Validation. VLDB 1986: 3-12
[17]: Allan Shepherd, Larry Kerschberg: Constraint Management in Expert Database Systems. Expert Database Workshop 1984: 309-331
[18]: Douglas R. Smith: Derived Preconditions and Their Use in Program Synthesis. CADE 1982: 172-193
[19]: Douglas R. Smith: Top-Down Synthesis of Divide-and-Conquer Algorithms. Artif. Intell. 27(1): 43-96(1985)
[20]: Douglas R. Smith, Gordon Kotik, Stephen J. Westfold: Research on Knowledge-Based Software Environments at Kestrel Institute. IEEE Trans. Software Eng. 11(11): 1278-1295(1985)
[21]: Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78
[22]: ...