Web service integration via matching of interaction specifications

UNIVERSITY

OF TRENTO

DIPARTIMENTO DI INGEGNERIA E SCIENZA DELL’INFORMAZIONE

38050 Povo – Trento (Italy), Via Sommarive 14

http://www.disi.unitn.it

INTEGRATION OF SERVICES THROUGH STRUCTURED

SEMANTIC MATCHING

Paolo Besana, Fiona McNeill, Fausto Giunchiglia, Lorenzino Vaccari,

Gaia Trecarichi and Juan Pane

August 2008

Technical Report # DISI-08-038

Semanti Mat hing PaoloBesana

1

, FionaM Neill

1

,FaustoGiun higlia

2

,LorenzinoVa ari

2

,Gaia Tre hari hi

2

,JuanPane

2

1

UniversityofEdinburgh,S otland, p.besanasms.ed.a .uk

|

f.j.m neilled.a .uk

2

UniversityofTrento,Povo,Trento,Italy, {fausto

|

va ari

|

gtre ari

|

pane}dit.unitn.it

Abstra t The automated ommuni ation of servi es is ru ial to the su ess ofsystems su has theSemanti Web.If global standards(the use of whi his problemati ) are not stri tlyadhered to, this requires servi es to be able to interpret both the vo abulary of alls made to them and the stru ture of these alls. In this paper, we des ribe the life y leofintera tionwithin theOpenKnowledgesystem,whi hallows servi estobefound, onta tedandintera tedwithduringrun-time with-outanyprioragreementonsemanti s.Instrumentaltothisworkisour stru ture-preserving semanti mat hing te hnique, whi hautomati ally mat hes inputsand outputs of servi es with alls representing servi e requirements,evenifthevo abularyandstru tureofthose allsare dif-ferenttothoseexpe tedbytheservi eand unknownpriortorun-time. Wedes ribe indetail as enario showing the omplexity ofintera tion allowed by ourapproa h,and dis uss the evaluation we havedone on ourte hniquesandtheen ouragingresultsthishasprodu ed.

1 Introdu tion

Theproblem of automatedintegration of servi esiskeyto thesu essful real-isation of theSemanti Web, orany other systemwhere servi esintera t with one another. Sofar, this has proved di ult. Global ontologies allow dierent servi es to be expressed using the sameterms, whi h are thus understandable to all.Buttherearesigni antdi ulties withthenotionofaglobalontology: boththerelevan eoftermsandappropriate atagorisationofthosetermsisvery ontext dependent. An ontologythat in ludedalltermsthat ould berelevant to any situation would be infeasibly unwieldy and allow no exibility for dif-ferent interpretations of situations. However, this is not the only problem for ommuni ationofservi es.Callstoservi esarestru tured.Forexample,WSDL servi esrequireinputand outputmessages,whi hareexpe tedin aparti ular orderandaredenedwithintheWSDLleinaparti ularway.Soforservi esto intera t, therenotonlyneedsto beapro essforinterpretation ofthedierent vo abulariesbut alsoawayto dealwiththedierentstru tureofthe alls.

ex-Altova is asystemwhi hfa ilitatesthis manualmapping.However, perform-ingthisistime onsumingandnots alable.Additionally,thispresupposesthat oneknowsin advan e what servi es onewill berequiredto intera t with dur-ing run-time.This is perhapsfeasible in asmall, stati system, but in alarge, dynami systemwhereservi esmaybetemporary,maybeupdated,maysuer from o asional ommuni ationbreakdown, andso on,wedonotwish tolimit thenumberofservi eswhi h itis possibletointera twith.

