IMPROVING THE DETERMINATION OF
MINIMAL HITTING SETS IN MODEL-BASED
DIAGNOSIS USING CONSTRAINT
DATABASES
M. T. G´omez-L´opez, R. M. Gasca and C. del Valle ∗,1
∗Escuela T´ecnica y Supe io de Ingenie ´ıa In o m´a ica de
Se illa, Spain
{may e, gasca, ca melo}@lsi.us.es
Abs ac : In model-based diagnosis, minimal hi ing se s a e usually used o
iden i y which componen s may ail in a sys em. This wo k p esen s a se o
algo i hms o imp o e he de e mina ion o all Minimal Hi ing Se s. Ou p oposal
uses he minimal conflic se s o ob ain, in an efficien way, he diagnosis o a
sys em. The imp o emen consis s o h ee algo i hms which analyse only he
ele an op ions. This p oposal builds an equi alen sys em in o de o ob ain all
minimal hi ing se s depending on he loca ion o he senso s. A he same ime,
all he in o ma ion o he p ocess is s o ed in a Cons ain Da abase, keeping
he in o ma ion pe sis en and eco e able. Some empi ical esul s a e p esen ed
in o de o show how he p oposal imp o es he p ocess in o de o ob ain all
minimal hi ing se s.Copy igh
Keywo ds: Model-based Diagnosis, Cons ain Da abases, minimal hi ing se s.
1. INTRODUCTION
A lo o heo e ical and p ac ical p oblems can
be pa ly educed o an ins ance o he minimal
hi ing se p oblem, as in model-based diagnosis
how i is explained in (Rei e , 1987). Model-based
diagnosis allows he iden ifica ion o he pa s
which may ail in a sys em using a model. The
models a e based on he knowledge o he sys em
o be diagnosed, and i can be ep esen ed by
cons ain s associa ed o he componen s. Inpu s
and ou pu s o componen s a e ep esen ed as
a iables in he cons ain s, and hey can be
obse able and non-obse able, depending on he
alloca ion o he senso s. In unc ion o he alue
o hese senso s, i is possible o know which
1This wo k has been unded by he Minis e io de Ciencia
y Tecnolog´ıa o Spain (DPI2003-07146-C02-01) and he
Eu opean Regional De elopmen Fund (ERDF/ FEDER).
g oups o componen s a e ailing looking o he
minimal hi ing se s. In his wo k, a new app oach
is p oposed in o de o au oma e and o imp o e
he de e mina ion o all minimal hi ing se s.
The e a e a significan amoun o wo ks ha deals
wi h minimal hi ing se s, bu mos o hem a e
only in e es ed in finding single minimal hi ing
se s and o special ypes o p oblems. Ou mo-
i a ion is o find all minimal hi ing se s, single
o mul iple. Ano he ad an age o ou echnique
is he possibili y o s o e all he diagnosis p ocess
in o ma ion using he ela ional calculus.
One o ou p e ious wo ks (G´omez-L´opez e al.,
2004) shows how o ob ain he possible minimal
conflic se s in an efficien way. This pape s a s
a his poin , and some algo i hms a e de eloped
and implemen ed o ob ain he minimal diagnosis.
In his pape , we p esen how some issues conce n-
ing Cons ain Da abases (CDBs) can imp o e he
efficiency in some s ages o he model-based diag-
nosis. A no el me hodology is p esen ed in o de
o p omo e he ad an ages o his echnology and
i s usage in indus ial diagnosis p oblems.
Mo eo e he ela ional model is no able o
ep esen he scien ific and enginee ing da a. Fo
his eason, we conside CDBs as a good ool o
ou easoning p ocess. The e a e lo s o wo ks,
as (Re esz, 2002) and (Kupe e al., 1998), ha
u ilise CDBs, bu nei he o hem uses hem o
diagnosis. CDBs pe mi o ea and s o e he
con inuous in o ma ion, as he beha iou o a
sys em. I allows he use o all he powe o
ela ional da abases in model-based diagnosis.
Ou pape has been o ganised as ollows: Sec-
ion 2 p esen s o he ele an p oposals. Sec ion
3 e iews some defini ions in o de o in oduce
he model-bases diagnosis. Sec ion 4 explains how
i is possible o ake ad an age o CDBs in he
de e mina ion o minimal hi ing se s. Sec ion 5
desc ibes he algo i hms o imp o e he diagno-
sis, showing some empi ical esul s. Finally he
conclusions a e p esen ed.
2. BACKGROUND
Rei e (Rei e , 1987) p esen ed one o he fi s
solu ions o he de e mina ion o minimal hi ing
se s using he so-called HS- ees. The p oblem
wi h comple e HS- ees is ha he size o he
ee g ows exponen ially wi h he size o he
collec ion o se s. Minimal hi ing se s can be
efficien ly ob ained by a p uned HS- ee, bu he
cons uc ion o p uned HS- ees is complex due
o unnecessa y esul s a e gene a ed. The HS- ee
was e ised by G eine (G eine e al., 1989) in o
an HS-DAG using a g aph. Among he solu ions
ha use ees, i is possible o find he BHS- ees
ha compu e he hi ing se s wi h a bina y- ee,
o he Wo awa’s p oposal (Wo awa, 2001), whe e
he HST- ee algo i hm is p esen ed. The HST-
ee algo i hm cons uc s he ee in a unique
way, whe e nodes a e o de ed om le o igh
depending on he size o hei edge labels.
O he p e ious wo ks ha e been cen e ed in ci -
cui s diagnosis, as (Hou, 1994) o (S ump ne and
Wo awa, 1997). (Hou, 1994) shows how o a oid
isi ing all subse s. The p oblem was ha his
p oposal skips o e some possible solu ions, and i
was co ec ed in (Han and Lee, 1999), whe e he
numbe o subse s equi ed o be explo ed was also
educed. The algo i hm called s uc u ed-based
abduc ion (SAB) o (Fa ah and Dech e , 1995)
is imp o ed in (S ump ne and Wo awa, 1997),
descending in o he ee o find he possible com-
bina ions which can be esponsible o an inco ec
beha iou .
The de e mina ion o minimal hi ing se s has
also been app oached wi hou using ees. (de la
Banda e al., 2003) p esen s algo i hms o he
de e mina ion o all he minimal unsa isfiable sub-
se o cons ain s. They use p ep ocessing s eps o
educe he size o he se o cons ain s, allowing
hem o sol e la ge p oblems han o he ech-
niques.
3. DEFINITIONS
In o de o ob ain he minimal hi ing se s, some
defini ions a e necessa y:
Defini ion 1. Con ex Se (CS): Any subse o
componen s which compose he sys em. The e a e
2ncomp −1 possible CSs, whe e ncomp is he
numbe o componen s o he sys em.
Defini ion 2. Con ex Ne wo k (CN): A g aph
o med by all he CSs acco ding o he way
p oposed by ATMS (Klee , 1986).
Defini ion 3. Con ex Analy ical Redundancy
Cons ain (CARC): A cons ain de i ed om
he sys em, in such a way ha only obse able
a iables ( a iables wi h senso s) a e ela ed.
Defini ion 4. Obse a ional Model (OM):Ase
o alues o he obse able a iables.
Defini ion 5. Possible Minimal Conflic Con ex s
(PMCC):CSs which ha e one o mo e han one
CARC associa ed, whe e i s subcon ex s a e no
PMCCs.
Defini ion 6. Minimal Conflic Con ex (MCC):
APMCC whose CARCs a e unsa isfiable o
an OM.TheMCCs help us o find ou which
componen s a e ailing.
Defini ion 7. Hi ing Se (HS) o a collec ion o
se s Cis a se H⊆S∈C Ssuch ha Hcon ains
a leas one elemen o each S∈C.AHS o C
is minimal iff no p ope subse o i is a HS o C.
The minimal HSs o a se o MCCs a e o med
by {H1,H2,... Hn}, whe e Hiis a minimal HS
o componen s. The ca dinali y o Hi(|Hi|)is he
numbe o componen s o Hi.
In o de o know he MCC, i is necessa y o
ob ain he CARCs o he sys em. Ou p oposal
uses G ¨obne Bases heo y (Buchbe ge , 1985),
which is he o igin o many symbolic algo i hms
used o manipula e mul iple a iable polynomials.
The main idea is o ha e he se o equali y poly-
nomial cons ain s o he o m P=0,G ¨obne
bases heo y p oduces an equi alen sys em G=0
which has he same solu ion as he o iginal one,
bu subs i u ing some a iables o o he s.
In o de o unde s and he G ¨obne Bases’ ech-
nique be e , Figu e 1 shows a well-know exam-
ple, whe e Mia e mul iplie s, Aia e adde s, and
{a, b, c, d, e, , g}a e he obse able a iables. In
his case, using G ¨obne Bases, an equi alen se
o cons ain s is ob ained:
•CARC−1{ =a∗c+b∗d}: Gene a ed om he
cons ain s o he componen s {M1,M
2,A
1}
•CARC−2{g=b∗d+c∗e}: Gene a ed om he
cons ain s o he componen s {M2,M
3,A
2}
•CARC−3{ −g=a∗c−c∗e}: Gene a ed om he
cons ain s o he componen s {M1,M
3,A
1,A
2}
I a CARC is unsa isfiable o an OM, i means
han one o mo e han one componen ela ed
wi h his CARC is w ong.
M
1
M
2
M
3
A
2
A
1
a
b
c
d
e
x
y
z
g
Fig. 1. A Well-known example o Model-based
Diagnosis
4. CONSTRAINT DATABASES
One o he difficul ies in model-based diagnosis is
handling all he in o ma ion, making he in o ma-
ion pe sis en and eco e able. In his pape we
p opose o s o e all he in o ma ion in a Rela ional
CDB, acili a ing he diagnosis p ocess. I will
allow us o s o e pa ial esul s and imp o e he
diagnosis ask.
Con ex Ne Wo k
(k)IdCon ex : in
IdComponen : in
Componen
(k)IdComponen : in
Name: S ing
E o P obabili y: in
Cons ain Con ex
(k)IdCon ex : in
(k)IdCons ain : in
CARC
(k)IdCons ain : in
Cons ain :Cons ain Obse a ionalModel
(k)IdOM: in
ObsModel: S ing
Unsa is iableCARC
(k)IdOM: in
(k)IdCons ain : in
1..n
1..n
1..n
1..n
1..n
1..1
1..1
0..n
0..n
1..1
Hi ingSe
(k)IdHi ingSe : in
(k)IdComponen s: in
IdMO: in
1..n
1..1
1..n
0..n
Fig. 2. Tables o he Cons ain Da abase
In he Figu e 2, he ables o he CDB a e shown,
and how he in o ma ion is s o ed. The seman ics
o hese ables a e:
(1) Componen : This able con ains he names,
he iden ifie s and he p obabili y o e o o
each componen .
(2) Con ex Ne wo k: This able ep esen s
he CSs ela ing he Componen s. The able
has po en ially 2ncomp −1 combina ions o
elemen s, bu all o hem do no ha e o be
s udied.
(3) CARC: This able s o es all he cons ain s
de i ed om he sys em.
(4) Cons ain Ne wo k: This able ela es he
CSs and he CARCs. Fo example, he con-
ex {M1,M
2,A
1}has he CARC { =a∗
c−b∗d}associa ed.
(5) Obse a ionalModel: This able con ains
he alues o all he obse able a iables.
(6) Unsa isfiableCARC: This able s o es wha
CARCs ail o each OM.
(7) Hi ingSe : This able s o es he compo-
nen s ela ed o he minimal HSs o an OM.
The use o CDBs in he diagnosis p ocess is a
good decision because he e a e cha ac e is ics o
model-based diagnosis ela ed o he ela ional
calculus used in ela ional da abases. Fo exam-
ple, he componen s a e ela ed among hem us-
ing a iables, he CSs and he HSs a e o med
by componen s, he CSs can ha e associa ed
CARCs...All hese ela ions can be ep esen ed
and ea ed in an easy way using CDBs. Also,
i is possible o s o e all he possible ailu es o
he CARCs. I means ha he de e mina ion o
he minimal HSs will be linea in unc ion o
he numbe o CARCs. Fis o all, we can hink
ha i is necessa y o s o e all he possible alues
o OMs. Bu i is no ue, because we only
need o s o e he diffe en ypes o ailu es. Fo
he example shown in Figu e 1, he e a e only
h ee ypes o CARCs’ ailu es o wha e e OM:
{CARC −1; CARC −3},{CARC −2; CARC −3}o
{CARC −1; CARC −2; CARC −3}, o he op ions a e
impossible. This p ocess can be off-line and he
diagnosis o an OM can be on-line and immedi-
a e.
5. THE IMPROVEMENTS
In his Sec ion, we p opose some imp o emen s
o a oid he s udy o all minimal HSs once we
ha e he MCCs o an OM.ThePMCCs a e
only c ea ed once and s o ed in he CDB. In o de
o ob ain he MCCs, he algo i hms desc ibed in
(G´omez-L´opez e al., 2004) a e used, whe e only
he ele an con ex s a e analysed.
In o de o de e mine all he minimal HSs in an
efficien way, we build a bidimensional able ha
ep esen s he ela ions be ween he componen s
and he MCCs ( ableCompsMCCs). I he CDB
had no been used, he ob aining o he in o ma-
ion would be much mo e difficul .
The ableCompsMCCs o he example o Figu e
1 is shown in Table 1, whe e he MCC-i is ela ed
o he CARC-i. Fo his example, all he PMCC
a e MCCs, i means ha all he CARCs a e
unsa isfiable o an OM. The able has 1in he
posi ion {i, j}i he MCC-iis ela ed o he
componen j,and0in o he wise.
M1M2M3A1A2
MCC-1 1 1 0 1 0
MCC-2 0 1 1 0 1
MCC-3 1 0 1 1 1
Table 1. Table o Figu e 1
5.1 Fi s Imp o emen : Sea ching he Rep esen a-
i e Componen s
In his subsec ion, we will s udy how o de e mine
equi alen componen s, p oposing he ollowing
defini ions:
Defini ion 8. MCCs affec ed by a componen c
(MCCsAffec (c)) a e he se o MCCs ha can
ail when he beha iou o componen cis w ong.
Lemma: I a componen Aaffec s he same
MCCs han ano he one B, i means ha i he e
exis s a minimal HS M such as M=A∪N(N
is a se o componen s whe e nei he Ano Bis
included in N) ano he minimal HS M=B∪N
exis s. In his case, i is no necessa y o s udy
bo h possibili ies, only one.
P oo : Le us eason by con adic ion. I Mis a
minimal HS, i means ha Aaffec s some MCCs
which a e no affec ed by nei he componen o N.
I Bdoes no affec he same componen s han A,
i means ha Bcould affec mo e MCCs han
A(Mwould no be minimal), less o diffe en
MCCs han A(Mwould no be a HS). Con a-
dic ion.
Defini ion 9: G oup o Equi alen Componen s
(GEC) is a se o componen s which affec s he
same MCCs. The e o e, i is only necessa y o
s udy one componen o each GEC.
I all he possible minimal HSs a e s udied, i will
be necessa y o analyse 2ncomp −1 possibili ies.
Howe e , using his imp o emen , he numbe o
possible minimal HSs can be educed. Figu e 3
shows o se e al andom examples, he pe cen -
age o he possibili ies elimina ed, s udying only
one componen o each GEC.
0
5
10
15
20
0
20
40
60
0
20
40
60
80
100
Numbe o MCCsNumbe o Componen s
Pe cen age o possible Minimal Hi ing Se s elimina ed (%)
Fig. 3. Pe cen age o possibili ies elimina ed
When he pe cen age is ze o, i means ha all
he GECs ha e only one componen , and he e
a e no componen s which affec he same MCCs.
Figu e 3 also shows how he pe cen age o elim-
ina ions dec eases when he numbe o MCCs
inc eases. I can be explained, due o i he e a e
ew componen s and a lo o MCCs will be less
p obable ha wo componen s affec he same
MCCs.
5.2 Second Imp o emen : Sea ching Single Mini-
mal HSs
Be o e s a ing he analysis o he nex p oposal,
a new case o s udy is going o be in oduced,
because he example shown in Figu e 1 is no
big enough o see all he ypes o p oblems ha
can happen in eal sys ems. The Table 2 shows
he Componen sMCCs able o he new example.
The e a e 8 GECs:{{s0},{s1},{s2,s
3,s
7,s
8,s
11},
{s4},{s5,s
9,s
12,s
14},{s6},{s10,s
13},{s15}}.
s0s1s2s3s4s5s6s7s8s9s10s11s12s13s14s15
MCC-1 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1
MCC-2 1 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1
MCC-3 0 1 1 1 1 1 0 1 1 1 0 1 1 0 1 1
MCC-4 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
MCC-5 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1
Table 2. Table Example
The e is ano he solu ion (de la Banda e al.,
2003), ha looks o minimal single HSs a he
beginning o he HSs de e mina ion. This so-
lu ion de e mines he HSs o one componen
s udying i he e is a componen csuch as {C −
c}is sa isfiable, whe e Cis he se o unsa isfi-
able cons ain s. Ou solu ion does no need o
s udy he sa isfiabili y o he cons ain s, only
de e mines i he e is a componen which affec s
all he MCCs. The eby i a column jonly has
1s, i means ha he componen ep esen ed by
he column jaffec s e e y MCCs and i o ms
a minimal HS o only one componen (single
minimal HS). The e o e his componen will no
be in ol ed in any o he minimal HSs.Inou
example he e is a single minimal HS ({s15}).
The e o e, ou p oblem has been educed om
16 o 7, and he ep esen a i e componen s a e:
{s0,s
1,s
2,s
4,s
5,s
6,s
10}.
5.3 Thi d imp o emen : To a oid s udying edun-
dan o unp omising combina ions o componen s
Be o e con inuing he s udy o minimal HSs,
i is possible o know he g ea es numbe o
componen s o he minimal HSs o a sys em (Max
(|Hi|)). Using he example o Table 2 again, i
is possible o know ha he bigges size o any
minimal HS o he example is 3, because he
componen s ha less affec he MCCs a e s0,s1
and s6. Fo example s0does no affec MCC-1 o
MCC-3, meaning ha in he wo s case only wo
componen s mo e would be necessa y.
Fo his eason, i is possible o gua an ee ha :
Le H={h1,...,h
x}be hi ing se s and
C={c1,...,c
n}be componen s hen
Max(|hi|)=
Numbe o MCCs−Min(|MCCsAffec ed(cj)|)+1
o iin 1 ... x, jin 1 ... n
S a ing wi h he ep esen a i e componen s o
each GEC, we need o combine hese componen s
o know i hey make up a minimal HS, bu
hese combina ions will no be a blind sea ch. Le
{ 1,
2,...,
n}be he ep esen a i e componen s,
he ollowing pseudo-code helps o s o e in he
a iable Hall he minimal HSs o wo compo-
nen s, and in he queue Q he couples o p omising
componen s which a e no HSs will be s o ed.
Fo each couple o componen s { i,
j}|i<j.
I { i,
j}is a minimal HS hen
H:= H∪{ i,
j}
else
I ¬(MCCsAffec ( i)⊂MCCsAffec ( j)) AND
¬(MCCsAffec ( j)⊂MCCsAffec ( i)) hen
Q:= Q∪{ i,
j}
endi
endi
end o each
I { i,
j}is no a minimal HS, bu hese wo
componen s could pa icipa e in a minimal HS
wi h mo e componen s, hey will be included in
Q o u u e sea ches. Bu i he MCCs affec ed
by a componen a e included in he influenced
MCCs o ano he componen , i means ha
hese wo componen s will ne e pa icipa e in a
minimal HS oge he , and hey will no be added
o Q. I (MCCsAffec ( i)⊂MCCsAffec ( j)) o
(MCCsAffec ( j)⊂MCCsAffec ( i)), i means
ha he beha iou o he componen iis included
in j. In o de o gene alise his idea, i is neces-
sa y he ollowing defini ion.
Defini ion 10: Beha iou o a Componen In-
cluded in o he componen s C={ci,...,c
j}(Be-
ha iou Included( ,C)) iff he beha iou o he
componen is included in he componen s cio
... o cj.
In o de o know i MCCsAffec ( ) is included in
MCCsAffec (ci), we use he bina y AND ope a o
be ween he columns and ci.I ( AND ci)= ,
i means ha he beha iou o is a subse o
he cibeha iou . Fo example, he s0beha iou
is included in s2, so hese componen s a e ne e
going o be oge he in a minimal HS.
In ou example, some o he minimal HSs o wo
componen s a e: {(s0,s
4),(s0,s
5),(s1,s
4),(s1,s
5),
(s1,s
10),(s2,s
4),(s2,s
5),(s2,s
6),(s2,s
10),(s4,s
5),(s4,s
6),
(s4,s
10),(s5,s
6),(s5,s
10)}. The es o combina ions
o wo componen s a e added o he queue Q,
because pe haps hey can o m minimal HSs
combining hem wi h o he componen s. Fo ou
example, he couples added o he queue a e:
{(s0,s
1),(s0,s
6),(s1,s
6)}.
The sea ch will no end un il Qis emp y. Wi h
he se o componen s aken ou om Q,we y
o c ea e minimal HSs o n+1 componen s, whe e
nis he numbe o componen s ob ained om Q.
I hese n+ 1 componen s a e no a minimal HS
and (n+1)=(Max (|Hi|)), hese will no be added
o Q.
In o de o a oid possible non minimal HSs, he
algo i hm combines he componen s C aken ou
om he queue C={ci,...,c
j}wi h ano he {ck}
i and only i k>j. The ollowing algo i hm is
execu ed o each o he men ioned possibili ies
and he componen s ob ained om he queue.
I (¬Beha iou Included(ck,C))
I (MinimalHi ingSe (C,ck))
H:= H∪{C∪ck}
else
Q:= Q∪{C∪ck}
endi
endi
In o de o unde s and he abo e algo i hm, i is
necessa y o explain he ollowing me hod:
The MinimalHi ingSe (Componen s C, Compo-
nen c) me hod e u ns ue i C∪cis a mini-
mal HS, a oiding n- uples like {s0,s
1,s
4}. These
h ee componen s a e a HS, bu no a minimal
HS. The idea o he me hod is o de e mine i all
he componen s o a se Ca e essen ial o o m a
minimal HS analysing each MCC.I means ha
i we se aside a componen , he se o emaining
componen s would no be a HS. Fo example, i
we wan o know i {s0,s
1,s
4}is a minimal HS,
he Table 3 will be s udied.
s0s1s4
MCC-1 0 0 1
MCC-2 1 1 1
MCC-3 0 1 1
MCC-4 1 1 0
MCC-5 1 0 1
Table 3. Example o minimal HS
In o de o s o e he indispensable componen s,
we will use a se I={I1,...,In}, such ha i
Iihas one componen , i means ha his com-
ponen is indispensable. Bu i Iihas se e al
componen s, i means ha one o hese com-
ponen s a e indispensable. In gene al he se I
={{si...s
j},{sk...s
h},...,{sl...s
m}} means
ha he indispensable componen s a e {(si∨...∨
sj)∧(sk∨...∨sh)∧(sl∨...∨sm)}.Fo each
MCC,Iwill be modified as ollow:

