A framework for ontology integration

DiegoCalvanese,GiuseppeDeGiacomo,MaurizioLenzerini

DipartimentodiInformaticaeSistemistica

Universit`adiRoma“LaSapienza”ViaSalaria113,00198Roma,Italy

{calvanese,degiacomo,lenzerini}@dis.uniroma1.it

Abstract.Oneofthebasicproblemsinthedevelopmentoftechniquesforthesemanticwebistheintegrationofontologies.Indeed,thewebisconstitutedbyavarietyofinformationsources,eachexpressedoveracertainontology,andinordertoextractinformationfromsuchsources,theirsemanticintegrationandreconciliationintermsofaglobalontologyisrequired.Inthispaper,weaddressthefundamentalproblemofhowtospecifythemappingbetweentheglobalontologyandthelocalontologies.Wearguethatforcapturingsuchmappinginanappropriateway,thenotionofqueryisacrucialone,sinceitisverylikelythataconceptinoneontologycorrespondstoaview(i.e.,aquery)overtheotherontologies.Asaresultqueryprocessinginontologyintegrationsystemsisstronglyrelatedtoview-basedqueryansweringindataintegration.

1Introduction

Oneofthebasicproblemsinthedevelopmentoftechniquesforthesemanticwebistheinte-grationofontologies.Indeed,thewebisconstitutedbyavarietyofinformationsources,andinordertoextractinformationfromsuchsources,theirsemanticintegrationandreconcilia-tionisrequired.Inthispaperwedealwithasituationwherewehavevariouslocalontologies,developedindependentlyfromeachother,andwearerequiredtobuildanintegrated,globalontologyasameanforextractinginformationfromthelocalones.Thus,themainpurposeoftheglobalontologyistoprovideaunifiedviewthroughwhichwecanquerythevariouslocalontologies.

Mostoftheworkcarriedoutonontologiesforthesemanticwebisonwhichlanguageorwhichmethodtousetobuildtheglobalontologyonthebasisofthelocalones[13,2].Forexample,theOntologyInferenceLayer(OIL)[13,2]proposestousearestrictedformoftheexpressiveanddecidableDLstudiedin[4]toexpressontologiesforthesemanticweb.

Inthispaper,weaddresswhatwebelieveisacrucialproblemforthesemanticweb:howdowespecifythemappingbetweentheglobalontologyandthelocalontologies.Thisaspectisthecentraloneifwewanttousetheglobalontologyforansweringqueriesinthecontextofthesemanticweb.Indeed,wearenotsimplyusingthelocalontologiesasanintermediatesteptowardstheglobalone.Instead,weareusingtheglobalontologyforaccessinginformationinthelocalones.Itisouropinionthat,althoughtheproblemofspecifyingthemappingbetweentheglobalandthelocalontologiesisattheheartofintegrationintheweb,itisnotdeeplyinvestigatedyet.

Wearguethateventhemostexpressiveontologyspecificationlanguagesarenotsufficientforinformationintegrationinthesemanticweb.Inarealworldsetting,differentontologies

arebuildbydifferentorganizationsfordifferentpurposes.Henceoneshouldexpectthesameinformationtoberepresentedindifferentformsandwithdifferentlevelsofabstractioninthevariousontologies.Whenmappingconceptsinthevariousontologiestoeachother,itisverylikelythataconceptinoneontologycorrespondstoaview(i.e.,aquery)overtheotherontologies.Observethatherethenotionof“query”isacrucialone.Indeed,toexpressmappingsamongconceptsindifferentontologies,suitablequerylanguagesshouldbeaddedtotheontologyspecificationlanguage,andconsideredinthevariousreasoningtasks,inthespiritof[4,5].Asaresultqueryprocessinginthissettingisstronglyrelatedtoview-basedqueryansweringindataintegrationsystems[20,17].Whatdistinguishesontologyintegrationfromdataintegrationasstudiedindatabases,isthat,whileindataintegrationoneassumesthateachsourceisbasicallyadatabases,i.e.,alogicaltheorywithasinglemodel,suchanassumptionisnotmadeinontologyintegration,wherealocalontologyisanarbitrarylogicaltheory,andhencecanhavemultiplemodels.

Ourmaincontributioninthispaperistopresentageneralframeworkforanontologyofintegrationwherethemappingbetweenontologiesisexpressedthroughsuitablemechanismsbasedonqueries,andtoillustratetheframeworkproposedwithtwosignificantcasestudies.Thepaperisorganizedasfollows.Inthenextsectionwesetupaformalframeworkforon-tologyintegration.InSections3and4,weillustratethesocalledglobal-centricapproachandlocal-centricapproachtointegration,andwediscussforeachofthetwoapproachesaspecificcasestudyshowingthesubtletiesinvolved.InSection5webrieflypresentanapproachtoin-tegrationthatgoesbeyondthedistinctionbetweenglobal-centricandlocal-centric.Finally,Section6concludesthepaper.2Ontologyintegrationframework

Inthissectionwesetupaformalframeworkforontologyintegrationsystems(OISs).Wearguethatthisframeworkprovidesthebasisofanontologyofintegration.Forthesakeofsimplicity,wewillrefertoasimplifiedframework,wherethecomponentsofanOISaretheglobalontology,thelocalontologies,andthemappingbetweenthetwo.Wecallsuchsystems“one-layered”.Morecomplexsituationscanbemodeledbyextendingtheframeworkinordertorepresent,forexample,mappingsbetweenlocalontologies(inthespiritof[12,6]),orglobalontologiesthatactaslocaloneswithrespecttoanotherlayer.

Inwhatfollows,oneofthemainaspectsisthedefinitionofthesemanticsofboththeOIS,andofqueriesposedtotheglobalontology.Forkeepingthingssimple,wewilluseinthefollowingauniquesemanticdomain∆,constitutedbyafixed,infinitesetofsymbols.Formally,anOISOisatriple󰀚G,S,MG,S󰀛,whereGistheglobalontology,Sisthesetoflocalontologies,andMG,SisthemappingbetweenGandthelocalontologiesinS.Globalontology.WedenotewithAGthealphabetoftermsoftheglobalontology,andweassumethattheglobalontologyGofanOISisexpressedasatheory(namedsimplyG)insomelogicLG.Localontologies.WeassumetohaveasetSofnlocalontologiesS1,...,Sn.WedenotewithASithealphabetoftermsofthelocalontologySi.WealsodenotewithAStheunionofalltheASi’s.WeassumethatthevariousASi’saremutuallydisjoint,andeachoneisdisjointfromthealphabetAG.Weassumethateachlocalontologyisexpressedas

atheory(namedsimplySi)insomelogicLSi,andweuseStodenotethecollectionoftheoriesS1,...,Sn.

Mapping.ThemappingMG,SistheheartoftheOIS,inthatitspecifieshowtheconcepts1

intheglobalontologyGandinthelocalontologiesSmaptoeachother.Semantics.Intuitively,inspecifyingthesemanticsofanOIS,wehavetostartwithamodelofthelocalontologies,andthecrucialpointistospecifywhicharethemodelsoftheglobalontology.Thus,forassigningsemanticstoanOISO=󰀚G,S,MG,S󰀛,westartbyconsideringalocalmodelDforO,i.e.,aninterpretationthatisamodelforallthetheoriesofS.WecallglobalinterpretationforOanyinterpretationforG.AglobalinterpretationIforOissaidtobeaglobalmodelforOwrtDif:

•IisamodelofG,and

•IsatisfiesthemappingMG,SwrtD.

Inthenextsections,wewillcomebacktothenotionofsatisfyingamappingwrtalocalmodel.ThesemanticsofO,denotedsem(O),isdefinedasfollows:

sem(O)={I|thereexistsalocalmodelDforO

s.t.IisaglobalmodelforOwrtD}

Queries.QueriesposedtoanOISOareexpressedintermsofaquerylanguageQGoverthealphabetAGandareintendedtoextractasetoftuplesofelementsof∆.Thus,everyqueryhasanassociatedarity,andthesemanticsofaqueryqofaritynisdefinedasfollows.TheanswerqOofqtoOisthesetoftuples

qO={󰀚c1,...,cn󰀛|forallI∈sem(O),󰀚c1,...,cn󰀛∈qI}

whereqIdenotestheresultofevaluatingqintheinterpretationI.

Aswesaidbefore,themappingMG,SrepresentstheheartofanOISO=󰀚G,S,MG,S󰀛.Intheusualapproachestoontologyintegration,themechanismsforspecifyingthemappingbetweenconceptsindifferentontologiesarelimitedtoexpressingdirectcorrespondencesbetweenterms.Wearguethat,inareal-worldsetting,oneneedsamuchmorepowerfulmechanism.Inparticular,suchamechanismshouldallowformappingaconceptinoneontologyintoaview,i.e.,aqueryovertheotherontologies,whichacquirestherelevantinformationbynavigatingandaggregatingseveralconcepts.

Followingtheresearchdoneindataintegration[16,17],wecandistinguishtwobasicapproachesfordefiningthismapping:

•theglobal-centricapproach,whereconceptsoftheglobalontologyGaremappedintoqueriesoverthelocalontologiesinS;

•thelocal-centricapproach,whereconceptsofthelocalontologiesinSaremappedtoqueriesovertheglobalontologyG.

Wediscussthesetwoapproachesinthefollowingsections.

1

Hereandbelowweusetheterm“concept”fordenotingaconceptoftheontology.

3Global-centricapproach

Intheglobal-centricapproach(akaglobal-as-viewapproach),weassumewehaveaquerylanguageVSoverthealphabetAS,andthemappingbetweentheglobalandthelocalon-tologiesisgivenbyassociatingtoeachtermintheglobalontologyaview,i.e.,aquery,overthelocalontologies.TheintendedmeaningofassociatingtoatermCinGaqueryVsoverS,isthatsuchaqueryrepresentsthebestwaytocharacterizetheinstancesofCusingtheconceptsinS.AfurthermechanismisusedtospecifyifthecorrespondencebetweenCandtheassociatedviewissound,complete,orexact.LetDbealocalmodelforO,andIaglobalinterpretationforO:

•Isatisfiesthecorrespondence󰀚C,Vs,sound󰀛inMG,SwrtD,ifallthetuplessatisfyingVsinDsatisfyCinI,

•Isatisfiesthecorrespondence󰀚C,Vs,complete󰀛inMG,SwrtD,ifnotupleotherthanthosesatisfyingVsinDsatisfiesCinI.

•Isatisfiesthecorrespondence󰀚C,Vs,exact󰀛inMG,SwrtD,ifthesetoftuplesthatsatisfyCinIisexactlythesetoftuplessatisfyingVsinD.

WesaythatIsatisfiesthemappingMG,SwrtD,ifIsatisfieseverycorrespondenceinMG,SwrtD.

Theglobal-centricapproachistheoneadoptedinmostdataintegrationsystems.Insuchsystems,sourcesaredatabases(ingeneralrelationalones),theglobalontologyisactuallyadatabaseschema(again,representedinrelationalform),andthemappingisspecifiedbyas-sociatingtoeachrelationintheglobalschemaonerelationalqueryoverthesourcerelations.Itisacommonopinionthatthismechanismallowforasimplequeryprocessingstrategy,whichbasicallyreducestounfoldingthequeryusingthedefinitionspecifiedinthemapping,soastotranslatethequeryintermsofaccessestothesources[20].Actually,whenweaddconstraints(evenofaverysimpleform)totheglobalschema,queryprocessingbecomesevenharder,asshowninthefollowingcasestudy.3.1

Acasestudy

Wenowsetupaglobal-centricframeworkforontologyintegration,whichisbasedonideasdevelopedfordataintegrationoverglobalschemasexpressedintheEntity-Relationshipmodel[3].Inparticular,wedescribethemaincomponentsoftheontologyintegrationsystem,andweprovidethesemanticsbothofthesystem,andofqueryanswering.TheOISO=󰀚G,S,MG,S󰀛isdefinedasfollows:•TheglobalontologyGisexpressedintheEntity-Relationshipmodel(orequivalentlyasUMLclassdiagrams).Inparticular,Gmayinclude:

–typingconstraintsonrelationships,assigninganentitytoeachcomponentoftherelationship;

–mandatoryparticipationtorelationships,sayingthateachinstanceofanentitymustparticipateasi-thcomponenttoarelationship;–ISArelationsbetweenbothentitiesandrelationships;

–typingconstraints,functionalrestrictions,andmandatoryexistence,forattributesbothofentitiesandofrelationships.

•ThelocalontologiesSareconstitutedsimplybyarelationalalphabetAS,andbytheextensionsoftherelationsinAS.Forexample,suchextensionsmaybeexpressedasrelationaldatabases.ObservethatweareassumingthatnointensionalrelationbetweentermsinASispresentinthelocalontologies.

•ThemappingMG,SbetweenGandSisgivenbyasetofcorrespondencesoftheform󰀚C,Vs,sound󰀛,whereCisaconcept(i.e.,eitheranentity,arelationship,oranattribute)intheglobalontologyandVsisaqueryoverS.Moreprecisely,

–Themappingassociatesaqueryofarity1toeachentityofG.

–Themappingassociatesaqueryofarity2toeachentityattributeAofG.Intuitively,ifthequeryretrievesthepair󰀚x,y󰀛fromtheextensionofthelocalontologies,thismeansthatyisavalueoftheattributeAoftheentityinstancex.Thus,thefirstargumentofthequerycorrespondstotheinstancesoftheentityforwhichAisdefined,andthesecondargumentcorrespondstothevaluesoftheattributeA.–ThemappingassociatesaqueryofarityntoeachrelationshipRofarityninG.Intuitively,ifthequeryretrievesthetuple󰀚x1,...,xn󰀛fromtheextensionofthelocalontologies,thismeansthat󰀚x1,...,xn󰀛isaninstanceofR.

–Themappingassociatesaqueryofarityn+1toeachattributeAofarelationshipRofarityninG.ThefirstnargumentsofthequerycorrespondtothetuplesofR,andthelastargumentcorrespondstothevaluesofA.

Asspecifiedabove,theintendedmeaningofthequeryVsassociatedtotheconceptCisthatitspecifieshowtoretrievethedatacorrespondingtoCintheglobalschemastartingfromthedataatthesources.Thisconfirmsthatwearefollowingtheglobal-as-viewsapproach:eachconceptintheglobalontologyisdefinedasaviewovertheconceptsinthelocalontologies.Wedonotposeanyconstraintonthelanguageusedtoexpressthequeriesinthemapping.Sincetheextensionsoflocalontologiesarerela-tionaldatabases,wesimplyassumethatthelanguageisabletoexpresscomputationsoverrelationaldatabases.

Tospecifythesemanticsofadataintegrationsystem,wehavetocharacterize,giventhesetoftuplesintheextensionofthevariousrelationsofthelocalontologies,whicharethedatasatisfyingtheglobalontology.Inprinciple,onewouldliketohaveasingleextensionasmodeloftheglobalontology.Indeed,thisisthecaseformostofthedataintegrationsystemsdescribedintheliterature.However,wewillshowinthefollowingthesurprisingresultthat,duetothepresenceofthesemanticconditionsthatareimplicitintheconceptualschemaG,ingeneral,wewillhavetoaccountforasetofpossibleextensions.

Example1.Figure1showstheglobalschemaG1ofadataintegrationsystemO1=󰀚G1,S1,M1󰀛,whereAgeisafunctionalattribute,StudenthasamandatoryparticipationintherelationshipEnrolled,EnrolledisaMember,andUniversityisaOrganization.Theschemamodelspersonswhocanbemembersofoneormoreorganizations,andstudentswhoare

PersonMemberOrganizationStudentAgeEnrolledUniversityFigure1:GlobalontologyofExample1

enrolledinuniversities.SupposethatSisconstitutedbyS1,S2,S3,S4,S5,S6,S7,S8,andthatthemappingM1isasfollows:

Person(x)Organization(x)Member(x,y)Student(x)Age(x,y)University(x)Enrolled(x,y)

←←←←←←←

S1(x)S2(x)

S7(x,z)∧S8(z,y)S3(x,y)∨S4(x)S3(x,y)∨S6(x,y,z)S5(x)S4(x,y)

FromthesemanticsoftheOISOitiseasytoseethat,givenalocalmodelD,severalsituationsarepossible:

1.Noglobalmodelexists.Thishappens,inparticular,whenthedataintheextensionofthelocalontologiesretrievedbythequeriesassociatedtotheelementsoftheglobalontologydonotsatisfythefunctionalattributeconstraints.2.Severalglobalmodelsexist.Thishappens,forexample,whenthedataintheextensionofthelocalontologiesretrievedbythequeriesassociatedtotheglobalconceptsdonotsatisfytheISArelationshipsoftheglobalontology.Inthiscase,itmayhappenthatseveralwaysexisttoaddsuitableobjectstotheelementsofGinordertosatisfytheconstraints.Eachsuchwaysyieldsaglobalmodel.Example2.ReferringtoExample1,consideralocalmodelD1,whereS3containsthetuple󰀚t1,a1󰀛,andS6containsthetuple󰀚t1,a2,v1󰀛.ThequeryassociatedtoAgebythemappingM1specifiesthat,ineverymodelofO1bothtuplesshouldbelongtotheextensionofAge.However,sinceAgeisafunctionalattributeinG1,itfollowsthatnomodelexistsfortheOISO1.

Example3.ReferringagaintoExample1,consideralocalmodelD2,whereS1containsp1andp2,S2containso1,S5containsu1,S4containst1,andthepairs󰀚p1,o1󰀛and󰀚p2,u1󰀛areinthejoinbetweenS7andS8.BythemappingM1,itfollowsthatineverymodelofO1,we

havethatp1,p2∈Person,󰀚p1,o1󰀛,󰀚p2,u1󰀛∈Member,o1∈Organization,t1∈Student,andu1∈University.Moreover,sinceG1specifiesthatStudenthasamandatoryparticipationintherelationshipEnrolled,ineverymodelforO1,t1mustbeenrolledinacertainuniversity.ThekeypointisthatnothingissaidinD2aboutwhichuniversity,andthereforewehavetoacceptasmodelsallinterpretationsforO1thatdifferintheuniversityt1isenrolledin.Intheframeworkproposed,itisassumedthatthefirstproblemissolvedbythequeriesextractingdatafromtheextensionofthelocalontologies.Inotherwords,itisassumedthat,foranyfunctionalattributeA,thecorrespondingqueryimplementsasuitabledatacleaningstrategy(see,e.g.,[15])thatensuresthat,foreverylocalmodelDandeveryx,thereisatmostonetuple(x,y)intheextensionofA(asimilarconditionholdsforfunctionalattributesofrelationships).

Thesecondproblemshowsthattheissueofqueryansweringwithincompleteinforma-tionarisesevenintheglobal-as-viewapproachtodataintegration.Indeed,theexistenceofmultipleglobalmodelsfortheOISimpliesthatqueryprocessingcannotsimplyreducetoevaluatingthequeryoverasinglerelationaldatabase.Rather,weshouldinprincipletakeallpossibleglobalmodelsintoaccountwhenansweringaquery.

Itisinterestingtoobservethatthereareatleasttwodifferentstrategiestosimplifythesetting,andovercomethisproblemthatarefrequentlyadoptedindataintegrationsys-tems[16,20,17]:

•Dataintegrationsystemsusuallyadoptasimplerdatamodel(often,aplainrelationaldatamodel)forexpressingtheglobalschema(i.e.,theglobalontology).Inthiscase,thedataretrievedfromthesources(i.e.,thelocalontologies)triviallyfitsintotheschema,andcanbedirectlyconsideredastheuniquedatabasetobeprocessedduringqueryanswering.•Thequeriesassociatedtotheconceptsoftheglobalschemaareoftenconsideredasexact.Inthiscase,analogouslytothepreviousone,itiseasytoseethattheonlyglobalexten-siontobeconsideredistheoneformedbythedataretrievedbytheextensionofthelocalontologies.However,observethat,whendatainthisextensiondonotobeyallsemanticconditionsthatareimplicitintheglobalontology,thissingleextensionisnotcoherentwiththeglobalontology,andtheOISisinconsistent.Thisimpliesthatqueryansweringinmeaningless.Wearguethat,intheusualcaseofautonomous,heterogeneouslocalon-tologies,itisveryunlikelythatdatafitintheglobalontology,andtherefore,thisapproachistoorestrictive,inthesensethattheOISwouldbeofteninconsistent.

Thefactthattheproblemofincompleteinformationisoverlookedincurrentapproachescanbeexplainedbyobservingthattraditionaldataintegrationsystemsfollowoneoftheabovementionedsimplifyingstrategies:theyeitherexpresstheglobalschemaasasetofplainrelations,orconsiderthesourcesasexact(see,forinstance,[11,19,1]).

In[3]wepresentanalgorithmforcomputingthesetofcertainanswerstoqueriesposedtoadataintegrationsystem.ThekeyfeatureofthealgorithmistoreasonaboutboththequeryandtheglobalontologyinordertoinferwhichtuplessatisfythequeryinallmodelsoftheOIS.Thus,thealgorithmdoesnotsimplyunfoldthequeryonthebasisofthemapping,asusuallydoneindataintegrationsystemsbasedontheglobal-as-viewapproach.Indeed,thealgorithmisabletoaddmoreanswerstothosedirectlyextractedfromthelocalontologies,byexploitingthesemanticconditionsexpressedintheconceptualglobalschema.

LetO=󰀚G,S,MG,S󰀛beanOIS,letDbealocalmodel,andletQbeaqueryovertheglobalontologyG.Thealgorithmisconstitutedbythreemajorsteps.

1.FromthequeryQ,obtainanewqueryexpandG(Q)overtheelementsoftheglobalontol-ogyGinwhichtheknowledgeinGthatisrelevantforQhasbeencompiledin.2.FromexpandG(Q),computethequeryunfoldMG,S(expandG(Q)),byunfoldingexpandG(Q)onthebasisofthemappingMG,S.TheunfoldingsimplysubstituteseachatomofexpandG(Q)withthequeryassociatedbyMG,Stotheelementintheatom.TheresultingunfoldMG,S(expandG(Q))isaqueryovertherelationsinthelocalontologies.3.EvaluatethequeryunfoldMG,S(expandG(Q))overthelocalmodelD.

Thelasttwostepsarequiteobvious.Instead,thefirstonerequirestofindawaytocompileintothequerythesemanticrelationsholdingamongtheconceptsoftheglobalschemaG.Awaytodosoisshownin[3].ThequeryexpandG(Q)returnedbythealgorithmisexponentialwrttoQ.However,expandG(Q)isaunionofconjunctivequeries,which,ifthequeriesinthemappingarepolynomial,makestheentirealgorithmpolynomialindatacomplexity.Example4.ReferringtoExample3,considerthequeryQ1toO1:

Q1(x)←Member(x,y)∧University(y)

Itiseasytoseethat{p2,t1}isthesetofcertainanswerstoQ1withrespecttoO1andD2.Thus,althoughD2doesnotindicateinwhichuniversityt1isenrolled,thesemanticsofO1specifiesthatt1isenrolledinauniversityinalllegaldatabaseforO1.SinceMemberisageneralizationofEnrolled,thisimpliesthatt1isinQO1,andhenceisinunfM1(expG1(Q1))evaluatedoverD2.

4Local-centricapproach

Inthelocal-centricapproach(akalocal-as-viewapproach),weassumewehaveaquerylan-guageVGoverthealphabetAG,andthemappingbetweentheglobalandthelocalontologiesisgivenbyassociatingtoeachterminthelocalontologiesaview,i.e.,aqueryovertheglobalontology.Again,theintendedmeaningofassociatingtoatermCinSaqueryVgoverG,isthatsuchaqueryrepresentsthebestwaytocharacterizetheinstancesofCusingtheconceptsinG.Asintheglobal-centricapproach,thecorrespondencebetweenCandtheassociatedviewcanbeeithersound,complete,orexact.LetDbealocalmodelforO,andIaglobalinterpretationforO:

•Isatisfiesthecorrespondence󰀚Vg,C,sound󰀛inMG,SwrtD,ifallthetuplessatisfyingCinDsatisfyVginI,

•Isatisfiesthecorrespondence󰀚Vg,C,complete󰀛inMG,SwrtD,ifnotupleotherthanthosesatisfyingCinDsatisfiesVginI,

•Isatisfiesthecorrespondence󰀚Vg,C,exact󰀛inMG,SwrtD,ifthesetoftuplesthatsatisfyCinDisexactlythesetoftuplessatisfyingVginI.

Asintheglobal-centricapproach,wesaythatIsatisfiesthemappingMG,SwrtD,ifIsatisfieseverycorrespondenceinMG,SwrtD.

Recentresearchworkondataintegrationfollowsthelocal-centricapproach[20,17,18,6,8].Themajorchallengeofthisapproachisthat,inordertoansweraqueryexpressedoverthe

globalschema,onemustbeabletoreformulatethequeryintermsofqueriestothesources.Whileintheglobal-centricapproachsuchareformulationisguidedbythecorrespondencesinthemapping,heretheproblemrequiresareasoningstep,soastoinferhowtousethesourcesforansweringthequery.Manyauthorspointoutthat,despiteitsdifficulty,thelocal-centricapproachbettersupportsadynamicenvironment,wherelocalontologiescanbeaddedtothesystemswithouttheneedforrestructuringtheglobalontology.4.1

Acasestudy

WepresenthereanOISarchitecturebasedontheuseofDescriptionLogicstorepresentontologies[6,7].Specifically,weadopttheDescriptionLogicDLR,inwhichbothclassesandn-aryrelationscanberepresented[4].WefirstintroduceDLR,andthenweillustratehowweusethelogictodefineanOIS.4.1.1

TheDescriptionLogicDLR

DescriptionLogics2(DLs)areknowledgerepresentationformalismsthatareabletocapturevirtuallyallclass-basedrepresentationformalismsusedinArtificialIntelligence,SoftwareEngineering,andDatabases[9,10].

Oneofthedistinguishingfeaturesoftheselogicsisthattheyhaveoptimalreasoningalgo-rithms,andpracticalsystemsimplementingsuchalgorithmsarenowusedinseveralprojects.InDLs,thedomainofinterestismodeledbymeansofconceptsandrelations,whichdenoteclassesofobjectsandrelationships,respectively.Here,wefocusourattentionontheDLDLR[4,6],whosebasicelementsareconcepts(unaryrelations),andn-aryrelations.WeassumetodealwithanalphabetAconstitutedbyafinitesetofatomicrelations,atomicconcepts,andconstants,denotedbyP,A,anda,respectively.WeuseRtodenotearbitraryrelations(ofgivenaritybetween2andnmax),andCtodenotearbitraryconcepts,respectivelybuiltaccordingtothefollowingsyntax:

C::=󰀈1|A|¬C|C1󰀞C2|∃[i]R|(≤k[i]R)R::=󰀈n|P|i/n:C|¬R|R1󰀞R2

whereidenotesacomponentofarelation,i.e.,anintegerbetween1andnmax,ndenotesthearityofarelation,i.e.,anintegerbetween2andnmax,andkdenotesanonnegativeinteger.Weconsideronlyconceptsandrelationsthatarewell-typed,whichmeansthatonlyrelationsofthesamearitynarecombinedtoformexpressionsoftypeR1󰀞R2(whichinheritthearityn),andi≤nwheneveridenotesacomponentofarelationofarityn.

ThesemanticsofDLRisspecifiedasfollows.AninterpretationIisconstitutedbyaninterpretationdomain∆I,andaninterpretationfunction·Ithatassignstoeachconstantanelementof∆Iundertheuniquenameassumption,toeachconceptCasubsetCIof∆I,andtoeachrelationRofaritynasubsetRIof(∆I)n,suchthattheconditionsinFigure2aresatisfied.Observethat,the“¬”constructoronrelationsisusedtoexpressdifferenceofrelations,andnotthecomplement[4].

ADLRknowledgebaseisasetofinclusionassertionsoftheform

C1󰀟C2

2

R1󰀟R2

Seehttp://dl.kr.orgforthehomepageofDescriptionLogics.

󰀈I1AI(¬C)I(C1󰀞C2)I

(∃[i]R)I(≤k[i]R)I󰀈InIPi/n:CI(¬R)I(R1󰀞R2)I

=⊆====⊆⊆===

∆I∆I

∆I\\CI

II

∩C2C1

{d∈∆I|∃󰀚d1,...,dn󰀛∈RI.di=d}

I

|di=d}≤k}{d∈∆I|󰀎{󰀚d1,...,dn󰀛∈R1(∆I)n

󰀈In

I

{󰀚d1,...,dn󰀛∈󰀈In|di∈C}

I

󰀈In\\R

II

∩R2R1

Figure2:SemanticrulesforDLR(P,R,R1,andR2havearityn)

whereC1andC2areconcepts,andR1andR2arerelationsofthesamearity.Aninclusion

II

⊆C2(resp.,assertionC1󰀟C2(resp.,R1󰀟R2)issatisfiedinaninterpretationIifC1

II

⊆R2).AninterpretationisamodelofaknowledgebaseK,ifitsatisfiesallassertionsinR1

K.KlogicallyimpliesaninclusionassertionρifρissatisfiedinallmodelsofK.

Finally,weintroducethenotionofqueryexpressioninDLR.Weassumethattheal-phabetAisenrichedwithafinitesetofvariablesymbols,simplycalledvariables.AqueryexpressionQoveraDLRknowledgebaseKisanon-recursivedatalogqueryoftheform

Q(󰀟x)←conj1(󰀟x,󰀟y1)∨···∨conjm(󰀟x,󰀟ym)

whereeachconji(󰀟x,󰀟yi)isaconjunctionofatoms,and󰀟x,󰀟yiareallthevariablesappearing

intheconjunct.EachatomhasoneoftheformsR(󰀟t)orC(t),where󰀟tandtarevariables

yiorconstantsinA,RisarelationofK,andCisaconceptofK.Thenumberofin󰀟xand󰀟

variablesof󰀟xiscalledthearityofQ,andisthearityoftherelationdenotedbythequeryQ.WeobservethattheatomsinqueryexpressionsarearbitraryDLRconceptsandrelations,freelyusedintheassertionsoftheKB.

GivenaninterpretationI,aqueryexpressionQofaritynisinterpretedasthesetQIofn-tuplesofconstants󰀚c1,...,cn󰀛,suchthat,whensubstitutingeachciforxi,theformula

∃󰀟y1.conj1(󰀟x,󰀟y1)∨···∨∃󰀟ym.conjm(󰀟x,󰀟ym)

evaluatestotrueinI.

DLRisequippedwitheffectivereasoningtechniquesthataresoundandcompletewithrespecttothesemantics.Inparticular,checkingwhetheragivenassertionlogicallyfollowsfromasetofassertionsisEXPTIME-completein(assumingthatnumbersareencodedinunary),andquerycontainment,i.e.,checkingwhetheronequeryiscontainedinanotheroneineverymodelofasetofassertions,isEXPTIME-hardandsolvablein2EXPTIME[4].4.1.2DLRlocal-centricOIS

Wenowsetupalocal-centricframeworkforontologyintegration,whichisbasedonideasdevelopedfordataintegrationoverDLRknowledgebases[6,5].Inparticular,wedescribe

themaincomponentsoftheontologyintegrationsystem,andweprovidethesemanticsbothofthesystem,andofqueryanswering.

Inthissetting,anOISO=󰀚G,S,MG,S󰀛isdefinedasfollows:•TheglobalontologyGisaDLRknowledgebase.

•ThelocalontologiesSareagainseenasasetofrelationseachgivingtheextensionofanontology-conceptintheontology.WeobservethatagainwehaveonlyextensionalknowledgeonsuchrelationsinS.

•ThemappingMG,SbetweenGandSisgivenbyasetofcorrespondencesoftheform󰀚Vg,T,as󰀛,whereTisarelationofalocalontology,VgisaqueryexpressionoverG,andasiseithersound,complete,orexact.

Observethatwecouldpartitiontheglobalontologyinseveralparts,oneforeachlocalontology,modelingtheintensionalknowledgeonthelocalontologywrttheOIS,plusoneforthereconciledglobalviewofsuchontologies.Bymakinguseofthesocalledinterschemaassertions[12]thedifferentpartscanberelatedtoeachattheintesionallevel.Forsimplicitywedonotdealwithinterschemaassertioninthiscasestudy,howeveritisimmediatetoextendtheframeworkpresentedheretoincludethemaswell[6,7].

Queryansweringinthissettingrequiresquitesophisticatedtechniquesthattakeintoac-counttheknowledgebothintheglobalontologyandinthemappinginansweringaqueryposedovertheglobalontologywiththedatacontainedinthelocalontologies.Suchqueryansweringtechniquesarestudiedin[5].

Example5.ConsiderforexampletheOISOd=󰀚Gd,Sd,Md󰀛definedasfollows:•TheglobalontologyGdistheDLRknowledgebase

American󰀞∃[1](RELATIVE󰀞2:Doctor)󰀟Wealthy

Surgeon󰀟Doctor

expressingthatAmericanswhohaveadoctorasrelativearewealthy,andthateachsur-geonisalsoadoctor.

•ThesetSdoflocalontologiesconsistsoftwoontologies,containingrespectivelytherelationsT1andT2,withextensions{ann,bill}and{ann,dan}.•ThemappingMG,Sis{󰀚V1,T1,sound󰀛,󰀚V2,T2,sound󰀛},with

V1(x)←RELATIVE(x,y)∧Surgeon(y)V2(x)←American(x)

GiventhequeryexpressionQw(x)←Wealthy(x)overGd,askingforthosewhoarewealthy,

dwehavethattheonlyanswerinQOwisann.Consideranadditionallocalontology,consisting

ofarelationT3withanextensionnotcontainingbill,andmappedtoGbythecorrespondence󰀚V3,T3,exact󰀛,withV3(x)←Wealthy(x).Then,fromtheconstraintsinGdandtheinfor-mationwehaveonthecorrespondences,wecanconcludethatbillisnotananswertothequeryaskingfortheAmericans.

5Combiningtheglobal-centricandlocal-centricapproaches

Theglobal-centricandthelocal-centricapproachcanbecombinedtogetherintoanapproachusingunrestrictedmappings,inwhichtherestrictionsonthedirectionofthecorrespondencebetweenglobalandlocalontologiesareovercome[14].Intheunrestrictedapproach,wehavebothaquerylanguageVSoverthealphabetAS,andaquerylanguageVGoverthealphabetAG,andthemappingbetweentheglobalandthelocalontologiesisgivenbyrelatingviewsovertheglobalontologytoviewsoverthelocalontologies.Again,theintendedmeaningofrelatingtheviewVgovertheglobalontologytotheviewVsoverthelocalontologyisthatVsrepresentsthebestwaytocharacterizetheobjectssatisfyingVgintermsoftheconceptsinS.Analogouslytotheothercases,thecorrespondencesbetweenVgandVscanbecharacterizedassound,complete,orexact.LetDbealocalmodelforO,andIaglobalinterpretationforO:

•Isatisfiesthecorrespondence󰀚Vg,Vs,sound󰀛inMG,SwrtD,ifallthetuplessatisfyingsatisfyingVsinDsatisfyVginI,

•Isatisfiesthecorrespondence󰀚Vg,Vs,complete󰀛inMG,SwrtD,ifnotupleotherthanthosesatisfyingVsinDsatisfyVginI,

•Isatisfiesthecorrespondence󰀚Vg,Vs,exact󰀛inMG,SwrtD,ifthesetoftuplesthatsatisfyVginIisexactlythesetoftuplessatisfyingVsinD.

Again,wesaythatIsatisfiesthemappingMG,SwrtD,ifIsatisfieseverycorrespon-denceinMG,SwrtD.

Example6.ConsidertheOISOu=󰀚Gu,Su,Mu󰀛,wherebothGuandthetwoontologiesS1andS2formingSuaresimplysetsofrelationswiththeirextensions.

•TheglobalontologyGucontainstwobinaryrelations,WorksFor,denotingresearchersandprojectstheyworkfor,andArea,denotingprojectsandresearchareastheybelongto.•ThelocalontologyS1containsabinaryrelationInterestedIndenotingpersonsandfieldstheyareinterestedin,andthelocalontologyS2containsabinaryrelationGetGrant,denotingresearchersandgrantsassignedtothem,andabinaryrelationGrantFordenotinggrantsandprojectstheyreferto.

•ThemappingMuisformedbythefollowingcorrespondences

–󰀚V1,InterestedIn,complete󰀛,withV1(r,f)←WorksFor(r,p)∧Area(p,f)–󰀚WorkFor,V2,sound󰀛,withV2(r,p)←GetGrant(r,g)∧GrantFor(g,p)

Thissituationcanberepresentedneitherintheglobal-centricnorinthelocal-centricap-proach.

Queryansweringinthisapproachislargelyunexplored,mainlybecauseitcombinesthedifficultiesoftheotherones.However,inarealworldsetting,thismaybetheonlyapproachthatprovidestheappropriateexpressivepower.

6Conclusions

Wehavepresentedageneralframeworkforontologyintegration,whereaglobalontologyisusedtoprovideaunifiedviewforqueryinglocalontologies,asinthesemanticweb.Theframeworkrepresentsasortofdesignspacefortheproblemofintegratingontologieswithinsemanticwebapplications.Wehavearguedthatthemappingbetweentheglobalandthelocalontologiesisthemainaspectoftheframework,andwehavediscussedvariousapproachesforspecifyingsuchamapping.Independentlyoftheapproach,wehavestressedthatthenotionofqueryiscrucialforthetaskofontologyintegration.

Thetwocasestudieswehavepresentedhaveshowntheneedofsophisticatedtechniquesforqueryansweringinanontologyintegrationsystem.Thetwocasestudiesillustratedsim-plifiedsettings,drawnfromdataintegration.Oneshouldexpectthingstobecomeevenmorecomplexwhenontologyintegrationisconsideredinitsfullgenerality.Recentlyseveralpro-posalshavebeenmade,basedontheideaofexpressingontologiesasknowledgebases,e.g.,inDescriptionLogics[13,2],andapplyingautomatedreasoningtechniquesforseveralser-vicesinthedesignofandtheinteractionwiththesemanticweb.Webelievehoweverthatsuchanideaneedstobeextendedbyconsideringqueriesasfirstordercitizensandhavingtheabilitytoreasononthem.References

[1]M.BouzeghoubandM.Lenzerini.Specialissueondataextraction,cleaning,andreconciliation.Infor-mationSystems,2001.Toappear.[2]J.Broekstra,M.Klein,D.Fensel,andI.Horrocks.AddingformalsemanticstotheWeb:buildingontop

ofRDFSchema.InProc.oftheECDL2000WorkshopontheSemanticWeb,2000.[3]A.Cal`ı,D.Calvanese,G.DeGiacomo,andM.Lenzerini.Accessingdataintegrationsystemsthrough