Inthispaper,weproposeasolutiontothis problem. Throughfo ussingon sharedworkowsratherthansharedsemanti standards,weprovideawayto al-lowtheintera tionofsemanti allyheterogeneousservi estosu essfullyintera t withoneanother.Bynotrequiringsharedsemanti s,weallowservi edesigners to use languageand stru ture that is appropriateto theirworld-view and the given ontext.Removingtheneedforsharedsemanti snaturallyintrodu esthe needformat hingbetweentwodierentdes riptions;however,throughtheuse of these sharedworkows,weredu e the vastnessof the mat hingproblem by providinga ontextfor theintera tion to takepla e in:onlyterms relevant to that ontext need be interpreted, and the ontext itself provides valuable in-formation for the mat hing pro ess. This solution is lightweightenough to be donequi klyon-the-y,during run-time,sothat weneed haveno expe tations ofwhi hservi eswewillwanttointera twithinadvan eofrun-time.Moreover, thismat hingnotonlydete tsperfe tmat hesbut analsoidentifygoodenough mat hes,wheregoodenough isdeterminedthrough hangeableparameters[10℄. Thisvastly in reasestherangeofservi esitispossibletointera twith.

Theseintera tions takepla e within asystem,the OpenKnowledge 4

frame-work[29℄,whi hprovidestheinfrastru turene essaryforthefulllife- y leofthis intera tion pro ess.That is, adis overyservi eisprovidedto ndappropriate workowsforagivensituationand,thereby,tondpotentiallysuitableservi es with whi h tointera t; amat hingservi e(the fo usof thispaper)determines thesimilaritybetweenrequirementandability;atrust omponenttoallowusers to assess with whi h servi es they wish to intera t; and the infrastru ture to fa ilitatetheseintera tionsisprovided.

Se tion2introdu esthe languageused to deneintera tions. Se tion 5 de-nes the steps the peers follows in order to sele t and exe ute a distributed intera tion. Se tion 3des ribesthemat hingpro ess,andSe tion 4showsone ofthe asestudiesusedto evaluatetheframework.Evaluation ofourapproa h is givenin Se tion 6,Se tion 7presentsrelatedworks and Se tion8 on ludes thepaper.

2 Des ribing intera tions

The ore on eptin OpenKnowledgearetheintera tionsbetweenparti ipants, dened by Intera tion Models (IMs) written in Lightweight Coordination Cal- ulus: LCC[27,28℄ is a horeographylanguagebasedon

π

- al ulusand anbe

3

http://www.altova. om/ 4

M odel

:= {Clause, . . .}

Clause

:= Role :: Def

Role

:= a (T ype, Id)

Def

:= Role | M essage | Def then Def | Def or Def

M essage

:= M ⇒ Role | M ⇒ Role ← C | M ⇐ Role | C ← M ⇐ Role

C

:= Constant | P (T erm, . . .) | ¬C | C ∧ C | C ∨ C

T ype

:= T erm

Id

:= Constant | V ariable

M

:= T erm

T erm

:= Constant | V ariable | P (T erm, . . .)

Constant

:= lower case character sequence or number

V ariable

:= upper case character sequence or number

Figure1.LCCsyntax

annotation

:= @annotation(about, innerAnnotation)

about

:= @role(Role)|@message(M )|@constraint(T erm)|@variable(V ariable)

innerAnnotation

:= annotation|tree

tree

:= Constant|tree|Constant, tree

Knowledge expressesboth the ontrol-ow andthe data-ow perspe tivesofa workow:itdenesthea tivitiesthatneedtobeperformedandtheirorderand spe iestheowofdatabetweenthe omponentsandthesemanti stru tureof thedata.Mostor hestration-orientedworkowlanguagesspe ifythebehaviour ofasingleparti ipant:fortheotherparti ipants,onlytheirinvo ationandtheir repliesaredened.Nothingissaidontheirbehaviourandontheinterplaywith theothera tors:howtheya tandrea ttotheunfoldingmessagestheyre eive. Thebehaviouroftheotherparti ipantsisdenedinseparate,possiblyunknown, workows or it is embedded in their ode. IMsin OpenKnowledge spe ify the behaviourof allthe parti ipants,fo ussing in parti ularon theirinterplay, ex-pressedthroughtheex hangedmessages.

AnIM in LCCis ade laratives ript,that is alsodire tly exe utableusing rewrite rulesto expand the stateand nd thenextmovefor ea h parti ipant. An IM is a set of lauses, ea h of whi h denes how a role in the intera tion must be performed. Roles are des ribed by the type of role and an identier for the individual parti ipant undertaking that role. Depending on the IM, it maybe possiblefor several parti ipantsto play thesamerole: for example,in theIMin Figure 7,wewouldexpe tseverelparti ipantsto beplayingtherole ofre_ghter simulataneously(thenumberofpossibleparti ipantsforasingle roleisspe iedintheproto ol).Asingleparti ipantmayalsoplayseveralroles aton e.

Parti ipants in an intera tion hoose their entry-role. This is the role that theywillinitiallyplay,whi hmayentailplayingsubsequent,non-entryroles.For example,fulllingtheentry-rolesellermayentailtakingontheroledeliverer,or, in theIM in Figure 7,theentry-rolere_ghter_ oordinator leadsto therole re_ghter_ oordinator(List). Parti ipants follow the unfolding of the lause spe iedusinga ombinationsofthesequen eoperator(`

then

')or hoi e opera-tor(`

or

')to onne tmessagesand hangesofrole.Messagesareeitheroutgoing toanotherparti ipantinagivenrole(`

⇒

')orin omingfromanotherparti ipant in a given role (`

⇐

'). Message input/output or hange of role is ontrolled by a onstraintdened usingthenormallogi aloperatorsfor onjun tion, disjun -tionandnegation.Constraintsareexpressedasrst-orderterms,andthereisno expli itdierentiationbetweeninputsandoutputs.Forexample,the onstraint

get

_

route(From, To, Path)

shown in the intera tion model in Figure 7 ndsa pathbetweentwopoints:theinputparametersare

From

and

To

,whilethe out-putparameteris

Path

.Theinputparametersmustbealreadyinstantiatedwhen the onstraintis alled, while the output parameters are instantiated through the solvingof the onstraint. There is no ommitment to the method used to solve onstraints - so dierent parti ipants might operate dierent onstraint solvers(in ludinghumanintervention).Figure 1denesthesyntaxofLCC.

AnIMspe iesonlytheabstra tex hangeofmessagesbetweenparti ipants, andthefa tthatsome onditionmustholdbeforeorafterthesemessages:it an-notspe ifythetypeof theparametersin messagesor onstraints, ortimeouts.

sages hanges.

However,the framework relies on mat hing IMs with parti ipants' ompo-nents,whi h requiressemanti informationaboutboth,andrealworld appli a-tionsmayneedtoexpresstimeoutsoradditionalinformationsabout onstraints ormessages. To enablethis, weadded a layer of annotations,whose syntax is shown in Figure 2. Any element in the IM an be annotated: variables, mes-sages, roles, onstraints. Theonly annotationswhose meaning is spe ied and usedinside theframework arethoseaboutvariables,that denetheirsemanti stru tures.Theotherannotationsareopentofutureappli ations:dierent om-munity will usethem dierently. The framework provides a ess to them, but itsbehaviour anbeextended.

The semanti annotationof variables urrently uses keywords and trees of keywordsto representstru turedparameters.The s opeof avariable is arole lause, sovariable annotationsare inside role annotations. Figure 3 shows an example of annotation: the variable Event, within the role alarmClo k, is a tree stru ture whose nodes are the name, the des ription and the date of the event.Thedateisatreestru ture omposedbyyear,monthandday.Usingtags simpliestheworkofthedevelopers,and makesthe ode morereadablebut is lessstringent:itispossibletorepla etagswithURIfromformalontologies.

IntheOpenKnowledgesystem,weexpe tthatonlyaminorityofuserswould beinterestedinwritingtheirownIMs.Generally,userswillsear hforandresuse thoseIMsthathavebeenwrittenbythis oregroup.Forthosethatwishtowrite theirownIMsor toalterexistingIMsto bettersuittheirpurposes, weprovide toolstofa ilitatethis.However,IMsareintentedtobegeneralandreusableand themajorityofusersarefreetoignorethete hni aldetaildis ussedhere.

a(alarmClo k,A)::

alert(Event)=>a(re ipient,R) <- importantAlert(Event) ...

annotation(role(alarmClo k),

annotation(variable(Event),ev ent( name, des ripti on,da te(y ear,m onth ,day) ))) Figure3.Exampleofannotatedvariable

The IMs are published by the authors on the distributed dis overy servi e [22℄withakeyword-baseddes ription.TherolesintheIMsareplayedbypeers: a peer is a node in the network that is able to perform the basi a tivities of subs ribing to a role in an IM and satisfying the onstraints in that role. The OpenKnowledge kernel provides the fun tionality needed to subs ribe to a role and theframework for handlingthe plug-in omponents used to satisfy onstraints.Aplug-in omponentisjarlethatprovideaninterfa etoasetof annotatedmethods [3℄. Themethods anbe simplewrappersforwebservi es. We havedeveloped atoolthat generates awrapper omponentfrom aWSDL

Skype,oraserverappli ationthatsolvesthe onstraintsautomati ally,possibly allingthewebservi eswrappedbythe omponentsora essingadatabase.

Intera tionsareruninorderto performsometaskthatrequires the oordi-nationofvariousparti ipants.Assumingthatanintera tionmodelforthetask hasalreadybeenpublished,whentheneedforsu hataskarises,thelife y leof anintera tionis:

Intera tion sele tion: apeerthatwantstoperformsometasksear hesonthe dis overyservi e for the published IMs for the task bysending a keyword query. Thedis overyservi ereplieswith alistof IMs satisfyingthequery. Thepeerneedsto omparethere eivedIMswithitsplug-in omponents,in ordertosele ttheonethatbestmat hesits apabilities:Se tion3des ribes thepro essindetail.IfitndsasuitableIM,itsubs ribesonthedis overy servi eto perform the appropriate role in it. Forexample, in the s enario des ribed in Se tion 4, reghters subs ribe to play the role re_ghter andvariousroutenders(whi hmaybelongtodierentorganisationsorbe independent)subs ribetotheroleroute_servi e.Whenthere oordinator needstotellthereghtertogosomewhere,itlookupthisIM,triestomat h its omponents with the onstraints and then subs ribes to it. In another s enario,su h asabuyer/sellerone, various vendorsmaybesubs ribed to dierent pur hase IMs: when a ustomer needs to buy something, it look up for the pur hase IMs and then subs ribes to the one the best ts its omponent.

bootstrap: when all the roles in an IM are subs ribed, the dis overy servi e randomlysele tsapeerin thenetwork,askingittoplaythe oordinatorof theintera tion. This peer may ormay not be subs ribed to play arole in the IM - though if the peer network is large, this would be very unlikely. If it a epts,it be omesthe IM oordinator (not to be onfused with any oordinationrolewithintheIM,su hasthere oordinator)andasksallthe subs ribed peers to sele t whothey wantto intera t with. The peers may use dierent me hanismsto sele t the peers: they an use their own past experien e,ora ess asharedrepositoryofexperien es,orask otherpeers. The OpenKnowledge system provides atrust omponent to assist peer in makingthis assessment[10℄. After re eivingthe peers'preferen es, the IM oordinator reatesagroupofpeers whoareallhappytointera twithone anotherintheirproposedroles.Ifthegroup oversalltheroles,itstartsthe intera tion. Inthe emergen y response s enario,when the re oordinator subs ribestotheIMinFigure7,thedis overyservi es he kswhetherallthe rolesaresubs ribed.Ifso,thedis overyservi e andelegatearandompeer tobetheIM oordinatorandbootstraptheintera tion.Allpeerssubs ribed re eivethelistofthesubs riptions.Theemergen y oordinatormayhavean internallistofreghterto onta t,and hooseto intera tonlywiththem. In the pur hase s enario, the ustomer may want to intera t only with a spe i vendorashetrustit.Thevendor,ontheotherhand,mayreje tthe

theIM,andrunsitlo ally.Themessagesareex hangedbetweentheproxies, whilethepeersare onta tedinordertosolvethe onstraints.Intheexample inFigure9,thereghter1 is alledto solvethe onstraint

getPos

(Pos)

.If thepeerappli ationrunsonthereghter'spalmdevi e,themethodsolving the onstraintmaya ess the intenal GPS, orbeepand ask the person to introdu etheinformationthroughaGUI.

follow-up: after the runof the intera tion, the IM oordinatorsends the log ofthe intera tion to allthe involved peer so that they ananalyseit. The analysis an be aimed at omputing a trustvaluefor the other peers [10℄ tobeusedin sele tingpeersin future intera tionsorto reate astatisti al modelforthe ontentofthemessages,inorderto improvemapping[4℄.For example,aftertheintera tioninFigure7hasrun,areghtermayndthat thepathprovidedbytheroute-nderisblo kedandreport somewhere(for exampleonareputation server)that therouteservi ehasbeenunreliable. If,intera tion after intera tion, the routeservi e is onsistently unreliable, itwill besele tedlessandlessbytheotherpeers.

Inamoreor hestrationorientedmodel,theinvo ationstoservi esarenormally grounded at design time by the designer of the workow. In this model, the peersde ide totakepartin intera tions: they anlook upanintera tion fora spe i task,they an bealertedwhen newintera tionsare published, orthey anbeaskedtoevaluateanintera tionupontherequestofanotherpeer,butin all asestheyevaluatetheIMstheyre eiveandthen sele tthosetheywantto subs ribeto. Thetaskofhandlingheterogeneityisthereforedistributed among thepeers.

3 Mat hing servi e des riptions

One of the key feature of the framework is its inherent apabilityof handling heterogeneitydynami ally.Apeer andownloadaplug-in omponentwrittenfor aslightlydierentIMthantheoneinwhi hthepeerwantstoparti ipate:the frameworktriesto mat hthemethods inthe omponentswiththe onstraints, reatinganadaptorfortransparentlya essingtheparametersfrom withinthe method. Even in situations where the intera tions and the omponents where agreedin advan e,theymaydriftovertime.

Themethods, asbriey statedabove,areannotatedin asimilarwaytothe onstraints(usingJava5annotationme hanism):thearguments anbe stru -tures,and the elementsin thestru tures area essed using theirpath. Figure 4showsanexample ofa method that would bemat hed by theframework to the onstraintimportantAlert(Event)in Figure3,obtainingthe orrespon-den esin Figure5.

Internally, themethod a essesthe elements of itsarguments using the lo- ally denedstru ture: soto a essthedayofthedate oftheevent,it willuse

...

MethodSemanti (language=tag ,

args={event(name_of_event, o mment ), date(day,month,year))} boolean relevantAlert(Argument E, Argument D){...}

... }

Figure4.Exampleofannotatedmethod

Figure5.Mat hingbetweenthe onstraintinFigure3andthemethodinFigure4.

dened in theIM and howit wasused bythe other peers: the a ess and the storageoftheargumentsarede oupledbyanadaptor.

Ifa omponentwrapsaWSDLle,ea hmethod orrespondstoanoperation inWSDL,andthemethodannotationsree tthestru turesdenedinit:thanks to theadaptor, a essing thewebservi e isde oupled from therepresentation ofthe onstraintin theIM.

Themat hingpro ess isorganizedin twosteps:

(i)

nodemat hing and

(ii)

tree mat hing. Node mat hing solves the semanti heterogeneity problem by onsidering only labels at nodes and ontextual information of the trees. We useheretheS-Mat hsystem[17℄. Te hni ally,twonodes

n

1

∈ T 1

and

n

2

∈ T 2

mat hi:

c@n

1

R c@n

2

holds,where

c@n

1

and

c@n

2

arethe on eptsatnodes

n

₁

and

n

2

,and

R

∈ {=, ⊑, ⊒}

.Insemanti mat hing[13,14,9℄ asimplemented in the S-Mat hsystem [17℄ thekeyideais that therelations, e.g.,equivalen e and subsumption, betweennodesare determined by

(i)

expressingthe entities oftheontologiesaslogi alformulasandby

(ii)

redu ingthemat hingproblem to alogi al validity problem. Spe i ally, the entities are translated into logi- alformulaswhi hexpli itlyexpressthe on eptdes riptionsasen odedinthe ontologystru ture and in externalresour es,su h asWordNet [8℄. Thisallows foratranslationofthemat hingprobleminto alogi alvalidityproblem,whi h anthenbee ientlyresolvedusingsoundand ompletestate-of-the-art satis-abilitysolvers[15℄. Notethattheresultofthisstageisthesetof one-to-many orresponden esholding betweenthenodesofthetrees.

Tree mat hing, in turn, exploits the results of the node mat hing and the stru ture of the trees to nd if these globally mat h ea h other. Spe i ally, given the orresponden es produ ed by the node mat hing, abstra tion

oper-variablesto variables.Then,thepreserved orresponden esareusedasallowed operationsofatreeeditdistan einordertodetermineglobalsimilaritybetween trees under onsideration. If this global similarity measure is higher than an empiri allyestablishedthreshold,thetreesare onsideredtobesimilarenough, andare onsideredtobenotsimilarotherwise.Te hni ally,twotrees

T

1

and

T

2

approximatelymat hi thereisat leastonenode

n

1i

in

T

1

and anode

n

2j

in

T

2

su hthat:

(i) n

1i

approximatelymat hes

n

2j

,and

(ii)

allan estorsof

n

1i

are approximatelymat hedto thean estorsof

n

2j

,where

i

=1,...,N1;

j

=1,...,N2; N1andN2arethenumberofnodesin

T

1

and

T

2

,respe tively.

Semanti heterogeneityis thereforeredu ed in twosteps:

(i)

mat hing the webservi es,therebyobtainingingan alignment, and

(ii)

using this alignment forthea tualwebservi eintegration.Thispro essisdis ussedindetailin [16℄.

4 Case study

Figure6.A tivitydiagramfor theintera tion

5 Life y le

TheOpenKnowledgesystemisfullygeneraland anbeappliedin anydomain in whi hsystems(orpeers,servi es,pro esses,et )areintera ting. However,it has beenspe i ally evaluated in twotestbeds, one of whi h is emergen y re-sponse.Thiswas hosenasbeingaparti ularlyknowledge-intensiveanddynami appli ationdomain, withmanyplayersandahighpotentialforunexpe ted

de-a(f ire

_

f ighter

_

coordinator, FFC

) ::

null

← getPeers (“fire

_

fighter”, FFL)

then a(fire

_

fighter

_

coordinator

(FFL), FFC )

a(fire

_

fighter

_

coordinator

(F F L), F F C) ::

null

← F F L = []

or

alert(M P ) ⇒ a(fire

_

fighter , FFH

) ← FFL = [FFH |FFT ] and assign

_

mp(FFH , MP)

then

a(fire

_

fighter

_

coordinator

(FFT ), FFC )

!

a(fire

_

fighter , FF) ::

alert

(MP) ⇐ (fire

_

fighter

_

coordinator , FFC

)

then null

← getP os(Pos)

then

(null ← equal(MP , Pos))

or

request

_

route(Pos, MP ) ⇒ a(route

_

service, RS)

then route(From, To, Path) ⇐ a(route

_

service, RS

)

then null

← goto(MP , Path)

!

a(route

_

service, RS

) ::

request

_

route

(From, To) ⇐ a(fire

_

fighter , FF)

then route(From, To, Path) ⇒ a(fire

_

fighter , FF) ← get

_

rout e(From, To, Path)

then a(route

_

service, RS)

Figure7.IMforthee-res ueintera tion

@annotation (@role (route

_

f inder) ,

@annotation (@variable(F rom), f rom(location(name, lat, long))))

@annotation (@role (route

_

f inder) ,

@annotation (@variable(T o), to (location (name, lat, long))))

@annotation (@role (route

_

f inder) ,

@annotation (@variable(P ath), path (list (location (name, lat, long)))))

Figure8.Semanti annotationsrelativetotheintera tion

Inthis se tion, we briey outline the general s enarioand then des ribea spe i intera tion in moredetail,highlighting where thete hniques dis ussed in thispaperwillbeutilised.

Thegenerals enarioweareexploringisthe aseoftheoodingoftheriver Adigein theTrentinoregionofItaly,whi h presentsasigni antthreatto the ity ofTrento and thesurrounding areaandwhi hhas ooded seriouslymany times before, most notablyonNovember4th,1966. Wehave largeamountsof data from the 1966 ood, as well as data on erning the emergen y ooding responseplansoftheTrentinoauthorities.Aroundthisdata,wehavedeveloped s enariosofintera tingpeers:forexample, oordination entres,emergen y mon-itoringservi es,therebrigade,sensornodes,GISsystems,routendingservi es andweatherservi es.

Emergen y response is not inherently peer-to-peer: we would of ourse ex-pe tthatthekeyplayerswouldhavestrategiesworkedoutwellinadvan eand would have established the infrastru ture and vo abulary for ommuni ating withotherkeyplayers.However,the haoti natureofanemergen ymeansthat manyplayerswhowillnothavebeenableto oordinateinadvan e,orwhowere not expe ted to parti ipate, may be ome involved. Additionally, servi es who were partof an emergen yresponse may be unexpe tedly unavailable or may be swamped by requests, and in su h a situation,it is ru ial that the emer-gen y response an arry onregardless. Additionally, servi e may developand hangeanditisunrealisti toexpe tthese hangeswouldalwaysbeknownand a ountedforin advan e.

Theparti ularintera tionwefo usonhereisthere ontrol entresending itsreteamstodestinationswheretheyareneeded.TheIMforthisintera tion is shown in Figure7and Figure8showstheannotationsforthis IM. Figure6 illustratesthisintera tionasana tivitydiagramandFigure9representsa pos-siblerunofthisintera tionwithtworeteams. Thelife y leoftheintera tion intera tionpro essisillustratedinFigure10

monitoring entreanddetailsofthe urrentstateoftheood,togetherwith informationaboutvulnerablepeopleandgoods.There oordination entre thenworksoutthepla eswhere thereteamsshould besentto(this part ofthepro essisnotdes ribedinthediagramsortheIM).

 The re oordination entre uses the routing servi e to lo ate the teams that are subs ribed to playing the role of re team. Of ourse, we may assumethatthere oordination entreknowswhothereteamsare,sothis routingpro essmaynotbene essary,buttheadvantageisthat itprovides informationaboutwhoisavailableto playtheirroleatanygiventime.  There oordination entre ir ulatesoneofthe hosendestinationstoea h

ofthereteams.Inthisparti ulars enario,thisisdonearbitrarilywithno referen eto wherethereteams urrentlyare.

 On e a re team re eives its destination, it will rst he k whether it is already at that destination and, if not, it will make plans to move there. Thisinvolvesmovingontoanewpartoftheintera tion,thistimeinvolving aroutingservi e,tondouthowitshouldgetto the hosendestination.  Theroutingservi eisabletoprovidearoutebetweentwopointsthattakes

intoa ountroadsthat mightbeooded, blo kedorotherwiseina esible. It does this by having a map of the area and through running separate intera tions with sensor nodes and with other peers to keep tra k of the urrentstateoftheroads.

 On e the re teams havea route, they move to their destination and the intera tionterminates.

We would expe t, sin e these intera tions represent the expe ted proto ol of a ooding response, that the re teams would already know a routingservi e and would have pra ti ed these intera tions. However, there are nevertheless reasonswhy all to su h aroutingservi emaybeinappropriate.Forexample, the routing servi e may have altered over time - the route-servi e peer may be involved frequently in many other intera tions and its omponents may be hangedovertimetoadaptbettertotheseintera tions-andhavefailedtokeep the re servi e up to date with these hanges (a servi e would not normally expe ttokeepallservi eusersuptodate),meaningthatthe allthereservi e makeswould bein orre t and mat hing would be required for the intera tion to su eed. Other situations ould be that the routing servi e lost onne tion or wasswamped with requests, and the re team would then have to use the dis overyservi etolo ateanewroutingservi eandreusetheoldroutingservi e allto allthisnewroutingservi e.

6 Evaluation

We have seen that drifting an ause heterogeneity between omponents and IMs: omponents that were designed for a parti ular intera tion are used in

unrelatedlabel.Theunrelatedlabelisrandomlysele tedfromadi tionary. Example:

 Originaltree:find_Address_By_Point(point, address_Finder_Options, part)

 Alteredtree:find_Address_By_Point( atom_firmer, dis ussion, part)

2. addorremove aterminanodelabel. Example:

 Originaltree:find_Address_By_Point(point,a ddres s_Fin der_ Optio ns, part)

 Modiedtree:find_By_Point(toast_point, address_Options, surfa e_part)

3. repla e a term in a node label with a related one: e.g., by using synonyms, hyponyms,hypernymsfromWordNet3.0.

Example:

 Originaltree:find_Address_By_Point(point,a ddres s_Fin der_ Optio ns, part)

 Modiedtree:find_Address_By_Point(aim,add ress _Find er_O ption s, se tion)

4. altersynta ti ally alabel: hara ters inthelabelaredropped,added,or hanged. Example:

 Originaltree:find_Address_By_Point(point,a ddres s_Fin der_ Optio ns, part)

 Modiedtree:finm_Address_By_Poioat(einqt, ddress_Finder_Optxions, vpar )

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Recall

Alteration Operations: Alter semantically anmd syntactically a label, threshold = 0.8: Recall

Meaning

Syntax

Recall

Figure11.Re allforin reasingdierentfun tions

originalintera tion,mat hing isrequired. Similarly, intera tionsdesignedfora spe i ontext maybeusedfordierentaimsand hangetoadapt.Moreover, newintera tionsor omponents anbedevelopedby opyingothers.

Startingfromtheseassumption,wetriedtoevaluatehowthemat hing me h-anism,des ribedinSe tion3, an opewiththesesortofheterogeneity.

Thus, the evaluation datasetwas omposed of trees that are alterations of severaloriginaltrees.Initially,80treeswerebuiltoutoftheESRIAr Web Ser-vi es(SOAPmethods

5

).Examplesin lude:find_Address_By_Point(point, address_Finder_Options,part),get_Distan e(lo ation1, lo ation2, num_Points, return_Geometry, token, units)and onvert_Map_Coords_ To_Pixel_Coords(map_Area, map_Size, map_Coords, token).Then,forea h ofthe80originaltrees,20alteredoneswereautomati allygenerated.Pairswere omposed of the original tree and one varied tree, thereby resulting in 1600 mat hingtasks,whi hwerethenmat hedusingourstru ture-preserving seman-ti mat hing te hniques. The tree alteration pro edure has been inspired by the work in Euzenat [6℄ onsystemati ben hmarks. Thealteration operations, semanti orsynta ti ,areappliedtonodesandareshownin Table1.

Sin ethetree alterationsmadeare known, these providetheground truth, andhen ethereferen eresultsareavailableforfreeby onstru tion:thisallows forthe omputationofthemat hingqualitymeasures,su hasPre ision(whi h is a orre tness measure) and Re all (whi h is a ompleteness measure). The alterations are applied probabilitisti ally on ea h node of the original tree: in- reasingtheprobabilitiesofthemodi ationsitispossibletoobtaintreesthat arestatisti allymoreandmoredistantfromtheoriginalone.

Figure11 showshow re allbehaveswhenthe probabilitiesofsynta ti and semanti alterationsare in reased.Re all de reasesslowly: onlywhen both

experiments,pre isionwasalwaysveryhigh.Thisisnotun ommoninmat hing s enarios,wherere allisoftentheproblem.

7 Related work

Webelievethatthisapproa htostru turedmat hingisuniqueandthereforeit isdi ulttoperformany omparitiveanalysis.Inordertodemonstratethatwe makeuseofpowerfulontologymat hingtoolsforthestandardontologymat hing step ofthe pro ess, we an ompare S-Mat hagainst otherontologymat hing tools. However, the full stru ture preserving mat hing addresses a previously unsolvedproblem.Inthisse tion,wedis ussothermethodsthataddresssimilar problems.

Theproblemoflo ationofwebservi esonthebasisofthe apabilities that theyprovide(oftenreferredasthemat hmakingproblem)hasre entlyre eived a onsiderableattention. Mostof theapproa hesto themat hmaking problem sofaremployedasingleontologyapproa h(i.e.,thewebservi esareassumedto bedes ribedbythe on eptstakenfromthesharedontology).See[21,23,26℄for example.Probablythemostsimilartooursistheapproa htakenin METEOR-S[1℄and in[25℄,where theservi esareassumedto beannotatedwiththe on- epts taken from various ontologies. Thenthe mat hmaking problem is solved by theappli ation of themat hing algorithm. The algorithm ombines the re-sultsofatomi mat hersthat roughly orrespondtotheelementlevelmat hers exploited as partofouralgorithm. In ontrast tothis work,weexploit amore sophisti atedmat hing te hniquethat allowsusto utilisethe ontextprovided bytherstorderterm.

Manydiversesolutionstotheontologymat hingproblemhavebeenproposed sofar.See[30℄fora omprehensivesurveyand[7,24,5,18,2,20,31℄forindividual solutions.Howevermosteorts has been devoted to omputation ofthe orre-sponden esholding among the lassesof des riptionlogi ontologies.Re ently, several approa hesallowed omputationof orresponden esholding amongthe obje tproperties (or binarypredi ates) [32℄. The approa h taken in [19℄ fa il-itates the nding of orresponden es holding among parts of des ription logi ontologiesorsubgraphsextra tedfromtheontologygraphs.In ontrasttothese approa hes,weallow the omputation of orresponden es holding among rst orderterms.

8 Con lusion

Su essful servi eintegration is fundamental to therealisationof thesemanti web. The ommon approa h is to write workowsthat integrate servi e alls, reatinganew,moresophisti atedservi e. Theapproa hwehavepresentedin this paper, basedon the OpenKnowledge proje t, relies on shareddistributed workows, alled Intera tion Models. We havedes ribed thelife y le of an

in-ourstru ture-preservingsemanti mat hingte hniquethatallowsustomapthe alls toservi esfrom theseworkowswiththeinputsand outputsexpe tedby the servi e, even when these are unknown prior to run-time. In this way, we fa ilitatetheautomatedintera tionofservi eswithoutanyagreedsemanti sor anyexpe tationspriortorun-timeofwhatservi ewewillintera twith.Wehave illustratedthispro essthrougha asestudybasedonemergen yresponse and havepresentedpromising resultsindi atingthee a yofthisapproa h.

Referen es

1. R.Aggarwal,K.Verma,J.A.Miller,andW.Milnor.Constraintdrivenwebservi e ompositioninMETEOR-S. InPro eedingsofIEEE SCC,2004.

2. S.Bergamas hi, S.Castano,and M. Vin ini. Semanti integration of semistru -turedandstru tureddatasour es. SIGMODRe ord,28(1),1999.

3. P.Besana,D.Dupplaw,andA.DePinni k.Openknowledgedeliverable1.3: Plug-in omponents. Te hni alreport,2007.

4. P.Besanaand D.Robertson. Howservi e horeography statisti sredu e the on-tologymappingproblem. InISWC2007,2007.

5. M.Ehrig,S.Staab,andY.Sure.Bootstrappingontologyalignmentmethodswith APFEL. InPro eedingsofISWC,2005.

6. J.EuzenatandP.Shvaiko.Ontologymat hing. Springer,2007.

7. J.EuzenatandP.Valt hev. Similarity-basedontologyalignmentinOWL-lite. In Pro eedingsofECAI,2004.

8. C.Fellbaum. WordNet: anele troni lexi aldatabase. MITPress, 1998.

9. F. Giun higlia, P. Shvaiko, and M. Yatskevi h. Semanti s hema mat hing. In Meersman R. and Tari Z., editors, On the move to meaningful internet systems 2005: oopIS,DOA,andODBASE:OTMConfederatedInternationalConferen es, volume3760/2005ofLNCS,AgiaNapa,Cyprus,2005.

10. F.Giun higlia,C.Sierra, F.M Neill,N. Osman,and R.Siebes. Deliverable4.5: Goodenoughansweralgorithms.Te hni alreport,UniversityofEdinburgh,2008. 11. F. Giun higlia andT. Walsh. Abstra ttheoremproving. InBassi S., Sridharan N., Berta oS., and Boni elli R.,editors, 11th internationaljoint onferen e on arti ial intelligen e (IJCAI'89), volume 1, Detroit, Mi h., 20-25 August 1989 1989.

12. F. Giun higlia and T. Walsh. A theory of abstra tion. Arti ial Intelligen e, 57(2-3),1992.

13. F.Giun higliaandM.Yatskevi h.Elementlevelsemanti mat hing.InM ilraithS. A.,PlexousakisD.,andVanHarmelenF.,editors,TheSemanti Web:ISWC2004: ThirdInternational Semanti WebConferen e:Pro eedings,Hiroshima, Japan,6 November20042004.Berlin:Springer.

14. F.Giun higlia,M.Yatskevi h,andE.Giun higlia.E ientsemanti mat hing.In GomezperezA.andEuzenatJ.,editors,Pro eedings ofthe2ndEuropean seman-ti web onferen e (ESWC'05),volume3532/2005 ofLe ture Notes in Computer S ien e,Heraklion,Crete,Gree e, 29May-1June20052005.

mat hing. In Pro eedings of the ISWCworkshop on Ontology Mat hing, Busan, Korea,November,20072007.

17. F. Giun higlia, M. Yatskevi h,and P.Shvaiko. Semanti mat hing: Algorithms andimplementation. JournalonDataSemanti s,IX,2007.

18. R. Gligorov, Z. Aleksovski, W. ten Kate, and F. van Harmelen. Using google distan etoweightapproximateontologymat hes. InPro eedingsofWWW,2007. 19. W.HuandY.Qu. Blo kmat hingfor ontologies. InPro eedingsofISWC,2006. 20. Y. KalfoglouandM. S horlemmer. IF-Map:anontologymappingmethodbased

oninformationowtheory. JournalonDataSemanti s,I,2003.

21. M. Klus h,B.Fries, and K.Sy ara. Automatedsemanti web servi edis overy withOWLS-MX. InPro eedingsofAAMAS,2006.

22. S.KotoulasandRSiebes. Deliverable2.2:Adaptiveroutinginstru tured peer-to-peeroverlays. Te hni alreport,OpenKnowledge.

23. L.Li andI.Horro ks. Asoftwareframeworkfor mat hmakingbasedonsemanti webte hnology. InPro eedings ofWWW,2003.

24. N.NoyandM.Musen.ThePROMPTsuite:intera tivetoolsforontologymerging andmapping. InternationalJournalofHuman-ComputerStudies,59(6),2003. 25. S.Oundhakar,K.Verma,K.Sivashanugam,A.Sheth,andJ.Miller. Dis overyof

webservi es inamulti-ontologyand federatedregistry environment. Journal of WebServi esResear h,2(3),2005.

26. M. Paolu i,T.Kawamura,T.Payne,andK.Sy ara. Semanti mat hingofweb servi es apabilities. InPro eedingsof ISWC,2002.

27. DRobertson.Alightweight oordination al ulusforagentsystems.InDe larative AgentLanguagesandTe hnologies,pages183197,2004.

28. DRobertson.Alightweightmethodfor oordinationofagentorientedwebservi es. InAmeri anAsso iationforArti ialIntelligen e,editor,Te hni alReport SS-04-06,2004.

29. D.Robertson,F.Giun higlia,F.vanHarmelen,M.Mar hese,M.Sabou,M. S hor-lemmer,N.Shadbolt,R.Siebes,C.Sierra,C.Walton,S.Dasmahapatra,D. Dup-plaw, P. Lewis, M. Yatskevi h,S. Kotoulas, A. P. de Pinnin k, and A. Loizou. Open knowledge semanti webs throughpeer-to-peerintera tion. Te hni al Re-portDIT-06-034,UniversityofTrento,2006.

30. P.ShvaikoandJ.Euzenat. Asurveyofs hema-basedmat hingapproa hes. Jour-nal onDataSemanti s,IV,2005.

31. U.Stra iaandR.Tron y.oMAP:Combining lassiersforaligningautomati ally OWLontologies. InPro eedings ofWISE,2005.

32. J.Tang,J.Li,B.Liang,X.Huang,Y.Li,andK.Wang. UsingBayesiande ision forontologymapping. Journalof WebSemanti s,4(1),2006.