An On ology connec ed o se e al da a eposi o ies: que y
p ocessing s eps
Al edo Go˜
ni
Dep o. LSI. Uni e sidad del Pa´ıs Vasco
[email p o ec ed]
h p://siul02.si.ehu.es/˜ji gbda
A an za Illa amendi
Dep o. LSI. Uni e sidad del Pa´ıs Vasco
[email p o ec ed]
Edua do Mena
Dep o. IIS. Uni e sidad de Za agoza.
[email p o ec ed].es
Jos´
e Miguel Blanco
Dep o. LSI. Uni e sidad del Pa´ıs Vasco
[email p o ec ed]
Abs ac
The g ea expansion o communica ion ne wo ks has made a ail-
able o use s a huge numbe o he e ogeneous and au onomous da a
eposi o ies ha p esen di e en s uc u es/o ganiza ions, que y
languages and da a seman ics. In ha con ex i is clea ha new
in o ma ion e ie al echniques wi h a s a egy ha ocuses on in-
o ma ion con en and seman ics a e needed. We p opose o use
domain speci ic On ologies o cap u e he in o ma ion con en o
such eposi o ies whene e a ailable. We desc ibe such On olo-
gies using a sys em based on Desc ip ion Logics. In his pape
we p esen all he s ages o he p ocessing o a que y o mula ed
o e an On ology when he answe mus be ound in he unde ly-
ing da a eposi o ies. Those s ages make up a subpa o he global
que y p ocessing s a egy de ined o a se o loosely-coupled On-
ologies. We show i s how he que y is ans o med in o a seman-
ically equi alen one and how inconsis en que ies a e de ec ed.
Then, we explain he es o e i y i he que y can be answe ed
om he cache memo y. Nex , we p esen a se o heu is ics used
du ing he que y decomposi ion p ocess. La e on, we show how o
op imize plans associa ed o subque ies ha access he unde lying
da a eposi o ies and inally we illus a e how he answe s e ie ed
om he eposi o ies a e co ela ed in o de o gene a e he que y
answe .
Keywo ds: On ologies, Knowledge-based sys ems, Que y P o-
cessing.
1 In oduc ion
On he global in o ma ionin as uc u e, he g ea expansion
o communica ion ne wo ks has made a ailable o use s a
huge numbe o he e ogeneous and au onomous da a epos-
i o ies. Howe e , hese eposi o ies p esen di e en s uc-
u es/o ganiza ions, que y languages and da a seman ics,
making i e ydi icul o he use s o access he da a s o ed
in hem.
A possible solu ion o ligh en he p oblem o lack o
uni o mi y when dealing wi h a ailable eposi o ies consis s
o de ining new in o ma ion e ie al echniques wi h a
s a egy ha ocuses on in o ma ion con en and seman ics.
We p opose o ep esen in ensional desc ip ions o he
objec s in he eposi o ies as me ada a, in oducing in his
way a seman ic le el o e he eposi o ies. In he exis ing
syn ac ic-keywo d na ega ional app oaches, in which he
que y is a se o keywo ds, he use has o do mos o he
in o ma ion il e ing and co ela ion [Al , In ].
In o de o de ine a seman ic le el o e a eposi o ydi e -
en echniques can be used. We use one o mo e p e-exis ing
On ologies, cha ac e izing in o ma ion in di e en domains,
o c ea e he seman ic le el. An On ology may be de ined
as he speci ica ion o a ep esen a ional ocabula y o a
sha ed domain o discou se which may include de ini ions
o concep s, ela ions, unc ions and o he objec s [G u93].
On ologies ha e been used o desc ibe in o ma ion con en
in eposi o ies independen o he unde lying syn ac ic ep-
esen a ion o he da a [KS96, MP97].
In ou p oposal, On ologies a e desc ibed using a sys-
em based on Desc ip ion Logics (DL) [BBMR89] and he
mapping in o ma ion
1
is exp essed using he ex ended e-
la ional algeb a. Reasoning mechanisms om DL a e use-
ul o pe o m que y op imiza ion and in pa icula seman ic
and caching op imiza ion. DL sys ems a e also app op ia ed
o o e in ensional answe s o he use s. Mapping desc ip-
ions play a key ole in encapsula ing he he e ogenei y due
o di e en o ma s and o ganiza ion o he da a in he a -
ious eposi o ies. They ac as an in e media y language be-
ween he DL exp essions and he que y languages o he
local eposi o ies. Ou ocus in his pape is o p esen he
que y p ocessing s eps de ined o sea ching e icien ly he
da a s o ed in one o mo e da a eposi o ies ha may con-
ain o e lapping da a unde one ele an On ology. Wi h e-
spec o o he ela ed wo ks ha also conside he p oblem
o accessing e icien ly unde lyingda a eposi o ies om se-
man ically ich iews [ASD
+
91, AKS96, CHS91, FRV96,
LSK95], ou pa icula con ibu ionconsis s o inco po a ing
new enhancemen s in he di e en que y p ocessing s eps.
So, we show: 1) he de ini ion and use o he no ion o Mos
Immedia e Supe concep s in he s ep o seman ic ans o -
1
Mapping in o ma ion is he in o ma ion ha ela es On ologies wi h
one o mo e eposi o ies whe e he ac ual da a a e s o ed.
ma ion and decomposi ion. This no ion allows one o ob ain
some e ms ha do no appea in he que y bu ha can be
used o ob ain a be e que y execu ion plan, as well as o
elimina e cons ain s and edundan e ms; 2) a es o decide
i he ini ial que y can be answe ed wi h he da a s o ed in
he cache memo y; 3) a se o heu is ics ha make an e i-
cien que y decomposi ion; 4) how o op imize he mapping
in o ma ion co esponding o he subque ies p e iously de-
composed and ha ha e o be p ocessed in he unde lying
eposi o ies.
In he es o he pape we p esen i s he o e iew o
he que y p ocessing. In he ollowing sec ions we ocus
on he di e en s eps o he que y p ocessing: seman ic
ans o ma ion, cache op imiza ion, que y decomposi ion,
op imiza ion o he mapping in o ma ion and co ela ion o
he answe .
2 Que y P ocessing: an o e iew
Fi e main s eps a e ollowed du ing he que y p ocessing:
pa sing o he que y; seman ic ans o ma ion, cache op i-
miza ion and que y decomposi ion; que y p ocessing in he
unde lying eposi o ies; loadingo he answe s b ough om
he eposi o ies in he cache memo y; and, que y p ocessing
o e he cache memo y.
Du ing he pa sing s ep, lexical and syn ac ical e o s a e
de ec ed. In ou case his is achie ed by using he pa se
o he DL sys em. In he ollowing sec ions we explain
he ea u es o he second and hi d s eps. Finally we do
no explain he las wo s eps because he e a e no new
enhacemen s in hem.
2.1 Que y exp ession
The gene al o m o a que y o mula ed o e an On ology
desc ibed using a DL sys em is:
[ ( ole) o ] ge all concep desc ip ion
whe e ( ole) means o p ojec he ole alues o ha
concep desc ip ion. The condi ions ha o m pa o he
concep desc ip ion a e a conjunc ion o concep names and
ole es ic ions. A concep
2
g oups indi idual elemen s
o he eal wo ld. A ole ep esen s a bina y ela ionship
be ween concep s o be ween concep s and scala da a ypes.
Howe e wha dis inguishes he no ion o concep om
he class speci ica ion in seman ic da a models o objec -
o ien ed da abases, is ha i is possible o desc ibe concep s
using in ensional desc ip ions ph ased no only in e ms o
necessa y p ope ies ha mus be sa is ied by hei ins ances
(in his case he concep is called a p imi i e concep and
is deno ed as
:
<
like using no a ion o he BACK sys em
[ LNPS87]) bu also in e ms o necessa y and su icien
p ope ies(in his case heconcep is calleda de inedconcep
and is deno ed as
:=
) [Bo 92]. The ole es ic ions can be
ca dinali y es ic ions like a leas (n, ole) o a mos (m, ole)
2
In some DL sys ems, he names class and a ibu e a e used ins ead o
concep and ole.
o alue es ic ions like all( ole,concep ype), ole: alue
and ole: close( alue)
3
Que ies in DL sys ems a e conside ed as new concep s
ha desc ibe he condi ions ha he ins ances ha cons i u e
hei answe s mus sa is y. Que ies a e classi ied in he On-
ology. The classi ica ionmechanismconsis s o disco e ing
he subsump ion ela ionships be ween concep s when a new
concep is decla ed, i.e. he new concep is au oma ically
loca ed in o he hie a chy o e ms. One concep subsumes
ano he one i in all possible ci cums ances, any ins ance o
he secondone mus bein he i s one. Using a DLsys em, i
is possible o know whe he one concep is subsumed by an-
o he one simply by lookinga he de ini ion o he concep s,
wi hou accessing he ins ances.
2.2 Example que y
To illus a e he que y p ocessing app oach, we show he
di e en s eps pe o med when answe ing he nex que y:
(numbe -o -pages) o ge all documen and
pe iodical publica ion and mul imedia documen and
a leas (1,doc-au ho -name)a mos (1,doc-au ho -name)and
all(doc-au ho -name,o ganiza ion)
ha e ie es he page numbe s o all he documen s ha
e i y he ollowing condi ions: hey a e pe iodical, mul i-
media, wi h only one au ho and ha he au ho name co e-
sponds o an o ganiza ion. Fo example,
<
25,Ja aWo ld1
>
could be an elemen o he answe whe e Ja aWo ld1 is he
ins ance ha e e s o a numbe o he Ja aWo ld on-line
publica ion, published in h p://www.ja awo ld.com and con-
side ing ha he o ganiza ionIDG is he au ho .
The p e ious que y is o mula ed o e he STANFORD-I
On ology (h p://siul02.si.ehu.es/˜ji gbda /OBSERVER) and ha
is a subse o he Bibliog aphic-Da a On ology [G u94]
de eloped as a pa o he ARPA Knowledge Sha ing E o .
3 Seman ic T ans o ma ion
The seman ic ans o ma ion consis s o inding a seman i-
cally equi alen que y o he use que y. Fo ha , he se o
Mos Immedia e Supe concep s (
MI S
) is calcula ed. Le
T
=
T
1
,
:::
,
T
P
g
be he se o concep s and oles ha o m he
On ology, and le
C
=
C
1
,
:::
,
C
N
g
be he se o concep s
and ole es ic ions ha o m he concep desc ip ion o he
que y hen he se
MI S
4
co esponding o he que y is:
MI S
=
D
j
(D
2T _
D
2C
)
^
(D subsumes(C
1
and
::
and C
N
))
^8
E(E
2MI S ^
E
6
=
D
!
E does no subsume D)
g
The concep desc ip ion o he que y
C
,
C
1
and
:::
and
C
N
, is seman ically equi alen o he in e sec ion o all he
immedia e supe concep s in he se
MI S
D
1
and
:::
and
D
M
. In [GIMB97] he p oo o he p e ious s a emen
3
The es ic ion ole: close( alue) means ha he ole mus ake ha
alue and only ha .
4
In o de o ge he
MI S
se he sys em uses he subsump ion no ion.
appea s and also i is easoned ha he complexi y o he
ope a ion o calcula e he
MI S
se is polynomial.
3.1 Applica ion o he example
The
MI S
se co esponding o he que y p esen ed in
sec ion 2.2 is:
mul imedia documen , a leas (1,doc-au ho -name),
a mos (1,doc-au ho -name),magazine
g
By calcula ing he
MI S
se some mo e speci ic concep s
o be used in he nex s eps and ha do no appea in he
ini ial que y a e de ec ed (in he example magazine) and
o he edundan concep s and ole es ic ions o he ini ial
que y a e iden i ied (in he example documen , all(doc-
au ho -name,o ganiza ion)because heydono belong o he
MI S
se ).
The seman ically equi alen que y is he e o e
(numbe -o -pages) o ge all mul imedia documen and
a leas (1,doc-au ho -name)and a mos (1,doc-au ho -name)
and magazine
3.2 De ec ion o inconsis en que ies and gene a ion o
in ensional answe s
Using he
MI S
se , he ini ial que y may be de ec ed as
inconsis en and also in ensional answe s may be gi en o
he use .
I is de ec ed ha he que y is inconsis en when ge all
no hing is a seman ically equi alen que y o he use que y,
ha is, when no hing is in he se o Mos Immedia e
Supe concep s.
Fo example, i he que y we e
ge all mul iple-au ho -documen and
a mos (1,doc-au ho -name)
hen i would be de ec ed as inconsis en due o mul iple-
au ho -documen is de ined as
mul iple-au ho -documen
:=
documen and
a leas (2,doc-au ho -name)
and he e o e no hing would be in he
MI S
se o he
p e ious que y.
When wo king wi h DL sys ems, i is also possible o
gi e in ensional answe s, ha is, answe s in e ms o he
desc ip ions ha he ins ances ha o m he ex ensional
answe sa is y. These in ensional answe s can be o e ed o
heuse be o e heex ensionalanswe is eady. Twodi e en
ypes o in ensional answe s a e possible: Mos Speci ic
Fo mula ion (MSF) o he que y and Ex ended Fo mula ion
(EF) o he que y. The i s one is o med by he elemen s
o he
MI S
se co esponding o he que y (no ice ha
he MSF exp ession is he seman ically equi alen que y)
and he second one is o med by ecu si ely subs i u ing he
concep s in he ini ial que y by hei de ini ions. Bo h ypes
o in ensional answe s (MSF and EF) a e o e ed o he use
by eques bu , in pa icula , he EF is also o e ed when
he ini ial que y is inconsis en , because i becomes mo e
explici whe e he inconsis ency is.
The EF o he p e ious inconsis en que y, ge all mul iple-
au ho -documen and a mos (1,doc-au ho -name), appea s
below, whe e he inconsis ency can be iden i ied.
ge all documen and
a leas (2,doc-au ho -name)and a mos (1,doc-au ho -name)
4 Cache op imiza ion
When dealing wi h On ologies connec ed o se e al da a
eposi o ies, i is wo h ha ing some da a cached wi hin
he On ologies in o de o a oid accessing he unde lying
eposi o ies each ime a use o mula es a que y. Then,
du ing he que y p ocessing, i is necessa y o de ec i he
que y can be answe ed wi h he da a s o ed in he cache. In
gene al, i is no easy o e i y i he answe o a que y is
con ained in he cache memo y because i depends on he
que y language and how he cached da a a e ep esen ed.
Fu he mo e, e i ica ion ha he que y is no cached should
be as as as possible.
In his sec ion we s a e i s he no ion o explici and
implici cache, hen he es o decide i he que y answe
is in he cache memo y and inally we poin ou he p oblem
o inding he con en so he op imalcache memo yand gi e
a possible op imal cache memo y o he example.
4.1 Explici and implici cache memo y
Wo king wi h DL sys ems i is possible o cache explici ly
he ins ances o concep desc ip ions and he alues o oles.
Taking in o accoun ha que ies a e conside ed as new
concep s (possibly wi h p ojec ion o oles) ha means ha
que y answe s can be explici ly cached. Mo eo e , he e a e
o he que ies buil using as base se s only se s in he explici
cache, ha a e implici ly cached.
A concep C ha belongs o he On ology, C
2 T
,
is explici ly cached by s o ing he ins ances in he cache
memo y and adding ge all C o he se
ECQ
.
A ole
2T
is explici ly cached o a concep C
2T
by s o ing hei co esponding alues in he cache memo y
and adding ( ) o ge all C o he se
ECQ
. A ole can be
explici lycachedonly o concep s ha a e explici lycached.
The se
ECQ
is o med by all he concep desc ip ions and
oles ha a e cached.
A que y q

[ ( ) o ] ge all
C
is implici ly cached,
deno ed by q
2ICQ
, i all he e ms (concep s and oles)
ha o m pa o he seman ically equi alen que y o qa e
cached (ei he implici ly o explici ly).
4.2 How cached da a can be iden i ied
The p oblem o e i ying i a que y can be answe ed
comple ely wi h he con en s o he cache memo y is simila
o he p oblem o e i ying i a que y is implici ly cached
by he se o explici ly cached que ies. The only di e ence
is ha he concep exp ession o he que y can be anyone (q

[ ( ) o ] ge all
C
1
and
:::
and
C
N
ins ead o q

[ ( )
o ] ge all
C
). The es o decide i he que yanswe is in he
cache memo y is he nex one:
A que y q

[ ( ) o ] ge all
C
1
and
:::
and
C
N
is cachedi
all he concep s whose names (
D
i
) appea in he se
MI S
=
D
1
,
:::
,
D
M
g
co esponding o qa e explici ly o implici ly
cached (ge all
D
i
2ECQ I C Q
) and all he oles ha
appea in he se
MI S
and he oles o be p ojec ed in he
que y(
j
) a e also cached ( (
j
) o ge all
D
2 ECQICQ
whe e
D
subsumes
C
1
and
:::
and
C
N
)
The complexi yo he p e ious es is polynomialbecause
i is based on e i yingi all he elemen s in he se
MI S
a e
cached, ha is, i hey a e in he p e iously compu ed
ECQ
and
ICQ
se s.
Ano he no el y o ou app oach is ha i does no ma e
how he use o mula es he que y
ge all documen and a leas (2,doc-au ho -name)
ge all a leas (2,doc-au ho -name)and documen
ge all biblio hing and a leas (2,doc-au ho -name)
ge all mul iple au ho documen
because he
MI S
se
mul iple au ho documen
g
is calcu-
la ed i s and he e i ica ion is made based on his se using
he
ECQ
and he
ICQ
no ions.
4.3 Con en s o he op imal cache memo y o he
example.
A di e en p oblem no di ec ly ela ed o he que y p ocess-
ing s eps bu ha needs a solu ion is o de ine he con en s o
he op imal cache memo y. In [GIMB97] we p esen an ap-
p oach o de ine an op imal cache, he cos model and he
algo i hm used o decide which que ies a e wo h caching.
The algo i hm has o calcula e he se
ECQ
ha p oduces he
g ea es bene i o a limi ed size o he cache memo y. In
o de o know he bene i p oduced by a se
ECQ
hen i s
co esponding se
ICQ
has o be calcula ed and a se o pa-
ame e s ha measu e he bene i ha e o be a ailable. We
use an algo i hm based on he A

, ins ead o an exhaus-
i e sea ch algo i hm, ha calcula es quasi-op imal solu ions
and ha ou expe imen al esul s show ha is mo e e icien .
Mo eo e , he algo i hm is no pe o med du ing que y p o-
cessing bu be ween sessions (a nigh o example). Wi hin
a session he LRU (Leas Recen ly Used) s a egy is used as
he s a egy o eplacemen in he cache memo y.
The algo i hm p oposed is:
1) c ea e he ini ial s a e
2) while exis s a s a e
S
no isi ed ye
2.1) build he new s a es esul ing om adding a new que y o he
ECQ
and calcula e he new
ICQ
, bene i
B
and cos
C
2.2) o de he lis o s a es by dec easing o de o bene i
B
2.3) elimina e he s a es
(
ECQ
1

ICQ
1
B
1
C
1)
whe e he e exis s ano he
s a e
(
ECQ
2

ICQ
2
B
2
C
2)
wi h cos (
C
2
<C
1
) and bene i (
B
2
>B
1
)
Finally, in o de o ollow wi h he es o he que y
p ocessing s eps, le us suppose ha he con en o he cache
memo y, as calcula ed by he p e ious algo i hm, is:
mul imedia documen , agen , o ganiza ion, publishe ,
uni e si y, [agen name, agen ]
5
, [doc i le,
mul imedia documen ]
g
I can beseen ha he exampleque ycanno be comple ely
answe ed wi h he con en s o he cache memo y because
i s co esponding seman ically equi alen que y exp ession
con ains e ms (magazine,doc-au ho -name and numbe -o -
pages) ha a e no in he cache memo y.
5 Que y Decomposi ion
Que y decomposi ion implies o ob ain and analyze all
he possible combina ions o subque ies ha can be made
on he unde lying eposi o ies in o de o ge he que y
answe . In his sec ion we p esen he heu is ics de ined in
o de o pe o m an e icien que y decomposi ion and hei
applica ion o he example.
5.1 Heu is ics
In gene al, que y decomposi ion is a e y complex ask
because he e can be many di e en ways o decomposing
a que y in o se s o subque ies and s a is ic in o ma ion and
access pa hs in he local sys ems a e no a ailable. Fo ha
eason, ins ead o calcula ingall he possible pa i ions
6
, ha
is se s o subque ies, ha can be made s a ing om he
seman ically equi alen que y [ ( ) o ] ge all
D
1
and
:::
and
D
M
and es ima ing he cos o each pa i ion, we ha e
de ined a s a egy ha a oids sea ching all he possibili ies
by applying a se o heu is ics. The s a egy consis s o , i s
o all, ob aining he e ms o he que y ha a e no cached
o which he heu is ics H1, H2, H3 and H4 (de ined below)
a e ied o apply. A e his s ep i is known he se o e ms
ha necessa ily ha e o be in a leas one o he decomposed
subque ies o answe om he da a eposi o ies. Nex , hose
non-cached e ms a e g ouped in o subque ies ha ha e o
beanswe ed om he same eposi o y owhich he heu is ics
H5,H6 andH7a e ied oapply. H5 andH6 y o educe he
size o he subque iesandH7 ies o educe he compu a ion
cos . The gene al goals o hese heu is ics a e:

