An Overview of Production Rules in Database Systems
---
paper_title: Supporting Semantic Rules by a Generalized Event/Trigger Mechanism

paper_content:

Non-standard applications like CAD/CAM, image processing and AI require database systems with facilities to handle sophisticated semantics. Advanced data models supporting complexly structured objects, abstract data types and the like have been developed to this end. However, any data model remains necessarily restricted to rather static and global semantics, not taking into account individual and dynamically changing issues. It is therefore necessary to formulate additional semantic rules, which may be rather complex and pose a variety of checking as well as enforcement requirements.
---
paper_title: A Model for Active Object Oriented Databases

paper_content:

This paper presents a logical model for an active object oriented dntahaae. The main idea is to use standard concepts of OODB such aa encapsulation and inheritance, In particular triggers are special met,hods encapsulated in the appropriate object. The execution model uses nested transactions. The model is shown to he flexihle and to generalize previous proposals,
---
paper_title: Rule Management in Object Oriented Databases: A Uniform Approach

paper_content:

Rules have been proposed for providing active behaviour in DBMS. Previous attempts to add rules to Object Oriented DBs have often resulted in a dichotomy between rules and other kind of objects. Bere a uniform approach is presented, in which rules are described and handled in the same way as any other object in the system, without any additional mechanisms being introduced. Thus rules can be related to other objects or arranged in hierarchies, and rules can even be defined which are triggered by methods attached to rules themselves. Since rules and classes are both objects, a relationship between these two kinds of objects can be used to provide a class-based index for rules. In this way, the search for applicable rules is considerably reduced. An early implementation and several examples are shown in ADAM, an Object Oriented DB in PROLOG.
---
paper_title: The HiPAC project: combining active databases and timing constraints

paper_content:

The HiPAC (High Performance ACtive database system) project addresses two critical problems in time-constrained data management: the handling of timing constraints in databases, and the avoidance of wasteful polling through the use of situation-action rules that are an integral part of the database and are monitored by DBMS's condition monitor. A rich knowledge model provides the necessary primitives for definition of timing constraints, situation-action rules, and precipitating events. The execution model allows various coupling modes between transactions, situation evaluations and actions, and provides the framework for correct concurrent execution of transactions and triggered actions. Different approaches to scheduling of time-constrained tasks and transactions are explored and an architecture is being designed with special emphasis on the interaction of the time-constrained, active DBMS and the operating system. Performance models are developed to evaluate the various design alternatives.
---
paper_title: The architecture of an active database management system

paper_content:

The HiPAC project is investigating active, time-constrained database management. An active DBMS is one which automatically executes specified actions when specified conditions arise. HiPAC has proposed Event-Condition-Action (ECA) rules as a formalism for active database capabilities. We have also developed an execution model that specifies how these rules are processed in the context of database transactions. The additional functionality provided by ECA rules makes new demands on the design of an active DBMS. In this paper we propose an architecture for an active DBMS that supports ECA rules. This architecture provides new forms of interaction, in support of ECA rules, between application programs and the DBMS. This leads to a new paradigm for constructing database applications.
---
paper_title: Alert: An Architecture for Transforming a Passive DBMS into an Active DBMS

paper_content:

Alert is an extension architecture designed for transforming a passive SQL DBMS into. an active DBMS. The salient features of the design of Alert are reusing, to the extent possible, the passive DBMS technology, and making minimal changes to the language and implementation of the passive DBMS. Alert provides a layered architecture that allows the semantics of a variety of production rule languages to be supported on top. Rules may be specified on userdefined as well as built-in operations. Both synchronous and asynchronous event, monit,oring are possible. This paper presents the design of Alert and its implementation in the Starburst extensible DBMS.
---
paper_title: Compiling complex database transition triggers

paper_content:

This paper presents a language for specifying database updates, queries and rule triggers, and describes how triggers can be compiled into an efficient mechanism. The rule language allows specification of both state and transition constraints as special cases, but is more general than either. The implementation we describe compiles rules and updates independently of each other. Thus rules can be added or deleted without recompiling any update program and vice versa.
---
paper_title: Set-oriented production rules in relational database systems

paper_content:

We propose incorporating a production rules facility into a relational database system. Such a facility allows definition of database operations that are automatically executed whenever certain conditions are met. In keeping with the set-oriented approach of relational data manipulation languages, our production rules are also set-oriented—they are triggered by sets of changes to the database and may perform sets of changes. The condition and action parts of our production rules may refer to the current state of the database as well as to the sets of changes triggering the rules. We define a syntax for production rule definition as an extension to SQL. A model of system behavior is used to give an exact semantics for production rule execution, taking into account externally-generated operations, self-triggering rules, and simultaneous triggering of multiple rules.
---
paper_title: Logic Programming and Databases

