Semantics Web Research

Dynamic Discovery of Complex Constraint-basedSemantic Web ServicesLe Duy Ngan Data Mining Department, I2R, A*STAR, Singapore dnle@.sgLim Yuan JieTemasek Polytechnic,Singaporeyuanjie91@Rajaraman KanagasabaiData Mining Department,I2R, A*STAR, Singaporekanagasa@.sgAbstract — Web service discovery is the process of finding web service providers that satisfy specific service requester requirem ents. In real life scenarios, services are often described with com plex constraints and contain dynam ic aspects that are not adequately supported by m ost of the current discovery system s. In this paper, we propose a novel OWL-S based sem antic service discovery system for dynam ically discovering com plex constraint-based services. The proposed system is based on representing complex service constraints as Sem antic Web Rule Language (SWRL) rules and using a rule engine for m atchm aking, and handling dynam ism via a real-tim e ontology population and reasoning infrastructure. We consider the Semantic Web Service (SWS) Challenge shipping discovery scenario, and show with detailed illustration that our system is able to solve all the five service complexity levels successfully.Keywords-web service discovery; semantic web services; semantic service matchmaking; ontologies; semantic rules ;I.I NTRODUCTIONA Web service is a software component representing a service which is a business operation, a task, or an activity. It has become a key technology in the Web as it enables the interoperation of heterogeneous systems and the reuse of distributed functions in applications. A standard service-oriented ecosystem is comprised of service providers offering Web services and service requesters describing requirements in order to locate services. In such an ecosystem, publishing, binding, and discovering Web services are three important tasks. Among them, discovering services is a fundamental task that involves the process of finding web services, which satisfy specific requirements.Current Web services based on Web Service Description Language (WSDL) [1] employ naive syntactic representations to describe the services. This leads to a lackof semantic understanding that prevents fully automatic discovery, composition, and interoperability. Towards addressing this, Semantic Web Service (SWS) formalisms [2] that exploit Semantic Web Technologies [3], have been proposed to facilitate rich and formal representations of services. Several semantic Web service description languages such as OWL-S [4], WSMO [5], SA-WSDL [6], etc. have been developed.Semantic Web Service discovery leverages on the SWS formalisms to search for service providers satisfying a service requester's requirement [10]. OWLSMX [7], TUB [8], and MOD [9] are examples of such systems. However, most of these discovery systems support service matching mainly based on the input parameters required to execute the service and the service output that represents the results of the execution. This limitation is partly caused by the current description languages, e.g. OWL-S, that have limited support for describing functional and non-functional properties. They are often not expressive enough to support advanced service descriptions that involve complex constraints that are common in real world applications [10].For example, consider a shipping scenario where a shipping provider offers a service to ship a package from one place to another place. The service provider may have several constraints on its service as follows: (1) Ships to Africa, North America, Europe, and Asia; (2) Only packages weighing 50 lbs or less are shipped; and (3) If the collected time is before 6pm, then the shipping duration will be less than a day. Of these, the first constraint can be described in the standard ontology modeling the services. However, this is not true for the second and the third constraints as the current ontology languages have limited support for such complex constraints. Similarly, the service requester may have similar sophisticated constraints in the requests. Towards modeling real world scenarios, we argue that it is important to support such constraint descriptions in current description languages. On another direction, the semantic description of some advertised Web services may completely be available only by invocation. This may be the case if, for example, it turns out to be impractical to provide an exhaustive semantic description of the capabilities offered. It is desirable that the web service discovery system supports matching of service providers and requesters dynamically.WSMO-based works that support complex constraints have been reported in the literature [11-12] but systems based on OWL-S are a few. This paper aims to investigate if dynamic discovery of complex web services is feasible with OWL-S and related W3C technologies alone. We propose a novel OWL-S based semantic service discovery system for dynamically discovering complex constraint-based services.A novel service matchmaking method is proposed when2011 Fifth IEEE International Conference on Semantic Computingservice offers and goals come with complex constraints. The proposed system is based on representing complex service constraints as Semantic Web Rule Language (SWRL) rules and using a rule engine for matchmaking, and handling dynamism via a real-time ontology population and reasoning infrastructure. We consider the SWS Challenge shipping discovery scenario, and show with detailed illustration that our system can solve all the five service complexity levels successfully.The rest of the paper is organized as follows: Section 2 introduces Web service discovery and provides the problem definition. Section 3 presents our proposed semantic rule based dynamic web service discovery system. In Section 4, we describe evaluation of our system on Semantic Web Services Challenge discovery scenario1. Related work is discussed in Section 5, and followed by the conclusion in Section 6.II.W EB SERVICE DISCOVERY: PROBLEM F ORMULATIONA.Web Service DiscoveryWeb service (WS) discovery is the process of finding web services that satisfy specific requirements. A typical service discovery framework has service providers advertising their web services at one end and a service requester searching for the advertised services matching its specific requirements, at the other end. Services are often described by the functional description including Inputs, Outputs, Preconditions, and Effects (IOPE’s) and the Non-Functional Properties (NFP’s). The service repository aggregates the advertised services after suitable mediation and/or alignment to resolve the heterogeneities. When a request service is initiated, it is first matched against the advertised services in the repository using the matchmaking engine. A fter matched results are obtained, service negotiation is invoked to interact with the providers to access dynamic information, if any. Service selection is then doneto the requester's preferences and/or based on NFP considerations. Finally, the selected service is invoked and the results returned.The key foundation of the framework is the formalism employed for representing service descriptions. WSDL [1] isa well-known standard for non-semantic web services. For semantic web services, typical formalisms include OWL-S [13], WSMO [5], and WSDL-S [14]. A Web service discovery system needs to satisfy several important criteria, which vary depending on the contexts and applications. Some of the key criteria to be considered include: constraints, standards compliance, expressiveness, autonomy, QoS, scalability, robustness, dynamism, and heterogeneity [10].1 /wiki/index.php/Main_Page B.Motivation of our WorkDiscovery systems typically support matching the services primarily based on the input parameters required to execute the service and the service output that represents the results of the execution. Most of the existing systems are not able to handle the complexities in real-life service discovery that include:1)Constraints for discovery: A Web service is often characterized by certain attributes. For example, the web service can be invoked if a set of attributes satisfy some pre-specified rules. Some other attributes could be characteristics of the services or characteristics of the products associated with the service. These attributes characterize the service as a whole. When a service provider publishes a Web service, it is important to specify the constraints associated with these attributes (i.e., the values that these different types of attributes should or can have). The service is only involked if its constraints are satisfied.2)Dynamism for discovery: The semantic description of advertised Web services and requested Web services may be insufficient for discovery to take place, due to cases where services do not provide an exhaustive semantic description of the capabilities and functions offered. For instance, in the case of , a semantic description of the Amazon Web Service capabilities could not include all the books available for sale at any instant. Instead, it is possible to invoke an operation on the Web Service to determine if a specific book is available and to get additional information about the book such as its price or availability. This information may be necessary for a discovery engine looking for a service that can sell a certain book at or below a specified maximum price.In this paper, our objective is to develop a web service discovery system that supports i) descriptions with complex constraints, and ii) matching of service providers and requesters dynamically.C.Problem DefinitionDefinition 1 (Web Service): Given IN S is a set of input and OUT S is a set of output of service S. C S is an optional set of atomic or conjunction of atomic constraints. Service S is represented as follow:S S = (IN S, OUT S, C S)Following Definition 1, a requested Web service is represented as:S R = (IN R, OUT R, C R)and an advertised Web service is represented as:S P = (IN P, OUT P, C P)Definition 2 (Service discovery):Given a repository of provided services ReP and S R is a requested service. Service Discovery is a process to search for provided services S PאReP such that: IN R is subsumed by IN P, OUT P is subsumed by OUT R and every constraint in C R is satisfied by C P.The next section presents our method for discovering services according to Definition 2.III.SEMANTIC R ULE BASED DYNAMIC DISCOVERYSYSTEMA.Supporting Constraints in OWL-SOWL-S is a service description formalism and has strong support from the research and industry communities [15]. It comprises three main parts: Service Profile, which is for advertising and discovering service capabilities; Service Model, which gives a detailed description of a service's operation; and Service Grounding, which provides details on how to interoperate with a service, via messages. Generally speaking, OWL-S Service Profile provides both the functional and non-functional information needed for an agent to discover a service, while OWL-S Service Model and OWL-S Service Grounding, taken together, provide enough information for an agent to make use of a service, once found. OWL-S provides a generic way of representing condition expressions2 in Web services. It supports six languages and logics including SWRL, SWRL-FOL, DRS, KIF, SPA RQL and RDQL and can be easily extended to support other logic expressions. However, reasoning support over logic expressions embedded in OWL-S is limited. In this paper, we take a different approach whereby we model the pre-conditions and post-conditions as constraints in the domain ontology. As proof of concept, we adopt SWRL [16] to model the constraints.SWRL is a proposal for a Semantic Web rule language, combining sub-languages of the OWL Web Ontology Language (OWL DL and Lite) with those of the Rule Markup Language. Therefore, SWRL uses OWL axioms and enables Horn-like rules to be combined with an OWL knowledge base. SWRL rules are written as pairs of antecedent (head) and consequent (body), both expressed as a conjunction of one or more atoms. A rule expresses the following meaning: whenever the conditions specified in the antecedent hold, then the conditions specified in the consequent must also hold. Rules with disjunctive antecedents can be equivalently rewritten as multiple rules each corresponding to a disjunct. Similarly, rules with conjunctive consequents could be changed into multiple rules each with an atomic consequent. Thus, SWRL rules give additional expressivity but at the expense of decidability. In this paper, we consider a subset of SWRL where the variables bind only to known instances in an ontology, but may contain builtins.The syntax for SWRL extends the abstract syntax of OWL. A rule, in this syntax, has the form: "antecedent consequent" where both antecedent and consequent are conjunctions of atoms written a1 ... a n. Variables are indicated using the standard convention of prefixing them with a question mark (e.g., ?x) [17]. Using this syntax, a rule asserting that the composition of parent and brother 2 /daml/services/owl-s/1.2/generic/Expression.owl properties implies the uncle property would be written as: "parent(?x; ?y) ^ brother(?y; ?z) uncle(?x; ?z)". If Bill has Job as a parent and Job has David has a brother, then this rule requires that Bill has David as an uncle.Figure 1. A SWRL exampleSWRL rules reason about OWL individuals, primarily in terms of OWL classes and properties. For example, a SWRL rule expressing that if the shipping requester expects to ship a package to the shipping provider residing in the same country then the provider can satisfy the requester is depicted in Figure 1. Intuitively, the concept of ShippingServiceRequester and ShippingServiceProvider can be captured using an OWL class; shipTo is a property of the ontology. Executing this rule would have the effect of setting the ShippingProviderMatched property to Provider in the individual that satisfies the rule, named Requester.Jess is a rule engine and scripting environment for the Java platform3. Jess is small, light, and one of the fastest rule engines available. Jess has many unique features including backwards chaining and working memory queries, and Jess can directly manipulate and reason about Java objects. Our SWRL rules are executed using Jess. SQWRL [18] is based on the SWRL rule language and uses SWRL semantic foundation as its formal underpinning. It offers a way to allow OWL ontologies to be queried. It also provides a set of operators to perform closure operations to allow limited forms of negation as failure, counting, and aggregation.B.Dynamism for DiscoveryOur approach uses an in-house semantic technology infrastructure powered by A llegroGraph44, to process the ontology, perform population & reasoning, before invoking the matchmaking. The strategy for handling dynamism is as follows. Given a service request, first an ontology loader reads up the service offers in the repository. Each service offer may have WSDL end points containing methods that can be invoked only during run-time (e.g., shipping rate computation). The needed WSDL methods are invoked based on the service specifications and the results are added to the ontology with the Ontology Population engine. The matchmaker makes use of the populated information to return suitable service offers.3 Jess Rule: /4 /agraph/allegrograph/C.Semantic Rules based MatchmakerMost of existing discovery systems are based on input and output matching alone. In this paper, the focus is on matchmaking engine that supports complex constraints.Our match-making engine includes three main components, namely, input-output matching, SWRL rule based matching, and dynamic discoverer. The input-output matching (shortly, IO matching) performs semantic matching of the input and output concepts using ontological reasoning. The dynamic discoverer component is responsible for dynamic matching while the Rule based matching engine takes care of the complex constraints.Figure 2. Architecture of the proposed systemThe proposed discovery system is presented in Figure 2. The provider services (or advertised services) are aggregated to form the service repository. Suitable domain ontologies are assumed to be pre-specified. The core of the system is the match-making engine component which matches the given Web service request against the services in the repository to return the best match(es). The engine first performs IO matching which is followed by constraints matching. The latter is done via SWRL rule matching with Jess. Specifically, the facts and rules embedded in the OWL ontology are first translated to Jess format, and then Jess engine is then invoked to generate new facts. Finally the new facts are translated back into OWL and instantiated into the ontology. The resulting ontology is then analyzed to infer the matched results.To handle dynamically available service descriptions, an additional step is needed before matchmaking. To verify if such a service matches the given request, first the service descriptions are retrieved on-the-fly and the retrieved descriptions populated into the ontology. Now matchmaking engine is executed to perform IO matching and constraints matching.IV.C ASE S TUDY: SOLVING THE SWS CHALLENGES HIPPING DISCOVERY SCENARIOA.SWS Challenge Shipping Scenario DescriptionSWS Challenge5is an initiative to develop a common understanding of various technologies intended to facilitatethe automation of mediation, choreography and discovery of Web services using semantic annotations. It presents several complementary scenarios involving mediation, discovery and composition. For service discovery, it provides a shipping scenario wherein the objective is to find the best shipment service, taking into consideration pickup location, delivery location, delivery time, price and similar constraints. Five shipping service providers namely, Muller, Racer, Runner, Walker, and Weasel with varying levels of service offer complexity are described and exposed via WSDL endpoints. For example, Muller, Racer, and Runner provide different shipping specifications, e.g. Muller only provides rates on request; Racer adds $12.50 for each collection order; Runner requires that only one package can be ordered per shipment.The discovery task involves finding service offers that satisfy/match a set of service goals. Such goals, in turn, are defined in terms of varying levels of difficulty, e.g., discovery based on destination; discovery based on destination and weight; discovery based on destination, weight and price; discovery involving simple composition;as well as discovery including temporal reasoning. The more attributes are involved in the discovery process, the more difficult and complex this task becomes.B.Our SolutionThe solution involves constructing a semantic model to describe the service offers and goals, and then applying our method (Section III) to perform matchmaking.1)Service and Domain Ontologies:a)Domain Ontology Model: We first design a domain ontology to capture the concepts and properties involved inthe shipping scenario. Protégé ontology editor was used to create the ontology (Figure 3(a)). ShippingServiceProvider, ShippingServiceRequester, Country, and Rate are the main concepts used. ShippingServiceProvider is the class of shipping providers whose instances are Muller, Racer, Runner, Walker, and Weasel. Their data type properties are deliveryTime and hasInterval. Their object properties are hasRates and ShippingProviderMatched. Concept ShippingServiceRequester describes Goal's information. Its instances are goals (also called service requests). They have data type properties such as hasPrice, hasCollectionTime, hasCollectionOrder and so on.b)Service Ontology Model:OWL-S Service Description:Fig.3(b) represents interfaceof Muller service. The service includes two inputs, namely: shipmentOrderRequest and invokePriceRequest and two outputs, namely: shipmentOrderResponse and 5 /wiki/index.php/Main_PageinvokePriceResponse. The two inputs and two outputs are concepts from Shipping ontology represented in Fig.3. The description of Muller service in OWL-S is as follows. OWL-S description for a service including 4 classes, namely: Service, Service Profile, Service Process, and Service Grounding. However, for discovery, only Service Profile is needed as it contains all information required to discover the service. However, in order to access Service Profile, we need to start from the Class Service which is the starting point containing links to Service Profile, Service Process, and Service Grounding. Service Profile presents their input and output via Service Process. Service Grounding, which describes how to invoke the service, is used for binding and after the discovery process.a) Shipping Classes b)Object Propertiesc) Datatype propertiesFigure 3 (a) Shipping ontologyFigure 3 (b) Muller service classFigure 3. Shipping service ontologySWRL Descriptions: Simple service descriptions such as"Ships to A frica, North A merica, Europe and A sia" areeasily modeled within the OWL-S ServiceProfile by usingrespective concepts from domain ontology. However, forcomplex service descriptions such as "Ships in 2/3 businessdays if collected by 5pm", OWL-S model is insufficient.Our solution represents such descriptions with SWRL asdescribed below.2)Constraint Modelling: In general, the servicedescriptions primarily specify criteria on four aspects: i)Package dimensions & weight; ii) Shipping rate; iii)Delivery (Place & Time); and iv) Collection. Among them,Delivery (Place) is the simplest and can be modeled withstandard OWL-DL. Shipping rate computation is specifiedthrough a formula except in the case of Muller due to thefact that the shipping rates are only provided upon actualrequest. In our approach, we compute the shipping ratesdynamically during run-time with our semantic backend.Other constraints are modeled with SWRL as illustratedbelow. In the following discussions, we use shipping serviceprovider Muller as an example. Rules for the other providersare created as in the same manner.a)Constraints on Collection: Consider Muller'scollection constraints:1.There must be at least an interval of 90 minutes forcollection.2.Collection is possible between 7am and 8pm.3.Collection can be ordered max 2 working days inadvance.We use the Collection concept in the shipping domainontology, to define a SWRL rule as described in Figure 4:Figure 4. SWRL for constraints on collectionb)Constraints on Delivery Time:As above, we use theDelivery concept in the shipping ontology. The constraint"Ships in 2/3 (domestic / international) business days ifcollected by 5pm" is modeled as the rule shown in Figure 5:Figure 5.SWRL for constraints on delivery timeIn short, the complete rule, which is an aggregation ofmultiple atomic rules, for Muller is presented in figure 6 andfigure 7. Figure 6 is the case when the collection time isbefore 5pm and figure 7 is the case when the collection timeis after 5pm.Figure 6. Muller advertised service with collection time before 5pmFigure 7. Muller advertised service with collection time after 5pmTABLE I. SWRL C ONSTRAINTS3)Dynamic DiscoveryMuller has a special feature whereby it provides rates by invocation via the invokePrice method in WSDL. This implies that the rates constraint cannot be verified during planning stage. We employ our dynamic discoverer component to tackle this, by calling the invokePrice method and asserting the hasRates property. Now the SWRL rules are reasoned over to perform matchmaking.4)Discovery Requests and Results: Next, we briefly discuss different discovery requests and their expected match-making results. The goals are organized according to their anticipated difficulty beginning with the simplest. Each level containts one, two, or three goals. We have modelled and tested all the goals but, due to space limitations, we present one example goal for each level of difficulty. The goals are A1, B1, C1, D1, and E1 as described in SWS Challenge6. The actual rules to perform matchmaking between the goals and service offers, are presented in TableI.a)Discovery Based on Destination: This discovery is based on only one criteria: Destination. A rule that matches destinations of a requested Web service with an advertised Web service is presented in Table 1 (Index 1). This is achieved by comparing the 'country' from which the advertised service offers shipment and the 'country' to which the requested service asks for shiping. Goal A1 constraints are described as follows:•to: Szyslak (Tunis)•package dimensions: (l/w/h) 7/6/4 (inch)•package weight: 1 lbThis is the simplest goal as the purpose is to test on the destination only. Given that the package dimension and weight are very small (1 lb) all providers are satisfied. It is interesting that goal A1 asks for a shipment to a City (Tunis) but the providers only specify shipment requirements to Countries. By modeling the relationship between City and Country in Domain Ontology (Figure 3(a)), the system is able to infer that a particular City (ie. Tunis) belonging to a particular Country (ie. Szyslak). Hence, among the providers, only Muller, Runner, and Walker ship to Szyslak (Tunis). Racer and Weasel do not ship to Szyslak (Tunis). Therefore, the matched providers are Muller, Runner, and Walker.b)Discovery based on Destination and Weight: This discovery is based on two criteria: Destination and Weight. Rules for matching Destinations were presented above. Rules for comparing weights are shown in Table 1 (Index 2). Constraints for Goal B1 are as follows:•to: Szyslak (Tunis)•package dimensions: (l/w/h) 40/10/10 (inch)•package weight: 30 lbsThough this request comes with more constraints, the results are same as for Goal A1 since all the providers are able to ship package heavier than 30 lbs.6 http://sws-/index.php/Scenario:_Shipment_Discoveryc)Discovery based on Destination, Weight, and Price: This discovery is based on three criteria: Destination, Weight, and Price. We illustrate with Goal C1 whose contraints are as follows:•to Gumble (New York)•package dimensions: (l/w/h) 10/2/3 (inch)•package weight: 5 lbs•for less than $20This is even more difficult as it involves price in match-making and which must be computed based on the weight, rates, and size of the packages. We model this via SWRL built-in constructs Rules for comparing prices are presented in Table 1 (Index 3). The results of this matching are Runner and Weasel. Muller, Racer, and Walker do not match as their prices are higher than requested. (Muller’s price is $35; Racer’s price is $59.50; Walker’s price is $49.50).d)Discovery Involving Simple Composition: This matching criteria is simple as it is based on destination and weight only. Goal D1 constraints are as follows:•to Szyslak (Tunis)•no of packages: 2•package dimensions: (l/w/h) 5/3/2 (inch)•package weight: 60 lbs (each)The number of packages is two but all providers limit ordering to 1 package only. This goal tests the ability to do simple composition. We model this via SWRL built-in constructs Rules for invocation presented in Table 1 (Index 4). Only Runner satisfies the goal but it needs two invocations since it does not allow ordering multiple packages in one invocation. The others are not matched because Racer does not ship to Tunesia; Muller does only ship 50lbs; Walker does only ship 50lbs; and Weasel does not ship to Tunisia.e)Discovery Including Temporal Reasoning: This matching criteria relates to the delivery time. Contraints for Goal E1are as follows:•to Gumble (New York)•package dimensions: (l/w/h) 10/2/3 (inch)•package weight: 5 lbs•for less than 20$•Current Time is 7:30 am•Next day deliveryThis is the most difficult goal as the requester also considers delivery time. This rule is a kind of ‘If-Then- Else’ type. In order to model this rule in SWRL, we need to have two SWRL rules: one to present the 'If Clause' and the other presents the 'Else Clause'. The corresponding rules are presented as in Table 1 (Index 5). Only Weasel is matched. The remaining providers are not matched because Muller needs 2 days; Racer needs 2 days; Runner needs 3 days; and Walker needs 2 days while the requester ask for 1 day only.In summary, the case study shows that our discovery system solves the SWS Challenge Shipping scenario completely with all tasks in the five levels of difficulty including the individual goals of each level. It also indicatesthat OWL-S based discovery with SWRL rule modeling can handle real life situations that involve complex constraintsand dynamism.V.R ELATED WORKSWS discovery has received significant attention in thelast few years, and various systems have been proposed [10].Most of the works focus mainly on Input-Output matchingand do not address the constraints and dynamism issues, e.g. OWLSMX [7], TUB [8], and MOD [9].For constraint support, Degwekar et al. [19] presented an extension of WSDL to include constraint specifications in service descriptions due to the fact that WSDL does not support constraints descriptions. This is done by specifying a constraints tag for elements in WSDL. For instances, “input_constraint”, “output_constraint”, and “operation_constraint” tags give the constraint descriptionsfor the input, output, and operation elements, respectively.The work only supports WSDL specification which does nothave semantic descriptions and annotations.Hwang et al. [20] proposed an inference process to provide intelligent acknowledge using OWL and user defined rules using SWRL. Li et al. [21] proposed a RuleSpaces for SWS based on a combination tuple-spaceand SWRL. Dong-wei et al. [22] introduced a semantic matchmaking method of web services constraint conditions.Fu et al. [23] and Martin et al. [24] attempt to combine inputand output matching, pre- and post- condition matching, andQoS matching. These methods only solve simple constraint based-applications. For instance, Hwang et al. [20] is limitedto control point management applications which support administrator, checker, installer, surveyor, and observer. Moreover, these systems do not address the dynamism aspect.SWE-ET [11], DERI [12], and DIA NE [25] are discovery systems which attempted to solve the Shipping Discovery Scenario defined by SWS-Challenge. SWE-ET performed matchmaking based on the notion of a single goal instance and the available web service instances. DERI is based upon WSMX – the WSMO execution environment, models services, goals and ontologies directly in WSMT7,and expresses rules using WSML. DIANE employs a fuzzyset based approach to matchmaking but the matchmaking algorithm based only on logic matching is simple since thework focus is on web service composition. Hence, SWE-ET [11], and DERI [12] are based on WSMO and DIANE basedon its own description language, namely, DSD (DIA NE Service Descriptions) to solve the constraints and dynamism issues. In contrast, our system not only solves the SWS Challenge Shipping scenario completely but is possibly thefirst system to do so using an OWL-S based approach.7 /TR/d9/d9.1/v0.1/20050127/。