Que y Con ainmen Wi h Nega ed IDB P edica es (Ex ended
Ve sion)
Ca les Fa é, E nes Tenien e and Toni U pí
Uni e si a Poli ècnica de Ca alunya
08034 Ba celona, Ca alonia
[ a e | enien e | u pi]@lsi.upc.es
Abs ac . We p esen a me hod ha checks Que y Con ainmen o que ies wi h nega ed IDB
p edica es. Exis ing me hods ei he deal only wi h es ic ed cases o nega ion o do no check
ac ually con ainmen bu uni o m con ainmen , which is a su icien bu no necessa y
condi ion o con ainmen . Addi ionally, ou que ies may also con ain equali y, inequali y and
o de compa isons. The gene ali y o ou app oach allows ou me hod o deal s aigh o wa dly
wi h que y con ainmen unde cons ain s. Ou me hod is sound and comple e bo h o success
and o ailu e and we cha ac e ize he da abases whe e hese p ope ies hold. We also s a e he
class o que ies ha can be decided by ou me hod.
1 In oduc ion
Que y Con ainmen (QC) is he p oblem conce ned wi h checking whe he he answe s ha a que y
ob ains a e a subse o he answe s ob ained by ano he que y o e e y da abase. QC Checking is applied
as a base echnique in se e al con ex s: que y op imiza ion [Ull89], ew i ing que ies using iews
[Hal01], de ec ing independence o que ies om da abase upda es [LS93], cons ain e i ica ion
[GSUW94, LR98], e c.
QC was i s s udied o he class o conjunc i e que ies [CM77, CR97]. QC o conjunc i e que ies
wi h o de compa isons was s udied in [Klu88, LS93, Ull97]. Conjunc i e QC wi h sa e nega ed EDB
a oms was in es iga ed in [LS93, Ull97, WL03]. EDB s ands o ex ensional da abase, ha is, he
da abase’s s o ed ela ions whe eas IDB means in ensional da abase, ha is, he ela ions cons uc ed by
deduc i e ules.
The me hods ha deal wi h nega ed IDB subgoals can be classi ied in o wo di e en app oaches. The
i s one is aken by hose me hods ha check QC o que y classes whe e nega ion is used in a es ic i e
way [HMSS01, LS95]. The second app oach is ep esen ed by hose me hods ha do no check “ ue” QC
bu ano he ela ed p ope y called Uni o m QC [LS93, DS96], which is a su icien bu no necessa y
condi ion o QC [Sag88].
When conside ing in eg i y cons ain s, he con ainmen ela ionship be ween wo que ies does no
need o hold o any s a e o he da abase bu only o hose ha sa is y he in eg i y cons ain s. This idea
is cap u ed by he no ion o Que y Con ainmen unde Cons ain s (QCuC). QCuC checking was
in es iga ed o conjunc i e que ies unde in eg i y cons ain s exp essing unc ional dependencies
[ASU79, JK84], inclusion dependencies [JK84] o objec da abase schemas [Cha92, BJNS94, LS97]; o
da alog que ies, wi hou nega ion, unde in eg i y cons ain s exp essing uple-gene a ing dependencies
was add essed in [Sag88, DS96] by aking he uni o m con ainmen app oach; and also in he con ex o
hyb id sys ems combining conjunc i e o da alog que ies and cons ain s exp essed in a Desc ip ion
Logic language [BJNS94, LR96, CDL98].
In [FTU99] we ske ched a me hod, named Cons uc i e Que y Con ainmen me hod (CQC o sho ),
o check “ ue” QC and QCuC in he p esence o nega ion on IDB subgoals. In ui i ely, he aim o ou
CQC me hod was o cons uc a coun e example ha p o es ha he e is no QC (o QCuC). This me hod
2 Ca les Fa é, E nes Tenien e and Toni U pí
used di e en Va iable Ins an ia ion Pa e ns (VIPs), acco ding o he syn ac ic p ope ies o he que ies
and he da abases conside ed in each es . Such a cus omiza ion only a ec s he way ha he ac s o be
pa o he coun e example a e ins an ia ed. The aim was o p une he sea ch o he coun e example by
gene a ing only he ele an ac s.
We ex end he e ou p e ious wo k by:
− p o iding no jus an in ui i e idea bu also he ull o maliza ion o he CQC me hod.
− p o ing wo addi ional heo ems ha hold when he e a e no ecu si ely de ined IDB ela ions:
ailu e soundness, which gua an ees ha con ainmen holds i he me hod e mina es wi hou
building any coun e example; and ailu e comple eness, which ensu es ha i con ainmen holds
be ween wo que ies hen ou me hod ails ini ely (and e mina es).
− ensu ing e mina ion when checking con ainmen o conjunc i e que ies wi h sa e EDB nega ion
and buil -in li e als.
− showing ha he CQC me hod is no less e icien han o he me hods ha deal wi h conjunc i e
que ies wi h o wi hou sa e EDB nega ion. We p opose an addi ional VIP, he simple VIP, o
pe o m such a compa ison.
− decomposing he Gene al VIP in wo: he disc e e o de VIP and he dense o de VIP ha allow
us o deal wi h buil -in li e als assuming bo h disc e e and dense o de domains.
I ollows om hese new esul s ha he me hod we p opose he e imp o es p e iously p oposed
algo i hms since i p o ides an e icien decision p ocedu e o known decidable cases and can also be
applied o mo e gene al o ms o que ies ha we e no handled by p e ious algo i hms. In hese mo e
gene al cases ou me hod is semidecidable because i can no be gua an eed e mina ion unde he
p esence o in ini e coun e examples. Ne e heless, i he e is a ini e coun e example ou me hod inds i
and e mina es and i con ainmen holds ou me hod ails ini ely and e mina es.
Sec ion 2 se s he base concep s used h ough he pape . In Sec ion 3, we in oduce ou me hod and
Sec ion 4 o malizes i . In Sec ion 5, we p esen he main co ec ness esul s o ou me hod. In Sec ion 6,
we discuss he decidabili y issues ega ding ou me hod. In Sec ion 7, we compa e ou me hod wi h
ela ed wo k. The pape ends wi h he conclusions, Sec ion 8, and e e ences. Fo a mo e de ailed
o maliza ion and de ailed p oo s, we e e o [FTU02].
2 Base Concep s
A deduc i e ule has he o m:
p(X
¯
) ← 1(X
¯
1) ∧ … ∧ n(X
¯
n) ∧ ¬ n+1(Y
¯
1) ∧ … ∧ ¬ m(Y
¯
s) ∧ C1 ∧… ∧ C
whe e p and 1, …, m a e p edica e (also called ela ion) names. The a om p(X
¯
) is called he head o he
ule, and 1(X
¯
1), …, n(X
¯
n), ¬ n+1(Y
¯
1), …, ¬ m(Y
¯
s) a e he posi i e and nega i e o dina y li e als in he body
o he ule. The uples X
¯
, X
¯
1, …, X
¯
n, Y
¯
1, …, Y
¯
s con ain e ms, which a e ei he a iables o cons an s. Each
Ci is a buil -in li e al in he o m o A1 θ A2, whe e A1 and A2 a e e ms. Ope a o θ is <, =, >, =, = o ?.
We equi e ha e e y ule be sa e, ha is, e e y a iable appea ing in X
¯
, Y
¯
1, …, Y
¯
s, C1 , … o C mus also
appea in some X
¯
i.
The p edica e names in a deduc i e ule ange o e he ex ensional da abase (EDB) p edica es, which
a e he ela ions s o ed in he da abase, and he in ensional da abase (IDB) p edica es (like p abo e),
which a e he ela ions de ined by he deduc i e ules. EDB p edica es mus no appea in he head o a
deduc i e ule.
A se o deduc i e ules P is hie a chical i he e is a pa i ion P = P1 ∪ … ∪ Pn such ha o any
o dina y a om (X
¯
) occu ing posi i ely o nega i ely (as ¬ (X
¯
)) in he body o a clause in Pi, he
de ini ion o is con ained wi hin Pj wi h j < i. No e ha a hie a chical se o deduc i e ules con ains no
ecu si e de ini ions abou IDB ela ions.
Que y Con ainmen Wi h Nega ed IDB P edica es (Ex ended Ve sion) 3
A condi ion has he denial o m o :
← 1(X
¯
1) ∧ … ∧ n(X
¯
n) ∧ ¬ n+1(Y
¯
1) ∧ … ∧ ¬ m(Y
¯
s) ∧ C1 ∧… ∧ C
whe e 1(X
¯
1), …, n(X
¯
n), ¬ n+1(Y
¯
1), …, ¬ m(Y
¯
s) a e he (posi i e and nega i e) o dina y li e als; and C1, …,
C a e buil -in li e als. I Z
¯
is he se o he a iables occu ing in in Y
¯
1, …, Y
¯
s, C1 , … o C , he we equi e
ha each a iable in Z
¯
mus also occu in some X
¯
i. Roughly, a condi ion in denial o m exp esses a
p ohibi ion: a conjunc ion o ac s (li e als in he body) ha mus no hold on he da abase all a once.
The e o e, a condi ion is iola ed (no sa is ied), whene e ∃Z
¯
( 1(X
¯
1) ∧ … ∧ n(X
¯
n) ∧ ¬ n+1(Y
¯
1) ∧ … ∧
¬ m(Y
¯
s) ∧ C1 ∧… ∧ C ) is ue on he da abase.
A que y Q is a ini e se o deduc i e ules ha de ines a dedica ed n-a y que y p edica e q. Wi hou
loss o gene ali y, o he p edica es han q appea ing in Q a e EDB o IDB p edica es.
A que y Q1 is con ained in a que y Q2, deno ed by Q1 S Q2, i he se o answe s o Q1(D) is a subse o
hose o Q2(D) o any da abase D. Mo eo e , Q1 is con ained in Q2 w IC, deno ed by Q1 SIC Q2, i he
se o answe s o Q1(D) is a subse o hose o Q2(D) o any da abase D sa is ying a ini e se IC o
condi ions (in eg i y cons ain s).
3 The Cons uc i e Que y Con ainmen (CQC) Me hod
The con ainmen ela ionship be ween wo que ies mus hold o he whole se o possible da abases in
he gene al case. A sui able way o checking QC is o check he lack o con ainmen , ha is, o ind jus
one da abase whe e he con ainmen ela ionship ha we wan o check does no hold: Q1 is no con ained
in Q2, w i en Q1 c Q2, i he e is a leas one da abase D such ha Q1(D) ⊄ Q2(D).
Gi en Q1 and Q2 wo que ies, he CQC me hod is add essed o cons uc he ex ensional pa o a
da abase (EDB) whe e he con ainmen ela ionship does no hold. I equi es wo main inpu s: he goal o
a ain and he se o condi ions o en o ce. Ini ially, he goal is de ined G0 = ← q1(X1, ..., Xn) ∧ ¬q2(X1, ...,
Xn), meaning ha we wan o cons uc a da abase whe e (X1, ..., Xn) could be ins an ia ed in such a way
ha q1(X1, ..., Xn) is ue and q2(X1, ..., Xn) is alse. The se o condi ions o en o ce is F0 = ∅, meaning ha
he e is no ini ial in eg i y cons ain o ake ca e abou .
When conside ing a se IC o in eg i y cons ain s, we say ha Q1 is no con ained in Q2 w IC, w i en
Q1 cIC Q2, i he e is a leas one da abase D sa is ying IC, such ha Q1(D) ⊄ Q2(D). In his case, he EDB
ha he CQC me hod has o cons uc o e u e he con ainmen ela ionship mus also sa is y he
condi ions in IC. This is gua an eed by making he ini ial se o condi ions o en o ce F0 = IC oge he
wi h he goal G0 = ← q1(X1, ..., Xn) ∧ ¬q2(X1, ..., Xn).
3.1 Example: Q1 c Q2
The ollowing example is adap ed om he one in [FTU99] by in oducing double nega ion on IDB
p edica es. I allows illus a ing he main ideas o ou me hod and o show i s beha io unde hese
complex cases. Le Q1 and Q2 be wo que ies:
Q1 = { sub1(X) ← emp(X) ∧ ¬chie (X) }
Q2 = { sub2(X) ← emp(X) ∧ ¬boss(X) }
whe e emp is an EDB p edica e and chie and boss a e IDB p edica es de ined by a se DR o deduc i e
ules:
DR = {boss(X) ← wo ksFo (Z, X)
chie (X) ← wo ksFo (Y, X) ∧ ¬boss(Y) }
whe e wo ksFo is ano he EDB p edica e.
4 Ca les Fa é, E nes Tenien e and Toni U pí
In ui i ely, we can see ha Q1 is less es ic i e han Q2 because Q2 does no e ie e hose employees
ha ing anyone wo king o hem, while Q1 allows e ie ing employees ha ing some boss wo king o
hem. Hence, we can ind a da abase con aining EDB ela ions such as emp(joan), wo ksFo (ma y, joan)
and wo ksFo (ann, ma y), whe e sub1(joan) is ue bu sub2(joan) is alse (chie (joan) is alse because
boss(ma y) is ue whe eas boss(joan) is ue). The e o e, Q1 is no con ained in Q2. No e ha an e en
smalle EDB con aining jus emp(joan) and wo ksFo (joan, joan) would ha e lead us o he same
conclusion.
A CQC-de i a ion ha cons uc s an EDB ha p o es Q1 c Q2 a e shown in igu e 3.1. Each ow on
he igu e co esponds o a CQC-node ha con ains he ollowing in o ma ion (columns):
1. The goal o a ain: he li e als ha mus be made ue by he EDB unde cons uc ion. When he
goal is [] i means ha no li e al needs o be sa is ied. He e, he ini ial CQC-node con ains he
goal G0 = ← sub1(X) ∧ ¬sub2(X). Tha is, we wan he CQC me hod o cons uc a da abase whe e
exis s a leas a cons an k such ha bo h sub1(k) and ¬sub2(k) a e ue
2. The condi ions o be en o ced: he se o condi ions ha he cons uc ed EDB is equi ed o
sa is y. Recall ha a condi ion is iola ed whene e all o i s li e als a e e alua ed as ue. He e,
he ini ial CQC-node con ains he se o condi ions o en o ce F0 = ∅.
3. The EDB unde cons uc ion. The ini ial CQC-Nodes has always an emp y EDB.
4. The condi ions o be main ained: he se con aining hose condi ions ha a e known o be sa is ied
in he cu en CQC-node and ha mus emain sa is ied un il he end o he CQC-de i a ion.
Ini ial CQC-Nodes ha e always his se emp y.
5. The accoun o cons an s in oduced in he cu en and/o he ances o CQC-nodes o ins an ia e
he EDB ac s in he EDB unde cons uc ion. Ini ially, such a se con ains always he cons an s
appea ing al eady in DR∪Q1∪Q2∪G0∪F0.
The ansi ion be ween wo consecu i e CQC-nodes, i.e. be ween an ances o node and i s successo , is
a CQC-s ep ha is pe o med by applying a CQC-expansion ule o a selec ed li e al o he ances o CQC-
node. The selec ion o li e als in he CQC-de i a ion o igu e 3.1 is nea ly a bi a y: he only necessa y
c i e ion is o a oid picking a non-g ound nega i e-o dina y o buil -in li e al. In igu e 3.1, he CQC-
s eps a e labeled wi h he name o he CQC-expansion ule ha is applied and he selec ed li e al in each
s ep is unde lined. We e e o Sec ion 4.2 o a p ope o maliza ion o he CQC-expansion ules.
The i s s ep un olds he selec ed li e al, he IDB a om sub1(X) om he goal pa , by subs i u ing i
wi h he body o i s de ining ule. A he second s ep, he selec ed li e al om he goal pa is emp(X),
which is a posi i e EDB li e al. To ge a success ul de i a ion, i.e. o ob ain an EDB sa is ying he ini ial
goal, emp(X) mus be ue on he cons uc ed EDB. Hence, he me hod ins an ia es X wi h a cons an and
includes he new g ound EDB ac in he EDB unde cons uc ion. The p ocedu e assigns an a bi a y
cons an o X, e.g. 0. So emp(0) is he i s ac included in he EDB unde cons uc ion.
¬chie (0) is he selec ed li e al in s ep 3. To ge success o he de i a ion, chie (0) mus no be ue on
he EDB. This is gua an eed by adding ← chie (0) as a new condi ion o be en o ced. S ep 4 is simila o
s ep 3, yielding ← sub2(0) o be conside ed as ano he condi ion o be en o ced. A e pe o ming his
la e s ep, we ge a CQC-node wi h a goal like []. Howe e , he wo k is no done ye , since we mus
ensu e ha he wo condi ions ← sub2(0) and ← chie (0) a e no iola ed by he cu en EDB. In o he
wo ds, we mus make bo h chie (0) and sub2(0) alse.
S ep 5 un olds he selec ed li e al chie (0) om one o he wo condi ions, ge ing ← wo ksFo (Y, 0) ∧
¬boss(Y) as a new condi ion ha eplaces ← chie (0). A leas one o he wo li e als o his condi ion
mus be alse. In s ep 6, he selec ed li e al is he posi i e EDB li e al is wo ksFo (Y, 0). Since i ma ches
wi h no EDB a om in he EDB unde cons uc ion, wo ksFo (Y, 0) is alse and, consequen ly, he whole
condi ion ← wo ksFo (Y, 0) ∧ ¬boss(Y) is no iola ed by he cu en EDB. Fo his eason, such a
condi ion is mo ed om he se o condi ions o en o ce o he se o condi ions o main ain.
Que y Con ainmen Wi h Nega ed IDB P edica es (Ex ended Ve sion) 5
S ep 7 un olds he selec ed IDB a om sub2(0) om he emaining condi ion o en o ce. The EDB a om
emp(0) is he selec ed li e al in s ep 8. Since emp(0) is also p esen in he EDB unde cons uc ion, i
canno be alse. So his li e al is d opped om he condi ion because i does no help o en o ce he
condi ion. In s ep 9 he selec ed li e al is he nega i e li e al ¬boss(0). Since i is he only li e al o he
condi ion, i mus be made alse necessa ily. So boss(0) becomes a new (sub)goal o achie e and is
ans e ed, hus, o he goal pa .
{emp
(0)}
←
sub
1
(
X
)
∧
¬
sub
2
(
X
)
←
emp(X)
∧
¬chie (X)
∧
¬
sub
2
(
X
)
←
¬chie (0)
∧
¬sub2(0)
Goal o a ain
{
←
emp(0)
∧
¬boss(0) }
←
boss(0)
{
←
chie (0)}
{
←
¬boss(0)}
∅
{emp
(0)}
{emp
(0)}
{emp
(0)}
{emp
(0)}
{emp
(0)}
[] {emp(0),
wo ksFo (0,
0)}
[]
EDB
Condi ions
o man ain
1:A1
←
wo ksFo (Z,0)
∅
[]
∅
{
←
wo ksFo (Y,0)
∧
¬boss(Y),
← sub2(0) }
{
←
wo ksFo (Y,0)
∧
¬
boss
(
Y
)}
{
←
sub2(0)}
{
←
wo ksFo (Y,0)
∧
¬boss(Y)}
←
boss
(0)
←
wo ksFo (Z,0)
∅
∅
∅
{emp(0),
wo ksFo
(0,0)}
{emp(0),
wo ksFo
(0,0)}
{emp(0),
wo ksFo
(0,0)}
{
emp
(0)}
{
emp
(0)}
∅
∅
{emp(0),
wo ksFo
(0,0)}
[]
[]
[]
[]
←
¬sub2(0)
{
←
wo ksFo (Y,0)
∧
¬
boss
(
Y
)}
{
←
wo ksFo (Y,0)
∧
¬
boss
(
Y
)}
{
←
wo ksFo
(
Y
,0)
∧
¬
boss
(
Y
)}
{
←
wo ksFo (Y,0)
∧
¬
boss
(
Y
)}
{
←
wo ksFo (Y,0)
∧
¬
boss
(
Y
)}
{
←
wo ksFo (Y,0)
∧
¬
boss
(
Y
)}
{
←
wo ksFo (Y,0)
∧
¬
boss
(
Y
)}
{
←
wo ksFo (Y,0)
∧
¬
boss
(
Y
)}
∅
∅
∅
∅
∅
{
←
¬
boss
(0)
}
5:B1
2:A2
3:A3
6:B2
7:B1
8:B2
9:B3
10:A1
11:A2
15:A2
12:B2
13:B3
14:A1
{
←
chie
(0)
,
←
sub
2
(0)}
{
emp
(0)}
∅
4:A3
[]
∅
∅
∅
Condi ions
o en o ce
Used
cons an s
∅
∅
{ 0 }
{ 0 }
{
0 }
{
0 }
{
0 }
{ 0 }
{ 0 }
{ 0 }
{ 0 }
{ 0 }
{
0 }
{
0 }
{
0 }
{
0 }
Fig. 3.1.
S ep 10 un olds he selec ed li e al boss(0) om he goal pa as in s ep 1. wo ksFo (z, 0) is he selec ed
li e al in s ep 11. As in s ep 2, he me hod should ins an ia e Z wi h a cons an . In his case, he chosen
cons an is 0 again, so wo ksFo (0, 0) is added o he EDB unde cons uc ion. Mo eo e , he condi ion
← wo ksFo (Y, 0) ∧ ¬boss(Y) is mo ed back o he se o condi ions o en o ce o a oid ha he new
inclusion o wo ksFo (0, 0) in he EDB iola es i .
In s ep 12, he selec ed li e al is he posi i e EDB li e al is wo ksFo (Y, 0) om he emaining
condi ion o en o ce. Now, i ma ches wi h he cu en con en s o he EDB wi h Y = 0. As in s ep 8, such
a li e al is d opped om he condi ion. Howe e , he whole condi ion ← wo ksFo (Y, 0) ∧ ¬boss(Y) is
6 Ca les Fa é, E nes Tenien e and Toni U pí
mo ed again o he se o condi ions o main ain in o de o p e en u he inclusions o new ac s abou
wo ksFo in he EDB om iola ing i .
S eps 13 and 14 a e iden ical o s eps 9 and 10. In s ep 15, he cons an 0 is selec ed again o ins an ia e
wo ksFo (Z, 0). Since wo ksFo (0, 0) is al eady included in he EDB, he e is no need o ans e back
any condi ion om he se o condi ions o main ain o he se o condi ions o en o ce.
The CQC-de i a ion ends success ully since i eaches a CQC-node whe e he goal o a ain is [] and
he se o condi ions o sa is y is emp y. In o he wo ds, we can be su e ha i s EDB, {emp(0),
wo ksFo (0, 0)}, con ains a se o ac s ha makes he da abase sa is y he goals and condi ions o all
p eceding CQC-nodes, including, na u ally, he i s CQC-node. Then we conclude Q1 c Q2.
3.2 Va iable Ins an ia ion Pa e ns
When a CQC-de i a ion e mina es success ully, we ob ain a p oo , he cons uc ed EDB, which shows
ha he con ainmen ela ionship is no ue. On he con a y, when a de i a ion ends unsuccess ully, ha
is, i e mina es bu i ails o cons uc a coun e example, we canno conclude ha con ainmen holds
based on a single esul . Then he ques ion is how many de i a ions mus be conside ed be o e achie ing
a eliable conclusion. Indeed, a he han he accoun o all possible de i a ions, he eal poin is o know
how many a iable ins an ia ion al e na i es mus be conside ed when adding new ac s o he EDB unde
cons uc ion. Since he se o possible combina ions o al e na i e cons an assignmen s o ins an ia e
EDB ac s is wha de e mines he se o di e en EDBs ha can be cons uc ed.
The aim o he CQC me hod is o es only he a iable ins an ia ions ha a e ele an wi hou losing
comple eness. The “s a egy” o ins an ia ing he EDB ac s o be included in he EDB unde
cons uc ion is connec ed o, indeed i is inspi ed by, he concep o canonical da abases ound in [Klu88,
LS93, Ull97]. This concep is based on he idea ha i is no necessa y o check he whole (in ini e) se o
possible EDBs o p o e con ainmen bu only a ( ini e) subse o hem, he se o canonical EDBs. In his
way, i i is p o ed ha a con ainmen ela ionship holds on any canonical EDB, hen QC holds o any
EDB. The soundness o his app oach is gua an eed by p o ing ha any possible EDB is ep esen ed by
one canonical EDB and ha his co espondence p ese es he con ainmen ela ionship.
In con as o [Klu88, LS93, Ull97], ou me hod does no need o gene a e he whole se o canonical
da abases in ad ance. Ou con ainmen es s end as soon as a success ul a CQC-de i a ion leading o a
canonical coun e example is ound. I is only in he wo s case, when no coun e example exis s, when he
comple e ee o ailed CQC-de i a ions will ha e es e e y canonical da abase. Howe e , e en in his
case, ec ea ing comple ely each canonical da abase may no be always equi ed be o e disca ding i
since, o ins ance, i is ea ly de ec ed ha some condi ion is iola ed wi h no possible epai .
Since he canonical da abases o be aken in o accoun depend on he conc e e subclass o que ies ha
a e conside ed, we dis inguish h ee di e en a iable ins an ia ion pa e ns, VIPs o sho hand. Each o
hem de ines how he CQC me hod has o ins an ia e he EDB ac s o be added o he EDB unde
cons uc ion. The ollowing h ee VIPs a e o malized in Appendix A: Simple VIP, Nega ion VIP (as
conside ed in [FTU99]), Dense O de VIP and Disc e e O de VIP.
The CQC me hod uses he Simple VIP when checking con ainmen bu no QC unde cons ain s.
Mo eo e , he deduc i e ules de ining que y p edica es as well as IDB p edica es mus sa is y he
ollowing condi ions: hey mus no ha e any nega i e o buil -in li e al1 in hei ule bodies; hey mus
no ha e cons an s in hei heads; and hey mus no ha e any a iable appea ing wice o mo e imes in
hei heads. Acco ding o he Simple VIP, each dis inc a iable is bound o a dis inc new cons an .
The CQC me hod uses he Nega ion VIP when checking QCuC o when checking con ainmen unde
he p esence o nega ed IDB subgoals, nega ed EDB subgoals and/o (in)equali y compa isons (=, ?). In
1 Howe e , no e ha i a deduc i e ule has a li e al o he o m z = k o z = x in i s body such ha z does no appea in he head,
hen ha li e al can be omi ed by eplacing each occu ence o z in he ule body by k o x, espec i ely.
Que y Con ainmen Wi h Nega ed IDB P edica es (Ex ended Ve sion) 7
any case, o de compa isons (<, =, >, =) a e no allowed. EDBs gene a ed and es ed wi h his VIP
co espond o he canonical EDBs conside ed in [LS93, Ull97] o he conjunc i e que y case wi h
nega ed EDB subgoals. The in ui ion behind his VIP is clea : Each new a iable appea ing in a EDB ac
o be g ounded is ins an ia ed wi h ei he some cons an p e iously used o a cons an ne e used be o e.
This is he pa e n used in he CQC-de i a ion showed in he igu e 3.1.
The o he wo VIPs, Dense O de VIP and Disc e e O de VIP, a e applied when he e a e o de
compa isons (<, =, >, =) in he deduc i e ules, wi h o wi hou nega ion. In his case, each dis inc
a iable mus be bound o a cons an acco ding o ei he a o me o a new loca ion in he o al linea
o de o cons an s in oduced p e iously [Klu88, LS93, NSS98, Ull97]. The elec ion be ween o apply
ei he he Dense O de VIP o he Disc e e O de VIP depends on whe he he compa isons a e
in e p e ed on a dense o de (e.g. a ional and eal numbe s) o on a disc e e o de (e.g. in ege numbe s).
4 Fo maliza ion O The CQC Me hod
Le Q1 and Q2 be wo que ies, DR he se o deduc i e ules de ining he da abase IDB ela ions and IC a
ini e se o condi ions exp essing he da abase in eg i y cons ain s. I he CQC me hod pe o ms a
success ul CQC-de i a ion om (← q1(X1, ..., Xn) ∧ ¬q2(X1, ..., Xn) ∅ ∅ ∅ K) o ([] ∅ T C K’) hen Q1 c
Q2, whe e K is he se o cons an s appea ing in DR∪Q1∪Q2. Mo eo e , i he CQC me hod pe o ms a
success ul CQC-de i a ion om (← q1(X1, ..., Xn) ∧ ¬q2(X1, ..., Xn) IC ∅ ∅ K’’) o ([] ∅ T C K’’’) hen
Q1 cIC Q2, whe e K’’ is he se o cons an s appea ing in DR∪Q1∪Q2∪IC.
CQC-de i a ions s a om a 5- uple (G0 F0 T0 C0 K0) consis ing o he goal G0 = ← q1(X1, ..., Xn) ∧
¬q2(X1, ..., Xn), he se o condi ions o en o ce F0 = ∅ o IC, he ini ially-emp y EDB T0 = ∅, he emp y
se o condi ions o main ain C0 = ∅ and he se K0 o cons an alues appea ing in DR∪Q1∪Q2[∪IC].
A success ul CQC-de i a ion eaches a 5- uple (Gn Fn Tn Cn Kn) = ([] ∅ T C K’), whe e he emp y goal
Gn = [] means ha we ha e eached he goal G0 we we e looking o . The emp y se Fn = ∅ means ha no
condi ion is wai ing o be sa is ied. Tn = T is an EDB ha sa is ies G0 as well as F0. Cn = C is a se o
condi ions eco ded along he de i a ion and ha T also sa is ies. Kn = K’ is he se o cons an alues
appea ing in DR∪Q1∪Q2[∪IC]∪T.
On he con a y, i e e y “ ai ” CQC-de i a ion s a ing om (← q1(X1, ..., Xn) ∧ ¬q2(X1, ..., Xn) ∅
[∪IC] ∅ ∅ K) is ini e bu does no each ([] ∅ T C K’), i will mean ha no EDB sa is ies he goal G0 =
← q1(X1, ..., Xn) ∧ ¬q2(X1, ..., Xn) oge he wi h he se o condi ions F0 = ∅ [∪IC], concluding ha Q1 S
Q2 (Q1 SIC Q2). Sec ion 5 below p o ides he comple e esul s and p oo s ega ding he soundness and
comple eness o he CQC me hod.
4.1 CQC-Nodes, CQC-T ees and CQC-De i a ions
Le Q1 and Q2 be wo que ies, DR be he se o deduc i e ules de ining he da abase IDB ela ions and IC
be a ini e se o condi ions exp essing he da abase in eg i y cons ain s. A CQC-node is a 5- uple o he
o m (Gi Fi Ti Ci Ki), whe e Gi is a goal o a ain; Fi is a se o condi ions o en o ce; Ti is a se o g ound
EDB a oms, an EDB unde cons uc ion; Ci is a se o condi ions ha a e cu en ly sa is ied in Ti and mus
be main ained; and Ki is he se o cons an s appea ing in R = DR∪Q1∪Q2[∪IC] and Ti.
A CQC- ee is induc i ely de ined as ollows:
1. The ee consis ing o he single CQC-node (G0 F0 ∅ ∅ K) is a CQC- ee.
2. Le E be a CQC- ee, and (Gn Fn Tn Cn Kn) a lea CQC-node o E such ha Gn ? [] o Fn ? ∅. Then
he ee ob ained om E by appending one o mo e descendan CQC-nodes acco ding o a CQC-
expansion ule applicable o (Gn Fn Tn Cn Kn) is again a CQC- ee.
I may happen ha he applica ion o a CQC-expansion ule on a lea CQC-node (Gn Fn Tn Cn Kn) does
no ob ain any new descendan CQC-node o be appended o he CQC- ee because some necessa y
8 Ca les Fa é, E nes Tenien e and Toni U pí
cons ain de ined on he CQC-expansion ule is no sa is ied. In such a case, we say ha (Gn Fn Tn Cn Kn)
is a ailed CQC-node.
Each b anch in a CQC- ee is a CQC-de i a ion consis ing o a ( ini e o in ini e) sequence (G0 F0 T0
C0 K0), (G1 F1 T1 C1 K1), … o CQC-nodes.
A CQC-de i a ion is ini e i i consis s o a ini e sequence o CQC-nodes; o he wise i is in ini e. A
CQC-de i a ion is success ul i i is ini e and i s las (lea ) CQC-node has he o m ([] ∅ Tn Cn Kn). Tha
is, bo h he goal o a ain and he se o condi ions o sa is y a e emp y. A CQC-de i a ion is ailed i i is
ini e and i s las (lea ) CQC-node is ailed.
A CQC- ee is success ul when a leas one o i s b anches is a success ul CQC-de i a ion. A CQC- ee
is ini ely ailed when each one o i s b anches is a ailed CQC-de i a ion.
Table 4.1. CQC-expansion ules: A#- ules.
A1) P(Gi) = d(X
¯
) is a posi i e IDB a om:
(Gi Fi Ti Ci Ki)
(Gi+1,1 Fi Ti Ci Ki) | … | (Gi+1,m Fi Ti Ci Ki)
only i m ≥ 1 and each Gi+1,j is he esol en o Gi and some deduc i e ule d(Y
¯
) ← M1
∧…∧ Mq in R.
A2) P(Gi) = b(X
¯
) is a posi i e EDB a om:
(Gi Fi Ti Ci Ki)
((Gi b(X
¯))σ1 Fi+1,1 Ti+1,1 Ci+1,1 Ki+1,1) | … | ((Gi b(X
¯))σm Fi+1,m Ti+1,j Ci+1,m Ki+1,m)
such ha Fi+1,j = Fi∪Ci, Ti+1,j = Ti∪{b(X
¯
)σj} and Ci+1,j = ∅ i b(X
¯)σj ∉ Ti; o he wise Fi+1,j
= Fi, Ti+1,j = Ti and Ci+1,j = Ci. Each σj is one ou o m possible dis inc g ound
subs i u ions, ob ained ia a a iable ins an ia ion p ocedu e om ( a s(X
¯
), ∅, Ki) o (∅,
σj, Ki+1,j) acco ding o he app op ia e a iable ins an ia ion pa e n, ha assigns a
cons an om Ki+1,j o each a iable in a s(X
¯). See mo e de ails in Appendix A.
A3) P(Gi) = ¬p(X
¯) is a g ound nega ed a om:
(Gi Fi Ti Ci Ki)
(Gi ¬p(X
¯
) Fi∪{← p(X
¯
)} Ti Ci Ki)
A4) P(Gi) =L is a g ound buil -in li e al:
(Gi Fi Ti Ci Ki)
(Gi L Fi Ti Ci Ki)
only i L is e alua ed ue.
4.2 The CQC-Expansion Rules
The nine CQC-expansion ules a e lis ed in ables 4.1 and 4.2. Fo he sake o no a ion, i Gi = ← L1 ∧ …
∧ Lj-1 ∧ Lj ∧ Lj+1 ∧ … ∧ Lm hen Gi Lj = ← L1 ∧ … ∧ Lj-1 ∧ Lj+1 ∧ … ∧ Lm. I Gi = ← L1 ∧ … ∧ Lm hen
Gi∧p(X
¯
) = ← L1 ∧ … ∧ Lm ∧ p(X
¯
).
The applica ion o a CQC-expansion ule on a gi en CQC-node (Gi Fi Ti Ci Ki) may esul in none, one
o se e al al e na i e (b anching) descendan CQC-nodes depending on he selec ed li e al P(Ji) = L.
He e, Ji is ei he he goal Gi o any o he condi ions Fi,j in Fi. L is selec ed acco ding o a sa e
compu a ion ule P [Llo87], which selec s nega i e and buil -in li e als only when hey a e ully
g ounded. To gua an ee ha such li e als a e soone o la e selec ed we equi e deduc i e ules and goals
o be sa e.
Que y Con ainmen Wi h Nega ed IDB P edica es (Ex ended Ve sion) 9
Once a li e al is selec ed, only one o he CQC-expansion ules can be applied. We dis inguish wo
classes o ules: A- ules and B- ules. A- ules a e hose whe e he selec ed li e al belongs o he goal Gi.
Ins ead, B- ules co espond o hose whe e he selec ed li e al belongs o any o he condi ions Fi,j in Fi.
Inside each class o ules, hey a e di e en ia ed wi h espec o he ype o he selec ed li e al.
In each CQC-expansion ule, he pa abo e he ho izon al line p esen s he CQC-node o which he
ule is applied. Below he ho izon al line is he desc ip ion o he esul ing descendan CQC-nodes.
Ve ical ba s sepa a e al e na i es co esponding o di e en descendan s. Some ules like A1, A5, B2
and B4 include also an “only i ” condi ion ha cons ain s he ci cums ances unde which he expansion
is possible. I such a condi ion is e alua ed alse, he CQC-node o which he ule is applied becomes a
ailed CQC-node.
Finally, no e ha h ee CQC-expansion ules, namely A1, B1 and B2, use he esolu ion p inciple as is
de ined in [Llo87].
Table 4.2. CQC-expansion ules: B#- ules.
B1) P(Fi,j) = d(X
¯
) is a posi i e IDB a om:
(Gi {Fi,j}∪Fi Ti Ci Ki)
(Gi S∪Fi Ti Ci Ki)
whe e S is he se o all esol en s Su o clauses in R and Fi,j on d(X
¯). S may be emp y.
B2) P(Fi,j) = b(X
¯
) is a posi i e EDB a om:
(Gi {Fi,j}∪Fi Ti Ci Ki)
(Gi S∪Fi Ti Ci+1 Ki)
only i [] ∉ S.
Ci+1 = Ci i X
¯ con ains no a iables and b(X
¯) ∈ Ti; o he wise, Ci+1 = Ci∪{Fi,j}
S is he se o all esol en s o clauses in Ti wi h Fi,j on b(X
¯
). S may be emp y, meaning
ha b(X
¯
) canno be uni ied wi h any a om in Ti.
B3) P(Fi,j) = ¬p(X
¯) is a g ound nega i e o dina y li e al:
(Gi {Fi,j}∪Fi Ti Ci Ki)
(Gi {← p(X
¯)}∪{Fi,j ¬p(X
¯)}∪Fi Ti Ci Ki) only i Fi,j ¬p(X
¯) ≠ [] | (Gi∧p(X
¯) Fi Ti Ci Ki)
B4) P(Fi,j) = L is a g ound buil -in li e al ha is e alua ed ue:
(Gi {Fi,j}∪Fi Ti Ci Ki)
(Gi {Fi,j L}∪Fi Ti Ci Ki)
only i Fi L ≠ [].
B5) P(Fi,j) = L is a g ound buil -in li e al ha is e alua ed alse:
(Gi {Fi,j}∪Fi Ti Ci Ki)
(Gi Fi Ti Ci Ki)
5 Co ec ness Resul s Fo The CQC Me hod
In his Sec ion, we summa ize and ske ch he new p oo s o co ec ness o he CQC me hod. We e e he
eade o [FTU02] o he de ailed p oo s. We also s a e he class o que ies ha can be ac ually decided
by he CQC me hod. Be o e p o ing hese esul s, we need o make explici he model- heo e ic seman ics
o wi h espec hose esul s a e es ablished.
16 Ca les Fa é, E nes Tenien e and Toni U pí
necessa ily he comple e se o canonical EDBs ha he me hod o [Ull97] needs o cons uc . We apply
he heo e ical esul s in which his algo i hm is based o show ha he Simple VIP may eplace he
Nega ion VIP when using he CQC Me hod o check QC o conjunc i e que ies wi h nega ed EDB a om,
wi hou any loss o comple eness. Applying he Simple VIP we do no o gene a e all he canonical EDBs
ha he Nega ion VIP and [Ull97] would conside o p o e Q1 S Q2 and we can conclude ha he CQC
me hod + Simple VIP is as e icien as he algo i hm in [WL03] o he cases co e ed by his me hod.
Le Q1 and Q2 be wo conjunc i e que ies wi h nega ed EDB a oms:
Q1 = { q(X
¯
) ← p1(X
¯
1) ∧ … ∧ pn(X
¯
n) ∧ ¬s1(Y
¯
1) ∧ … ∧ ¬sm(Y
¯
m) }
Q2 = { q(U
¯
) ← 1(U
¯
1) ∧ … ∧ h(U
¯
h) ∧ ¬ 1(W
¯
1) ∧ … ∧ ¬ k(W
¯
k) }
Acco ding o [WL03, Theo em 2], Q1 S Q2 i and only i he ollowing wo condi ions ge sa is ied:
1. The e is a con ainmen mapping ? om Q2
+ o Q1
+ such ha Q1
+ S Q2
+, whe e
Q1
+ = { q(X
¯
) ← p1(X
¯
1) ∧ … ∧ pn(X
¯
n) }
Q2
+ = { q(U
¯
) ← 1(U
¯
1) ∧ … ∧ h(U
¯
h) }
2. Fo each j, 1 = j = k, Pj S Q2 holds, whe e
Pj = { q(X
¯
) ← p1(X
¯
1) ∧ … ∧ pn(X
¯
n) ∧ ?( j(W
¯
j)) ∧ ¬s1(Y
¯
1) ∧ … ∧ ¬sm(Y
¯m) }
No ice ha his esul has an in insic ecu si e s uc u e: each es o Pj S Q2 may equi e e-
e alua ing he wo condi ions jus de ined. The e a e wo base cases ha s op ecu sion. The i s one
occu s when Pj is unsa is iable since ?( j(W
¯
j)) = ¬¬si(Y
¯
i), o some i, 1 = i = m. Consequen ly, Pj S Q2
holds i ially. The second base case occu s when Pj c Q2 since o each pi being a con ainmen mapping
om Q2
+ o Pj+ he e exis s a leas one g, 1 = g = k, such ha pi( g(W
¯
g)) ∈ {p1(X
¯
1), …, pn(X
¯
n), ?( j(W
¯
j))}
[WL03, Theo em 1]. When his la e occu s, Q1 c Q2.
In he p e ious sec ion, example 7.1 helped o show ha he CQC Me hod + Nega ion VIP ope a es
simila ly han he me hod o [Ull97] when checking conjunc i e que y con ainmen wi h nega ed EDB
a oms. Now, he same example will help o g asp hese new esul s om [WL03] as well as o show how
hey a e applied inhe en ly by he CQC Me hod + Simple VIP.
Example 7.2
Recall Q1 and Q2 being wo que ies de ining he same 2-a y que y p edica e p:
Q1 = { p(X, Y) ← a(X, Z) ∧ a(Z, Y) ∧ ¬a(X, Y) }
Q2 = { p(X, Y) ← a(X, Z) ∧ a(Z, Y) ∧ a(Z, W) ∧ ¬a(X, W) }
whe e a is, o cou se, an EDB ela ion.
In his example, he e is jus one con ainmen mapping om Q2
+ o Q1
+ which p o es Q1
+ S Q2
+:
? = { XQ2 → XQ1, YQ2 → YQ1, ZQ2 → ZQ1, WQ2 → YQ1},
Acco ding o [WL03, Theo em 2] only one o all possible con ainmen mappings su ices o
accomplish he second condi ion o he heo em. Ob iously, any algo i hm claiming comple eness mus
sys ema ically es all con ainmen mappings be o e concluding ha none is he “elec ed” one.
Ne e heless, in his example i is enough o explo e jus one al e na i e and no many o hem.
Mo eo e , since Q2 only con ains a nega ed a om, ¬a(X, W), only one new conjunc i e que y P1 needs o
be gene a ed:
P1 = { p(X, Y) ← a(X, Z) ∧ a(Z, Y) ∧ a(X, Y) ∧ ¬a(X, Y) }
whe e a(XQ1, YQ1) comes om ?(a(XQ2, WQ2)).
Clea ly, P1 is unsa is iable since i con ains bo h a(X, Y) and ¬a(X, Y) and, hus, i compu es no answe
in any da abase. Consequen ly, P1 S Q2, so Q1 S Q2.
Que y Con ainmen Wi h Nega ed IDB P edica es (Ex ended Ve sion) 17
Now, conside again he CQC-de i a ion depic ed pa ially in igu e 7.1 as he mos - igh b anch in he
CQC-T ee ske ched he e, and hen concluded in igu e 7.3. This de i a ion in oduces a new cons an
each ime ha a dis inc a iable equi es o be ins an ia ed, so i can be hough o implemen ing he
Simple VIP. In ac , cons uc ing and hen es ing a canonical EDB wi h he Simple VIP is an indi ec
me hod o ind ou con ainmen mappings.
In his way, s eps 2b and 3bc in he CQC- ee shown in igu e 7.1 cons uc a canonical EDB o Q1
+
acco ding o he Simple VIP: {a(0, 1), a(1, 2)} . Con e sely, s eps 8bc, 9bc and 10bc in igu e 7.3
success ully ma ch he a oms in Q2
+ wi h he cons uc ed EDB, so he con ainmen mapping ? can be
de i ed s aigh o wa dly: {XQ2 → 0 → XQ1, YQ2 → 2 → YQ1, ZQ2 → 1 → ZQ1, WQ2 → 2 → YQ1}.
The second pa o he es , ha is, whe he P1 S Q2 holds, can also be acked easily on he CQC-
de i a ion in igu e 7.3. The gene a ion i sel o he new que y P1 by adding ?(a(XQ2, WQ2)) = a(XQ1, YQ1)
o he body o Q1 has i s “CQC-coun e pa ” in he addi ion o a(0, 2) = a(XQ2, WQ2){XQ2 0, WQ2 2} o he
goal pa , in s ep 11bc, which was “inhabi ed” p e iously by he a oms coming om he body o Q1. The
unsa is iabili y o P1 is de ec ed as soon as a(0, 2) is added o he EDB and condi ion C1 is igge ed and
e alua ed. No ice ha he EDB cons uc ed by hen is no hing bu he “ ozen” body o P1
+. Mo eo e , i
P1 had no been unsa is iable hen he igge ing and la e e alua ion o condi ion C2 = ← a(0, Z) ∧ a(Z,
2) ∧ a(Z, W) ∧ ¬a(X, W) would ha e de e mined whe he he e exis ed a con ainmen mapping om Q2
+
o P1
+ in o de o p o e P1
+ S Q2
+ as a i s s ep owa ds p o ing P1 S Q2.
8 Conclusions
In his pape we ha e p esen ed he Cons uc i e Que y Con ainmen (CQC) me hod o QC Checking
which ckecks “ ue” QC and QcuC o que ies o e da abases wi h sa e nega ion in bo h IDB and EDB
subgoals and wi h o wi hou buil -in p edica es. As a as we know, ou s is he i s p oposal ha co e s
all hese ea u es in a single me hod and in a uni o m and in eg a ed way.
We ha e p o ed se e al p ope ies ega ding he co ec ness o he CQC me hod: ini e success
soundness o hie a chical que ies and da abases, ailu e soundness, ini e success comple eness o s ic -
s a i ied que ies and da abases and ailu e comple eness o hie a chical que ies and da abases. F om
hese esul s, and om p e ious esul s ha showed ha in ini e non-con ainmen coun e examples ne e
exis in he pa icula case o checking QC o conjunc i e que ies wi h sa e EDB nega ion and buil -in
p edica es, we can ensu e e mina ion, and hus decidabili y, o ou me hod o hose cases.
The main con ibu ions o his pape a e wo old. Fi s , we ha e shown ha he CQC me hod pe o ms
con ainmen es s o mo e and b oade cases o que ies and da abase schemas han p e ious me hods.
Second, we ha e also shown ha he CQC me hod is decidable and no less e icien han o he me hods
o check que y con ainmen o conjunc i e que ies wi h o wi hou sa e nega ed EDB p edica es.
As a u he wo k we plan o cha ac e ize o he classes o que ies and deduc i e ules o which ou
me hod always e mina es.
Re e ences
[AHV95] S. Abi eboul, R. Hull, V. Vianu. Founda ions o Da abases. Addison Wesley, 1995.
[ASU79] A.V. Aho, Y. Sagi , J.D. Ullman. E icien Op imiza ion o a Class o Rela ional Exp essions. ACM
ToDS, 4(4):435-454, 1979.
[BEST98] F. B y, N. Eisinge , H. Schü z, S. To ge. SIC: Sa is iabili y Checking o In eg i y Cons ain s. In
P oceedings o he 6 h In e na ional Wo kshop on Deduc i e Da abases and Logic P og amming
(DDLP'98), 25-36, 1998.
[BJNS94] M. Buchhei , M.A. Jeus eld, W. Nu , M. S aud . Subsump ion o que ies in objec -o ien ed da abases.
In o ma ion Sys ems, 19(1):33-54, 1994.
18 Ca les Fa é, E nes Tenien e and Toni U pí
[BM86] F. B y, R. Man hey. Checking Consis ency o Da abase Cons ain s: a Logical Basis. In P oceedings o
VLDB’86, 13-20, 1986.
[CDL98] D. Cal anese, G. De Giacomo, M. Lenze ini. On he Decidabili y o Que y Con ainmen unde
Cons ain s. In P oceedings o he PODS’98, 149-158, 1998.
[Cha92] E.P.F. Chan. Con ainmen and Minimiza ion o Posi i e Conjunc i e Que ies in OODB's. In
P oceedings o PoDS’92, 202-211, 1992.
[CL89] L. Ca edon, J.W. Lloyd. A Comple eness Theo em o SLDNF Resolu ion, Jou nal o Logic
P og amming, 7(3):177-191, 1989.
[Cla77] K.L. Cla k. Nega ion as Failu e. In Logic and Da a Bases, 293-322, Plenum P ess, 1977
[CM77] A.K. Chand a, P.M. Me lin. Op imal Implemen a ion o Conjunc i e Que ies in Rela ional Da a Bases.
In P oc. o he 9 h ACM SIGACT Symposium on Theo y o Compu ing, 77-90, 1977.
[CR97] C. Cheku i, A. Raja aman. Conjunc i e Que y Con ainmen Re isi ed. In P oceedings o ICDT’97, 56-
70, LNCS 1186, Sp inge , 1997.
[DLNN97]
F. Donini, M. Lenze ini, D. Na di, W. Nu . The Complexi y o Concep Languages. In o ma ion and
Compu a ion, 134(1):1-58, 1997..
[DS96] G. Dong, J. Su. Conjunc i e Que y Con ainmen wi h espec o iews and cons ain s. In o ma ion
P ocessing Le e s, 57(2):95-102, 1996.
[FTU02] C. Fa é, E. Tenien e, T. U pí. Fo maliza ion And Co ec ness O The CQC Me hod. Technical Repo
LSI-02-68-R. h p://www.lsi.upc.es/~ a e/pape s/CQC.ps.gz
[FTU99] C. Fa é, E. Tenien e, T. U pí. The Cons uc i e Me hod o Que y Con ainmen Checking. In
P oceedings o he DEXA’99, 583-593, 1999.
[GSUW94]
A. Gup a, Y. Sagi , J.D. Ullman, J. Widom. Cons ain Checking wi h Pa ial In o ma ion. In
P oceedings o PoDS’94, 45-55, 1994.
[Hal01] A.Y. Hale y. Answe ing que ies using iews: A su ey. VLDB Jou nal, 10(4): 270-294,2001.
[JK84] D.S. Johnson, A. Klug. Tes ing Con ainmen o Conjunc i e Que ies unde Func ional and Inclusion
Dependencies. Jou nal o Compu e and Sys em Sciences, 28(1):167-189, 1984.
[Klu88] A. Klug. On Conjunc i e Que ies Con aining Inequali ies. Jou nal o he ACM, 35(1):146-160, 1988.
[Llo87] J.W. Lloyd. Founda ions o Logic P og amming, Sp inge , 1987.
[HMSS01]
A.Y. Hale y, I.S. Mumick, Y. Sagi , O. Shmueli. S a ic Analysis in Da alog Ex ensions. Jou nal o he
ACM, 48(5): 971-1012, 2001.
[LR96] A. Le y, M-C. Rousse . CARIN: A Rep esen a ion Language Combining Ho n Rules and Desc ip ion
Logics. In P oc. o he ECAI’96, 323-327, 1996.
[LR98] A. Le y, M-C Rousse . Ve i ica ion o Knowledge Bases Based on Con ainmen Checking. A i icial
In elligence, 101(1-2):227-250, 1998.
[LS93] A. Le y, Y. Sagi . Que ies Independen o Upda es. In P oceedings o he VLDB’93, 171-181, 1993.
[LS95] A. Le y, Y. Sagi . Seman ic Que y Op imiza ion in Da alog P og ams. In P oceedings o PoDS’95,
163-173, 1995.
[LS97] A. Le y, D. Suciu. Deciding Con ainmen o Que ies wi h Complex Objec s. In P oceedings o
PoDS’97, 20-31, 1995.
[NSS98] W. Nu , Y. Sagi , S. Shu in. Deciding Equi alences Among Agg ega e Que ies. In P oceedings o
PODS’98, pages 214-223, 1998.
[Sag88] Y. Sagi . Op imizing Da alog P og ams. In Founda ions o Deduc i e Da abases and Logic
P og amming, 659-698, Mo gan Kau mann, 1988.
[ST96] M. S aud , K. . Thadden. A Gene ic Subsump ion Tes ing Toolki o Knowledge Base Que ies. In
P oceedings o DEXA’96, 834-844, 1996
[Ull89] J. D. Ullman. P inciples o Da abase an Knowledge-Base Sys ems, Volume 2: The New Technologies.
Compu e Science P ess, 1989.
Que y Con ainmen Wi h Nega ed IDB P edica es (Ex ended Ve sion) 19
[Ull97] J. D. Ullman. In o ma ion In eg a ion Using Logical Views. In P oc. o he ICDT’97, 19-40, 1997
[WL03] F. Wei, G. Lausen. Con ainmen o Conjunc i e Que ies wi h Sa e Nega ion. To appea in P oceedings
o ICDT'03.
20 Ca les Fa é, E nes Tenien e and Toni U pí
Appendix A: Va iable Ins an ia ion P ocedu e
A a iable ins an ia ion p ocedu e om ({X1, X2, …, Xn} θ0 K0) o (Ø θn Kn) is a sequence ({X1, X2, …, Xn
} θ0 K0), ({X2, …, Xn } θ1 K1), …, (Ø θn Kn) such ha o each 0 = i = n, θi is a g ound subs i u ion and Ki
is a se o cons an s.
A a iable ins an ia ion s ep pe o ms a ansi ion om (X
¯
i θi Ki) o (X
¯
i+1 θi+1 Ki+1) ha ins an ia es he
a iable Xi+1 o X
¯
i acco ding o one o he VIP- ules de ined by selec ed a iable ins an ia ion pa e n
(VIP). The applica ion o he app op ia e VIP o a gi en class o que ies and da abases ensu es he
comple eness o he CQC me hod wi h espec o ha class.
The o maliza ion o he VIP- ules is gi en below. We deno e cons an s as k, knew and ki. max and min
a e wo unc ions ha ange o e se s o cons an s and hey e u n he cons an s ha ing he g ea es alue
and he leas alue, espec i ely, o hose se s.
VIP- ule o he Simple VIP
S. X
¯
i+1 = X
¯
i Xi+1, θi+1 = θ1∪{Xi+1/knew} and Ki+1 = Ki∪{knew}, whe e knew ∉ Ki.
VIP- ules o he Nega ion VIP
N1. X
¯
i+1 = X
¯
i Xi+1, θi+1 = θ1∪{Xi+1/k} and Ki+1 = Ki, whe e k ∈ Ki.
N2. X
¯
i+1 = X
¯
i Xi+1, θi+1 = θ1∪{Xi+1/knew} and Ki+1 = Ki∪{knew}, whe e knew ∉ Ki.
VIP- ules o he Dense O de VIP
Den1. X
¯
i+1 = X
¯
i Xi+1, θi+1 = θ1∪{Xi+1/k} and Ki+1 = Ki, whe e k ∈ Ki.
Den2. X
¯
i+1 = X
¯
i Xi+1, θi+1 = θ1∪{Xi+1/knew} and Ki+1 = Ki∪{knew}, whe e knew < min(Ki).
Den3. X
¯
i+1 = X
¯
i Xi+1, θi+1 = θ1∪{Xi+1/knew} and Ki+1 = Ki∪{knew}, whe e kj < knew < k
j+1, {kj,kj+1} ⊆ Ki
and he e is no kh ∈ Ki such ha kj < kh < kj+1.
Den4. X
¯
i+1 = X
¯
i Xi+1, θi+1 = θ1∪{Xi+1/knew} and Ki+1 = Ki∪{knew}, whe e max(Ki) < knew.
VIP- ules o he Disc e e O de VIP
The o maliza ion o he ules o his VIP equi es supplemen a y de ini ions. A i ual cons an
[NSS98] is a disc e e cons an whose alue is no de e mina ed by a nume ic quan i y bu by i s ela i e
posi ion in a linea o de ing o cons an s. Le om now on s a ic cons an s and o a disc e e cons an
ha is no a i ual cons an . We explici ly deno e i ual cons an s as dnew and d
i, and s a ic cons an s
om R as ci, cmin and cmax. Selec and apply one o he ollowing six ules:
Dis1. X
¯
i+1 = X
¯
i Xi+1, θi+1 = θ1∪{Xi+1/k} and Ki+1 = Ki, whe e k ∈ Ki.
Dis2. X
¯
i+1 = X
¯
i Xi+1, θi+1 = θ1∪{Xi+1/dnew} and Ki+1 = Ki∪{dnew}, whe e d
new is a new i ual cons an
such ha dnew < min(Ki).
Dis3. X
¯
i+1 = X
¯
i Xi+1, θi+1 = θ1∪{Xi+1/dnew} and Ki+1 = Ki∪{dnew}, whe e dnew is a new i ual cons an s. .
− min(Ki) = dj < dnew < kj+1 = cmin, {dj, kj+1, cmin} ⊆ Ki,
− he e is no i ual cons an dh ∈ Ki such ha dj < dh < kj+1 and
− he e is no s a ic cons an cp ∈ Ki such ha cp < cmin.
Dis4. X
¯
i+1 = X
¯
i Xi+1, θi+1 = θ1∪{Xi+1/dnew} and Ki+1 = Ki∪{dnew}, whe e dnew is a new i ual cons an s. .
− cj = kj < dnew < kj+1 = cj+1, {cj, kj, kj+1, cj+1} ⊆ Ki,
− he e is no i ual cons an dh ∈ Ki such ha kj < dh < kj+1,
Que y Con ainmen Wi h Nega ed IDB P edica es (Ex ended Ve sion) 21
− he e is no s a ic cons an cp ∈ Ki such ha cj < cp < cj+1 and
− |{dq | dq ∈ Ki and cj < dq < cj+1}| < |cj+1−cj|−1
Dis5. X
¯
i+1 = X
¯
i Xi+1, θi+1 = θ1∪{Xi+1/dnew} and Ki+1 = Ki∪{dnew}, whe e dnew is a new i ual cons an s. .
− cmax
= kj < dnew < dj+1 = max(Ki), {cmax, kj, dj+1} ⊆ Ki,
− he e is no i ual cons an dh ∈ Ki such ha kj < dh < dj+1 and
− he e is no s a ic cons an cp ∈ Ki such ha cmax < cp
X
¯
i+1 = X
¯
i Xi+1, θi+1 = θ1∪{Xi+1/dnew} and Ki+1 = Ki∪{dnew}, whe e dnew is a new i ual cons an such ha
max(Ki) < dnew.
