DerivingProductionRulesforConstraintMaintenance资源-CSDN文库

共1个文件

pdf：1个

数据挖掘

需积分: 3 7 浏览量 2008-06-13 08:04:26 上传评论收藏 134KB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

Deriving Production Rules for Constraint Maintenance.rar （1个子文件）

Deriving Production Rules for Constraint Maintenance.pdf 259KB

Proc. of 1990 VLDB Conference, pages 566{577

Deriving Pro duction Rules for Constraint Maintenance

Stefano Ceri



Jennifer Widom

IBM Almaden Research Center

650 Harry Road

San Jose, CA 95120

ceri@cs.stanford.edu, widom@ibm.com

Abstract.

Traditionally, integrity constraints in database

systems are maintained either by rolling back any transac-

tion that produces an inconsistent state or by disallowing

or mo difying operations that may produce an inconsistent

state. An alternative approach is to provide automatic e-

pair" of inconsistent states using production rules. For each

constraint, a pro duction rule is used to detect constraint

violation and to initiate database operations that restore

consistency.

We describe an SQL-based language for dening integrity

constraints and a framework for translating these constraints

into constraint-maintaining pro duction rules. Some parts of

the translation are automatic while other parts require user

intervention. Based on the semantics of our set-oriented pro-

duction rules language and under certain assumptions, we

prove that at the end of each transaction the rules are guar-

anteed to produce a state satisfying all dened constraints.

We apply our approach to a go od-sized example.

1 Intro duction

In database systems, an

integrity constraints

facility

permits logical specication of those database states

that are considered acceptable, or

consistent

. In cur-

rent systems, mechanisms for dening and enforcing in-

tegrity constraints are limited. Most relational database

systems support only sp ecic types of constraints, such

as uniqueness of keys and referential integrity, rather

than supp orting arbitrary predicates. Furthermore,

when constraints are violated, epair" of the database

state usually is limited to xed reversal actions, such as

rolling back the current op eration or the entire transac-

tion. (Consequently, for increased exibility, integrity

constraints often are enco ded within applications, usu-

ally in an ad-ho c manner.) An improved approach to

constraint enforcement allows denition of compensat-

ing actions that correct violation of each constraint ac-

cording to a well-understoo d, application-dependent se-

mantics.

Most research in the area of integrity constraints has

focused on eciently determining actual or potential



On leave from University of Modena

constraint violation, sometimes considering quite gen-

eral constraints (such as arbitrary predicates). In this

paper, we also consider general constraints, but we fo-

cus on the issue of constraint enforcement. A lan-

guage is prop osed for sp ecifying constraints on relational

databases. We then provide a framework for translat-

ing constraint specications into

production rules

that

maintain the constraints. Pro duction rules in database

systems allow sp ecication of data manipulation opera-

tions that are automatically executed whenever certain

events o ccur and/or certain conditions are met [DE89,

Han89,KdMS90, SJGP90, WF90]. The usefulness of in-

corporating pro duction rules into database systems is

well accepted [EC75, MD89, Mor83], particularly in the

context of constraint enforcement. However, we know of

no automatic (or semi-automatic) method for specifying

general constraints in a high-level, non-pro cedural lan-

guage, then deriving lower-level production rules that

maintain the constraints. We describe such a method.

The constraint and rule languages we use are based

on an extended version of SQL [HFLP89, IBM88], al-

though our work could easily be adapted for alternate

languages. Constraints are expressed as predicates over

the database state: if the predicate is true in a partic-

ular state, then the constraint is

violated

and the state

inconsistent

Constraints may b e ordered, sp ecify-

ing that certain constraints will be enforced earlier than

(and therefore may b e assumed valid by) other con-

straints. The pro duction rule language is describ ed in

[WF90]. Prior familiarity with this rule language is not

necessary; an overview is provided.

Production rules enforce constraints by issuing ac-

tions to correct violation. In many cases, several p ossi-

ble actions may correct a given constraint violation, and

which action is most appropriate may depend on the ap-

plication. Thus, for each constraint, the compensating

actions are specied by the application designer. How-

ever, several other necessary comp onents of the deriva-

tion can be performed automatically. We envision an

interactive system for deriving rules from constraints

with a structure as illustrated in Fig. 1. The automatic

portions of the derivation include:



Producing

rule templates

from constraints: Rule

templates enumerate all op erations that may cause

constraint violation (these form the triggering com-

For our framework, it is more convenient for constraints

to sp ecify the inconsistent rather than the consistent states.

This choice does not aect expressiveness, since the alter-

native semantics can b e achieved simply by negating each

constraint.

Constraints Editor (User)

Constraint Denitions

Rule Template Generator (System)

Rule Templates

Rules Editor (User)

Preliminary Rules Potential Cycles

Rule-Set Analyzer (System)

Final Rules

Rule Optimizer (System)

Optimized Rules



Figure 1:

Interactive System for Rule Derivation

ponents of the constraint-enforcing rules) and in-

clude rule conditions. Rule actions are provided by

the user.



Detecting p otential cycles in rule activation: As the

number of rules increases and rules become more

complex, there is increasing possibility of innite

triggering behavior. This component detects the

potential for such behavior and provides warnings

to the user.



Rule optimization: The system automatically op-

timizes rules derived from constraints, preserving

their constraint-maintaining semantics.

Each automatic comp onent is described in some de-

tail. We also describe those tasks that must be per-

formed by the users of the system. Finally, a theorem is

proven stating that under certain assumptions regarding

the users' obligations (such as correctness of comp ensat-

ing actions and nite triggering behavior), the nal set