paper_content:

This book presents a systematic overview of the interaction between logic programming and database systems. Merging these two technologies permits new types of systems which extend the frontiers of computer science and open up new applications, such as deductive databases, knowledge base management systems, and expert database systems. The book opens with an overview and an introductory review, then is divided into three parts devoted to - the coupling of Prolog with relational databases, - the precise definition of the Datalog language, and - the description of query optimization techniques and extensions of Datalog. A closing chapter reviews the main projects on the integration of logic programming and databases, including LDL, Nail! and the Fifth Generation Project. The presentation achieves a balance between theoretical and technological issues, by providing a careful introduction to the underlying paradigms and their theoretical foundations, and by stressing the problems involved in achieving efficiency when interfacing logic programming formalisms with large databases. The book is thus suited for members of both the database and logic programming communities. The authors use a tutorial style complete with examples and exercises to introduce students as well as researchers to this developing field.
---
paper_title: Active Databases as a Paradigm for Enhanced Computing Environments

paper_content:

Abstract : Active databases emphasize the notion that a body of information is dynamic and should respond intelligently and in non-trivial ways to the user. It provides a paradigm for research and development which combines aspects of both databases and artificial intelligence technologies. A prototype system has shown the viability of this approach. The author focuses on the following database issues : (1) Descriptions are used as semantic templates for associatively accessing and manipulating data objects; (2) Dynamic views minimize the typical distinctions between queries and retrievals, and between views and real data, and thereby increase the perceived immediacy of the user interface; and (3) Constraint Equations are developed as a declarative representation for semantic constraints. The uniform approach they provide for expressing database integrity, consistency, and more general semantics derives its power from the rule-based framework of recent A.I. expert systems. The efficiency of constraint maintenance also is considered. Lastly, (4) The notion of binding time of data associations and reference is discussed relative to both the choice of data model and to the method of data access. (Author)
---
paper_title: Implementing large production systems in a DBMS environment: concepts and algorithms

paper_content:

It has been widely recognized that many future database applications, including engineering processes, manufacturing and communications, will require some kind of rule based reasoning. In this paper we study methods for storing and manipulating large rule bases using relational database management systems. First, we provide a matching algorithm which can be used to efficiently identify applicable rules. The second contribution of this paper, is our proposal for concurrent execution strategies which surpass, in terms of performance, the sequential OPS5 execution algorithm. The proposed method is fully parallelizable, which makes its use even more attractive, as it can be used in parallel computing environments.
---
paper_title: On the Coupling of a Production System Shell and a DBMS.

paper_content:

This paper investigates strategies for building very large knowledge-based systems (KBSs). We assert that a DBMS can perform knowledge-based reasoning in addition to its other tasks. Specifically, we prove that OPS5 (chosen as a representative of KBSs) can be emulated by QBE. The creation of KBSs using a DBMS as an infrastructure may supply immediate solutions to many problems of current KBS environments, such as too large fact and/or rule bases to enable strictly main memory processing, recovery, concurrency control, etc. A potential drawback of the DBMS-based implementation is a reduced performance. A solution to this problem would be demonstrated by a working system whose performance would be similar to that of other implementations. As a step toward this goal, we describe suggestions for performance improvements.
---
paper_title: Behavior of database production rules: termination, confluence, and observable determinism

paper_content:

Static analysis methods are given for determining whether arbitrary sets of database production rules are (1) guaranteed to terminate; (2) guaranteed to produce a unique final database state; (3) guaranteed to produce a unique stream of observable actions. When the analysis determines that one of these properties is not guaranteed, it isolates the rules responsible for the problem and determines criteria that, if satisfied, guarantee the property. The analysis methods are presented in the context of the Starburst Rule System; they will form the basis of an interactive development environment for Starburst rule programmers.
---
paper_title: Making deductive databases a practical technology: a step forward

paper_content:

Deductive databases provide a formal framework to study rule-based query languages that are extensions of first-order logic. However, deductive database languages and their current implementations do not seem appropriate for improving the development of real applications or even sample of them. Our goal is to make deductive database technology practical. The design and implementation of the RDL1 system, presented in this paper, constitute a step toward this goal. Our approach is based on the integration of a production rule language within a relational database system, the development of a rule-based programming environment and the support of system extensibility using Abstract Data Types. We discuss important practical experience gained during the implementation of the system. Also, comparisons with related work such as LDL, STARBURST and POSTGRES are given.
---
paper_title: A production rule based approach to deductive databases

