Transcript slides - UCLA Computer Science

CS240A: Databases and Knowledge Bases
Applications of Active Database
Carlo Zaniolo
Notes From Ch 3 of Advanced
Database Systems by Zaniolo,
Department of Computer Science
Ceri, Faloutsos, Snodgrass,
University of California, Los Angeles
Subrahmanian and Zicari
Morgan Kaufmann, 1997
A Taxonomy of Active Rule Applications



Internal to the database:

Integrity constraint maintenance

Support of data derivation (including data replication).
Extended functionalities (used in many applications):

Workflow management systems

Version managers

Event tracking and logging

Security administration
Business Rules (application specific):

Trading rules for the bond market

Warehouse and inventory management

Energy management rules
Internal VS Extended Rules

Perform classical DBMS functions

Can be approached with structured approaches
and techniques

Can be automatically or semiautomatically
generated

Can be declaratively specified
Declarative Design of Active Rules
for Integrity and View Maintenance


Internal applications of active databases are:

Static

Declarative

Highlevel, easy to understand
Approach

User specifies application at declarative (high) level

System derives lowlevel rules that implement it
 automatically
 or
semiautomatically
Framework

Rules should be programmed by DBA

Rule programming should be assisted by rule
design tools

Rule derivation can be:

Completely automatic (for few welldefined problems)
 Partially
users
automatic—requiring some interaction with
Integrity Constraint Maintenance


Constraints are static conditions

Every employee's department exists

Every employee's salary is between 30 and 100
Rules monitor dynamic database changes to enforce constraints

when change to employees or departments
if an employee's department doesn't exist
then fix the constraint

when change to employee salaries
if a salary is not between 30 and 100
then fix the constraint

Generalizing:

when potentially invalidating operations

if constraint violated

then fix it
IntegrityPreserving Rules
Constraint: condition C

Rules(s):
when operations that could
make C become false
if C is false
then make C true
or abort transaction
Example:
C = every employee's
department must exist
Operations = insert into emp,
delete from dept,
update to emp.deptno,
update to dept.dno

Condition:


There is some employee
violating C (due to those ops)
Action: make C true

Rollback insertion of emp

Rollback deletion of dept

Put emp into a dummy dept
Example: Referential Integrity

Constraint:

Abort Rules
EXISTS (SELECT *
CREATE RULE DeptEmp1 ON Emp
WHEN INSERTED,UPDATED(Deptno)
FROM Dept
IF EXISTS (SELECT * FROM Emp
WHERE Dno = Emp.Deptno)
WHERE NOT EXISTS
(SELECT * FROM Dept

Denial form:
WHERE Dno = Emp.DeptNo))
NOT EXISTS (SELECT *
THEN ROLLBACK
FROM Dept WHERE
Dno = Emp.Deptno)
CREATE RULE DeptEmp2 ON Dept
WHEN DELETED, UPDATED(Dno) IF
EXISTS (SELECT * FROM Emp
WHERE NOT EXISTS
(SELECT * FROM Dept WHERE
Dno = Emp.DeptNo)) THEN
ROLLBACK
Referential Integrity
using Repair Rules for EMP
CREATE RULE DeptEmp1 ON Emp
WHEN INSERTED
IF EXISTS ( SELECT * FROM INSERTED
WHERE NOT EXISTS
(SELECT * FROM Dept
WHERE Dno =Emp.DeptNo))
THEN UPDATE Emp
SET DeptNo = NULL
WHERE EmpNo IN
(SELECT EmpNo FROM INSERTED) AND
NOT EXISTS
(SELECT * FROM Dept
WHERE Dno = Emp.DeptNo))
Repair Rules for EMP (cont.)
CREATE RULE DeptEmp2 ON Emp
WHEN UPDATED(Deptno)
IF EXISTS (SELECT * FROM NEWUPDATED WHERE NOT
EXISTS
(SELECT * FROM Dept
WHERE Dno = Emp.DeptNo))
THEN UPDATE Emp
SET DeptNo = 99
WHERE EmpNo IN
(SELECT EmpNo FROM NEWUPDATED)
AND NOT EXISTS
(SELECT * FROM Dept
WHERE Dno = Emp.DeptNo))
Repair Rule for Dept

See Chapter 3 of ADS textbook
View Maintenance

Logical tables derived from base tables


Portion of database specified by retrieval query
Used to provide different abstraction levels---similar to external
schemas. Referenced in retrieval queries.
Virtual views


Not physically stored

Implemented by query modification
Materialized views


Physically stored

Kept consistent with base tablesee Chapter 2 of textbook
Virtual Views

Views define derived data by static database queries
Table highpaid = All employees with high salaries

Virtual views are not stored in the database

Rules dynamically detect queries on
virtual views and
transform into queries on base tables:
When retrieve from highpaid
then retrieve from emp
where sal > X
Materialized Views






Rules(s):
when operations happen that can change the result of Q
then modify V
How to generate rule(s) from view?
Generate triggering operations by analyzing Q
Example: V = all employees with high salaries
Ops =
insert into emp,
delete from emp,
update emp.sal
Generate action to modify V
1.
2.
3.
Evaluate query Q, set V = result
Evaluate Q using changed values, update V
Determine if you can use 2 or have to use 1 by analyzing Q
Materialized Views (cont.)
define view V as
select Cols from Tables
where Predicate

Materialized initially, stored in database

