A Necessary Condition For Semantic Interoperability in the Large

ANecessaryConditionforSemantic

InteroperabilityintheLarge󰀁

PhilippeCudr´e-MaurouxandKarlAberer

SchoolofComputerandCommunicationSciencesSwissFederalInstituteofTechnology(EPFL)1010Lausanne,Switzerland{philippe.cudre-mauroux,karl.aberer}@epfl.ch

Abstract.WithnewstandardslikeRDForOWLpavingthewayfor

themuchanticipatedsemanticweb,anewbreedoflargescalesemanticsystemsisabouttoappear.Evenifresearchonsemanticreconciliationmethodsisabundant,itisnotclearhowinteroperableverylargescalesemanticsystemscanbe.Thispaperrepresentsafirstefforttowardsanalyticallyanalyzingsemanticinteroperabilityinthelarge:Byadaptingarecentgraph-theoreticframework,weexaminethedynamicsoflargescalesemanticsystemsandderiveanecessaryconditionforfosteringglobalsemanticinteroperability.

1Introduction

Informationsystemsareabouttoundergoprofoundchangesthroughthewide

adoptionofasetofsemanticstandardscomprisingRDF,RDFSorOWL.These

specificationsaimatprovidingmachine-processableinformationandshouldun-derpinthecreationofsystemswheredataaregivenwell-definedsemantics.

In[2],weintroducedSemanticGossipingasanewwayofreconcilingseman-

ticallyheterogeneousdomainsinanevolutionaryandcompletelydecentralized

manner.Wehaveshown[3]thatsetsofpair-wise,localtranslationscanbesuf-

ficientforcreatingaglobalself-healingsemanticnetworkwheresemantically

correcttranslationsgetreinforced.Avarietyofrelatedworks,fosteringglobal

interoperabilityfromlocalmappings(seeforexample[5,6,9])havealsoproven

tobesuccessful,demonstratingthegeneralvalidityofthisapproachrecently

termedasPeerDataManagement.Evenifmuchefforthasrecentlybeendevoted

tothecreationofsophisticatedschemestorelatepairsofschemasorontologies

(see[11]forasurvey),itisstillfarfrombeingclearhowsuchlarge-scaleseman-

ticsystemsevolveorhowtheycanbecharacterized.Forexample,evenifalack

ofontologymappingsclearlylimitsthequalityoftheoverallsemanticconsensus

inagivensystem,theexactrelationshipsbetweentheformerandthelatterare

unknown.Isthereaminimumnumberofmappingsrequiredtofostersemantic

󰀁Theworkpresentedinthispaperwassupported(inpart)bytheNationalCom-petenceCenterinResearchonMobileInformationandCommunicationSystems(NCCR-MICS),acentersupportedbytheSwissNationalScienceFoundationundergrantnumber5005-67322.

R.Meersman,Z.Tari(Eds.):CoopIS/DOA/ODBASE2004,LNCS3291,pp.859–872,2004.c󰀂Springer-VerlagBerlinHeidelberg2004860P.Cudr´e-MaurouxandK.Aberer

interoperabilityinanetworkofinformationsharingparties?Givenalargeset

ofontologiesandontologymappings,canwesomehowpredicttheimpactofa

queryissuedlocally?

Thispaperrepresentsafirstattempttolookattheproblemfromamacro-

scopicpointofview.Ourcontributionistwo-fold:First,wedevelopamodel

capturingtheproblemofsemanticinteroperabilitywithanadequategranular-

ity.Second,weidentifyrecentgraphtheoreticresultsandshowhowtheyare

(withsomeslightadaptation)applicabletoourproblem.Moreparticularly,we

deriveanecessaryconditiontofostersemanticinteroperabilityinthelargeand

presentamethodforevaluatingthepropagationofaqueryissuedlocally.Also,

wegivesomeinitialevaluationofourmethods.Therestofthispaperisor-

ganizedasfollows:Westartbyintroducingagenerallayeredrepresentationof

distributedsemanticsystems.Section3isdevotedtotheformalmodelwith

whichweanalyzesemanticinteroperabilityinthelarge.Themaintheoretical

resultsrelatedtosemanticinteroperabilityandsemanticcomponentsizesare

detailedinSection4andSection5.Finally,wediscusspracticalapplicationsof

ourmainresultsbeforeconcluding.

2TheModel

Large-scalenetworksaretraditionallyrepresentedbyagraph.Inourcase,how-

ever,asinglegraphisinsufficienttoaccuratelymodeltherelationshipsbetween

boththesystemsandtheirschemas.Wepresentbelowasetofrepresentational

modelsforlarge-scalesemanticsystemswhichwillthenbeusedthroughoutthe

restofthispaper.Wemodelinformationpartiesaspeersrelatedtoeachother

physically(Peer-to-Peermodel).Peersusevariousschemasorontologiestoanno-

tatetheirresources(Peer-to-Schemamodel).Finally,schemasthemselvescanbe

relatedthroughmappingswetermtranslationlinks(Schema-to-Schemamodel).

EachofthesemodelsrepresentsadistinctfacetoftheoverallPeerDataMan-

agementSystemandcanbequiteindependentoftheothertwo(as,forexample,

intheGridVinesystem[4]).

2.1ThePeer-to-PeerModel

Peersrepresentautonomouspartiesproducingandconsuminginformationina

system.Eachpeerp∈Phasabasiccommunicationmechanismthatallowsitto

establishconnectionswithotherpeers.Wedonotmakeanyotherassumptionon

thismechanism,exceptthatanypeershouldbeabletocontactanyotherpeer

inthesystem–eitherbybroadcasting(Gnutella)orbyusingacentral(Nap-

ster),hierarchical(DNS)ordecentralized(P-Grid[1])registry.Furthermore,we

assumethattheinformationandmeta-information(i.e.,metadata,schemasand

schematranslations)availableinthesystemareallindexedinasimilarway,

allowingapeertoretrieveanyresourceindependentlyofitsexactnature.