An Ontology Connected to Several Data Repositories: Query Processing Steps

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.