Automatic Generation of Production Rules for Integrity Maintenance.

@article{DBLP:journals/tods/CeriFPT94,
  author    = {Stefano Ceri and
               Piero Fraternali and
               Stefano Paraboschi and
               Letizia Tanca},
  title     = {Automatic Generation of Production Rules for Integrity Maintenance},
  journal   = {ACM Trans. Database Syst.},
  volume    = {19},
  number    = {3},
  year      = {1994},
  pages     = {367-422},
  ee        = {http://doi.acm.org/10.1145/185827.185828, db/journals/tods/CeriFPT94.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this article we present an approach to integrity maintenance, consisting of automatically generating production rules for integrity enforcement. Constraints are expressed as particular formulas of Domain Relational Calculus; they are automatically translated into a set of repair actions, encoded as production rules of an active database system. Production rules may be redundant (they enforce the same constraint in different ways) and conflicting (because repairing one constraint may cause the violation of another constraint). Thus, it is necessary to develop techniques for analyzing the properties of the set of active rules and for ensuring that any computation of production rules after any incorrect transaction terminates and produces a consistent database state.

Along these guidelines, we describe a specific architecture for constraint definition and enforcement. The components of the architecture include a Rule Generator, for producing all possible repair actions, and a Rule Analyzer and Selector, for producing a collection of production rules such that their execution after an incorrect transaction always terminates in a consistent state (possibly by rolling back the transaction); moreover, the needs of applications are modeled, so that integrity-enforcing rules reach the final state that better represents the original intentions of the transaction's supplier. Specific input from the designer can also drive the process and integrate or modify the rules generated automatically by the method. Experimental results of a prototype implementation of the proposed architecture are also described.

Copyright © 1994 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.

Joint ACM SIGMOD / IEEE Computer Society 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/An3-2 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/aDVD2 or /dvd

Online Edition: ACM Digital Library

Addendum

References

[Abiteboul and Grumbach 1991]

Serge Abiteboul, Stéphane Grumbach: A Rule-Based Language with Functions and Sets. ACM Trans. Database Syst. 16(1): 1-30(1991) BibTeX

[Aiken et al. 1992]

Alexander Aiken, Jennifer Widom, Joseph M. Hellerstein: Behavior of Database Production Rules: Termination, Confluence, and Observable Determinism. SIGMOD Conference 1992: 59-68 BibTeX

[Bancilhon and Spyratos 1981]

François Bancilhon, Nicolas Spyratos: Update Semantics of Relational Views. ACM Trans. Database Syst. 6(4): 557-575(1981) BibTeX

[Blakeley et al. 1989]

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) BibTeX

[Brownston et al. 1985]

...

[Bry et al. 1988]

François Bry, Hendrik Decker, Rainer Manthey: A Uniform Approach to Constraint Satisfaction and Constraint Satisfiability in Deductive Databases. EDBT 1988: 488-505 BibTeX

[Cacace et al. 1990]

Filippo Cacace, Stefano Ceri, Stefano Crespi-Reghizzi, Letizia Tanca, Roberto Zicari: Integrating Object-Oriented Data Modeling with a Rule-Based Programming Paradigm. SIGMOD Conference 1990: 225-236 BibTeX

[Cannan and Otten 1992]

...

[Casanova et al. 1988]

Marco A. Casanova, Luiz Tucherman, Antonio L. Furtado: Enforcing Inclusion Dependencies and Referencial Integrity. VLDB 1988: 38-49 BibTeX

[Ceri and Garzotto 1988]

...

[Ceri and Widom 1990a]

Stefano Ceri, Jennifer Widom: Deriving Production Rules for Constraint Maintainance. VLDB 1990: 566-577 BibTeX

[Ceri and Widom 1990b]

...

[Ceri et al. 1992a]

...

[Ceri et al. 1992b]

Stefano Ceri, Piero Fraternali, Stefano Paraboschi, Letizia Tanca: Constraint Enforcement Through Production Rules: Putting Active Databases at Work. IEEE Data Eng. Bull. 15(1-4): 10-14(1992) BibTeX

[Ceri et al. 1992c]

...

[Ceri et al. 1990]

Stefano Ceri, Georg Gottlob, Letizia Tanca: Logic Programming and Databases. Springer 1990, ISBN 3-540-51728-6
BibTeX

[Chakravarthy 1989]

Sharma Chakravarthy: Rule Management and Evaluation: An Active DBMS Perspective. SIGMOD Record 18(3): 20-28(1989) BibTeX

[Chomicki 1992]

Jan Chomicki: History-less Checking of Dynamic Integrity Constraints. ICDE 1992: 557-564 BibTeX

[Dayal et al. 1988]

Umeshwar Dayal, Barbara T. Blaustein, Alejandro P. Buchmann, Upen S. Chakravarthy, Meichun Hsu, R. Ledin, Dennis R. McCarthy, Arnon Rosenthal, Sunil K. Sarin, Michael J. Carey, Miron Livny, Rajiv Jauhari: The HiPAC Project: Combining Active Databases and Timing Constraints. SIGMOD Record 17(1): 51-70(1988) BibTeX

[Fraternali and Paraboschi 1993]

Piero Fraternali, Stefano Paraboschi: A Review of Repairing Techniques for Integrity Maintenance. Rules in Database Systems 1993: 333-346 BibTeX

[Fraternali and Paraboschi 1992]

...

[Fraternali et al. 1994]

Piero Fraternali, Danilo Montesi, Letizia Tanca: Active Database Semantics. Australasian Database Conference 1994: 195-212 BibTeX

[Fraternali et al. 1993]

Piero Fraternali, Stefano Paraboschi, Letizia Tanca: Automatic Rule Generation for Constraint Enforcement in Active Databases. FMLDO 1992: 153-173 BibTeX

[Gallo et al. 1993]

...

[Garey and Johnson 1979]

M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX

[Gertz and Lipeck 1993]

Michael Gertz, Udo W. Lipeck: Deriving Integrity Maintaining Triggers from Transition Graphs. ICDE 1993: 22-29 BibTeX

[Gottlob et al. 1988]

Georg Gottlob, Paolo Paolini, Roberto Zicari: Properties and Update Semantics of Consistent Views. ACM Trans. Database Syst. 13(4): 486-524(1988) BibTeX

[Hanson and Widom 1992]

...

[Karadimce and Urban 1991]

Anton P. Karadimce, Susan Darling Urban: Diagnosing Anomalous Rule Behavior in Databases with Integrity Maintenance Production Rules. FMLDO 1991: 77-102 BibTeX

[Karp 1972]

...

[Keller 1986]

Arthur M. Keller: Choosing a View Update Translator by Dialog at View Definition Time. VLDB 1986: 467-474 BibTeX

[Larson and Sheth 1991]

James A. Larson, Amit P. Sheth: Updating relational views using knowledge at view definition and view update time. Inf. Syst. 16(2): 145-168(1991) BibTeX

[Lipeck and Saake 1987]

Udo W. Lipeck, Gunter Saake: Monitoring dynamic integrity constraints based on temporal logic. Inf. Syst. 12(3): 255-269(1987) BibTeX

[Moerkotte and Lockemann 1991]

Guido Moerkotte, Peter C. Lockemann: Reactive Consistency Control In Deductive Databases. ACM Trans. Database Syst. 16(4): 670-702(1991) BibTeX

[Morgenstern 1984]

Matthew Morgenstern: Constraint Equations: Declarative Expression of Constraints With Automatic Enforcement. VLDB 1984: 291-300 BibTeX

[Naqvi and Tsur 1989]

Shamim A. Naqvi, Shalom Tsur: A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
BibTeX

[Nicolas and Yazdanian 1978]

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

[Paredaens et al. 1989]

...

[Pastor 1992]

Joan Antoni Pastor: Deriving Consistency-preserving Transaction Specifications for (View-)Updates in Relational Databases. DAISD 1992: 275-300 BibTeX

[Schewe et al. 1993]

Klaus-Dieter Schewe, Bernhard Thalheim, Joachim W. Schmidt, Ingrid Wetzel: Integrity Enforcement in Object-Oriented Databases. FMLDO 1992: 174-195 BibTeX

[Sheard and Stemple 1989]

Tim Sheard, David W. Stemple: Automatic Verification of Database Transaction Safety. ACM Trans. Database Syst. 14(3): 322-368(1989) BibTeX

[Stemple et al. 1987]

David W. Stemple, Subhasish Mazumdar, Tim Sheard: On the Modes and Meaning of Feedback to Transaction Designers. SIGMOD Conference 1987: 374-386 BibTeX

[Stonebraker et al. 1990]

Michael Stonebraker, Anant Jhingran, Jeffrey Goh, Spyros Potamianos: On Rules, Procedures, Caching and Views in Data Base Systems. SIGMOD Conference 1990: 281-290 BibTeX

[Thalheim 1991]

...

[Ullman 1982]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[Urban and Delcambre 1990]

Susan Darling Urban, Lois M. L. Delcambre: Constraint Analysis: A Design Process for Specifying Operations on Objects. IEEE Trans. Knowl. Data Eng. 2(4): 391-400(1990) BibTeX

[Urban and Desiderio 1992]

Susan Darling Urban, Mario Desiderio: CONTEXT: A CONstrainT EXplanation Tool. Data Knowl. Eng. 8: 153-183(1992) BibTeX

[Urban et al. 1992]

Susan Darling Urban, Anton P. Karadimce, Ravi B. Nannapaneni: The Implementation and Evaluation of Integrity Maintenance Rules in an Object-Oriented Database. ICDE 1992: 565-572 BibTeX

[Urban and Lim 1993]

...

[Van Gelder and Topor 1991]

Allen Van Gelder, Rodney W. Topor: Safety and Translation of Relational Calculus Queries. ACM Trans. Database Syst. 16(2): 235-278(1991) BibTeX

[Widom 1992]

Jennifer Widom: A Denotational Semantics for the Starburst Production Rule Language. SIGMOD Record 21(3): 4-9(1992) BibTeX

[Widom and Finkelstein 1990]

Jennifer Widom, Sheldon J. Finkelstein: Set-Oriented Production Rules in Relational Database Systems. SIGMOD Conference 1990: 259-270 BibTeX

[Widom et al. 1991]

Jennifer Widom, Roberta Cochrane, Bruce G. Lindsay: Implementing Set-Oriented Production Rules as an Extension to Starburst. VLDB 1991: 275-285 BibTeX

[Wüthrich 1993]

Beat Wüthrich: On Updates and Inconsistency Repairing in Knowledge Bases. ICDE 1993: 608-615 BibTeX

[Zhou and Hsu 1990]

Yuli Zhou, Meichun Hsu: A Theory for Rule Triggering Systems. EDBT 1990: 407-421 BibTeX

Referenced by

1. Enric Mayol, Ernest Teniente: A Survey of Current Methods for Integrity Constraint Maintenance and View Updating. ER (Workshops) 1999: 62-73
2. Naci Ishakbeyoglu, Z. Meral Özsoyoglu: Maintenance of Implication Integrity Constraints Under Updates to Constraints. VLDB J. 7(2): 67-78(1998)
3. Elena Baralis, Stefano Ceri, Stefano Paraboschi: Compile-Time and Runtime Analysis of Active Behaviors. IEEE Trans. Knowl. Data Eng. 10(3): 353-370(1998)
4. Piero Fraternali, Stefano Paraboschi: Ordering and Selecting Production Rules for Constraint Maintenance: Complexity and Heuristic Solution. IEEE Trans. Knowl. Data Eng. 9(1): 173-178(1997)
5. Nicole Bidoit, Sofian Maabout: A Model Theoretic Approach to Update Rule Programs. ICDT 1997: 173-187
6. Klaus-Dieter Schewe: Well-Behaving Rule Systems for Entity-Relationship and Object-Oriented Models. ER 1997: 141-154
7. Elena Baralis, Stefano Ceri, Stefano Paraboschi: Modularization Techniques for Active Rules Design. ACM Trans. Database Syst. 21(1): 1-29(1996)
8. Jennifer Widom: The Starburst Active Database Rule System. IEEE Trans. Knowl. Data Eng. 8(4): 583-595(1996)
9. Stefano Ceri, Raghu Ramakrishnan: Rules in Database Systems. ACM Comput. Surv. 28(1): 109-111(1996)
10. I-Min A. Chen: Query Answering Using Discovered Rules. ICDE 1996: 402-411
11. Martin Steeg: The Conceptual Database Design Optimizer CoDO - Concepts, Implementation, Application. ER 1996: 105-120
12. Jennifer Widom, Stefano Ceri (Eds.): Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996, ISBN 1-55860-304-2
    Contents
13. Piero Fraternali, Letizia Tanca: A Structured Approach for the Definition of the Semantics of Active Databases. ACM Trans. Database Syst. 20(4): 414-471(1995)
14. I-Min A. Chen, Richard Hull, Dennis McLeod: An Execution Model for Limited Ambiguity Rules and Its Application to Derived Data Update. ACM Trans. Database Syst. 20(4): 365-413(1995)
15. Stefano Ceri, Piero Fraternali, Stefano Paraboschi, Letizia Tanca: Addendum to "Automatic Generation of Production Rules for Integrity Maintenance". ACM Trans. Database Syst. 20(3): 364(1995)
16. Stefano Ceri, Piero Fraternali, Stefano Paraboschi: Constraint Management in Chimera. IEEE Data Eng. Bull. 17(2): 4-8(1994)
17. Elena Baralis, Stefano Ceri, Stefano Paraboschi: Declarative Specification of Constraint Maintenance. ER 1994: 205-222