A structured approach for the definition of the semantics of active databases

ABSTRACT

Active DBMSs couple database technology with rule-based programming to achieve the capability of reaction to database (and possibly external) stimuli, called events. The reactive capabilities of active databases are useful for a wide spectrum of applications, including security, view materialization, integrity checking and enforcement, or heterogeneous database integration, which makes this technology very promising for the near future. An active database system consists of a (passive) database and a set of active rules; the most popular form of active rule is the so-called event-condition-action (ECA) rule, which specifies an action to be executed upon the occurrence of one or more events, provided that a condition holds. Several active database systems and prototypes have been designed and partially or completely implemented. Unfortunately, they have been designed in a totally independent way, without the support of a common theory dictating the semantics of ECA rules, and thus often show different behaviors for rules with a similar form. In this article we consider a number of different possible options in the behavior of an active DBMS, based on a broad analysis of some of the best known implemented systems and prototypes. We encode these options in a user-readable form, called Extended ECA. A rule from any existing system can be rewritten in this formalism making all the semantic choices apparent. Then an EECA rule can be automatically translated into an internal (less readable) format, based on a logical style, which is called core format: the execution semantics of core rules is specified as the fixpoint of a simple transformation involving core rules. As an important premise to this research, a semantics for database updates and transactions has also been established, with respect to a notion of state that comprises both data and events. The article also presents an extensive bibliography on the subject of active databases.

REFERENCES

