Automatic generation of production rules for integrity maintenance

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.

REFERENCES

• 1: Serge Abiteboul , Stéphane Grumbach, A rule-based language with functions and sets, ACM Transactions on Database Systems (TODS), v.16 n.1, p.1-30, March 1991 [doi>10.1145/103140.103141]
• 2: Alexander Aiken , Jennifer Widom , Joseph M. Hellerstein, Behavior of database production rules: termination, confluence, and observable determinism, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.59-68, June 02-05, 1992, San Diego, California, United States
• 3: F. Bancilhon , N. Spyratos, Update semantics of relational views, ACM Transactions on Database Systems (TODS), v.6 n.4, p.557-575, Dec. 1981 [doi>10.1145/319628.319634]
• 4: José A. Blakeley , Neil Coburn , Per-:1Vke Larson, Updating derived relations: detecting irrelevant and autonomously computable updates, ACM Transactions on Database Systems (TODS), v.14 n.3, p.369-400, Sept. 1989 [doi>10.1145/68012.68015]
• 5: Lee Brownston , Robert Farrell , Elaine Kant , Nancy Martin, Programming expert systems in OPS5: an introduction to rule-based programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 6: François Bry , Hendrik Decker , Rainer Manthey, A Uniform Approach to Constraint Satisfaction and Constraint Satisfiability in Deductive Databases, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.488-505, March 14-18, 1988
• 7: F. Cacace , S. Ceri , S. Crespi-Reghizzi , L. Tanca , R. Zicari, Integrating object-oriented data modelling with a rule-based programming paradigm, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.225-236, May 23-26, 1990, Atlantic City, New Jersey, United States
• 8: CANNAN, S. J. AND OTT~N, G. A. M. 1992. SQL--The Standard Handbook. McGraw-Hill, London.
• 9: Marco A. Casanova , Luiz Tucherman , Antonio L. Furtado, Enforcing Inclusion Dependencies and Referencial Integrity, Proceedings of the 14th International Conference on Very Large Data Bases, p.38-49, August 29-September 01, 1988
• 10: CERI, S. AND GARZOTTO, F. 1988 Specification and management of database integnty constraints through logSc programming. Tech. Rep. 88~025, Politecnico di Milano, Dipartimento di Elettronica e Informazione, Milan, Italy.
• 11: Stefano Ceri , Jennifer Widom, Deriving production rules for constraint maintenance, Proceedings of the sixteenth international conference on Very large databases, p.566-577, September 1990, Brisbane, Australia
• 12: CErn, S. ANo WmOM, J. 1990b. Deriving production rules for constraint maintenance Tech. Rep. RJ7348, IBM Almaden Research Center, San Jose, Calif.
• 13: CERI, S. I~RATERNALI, P., PARABOSCHI, S., AND TANCA, L. 1992a. Automatic generation of production rules for integTity maintenance. Tech. Rep. 92-054, Politecnico di Milano, D~partlmento di Elettromca e Informazione, Milan, Italy.
• 14: CERI, S.. FRATERNALI, P., PARABOSCHI, S., AND TANCA, L. 1992b. Constraint enforcement through production rules: Putting active databases to work. IEEE Data Eng. 15, 1 4, 10-14.
• 15: CERI, S., GARZOTTO, F., AND GOTTLOB, G 1992c. Specification and management of database integTlty constraints through logie programming techniques. Tech. Rep. 92-089, Politeenico dl Milano, Dipartimento di Elettronica e Informazione, Milan, Italy.
• 16: Stefano Ceri , Georg Gottlob , Letizia Tanca, Logic programming and databases, Springer-Verlag New York, Inc., New York, NY, 1990
• 17: S. Chakravarthy, Rule management and evaluation: an active DBMS perspective, ACM SIGMOD Record, v.18 n.3, p.20-28, Sep. 1989 [doi>10.1145/71031.71034]
• 18: Jan Chomicki, History-less Checking of Dynamic Integrity Constraints, Proceedings of the Eighth International Conference on Data Engineering, p.557-564, February 03-07, 1992
• 19: U. Dayal , B. Blaustein , A. Buchmann , U. Chakravarthy , M. Hsu , R. Ledin , D. McCarthy , A. Rosenthal , S. Sarin , M. J. Carey , M. Livny , R. Jauhari, The HiPAC project: combining active databases and timing constraints, ACM SIGMOD Record, v.17 n.1, p.51-70, March, 1988 [doi>10.1145/44203.44208]
• 20: FRATERNALi, P. AND PARABOSCHI, S. 1993. A review of repairing techniques for integrity maintenance. In Proceedzng~ of the 1st Workshop on Rules m Database Systems. Springer- Verlag, Berlin.
• 21: FRATERNALI, P. AND PARABOSCHI, S. 1992. Selecting production rules for constraint maintenance: Comp}exity and heuristic solution. Tech. Rep. 92-057, Politecmco di Milano, Dipartimento di Elettronica e Informazlone, Milan, Italy.
• 22: FRATERNALI, F., MONTESI, D., AND TANCA, L. 1994. Active database semantics. In Proceedmgs of ADC '94 Flfih Australastan Database Conference. Univ. of Canterbury, New Zealand.
• 23: FRATERNALI, P., PARABOSCHI, S., AND TANCA, L. 1993. Automatic ru}e generation for correction of constraint violatmns in active databases. In Modelling Database Dynamws. Springer-Verlag, Berlin, 153-173
• 24: Giorgio Gallo , Giustino Longo , Stefano Pallottino , Sang Nguyen, Directed hypergraphs and applications, Discrete Applied Mathematics, v.42 n.2-3, p.177-201, April 27, 1993 [doi>10.1016/0166-218X(93)90045-P]
• 25: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 26: Michael Gertz , Udo W. Lipeck, Deriving Integrity Maintaining Triggers from Transition Graphs, Proceedings of the Ninth International Conference on Data Engineering, p.22-29, April 19-23, 1993
• 27: Georg Gottlob , Paolo Paolini , Roberto Zicari, Properties and update semantics of consistent views, ACM Transactions on Database Systems (TODS), v.13 n.4, p.486-524, Dec. 1988 [doi>10.1145/49346.50068]
• 28: HANSON, E H. AND WIDOM, J. 1992. An overview of production rules m database systems. Knowl. Eng. 8, 2, 121-143
• 29: KARADIMCE, A. P AND URBAN, S.D. 1991. Dmgnosing anomalous rule behavior in databases with integrity mmntenance production rules. In Proceedmgs ofthe 3rcl International Workshop on Foundahons of Models and Languages for Data and Objects. Technische Universit~t Clausthal, 77 102.
• 30: KARP, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. Plenum Press, New York.
• 31: Arthur M. Keller, Choosing a View Update Translator by Dialog at View Definition Time, Proceedings of the 12th International Conference on Very Large Data Bases, p.467-474, August 25-28, 1986
• 32: James A. Larson , Amit P. Sheth, Updating relational views using knowledge at view definition and view update time, Information Systems, v.16 n.2, p.145-168, 1991 [doi>10.1016/0306-4379(91)90012-X]
• 33: U. W. Lipeck , G. Saake, Monitoring dynamic integrity constraints based on temporal logic, Information Systems, v.12 n.3, p.255-269, 1987 [doi>10.1016/0306-4379(87)90004-4]
• 34: Guido Moerkotte , Peter C. Lockemann, Reactive consistency control in deductive databases, ACM Transactions on Database Systems (TODS), v.16 n.4, p.670-702, Dec. 1991 [doi>10.1145/115302.115298]
• 35: Matthew Morgenstern, Constraint Equations: Declarative Expression of Constraints With Automatic Enforcement, Proceedings of the 10th International Conference on Very Large Data Bases, p.291-300, August 27-31, 1984
• 36: S. Naqvi , S. Tsur, A logical language for data and knowledge bases, Computer Science Press, Inc., New York, NY, 1989
• 37: N~COLAS, J. M. AND YAZDaMAN, K. 1978. Integrity checking in deductive data bases. In Log~c and Data Bases. Plenum Press, New York, 325-343.
• 38: Jan Paredaens , Paul De Bra , Marc Gyssens , Dirk Van Gucht, The structure of the relational database model, Springer-Verlag New York, Inc., New York, NY, 1989
• 39: PASTOR, J.A. 1992. Deriving consistency-preserving transaction specifications for (vlew-) updates in relational databases. In Proceedings of the 3rd International Workshop on the Deductwe Approach to Information Systems and Databases. Universitat Politecnica de Catalunya, 275-300.
• 40: Klaus-Dieter Schewe , Bernhard Thalheim , Joachim W. Schmidt , Ingrid Wetzel, Integrity Enforcement in Object-Oriented Databases, Selected Papers from the Fourth International Workshop on Foundations of Models and Languages for Data and Objects: Modelling Database Dynamics, p.174-195, October 19-23, 1992
• 41: Tim Sheard , David Stemple, Automatic verification of database transaction safety, ACM Transactions on Database Systems (TODS), v.14 n.3, p.322-368, Sept. 1989 [doi>10.1145/68012.68014]
• 42: David Stemple , Subhasish Mazumdar , Tim Sheard, On the modes and meaning of feedback to transaction designers, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.374-386, May 27-29, 1987, San Francisco, California, United States
• 43: Michael Stonebraker , Anant Jhingran , Jeffrey Goh , Spyros Potamianos, On rules, procedure, caching and views in data base systems, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.281-290, May 23-26, 1990, Atlantic City, New Jersey, United States
• 44: THALHEIM, B. 1991. Dependeneies in Relational Databases. B. G. Teubner Verlagsgesellschaft, Stuttgart.
• 45: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 46: S. D. Urban , L. M. L. Delcambre, Constraint Analysis: A Design Process for Specifying Operations on Objects, IEEE Transactions on Knowledge and Data Engineering, v.2 n.4, p.391-400, December 1990 [doi>10.1109/69.63251]
• 47: Susan D. Urban , Mario Desiderio, CONTEXT: a CONstrainT EXplanation Tool, Data & Knowledge Engineering, v.8 n.2, p.153-183, May 1992 [doi>10.1016/0169-023X(92)90035-A]
• 48: Susan Darling Urban , Anton P. Karadimce , Ravi B. Nannapaneni, The Implementation and Evaluation of Integrity Maintenance Rules in an Object-Oriented Database, Proceedings of the Eighth International Conference on Data Engineering, p.565-572, February 03-07, 1992
• 49: Susan Darling Urban , Billy B. L. Lim, An intelligent framework for active support of database semantics, International Journal of Expert Systems, v.6 n.1, p.1-37, 1993
• 50: Allen Van Gelder , Rodney W. Topor, Safety and translation of relational calculus, ACM Transactions on Database Systems (TODS), v.16 n.2, p.235-278, June 1991 [doi>10.1145/114325.103712]
• 51: Jennifer Widom, A denotational semantics for the Starburst production rule language, ACM SIGMOD Record, v.21 n.3, p.4-9, Sept. 1992 [doi>10.1145/140979.140980]
• 52: Jennifer Widom , S. J. Finkelstein, Set-oriented production rules in relational database systems, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.259-270, May 23-26, 1990, Atlantic City, New Jersey, United States
• 53: Jennifer Widom , Roberta Cochrane , Bruce G. Lindsay, Implementing Set-Oriented Production Rules as an Extension to Starburst, Proceedings of the 17th International Conference on Very Large Data Bases, p.275-285, September 03-06, 1991
• 54: Beat Wüthrich, On Updates and Inconsistency Repairing in Knowledge Bases, Proceedings of the Ninth International Conference on Data Engineering, p.608-615, April 19-23, 1993
• 55: Yuli Zhou , Meichun Hsu, A theory for rule triggering systems, Proceedings of the international conference on extending database technology on Advances in database technology, p.407-421, March 1990, Venice, Italy

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Experimentation, Management

Keywords:
automatic generation of production rules