Transcript CS245A3

Active Databases
Active Database Systems
Ref: Modern Database Systems, Won Kim (ed), Addison
Wesley, 1994 (chapter 21).
Conventional databases are passive
Active databases


Monitor situations of interest
Trigger a timely response when the situations occur

E.g., Inventory control systems monitor the quantity in stock.
When the stock falls below a threshold, a reordering activity
may be initiated
Possible Implementations


Check inventory level periodically (not timely)
Check the semantics of the condition in every program that
updates the inventory database (poor software engineering
approach)
These methods are not general.
2
A General Approach (Active Databases)
Express the derived behavior in rules
(conditions ---> actions)


The rule can be shared by many application
programs
Implementation can be optimized
Contains an inference engine which:



Applies all the rules in the system
Matches the condition parts of the rules with the
data in the working memory
Selects and finds the rule that best matches the
conditions
3
A General Approach (Active Databases)
The action part of the rule may modify the
working memory, which may cause further
actions. The cycle continues until no more rules
match.
on
event
if
condition
then
action
Rules can be triggered by the following events:



Database operations
Occurrence of database status
Transitions between database status
4
Characteristics of Rules
Rules are:



Defined and stored in the database
Evaluated by the database system
Subject to:



Authorization
Concurrency control
Recovery
Rules can be used to:






Enforce integrity constraints
Implement triggers and actions
Maintain derived data
Enforce access constraints
Implement version control policies
Gather statistics for database reorganization
5
Rule Models And Languages
Rules are defined as metadata in the schema
together with table, view, and integrity
constraints.
Rules operations are provided to:



Add
Drop
Modify
Rules are structured objects with the components of:



Events
Conditions
Action
Special operations of rules are:



Fire (triggers a rule)
Enable (activates a rule)
Disable (deactivates a rule)
6
Triggering an event may be implicit or explicit.
Explicit: flexibility in expressing transactions.

e.g., Keep Bob and Alice’s salaries the same.


If Alice’s salary constraint changes, then change Bob’s too.
If Bob’s constraint is violated because of changes by the user transaction, then
abort the transaction.
Implicit: any change to the database that can cause the condition
to become true is treated as a triggering event.
Languages vary based on the complexity of specified events,
conditions, and actions.
7
Event Specification
Explicitly triggered by database modification
Relational database
define rule monitor new events
on insert to employer
if...
then...
where employer is a table of employee information
Object-Oriented Database
define rules check raises
on
employee salary raises
if...
then...
where salary raises are a method defined by our objects in an
employee class
8
Rules to be triggered by data retrieval:
define rule monitor sal access
on retrieve salary
from
employee
if...
then...
9
Temporal events
absolute (8:00 on January 1, 1994)
relative (5 seconds after take-off)
periodic (17:00 hour every Friday)
In object-oriented databases, events can be:
 generic database operations (retrieve, insert, delete, update)
 type-specific operations (method invocation)
 an operation on rule objects
 transaction operations
 external events (messages or signals from devices)
 a composition of events (disjunction, sequence, and repetition)
Events are defined to have formal parameters.
Salary-raise (e: employee, oldsal: integer, newsal: integer)
 e of type employee
 oldsal and newsal of type integer
10
Condition Specification
The condition is satisfied by a predicate or query over
data in the database.
The condition is satisfied if the predicate is true or if
the query returns a non-empty answer.
Rule condition are arbitrary predicates over database
status, thus modified data can be referenced and
transition conditions can be specified.
define rule
on update to
if
then...
monitor raise
employee.salary
employee.salary is > 1.1 old employee.salary
11
Action Specification
Action part of a rule usually performs:
 inserts
 deletes
 updates
Data in the working memory based on data matching
the rule’s condition
define rule
favor employee
or insert to employee
then deletes employee e where e.name = employee.name
Whenever a new employee is inserted, its action deletes any existing
employees with the same name.
Rule actions can also be:
 arbitrary database operations
 transaction operations
 rule operations
 signals for the occurrence of user-defined events
 calls to application procedures
