S uc u ing he P ocess o In eg i y Main enance
(Ex ended Ve sion)
En ic Mayol
E nes Tenien e
Uni e si a Poli ècnica de Ca alunya
Facul a d'In o mà ica
Jo di Gi ona Salgado 1-3, Edi ici C6
E-08034 Ba celona - Ca alonia
e-mail: [mayol | enien e]@lsi.upc.es
Abs ac
Two di e en app oaches ha e been adi ionally conside ed o
dealing wi h he p ocess o in eg i y cons ain s en o cemen :
in eg i y checking and in eg i y main enance. Howe e , while
p e ious esea ch in he i s app oach has mainly add essed
e iciency issues, esea ch in he second app oach has been mainly
concen a ed in being able o gene a e all possible epai s ha
alsi y an in eg i y cons ain iola ion.
In his pape we add ess e iciency issues du ing he p ocess o
in eg i y main enance. In his sense, we p opose a echnique which
imp o es e iciency o exis ing me hods by de ining he o de in
which main enance o in eg i y cons ain s should be pe o med.
Mo eo e , we use also his echnique o being able o handle in an
in eg a ed way he in eg i y cons ain s en o cemen app oaches
men ioned abo e.
KEYWORDS: deduc i e da abase, upda ing, in eg i y checking, in eg i y
main enance
1. In oduc ion
Da abase upda ing has a ac ed a lo o esea ch du ing las yea s ([Abi88,
Win90]). In gene al, se e al p oblems may a ise when upda ing a deduc i e da abase
[TU95]. One o he mos impo an p oblems is ha o en o cing da abase
consis ency. A deduc i e da abase is called consis en i i sa is ies a se o in eg i y
cons ain s. When pe o ming an upda e, da abase consis ency may be iola ed. Tha
is, he upda e, oge he wi h he cu en con en o he da abase, may alsi y some
in eg i y cons ain .
A well-known app oach o deal wi h his p oblem is ha o in eg i y
main enance [CW90, KM90, ML91, CFPT92, GL93, Wü 93, TO95, Dec96], which
is conce ned wi h ying o epai cons ain s iola ions by pe o ming addi ional
upda es ha es o e consis ency o he da abase. In his way, i is gua an eed ha he
s a e esul ing om applying he upda e does no iola e any in eg i y cons ain and
ha i sa is ies he upda e eques ed by he use .
In gene al, in eg i y cons ain s a e e y in e ela ed because hey may ha e some
p edica es in common. These p edica es may appea explici ly in hei de ini ion o
implici ly because hey pa icipa e in he de ini ion o a ce ain de i ed p edica e ha
appea s in he in eg i y cons ain de ini ion. Fo his eason, he in eg i y
main enance p ocess uses o be e y complex since, o ins ance, epai s o an
in eg i y cons ain may co espond o iola ions o o he in eg i y cons ain s; o
since an al eady epai ed in eg i y cons ain could be iola ed again by he epai o
ano he in eg i y cons ain . This si ua ion is agg a a ed by he ac ha e en simple
in eg i y cons ain s can be iola ed h ough se e al upda es and because o en a
mul i ude o epai s exis .
The me hods p oposed so a o in eg i y main enance [KM90, ML91, CFPT92,
Wü 93, TO95, Dec96] ha e been mainly conce ned wi h he gene a ion o a
comple e se o epai s o in eg i y cons ain s iola ions, bu hey ha e paid li le
a en ion o e iciency issues. Thus, o ins ance, when a cons ain is epai ed all
o he cons ain s a e checked o consis ency e en hough hey we e al eady sa is ied
p io o he epai and hey could no be iola ed by he pe o med epai .
In his pape we p opose a echnique o de e mining he o de in which in eg i y
cons ain s should be handled o minimize he numbe o imes ha an in eg i y
cons ain mus be econside ed; imp o ing in his way e iciency o he whole
in eg i y main enance p ocess. This echnique p o ides wo impo an ad an ages.
Fi s , i minimizes he numbe o ecompu a ions o es ing whe he a gi en
cons ain is iola ed. Second, i ensu es ha a epai o a ce ain in eg i y cons ain
is pe o med only when all epai s o o he cons ain s ha could induce a iola ion
o i ha e been pe o med.
Ou echnique is based on he de ini ion o a g aph, he P ecedence G aph, which
explici ly s a es all ela ionships be ween epai s and po en ial iola ions o in eg i y
cons ain s. In o ma ion p o ided by his g aph is di ec ly applicable o he me hods
we ha e p oposed in he pas o handling consis en upda es in deduc i e da abases
[MT93, MT95, TO92, TO95] and i could be easily adap ed o be applicable o o he
exis ing me hods.
A di e en app oach o en o ce da abase consis ency is in eg i y checking; which
is conce ned wi h de eloping me hods o checking whe he a gi en upda e iola es
an in eg i y cons ain (see o example [Oli91, GCMD94]). In his case, when a
iola ion is de ec ed, he ansac ion is ejec ed. Bo h in eg i y cons ain en o cemen
app oaches a e easonable [Win90]. The co ec choice o an app oach o a pa icula
in eg i y cons ain depends on he seman ics o he in eg i y cons ain and o he
deduc i e da abase.
Mos o he exis ing me hods a e only conce ned wi h handling one o he
app oaches in an isola ed manne , wi hou aking in o accoun he s ong
ela ionship be ween he p oblems o be sol ed in bo h cases. As a as we know,
he only p oposal owa ds his di ec ion is ha o [CHM95] which p esen s a me hod
ha ollows he in eg i y checking app oach, bu makes some excep ions by using
ce ain cons ain s o sugges new upda es.
To u he con ibu e o en o cing da abase consis ency, we also p opose in his
pape a echnique o in eg a ing he ea men o in eg i y checking and in eg i y
main enance. This echnique is based on inco po a ing also in he p e ious g aph he
in o ma ion co esponding o he in eg i y cons ain s o be checked, and conside ing
i s ela ionship wi h cons ain s o be main ained.
This pape is o ganised as ollows. Nex sec ion e iews basic concep s o
deduc i e da abases. Sec ion 3, which is based on [Oli91, UO92], e iews he
concep s o e en , ansi ion ules and e en ules. In Sec ion 4 we p opose he
P ecedence G aph as a ool o s uc u ing he p ocess o in eg i y en o cemen . In
Sec ion 5 we p opose a mechanism o execu e ha g aph. In Sec ion 6 we ela e ou
app oach o o he ele an p e ious wo k. Finally, in Sec ion 7 we summa ize ou
conclusions.
2. Deduc i e Da abases
In his sec ion, we b ie ly e iew some de ini ions o he basic concep s ela ed o
deduc i e da abases [Llo87, Ull88] and p esen ou no a ion. Th oughou he pape ,
we conside a i s o de language wi h a uni e se o cons an s, a se o a iables, a
se o p edica e names and no unc ion symbols. We will use names beginning wi h
a capi al le e o p edica e symbols and cons an s (wi h he excep ion ha cons an s
a e also pe mi ed o be numbe s) and names beginning wi h a lowe case le e o
a iables.
A e m is a a iable symbol o a cons an symbol. I P is an m-a y p edica e
symbol and 1, ..., m a e e ms, hen P( 1, ..., m) is an a om. The a om is g ound
i e e y i (i = 1, …, m) is a cons an . A li e al is de ined as ei he an a om o a
nega ed a om. A ac is a o mula o he o m: P( 1, ..., m) ←, whe e P( 1, ..., m)
is a g ound a om.
A deduc i e ule is a o mula o he o m: P( 1, ..., m) ← L1 ∧...∧ Ln, wi h n ≥
1, whe e P( 1,..., m) is an a om deno ing he conclusion, and L1,...,Ln a e li e als
ep esen ing condi ions. Any a iable in P( 1, ..., m), L1, ..., Ln is assumed o be
uni e sally quan i ied o e he whole o mula. A de i ed p edica e P may be de ined
by means o one o mo e deduc i e ules. In his pape , we assume ha all a iables
appea ing in some condi ion o a ule appea also in i s head.
An in eg i y cons ain is a closed i s -o de o mula ha he deduc i e da abase
is equi ed o sa is y. We deal wi h cons ain s in denial o m: ← L1 ∧ ... ∧ Lm,
wi h m ≥ 1, whe e he Li a e li e als and all a iables a e assumed o be uni e sally
quan i ied o e he whole o mula. Mo e gene al cons ain s can be ans o med in o
his o m by i s applying he ange o m ans o ma ion [Dec89] and hen using he
p ocedu e desc ibed in [LT84].
Fo he sake o uni o mi y, we associa e o each in eg i y cons ain an
inconsis ency p edica e Icn, wi h o wi hou e ms, and hus hey ha e he same o m
as he deduc i e ules. We call hem in eg i y ules. Then, we ew i e he o me
denial as: Icn ← L1 ∧ ... ∧ Lm, wi h m ≥ 1
A deduc i e da abase D is a iple (EDB, IDB, IC), whe e EDB is a se o ac s,
IDB a se o deduc i e ules and IC a se o in eg i y cons ain s. The se EDB o
ac s is called he ex ensional pa o he da abase and he se o deduc i e ules and
in eg i y cons ain s is called he in ensional pa .
We assume ha deduc i e da abase p edica es a e pa i ioned in o base and de i ed
( iew) p edica es. A base p edica e appea s only in he ex ensional pa and
(e en ually) in he body o deduc i e ules. A de i ed p edica e appea s only in he
in ensional pa . Any da abase can be de ined in his o m [BR86]. We deal wi h
s a i ied da abases [Llo87] and, as usual, we equi e he da abase o be allowed
[Llo87]; ha is, any a iable ha occu s in a deduc i e ule has an occu ence in a
posi i e condi ion o an o dina y p edica e.
Example 2.1: The ollowing example o deduc i e da abase which is conce ned
abou membe s o a club o an associa ion will be used h oughou he pape :
Acc(Paul)
Rec(Paul)
Pa (Paul)
Mem(x) ← Rec(x) ∧ Acc(x)
Ac i e(x) ← Pa (x)
Ic1(x) ← Acc(x) ∧ Neg(x)
Ic2(x) ← Ac i e(x) ∧ ¬ Mem(x)
Ic3(x) ← Rec(x) ∧ ¬ Pa (x)
This da abase con ains ou base p edica es and wo de i ed ones:
Rec(x) s a es ha a pe son x is ecommended o be membe o a club
Acc(x) s a es ha a pe son x is accep ed as a membe o he club
Pa (x) s a es ha a pe son x has some pa icipa ion in an ac i i y o he club
Neg(x) s a es ha a pe son x has a nega i e epo
Mem(x) s a es ha a pe son x is a membe o a club i he/she is ecommended
and accep ed
Ac i e(x) s a es ha a pe son x has an ac i e a i ude i he/she pa icipa es in an
ac i i y o he club
No ice ha he da abase con ains also h ee in eg i y cons ain s s a ing,
espec i ely, ha people ha a e accep ed o he club could no ge a nega i e epo ;
ha people wi h an ac i e a i ude mus be membe s; and, ha i is equi ed ha a
ecommended pe son pa icipa es in some ac i i y.
3. The Augmen ed Da abase
The main goal o his pape is o p opose a echnique o de e mining he o de in
which in eg i y cons ain s should be handled. This o de is p o ided by he
P ecedence G aph, which explici ly s a es all ela ionships be ween epai s and
po en ial iola ions o in eg i y cons ain s. The de ini ion o his g aph, gi en in
nex sec ion, will ake in o accoun a se o ules ha p ecisely de ine he di e ence
be ween wo consecu i e da abase s a es. This se o ules, oge he wi h he o iginal
da abase D, o m he Augmen ed Da abase [Oli91, UO92], deno ed by A(D), which
explici ly de ines he inse ions and dele ions induced by a ansac ion T ha consis s
o a se o base ac upda es.
The concep o Augmen ed Da abase is s ongly based on he concep o e en .
Fo each p edica e P in he unde lying language o a gi en deduc i e da abase D, a
dis inguished inse ion e en p edica e ιP and a dis inguished dele ion e en p edica e
δP a e used o de ine he p ecise di e ence o deducible ac s o consecu i e da abase
s a es.
I P is a base p edica e, ιP and δP ac s (called base e en ac s) ep esen
inse ions and dele ions o base ac s, espec i ely. Fo his eason, we assume ha a
ansac ion T consis s o a se o base e en ac s. I P is a de i ed p edica e, ιP and
δP ac s ep esen induced inse ions and induced dele ions, espec i ely. I P is an
inconsis ency p edica e, ιP ep esen s a iola ion o he co esponding in eg i y
cons ain . Fo inconsis ency p edica es, δP ac s a e no de ined since we assume
ha he da abase is consis en be o e he upda e.
The de ini ion o ιP and δP depends on he de ini ion o P in D, bu is
independen o any ansac ion T and o he ex ensional pa o D. Fo each de i ed o
inconsis ency p edica e P, he Augmen ed Da abase con ains he ules abou ιP and
δP, called e en ules, which de ine exac ly he inse ions and dele ions o ac s abou
P ha a e induced by some ansac ion T. E en ules a e de ined as ollows:
ιP(x) ← Pn(x) ∧ ¬P(x)
δP(x) ← P(x) ∧ ¬Pn(x)
whe e P e e s o a p edica e e alua ed in he old s a e o he da abase, Pn e e s o he
p edica e P e alua ed in he new s a e o he da abase and x is a ec o o a iables.
The Augmen ed Da abase con ains also a se o ansi ion ules associa ed o each
de i ed o inconsis ency p edica e P. These ansi ion ules de ine he e alua ion o
p edica e P in he new s a e (deno ed by Pn) in e ms o he old s a e o he da abase
and he e en s ha occu in he ansi ion be ween bo h s a es. We illus a e e en
and ansi ion ules by means o an example.
Example 3.1: Conside he de i ed p edica e Mem(x) om example 2.1 de ined
by he ule Mem(x) ← Rec(x) ∧ Acc(x). E en and ansi ion ules associa ed o his
p edica e a e he ollowing:
ιMem(x) ← Memn(x) ∧ ¬Mem(x)
δMem(x) ← Mem(x) ∧ ¬Memn(x)
Memn(x) ← Rec(x) ∧ ¬δRec(x) ∧ Acc(x) ∧ ¬δAcc(x)
Memn(x) ← Rec(x) ∧ ¬δRec(x) ∧ ιAcc(x)
Memn(x) ← ιRec(x) ∧ Acc(x) ∧ ¬δAcc(x)
Memn(x) ← ιRec(x) ∧ ιAcc(x)
T ansi ion ules o Memn(x) de ine all possible ways o ha ing ac s abou
Mem(x) in he new s a e. The i s one co esponds o he case ha a ac o Mem(x)

