A Lightweight Prototype Implementation of SPARQL Filters for WSMO-based Discovery (Technical Report ISA-11-TR-01)

A Lightweight Prototype Implementation of SPARQL Filters for WSMO-based Discovery Jos´e Mar´ıa Garc´ıa, David Ruiz and Antonio Ruiz-Cort´es {josemgarcia,druiz,aruiz}@us.es Applied Software Engineering Research Group University of Seville, Spain May 2011 Technical Report ISA-11-TR-01 This report was prepared by the Applied Software Engineering Research Group (ISA) Department of computer languages and systems Av/ Reina Mercedes S/N, 41012 Seville, Spain http://www.isa.us.es/ Copyright c 2011 by ISA Research Group. Permission to reproduce this document and to prepare derivative works from this document for internal use is granted, provided the copyright and ’No Warranty’ statements are included with all reproductions and derivative works. NO WARRANTY THIS ISA RESEARCH GROUP MATERIAL IS FURNISHED ON AN ’AS-IS’ BASIS. ISA RESEARCH GROUP MAKES NO WARRANTIES OF ANY KIND, EITHER EXPRESSED OR IMPLIED, AS TO ANY MATTER INCLUDING, BUT NOT LIMITED TO, WARRANTY OF FITNESS FOR PURPOSE OR MERCHANTIBILITY, EXCLUSIVITY, OR RESULTS OBTAINED FROM USE OF THE MATERIAL. Use of any trademarks in this report is not intended in any way to infringe on the rights of the trademark holder. Support: This work has been partially supported by the European Commission (FEDER) and Spanish Government under CICYT project SETI (TIN2009-07366), by the Andalusian Government under projects ISABEL (TIC-2533) and THEOS (TIC-5906), by the EU FP7 IST project 27867 SOA4All, and by the EC FP7 Network of Excellence 215483 S-CUBE. 3 List of changes Version Date Description 1.0 May 2011 First release Abstract Semantic Web Services discovery is commonly a heavyweight task, which has scalability issues when the number of services or the ontology complexity increase, because most approaches are based on Description Logics reasoning. As more complex services become available, there is a need for solutions that improve discovery performance. Our proposal tackles this scalability problem by adding a preprocessing stage based on two SPARQL queries that filter service repositories, discarding service descriptions that do not refer to any property requested by the user before the actual discovery. By using this approach, the search space for discovery mechanisms is fairly reduced, consequently improving the overall performance of this task. Furthermore, this particular solution do not provide yet another discovery mechanism, but it is easily applicable to any of the existing ones. Moreover, proposed queries are automatically generated from service requests, transparently to the user. In order to validate our proposal, a concrete application to a wsmo discovery scenario is showcased in this paper. A comprehensive performance analysis is also presented in order to test and compare the results obtained from proposed queries and classical discovery approaches, discussing the benefits of our proposal. Contents 1 Introduction 1 2 Background 3 2.1 Querying the Semantic Web . . . . . . . . . . . . . . . . . . . 3 2.2 Semantic Web Services . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Discovering and Ranking . . . . . . . . . . . . . . . . . . . . . 6 3 Filtering Service Repositories using SPARQL 7 3.1 Querying a Service Repository . . . . . . . . . . . . . . . . . . 7 3.2 Automatic Generation of Queries . . . . . . . . . . . . . . . . 10 4 A WSMO Implementation 11 4.1 Ontology Mapping . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Query Rewriting . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.3 Query Execution . . . . . . . . . . . . . . . . . . . . . . . . . 15 5 Analysis and Evaluation 16 5.1 Defining the Experiments . . . . . . . . . . . . . . . . . . . . 16 5.2 Analyzing Tests Results . . . . . . . . . . . . . . . . . . . . . 19 5.2.1 Execution Time . . . . . . . . . . . . . . . . . . . . . . 19 5.2.2 Qsome Results....................... 21 5.2.3 Qall Results ........................ 22 5.2.4 Discovery Improvement . . . . . . . . . . . . . . . . . . 23 5.3 Statistical Analysis . . . . . . . . . . . . . . . . . . . . . . . . 24 5.4 Discussion............................. 25 6 Related Work 26 7 Conclusions 28 i List of Figures 1 Integrated ontology for querying a service repository. . . . . . 4 2 Semantic discovery and ranking processes. . . . . . . . . . . . 6 3 Service procurement architecture including a SPARQL filtering stage. 7 4 Parameters and output variables of experiments. . . . . . . . . 17 5 Execution time results. . . . . . . . . . . . . . . . . . . . . . . 20 6 Filtering results for Qsome..................... 21 7 Filtering results for Qall. ..................... 22 8 Performance evaluation of discovery mechanisms. . . . . . . . 23 ii List of Tables 1 Mappings between WSMO and our integrated model . . . . . 12 2 Mean and std. deviation, and IC of evaluated variables. . . . . 24 3 Pearson correlations between evaluated parameters. . . . . . . 25 iii 1 Introduction Current service discovery solutions that rely on Semantic Web technologies are not sufficiently scalable, so large and complex service repositories cannot be properly handled by them. Although there is a great research effort to improve discovery mechanisms, the underlying reasoning facilities do not scale well in general [14]. The approach taken in this paper does not consist on another discovery mechanism, but on the inclusion of a preprocessing stage where service repositories are filtered using two different queries, so that the search space for discovery processes is reduced in our experiments, on average, from 78.65% of the original repository size up to 5.83%, depending on the query used and the nature of the repository, consequently improving service discovery by reducing its execution time from a 63.93% to a 11.32% of the original time needed for each corresponding repository. Service repositories are increasing the number of registered services at a high pace, as more services can be found publicly1. Furthermore, semantic definitions of these services are richer and more complex than ever before, integrating many heterogeneous concepts. That leads to an scenario where discovery mechanisms based on different logic formalisms have scalability issues. Consequently, improvements and optimizations on those mechanisms are needed in order to enhance the usability of Semantic Web Services (SWS) [7, 9]. In order to alleviate the scalability problem on semantic discovery mechanisms, our proposal takes the novel approach of reducing the input for those mechanisms, so that the resulting process is more streamlined, only reasoning about services which actually matter with respect to the user request. Thus, services that can be discarded a priori, because they are not related at all with requirements and preferences stated by the user, are filtered so that the search space is considerably reduced prior to actual discovery mechanisms. For example, consider the following scenario: a semantic service repository contains thousands of services from several travel-related domains, such as hotel bookings, plane tickets, car rentals, and travel insurances. If a user looks for a service for renting a car, it is not necessary to process the whole repository to discover candidate services for the user request, but only consider the portion of services that are specifically related to the car rentals domain concepts, in this case. Thus, on an evenly distributed repository, where there were the same number of services related to each domain in the example (hotels, planes, car rentals, and insurances), only 25% of the services would be considered for the discovery process, considerably improving 1seekda.com service crawler has indexed at the moment of writing 28,529 services. 1 its performance. For the proposed preprocessing, the user request is analyzed in order to extract the concepts that are being used in its semantic definition (in the above example, some of them could be Car or DrivingLicence, for instance). Then, the repository is filtered so that only services that uses those same concepts are selected to become the input for the subsequent discovery process (e.g. services whose definitions refer to Car and/or DrivingLicence concepts, in the latter case). The filter is performed in our approach by two different SPARQL[27] queries, namely Qsome and Qall. The former selects service definitions that refers to some (at least one) of the concepts referred by a user request, assuming that those services may satisfy its requirements and/or preferences despite the missing information. In turn, the latter query returns only those services whose definitions contain all the concepts referred by a user request, assuming that services have to fulfill every term of the request in order to be useful for the user. Our solution does not pretend to provide yet another discovery mechanism, but to introduce a preprocessing stage, based on an accepted standard, that yields a notable improvement on heavyweight semantic processes, such as matchmaking of services. To the best of our knowledge, there is no proposals on filtering semantically-enhanced service repositories, but it is known that some sort of preprocessing can alleviate discovery and ranking tasks performed on those repositories [2]. To sum up, the main contributions of the proposal presented in this paper are the following: 1. A technique to improve semantic service discovery performance is proposed, based on a preprocessing stage where repositories are filtered in order to reduce the search space of subsequent discovery processes. 2. Our proposal is applicable to any discovery mechanism because it is performed before actual discovery occurs. In this work, a third-party lightweight Description Logics discovery mechanism is used to illustrate this point, namely wsmx DL discovery. 3. Preprocessing is performed automatically from user requests, analyzing them and obtaining standard SPARQL queries without user interaction. Two different queries are presented, enabling two filtering levels, depending on the user needs and the characteristics of service repositories. Each one is analyzed and thoroughly discussed throughout the article. 4. A comprehensive, experimental study is carried out in order to assess the actual impact of our proposal. Several theoretical scenarios were 2 user preference, another SPARQL query is proposed, which is more specific and precise. Qall query selects services from the repository that exactly have terms about all the properties which are referenced by the user request. In order to achieve this goal, the query must contain matching patterns for each property, specifying the property instances that the user is looking for. Listing 2 shows an example of such a query. Listing 2: The more specific query Qall.  PREFIX ao : <http ://www. i s a . us . es /2009/ IntegratedOntology . owl#> SELECT DISTINCT ? s e r v i c e WHERE {# ? s e r v i c e has at l e a s t t h r e e p r o p e r t i e s . . . ? s e r v i c e ao : hasFeatures ? featuredTerm1 . ? featuredTerm1 ao : r ef er sT o ? proper ty1 . ? s e r v i c e ao : hasFeatures ? featuredTerm2 . ? featuredTerm2 ao : r ef er sT o ? proper ty2 . ? s e r v i c e ao : hasFeatures ? featuredTerm3 . ? featuredTerm3 ao : r ef er sT o ? proper ty3 . FILTER (# . . . and t h e se p r o p e r t i e s are Car , Pri ce and A v a i l a b i l i t y ? property1 = <http ://www. example . org /2009/ DomainOntology . owl#Car>&& ? property2 = <http ://www. example . org /2009/ DomainOntology . owl#Price>&& ? property3 = <http ://www. example . org /2009/ DomainOntology . owl#A v a i l a b i l i t y > ) }  Concretely, this query looks for service descriptions in the repository that refer to at least three properties (i.e. that matches the six graph patterns of the WHERE clause), and afterwards it only returns instances whose matched properties are the specified in the FILTER clause (in the example, Car,Price and Availability. Note that each property may be defined in different ontologies, such as wsmo [28], or the proposed by Maximilien et al. [25], for instance. Nevertheless, this query can be derived from a user request automatically, so it can be adapted to match the specific properties referenced in each corresponding user request. This kind of specific query is more restrictive than the former query, shown in Listing 1, returning an even more reduced number of candidate services for the discovery stage, as it is discussed in Sec. 5. However, in certain scenarios, especially when the user request has several optional terms (as with preferences for the ranking process), Qsome query may be more appropriate, so there is a trade-off between precision or flexibility that has to be considered in each case. Thus, if user requests contain a high number of mandatory terms (requirements) that have to be fulfilled completely, Qall will return more accurate results than Qsome, though a hybrid approach may be also taken if both mandatory and optional terms are included in the user request. 9 3.2 Automatic Generation of Queries Queries need to be defined for each user request, because they depend on the structure of that request. On the one hand, query Qsome, as shown in Listing 1, only varies on the actual instance of UserRequest being used at that precise time. In this case the generation of Qsome is straightforward, because its main structure does not vary. On the other hand, in order to compose query Qall, some analysis have to be done, because concrete properties referred by the user request are used in the FILTER clause of the query. Thus, Qall generation depends not only on the structure of the ontology being used by our proposal, but on the concrete instance of UserRequest itself, especially on the properties referred by its terms. As a consequence, Qall has to be tailored depending on the corresponding instances managed by each discovery process. However, the generation of query Qall can be done automatically, maintaining the transparency for the user of our proposed SPARQL filtering stage within the discovery process. Algorithm 1 shows the procedure that compose Qall from a given user request. Algorithm 1: Generation of query Qall. Input: The user request instance u Output: A generated SPARQL query Qall 1Qall = “PREFIX ont: <http://www.isa.us.es/2009/AbstractOntology.owl#>” 2Qall += “SELECT DISTINCT ?service WHERE {” 3i= 0 4foreach Property pin u.hasRequirements.refersT o do 5i+ + 6Qall += “?service ont:hasFeatures ?featuredTerm” + i+ “.” 7Qall += “?featuredTerm” + i+ “ont:refersTo ?property” + i+ “.” 8end 9Qall += “FILTER (“ 10 foreach Property pin u.hasRequirements.refersT o do 11 Qall += “?property” + i+ “=” + p.IRI 12 i− − 13 if i > 0then Qall += “ && ” 14 end 15 Qall += “) }” The presented algorithm is fairly simple, and presents a linear complexity on the number of properties referred by the user request. It iterates over 10 properties adding the corresponding matching patterns and filter statements to the query. Thus, it does not depend on the number of services registered in the repository, or the complexity of the domain ontologies used, so the overhead of the composition of queries is practically negligible. 4 A WSMO Implementation Our proposed preprocessing stage can be easily adapted to any SWS framework, so that it can be virtually included within any discovery process. In order to do so, service descriptions and user requests, expressed using a specific SWS framework, need to be mapped to our integrated ontology, or the other way around, so that queries can be used directly as defined in Sec. 3.1, or mapped to the corresponding SWS framework concepts. This mapping can be defined using ontology mediators [5] or ontology mappings [26], for instance. Thus, the concrete work that has to be done for each mapping is summarized in the following steps: 1. Define mappings between concepts of the integrated ontology shown in Fig. 1 and equivalent concepts of the target framework. 2. Rewrite queries discussed in Sec. 3.1 using previously defined mappings. 3. Adapt query generation algorithms from Sec. 3.2 to iterate over the concepts of the target framework. Our solution can be easily applied to any SWS frameworks, such as wsmo, owl-s,sawsdl or wsmo-Lite. In the following, the mappings and queries rewriting to a concrete wsmo implementation are presented. 4.1 Ontology Mapping In order to to adapt our proposal to the wsmo ontological model, several mappings have to be defined. In Table 1, the correspondences between wsmo entities, and concepts from the integrated ontology used in our proposal (cf. Sec. 3) are summarized. Thus, the UserRequest concept from our ontology could be interpreted as a wsmo Goal, which describes its requirements (Terms in our ontology) as a requested Capability and some nonFunctionalProperties values. Additionally, a ServiceDescription are modeled in wsmo as a webService, which also features or provides some Capability, as well as nonFunctional- Properties. Both capabilities and non functional properties instances refer 11 Table 1: Mappings between WSMO and our integrated model wsmo ontology Integrated ontology Goal UserRequest webService ServiceDescription Capability axioms Terms nonFunctionalProperties Terms Concept Property to several concepts that are interpreted as instances of the Property concept of our ontology [13]. Using these mappings, our proposed queries can be expressed or rewrote using wsmo elements, so our preprocessing stage can be executed before any wsmo discovery implementation, provided that the wsml [32] repository to be used allows to access its semantic definitions in RDF. In the following, we discuss how to express and generate both queries so that they can be applied to wsmo services and goals. In order to implement an application of our proposed filtering stage that relies on wsmo descriptions, queries should be defined in terms of wsmo constructs. Basically, Terms in our integrated ontology corresponds to Capabilities in wsmo, and user requests are modeled as Goals, as described before. However, there is no direct equivalent to the refersTo relation in wsmo. Therefore, this relation must be inferred or extracted from descriptions transparently. Our approach consists on iterating capability descriptions in order to obtain concepts referred by them, and adding these concepts to service descriptions and goals using non-functional properties in wsml. Additionally, other properties, such as quality-of-service properties, that may be already present in the non-functional section of the wsml description, are also included in the values of the newly added refersTo property, which should contain all the concepts referred by service descriptions and goals. Algorithm 2 sums up the procedure to add the refersTo property to services and goals descriptions. Esentially, Alg. 2 iterate over the wsml axioms that describe service capabilities for webServices and goals, and look for instantiations of shared variables that are linked with their concept classes by the memberOf construct, which are interpreted as referred properties that have to be added to the refersTo set. In addition, it also looks at the non-functional properties and consider their classes as properties referred, consequently including them in the refersTo set, too. Although this process could be costly in terms of execution time if there 12 Algorithm 2: Obtain concepts referred by wsml descriptions. Input: A wsml webService description or goal desc Output: The webService or goal desc with a refersT o nonFunctionalProperty 1if desc.nonF unctionalP roperties.refersT o =∅then 2refersT oSet =∅ 3foreach Axiom ain desc.capability do 4foreach Variable var in ado 5if var is memberOf concept pthen 6refersT oSet =refersT oSet ∪p 7end 8end 9end 10 foreach nonFunctionalProperty nfp in desc do 11 refersT oSet =refersT oSet ∪nfp 12 end 13 desc.nonF unctionalP roperties.refersT o =refersT oSet 14 end were a high number of services, it can be done off-line before actual discovery and ranking are performed, at least for service descriptions. Thus, the refersTo non-functional property is only obtained and stored in the repository each time a new service description is added or modified, considerably reducing the overhead when discovering and ranking these descriptions, because the algorithm only has to be executed for the user goal at execution time. 4.2 Query Rewriting Elements based on the wsmo model are described using some variant of wsml language and are commonly serialized in plain text files. Although this serialization is performed using the standard wsml syntax, it is possible to represent wsml constructs using an RDF syntax, so that they can be queried using SPARQL. In order to translate original wsml files to wsml/rdf [6] representation WSMO4RDF library can be used, which is a part of the Ontology Representation and Data Integration Framework (ORDI SG)4. 4http://www.ontotext.com/ordi/ORDI_SG/Wsmo4rdf.html 13 Listing 3: Qsome query applied to wsmo.  PREFIX wsml : <http : //www. wsmo . org /wsml/wsml−syntax#> PREFIX ont : <http ://www. i s a . us . es /2009/ AbstractOntology . owl#> PREFIX part : <http ://www.w3 . org / . . . / SimplePartWhole/ part . owl#> PREFIX r d f : <http : //www. w3 . org /1999/02/22 −rdf−syntax−ns#> SELECT DISTINCT ? s e r v i c e WHERE { ? s e r v i c e r d f : type wsml : webService . ? s e r v i c e par t : ha s P a r t d i r e c tl y ?wsCap . ?wsCap ont : re fe rs To ? p r o p e r t i e s . : Goal r d f : type wsml : goal . ? g oal par t : ha s P a r t d i r e c tl y ? cap . ? cap ont : re fe rs To ? p r o p e r t i e s . }  Thus, the generic query Qsome is applied to wsml/rdf representation as shown in Listing 3. In this case, service descriptions and goals have to be differentiated by type checking, because both are related to capabilities using the same hasPart directly relation. Nevertheless, both services and goals are matched as in Listing 1 by properties referred by corresponding capabilities using the refersTo relation previously obtained. Similarly, Listing 4 presents the wsmo equivalent query for the case of a more specific query (cf. Listing 2 for the version defined after the integrated ontology presented before). Listing 4: Qall query applied to wsmo.  PREFIX wsml : <http : //www. wsmo . org /wsml/wsml−syntax#> PREFIX ao : <http : //www. i s a . us . es /2009/ AbstractOntology . owl#> PREFIX part : <http ://www.w3 . org / . . . / SimplePartWhole/ part . owl#> PREFIX r d f : <http : //www. w3 . org /1999/02/22 −rdf−syntax−ns#> SELECT DISTINCT ? s e r v i c e WHERE { ? s e r v i c e r d f : type wsml : webService . ? s e r v i c e par t : ha s P a r t d i r e c tl y ?wsCap . ?wsCap ont : refersTo ? property1 . ?wsCap ont : refersTo ? property2 . ?wsCap ont : refersTo ? property3 . FILTER ( ? property1 = <http ://www. example . org /2009/ DomainOntology . owl#Car>&& ? property2 = <http ://www. example . org /2009/ DomainOntology . owl#Price>&& ? property3 = <http ://www. example . org /2009/ DomainOntology . owl#A v a i l a b i l i t y > ) }  14 4.3 Query Execution In our experimental tool, query execution was implemented in Java using the Jena Semantic Web Framework. First of all, relevant wsml files are parsed and translated to wsml/rdf representation using WSMO4RDF, so that Jena is able to process them and execute our proposed SPARQL queries, conveniently adapted to the wsml/rdf representation. Then, the results from the query execution are used to filter the list of services that take part in the discovery process. The discovery implementation used for the experiments is the lightweight-DL discovery provided by wsmo reference implementation wsmx, which uses Pellet [31] as the DL reasoner. Algorithm 3: Generation of query Qall for wsmo. Input: The goal instance g Output: A generated SPARQL query Qall 1Qall = “PREFIX wsml: <http://www.wsmo.org/wsml/wsml-syntax#>” 2Qall += “PREFIX ont: <http://www.isa.us.es/2009/AbstractOntology.owl#>” 3Qall += “PREFIX part: <http://www.w3.org/.../SimplePartWhole/part.owl#>” 4Qall += “PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>” 5Qall += “SELECT DISTINCT ?service WHERE {” 6Qall += “?service rdf:type wsml:webService.” 7Qall += “?service part:hasPart directly ?wsCap.” 8i= 0 9foreach Property pin g.nonF unctionalP roperties.refersT o do 10 i+ + 11 Qall += “?wsCap ont:refersTo ?property” + i+ “.” 12 end 13 Qall += “FILTER (“ 14 foreach Property pin g.nonF unctionalP roperties.refersT o do 15 Qall += “?property” + i+ “=” + p.IRI 16 i− − 17 if i > 0then Qall += “ && ” 18 end 19 Qall += “) }” Finally, the automatic generation of queries, specifically Qall, has to be slightly modified to iterate over the values of the refersTo non-functional 15 property of the corresponding goal, which contains the classes of the properties referred by that goal. Algorithm 3 shows how this generation is performed. Note that, as a previous step, refersTo property of the goal has to be inferred, as discussed in Alg. 2. 5 Analysis and Evaluation Our proposed queries have to be thoroughly analyzed, using experimental results, in order to obtain conclusions about their soundness and benefits. Each query have been tested in different situations, measuring both time and size of the resulting repository. In this section, the performed experiments are described, along with an interpretation and discussion of the results for that experimental study, which validates our proposal. 5.1 Defining the Experiments In order to test the suitability and performance of our proposal, there is a need for a test collection that can be used with the developed tools. Experiments were conducted within a wsmo discovery scenario, as discussed in Sec. 4, so services and user requests have to be described using wsml. However, a suitable, complex enough test collection of wsml descriptions is not available, so we developed a method to generate parametrized test collections, which could be used for performance tests. Thus, several service repositories and related ontologies were created for the experiments. In order to populate these repositories, each service description is generated using concepts from a DL ontology which contains a simple hierarchy of disjoint properties. Then, a goal is similarly generated. Figure 4 presents the already discussed discovery scenario that our experiments are contextualized in. The identified parameters, shown using boxes, allow to test different situations varying their values. Each parameter have an influence in one of the input artifacts for the studied scenario, namely the service repository, the domain ontology and the user request, represented in Fig. 4 by the dashed arrows. Brief definitions and parameter ranges are enumerated in the following: •Repository size (R). The number of services stored in the repository is a parameter that ranged from 100 to 1,000, with a step of 100, for a total of 10 different values in the conducted experiments. •Domain ontology concepts (O). The number of the domain ontology concepts, which double as instances of Property class from Fig. 16 SPARQL Filtering Filtered Repository Discovery User Request Service Repository Domain Ontologies R O U S T some T all R’ some R’ all T DL ... parameters output variables Figure 4: Parameters and output variables of experiments. 1, can be also parametrized. In our experiments, this number ranged from 20 to 100 concepts, incrementing by 20 for each step. •User request properties (U). Another parameter that varies in our tests is the proportion of properties referred by the user request (i.e. goals), with respect to the previous parameter, i.e. the number of available properties defined in the domain ontology. Five different values were selected for this parameter, ranging from 5 percent to 25 percent. Higher values were not tested because it is unlikely that users define their requests using a high number of concepts, especially as the domain ontology size increases. •Service properties (S). Similarly, the proportion of properties referred by service descriptions is also parametrized, ranging as user request properties from 5% to 25%. As in the previous case, it is unlikely that services manage a lot of concepts, so it is not necessary to test higher values for this parameter. The ontology representing the domain managed by services is populated with a concrete number of simple concepts (O), depending on each generated repository (R). These concepts are mutually disjoint, with the exception of a simple hierarchy that is randomly created within the ontology: a superconcept is chosen among all the concepts, and then a random number of 17 concepts are declared as sub-concepts of the former. A scenario with a larger ontology represents a repository which could contain more heterogeneous services, i.e. described services offer many different functionalities. Moreover, a larger ontology also means a lower discovery performance, because its complexity increases. Goals and services are created after the ontology, by selecting one concept that is going to be part of a simple postcondition of the corresponding capability, and, with some additional concepts (up to Uand S, respectively), they are directly included in a refersTo non-functional property of the element described. Note that concepts from the domain ontology are treated as functional or non-functional property depending on the case, because our proposal does not make any distinction between the nature of referred properties. Additionally, properties referred by each service and the goal are selected using two different distributions, each one representing a different scenario. On the one hand, in the case of an uniform distribution of service properties, each property defined within the domain ontology has the same probability to appear in service descriptions. Thus, this kind of repository reflects a situation where services may offer many different functionalities. Potentially, each concept from the domain ontology will be referred by the same number of services, i.e. the number of different functionalities among services in the repository will be approximately the number of concepts of the ontology. On the other hand, a power-law distribution is also used to select which properties are referred by service definitions, so most of these definitions refers to a few common properties. Concretely, a Zipf distribution is used because it can be applied to our tested scenarios[1]. This distribution is based on the Zipf’s law [36], which interprets that the frequency of any concept is inversely proportional to its rank in the frequency table, i.e. the most referred concept will occur twice as often as the second most referred one, which occurs twice as often as the following most frequent concept, and so on. In this case, repositories are fairly homogeneous, i.e. they contain many services with the same functionality, and there are few different functionalities. This scenario may be closer to real-world repositories than uniformlydistributed repositories, because in general service repositories are focused on a particular domain. However, larger and more general repositories may fall in between a uniform and a Zipf distribution of properties referred by their service descriptions, so it is worth to test both extremes. For each experiment, several output variables have been measured. In Fig. 4, the following variables are showcased using dashed boxes, which are connected with dashed arrows to the measured artifacts and processes: 18 Table 3: Pearson correlations between evaluated parameters. Uniform Zipf R O U S R O U S R′ some 0.000 0.524 0.560 0.561 0.000 0.511 0.241 0.415 R′ all -0.003 -0.313 -0.321 0.141 0.000 -0.202 -0.618 0.345 Tsome 0.661 0.620 0.019 0.295 0.670 0.616 0.019 0.291 Tall 0.692 0.642 0.002 0.229 0.700 0.630 0.006 0.231 execution has a penalty time of at most 2.04 seconds (µ+σ). However, note that this time includes the RDF serialization needed to use SPARQL with our test repository, so if the repository used allowed to be directly accessed in RDF, that penalty time could be significantly shorter. Very narrow confidence intervals (CI), computed using a 99% confidence level, shows that, for every variable, mean values can be considered to be robust enough, so they can be used to summarize our experimental results. Thus, if our proposed filters were applied to real scenarios modeled like our test collections, the performance could be predicted by our presented results. Table 3 shows the two-tailed Pearson-coefficient values calculated between the evaluated variables and the parameters of each test scenario, as described in Sec. 5.1. Values written in bold face mark those p-values that give a correlation with a 99% significance. Thus, in the first two rows, R′ some and R′ all are correlated with O,Uand S. However, Uis more important (i.e. has a higher correlation) for Qsome performance in a uniformly-distributed repository than for Qall, though it is the other way around in a Zipf-distributed repository. Execution times for both queries (Tsome and Tall) depends on R, Oand S, according to the p-values shown in Table 3. 5.4 Discussion As a general conclusion from the performed tests, the more specific query (Qall) is better suited to filter and reduce the size of the service repository, so it clearly improve the subsequent discovery stage by reducing the search space for matchmaking algorithms. Furthermore, it scales well in every situation, providing even better precision in proportion when the service repository contains a higher number of services. However, in certain scenarios, where flexibility and soft matching are a concern, the more generic query (Qsome) may be more suitable. The higher time penalty must be taken into consideration, both in the filtering and 25 the discovery stage, because of the less reduced search space, though it still improves the performance of discovery and ranking processes. Thus, there is a trade-off between precision or recall that should be evaluated depending on the concrete scenario. Actually, the current trend in the literature and real-world applications is to achieve better performance and usability, by sacrificing precision, recall, or both[9], so our proposal provides a feasible and efficient solution in this direction. The main feature of using our proposed queries is that the time penalty is very low, so a hybrid approach may be taken, where both queries are used successively before discovery and ranking processes take part. Firstly, Qall may be executed, and if some results are returned, they are directly injected into the discovery and ranking process. However, if no results are returned by Qall, the more generic Qsome query is executed and its results are used in the subsequent discovery and ranking process. This approach is similar to the Best-Matches-Only solution proposed in [18], where if the most accurate results are found (i.e. Qall returns results), they are used, but in other case fairly appropriate results (i.e. results from Qsome) can be useful. Finally, if the execution time of the filtering stage is analyzed, actual query execution time is significantly lower than the wsml/rdf serialization (approximately 1 millisecond on average), an it is not so affected by the variation of the parameters defined in the experiment. Consequently, our proposed filtering stage could be further optimized by serializing repositories to RDF before performing that filtering. 6 Related Work There are some proposals that use a Semantic Web query language to perform discovery and ranking of services, though they do not use them to filter repositories. They choose SPARQL as their base language, though some extensions have to be added to fully support these tasks. Thus, Lamparter et al. [21] provide an ontology to represent service offers and requests that conforms the foundations for a discovery and selection process performed using rules in SWRL[15] and SPARQL queries. These queries includes predicates that have to be evaluated at run-time, so they include an extension to SPARQL that is implemented using different proposed algorithms. Thus, a query for a user request is provided, though this query depends on rules that change the matchmaking policy, e.g. allowing matching degrees as in [33]. Although this proposal effectively use extended SPARQL to perform discovery, it cannot be applied to generic scenarios because different rules have to be defined for each case. 26 Another discovery approach that uses SPARQL to actually perform semantic service discovery is proposed by Iqbal et al. in [16]. In this case, the authors embed semantic information about services using sawsdl, which is an extension to add semantics to WSDL descriptions [8]. Thus, they define pre and post-conditions of services using SPARQL CONSTRUCT queries so that depending on each service functionality, they add corresponding RDF tuples representing that functionality to the knowledge base. Then, their discovery algorithm use an ASK query to check whether a service fulfills a user request or not, returning the results. In this case, authors use standard-only SPARQL queries to perform discovery, though authors do not take non-functional properties into account. Finally, there is another approach, more related to ranking, presented in [29], where Siberski et al. propose an extension to SPARQL so that preferences are described directly using the query language, without basing on existing preferences and non-functional properties ontologies, as in other semantic ranking approaches [13, 12, 35]. They provide a PREFERRING clause that states preferences among values of variables, similar to FILTER expressions. However, this approach does not have the flexibility and reasoning facilities that provides a solution based on an external ontology, and it uses non-standard SPARQL extensions without providing an implementation. A study of these approaches and an analysis of the suitability of different query languages to perform discovery and ranking is presented in [10]. The conclusions of that study are that the main limitations of current approaches are, on the one hand, their lack of mechanisms to perform complex matchings and reasoning tasks, and on the other hand, their high coupling between description formalisms and algorithms used to evaluate the queries. The generic queries showcased in Sec. 3.1 conform a slightly different approach, because they are used at a previous stage of the discovery process, filtering the candidates and reducing the search space. Concerning the need for an improved discovery process which tackles scalability issues, Agarwal et al. discuss a hybrid approach that use different discovery mechanisms together, in order to improve discovery performance [2]. They also propose a simple filtering stage based on an efficient classificationbased discovery. However, this filter rely on a less expressive user request. Our proposal may be also applied to the authors hybrid approach in order to further improve discovery but using a more expressive model to describe user requests [13]. 27 7 Conclusions Although Semantic Web query languages are not widely used for SWS discovery and selection, they can certainly play a role in these scenarios. As discussed in this paper, some authors extend SPARQL query language to directly support these stages, but our proposal sticks to the standard, providing two different queries that may be used before actual discovery process in order to reduce the set of available services from the initial repository. Consequently, the reduced search space further improves scalability and performance in discovery and ranking stages. In this work, comprehensive simulation tests have been run, analyzing the actual reduction of the search space depending on several variables. The conclusions obtained are mainly that our proposal effectively reduce the search space, while it conforms a generic solution, adaptable to any SWS framework that a potential user may want to use. Particularly, an application to wsmobased services is discussed. Thus, a mixed approach is proposed, where both queries may be executed until reasonable results are returned, reducing the time consumption of matchmaking. Our proposal of including a (possibly multiple) filtering stage before the discovery and ranking processes has several benefits in addition to the already discussed optimization of discovery and selection processes by reducing the search space. These additional benefits are enumerated in the following: •Proposed filters are generic, so they can be used no matter what kind of user request and service descriptions are defined for each concrete scenario. Qall query is more specific, but can be generated automatically from a corresponding user request. •Our proposal do not distinguish between types of properties, i.e. both functional and non-functional properties can be used to filter the repository. In consequence, properties being used for both discovery and ranking stages are considered. •Filters can be applied to any SWS framework because they are based only in domain concepts referred by service descriptions and user requests. An application to the wsmo framework is presented in Sec. 4 •Our proposal is based on the current standard query language for the Semantic Web, i.e. SPARQL. Nevertheless, our proposed queries do not use any extension to the standard, so they are compatible with most SPARQL implementations. 28 References [1] L.A. Adamic and B.A. Huberman. Zipf’s law and the Internet. Glottometrics, 3(1):143–150, 2002. [2] S. Agarwal, M. Junghans, O. Fabre, I. Toma, and J. P. Lorre. D5.3.1 First Service Discovery Prototype. Technical report, SOA4All, 2009. [3] F. Alkhateeb, J. F. Baget, and J. Euzenat. Constrained Regular Expressions in SPARQL. In SWWS, pages 91–99. CSREA Press, 2008. [4] J. Bailey, F. Bry, T. Furche, and S. Schaffert. Web and Semantic Web Query Languages: A Survey. In N. Eisinger and J. Maluszynski, editors, Reasoning Web, volume 3564 of LNCS, pages 35–133. Springer, 2005. [5] J. de Bruijn, M. Ehrig, C. Feier, F. Martin-Recuerda, and F. Scharffe. Ontology Mediation, Merging, and Aligning. Wiley, 2006. [6] J. de Bruijn and J. Kopecky. WSML/RDF. Technical report, WSML, 2008. [7] John Domingue, Dieter Fensel, and Rafael Gonz´alez-Cabero. SOA4All, Enabling the SOA Revolution on a World Wide Scale. In ICSC, pages 530–537. IEEE Computer Society, August 2008. [8] Joel Farrell and Holger Lausen. Semantic Annotations for WSDL and XML Schema. Recommendation, W3C, August 2007. [9] Dieter Fensel. The Potential and Limitations of Semantics Applied to the Future Internet. In J. Filipe and J. Cordeiro, editors, WEBIST, pages 15–15. INSTICC Press, 2009. [10] J. M. Garc´ıa, C. Rivero, D. Ruiz, and A. Ruiz-Cort´es. On Using Semantic Web Query Languages for Semantic Web Services Provisioning. In SWWS, pages 67–71. CSREA Press, 2009. [11] J. M. Garc´ıa, D. Ruiz, A. Ruiz-Cort´es, O. Mart´ın-D´ıaz, and M. Resinas. An hybrid, QoS-aware discovery of semantic web services using constraint programming. In B. Kr¨amer, K.-J. Lin, and P. Narasimhan, editors, ICSOC, volume 4749 of LNCS, pages 69–80. Springer, 2007. [12] J. M. Garc´ıa, I. Toma, D. Ruiz, and A. Ruiz-cort´es. A service ranker based on logic rules evaluation and constraint programming. In 2nd ECOWS Non-Functional Properties and Service Level Agreements in 29 Service Oriented Computing Workshop, volume 411 of CEUR Workshop Proceedings, 2008. [13] J.M. Garcia, D. Ruiz, and A. Ruiz-Cort´es. A Model of User Preferences for Semantic Services Discovery and Ranking. In L. Aroyo, G. Antoniou, E. Hyv¨onen, A. ten Teije, H. Stuckenschmidt, L. Cabral, and T. Tudorache, editors, ESWC (2), volume 6089 of LNCS, pages 1–14. Springer, 2010. [14] Volker Haarslev and Ralf M¨oller. On the Scalability of Description Logic Instance Retrieval. Journal of Automated Reasoning, 41(2):99–142, August 2008. [15] I. Horrocks, P. F. Patel-Schneider, H. Boley, S. Tabet, B. Grosof, and M. Dean. SWRL: A Semantic Web Rule Language Combining OWL and RuleML. Technical report, W3C Member Submission, 2004. [16] K. Iqbal, M. L. Sbodio, V. Peristeras, and G. Giuliani. Semantic Service Discovery using SAWSDL and SPARQL. In SKG, pages 205–212. IEEE Computer Society, December 2008. [17] C. Kiefer, A. Bernstein, and M. Stocker. The Fundamentals of iS- PARQL: A Virtual Triple Approach for Similarity-Based Semantic Web Tasks. In K. Aberer et al., editors, ISWC/ASWC, volume 4825 of LNCS, pages 295–309. Springer, 2007. [18] W. Kießling. Foundations of preferences in database systems. In VLDB, pages 311—-322. Morgan Kaufmann, 2002. [19] M. Klusch, B. Fries, and K. Sycara. Automated semantic web service discovery with owls-mx. In AAMAS ’06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, pages 915–922, New York, NY, USA, 2006. ACM. [20] J. Kopeck´y and T. Vitvar. WSMO-lite. Technical Report D11v0.2 Working Draft, WSMO, 2008. [21] S. Lamparter, A. Ankolekar, R. Studer, and S. Grimm. Preferencebased selection of highly configurable web services. In WWW, pages 1013–1022. ACM Press, 2007. [22] L. Li and I. Horrocks. A software framework for matchmaking based on semantic web technology. In WWW, pages 331–339. ACM Press, 2003. 30 [23] C. Lutz and U. Sattler. A Proposal for Describing Services with DLs. In Int. Workshop on Description Logics, 2002. [24] D. Martin, M. Burstein, J. Hobbs, O. Lassila, D. McDermott, and Others. OWL-S: Semantic Markup for Web Services. Technical Report 1.2, DAML, 2006. [25] E.M. Maximilien and M.P. Singh. A framework and ontology for dynamic Web services selection. IEEE Internet Computing, 8(5):84–93, September 2004. [26] N. F. Noy. Semantic integration: a survey of ontology-based approaches. ACM SIGMOD Record, 33(4):65–70, December 2004. [27] E. Prud’hommeaux and A. Seaborne. SPARQL Query Language for RDF. Recommendation, W3C, 2008. [28] D. Roman, H. Lausen, and U. Keller. Web service modeling ontology (WSMO). Technical Report D2 v1.3 Final Draft, WSMO, 2006. [29] W. Siberski, J. Z. Pan, and U. Thaden. Querying the Semantic Web with Preferences. In ISWC, volume 4273 of LNCS, pages 612–624. Springer, 2006. [30] E. Sirin and B. Parsia. SPARQL-DL: SPARQL Query for OWL-DL. In C. Golbreich, A. Kalyanpur, and B. Parsia, editors, OWLED, volume 258 of CEUR Workshop Proceedings, 2007. [31] E. Sirin, B. Parsia, B. Grau, A. Kalyanpur, and Y. Katz. Pellet: A practical OWL-DL reasoner. Web Semantics: Science, Services and Agents on the World Wide Web, 5(2):51–53, June 2007. [32] N. Steinmetz and I. Toma. The Web Service Modeling Language WSML. Technical report, WSML, 2008. [33] K. Sycara, M. Paolucci, A. Ankolekar, and N. Srinivasan. Automated discovery, interaction and composition of Semantic Web services. Web Semantics: Science, Services and Agents on the World Wide Web, 1(1):27–46, December 2003. [34] I. Toma, D. Roman, D. Fensel, B. Sapkota, and J.M. Gomez. A multicriteria service ranking approach based on non-functional properties rules evaluation. In ICSOC, volume 4749 of LNCS, pages 435–441. Springer, 2007. 31 [35] X. Wang, T. Vitvar, M. Kerrigan, and I. Toma. A QoS-Aware Selection Model for Semantic Web Services. In A. Dan and W. Lamersdorf, editors, ICSOC, volume 4294 of LNCS, pages 390–401. Springer, 2006. [36] G.K. Zipf. Selected studies of the principle of relative frequency in language. Harvard University Press, 1932. 32