12
Event-Condition-Action Binding
Database production rule language may have explicitly specific events.
There is a need to specify different and varied conditions and actions.
The motion of binding is different from Al production rules (e.g. triggering an event
of a rule may be parameterized and the parameters may be referenced in the rule’s
condition and action.)
e.g. If rule is triggered by salary. raise (e: employee; oldsal: integer;
newsal: integer),
then e in the condition or action refers to the employee object. Oldsal and newsal
refer to the intergers bound when events occurred.
Composite event allows events (eg. salary raise) to occur one or more times (set of
queries)
Rules can be triggered by insertions, deletions, and/or updates on a particular table.
For example:
Create trigger DepDel
before deletion on
department
when
department budget<100,000
delete
employee
where
employee.dno=department.dno
The rule is triggered before the deletion of a department. The condition
(where clause) and action refer to the department being deleted.
13
Key words, old and new, can also be used.
define rules
on append to
then delete
form new emps
employee
employee when employee.name = new.name
define rules
on update to
of
100
then
Ave Too Big
employee.salary
(select ave (salary) from new updated) >
rollback
Abort the transaction whenever the average of the update exceeds
100.
14
Rule Ordering
Choice of which rule to execute when more than one
has been triggered is made:



arbitrary
numeric priorities
partially ordered
For any 2 rules, one rule can be specified as having higher
priority than the other rule, but an ordering is not required.
In HiPAC, multiple trigger rules can be executed
concurrently.
The rules are relatively ordered for serialization
(concurrency control).
15
Rule Organization
In relational systems




Rules are defined in the schema
Rules refer to particular tables
Rules subject to the same controls as other meta data objects (e.g. views, constraints)
If a table dropped, all rules defined for it are no longer operative
In HiPAC (object oriented systems)




Rules are first class objects
Rules are organized in types like other objects
Rule types are participants in system hierarchies; they can have attributes in relation to
other objects
Rules can be included in collections which can be explicitly named or defined by
queries
r In Flight-rule Where Effective Date (r) After 1/1/90
+ Flight rule is rule type
+ Effective date is an attribute defined for this query
+ Collections of rules can be selectively activated or deactivated
by the enable or disable operation
16
Rule Execution Semantics
Rule behavior can be complex and unpredictable so a precise execution semantics is
important
Using an inference engine is not adequate in a database system
Active database system rule processing must integrate with conventional database
activities:
 Queries
 Modifications
 Transactions
which cause the rules to be triggered and initiate rule processing.
Granularity of rule processing
 Set of tuples
firing the rules after modifying each tuple or firing after modifying all the tuples
 Set of objects
firing the rule after the end of a transaction
Triggering of more than one rule by the same event
 Conflict resolution
Nested triggering (termination)
17
Error Recovery
Cause for generating an error during execution of database rule





Data has been deleted
Data access privileges have been revoked
Dead lock is created from concurrently executing transactions
System generates error
Rule action has uncovered an error condition
Error recovery techniques




Delete data and revoke access privilege, invalidating the corresponding
rules
Abort the current rule processing if error occurred
Propagate the failure to its parent which may initiate other subtransactions to repair the error
Handle error recovery during system crashes


For recoverable events, their occurrences and parameter bindings have to be
reliability logged
For the decoupled conditions and actions, restart uncommitted transactions
18
Implementation Issues
Active databases must provide mechanisms for
Event detection and rule triggering
Condition testing
Rule action execution
User development of rule applications
19
Characteristics Of
Representative Systems
ARIEL (build using the Exodus database tool kit) Curey
et.al.1991.
A rule manager/rule catalog for handling rule definition and
manipulation tasks.
A rule execution monitor for maintaining the set of triggered
rules and scheduling their execution.
A rule execution planner to produce optimized execution
strategy.
20
POSTGRES
Tuple level processing (run time approach)


Places a marker on each tuple for each rule that has a condition matching
that tuple
When a tuple is modified or retrieved



If a tuple has one or more marker on it, then the rule or rules associated with
the marker(s) are located and their actions are executed.
Marker installed when rules are created
Marker deleted when rules are deleted
Query rewrite (compiler time approach)

A module is added between command parser and the query processor to
intercept user command