was ue in he old s a e and has no been dele ed by he ansac ion, while he o he s
e lec all possible ways o inse a ac o Mem(x) by he ansac ion.
Gi en a deduc i e da abase D, he Augmen ed Da abase A(D) consis s o D, i s
ansi ion ules and i s e en ules. Desc ip ion and discussion o he p ocedu e o
au oma ically de i ing an Augmen ed Da abase om a da abase can be ound in
[Oli91, UO92]. These e e ences also desc ibe se e al syn ac ical simpli ica ions o
ansi ion and e en ules.
Example 3.2: The ollowing example shows he Augmen ed Da abase o
example 2.1, a e simpli ica ion.
Mem(x) ← Rec(x) ∧ Acc(x)
Ac i e(x) ← Pa (x)
Ic1(x) ← Acc(x) ∧ Neg(x)
Ic2(x) ← Ac i e(x) ∧ ¬ Mem(x)
Ic3(x) ← Rec(x) ∧ ¬ Pa (x)
ιMem(x) ← Rec(x) ∧ ¬ δRec(x) ∧ ιAcc(x)
ιMem(x) ← ιRec(x) ∧ Acc(x) ∧ ¬ δAcc(x)
ιMem(x) ← ιRec(x) ∧ ιAcc(x)
δMem(x) ← δRec(x) ∧ Acc(x)
δMem(x) ← Rec(x) ∧ δAcc(x)
ιAc i e(x) ← ιPa (x)
δAc i e(x) ← δPa (x)
(C1)ιIc1(x) ← Acc(x) ∧ ¬ δAcc(x) ∧ ιNeg(x)
(C2)ιIc1(x) ← ιAcc(x) ∧ Neg(x) ∧ ¬ δNeg(x)
(C3)ιIc1(x) ← ιAcc(x) ∧ ιNeg(x)
(C4)ιIc2(x) ← Ac i e(x) ∧ ¬ δAc i e(x) ∧ δMem(x)
(C5)ιIc2(x) ← ιAc i e(x) ∧ ¬ Mem(x) ∧ ¬ ιMem(x)
(C6)ιIc2(x) ← ιAc i e(x) ∧ δMem(x)
(C7)ιIc3(x) ← Rec(x) ∧ ¬ δRec(x) ∧ δPa (x)
(C8)ιIc3(x) ← ιRec(x) ∧ ¬ Pa (x)) ∧ ¬ ιPa (x)
(C9)ιIc3(x) ← ιRec(x) ∧ δPa (x)
Rules C1 o C9 de ine all possible ways o inse ing ac s abou p edica es Ic1,
Ic2 and Ic3. These ules dese e special a en ion since hey de ine all possible
si ua ions in which da abase consis ency is iola ed by he applica ion o some
ansac ion.
4. S uc u ing he P ocess o In eg i y Main enance
S uc u ing he p ocess o in eg i y main enance is conce ned wi h de e mining
he o de in which in eg i y cons ain s should be handled. This o de is p o ided by
he P ecedence G aph, which explici ly s a es all ela ionships be ween epai s and
po en ial iola ions o in eg i y cons ain s. In his sec ion we de ine how his g aph
is ob ained and how i can be used o in eg a ing in eg i y main enance and in eg i y
checking.
To ob ain he P ecedence G aph we only ake in o accoun syn ac ical
in o ma ion associa ed o he de ini ion o each in eg i y cons ain . Thus, we do no
need o conside he con en s o he EDB no he ansac ion o be applied o he
da abase. The e o e, we gene a e he P ecedence G aph a de ini ion ime, and we
delay o un ime o es whe he po en ial dependencies de ined in he g aph
co espond o eal iola ions.
We ake ad an age o assuming ha he da abase is consis en be o e he
applica ion o a ansac ion T. Then, iola ions o da abase consis ency due o he
ansac ion T a e only p oduced because some inse ion e en ule associa ed o an
in eg i y cons ain becomes ue. Mo eo e , epai s o he cons ain a e de ined by
he iola ed inse ion e en ule, since a epai co esponds o an addi ional upda e
ha alsi ies he e ec o T on he co esponding e en ule. Fo his eason, we e e
o he inse ion e en ules o an in eg i y cons ain as he condi ions o ha
in eg i y cons ain .
In o de o s a e dependencies be ween in eg i y cons ain s mo e p ecisely, we
conside he condi ions associa ed o an in eg i y cons ain ins ead o he own
in eg i y cons ain de ini ion. Thus, he P ecedence G aph will s a e all ela ionships
be ween epai s and po en ial iola ions o hese condi ions.
Example 4.1: Condi ions associa ed o in eg i y cons ain Ic1 o he example
3.2 a e he ollowing:
Iden i ie Condi ion
C1← Acc(x) ∧ ¬ δAcc(x) ∧ ιNeg(x)
C2← ιAcc(x) ∧ Neg(x) ∧ ¬ δNeg(x)
C3← ιAcc(x) ∧ ιNeg(x)
No e ha each condi ion desc ibes a si ua ion o be a oided o ensu e ha an
upda e does no iola e in eg i y cons ain Ic1. The e o e, ensu ing ha no condi ion
holds we gua an ee ha no in eg i y cons ain is iola ed. In he ollowing we will
e e o each condi ion by i s iden i ie Ci (i=1..n).
4.1 E en s Dependency G aph
Se e al de i ed e en s and se e al condi ions may be induced when applying a
ansac ion consis ing o a se o base e en ac s. Fo ins ance, in he p e ious
example he applica ion o he base e en ιAcc may induce he de i ed e en ιMem
as well as condi ions C2 and C3. Ob aining he P ecedence G aph equi es o
de e mine which epai s o a condi ion a e po en ial iola ions o o he condi ions.
To de e mine his in o ma ion, we need i s o explici ly s a e he ela ionship
be ween base e en s and hei e ec on de i ed e en s and condi ions. Gi en he
Augmen ed Da abase A(D), we can iden i y he ollowing dependencies:
De ini ion 4.1 Le E be an e en and C be a condi ion o a de i ed e en . We
say ha C di ec ly depends on E i he e is a ule in A(D) wi h e en C as head and
such ha E appea s in i s body. A di ec dependence is posi i e ( esp. nega i e) i E
is a posi i e li e al ( esp. nega i e).
By conside ing oge he all di ec dependencies be ween e en s and condi ions we
can build he E en s Dependency G aph [Cos95], which explici ly s a es he
ela ionship be ween he applica ion o e en s on a da abase and hei induced e ec ,
and which builds he basis o he p ocess o s uc u ing in eg i y main enance.
De ini ion 4.2 An E en s Dependency G aph EDG o a se o e en s and a
se o condi ions, is a pai EDG = <Nod, Edg> whe e Nod is a ini e numbe o
nodes, Edg ⊆ (Nod x Nod) is a se o di ec ed edges such ha each node n ∈ Nod is
labelled wi h a condi ion iden i ie o an e en . Gi en wo nodes and ', he e
exis s an edge e=( , ') i ' di ec ly depends on . Edges a e ma ked posi i e ( esp.
nega i e) i he dependence is posi i e ( esp. nega i e).
Example 4.2: Conside again he da abase D o Example 3.2. Figu e 1
ep esen s he E en s Dependency G aph de i ed om he Augmen ed Da abase A(D).
Black a ows co espond o posi i e edges, while g ey a ows co espond o he
nega i e ones.
C1
C2C3
C4
C5C6
ιRec δRec
ιNeg δNeg ιAcc δAcc ιPa δPa
ιMem δMem ιAc i e δAc i e
C7C8
C9
Fig.1. E en s Dependency G aph o ou example
De ini ion 4.3 Le EDG be an E en s Dependency G aph and and ' wo
nodes in EDG. We say ha :
- depends on ' i EDG con ains a pa h om ' o .
- depends e enly ( esp. oddly) on ' i he e is a pa h om ' o in EDG
con aining an e en ( esp. odd) numbe o nega i e edges.
Dependencies be ween e en s and condi ions allow us o de e mine po en ial
iola ions and epai s o a condi ion. In ui i ely, a po en ial iola ion o a condi ion
Ci is an e en ha when applied o he da abase may induce an inse ion o he
inconsis ency p edica e associa ed o Ci. Tha is, Ci may become ue due o ha
e en . On he o he hand, a po en ial epai o a condi ion Ci is a base e en ha
when applied o he da abase may alsi y Ci. This no ion can also be gene alized o
de i ed e en s and we will e e o hem as po en ial alsi ie s. This in o ma ion can
be syn ac ically iden i ied by conside ing he dependencies de ined by he E en s
Dependency G aph.
De ini ion 4.4 Le E be an e en and Ci a condi ion.
- E is a po en ial iola ion o Ci i Ci depends e enly on E.
- E is a po en ial epai o Ci i E is a base e en and Ci depends oddly on E.
- E is a po en ial alsi ie o Ci i E is a de i ed e en and Ci depends oddly on
E.
A de ini ion ime we can no ensu e ha an e en will be a eal iola ion o a
ce ain condi ion a un ime since he da abase mus also sa is y o he equi emen s
ha may be unknown a his momen . This is why we alk abou po en ial
iola ions. We alk abou po en ial epai s and alsi ie s since, in gene al, epai ing a
condi ion may equi e he applica ion o mo e han one e en .
Example 4.3: Conside again condi ion C2 o Example 3.2:
C2 ← ιAcc(x) ∧ Neg(x) ∧ ¬ δNeg(x)
E en ιAcc(x) is a po en ial iola ion o C2 because i could make C2 ue
depending on he es o li e als o he condi ion. E en δNeg(x) is he only po en ial
epai o condi ion C2.
I may happen ha no po en ial epai exis s o a ce ain condi ion. So, we
dis inguish be ween wo di e en kinds o condi ions. Checking condi ions a e hose
ha ha e no po en ial epai ; while condi ions wi h some po en ial epai a e called
gene a ion condi ions. Each condi ion can be classi ied only in o one o hese wo
ca ego ies.
De ini ion 4.5 Le Ci be a condi ion. Ci is a checking condi ion i he e is no
po en ial epai associa ed o i . O he wise, Ci is a gene a ion condi ion.
Checking condi ions o he example a e C3, C6 and C9. All o he condi ions a e
gene a ion condi ions.
4.2 P ecedences Be ween Condi ions
We a e in e es ed on minimizing he numbe o imes ha a condi ion should be
econside ed. Fo his eason, we should i s deal wi h hose condi ions whose
epai s may induce a iola ion o o he condi ions. The E en s Dependency G aph
does no ell us which condi ions should p ecede which o he s, bu i p o ides he
basis o de e mining his in o ma ion.
In gene al, a condi ion will ha e se e al po en ial epai s. Mo eo e , due o he
mul ile el s uc u e o de i ed p edica es, de i ed e en s mus also be conside ed
when de e mining p ecedences among condi ions. Thus, some o he po en ial epai s
may be meaningless since hey a e al eady implied by conside ing po en ial alsi ie s.
The e o e, we ha e o de ine i s which a e he meaning ul e en s ha mus be
conside ed o de e mine he p ecedence be ween wo condi ions. We call hem
mee ing e en s and hey a e de ined as ollows:
De ini ion 4.6 Le Ci and Cj be wo di e en condi ions. A base o de i ed
e en E is a mee ing e en i one o he ollowing condi ions holds:
- i appea s in he de ini ion o bo h Ci and Cj.
- i appea s in he de ini ion o Ci and i de ines a de i ed e en ha appea s
in Cj bu no in Ci
- i de ines a de i ed e en ha appea s in Ci and ano he de i ed e en ha
appea s in Cj bu no in Ci.
In ui i ely, i can be seen ha o de e mine he p ecedence be ween wo
condi ions we ha e o conside only hose e en s ha pa icipa e on he de ini ion o
bo h condi ions. This may be done ei he explici ly by conside ing he de ini ion o
he condi ions o implici ly by aking in o accoun he de i ed e en s hey de ine and
ha appea in he de ini ion o he condi ions.
Example 4.4: Conside again he da abase example 3.2. The only mee ing
e en o condi ions C1 and C4 is δAcc(x); while mee ing e en s o condi ions C4
and C7 a e δRec(x) and δPa (x).
Now, by aking in o accoun mee ing e en s we can iden i y p ecedences be ween
condi ions. In ui i ely, condi ion Ci mus p ecede condi ion Cj i he e exis s a
mee ing e en ha , depending on whe he i holds o no , i may alsi y condi ion Ci
and sa is y condi ion Cj. Tha is, his e en will be conside ed when gene a ing a
- Remo e_Ma k (C, GT): i unma ks node C om GT and e u ns he new
ma ked g aph.
- Selec _Nex _Node (GT): gi en a ma ked g aph GT i selec s he nex node o be
p ocessed. Nodes wi h unma ked p edecesso s a e selec ed wi h p io i y. I he e a e
di e en candida es o selec , nodes co esponding o checking condi ions a e
conside ed i s . This helps o imp o e e iciency o he whole p ocess since i his
condi ion is iola ed, no o he node will be conside ed.
- Check_Condi ion (C, T): gi en a condi ion C and a ansac ion T, i es s
whe he C is iola ed by T. To imp o e e iciency, his can be done by means o any
a bi a y me hod o in eg i y checking.
- Compu e_All_Repai s (C, T): gi en a condi ion C and a ansac ion T, i
e u ns he se o all possible epai s o C. This unc ion mus ake in o accoun he
ansla ion o po en ial alsi ie s in o po en ial epai s.
T ea men o subg aphs is pe o med by means o a ecu si e call o he unc ion
Execu e_G aph(T, GT), whe e T is he cu en ansac ion and GT co esponds o he
subg aph de ined by he selec ed node.
Example 5.1: Conside again he da abase o example 4.8 and i s associa ed
P ecedence G aph shown in Fig.4. The ollowing able summa izes he execu ion o
he P ecedence G aph gi en he ini ial ansac ion T = {ιNeg(Paul)}.
In each ow, an 'V' shows he node selec ed a each s ep and an 'X' indica es ha a
node is ma ked. The column 'T ansac ion' indica es which e en s belong o he
ansac ion T and each new inclusion in o i is deno ed in i alic.
C
1
C
2
C
3
C4
C
5
C
6
C
7
C
8
C9
C
10
C1C1T ansac ion
VXιNeg(Paul),
δ
Acc(Paul)
XXXVιNeg(Paul),δAcc(Paul)
XXVιNeg(Paul),δAcc(Paul)
VXιNeg(Paul),δAcc(Paul)
VιNeg(Paul),δAcc(Paul),
δ
Pa (Paul)
VιNeg(Paul),δAcc(Paul),
δPa (Paul),
δ
Rec(Paul)
Ini ially, ma ked nodes a e C1 and C3. Node C1 is selec ed i s because i does
no ha e any p edecesso . T ansac ion T iola es i , and i is epai ed wi h he e en
δAcc(Paul). Then, node C1 is unma ked and nodes C4, C5 and C6 a e ma ked.
In nex s eps, nodes C6, C5 and C3 a e selec ed in his o de and unma ked since
hei co esponding condi ions a e no iola ed by he cu en ansac ion. A s ep 5
condi ion o node C4 is iola ed, and i is epai ed by including δPa (Paul) in he
ansac ion. As a consequence, node C7 is ma ked and i is conside ed a s ep 6.
Since C7 is iola ed, he addi ional e en δRec(Paul) is included in he ansac ion.
A e his s ep, he e is no ma ked node in he P ecedence G aph. Then, he
in eg i y main enance p ocess inishes and he ansac ion T'={ιNeg(Paul),

δAcc(Paul), δPa (Paul), δRec(Paul)} is ob ained. No e ha his is he only
ansac ion ha main ains da abase consis ency in ou example.
To main ain da abase consis ency in his example, we ha e p ocessed only 6
condi ions. In pa icula , we should no e ha none o hem has been conside ed mo e
han once. On he con a y, i we had no aken in o accoun he in o ma ion
p o ided by he P ecedence G aph, 45 condi ions would had been p ocessed. The
eason is ha in he la e case, when a condi ion is epai ed all o he condi ions
mus be checked again o consis ency e en hough hey we e al eady alse p io o
he epai and hey could no be iola ed by i . This impo an d awback is sha ed by
all me hods p oposed up o now o in eg i y main enance.
In ac , i is su icien o us ha only one in eg i y cons ain is epai ed o ha e
a be e pe o mance han in eg i y main enance me hods p oposed up o now. E en
in his simple case, cu en me hods mus econside again p e iously p ocessed
cons ain s. The numbe o unnecessa y cons ain s p ocessed by hese me hods
signi ican ly inc eases when he complexi y o he da abase, o he conside ed
ansac ions and o he numbe o necessa y epai s augmen s.
6. Rela ion wi h P e ious Wo k
A signi ican amoun o wo k has been de o ed o he a ea o in eg i y checking
o de ine he o de in which de i ed p edica es should be e alua ed o op imize he
es o whe he a ansac ion iola es an in eg i y cons ain [Ple93, Sel95]. In his
sense, se e al g aphs ha de ine his o de ha e been p oposed. Simila wo k has
been pe o med in he a ea o ac i e da abases o explici ly s a e he ela ionship
be ween he ac i a ion o ules o p edic ing e mina ion and con luence o ac i e
ules [BW94, KU94, AHW95].
Wo k in hese wo a eas is di e en om ou s since we a e aimed a de e mining
he o de in which in eg i y cons ain s should be handled and no he o de o
e alua ion o p edica es in ol ed in an in eg i y cons ain de ini ion. In ac , his
la e o de is de ined by ou E en s Dependency G aph which s a es he ela ionship
be ween base e en s and hei po en ial e ec on de i ed e en s and condi ions.
Howe e , as we ha e seen, his g aph is no su icien o de e mine he o de o
p ocessing in eg i y cons ain s.
Wo k mos ela ed o ou s has been p oposed in he a ea o in eg i y main enance.
As we said, me hods p oposed up o da e in his a ea ha e paid li le a en ion in
e iciency issues. A signi ica i e excep ion is he wo k pe o med by Ge z in
[Ge 93, Ge 94, GL93], which is conside ed in de ail in he ollowing subsec ion.
6.1 Ge z's App oach [Ge 93, Ge 94]
Ge z p oposes o ca y ou a de ini ion ime he analysis and he speci ica ion o
eac ions on cons ain iola ions. In his sense, he p o ides a decla a i e
speci ica ion language o eac ions on iola ions sui able o exp ess se e al in eg i y
cons ain s en o cemen app oaches. He desc ibes how o ob ain, once he in eg i y
cons ain s and hei co esponding eac ions ha e been speci ied by he designe , a
dependency g aph which exp esses he ela ionship be ween epai s and po en ial
iola ions o in eg i y cons ain s. Finally, he p esen s also a p ocedu e o de i ing
in eg i y en o cing igge s om his dependency g aph. Execu ion o hese igge s
gua an ees ha a ansac ion applied o a da abase main ains he in eg i y cons ain s.
Se e al di e ences exis be ween Ge z's p oposal and ou s. The i s one is
ela ed o he way o handling in eg i y main enance. Ge z p oposes he designe o
explici ly speci y eac ions o in eg i y cons ain s iola ions, while we conside
hese eac ions o be au oma ically gene a ed om he de ini ion o he in eg i y
cons ain s. Thus, looking o dependencies be ween in eg i y cons ain s is mo e
complex in ou app oach since hey a e no explici ly s a ed and ha e o be
implici ly de i ed om he in eg i y cons ain s de ini ion.
Ano he impo an di e ence e e s o he exp essi eness o he de ini ion
language conside ed in bo h p oposals. Ge z's p oposal is es ic ed o da abases
wi hou deduc i e ules, hus conside ing only la in eg i y cons ain s (i.e.
cons ain s ha a e de ined only by means o base p edica es); and i is es ic ed also
o in eg i y cons ain s in Implica i e No mal Fo m (which does no allow nega ion
in he body o a cons ain ). On he con a y, we handle deduc i e ules as well as
non- la in eg i y cons ain s and we allow nega ion o appea in he body o he
ules and o he cons ain s (in ac , he only equi emen s we impose on he da abase
a e hose o allowedness and s a i ica ion which a e much mo e gene al han Ge z
equi emen s). Thus, ou echnique can be applied in mo e cases han Ge z's
echnique. I is also wo h o men ion he addi ional complexi y o ou app oach due
o he ac ha we ha e o ake he de ini ion o de i ed p edica es in o accoun .
Finally, i mo e han one dependency exis s be ween wo in eg i y cons ain s,
Ge z o ces o he designe o weigh all possible eac ions o indica e which
eac ion should be conside ed wi h p io i y. Thus, i is gua an eed ha a execu ion
ime only one epai is conside ed o a conc e e iola ion o an in eg i y cons ain .
On he con a y, we ake in o accoun all possible epai s o a gi en in eg i y
cons ain de ini ion. Thus, we will be able o es o e da abase consis ency in cases
whe e Ge z app oach is no able o do i since he designe may no ha e
app op ia ely weigh ed he epai s o in eg i y cons ain s.
7 Conclusions
In his pape we ha e p oposed a echnique o imp o ing e iciency o he
in eg i y main enance p ocess. This echnique is based on he de ini ion and
execu ion o a g aph, he P ecedence G aph, which explici ly s a es he ela ionship
be ween epai s o an in eg i y cons ain and po en ial iola ions o o he in eg i y
cons ain s.
The p oposed echnique con ibu es o imp o ing e iciency o in eg i y
main enance in wo di e en ways. Fi s , i minimizes he numbe o
ecompu a ions o es ing whe he a gi en cons ain is iola ed. Second, i ensu es
ha a epai o a ce ain in eg i y cons ain is pe o med only when all epai s o
o he cons ain s ha could induce a iola ion o i ha e been pe o med.
Ano he con ibu ion o he echnique p oposed in his pape is ha i allows o
ake in o accoun in eg i y cons ain s o be checked in addi ion o in eg i y
cons ain s o be main ained. Thus, we ha e shown a possible way o in eg a ing
in o a single me hod bo h in eg i y cons ain en o cemen app oaches.
Acknowledgemen s
We a e g a e ul o D. Cos al, A. Oli é, J. A. Pas o , C. Que , M. R. Sancho, J.
Sis ac and T. U pí o many use ul commen s and discussions. This wo k has been
pa ially suppo ed by he CICYT PRONTIC p og am p ojec TIC94-0512.
Re e ences
[Abi88] Abi eboul, S. "Upda es, a New F on ie ", In . Con . on Da abase Theo y
(ICDT'88), Sp inge , 1988, pp.1-18.
[AHW95] Aiken, A.; Helle s ein, J.M.; Widom, J. "S a ic Analysis Techniques o
P edic ing he Beha io o Ac i e Da abase Rules", ACM T ansac ions on
Da abase Sys ems, Vol. 20, Nº 1, M ach 1995, pp. 3-41.
[BR86] Bancilhon, F.; Ramak ishnan, R, "An Ama eu 's In oduc ion o Recu si e
Que y P ocessing", P oc. ACM SIGMOD In . Con . on Managemen o Da a,
Washing on D.C., 1986.
[BW94] Ba alis, E.; Widom, J. "An Algeb aic App oach o Rule Analysis in Expe
Da abase Sys ems", P oc. o he 20 h VLDB Con e ence, San iago, Chile,
1994, pp. 475-486.
[GCMD94] Ga cía, C.; Celma, M; Mo a, L.; Decke , H. "Compa ing and Syn hesising
In eg i y Checking Me hods o Deduc i e Da abases", In . Con . on Da a
Enginee ing (ICDE'94), Hous on (Texas), 1994, pp. 214-222.
[CHM95] Chen, I.A.; Hull, R.; McLeod, D. "An Execu ion Model o Limi ed Ambigui y
Rules and I s Applica ion o De i ed Da a Upda e". ACM T ansac ions on
Da abase Sys ems, Vol. 20, Nº 4, Decembe 1995, pp. 365-413.
[Cos95] Cos al, D. "Un mè ode de plani icació basa en l'ac uali zació de is es en
bases de dades deduc i es", PhD Thesis, Ba celona, 1995 (in ca alan).
[CW90] Ce i, S.; Widom, J. "De i ing P oduc ion Rules o Cons ain Main enance",
P oc. o he 16 h VLDB Con e ence, B isbane, Aus alia, 1990, pp. 566-577.
[CFPT92] Ce i, S.; F a e nali, P.; Pa aboschi, S.; Tanca, L. "In eg i y Main enance
Sys ems: an a chi ec u e", Thi d In . Wo kshop on he Deduc i e App oach o
In o ma ion Sys ems and Da abases, Roses, Ca alonia, 1992, pp. 327-344.
[Dec89] Decke , H. "The Range Fo m o da abases o : How o a oid Flounde ing",
P oc. 5 h ÖGAI, Sp inge -Ve lag, 1989.
[Dec96] Decke , H. "An Ex ension o SLD by Abduc ion and In eg i y Main enance o
View Upda ing in Deduc i e Da abases", To appea in Join In e na ional
Con e ence and Symposium on Logic P og amming (JICSLP'96), Bonn
(Ge many), 1996.
[Ge 93] Ge z, M. "On Speci ying he Reac i e Beha io on Cons ain Viola ions",
In o ma ik-Be ich e 2/93, Ins i u ü In o ma ik, Uni e si ä Hanno e ,
1993.
[GL93] Ge z, M.; Lipeck, U.W. "De i ing In eg i y Main aining T igge s om
T ansac ion G aphs", In e na ional Con e ence on Da a Enginee ing
(ICDE'93), Vienna, 1993, pp. 22-29.
[Ge 94] Ge z, M. "Speci ying Reac i e In eg i y Con ol o Ac i e Da abases",
Resea ch Issiues on Da a Enginee ing: Ac i e Da abases (RIDE-ADS'94),
Hous on, Texas, 1994, pp. 62-70.
[KM90] Kakas, A.; Manca ella, P. "Da abase Upda es h ough Abduc ion", P oc. o he
16 h VLDB Con e ence, B isbane, Aus alia, 1990, pp. 650-661.
[KU94] Ka adimce, A.P.; U ban, S.D. "Condi ional Te m Rew i ing as a Fo mal Basis
o Analysis o Ac i e Da abase Rules" Resea ch Issiues on Da a Enginee ing:
Ac i e Da abases (RIDE-ADS'94), Hous on, Texas, 1994, pp. 156-162.
[Llo87] Lloyd, J.W. "Founda ions on Logic P og amming", 2nd edi ion, Sp inge ,
1987.
[LT84] Lloyd, J.W.; Topo , R.W. “Making P olog Mo e Exp essi e”. Jou nal o
Logic P og amming, 1984, No. 3, pp. 225-240.
[ML91] Moe ko e, G; Lockemann, P.C. "Reac i e Consis ency Con ol in Deduc i e
Da abases", ACM T ansac ions on Da abase Sys ems, Vol. 16, No. 4,
Decembe 1991, pp. 670-702.
[MT93] Mayol, E.; Tenien e, E. " Inco po a ing Modi ica ion Reques s in Upda ing
Consis en Knowledge Bases", Fou h In . Wo kshop on he Deduc i e
App oach o In o ma ion Sys ems and Da abases, Llo e de Ma , Ca alonia,
1993, pp. 335-360.
[MT95] Mayol, E.; Tenien e, E. "Towa ds an E icien Me hod o Upda ing Consis en
Deduc i e Da abases", Basque In e na ional Wo kshop on In o ma ion
Techlogogy (BIWIT'96): Da a Managemen Sys ems, IEEE Compu e Socie y
P ess, San Sebas ian, Spain, 1996, pp. 113-122.
[MT96] Mayol, E.; Tenien e, E. "Analysing he P ocess o En o cing In eg i y
Cons ain s", Technical Repo RR-96/38, 1996, Uni e si a Poli ècnica de
Ca alunya.
[Oli91] Oli é, A. "In eg i y Checking in Deduc i e Da abases", P oc. o he 17 h
VLDB Con e ence, Ba celona, Ca alonia, 1991, pp. 513-523.
[Ple93] Plexousakis, D. "In eg i y Cons ain and Rule Main enance in Tempo al
Deduc i e Knowledge Bases", P oc. o he 19 h VLDB Con e ence, Dublin,
I eland, 1993, pp. 146-157.
[Sel95] Seljée, R. "A New Me hod o In eg i y Cons ain s Checking in Deduc i e
Da abases", Da a & Knowledge Enginee ing, Vol. 15, 1995, pp. 63-102.
[TO92] Tenien e, E.; Oli é, A. "The E en s Me hod o View Upda ing in Deduc i e
Da abases", In . Con . on Ex ending Da abase Technology (EDBT’92),
Vienna, 1992, pp. 245-260.
[TO95] Tenien e, E.; Oli é, A. "Upda ing Knowledge Bases while Main aining hei
Consis ency", The VLDB Jou nal, Vol. 4, Num. 2, 1995, pp. 193-241.
[TU95] Tenien e, E.; U pí, T. "A Common F amewo k o Classi ying and Speci ying
Deduc i e Da abase Upda ing P oblems", In e na ional Con e ence on Da a
Enginee ing (ICDE'95), Taipei, 1995, pp. 173-182.
[Ull88] Ullman, J.D. "P inciples o Da abase and Knowledge-Base Sys ems",
Compu e Science P ess, New Yo k, 1988.
[UO92] U pí, T.; Oli é, A. "A Me hod o Change Compu a ion in Deduc i e
Da abases", P oc. o he 18 h VLDB Con e ence, Vancou e , 1992, pp. 225-
237.
[Win90] Winsle , M. "Upda ing Logical Da abases", Camb idge T ac s in Theo e ical
Compu e Science 9, 1990.
[Wü 93] Wü h ich, B. "On Upda es and Inconsis ency Repai ing in Deduc i e
da abases", In . Con . on Da a Enginee ing, Vienna, 1993, pp. 608 - 615.