Goal 1: To a oid ha he answe sen om each
eposi o y is oo la ge
7
.

Goal 2: To y ha he compu a ion cos in each
eposi o y is small, unless i is needed o each goal 1.
5
I means ha he ole agen name is cached o he concep agen .
6
I he que y is composed by
n
e ms, he e a e as much possible
decomposi ions as he numbe o possible pa i ions in a se o ca dinali y
n
.
Mo eo e , he possibili ies a e e en mo e because a e m can appea in mo e
han one subque y and a de ined concep can be subs i u ed by i s de ini ion.
7
In he ollowing, e ms la ge and small a e ela i e o he limi ed size
o he cache memo y whe e he answe s a e s o ed du ing each session.

Goal 3: To y no o b ing pa s ha a e al eady cached,
unless i is needed o each he p e ious goals.

Goal 4: To y o send subque ies ha sa is y he
wo i s goals o be execu ed in pa allel in di e en
eposi o ies. This a oids communica ion cos and a
g ea e compu a ion cos among he eposi o ies.
Heu is ic H1: Subs i u e a non-cached de ined concep
wi hou al e na i e
8
mapping in o ma ion by i s mos spe-
ci ic de ini ion. In gene al, i is no wo h b inging he in-
s ances co esponding o a de ined concep om he eposi-
o ies because he e may happen ha an al eady cached con-
cep o a edundan elemen is b ough om he eposi o ies.
Once he de ined concep is subs i u ed by i s mos speci ic
de ini ion he edundan elemen s in ha de ini ion a e e-
mo ed.
Heu is ic H2: Main ain a non-cached de ined concep wi h
al e na i e mapping. The non-cached de ined concep is
no subs i u ed by i s mos speci ic de ini ion because i
mainly a o s goal 2 (al e na i e mapping in o ma ions a e
p o ided o de ined concep s only i hey a e be e han he
au oma ically calcula ed om hei de ini ions).
Heu is ic H3: Subs i u e a non-cached p imi i e concep
by one o i s non-cached subconcep s only i he es o he
subconcep sa eall cachedand i i is he o algene aliza ion
o all i s subconcep s. A p imi i e concep ha is no cached
and ha is he o al gene aliza ion o se e al subconcep s
whe e only one is no cached can be subs i u ed by he only
non-cached subconcep . This a o s he goals 1, 2 and 3.
Heu is ic H4: No o send a subque y wi h p ojec ion o a
ole ha is al eady cached. I he ole o be p ojec ed in he
que y is cached o he que y concep , hen i is no needed
o e ie e he ole alues om he unde lying eposi o ies
bu only he ins ances o he que y desc ip ion. Once
answe s o he subque ies a e loaded in o he cache memo y
hen i is possible o e ie e he ole alues co esponding
o he ins ances ha sa is y he que y desc ip ion. This
heu is ic a o s he goal 1 because he answe sen om he
unde lying eposi o ies is smalle ( ole alues a e no sen ).
I also a o s he goal 3, because some pa s al eady cached
a e no b ough again: he ole alues.
Heu is ic H5: Reduce he size o he answe o a subque y
wi hin a eposi o y. I he size o he answe o a subque y
sen o a eposi o yis oo g ea , specially i he desc ip ionis
unsa e
9
, hen ha sizehas o be educedbyaddingsome e m
o he subque y ha can be answe ed in he same eposi o y
and ha educes he size because he in e sec ion o all he
e ms is calcula ed. I he e ms
E
1
,...,E
p
g
ha e o be
b ough om he same eposi o y and i is conside ed ha
8
Concep s and oles may ha e mo e han one mapping in o ma ion o
which we call al e na i e mapping in o ma ions.
9
A que y exp essed in DL is unsa e i only con ains es ic ions o he
ype all o a mos [De 93].
he size o he answe is oo g ea hen ano he e m E
q
belonging o he ini ial que y o ha subsumes he que y
has o be added o he subque y. E
q
has o e i y ha i
does no subsume E
1
and ... and E
p
because E
q
would no
educe he size o he answe . I is con enien ha E
q
has
he smalles possible size in o de o educe he size o he
answe o E
1
and ... and E
p
and E
q
, and ha i does no ha e
a high cos o compu e E
q
in he eposi o ies. I s a is ics a e
no a ailable hen i can be supposed ha p imi i econcep s,
es ic ions o he ype ole: alue, andde inedconcep swi h
al e na i e mapping do no ha e a high compu a ion cos ,
bu es ic ions o he ype a leas , a mos and all ha e a high
cos . The bes e ms o be added a e: 1) a non-cached e m o
he que y wi h an al e na i emapping in he same eposi o y
and 2) a cached e m o he que y ha can be e ie ed om
he same eposi o y. I he e a e no e ms ha e i y hese
condi ions hen he heu is ic H6 has o be applied.
Heu is ic H6: Me ge subque ies whose sizes o answe
ha e o be educed wi h subque ies wi h smalles sizes o
answe om o he eposi o ies. I he size o he answe
o a subque y in a eposi o y is oo g ea and he heu is ic
H5 canno be applied any longe , hen he me ge wi h o he
subque ies in o he eposi o ies has o be made, in o de o
educe ha size. Wi h his heu is ic he goal 4 is a o ed.
No ice ha his heu is ic is applied ins ead o calcula ing
he bes se o subque ies o be me ged which is a cos ly
p ocess as we explain nex . Le us suppose ha he e a e
n
subque ies
N
1
:::N
n
o b ing om
n
di e en nodes
and ha
N
1
:::N
m
(wi h
m

n
) need o educe i s size.
Fo ha , he esponse imes and sizes o he answe s o all
he di e en combina ions among
N
i
(
1

i

n
) would
ha e o be es ima ed and he bes one chosen. As s a is ics
co esponding o he eposi o ies a e no a ailable hen i
would be needed o use he s a is ics s o ed abou concep s
and oles o he On ology ( esponse imes and sizes o he
answe s) and es ima e he esponse imes and sizes o each
N
i
.
Heu is ic H7: T ans o m a subque y wi h se e al es ic-
ions o e he same ole whose size is no oo g ea by a
subque y wi h he p ojec ion o ha ole. I he size o he
ex ension o a ole is no oo g ea and he e a e se e al e-
s ic ions o e ha ole, hen he ole alues can be b ough
ins ead o he conjunc ion o he es ic ions. This a o s
goal 2 (bu no goal 1) and ha is why i is wo h only i he
size o he ex ension is eally small enough. In pa icula i
he e exis s a es ic ion o he o m all( ,c) and cis cached,
hen o compu e all( ,c) in he eposi o ies has a high cos
due o he kind o mapping in o ma ion co esponding o i
and i is mo e in e es ing o b ing he alues o he ole .
The algo i hm used o apply he heu is ics appea s in he
ollowing. The complexi y o he algo i hm is polynomial in
he numbe o e ms in he On ology, elemen s in he que y
and numbe o eposi o ies in ol ed in he que y.