paper_content:

The authors consider the problem of integrating a powerful production rule language, called RDLI, with a relational DBMS. A rule in RDLI is composed of a condition part which is a relational calculus expression and an action part which is a sequence of updates over a database. The semantics of a RDLI rule is presented according to a binary relation over databases states. Then, they introduce a general compilation technique for transforming producing rules in an execution model, the PCN, based on predicate transition networks (PrTN). The features of this model are its descriptive power and its query optimization support. >
---
paper_title: On rules, procedure, caching and views in data base systems

paper_content:

This paper demonstrates that a simple rule system can be constructed that supports a more powerful view system than available in current commercial systems. Not only can views be specified by using rules but also special semantics for resolving ambiguous view updates are simply additional rules. Moreover, procedural data types as proposed in POSTGRES are also efficiently simulated by the same rules system. Lastly, caching of the action part of certain rules is a possible performance enhancement and can be applied to materialize views as well as to cache procedural data items. Hence, we conclude that a rule system is a fundamental concept in a next generation DBMS, and it subsumes both views and procedures as special cases.
---
paper_title: A Model for Active Object Oriented Databases

paper_content:

This paper presents a logical model for an active object oriented dntahaae. The main idea is to use standard concepts of OODB such aa encapsulation and inheritance, In particular triggers are special met,hods encapsulated in the appropriate object. The execution model uses nested transactions. The model is shown to he flexihle and to generalize previous proposals,
---
paper_title: On rules, procedure, caching and views in data base systems

paper_content:

This paper demonstrates that a simple rule system can be constructed that supports a more powerful view system than available in current commercial systems. Not only can views be specified by using rules but also special semantics for resolving ambiguous view updates are simply additional rules. Moreover, procedural data types as proposed in POSTGRES are also efficiently simulated by the same rules system. Lastly, caching of the action part of certain rules is a possible performance enhancement and can be applied to materialize views as well as to cache procedural data items. Hence, we conclude that a rule system is a fundamental concept in a next generation DBMS, and it subsumes both views and procedures as special cases.
---
paper_title: A predicate matching algorithm for database rule systems

paper_content:

Forward-chaining rule systems must test each newly asserted fact against a collection of predicates to find those rules that match the fact. Expert system rule engines use a simple combination of hashing and sequential search for this matching. We introduce an algorithm for finding the matching predicates that is more efficient than the standard algorithm when the number of predicates is large. We focus on equality and inequality predicates on totally ordered domains. This algorithm is well-suited for database rule systems, where predicate-testing speed is critical. A key component of the algorithm is the interval binary search tree (IBS-tree). The IBS-tree is designed to allow efficient retrieval of all intervals (e.g. range predicates) that overlap a point, while allowing dynamic insertion and deletion of intervals. The algorithm could also be used to improve the performance of forward-chaining inference engines for large expert systems applications.
---
paper_title: Rule condition testing and action execution in Ariel

paper_content:

This paper describes testing of rule conditions and execution of rule actions in Ariel active DBMS. The Ariel rule system is tightly coupled with query and update processing. Ariel rules can have conditions based on a mix of patterns, events, and transitions. For testing rule conditions, Ariel makes use of a discrimination network composed of a special data structure for testing single-relation selection conditions efficiently, and a modified version of the TREAT algorithm, called A-TREAT, for testing join conditions. The key modification to TREAT (which could also be used in the Rete algorithm) is the use of virtual α-memory nodes which save storage since they contain only the predicate associated with the memory node instead of copies of data matching the predicate. The rule-action executor in Ariel binds the data matching a rule's condition to the action of the rule at rule fire time, and executes the rule action using the query processor.
---
paper_title: A declarative approach to active databases

paper_content:

A general description is provided of the field of active databases, focusing on the main problems yet to be solved. The author suggests that deductive databases may contribute to the understanding of some of these problems. Classes of applications that can be specified in a declarative manner are indicated. Important classes of active database applications can have a declarative interface supporting the designer during rule generation, resulting in collections of rules with an efficient and well-understood behavior. >
---
paper_title: Deriving Production Rules for Constraint Maintenance

paper_content:

Traditionally, integrity constraints in database systems are maintained either by rolling back any transaction that produces an inconsistent state or by disallowing or modifying operations that may produce an inconsistent state. An alternative approach is to provide automatic "repair" of inconsistent states using production rules. For each constraint, a production rule is used to detect constraint violation and to initiate database operations that restore consistency. We describe an SQL-based language for defining integrity constraints and a framework for translating these constraints into constraint-maintaining production rules. Some parts of the translation are automatic while other parts require user intervention. Based on the semantics of our set-oriented production rules language and under certain assumptions, we prove that at the end of each transaction the rules are guaranteed to produce a state satisfying all defined constraints. We apply our approach to a good-sized example.
---
paper_title: Deriving Production Rules for Incremental View Maintenance