of pro duction rules is guaranteed to maintain all dened

constraints. That is, at the end of every transaction,

rule execution terminates in a consistent state.

1.1 Related Work

As mentioned ab ove, most work involving integrity con-

straints in database systems has addressed|in a va-

riety of settings|the problem of eciently detecting

constraint violation [BBC80,HMN84,HI85,KP81,Nic82,

QS87,Sto75]. Some of this work describes algorithms for

detecting in advance that an op eration may cause con-

straint violation; such operations are not permitted to

proceed. In other work, inconsistent states are detected

as they occur; consistency is restored by p erforming

undo or rollback operations. In our approach, inconsis-

tent states may occur and are detected, but consistency

is restored by issuing corrective actions that dep end on

the particular constraint violation.

Approaches similar to ours are taken in [CTF88,

Mor84, UD90, UD91], but in restricted settings. In

[CTF88], only referential integrity and inclusion depen-

dency constraints are considered. The user may dene

compensating actions (drawn from a restricted set) to

be executed when constraints are violated. In [Mor84],

the focus is on a very high-level language for express-

ing inter-relational constraints. The set of expressible

constraints is a subset of those expressible using arbi-

trary predicates. In many cases, sp ecic comp ensating

actions may be derived automatically from constraints,

sub ject to certain \hints" provided by the constraint

dener. In [UD90,UD91], analysis of constraints is con-

sidered in an ob ject-oriented environment. Constraints

are represented using Horn logic (again permitting only

a subset of arbitrary predicates). Constraint analysis re-

veals the eects of constraints on ob ject manipulation,

determines p ossible constraint violations, and suggests

propagation actions for correcting violations.

Several other papers also extend the standard ap-

proaches to constraint denition and enforcement. In

[CG88], logic programming is used to express and eval-

uate constraints. At run-time, a given transaction can

be checked to verify that it will maintain consistency

with resp ect to a set of constraints. If consistency

is not guaranteed, the system can explain which con-

straints are violated and can suggest comp ensating ac-

tions. A similar approach is describ ed in [SMS87], how-

ever this work considers a compile-time rather than run-

time environment. When transactions are determined

to have potential for constraint violation, feedback is

provided to the user in the form of suggested tests and

updates to be added to the transaction. In [Wal89],

constraint denitions include both conditions on the

state (which are checked) and additional actions that

are automatically executed after certain op erations to

help maintain consistency. This is similar to dening

constraints directly as the rules that enforce them, as

in [SK84]. In our approach, constraints are dened at

a higher, non-pro cedural level, from which constraint-

maintaining rules are derived.

1.2 Outline of Paper

Preliminary material is presented in Section 2: a case

study is introduced, serving as a source of examples

throughout the pap er, and an overview of the rule lan-