conceptualschemas.InProc.ofthe20thInt.Conf.onConceptualModeling(ER2001),2001.Toappear.[4]D.Calvanese,G.DeGiacomo,andM.Lenzerini.Onthedecidabilityofquerycontainmentundercon-straints.InProc.ofthe17thACMSIGACTSIGMODSIGARTSymp.onPrinciplesofDatabaseSystems(PODS’98),pages149–158,1998.[5]D.Calvanese,G.DeGiacomo,andM.Lenzerini.Answeringqueriesusingviewsoverdescriptionlogics

knowledgebases.InProc.ofthe17thNat.Conf.onArtificialIntelligence(AAAI2000),pages386–391,2000.[6]D.Calvanese,G.DeGiacomo,M.Lenzerini,D.Nardi,andR.Rosati.Descriptionlogicframeworkfor

informationintegration.InProc.ofthe6thInt.Conf.onPrinciplesofKnowledgeRepresentationandReasoning(KR’98),pages2–13,1998.[7]D.Calvanese,G.DeGiacomo,M.Lenzerini,D.Nardi,andR.Rosati.Informationintegration:Concep-tualmodelingandreasoningsupport.InProc.ofthe6thInt.Conf.onCooperativeInformationSystems(CoopIS’98),pages280–291,1998.[8]D.Calvanese,G.DeGiacomo,M.Lenzerini,andM.Y.Vardi.View-basedqueryprocessingandconstraint

