Integrity Constraint Reformulation for Efficient Validation.

Xiaolei Qian, Douglas R. Smith: Integrity Constraint Reformulation for Efficient Validation. VLDB 1987: 417-425
  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,}


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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

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 BibTeX


Dushan Z. Badal, Gerald J. Popek: Cost and Performance Analysis of Semantic Integrity Validation Methods. SIGMOD Conference 1979: 109-115 BibTeX
Philip A. Bernstein, Barbara T. Blaustein, Edmund M. Clarke: Fast Maintenance of Semantic Integrity Assertions Using Redundant Aggregate Data. VLDB 1980: 126-136 BibTeX
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) BibTeX
Michael Hammer, Stanley B. Zdonik: Knowledge-Based Query Processing. VLDB 1980: 137-147 BibTeX
Arding Hsu, Tomasz Imielinski: Integrity Checking for Multiple Updates. SIGMOD Conference 1985: 152-168 BibTeX
Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517 BibTeX
Gilles M. E. Lafue: Semantic Integrity Dependencies and Delayed Integrity Checking. VLDB 1982: 292-299 BibTeX
Matthew Morgenstern: The Role of Constraints in Databases, Expert Systems, and Knowledge Representation. Expert Database Workshop 1984: 351-368 BibTeX
Jean-Marie Nicolas: Logic for Improving Integrity Checking in Relational Data Bases. Acta Inf. 18: 227-253(1982) BibTeX
Jean-Marie Nicolas, Kioumars Yazdanian: Integrity Checking in Deductive Data Bases. Logic and Data Bases 1977: 325-344 BibTeX
Robert Paige: Applications of Finite Differencing to Database Integrity Control and Query/Transaction Optimization. Advances in Data Base Theory 1982: 171-209 BibTeX
Xiaolei Qian, Gio Wiederhold: Knowledge-based Integrity Constraint Validation. VLDB 1986: 3-12 BibTeX
Allan Shepherd, Larry Kerschberg: Constraint Management in Expert Database Systems. Expert Database Workshop 1984: 309-331 BibTeX
Douglas R. Smith: Derived Preconditions and Their Use in Program Synthesis. CADE 1982: 172-193 BibTeX
Douglas R. Smith: Top-Down Synthesis of Divide-and-Conquer Algorithms. Artif. Intell. 27(1): 43-96(1985) BibTeX
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) BibTeX
Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 BibTeX

Referenced by

  1. Jan Chomicki: Efficient Checking of Temporal Integrity Constraints Using Bounded History Encoding. ACM Trans. Database Syst. 20(2): 149-186(1995)
  2. Wei Sun, Clement T. Yu: Semantic Query Optimization for Tree and Chain Queries. IEEE Trans. Knowl. Data Eng. 6(1): 136-151(1994)
  3. Subhasish Mazumdar: Optimizing Distributed Integrity Constraints. DASFAA 1993: 327-334
  4. Tok Wang Ling, Sin Yeung Lee: Improving Integrity Checking for Exists-Constraints. DASFAA 1993: 343-350
  5. H. V. Jagadish, Xiaolei Qian: Integrity Maintenance in Object-Oriented Databases. VLDB 1992: 469-480
  6. Stefano Ceri, Jennifer Widom: Deriving Production Rules for Constraint Maintainance. VLDB 1990: 566-577
  7. Clement T. Yu, Wei Sun: Automatic Knowledge Acquisition and Maintenance for Semantic Query Optimization. IEEE Trans. Knowl. Data Eng. 1(3): 362-375(1989)
  8. Sreekumar T. Shenoy, Z. Meral Özsoyoglu: Design and Implementation of a Semantic Query Optimizer. IEEE Trans. Knowl. Data Eng. 1(3): 344-361(1989)
  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
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:36 2009