Argument with additional commands reflecting the effect of rules (triggering
by the original command) which may trigger other rules
Recursively triggering may not terminate
Compiled time approach can be more efficient than runtime
approach
Select which mechanism to use when a rule is created
21
STARBURST (IBM Research, Hass et. al. 1990)
Extensibility
Use attachment feature to monitor data modification
that are of interest to the rules
Modifications are stored in a transaction log
Rules are processed at the end of a transaction or a
user command
Trigger rules are indexed according to the priorities
Reference to transition tables are implemented
Mechanisms are provided for concurrency control,
authorization, and crash recovery
22
HiPAC (An Object Oriented Database System), Dayal,
U. et al, 1988, SIGMOD Record, Vol. 17, No. 7, pp. 51-70
Rule manager



Coordinates rule processing
Stores rule objects
Implements operations



Implements the coupling modes of the execution model.
Concurrency control
Recovery for rule object
Event detector detects different events
Bi-directional interaction between application
programs and database rule system


Application can invoke database operations
Rules running inside the database can invoke application
operation
23
Rule Programming Support
Trace rule execution
Display the current set of trigger rules
Query and browse the set of rules
Cross reference rules and data
Activate and deactivate the selected rules for
processing the database transactions
24
Rule Termination
Impose sufficient syntactic restrictions on rule
definitions (limit the expressiveness of the rules)
Impose a rule triggering limit. The limit is specified
by the use or system default (needs to monitor the
number of rules executed during the rule processing).
Detect if the same rule is triggered a second time
with the same set of parameters
25
Future Directions
Support for application development



Application developments treat database rules as an
assembly language
Rules are generated automatically from high level
specifications
An increase in communication capabilities between
database rules and applications
Increasing expressive power of rules
Improved algorithms
Distribution and parallelism


Distribution and parallelism
Algorithms that guarantee equivalence with centralized
rule processing
26
Mediators In The Architecture Of Future
Information Systems
Reference: Gio Wiederhold, IEEE Computer
Magazine, March 1992, pp. 38-49.
27
28
29
Abstraction Functions
30
Mismatches in Data Resources
31
Knowledge and Data Feedback Loops
and Their Interaction
32
33
Mediators
A mediator is a software module that exploits encoded
knowledge about certain sets of subsets of data to
create information for a higher layer of applications.
Requirements:
small and simple
inspectable by potential users (for selection)
meta mediator (e.g., catalog list of mediators and
data resource)
Given a data source, locate a knowledgeable mediator;
for a desirable mediator, locate an adequate data
resource.
34
35
Mediator Interfaces
User’s workstation interface to the mediators
A language is needed to provide flexibility, composability,
iteration, and evaluation in this interface
Descriptive but static interface specification unable to support
the variety of control and information flow
The language should provide incremental growth and support
new functionality as additional mediator joins the network
Machine and communication friendly interfaces
Support high level functions for decision making
36
Three Layers of a Mediator Architecture
37
Interfaces for Information Flow
38
39
40
41
42
43
44
Interface of Mediator to the Database
Management Systems
SQL
RDA
SELECTION and VIEW are good starting points
A mediator combines information from multiple databases,
can use its knowledge to control the merging process,
specifying relational operations directly.
New access languages are needed to manage sensor-based
and simulation process (e.g., abstraction, fusion).
Mediator can create objects for a wide variety of
orthogonal views.
Making complex objects persistent.
45
Sharing Of Mediator Modules
Process tasks needed within a mediator:
selection, fusion, reduction, abstraction, and
generalization
effective use of mediator modules - sharing use for
different applications
e.g., mediator for inflation adjustment can be used by
many applications mediator understands postal codes
can be used by post offices, express delivery services,
and corporate mailrooms.
46
47
Distribution Of Mediators
Locality of maintenance
Economy for access
Autonomy
Reasons For Mediators Not Attached To DB:
Mediator contains knowledge beyond the scope of DB

e.g., factory production control system cannot expect to foresee all
the strategies used of the collected information
Concept of abstraction is not part of DB technology today
Intelligent processing data will involve dealing with
uncertainty
Mediator may access multiple DB and combine disjoint
sets of data prior to analysis and reduction
48
49
50
51
52
53
54
55
Active Infomediation Services
56
Layered Information Architecture & Processes
57