•I MCC-i is affec ed only by one componen c: I
means ha his componen is indispensable o ob ain
a minimal HS. And Iis upda ed as I:=I∪{c},
whe e cis he indispensable componen .
•I MCC-i is affec ed by a se o mo e han one
componen called C:
·I ∀Ii:i:1...n Ii∩C
=∅⇒I
i:= Ii∩C

·I ∃Ii:i:1...n Ii∩C
=∅⇒I:= I∪C

•MCC-i is affec ed by all he componen s C:Nei he
o hem a e indispensable.
I a e he s udy o all MCCs,I=C, i means
ha Cis a minimal HS. In o he cases Cwould
no be a minimal HS. The ace o he example
shown in Table 3 is:
o MCC-1 : I={s4}
o MCC-2 : I={s4}nei he componen is added
because MCC-2 is affec ed by all componen s
o MCC-3 : I={s4}
o MCC-4 : I={s4},{s0,s
1}
o MCC-5 : I={s4},{s0}
As Idoes no ha e {s0,s
1,s
4},i means ha
no all componen s a e indispensable, he e o e
{s0,s
1,s
4}is no a minimal HS.
Wi h all hese imp o emen s he numbe o pos-
sible minimal HSs is educed in an impo an
way. Figu e 4 shows he pe cen age o he pos-
sibili ies elimina ed wi h his echnique, ela ed
o he fi s imp o emen . And Figu e 5 shows he
compu a ional ime o se e al andom examples,
wi h diffe en numbe o componen s and MCCs.
0
5
10
15
20
0
10
20
30
40
50
20
30
40
50
60
70
80
90
100
Numbe o MCCs
Numbe o Componen s
Pe cen age o possible Minimal Hi ing Se s elimina ed(%)
Fig. 4. Pe cen age o possibili ies elimina ed
0
5
10
15
2
0
0
10
20
30
40
50
0
200
400
600
800
1000
1200
1400
1600
1800
Numbe o MCCs
Numbe o Componen s
Running Time
(ms)
Fig. 5. Execu ion ime(Pen . IV, 512 M memo y)
6. CONCLUSIONS
Ou wo k p oposes o build an equi alen sys em
wi h obse able a iables, which will be gene -
a ed once o each sys em and alida ed o each
OM. Mo eo e , h ee imp o emen s ha e been
p esen ed in o de o a oid he s udy o unp omis-
ing combina ions o componen s.
In o de o s o e all he in o ma ion, we use
a CDB. I allows us o ob ain and s o e he
pa ial da a and all he possible combina ion o
MPCCs and he minimal HSs. I makes possible
o ob ain a diagnosis in linea ime in unc ion o
he numbe o CARCs, because he ob aining o
he minimal HSs can be an off-line p ocess. In
un ime only will be necessa y o alida e each
CARC o know wha MCCs a e ailing, and o
que y he da abase abou he minimal HSs.
REFERENCES
Buchbe ge , B. (1985). G ¨obne bases: An algo-
i hmic me hod in polynomial ideal heo y.
D. Reidel Publishing Co.. pp. 184–232.
de la Banda, M. G., P. J. S uckey and J. Wazny
(2003). Finding all minimal unsa isfiable sub-
se s. In: PPDP ’03. ACM P ess. pp. 32–43.
Fa ah, Yous i El and Rina Dech e (1995). Di-
agnosing ee-decomposable ci cui s.. In: IJ-
CAI. pp. 1742–1749.
G´omez-L´opez, M. T., R. Ceballos, R. M. Gasca
and C. Del Valle (2004). Cons ain da abases
echnology o polynomial models diagnosis..
In: 15 h In e na ional Wo kshop on P inci-
ples o Diagnosis. pp. 215–220.
G eine , R., B. A. Smi h and R. W. Wilke son
(1989). A co ec ion o he algo i hm in e-
i e ’s heo y o diagnosis. Vol. 41. Else ie
Science Publishe s L d. pp. 79–88.
Han, B. and S. Lee (1999). De i ing minimal
conflic se s by cs- ees wi h ma k se in
diagnosis om fi s p inciples. Vol. 29-2.
Hou, Aimin (1994). A heo y o measu emen
in diagnosis om fi s p inciples. Vol. 65.
Else ie Science Publishe s L d.. pp. 281–328.
Klee , J. De (1986). An assump ion-based u h
main enance sys em. Vol. 2. pp. 127–161.
Kupe , G., L. Libkin and J. Pa edaes (1998).
Cons ain Da abases. Sp inge .
Rei e , R. (1987). A heo y o diagnosis om fi s
p inciples. Vol. 1. pp. 57–96.
Re esz, P. (2002). In oduc ion o cons ain
da abases. Sp inge -Ve lag New Yo k, Inc..
New Yo k, NY, USA.
S ump ne , Ma kus and F anz Wo awa
(1997). Diagnosing T ee-S uc u ed Sys ems.
Nagoya, Japan.
Wo awa, F anz (2001). A a ian o ei e ’s
hi ing-se algo i hm.. Vol. 79. pp. 45–51.