2011IEEEInternationalConferenceonWebServicesRetrievingCompatibleWebServicesVasiliosAndrikopoulosPierluigiPlebaniEuropeanResearchInstituteinServiceScience(ERISS)DipartimentodiElettronicaedInformazioneTilburgUniversityPolitecnicodiMilanoWarandelaan2,5000LETilburg,theNetherlandsPiazzaL.daVinci32,20133Milan,ItalyV.Andrikopoulos@uvt.nlplebani@elet.polimi.itAbstract—ServiceretrievalholdsacentralroleduringtheretrievalbasedontheevaluationofsimilaritybetweenWebdevelopmentofWebservicesandService-BasedApplicationsserviceinterfaces.InURBE,eachWebserviceinterfaceis(SBAs).Thehigherthenumberofavailableservices,themoredefinedinWebServicesDescriptionLanguage(WSDL);acomplexitbecomestolocatetheserviceclosertothedeveloperneeds.Thecomplexityincreasesfurtherwiththenumberofmatchmakingalgorithmcombinestheanalysisoftheirstruc-availableserviceversionsthatcouldalsobesuitableforthistureswiththesimilarityoftheusedtermsinordertoretrievepurpose.Existingapproachesonserviceretrievaluseasimilarityrelevantservicesforpurposesofreplacingaservice.Asmeasurebetweenserviceinterfacestoidentifypotentiallyrelevantdiscussedin[1],URBEperformsonaveragebetterwhenservices.Inthisworkwefocusonintroducinginformationaboutcomparedtoapproacheslike[3]andforthisreasonitwasthecompatibilityofserviceswhilecalculatingtheirsimilarityasthemeansforprovidingmoresuitableresults.Forthispurposeselectedasthebaselineforourwork.weupdateandextendanexistingWebservicesmatchmakerBothURBEandsimilarsolutionsconsidernotonlythecalledUDDIRegistryByExample(URBE).structurebutalsothesemanticsofcandidateservices.TheyIndexTerms—Serviceretrieval,servicecompatibility,similar-donothowevertakeintoaccountthepurposeofeachelementity.intheservicedescriptionwithrespecttoservicecompatibility.ServicecompatibilityreferstothepropertyofpreservationofI.INTRODUCTIONinteroperabilityforinternalizedchangestooneorbothinter-Duringtherecentyears,thenumberofpubliclyavailableactingparties(serviceproviderorconsumer),orequivalently,Webserviceshasbeenincreasingsteadily.Seekda1,oneoftheofthecapacityforreplacingoneservicewithanother(alsolargestWebservicessearchengine,hasindexedalmost30,000referredtoassubstitutabilityandreplaceability)[5].DifferentWebservices.AnimportantstepinenablingtheService-elementsintheservicedescriptionhavedifferenteffectsonOrientedArchitecture(SOA)paradigmistheabilityofserviceinteroperability:addingforexampleanoperationtoaWSDLandSBAdevelopers(simplyreferredtoasdevelopersfromdocumentdoesnothaveanyeffectonexistingclientsofnowon)tobeabletoretrievepotentiallyrelevantservices.theservice;removinganoperationhowevermayaffectthemInparticular,inthisworkwefocusonthetaskassignedtodramatically.developerstoidentifyatdesign-timewhichactivityistobeForthispurpose,theworkin[5]usesasubtypingrelationperformedandtodiscoverandselecttheWebservicesclosestbetweentheelementsofservicedescriptiondocumentsintotheirrequirements[1].Furthermore,itisalsonecessaryordertoformallydefineservicecompatibility.Followingthistobeabletoidentifyandreplaceservicesparticipatinginaapproach,compatibilityispreservedaslongasthepropertiesservicecompositionatrun-time[2].ofcovarianceofoutputandcontra-varianceofinputareInthissense,serviceretrieval,frequentlyreferredtoalsoaspreserved[6].Thisisapropertythatisnotconsideredinservicediscovery,isacriticalstepforreusingexistingservicesthematchmakingalgorithmsdiscussedinURBEandsimilarwhiledevelopingotherservicesandSBAs[3].Severalap-approaches.proacheshavebeenproposedintheliteratureforWebservicesTothiseffect,inthisworkweaimtocombineserviceretrieval,seeforexample[4].Wecandistinguishbetweenretrievalwithservicecompatibilitywiththegoalofimprovingtwocategoriesofsolutions:registry-basedandontology-basedthematchmakingofURBE.Thenewmatchmakingalgorithmones.Ontology-basedapproachesdonotusuallyconsidertakesintoaccountnotonlytheinterfacestructureandtermthestructureoftheWebserviceinterfacesandtheyrequiresimilarity,butalsotheimportanceofeachelementforserviceadditionaleffortintheformofannotationstoproduceaservicecompatibility.Asaresultofthissynergy,retrievedservicesdescription.Forthesereasons,anddespitetheeffectivenessarenotonlysimilartotherequiredservice,butadditionally,ofontology-basedapproaches,wefocusonaregistry-basedaminimumeffortisdemandedfromthedevelopersinordersolution.tobeabletousethisserviceonthecompositeserviceorInparticular,weuseasthestartingpointforourapproachSBAside.Furthermore,theupdatedURBEimplementationistheURBEmatchmaker[1].URBEisanapproachforserviceshowntoperformbetterbothintermsofprecisionandaverageresponsetimewithrespecttotheolderversion.1http://webservices.seekda.com/Therestofthepaperisstructuredasfollows.SectionII978-0-7695-4463-2/11$26.00©2011IEEE179DOI10.1109/ICWS.2011.24providesabetterbackgroundfortherestoftheworkbydiscussingcompatibilitybetweenserviceinterfaces.SectionIIIentersintothedetailontheevaluationofthematchmakingtheapproach.Finally,SectionVdiscussesrelatedworkandSectionVIfocusesonconcludingremarksandpossiblefuturework.II.SERVICECOMPATIBILITYServicecompatibilitycanbedistinguishedintwodimen-sions:horizontalcompatibility(orserviceinteroperability)andverticalcompatibility(alsoknownassubstitutabilityorreplaceability)[5].HorizontalcompatibilityorinteroperabilityFig.1.Exampleofrecordsubtyping.oftwoservicesexpressesthefactthattheservicescanpar-ticipatesuccessfullyinaninteractionasserviceproviderandserviceconsumer.Theunderlyingassumptionisthatthereisattheywillalwaysbelimitedbytwofactors:theirdependencyleastonecontext(configurationoftheenvironment,resourceontheparticulartechnologyused(WSDLinthiscase)andstatusandmessageexchangehistory)underwhichthetwotheirlackofarobusttheoreticalfoundation.Forthesereasonsservicescanfulfilltheirroles.Ontheotherhand,verticalcom-[5]introducesthenotionofT-shapedchangesbasedonthepatibilityorsubstitutability(fromtheprovider’sperspective)formalfoundationoftypetheoryfordefiningwhatconstitutesorreplaceability(fromtheconsumer’sperspective)ofservicecompatibleservicedescriptions.versionsexpressestherequirementsthatallowthereplacementInordertoapplytypetheoryconstructstoserviceinterfaces,ofoneversionbyanotherinagivencontext.[5]assumesthateachservicedescriptionSiscomprisedofCompatibilityistraditionallyfurtherdecomposedintoback-recordssthatrepresenttheconceptualdependenciesinsidethewardandforward.Adefinitionofforwardandbackwardcom-serviceinterfacedescription.Aservicerecordsisasubtype0patibilitywithrespecttolanguagesingeneral,andmessageofanotherrecordsifandonlyifithasatleastallthe0exchangesbetweenproducersandconsumersinparticular,istypedpropertiesofs(andpossiblymore)andallthecommongivenin[7].Forwardcompatibilitymeansthatanewversionpropertiesarealsoinasubtypingrelation.Inthiscasewewrite0ofamessageproducercanbedeployedwithouttheneedfors≤s.updatingthemessageconsumer(s).BackwardcompatibilityFig.1showsanexampleoftwoservicerecordsthataremeansthatanewversionofamessageconsumercanbeconnectedbysubtypingusingtwoversionsofpurchaseorderdeployedwithouttheneedforupdatingthemessageproducer.PODocumentdatatype:sPODocument2≤sPODocument1,Fullcompatibilityisthecombinationofbothforwardandthatis,PODocument2isasubtype(aspecialization)ofbackwardcompatibility.PODocument1sinceitcontainsmorexsd:elementtypesTheusualapproachfordefiningwhatconstitutesacom-–andtheonesitcontainsarelessgeneralthattherespec-patiblechangetoaserviceistoenumerateallpossiblecom-tiveonesofPODocument1.Theoptionalcardinalityofthepatibilitypreservingchangestoaservicedescription,usuallyDeliveryInfoelementinPODocument1ismoregeneralaWSDLdocument.TheallowedchangesessentiallydefinethantheobligatoryparticipationinPODocument2,sinceathetypeofdeltabetweentwoserviceversionsforwhichthemessageconsumerthatunderstandsitasanoptionalelementversionsarecompatibleandtheyareusuallyexpressedinacanalsounderstandthemessagealwayscontainingit.guidelinestyle.Theseguidelines(seeforexample[8])canbeTherecordssinserviceSaredistributedintotwopropersummarizedby:subsetsSproandSreq,representingthesetofrecordsfor1)Add(optional)messagedatatypes.whichtheserviceactsasaproducerandaconsumerofmes-2)Add(new)operation.sagesrespectively.Output-typerecordslike(WSDL)operation3)Add(new)porttype.outputorfaultmessagesandalltheiraffiliateddatatypesbelongtotheSset.Input-typerecordslikeoperationinputAnyothermodificationliketheremoval,oranykindofpromessagesandtheiraffiliateddatatypesareintheSset.modificationtoanoperationelementisstrictlyprohibited,reqCompatibilitybetweenservicedescriptionsSandS0isdefinedasisthemodificationofthemessagedatatypes(withthebasedonthisdistributionas:exceptionofadditionofoptionaldatatypes).Thisguideline-basedapproachiseasilyapplicableandrequiresminimumDefinition1(TypesofServiceCompatibility).Wedefinethreesupportinfrastructureandforthisreasoniswidelyaccepted.casesofcompatibility:0000Ontheotherhand,itisalsoveryrestrictiveand,evenmore•Forward:Sapplyacastingfromdttodt0.TableI,empiricallyobtained,th,wherethisathreshold.Incasealltheelementsindt0arequantifiesthisinformationloss.Forinstance,ifdtbelongstocovered,thenparSimreturnsthemaximumcompatibility,i.e.,theintegergroupanddt0totherealgroupthenthesimilarityis1.0.Ifanelementindtdoesnotappearindt0thenanew1.0sincewehavenoinformationloss.Intheoppositesituationelementshouldbeintroducedand,accordingtotheT-shapedinstead,thesimilarityis0.5sincewecanconvertarealintochangesdefinition,thedatatypesremaincompatibleandtheanintegerbutwelosethedecimals.Finally,ifdtordt0isparSimisnotaffectedifandonlyifdtanddt0areinput-complex,thestructureofthedatatypeisnotconsideredandtypeelements(Definition1).Ontheotherhand,ifnotallthethesimilarityonlydependsonthenameofthedatatype.elementsindt0arecoveredbydtthensomeelementsmustStartingfromthisversionofthealgorithm,inthisworkberemovedandthecompatibilityisnotensured.Inthatcase,weintegratethesubtypingtheory,discussedinthepreviousparSimwilldecreaseproportionallytothenumberofthesesection,insidetheparSimtoimprovetheeffectivenessofremovals.Thisanalysisisinversedifdtanddt0areoutput-typethediscoveryalgorithmproposedinURBE.Inparticular,ourelements.workfocusesontheanalysisofcomplexdatatypessincetheFig.3showsanabstractexampleofapossiblematching,simpledatatypecompatibility,asitisdrivenbythecastingwheretheweightslabellingtheedgesarecomputedbytheofdatatypes,alreadyincorporatesthenotionofcompatibility.dtSimfunctionwhichcalculatesthesimilarityofsimpleMoreindetail,considertwocomplexdatatypesdtanddt0datatypes.Inthiscase,assumingth=0.8thesolution4AssumingthatalltheservicescanbedescribedusingWSDL,thedataoftheassignmentinbipartitegraphsproblemrecognizesa000typeswillbeexpressedusingXSDschemassimilaritybetweenelements{hdt1,dt1i,hdt2,dt3i,hdt4,dt2i}.182Asaconsequence|matching({dt}{dt0})|=3,|dt0|=4and|{ws∈Retn(ws)|ws∈Rel(ws)}|ijjPn(ws)=iqiqthereforeparSim(dt,dt0)=0.75.qnAccordingtothisscenario,thevalueofthethresholdthAPistheaverageofprecisionscomputedaftertruncatingthebecomescrucialfortheapproach.Ifthwassettoatoohighlistaftereachoftherelevantdocuments,aslongasallthevalue,twodatatypescanbeconsideredasmatchingonlyifrelevantdocumentsareretrieved:theyarethesame;otherwise,ifthwassettoatoolowvalue,itmighthappenthattwodatatypesareconsideredrelevantevenrΣr=1..NP(wsq)iftheyarenot.ByusingthetuningperformedforURBEthisAP(wsq)=N|{wsi∈Ret|wsi∈Rel(wsq)}|thresholdiscurrentlysettoth=0.3.wsq0Furthermore,incasedtisasimpledatatypeanddtiswhereN=|{wsi∈Ret(wsq)|wsi∈Rel(wsq)}|istheacomplexdatatype(orviceversa),theapproachissimilar:numberofrelevantdocuments.5thealgorithmlooksforoneoftheelementscomposingtheFinally,theTop-5(obtainedasP(wsq))andTop-1010complexdatatypethatiscompatibletothesimpledatatype(P(wsq))precisionmetricsarealsoconsidered.Thesepa-andthesimilarityiscalculatedasdiscussedabove.rametersgivetheprecisionconsideringonlythefirst5or10entries,respectively.Thehigherthevalue,thehighertheIV.VALIDATIONprobabilitytohavearelevantserviceinthefirstpositions.A.ExperimentalSettingAlltheseparameterswerecalculatedforeachofthe42testqueriesincludedinthebenchmark.TheaveragesofAswithsimilarworks,theeffectivenessoftheproposedtheseparametersacrossalltestqueriesareusedinthenextapproachisvalidatedbymeasuringtheprecisionandre-paragraphasthebasisfortheevaluationofthealgorithm.callwithrespecttoapublicbenchmarkobtainedfromtheAlltheexperimentsdiscussedinthispaperhavebeendoneSAWSDL[12]serviceretrievaltestcollection(morespecif-onanMacOSX10.6installedonandIntelCore2Due2.33ically,SAWSDL-TC3)5.SAWSDLsemanticallyenrichestheGHzwith8GBytesofRAM.ThepartofthealgorithmableWSDL-basedservicedefinitionbyannotations:elementsoftosolvethelinearprogrammingproblemexploitstheopen-theWSDLareannotatedwithconceptsorganizedinaref-sourceapplicationLPSolve6andithasbeenformulatedtoerenceontology.Thebenchmarkconsistsof1080Webser-alwaysobtaintheglobaloptimumresult.vicescoveringdifferentapplicationdomains:communication,economy,education,food,medicalcare,travelandweaponry.B.ResultsThebenchmarkalsoincludes42testqueries,representedasTheeffectivenessofthepresentedapproachisillustratedSAWSDLdocuments,eachofwhichisassociatedwithasetinFig.4.Asabaselineforitsevaluationweconsidertheofservicesthattheproponentsofthebenchm