satisfaction.InProc.ofthe15thIEEESymp.onLogicinComputerScience(LICS2000),pages361–371,2000.[9]D.Calvanese,M.Lenzerini,andD.Nardi.Descriptionlogicsforconceptualdatamodeling.InJ.Chomicki

andG.Saake,editors,LogicsforDatabasesandInformationSystems,pages229–2.KluwerAcademicPublisher,1998.[10]D.Calvanese,M.Lenzerini,andD.Nardi.Unifyingclass-basedrepresentationformalisms.J.ofArtificial

IntelligenceResearch,11:199–240,1999.

[11]M.J.Carey,L.M.Haas,P.M.Schwarz,M.Arya,W.F.Cody,R.Fagin,M.Flickner,A.Luniewski,

W.Niblack,D.Petkovic,J.Thomas,J.H.Williams,andE.L.Wimmers.Towardsheterogeneousmulti-mediainformationsystems:TheGarlicapproach.InRIDE-DOM,pages124–131,1995.[12]T.CatarciandM.Lenzerini.Representingandusinginterschemaknowledgeincooperativeinformation

systems.J.ofIntelligentandCooperativeInformationSystems,2(4):375–398,1993.[13]S.Decker,D.Fensel,F.vanHarmelen,I.Horrocks,S.Melnik,M.Klein,andJ.Broekstra.Knowledgerep-resentationontheweb.InProc.ofthe2000DescriptionLogicWorkshop(DL2000),pages–97.CEURElectronicWorkshopProceedings,http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-33/,2000.[14]M.Friedman,A.Levy,andT.Millstein.Navigationalplansfordataintegration.InProc.ofthe16thNat.