guage is given. Section 3 presents the syntax and se-

mantics of the constraint language. Section 4 describes

the derivation of a rule for enforcing a single constraint,

including automatic generation of those op erations that

may cause constraint violation. Section 5 then consid-

ers the set of rules for maintaining multiple constraints;

in particular, it shows how p otential cyclic b ehavior in

such rule sets can be detected. Rule optimization is

covered in Section 6. Section 7 considers system execu-

tion, showing that termination in a consistent state is

guaranteed under certain assumptions. Finally, in Sec-

tion 8, we conclude, discuss general use of the facility,

and describe future work.

2 Preliminaries

2.1 Case Study

Examples throughout the paper are drawn from a case

study concerning a

Power Distribution Design System

, a

database application supp orting the design and mainte-

nance of electricity networks.

Due to space limitations,

only p ortions of the study are included in this pap er; all

details appear in the technical report [CW90]. Note that

many of the constraints considered in the study cannot

be supp orted in conventional database systems.

Briey, a power network connects a collection of

plants

to a collection of

users

, p ossibly through inter-

mediate

nodes

. The network designer determines the

location of plants, no des, and users. Also specied by

the designer is the power pro duced by each plant, the

power required by each user, and the p ower loss incurred

at each intermediate node. The designer places directed

wires

between plants, users, and no des, sp ecifying for

each the

wire type

along with the

voltage

and

power

be carried by that wire.

Multiple wires may be placed between any two points,

and each set of wires is enclosed within a

tube

. Place-

ment of tubes is not dicult: there is at most one

tube between any two points, a tub e should be

pro-

tected

if it contains high voltage wires, and tub es should

have large enough

cross sections

to enclose their wires.

Tub e placement can, in fact, be specied solely in terms

of constraints|tubes are then automatically inserted

and deleted by the rules that maintain the constraints.

Thus, once appropriate constraints are dened, the de-

signer need not consider tubes at all.

Further constraints specify that the power output re-

quired for each plant should not exceed the produced

power, the power output required for each no de should

not exceed the deliverable p ower (based on input), and

each user should receive at least its required p ower. For

reliability, each user should be connected to at least two

plants. Using capitalization to denote primary keys, the

relational schema for the case study is:

plant(PLANT-ID, location, power)

user(USER-ID, location, power)

node(NODE-ID, location, loss)

wire(WIRE-ID, fr, to, type, voltage, power)

tube(TUBE-ID, fr, to, type)

wire-type(TYPE, max-voltage, max-power

cross-section)

tube-type(TYPE, protected, cross-section)

ID's for plants, users, and nodes all are drawn from the

same domain|a constraint will specify that these are

not duplicated. Attributes

and

of tables

wire

and

tube

take their values from this domain.

2.2 Production Rules

We provide a brief overview of the set-oriented, SQL-

based production rules language used in the remainder

of the pap er. Further details and numerous examples

This problem was presented to author Ceri by L. Dalle

in the context of a joint study between

ENEL

|the Italian

Electric Energy Agency|and the Politecnico di Milano.

appear in [WF90]. We consider a relational database

system with an integrated pro duction rules facility. The

system has all the usual database functionality; in addi-

tion, a set of pro duction rules may b e dened. In gen-

eral, production rules sp ecify actions to be performed

when certain events occur or conditions are met. In our

language, each rule contains three comp onents: a

tran-

sition predicate

, which controls rule triggering, a

condi-

tion

, which is checked b efore the rule may execute its

action

, which is a sequence of data manipulation oper-

ations or a rollback request. Production rules are not

activated until the commit point of each transaction, at

which time all triggered rules are considered. The data

manipulation op erations executed as part of a rule's ac-

tion may trigger additional rules. Once there are no

triggered rules left to consider, the transaction is com-

mitted. Further details follow.

Rules are based on the notion of

transitions

. A transi-

tion is a database state change resulting from execution

of a sequence of data manipulation operations. We con-

sider the

net eect

of transitions, meaning that: (1) if

a tuple is updated several times, we consider only the

composite up date; (2) if a tuple is up dated then deleted,

we consider only the deletion; (3) if a tuple is inserted

