A denotational semantics for the Starburst production rule language

ABSTRACT

Researchers often complain that the behavior of database production rules is difficult to reason about and understand, due in part to the lack of formal declarative semantics. It has even been claimed that database production rule languages inherently cannot be given declarative semantics, in contrast to, e.g., deductive database rule languages. In this short paper we dispute this claim by giving a denotational semantics for the Starburst database production rule language.

REFERENCES

• 1: 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
• 2: Alexander Aiken , Jennifer Widom , Joseph M. Hellerstein, Behavior of database production rules: termination, confluence, and observable determinism, ACM SIGMOD Record, v.21 n.2, p.59-68, June 1, 1992
• 3: 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
• 4: Stefano Ceri , Georg Gottlob , Letizia Tanca, Logic programming and databases, Springer-Verlag New York, Inc., New York, NY, 1990
• 5: Umeshwar Dayal , Klaus R. Dittrich, Active Database Systems (Abstract), Proceedings of the 17th International Conference on Very Large Data Bases, p.209, September 03-06, 1991
• 6: E. N. Hanson, An initial report on the design of Ariel DBMS with an integrated production rule system, ACM SIGMOD Record, v.18 n.3, p.12-19, Sep. 1989 [doi>10.1145/71031.71033]
• 7: J. Roger Hindley , Jonathan P. Seldin, Introduction to combinators and &lgr;-calculus, Cambridge University Press, New York, NY, 1986
• 8: [HW92] E.N. Hanson and J. Widom. Rule processing in active database systems. In L. Delcambre and F. Petty, editors, Advances in Databases and Artificial Intelligence. JAI Press, Greenwich, Connecticut, 1992.
• 9: [KdMS92] J. Kiernan, C. de Maindreville, and E. Simon. Supporting deductive and active rules on top of a relational DBMS. Research report, INRIA, Le Chesnay, France, 1992.
• 10: 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
• 11: Louiqa Raschid , Jorge Lobo, Semantics for update rule programs and implementation in a relational database management system, University of Maryland at College Park, College Park, MD, 1991
• 12: [Sel89] T. Sellis, editor. Special lssue on Rule Management and Processing in Expert Database Systems, SIGMOD Record 18(3), September 1989.
• 13: 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
• 14: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 15: 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
• 16: 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

INDEX TERMS

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

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

General Terms:
Design, Languages, Management, Theory