Refreshed at rule processing points
Changes to base tables => ViewMaintaining Rules

Recomputation approach (easy but bad)


when changes to base table then recompute view
Incremental approach (better but harder an not always applicable)

when changes to base tables then change view

Incremental rules is difficult in the presence of duplicates and certain
base table operations
Example


Relational view selecting departments with one or more employee
who earns more than 50,000
DEFINE VIEW HighPaidDept AS
(SELECT DISTINCT Dept.Name
FROM Dept, Emp
WHERE Dept.Dno = Emp.Deptno
AND Emp.Sal > 50K)
Critical events
1.
2.
3.
4.
5.
6.
7.
insertions into Emp
insertions into Dept
deletions from Emp
deletions from Dept
updates to Emp.Deptno
updates toEmp.Sal
updates to Dept.Dno
Refresh Rules written in Starburst
CREATE RULE RefreshHighPaidDept1 ON Emp
WHEN INSERTED, DELETED, UPDATED(Deptno), UPDATED(Sal)
THEN DELETE * FROM HighPaidDept;
INSERT INTO HighPaidDept:
(SELECT DISTINCT Dept.Name FROM Dept, Emp
WHERE Dept.Dno = Emp.Deptno AND Emp.Sal > 50K)
CREATE RULE RefreshHighPaidDept2 ON Dept
WHEN INSERTED, DELETED, UPDATED(Dno)
THEN DELETE * FROM HighPaidDept;
INSERT INTO HighPaidDept:
(SELECT DISTINCT Dept.Name
FROM Dept, Emp
WHERE Dept.Dno = Emp.Deptno
AND Emp.Sal > 50K)
_______________________________________
Dept and Emp are switched in the ADS book
Incremental Refresh Rules

Incremental refresh rule for Insert on Dept:
CREATE RULE IncrRefreshHighPaidDept1 ON Dept
WHEN INSERTED
THEN INSERT INTO HighPaidDept:
(SELECT DISTINCT Dept.Name
FROM INSERTED, Emp
WHERE INSERTED.Dno = Emp.Deptno
AND Emp.Sal > 50K)

This rule is not needed if there is a FK constraint from Emp to Dept

Incremental refresh rules for Insert on Emp ?

Incremental refresh rules for Delete on Dept?

Incremental refresh rules for Delete on Emp ?
Replication
 A special case of data derivation (identical copies).


Main application: distributed systems (copies on different
servers).
Typical approach: asynchronous.

Capture Step: Active rules react to changes on one copy and
collect changes into deltas.

Apply step: Deltas are propagated to other copies at the
appropriate time.
Alternatives:


PrimarySecondary

Symmetric
Conclusion

Active rules are now used primarily for integrity
constraint maintenance

Special constructs are now available in SQL:2003
for concrete views and replication
 Active
rules still have an edge on delta maintenance

For more complex applications active rules have
proven to be impractical—the XCON experience.

Attempts to improve situation (e.g., Chimera have
produced little benefits)
Limitations of Active Rules:
according to Stottler Henke - Artificial Intelligence History
Early to mid 1980sA succession of early expert systems were built and put in use by
companies. Including:
 a hydrostatic and rotary bacteria-killing cooker diagnosis program at Campbell's Soup based
on Aldo Cimino's knowledge;
 a lathe and grinder diagnosis analyzer at GM's Saginaw plant using Charlie Amble's skills at
listening for problems based on sounds;
 a mineral prospecting expert system called PROSPECTOR that found a molybdenum deposit;
 a Bell system that analyzed problems in telephone networks, and recommended solutions;
 FOLIO, an investment portfolio advisor; and WILLARD, a forecaster of large thunderstorms.
AI groups were formed in many large companies to develop expert systems. Venture capitalists
started investing in AI startups, and noted academics joined some of these companies. 1986
sales of AI-based hardware and software were $425 million. Much of the new business were
developing specialized hardware (e.g., LISP computers) and software (e.g., expert system
shells sold by Teknowledge, Intellicorp, and Inference) to help build better and less expensive
expert systemsRule-based expert systems start to show limits to their commercially viable
size.
1987 Circa: XCON, the Digital Equipment Company expert system had reached about 10,000
rules, and was increasingly expensive to maintain. Reasons for these limits include:

As new rules are added to expert systems, it becomes increasingly difficult to decide
the order in which active rules ought to be acted upon. Unexpected effects may occur
as new rules are added!
Active Rule Experience

Inflexibility of these expert systems in applying rules, and the tunnel vision implied in their
limited knowledge, that can result in poor conclusions…difficulties with "non-monotonic"
reasoning.

Rule-based expert systems couldn't draw conclusions from similar past cases. Such
analogical reasoning is a common method used by humans.

Expert systems don't know what they don't know, and might therefore provide wrong
answers to questions with answers outside their knowledge. This behavior is called
"brittleness."

Expert systems can't share their knowledge

Expert systems can't learn, that is, they can't establish correspondence and analogies
between objects and classes of objects.
It was gradually realized that expert systems are limited to "any problem that can be and
frequently is solved by your in-house expert in a 10 to 30 minute phone call," as
expressed by Morris W. Firebaugh at the University of Wisconsin.
These problems are only partially related to the fact that AI applications seek very advanced
functionalities. Problems such as difficulty to predict and manage rule behavior also
appear in databases dealing with much fewer active rules.