then up dated, we consider this as inserting the up dated

tuple; (4) if a tuple is inserted then deleted, it is not

considered at all.

The syntax for dening production rules is:

create rule

name

when

transition predicate

[

condition

]

then

action

A rule is

triggered

by a given transition when its

transition predicate

holds with resp ect to that tran-

sition. Transition predicates sp ecify operations on

particular tables and columns. The permitted forms

are:

inserted into t

deleted from t

, and

updated

t.c

, where

is a table name and

is a column of ta-

ble

. A transition predicate lists one or more such

specications, and the predicate holds with resp ect to a

transition if at least one of the specied op erations o c-

curred in the net eect of the transition. Once a rule is

triggered, it may b e chosen for evaluation (as describ ed

below). At this point, the rule's

condition

is checked|

rule conditions are arbitrary predicates on the database

state. If the condition is true, the

action

is executed.

An action may sp ecify a list of SQL data manipulation

operations to b e executed or it may request a rollback

of the current transaction.

The condition and action parts of a rule may refer

to the current state of the database through embedded

SQL

select

operations. In addition, these components

may refer to

transition tables

. A transition table is a log-

ical table reecting changes that have o ccurred during

a transition. At the end of a given transition, transition

table

inserted t

refers to those tuples of table

in the

current state that were inserted by the transition, tran-

sition table

deleted t

refers to those tuples of table

the pre-transition state that were deleted by the tran-

sition, transition table

old updated t

refers to those

tuples of table

in the pre-transition state for which

column

was updated by the transition, and transition

table

new updated t.c

refers to the current values of

the same tuples. Transition tables may be referenced

in the

from

clauses of

select

operations in the usual

way. As a restriction, a rule may only refer to those

transition tables corresp onding to its transition predi-

cate. For example, a rule may refer to

old updated

t.c

and

new updated t.c

only if

updated t.c

is in-

cluded in its transition predicate; similarly for

inserted

and

deleted

Finally, we describ e rule execution. First, a user or

application executes a transaction|a sequence of SQL

operations; rules are considered at the commit point of

the transaction. The state change resulting from this

initial transaction creates the rst relevant transition,

and some set of rules are triggered by this transition.

One rule is chosen from this set for evaluation. To in-

uence rule selection, rules may b e partially ordered,

whereby a rule will b e chosen such that no other trig-

gered rule is higher in the ordering. The condition part

of the selected rule is checked; if it does not hold, a new

triggered rule is selected for evaluation. If the rule's

condition does hold, its action is executed. (If no trig-

gered rule with a true condition is found, rule execution

terminates.) Let

(say) b e the rule whose action is

executed, and assume its action is not

rollback

. After

execution of

's action, all rules not previously evalu-

ated are now triggered only if their transition predicate

holds with respect to the composite transition created

by the initial transaction and subsequent execution of

's action. That is, these rules consider

's action as if

it were executed as part of the user-generated transac-

tion. Rules already evaluated have already \processed"

the initial transaction; thus, they are triggered again if

their transition predicate holds with resp ect to the tran-

sition created by

's action. Rule

will be triggered

a second time only if future rule execution produces a

new net eect satisfying its transition predicate.

Consider now an arbitrary p oint in rule processing.

A given rule is triggered if its transition predicate holds

with respect to the (comp osite) transition since the

point following its most recent execution. If, at last

evaluation, the rule's condition was found to be false,

then the rule is considered with resp ect to the transition

since that point of evaluation.

If a rule has not yet b een

evaluated, it is considered with respect to the transition

since the start of the initial transaction. One rule is cho-

sen from the set of triggered rules; if its condition holds,

its action is executed, otherwise another triggered rule

is selected. If a

rollback

action is encountered, the sys-

tem rolls back to the start of the initial user-generated

transaction and no rules are triggered. Otherwise, rule

processing terminates when the set of triggered rules is

empty or when no triggered rule has a true condition;

the entire transaction is then committed.

Here, we deviate somewhat from the semantics as pre-

sented in [WF90], where a rule is considered with resp ect to

the transition since b efore its last execution. It should b e

possible in the rule system to permit b oth interpretations.

3 Constraint Language

We dene a general language for expressing integrity