• 1: Serge Abiteboul , Victor Vianu, Generic Computation and its complexity, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.209-219, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103444]
• 2: Rakesh Agrawal , Roberta Cochrane , Bruce G. Lindsay, On Maintaining Priorities in a Production Rule System, Proceedings of the 17th International Conference on Very Large Data Bases, p.479-487, September 03-06, 1991
• 3: ALLBASE 1992. Allbase Manuals.
• 4: E. Anwar , L. Maugis , S. Chakravarthy, A new perspective on rule support for object-oriented databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.99-108, May 25-28, 1993, Washington, D.C., United States
• 5: ARLEEN, R., GAVA, J., GEHANI, N., AND LmUWEN, D. 1995. Ode 4.0 (OdeiEOS~) user manual. Tech. Rep. AT & T Bell Labs, Murray Hill, NJ.
• 6: BARALIS, E., CERI, S., MONTELEONE, G., AND PAm~BOSCm, S. 1994. An intelligent database system application: The design of EMS. In Proceedings of First International Conference on Applications of Databases ADB-94, (Vadstena, Sweden), Lecture Notes in Computer Science, W. Litwin and T. Risch, Eds., Springer-Verlag, Berlin, 172-189.
• 7: Catriel Beeri , Tova Milo, A Model for Active Object Oriented Databases, Proceedings of the 17th International Conference on Very Large Data Bases, p.337-349, September 03-06, 1991
• 8: Anthony J. Bonner , Michael Kifer , Mariano P. Consens, Database Programming in Transaction Logic, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.309-337, August 30-September 01, 1993
• 9: BONNER, A. J., I<IFER, M. AND CONSENS, M.P. 1993b. Transaction logic programming. Tech. Rep. CSRI-270, University of Toronto. April (revised July 1, 1993).
• 10: BRANOING, H., BUCHMANN, A. P., KUDRASS, A., AND ZIMMERMANN, J. 1993. Rules in an open sysLem: The reach rule system. In Proceedings of the First Workshop on Rules in Database Systems (WICS, Edinburgh, Scotland), N. W. Paton and M. W. Williams, Eds. Springer-Verlag, Berlin, 111-126.
• 11: 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
• 12: Alejandro P. Buchmann , Jürgen Zimmermann , José A. Blakeley , David L. Wells, Building an Integrated Active OODBMS: Requirements, Architecture, and Design Decisions, Proceedings of the Eleventh International Conference on Data Engineering, p.117-128, March 06-10, 1995
• 13: CERI, S. AND FRATERNALL P. 1995. The IDEA methodology. Tech. Rep. IDEA.WP2.22P.001.03, ESPRIT Project no. 6333 IDEA.
• 14: Stefano Ceri , Piero Fraternali , Stefano Paraboschi , Letizia Tanca, Automatic generation of production rules for integrity maintenance, ACM Transactions on Database Systems (TODS), v.19 n.3, p.367-422, Sept. 1994 [doi>10.1145/185827.185828]
• 15: CERI, S., FRATERNALI, P., PARABOSCHI, S., AND TANCA, L. 1995. Active rule management in Chimera. In Active Database System6, J. Widom, and S. Ceri, Ed., Morgan-Kaufmann, San MaLeo, CA.
• 16: CERI, S. AND MANTHE~, R. 1993. Consolidated specification of Chimera, the conceptual interface of Idea. Tech. Rep. IDEA.DD.2P.004, ESPRIT Project no. 6333 Idea.
• 17: CERL S. AND WmOM, J. 1990a. Deriving production rules for constraint maintenance. Tech. Rep. 90-013, Politecnico di Milano, Dipartimento di Elettronica e Informazione.
• 18: 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
• 19: Stefano Ceri , Jennifer Widom, Deriving Production Rules for Incremental View Maintenance, Proceedings of the 17th International Conference on Very Large Data Bases, p.577-589, September 03-06, 1991
• 20: CHAKRAVARTHY, S., BLAUSTEIN, B., BUCHMANN, A., CAREY, M., DAYAL, U., GOLDHIRSCH, D., Ssu, M., JAUHARI, R., LADIN, R., LIVNI, M., McCARTHY, D., McKEE, R., AND ROSENTHAL, A. 1989. Hlpac: A research project in active, time-constrained database management Tech. Rep. XAIT-89-02, Xerox Advanced Information Technology
• 21: Christine Collet , Thierry Coupaye , T. Svensen, NAOS - Efficient and Modular Reactive Capabilities in an Object-Oriented Database System, Proceedings of the 20th International Conference on Very Large Data Bases, p.132-143, September 12-15, 1994
• 22: COMAI, S., FRATERNALI, P., PSAILA, G., AND TANCA, L. 1995. Active database semantms. Tech. Rep. 95-014, Politecnico di Milano, Dipartimento di Elettronica e Informazione.
• 23: DERANSART, P., JOURDAN, M., AND LORHO, B. 1988. Attribute Grammars, Vol. 323, Lecture Notes m Computer Science. Springer-Verlag, Berlin.
• 24: DIAZ, O. AND PATON, l~. 1991. Sharing behaviour in an object-oriented database using a rule-based mechanism In Proceedings of the Ninth British National Conference on Databases (Wolverhampton, UK), 17-37.
• 25: DIGITAL EQUIPMENT CORP. 1991. Rdb / VMS-SQL Reference Manual.
• 26: FRATENALI, P. AND TANCA, L. 1995. A structured approach for the definition of the semantics of active databases. Tech. Rep. 95-028, Politecnico di Milano, Dipartimento di Elettromca e Informazione. Avafiable at ftp://ftp.elet.polimi.it/pub/data/Letizia. Tanca/trep95028 ps.
• 27: GATZm, S. AND DITTRICH, K.R. 1992. Samos: An active object-oriented database system. IEEE Data Eng. 15, 1-4.
• 28: Stella Gatziu , Andreas Geppert , Klaus R. Dittrich, Integrating active concepts into an object-oriented database system, Proceedings of the third international workshop on Database programming languages : bulk types & persistent data: bulk types & persistent data, p.399-415, April 1992, Nafplion, Greece
• 29: Narain H. Gehani , H. V. Jagadish, Ode as an Active Database: Constraints and Triggers, Proceedings of the 17th International Conference on Very Large Data Bases, p.327-336, September 03-06, 1991
• 30: Narain H. Gehani , H. V. Jagadish , Oded Shmueli, Composite Event Specification in Active Databases: Model & Implementation, Proceedings of the 18th International Conference on Very Large Data Bases, p.327-338, August 23-27, 1992
• 31: N. H. Gehani , H. V. Jagadish , O. Shmueli, Event specification in an active object-oriented database, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.81-90, June 02-05, 1992, San Diego, California, United States
• 32: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 33: Eric N. Hanson, Rule condition testing and action execution in Ariel, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.49-58, June 02-05, 1992, San Diego, California, United States
• 34: HANSON, E. I-I. AND WIDOM, J. 1993. An overview of production rules in database systems. Knowl. Eng. 8, 2, 121-143.
• 35: David Harel, Statecharts: A visual formalism for complex systems, Science of Computer Programming, v.8 n.3, p.231-274, June 1, 1987 [doi>10.1016/0167-6423(87)90035-9]
• 36: Richard Hull , Dean Jacobs, Language Constructs for Programming Active Databases, Proceedings of the 17th International Conference on Very Large Data Bases, p.455-467, September 03-06, 1991
• 37: CORPORATE Informix Software, Informix guide to SQL, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 38: CORPORATE Informix Software, Informix guide to SQL, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 39: INGRES 1990. Ingres Database Administrator's Guide, Release 6.3.
• 40: INTERBASE 1990. DDL Reference Manual.
• 41: ISO-ANSI'94 1994. ISO-ANSI Working Draft: Database Language/SQL Foundation. Document DBL-RIO-004 and X3H2-94-329.
• 42: KAPPEL, G., RAUSCH-SCHO~W, S., AND RETSCHITZEGGER, W. 1994. Beyond coupling modes: Implementing active concepts on top of a commercial ooDBMS. Manuscript.
• 43: Dennis McCarthy , Umeshwar Dayal, The architecture of an active database management system, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.215-224, June 1989, Portland, Oregon, United States
• 44: On~CLE / I 1992. Oracle 7 Server Concepts Manual. No. 6693-70.
• 45: ORACLE / 2 1992. Oracle 7 server application developer's guide. No. 6695-70.
• 46: PALOPOLI, L. AND TORLONE, R. 1994. Modeling database applications using generalized production rules. In Fourth Internatzonal Workshop on Research Issues in Data Engineering: Active Database Systems (RIDE-ADS '94) (Houston, TX), 30-45.
• 47: PATON, N. W., DIAZ, O., WmLIAMS, M. H., C~PIN, J., DrNN, A., AND JAIME, A. 1993. Dimensions of active behaviour. In Proceedings of the First Workshop on Rules in Database Systems (WICS, Edinburgh, Scotland, Aug. 30-Sept. 1), N. W. Paten and M. H. Williams, Eds., Spfinger-Verlag, Berlin, 40-57.
• 48: P^TON, N. W. ANn WmL~S, M. H., Eos. 1993. Proceedings of First Workshop on Rules in Dalabase Systems (WICS, Edinburgh, Scotland, Aug. 30-Sept. 1), Springer-Verlag, Berlin.
• 49: Phillippe Picouet , Victor Vianu, Semantics and expressiveness issues in active databases (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.126-138, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220203]
• 50: SIMO~, E. AND KmRNAN, J. 1995. The A-RDL System. In Active Database Systems, Morgan Kaufmann, San Mateo, CA, 101-142.
• 51: M. Stonebraker, The Integration of Rule Systems and Database Systems, IEEE Transactions on Knowledge and Data Engineering, v.4 n.5, p.415-423, October 1992 [doi>10.1109/69.166984]
• 52: 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
• 53: SYBASE 1994. Sybase SQL Server: Transact-SQL User's Guide, Release 10.0.
• 54: TANcA, L. 1991. (Re~)action in deductive database. In Proceedings of the Second International Workshop on Intelligent and Cooperatwe Information Systems (Como, Italy), 55-61.
• 55: 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
• 56: 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]
• 57: WIDOM, J. AND CERI, S. 1995. Active Database Systems. Morgan-Kaufmann, San Mateo, CA.
• 58: 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
• 59: 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
• 60: Yannis E. Ioannidis , Timos K. Sellis, Conflict resolution of rules assigning values to virtual attributes, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.205-214, June 1989, Portland, Oregon, United States
• 61: ZANIOLO, C. 1993. A unified semantics for active and deductive databases. In Proceedings of the First Workshop on Rules in Database Systems (WICS, Edinburgh, Scotland), N. W. Paton and M. H. Williams, Eds., Springer-Verlag, Berlin, 271-288.
• 62: ZANIOLO, C. AND SADRI, R. 1994. A simple model for active rules and their behaviour in deductive databases. In Workshop on Deductive Database and Logic Programming (ICLP '94) (Santa Margherita Ligure, Italy), 13-26.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics

  H. Information Systems
  H.2 DATABASE MANAGEMENT

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Languages, Theory

Keywords:
active database systems, database rule processing, events, fixpoint semantics, rules, semantics