Conf.onArtificialIntelligence(AAAI’99),pages67–73.AAAIPress/TheMITPress,1999.[15]H.Galhardas,D.Florescu,D.Shasha,andE.Simon.Anextensibleframeworkfordatacleaning.Technical

Report3742,INRIA,Rocquencourt,1999.[16]R.Hull.Managingsemanticheterogeneityindatabases:Atheoreticalperspective.InProc.ofthe16th

ACMSIGACTSIGMODSIGARTSymp.onPrinciplesofDatabaseSystems(PODS’97),1997.[17]A.Y.Levy.Answeringqueriesusingviews:Asurvey.Technicalreport,UniversityofWashinghton,1999.[18]A.Y.Levy,D.Srivastava,andT.Kirk.Datamodelandqueryevaluationinglobalinformationsystems.J.

ofIntelligentInformationSystems,5:121–143,1995.[19]C.Li,R.Yerneni,V.Vassalos,H.Garcia-Molina,Y.Papakonstantinou,J.D.Ullman,andM.Valiveti.

CapabilitybasedmediationinTSIMMIS.InProc.oftheACMSIGMODInt.Conf.onManagementofData,pages5–566,1998.[20]J.D.Ullman.Informationintegrationusinglogicalviews.InProc.ofthe6thInt.Conf.onDatabase

Theory(ICDT’97),volume1186ofLectureNotesinComputerScience,pages19–40.Springer-Verlag,1997.