paper_content:

It is widely recognized that production rules in database systems can be used to automatically maintain derived data such as views. However, writing a correct set of rules for effciently maintaining a given view can be a diffcult and ad-hoc process. We provide a facility whereby a user defines a view as an SQL select expression, from which the system automatically derives set-oriented production rules that maintain a materialization of that view. The maintenance rules are triggered by operations on the view's base tables. Generally, the rules perform incremental maintenance: the materialized view is modified according to the sets of changes made to the base tables, which are accessible through logical tables provided by the rule language. However, for some operations substantial recomputation may be required. We give algorithms that, based on key information, perform syntactic analysis on a view definition to determine when effcient maintenance is possible.
---
paper_title: Logic Programming and Databases

paper_content:

This book presents a systematic overview of the interaction between logic programming and database systems. Merging these two technologies permits new types of systems which extend the frontiers of computer science and open up new applications, such as deductive databases, knowledge base management systems, and expert database systems. The book opens with an overview and an introductory review, then is divided into three parts devoted to - the coupling of Prolog with relational databases, - the precise definition of the Datalog language, and - the description of query optimization techniques and extensions of Datalog. A closing chapter reviews the main projects on the integration of logic programming and databases, including LDL, Nail! and the Fifth Generation Project. The presentation achieves a balance between theoretical and technological issues, by providing a careful introduction to the underlying paradigms and their theoretical foundations, and by stressing the problems involved in achieving efficiency when interfacing logic programming formalisms with large databases. The book is thus suited for members of both the database and logic programming communities. The authors use a tutorial style complete with examples and exercises to introduce students as well as researchers to this developing field.
---
paper_title: A declarative approach to active databases

paper_content:

A general description is provided of the field of active databases, focusing on the main problems yet to be solved. The author suggests that deductive databases may contribute to the understanding of some of these problems. Classes of applications that can be specified in a declarative manner are indicated. Important classes of active database applications can have a declarative interface supporting the designer during rule generation, resulting in collections of rules with an efficient and well-understood behavior. >
---

Title: An Overview of Production Rules in Database Systems

Section 1: Introduction
Description 1: Introduce the concept of production rules in database systems, their significance in transforming passive systems into active ones, and the broad capabilities they offer.

Section 2: Preliminaries
Description 2: Introduce basic concepts and terminology essential for understanding active database systems, covering both relational and object-oriented database models.

Section 3: Database Rule Languages
Description 3: Discuss the design considerations for database production rule languages, including event specification, condition specification, action specification, and event-condition-action binding.

Section 4: Event Specification
Description 4: Describe different types of triggering events for rules in database systems, including data modification events, data retrieval events, timing events, and composite events.

Section 5: Condition Specification
Description 5: Explain how conditions in rules are specified across various systems and the support for transition conditions and referencing modified data.

Section 6: Action Specification
Description 6: Detail the operations specified in the action part of rules and the mechanisms for executing these actions.

Section 7: Event-Condition-Action Binding
Description 7: Outline the mechanisms for linking triggering events to conditions and actions, including parameter passing and referencing modified data.

Section 8: Rule Ordering
Description 8: Discuss conflict resolution strategies and ordering mechanisms provided by different active database systems.

Section 9: Rule Processing Semantics
Description 9: Describe the runtime rule processing semantics, including the recognize-act cycle, the handling of multiple triggered rules, and concurrency concerns.

Section 10: System-Specific Implementations
Description 10: Provide implementation details for active database systems including Ariel, HiPAC, Ode, POSTGRES, and Starburst, highlighting their unique approaches to architecture.

Section 11: Error Recovery
Description 11: Discuss mechanisms for handling errors during rule processing and the importance of transaction management and dependency tracking.

Section 12: Condition Testing
Description 12: Detail methods for efficiently testing rule conditions, including the A-TREAT algorithm used in Ariel.

Section 13: Action Execution
Description 13: Explain the approaches taken by various systems to bind triggering data to rule actions and execute these actions.

Section 14: Rule Programming Support
Description 14: Cover programming support features for rule developers, including rule creation, deletion, activation, querying, and limiting forward-chaining.

Section 15: Conclusions, Applications, and Future Directions
Description 15: Summarize the current state, applications, and future directions for active database systems, emphasizing the potential improvements and advanced applications they enable.