ind he cached and non-cached pa s o he que y
g
1) ini ialize cached and non-cached wi h elemen s in
MI S
ha a e cached and no cached espec i ely
2) o each elemen C in non-cached
2.1) y o apply H1 o H2 o C and upda e cached and non-cached
2.2) y o apply H3 o C and upda e cached and non-cached
2.3) y o apply H4 and upda e cached and non-cached
ob ain subse o subque ies o ask in he eposi o ies
g
3) ini ialize subque ies wi h subse s o non-cached pa s o
be b ough om same eposi o y node
4) o each subque y S in subque ies
4.1) y o apply H5 o S and upda e S in subque ies
4.2) y o apply H7 o S and upda e S in subque ies
5) y o apply H6 o que ies in subque ies
The gene al ideas behind he p e ious heu is ics ag ee
wi h o he wo ks ha also conside hei de ini ion o a
simila con ex . Howe e , ou con ibu ion consis s o
de ining hem in he con ex o DL sys ems whe e he eexis
de ined and p imi i e concep s and whe e some o hem may
be al eady cached.
5.1.1 Applica ion o he example
In his subsec ion we show he applica ion o some heu is-
ics o he seman ically equi alen que y appea ing in sub-
sec ion 3.1 ha co esponds o he que y p esen ed in he
2.2, and supposing ha he con en s o he cache memo y
a e hose de ined in he 4.3.
As he e a e some elemen s in he se
MI S
ha a e no
cached (magazine and doc-au ho -name) hen heu is ics a e
applied o he seman ically equi alen que y.
a e ha ing ied he se o heu is ics, only H2 and H5
ha e been applied and he e o e i has been decided ha he
que ies Q1’ and Q2 ha e o be answe ed in he unde lying
eposi o ies (called ep1 and ep2.
Q2: ge all magazine and a leas (1,doc-au ho -name)and
a mos (1,doc-au ho -name)
in eposi o y ep1
g
Q1’: (numbe -o -pages) o ge all mul imedia documen
in eposi o y ep2
g
ha a e conside ed o be o a easonable size o be loaded
in o he cache memo y once hey ha e been answe ed om
he unde lying eposi o ies.
6 Que y P ocessing in he Reposi o ies
The se o subque ies ha ha e been selec ed in he p e ious
s ep ha e o be asked in he unde lying eposi o ies. Be-
o e gene a ing he exp essions in he que y languages o he
eposi o ies in ol ed, i is con enien o op imize he map-
ping in o ma ion ha has been exp essed in a languageinde-
penden o he que y languages o he unde lying eposi o-
ies: he ex ended ela ional algeb a. The e o e, in his s ep,
o each DL subque y a co esponding op imized mapping
in o ma ion ( ha is, a mo e simpli ied ex ended ela ional
algeb a exp ession) is gene a ed.
De ini iono mappingin o ma ion o aconcep . Le
E
be
a se o en i ies, a mappingin o ma ion o a concep de ined
upon
E
is a se
10
o iples
<
R,(a
1
,
:::
,a
n
),T
>
, whe e
R
is an ex ended ela ional algeb a exp ession upon
E
;
a
1
:::a
n
a e a ibu es o
R
; and
T
=
D
1

:::

D
n
,
whe e
D
i
is he domain o he a ibu e
a
i
o all
i
be ween
1
and
n
.
De ini ion o mapping in o ma ion o a ole. Le
E
be a
se o en i ies, a mappingin o ma ion o a ole de ined upon
E
is a se o 6- uples
<
R
l
,(a d
1
,...,a d
n
),(a n
1
,
:::
,a n
m
),T
C
,
l
,T
>
,
whe e
R
l
is an ex ended ela ional algeb a exp ession upon
E
;
a d
1
:::a d
n
and
a n
1
 : : :  a n
m
a e a ibu es
o
R
l
;T
C
=T
1

...

T
n
, whe e
T
i
is he domain o he
a ibu e
a d
i
o all
i
be ween
1
and
n
;
l
is a unc ion
wi h de ini ion
l
:D
1

:::

D
m
!
T
, whe e
D
j
is he
domain o he a ibu e
a n
j
o all
j
be ween
1
and
m
and
T
is he ange o he a ibu e. Finally, T
=D
1

...

D
m
.
Taking in o accoun ha he mapping in o ma ion has al-
eady been de ined o all he concep s and oles o he On-
ology, he mapping in o ma ion o all he cons uc o s ha
may appea in subque ies: a leas (n, ole), a mos (m, ole),
all( ole,concep ype), ole: alue, ole: close( alue) and o
combina ions o concep s has o be de ined. Fu he mo e,
his mappingcan be op imizedwhen somein o ma ionabou
he unde lying da a eposi o ies is known, e.g., unc ional,
inclusion and exclusion dependencies, anges o alues o
a ibu es, in o ma ion abou null alues, and when some
combina ions o cons uc o s happen. Due o space limi a-
ions we p esen he mapping in o ma ion only o one con-
s uc o , a leas (n, ole), and one combina ion,a leas (n, ole)
and a mos (m, ole), bu hey show he kind o op imiza ions
pe o med.
6.1 a leas (n, ole)
The cons uc o a leas (n, ole) de ines a concep , whose
ins ances a e he ins ances o he concep domain o ole
and ha ake a leas
n
alues o ha ole. Remembe
ha he mapping o a ole de ines he pai s (ins ance, alue)
co esponding o a ole ex ension.
Le
be a ole, S
he mapping o
and
n
an in-
ege g ea e han 0, he cons uc o
a l eas
(
n
)
has
S
a leas
(n, )
11
as mapping, whe e
10
Tha se
<
R
1
,(a
11
,
:::
,a
1
n
1
),T
1
>
,
<
R
2
,(a
21
,
:::
,a
2
n
2
),T
2
>
,
...
<
R
m
,(a
m
1
,
:::
,a
mn
m
),T
m
>
g
e e s o he union o he ins ances
ep esen ed by all he iples:
<
R
1

(
a
11
:::a
1
n
1
)=(
a
21
:::a
2
n
2
)
R
2
 
R
m
,(a
11
,
:::
,a
1
n
1
),T
1
>
11
The no a ion used o de ine a mapping in o ma ion
A
is:
A
=
y
1
i cond
1
(
x
)
:::y
N
i cond
N
(
x
)
:
x
2
B
g
The se o iples in A is he calcula ed by nex algo i hm:
ini ialize A wi h he emp y se
o each x in se B
i
cond
1
(x) add
y
1
o A
else
:::
else i
cond
N
(x) add
y
N
o A
S
a leas
(n, ) =
<
R
l
,
a d
,T
C
>
i
n
=1
^
no
(
can be nul l
(
a n
)
12
<
a d
6
=
NULL
(R
l
),
a d
,T
C
>
i
n
=1
^
can be nul l
(
a n
)
"
13
i
n>
1
^
unc ional dependency
(
a d
!
a n
)
14
<
coun >n
;
1
(
a d
F
coun a n
(R
l
)),
a d
,T
C
>
in o he case
:
<
R
l
,
a d
,
a n
,T
C
,
l
,T
>
2
S
g
6.2 a leas (n, ole) and a mos (m, ole)
We p esen he mapping in o ma ion o he combina ion
a leas (n, ole) and a mos (m, ole) and explain why i is be -
e han he mapping in o ma ion calcula ed as he conjunc-
ion o he mapping in o ma ions o a leas (n, ole) and a -
mos (m, ole). So, he mapping in o ma ion o he desc ip-
ion a leas (n, ) and a mos (m, ), when
n >
1
^
a d
6!
a n
^
m

n
is:
S
a leas
(n, )
^
a mos
(m, ) =
conjunc ion(S
a leas
(n, ),S
a mos
(m, )) =
conjunc ion(S
a leas
(n, ),complemen (S
a leas
(m+1, ))) =
<
coun >n
;
1
(
a d
F
coun a n
(R
l
)) –

coun >m
(
a d
F
coun a n
(R
l
)),
a d
,T
C
>
:
<
R
l
,
a d
,
a n
,T
C
,
l
,T
>
2
S
g
Howe e ,a be e mappingin o ma ion o his exp ession
is he ollowing one:
<
m

coun >n
;
1
(
a d
F
coun a n
(R
l
)),
a d
,T
C
>
:
<
R
l
,
a d
,
a n
,T
C
,
l
,T
>
2
S
g
The las mapping exp ession is much less complex han
he i s one and a oids one scan and compu ing one di e -
ence wha e e i is he kind o da a eposi o y in ol ed. In
gene al, he p ocedu e consis s o g ouping es ic ions o e
he same ole and ob aining he co esponding op imized
mapping exp ession o each combina ion o es ic ions.
Ou main con ibu ion in his s ep is ha we ha e used
he ex ended ela ional algeb a as a language independen
o he que y languages o he unde lying eposi o ies o
de ine he mapping in o ma ion among an On ology and
he eposi o ies. This o malism allows one o desc ibe a
wide spec um o possible mappings and o de ine some
op imiza ion cases.
12
can be null
(
a n
)
is a exp ession ha akes he alue ue i i is
possible ha
a n
akes NULL alues and alse in o he case.
13
In his case, i is a oided accessing he unde lying da a eposi o ies
because he answe is emp y.
14
unc ional dependency
(
a d
!
a n
)
is a exp ession ha akes
he alue ue i he unc ional dependency
a d
!
a n
is sa is ied and
alse in o he case.
6.3 Applica ion o he example
The mapping in o ma ion o he i s que y:
Q1’: (numbe -o -pages) o ge all mul imedia documen
is he ollowing:
<

ep2. ec.003$[24-27]=“m”
( ep2. ec), ep2. ec.010
$
a, ep2. ec.300
$
a,s ,-,in
>
g
This exp ession canno be op imized because he e is
no a combina ion o es ic ions o e he same ole no
in o ma ion abou da a dependencies.
The mapping in o ma ion o he second que y:
Q2: ge all magazine and a leas (1,doc-au ho -name)and
a mos (1,doc-au ho -name)
is he nex one:
<

1

coun

1
((loc
F
coun (name) (

se ies i le=“magazine”
(doc)
1
(name=name) ep1.doc))), ep1.doc.loc,s
>
g
Howe e , i can be op imized aking in o accoun ha
he eexis s he unc ionaldependency ep1.doc.loc
!
ep1.doc.name. The op imized mapping in o ma ion is:
<

ep1.doc.se ies i le=“magazine” ( ep1.doc), ep1.doc.loc,s
>
g
whe e he compu a iono a join and an agg ega e unc ion
a e a oided.
7 Co ela ion o he answe
Each op imized mapping in o ma ion p e iously ob ained
has o be ansla ed in o a plan ha depends on he conc e e
da a eposi o ies. A di e en w appe ha ansla es he
mapping in o ma ion in o he conc e e que y language is
needed o each kind o da a o ganiza ion in ol ed in he
Global In o ma ion Sys em.
The co esponding SQL que y in he eposi o y ep1 (i is
an objec -o ien ed ela ional da abase) o he nex mapping
in o ma ion
<

ep1.doc.se ies i le=“magazine” ( ep1.doc), ep1.doc.loc,s
>
g
would be:
selec loc
om doc
whe e se ies i le="magazine"
The co esponding que y in he eposi o y ep2 (i is a
MARC [Pie94] ile sys em) o he nex mapping in o ma-
ion
<

ep2. ec.003$[24-27]=“m”
( ep2. ec), ep2. ec.010
$
a, ep2. ec.300
$
a,s ,-,in
>
g
would be:
Files: /home/g ad/MARC/UGA/oclcwkly.unica
P ojec ions: 010$a | 300$a
Condi ions: 008$[24-27] = m
This in o ma ion would be p ocessed by a w appe ha
accesses MARC iles and e ie es he eco ds ha sa is y
he co espondingcondi ions.
The inal co ela ion o he answe is made in he cache
memo y. Di e en answe s o he subque ies a e loaded in
he cache memo y and hen he answe is ob ained om he
cache memo y using he DL sys em que y capabili ies.
In cases whe e i is decided no o cache all he subque ies
answe s, co ela ion should be pe o med ou side he DL
sys em.
8 Conclusions
We p opose o use p e-exis ing On ologies in o de o
acili a e o he use he ask o que ying abou s o ed
da a in he e ogeneous and dis ibu ed da a eposi o ies. In
his pape we ha e p esen ed a s a egy ha sol es he
speci ic p oblem o gi ing answe s o o mula ed que ies
o e one On ology by accessing da a s o ed in di e en da a
eposi o ies connec ed o ha On ology. This s a egy makes
up a subpa o he global que y p ocessing s a egy de ined
o a se o loosely-coupled On ologies. In he p oposed
solu ion, we ha e shown i s , how o ob ain a seman ically
equi alen que y ha elimina es edundan elemen s and
de ec s o he s ha may inc emen he e iciency o he
que y p ocessing. This new equi alen que y exp ession is
ob ained by using he capabili ies o he DL sys ems. In his
s ep inconsis en que ies a e also de ec ed and in ensional
answe s may be gi en o he use . Nex , we ha e explained
he es o e i y i he que y can be answe ed om he
cache memo y. This es has o be checked only i a
cache memo y is a ailable. Then, we ha e p esen ed a
se o heu is ics applied in o de o pe o m an e icien
decomposi ion p ocess o he que y. Las , we ha e shown
how op imized mapping in o ma ions co esponding o he
decomposed subque ies can be ob ained as a p e ious s ep
o gene a e he sen ences in he que y languages used in he
unde lying da a eposi o ies. In summa y, we can say ha
ou wo k ea s all he s eps needed o answe que ies in
he conside ed con ex and p esen s new p oposals o all
o hem, al hough due o space limi a ions each s ep is no
explained in de ail.
Re e ences
[AKS96] Y. A ens, C.A. Knoblock, and W. Shen. Que y
e o mula ion o dynamic in o ma ion in eg a ion.
Jou nal o In elligen In o ma ion Sys ems, 6(2-3):99–
130, 1996.
[Al ] Al a is a. h p://www.al a is a.digi al.com.
[ASD
+
91] R. Ahmed, P. Smed , W. Du, W. Ken , M. Ke abchi,
and W.A. Li win. The Pegasus he e ogeneous mul i-
da abase sys em. IEEE Compu e , 24:19–27, Decem-
be 1991.
[BBMR89] A. Bo gida, R.J. B achman, D.L. McGuinness, and
L.A. Resnick. CLASSIC: A s uc u al da a model o
objec s. In P oceedings ACM SIGMOD-89, Po land,
O egon, 1989.
[Bo 92] A. Bo gida. F om ype sys ems o knowledge ep-
esen a ions: Na u al seman ics speci ica ions o de-
sc ip ion logics. In e na ional Jou nal on In elligen
and Coope a i e In o ma ion Sys ems, 1(1), 1992.
[CHS91] C. Colle , M. N. Huhns, and W. Shen. Resou ce
in eg a ion using a la geknowledge base in CARNOT.
IEEE Compu e , pages 55–62, Decembe 1991.
[De 93] P.T. De anbu. T ansla ing Desc ip ion Logics o
In o ma ion Se e Que ies. In P oceedings o he
ISMM In e na ional Con e ence on In o ma ion and
Knowledge Managemen CIKM, 1993.
[FRV96] D. Flo escu, L. Raschid, and P. Valdu iez. A me hod-
ology o que y e o mula ion in CIS using seman ic
knowledge. In e na ional Jou nal o Coope a i e In-
o ma ion Sys ems, 5(4):431–467, 1996.
[GIMB97] A. Go˜ni, A. Illa amendi, E. Mena, and J.M. Blanco.
An op imal cache o a ede a ed da abase sys em.
Jou nal o In elligen In o ma ion Sys ems, 9(2):125–
156, Sep embe /Oc obe 1997.
[G u93] T. G ube . A ansla ion app oach o po able on-
ology speci ica ions. Knowledge Acquisi ion, An
In e na ional Jou nal o Knowledge Acquisi ion o
Knowledge-Based Sys ems, 5(2), June 1993.
[G u94] T. G ube . Theo y BIBLIOGRAPHIC-DATA,
Sep embe 1994. h p://www-ksl.s an o d.edu/-
knowledge-sha ing/on ologies/h ml/bibliog aphic-
da a/index.h ml.
[In ] In oseek. h p://www.in oseek.com.
[KS96] V. Kashyap and A. She h. Seman ic and Schema ic
Similila i ies be ween Da abases Objec s: A Con ex -
based app oach. The VLDB Jou nal, 5(4), Decembe
1996.
[LSK95] A.Y. Le y, D. S i as a a, and T. Ki k. Da a model
and que y e alua ion in global in o ma ion sys ems.
Jou nal o In elligen In o ma ion Sys ems, 5(2):121–
143, Sep embe 1995.
[MP97] S. Milline and M. Papazoglou. Scalable in o ma ion
elici a ion in la ge he e ogeneous da abase ne wo ks.
To be published in IEEE In e ne Jou nal, 1997.
[Pie94] S. Piepenbu g. Easy MARC: A simpli ied guide
o c ea ing ca alog eco ds o lib a y au oma ion
sys ems: P e- o ma in eg a ion, 1994.
[ LNPS87] K. on Luck, B.Nebel, C. Pel ason, and A.Schmiedel.
The ana omy o he BACK sys em. Technical Repo
KIT Repo 41, Technical Uni e si y o Be lin, Be lin,
F.R.G., 1987.