constraints. A constraint has two parts: a

table list

specifying tables relevant to the constraint, and an un-

restricted

SQL predicate

, which must hold in exactly

those states violating the constraint. As an introduc-

tory example, consider the constraint \each wire's volt-

age does not exceed the maximum for its wire type". In

the prop osed language, this is expressed as:

wire: voltage > any (select max-voltage

from wire-type

where type = wire.type)

(We must use \

> any

" here rather than the more natu-

ral \

" since the right side of the comparison is a single-

ton set, not a single value.) Remember that a constraint

species the inconsistent states. Thus, a state violates

this constraint if any tuple in table

wire

has a

voltage

exceeding the

max-voltage

for its wire

type

. A com-

plete syntax and semantics follows.

3.1 Syntax

A grammar for the constraint language is given in Fig. 2;

many examples are provided below. The core of the

language is a variation on the usual SQL syntax for

predicates, similar to that used in the

clause of our

production rules [WF90]. Several advanced features are

included, such as bo olean types, tuple constructors, and

user-dened functions. In [CW90], we also include

ta-

ble expressions

(as described with resp ect to the

Star-

burst

database system in [HFLP89]); space considera-

tions have forced their omission here. In the grammar's

productions, we use T

to denote table names, V

denote table variable names, and C

to denote column

names. Rep etition is represented explicitl y by enumer-

ating

terms (

n >

0). Optional terms are enclosed in

square brackets. (In our examples, we p ermit several

straightforward abbreviations to the syntax.)

3.2 Semantics

The semantics of our constraint language is straight-

forward: a constraint is violated in a state i one or

more tuples in the Cartesian pro duct of the listed ta-

bles satises the specied predicate. Constraints may b e

partially ordered: the user may sp ecify for any pair of

constraints that one constraint is to b e enforced before

the other (as long as there is no cycle in the prioriti-

zation). Constraint ordering allows the user to safely

assume that some higher priority constraint will be sat-

ised whenever some lower priority constraint is consid-

ered. For example, in the constraint \each wire's voltage

does not exceed the maximum for its wire type" (speci-

ed above), it is assumed that the constraint \each type

in the wire table app ears in the wire-type table" (spec-

ied b elow) already holds.

3.3 Examples

The referential integrity constraint \each type in the

wire table app ears in the wire-type table" is expressed:

wire: type not in (select type from wire-type)

评论收藏

内容反馈

morre

粉丝: 187
资源: 2336

Deriving Production Rules for Constraint Maintenance

APPROACH FOR DERIVING SCENARIOS FOR SAFETY OF THE INTENDED FUNCT

Letter Recognition Using Holland-Style Adaptive Classifiers

Deriving new business insights with Big Data Skill Level

ppx_deriving:OCaml的类型驱动代码生成

Intelligent Multimedia Systems

TuckER：Tensor Factorization for Knowledge Graph Completion.pdf

Variable Precision Rough Set and a Fuzzy Measure

Finite time convergent observers for linear time-varying systems

tabletest3:用于类表测试的单元测试模块，适用于Python 3

A simple atmospheric correction algorithm for MODIS in shallow turbid waters

deriving-yojson:将 ocaml 值解析为 yojson ast

Artificial.Intelligence.and.Soft.Computing.17th.International.Conference.Part.I

ppx_deriving_protobuf:用于OCaml的协议缓冲区编解码器生成器

deriving-aeson:取消手动滚动的aeon实例

NIST SP800-132.pdf

Deriving merchantable volume in poplar through non-destructive terrestrial laser scanning

Deriving OD matrix from Railway ticket records based on merge sort method

SM空间调制论文

A Mathematical Introduction to Robotic Manipulation.pdf

安卓期末大作业（AndroidStudio开发），垃圾分类助手app，分为前台后台，代码有注释，均能正常运行

Notepad++安装包

SwitchHosts

微信小程序源码-合集1.rar

2024北森能力测评题库.7z

ruoyi-vue-pro 芋道源码项目的表结构

jdk-11-windows-x64.zip

Java面试八股文2023最新版

ruoyi-vue-pro开发指南PDF下载

JDK1.8 windows 64位

最新资源