The vision of Semantic Web services is that computer systems shall find eligible services autonomously. This can be realised with providing semantic description about advertised and requested services. In this scenario a so-called matchmaker finds matches between service requirements and advertisements according to their description. Based on the ontology language DAML+OIL a proposal for an upper ontology for the semantic description of services called DAML-S exists already. Also, approaches were introduced, which act as matchmakers for DAML-S descriptions. The contribution of this work is a new algorithm, which ranks the level of matching for DAML-S descriptions. To determine the different degrees of matching, elements of the DAML-S description are considered and matched individually. With ranking a criterion is available to select a service among a large set of results. Consider the result of flat matchmaking that consists of a set of matching and another set of non-matching services. If an autonomous system must still choose one of the set of matching services. An ordered list of services provides a decision support to autonomously choose the best service possible.
The Semantic Web working group of the W3C develops technologies and
standards for the semantic description of the Web. The goal of these efforts is to
make the Web understandable by machines in order to increase the level of
autonomous interoperation between computer systems [
Service Provider
Service
Client
These languages are primarily used for content. The next logical step is to
describe the semantics of services for optimising their platform- and
organisationindependent interoperability over the Internet. Referring to the Semantic Web,
the research field addressing this objective is named Semantic Web services [
Using DAML-S for the description of Web services can increase the ability of computer systems to nfid eligible services autonomously. A service provider describes his advertised services in a DAML-S description and a service requester queries for services with a DAML-S description expressing his requirements. In this scenario a socalled matchmaker nfids matches between service requirements and advertised services according to their descriptions.
We will introduce previous work already addressing the matching of DAMLS descriptions more precisely in section 4. Our approach is an algorithm, which ranks the level of matching for advertisements with requirements. The ranks are determined by considering individual elements of the DAML-S description and the aggregation of their individual matchmaking. 2
For the application of the matching algorithm, we can distinguish two scenarios: In the rfist, the semantic description of individual services is stored and processed on a central server. For this, existing repositories managing information and addresses of Web services could be extended to be compatible with DAML-S descriptions. A service requester provides with his query also his description and the server processes this request by matching the requirements with the description of eligible services. Then the server returns the best match. This scenario pretends that a generally accepted organisation maintains the repository and service providers are willing to submit a DAML-S description about their services. Figure 1 outlines this schema. An existing specicfiation for a repository Service Repository
UDDI DB returns service
address
queries
services
registers service
to nfid Web services in the Internet is UDDI [
In the second case the service requester obtains the DAML-S description for eligible services and performs the matching process on its own. The address of the service and the information how to obtain the DAML-S description can be found in a repository. Figure 2 outlines a scenario, where the service requester contacts an UDDI repository to nfid eligible services. Then, the individual services are contacted and their descriptions are requested. The service requester processes the descriptions and ranks the service by their level of matching. To favour either the server-centirc solution the following considerations are relevant: Simple Client: The implementation of a client, which acts as the service requester can be kept very simple. Thus, the effort for finding services on the client side is very low.
Centralised Logic: Since currently DAML-S is an evolving proposal, it is likely that languages, standards and maybe the matching algorithm may become revised. Applying the necessary changes only on the server-side means lower efforts than keeping various applications up-to-date.
These two advantages are also well known for other approaches, which have lead to a server-oriented architecture in general. However, some advantages exist, which might be deciding to prefer a client-sided approach: Custom Matching: A service requester wants to use an own matching algorithm instead of the implementation of the central server. In our matching algorithm we also provide to extend the matching with user-denfied modules. These user-defined modules can denfie constraints that must be present in the DAML-S description of the advertised service. Only with the clientsided execution of such modules the personalisation of the matching process is possible.
Organisational Limitations: To perform the matchmaking of DAML-S descriptions on a central server pretends the cooperation of the service providers to submit their DAML-S descriptions. A decentralised approach would mean less organisational efforts and a quicker adoption within an organisational domain.
Since our approach includes user-customisable modules to enhance the matching algorithm, we favour the client-sided scenario. In our work a client application representing the service requester queries the DAML-S description from an already obtained list of services to find the best match. 2.1
Short Introduction to DAML-S The DAML-S ontology denfies three basic elements: (1) a service profile to describe the functionality of a service, (2) a service model to model the structure of the service, and (3) a service grounding to map the abstract interface to a concrete binding information. As the focus of this work is on the discovery and selection of Web services, our main interest lies in the prolfie, which provides the necessary information for the matching algorithm. The prolfie provides three basic types of information. First, it presents a textual description and contact information, which is mainly intended for human users.
The next information provided is a functional description of the service. This functional description is expressed in terms of the input parameters and the output parameters generated by the service. Additionally, the functional description is described by two sets of conditions, namely preconditions, which have to hold before the service can be executed properly, and effects, which are conditions that hold after the successful execution of the service. These four functional descriptions are also referred to as IOPE (Input Output Precondition Effect). The IOPEs are realized through an object property called parameter. This property assigns a class of type ParameterDescription to the prolfie. The following four object properties are subproperties of parameter, and describe the functional behaviour of the Web service: input output precondition Effect
have as many inputs as required (including none).
have as many outputs as required (including none).
Finally, the prolfie comes with a set of additional properties that are used to describe features of the service. From these properties we use in our algorithm the service category, which is used to classify the service with respect to some ontology or taxonomy of services. The value of the property is an instance of the class ServiceCategory. 3
As defined in the DAML-S specification, a Web service is semantically described by an instance of the class Profile . Although a service can have multiple profiles as a Web service can provide multiple operations, in the following the words service and prolfie are used synonymously, meaning one specicfi profile definition.
F ail(A, B) Subconcept(A, B) Equivalent(A, B) An instance of this class holds all the inputs and outputs associated with that service as object properties; it is therefore possible to find a relation between two services by directly finding the semantic relationship between the instances of the referring Profile classes, which would include all the existing relationships between the input and output parameters, as these are properties of the prolfie. Moreover, if the Web service is described by an instance of a subclass of the class Profile, a matching algorithm can also perform a subsumption reasoning to determine the relation between the two services.
The result of this consideration is a matching algorithm, which is divided into three stages: (a) the matching of inputs, (b) the matching of outputs, and (c) the matching of the service prolfie classification itself. This algorithm determines the matching for each of the stages individually. The result is aggregated with a fourth stage, where user-denfied constraints or functionality can complete the matching result. Most parts of the matching algorithm will build on the semantics of the services. Using DAML-S means that the semantics are denfied in a DAML+OIL ontology. Our first task is thus classifying the different relations between two concepts and two properties to determine the degree of matching. From sections 3.1 to 3.3 we will explain the different three stages and the forth user-defined stage. In section 3.5, we present how the results of the different stages are aggregated to form the whole algorithm.
Let A, B denote two concepts which originate from a given set of ontologies. Then the following three relationships between A and B are considered:
The matching algorithm queries the underlying knowledge base to determine the relationship between the concepts. For checking the equivalence of two concepts, it is not sufficient to check if A = B. Two concepts can be equal even if they have different names and are defined in two different ontologies, as it is possible to equalise two concepts with usage of the <sameClassAs> element.
Let R and S denote two properties which originate from a given set of ontologies. We then have the following relationships between R and S: F ail(R, S) Subproperty(R, S) Equivalent(R, S)
The matching algorithm provides a functionality to determine the above mentioned relation between two given properties. As with concepts, two different properties can be defined to be equivalent by using the tag element <samePropertyAs>. In the implementation the matching algorithm queries the knowledge base to determine if two properties are equivalent. 3.1
Matching of Inputs At this matching stage it is determined how well each input of the advertised service matches with an input of the requested service. As a general condition for using the advertised service properly, every input of the advertised service has to be matched. Since any input itself is defined as a property, there are two possibilities of nfiding a match: property matches and type matches. For the matching of the input properties table the following matching results can be distinguished: F AIL SU BP ROP ERT Y
put of the advertised service. This means that the more specific property of the requested service will at least provide the same characteristic as required for proper invocation of the advertised service.
EQU IV ALEN T
For the matching of input types as defined in the service prolfie, subsumption reasoning can be applied, because the types are described as concepts: F AIL SU BSU M ES
matched or the requested service subsumes the input type of the advertised service. This means that a more specific input type is required than advertised. In this case the demands of the service requester are not met.
EQU IV ALEN T
For the ranking of the matching result of this stage, the result of property matching and type matching must be combined. In this combination, the property matching is given a higher priority than the type matching, because the classicfiation of an input gives more insight to it’s purpose than it’s type definition. The table 1 lists the different combinations of results from the propertyand type-matching and the applied ranks. 0 1 2 3 4
Any Any
In this stage of matching it is determined how well the outputs of the advertised service correspond to the outputs of the requested service. During the output parameter matching, the algorithm tries to nfid a match for each output of the requested service. Analogously to the matching of inputs, the matching of outputs considers property-match and type-match degrees to find a relationship between two outputs.
However, the direction of the generalisation is now reversed, meaning that a Subproperty degree is recognized when the output of the advertised service is a subproperty of the output of the requested service and a Subsumes degree is found whenever the type of the output parameter of the advertised service is subsumed by the type of the output parameter of the requested service. In other words the output of requested service considers more general denfiitions than the output of the advertised service. This ensures that the requirements of the service requester will still be met. The denfiition of matching results for the property-matching and type-matching is omitted, because of it’s mentioned
Any Any
of the advertised service. For every output pair the property-match degree is Equivalent, but at least for one output pair the type-match degree is
similarities to the input matching. Table 2 summarises the ranking levels for output parameter matching like table 1 for the input parameter matching. For every output parameter of the requested service the algorithm tries to find the matching output parameter of the advertised service that would result in the highest rank. As expected, these two output parameters then form a (matched) output pair. 3.3
Matching of the Service Profile In DAML-S a service can be classified with certain categories described in a DAML+OIL ontology. In this ontology the individual service is an instance of a subclass of the class ServerCategory. With prolfie matching we try to determine how well the service category of the advertised service fits into the service category that the requested service demands. Let reqServiceCat denote the service classicfiation of the requested service, and advServiceCat denote the service classification of the advertised service. Both reqServiceCat and advServiceCat are thus concepts defined in some service classifying ontology. The identified matching results when matching the profile of the service request and the advertised profile are shown in table 3.
Rank Degree of Match
Interpretation 0 1 2 3
Either the description of the advertised or the required service is not classified or one of the both are instances of the class Profile . advServiceCat is an instance of class, which is subsumed by the class of the instance of reqServiceCat. In this case the classification of advServiceCat is more more specific than the classification of reqServiceCat. This means that the advertised service oeffrs more specific functionality than required. reqServiceCat and advServiceCat are instances of the same class.
To clarify the meaning of the Subsumes degree, let us consider a small example: Assume a computer program which acts as a broker wants to let its user buy computers from different web stores. Therefore the program needs to make use of functions by web merchants who offer Web services, which allow to buy computers. The broker program thus looks for Web services which are classified into the service category BuyComputers, for example. Any advertised Web service which falls into the categories BuyDesktopComputers or BuyLaptopComputers, which both are subcategories of the category BuyComputers, would still be useful to the computer agent, allowing its users in turn to buy more specific kind of computers. 3.4
User-defined Matching In addition to the three matching stages also a user-defined matching stage is provided. In the implementation, this matching stage consists of one or more additional modules, which can define specicfi requirements or conditions, which must be found in the description of the advertised service. As a result each of the modules returns either true or false. All matching results from the modules are interpreted conjunctively. If one user-defined matching function fails, the whole user-denfied matching fails. For example, an important aspect that comes with the user-defined matching is the ability to verify that Quality of Service
DAML-S Description of Requested Service
DAML-S Descriptions of Advertised Services Input Matching
Output Matching
Profile Matching
Custom
Module Aggregate Results Rank/Fail
Matchmaking
Software (QoS) constraints are met. A prolfie in DAML-S allows the specification of QoS for a given Web service via its class QualityRating. Thus, with given service denfiitions, it is possible to create plugins that performs a quality of service matching based on the available additional information in a service prolfie. The result of the matching algorithm is an aggregation of the individual four stages. The simplest approach is to add up the ranks of the rfist three stages and complete the sum with the result of the user-denfied module(s). The aggregated result is either the sum of the rank of the individual stages, which is an abstract measure of the matching quality, or the conclusion, that the descriptions did not match. However, the aggregation must consider, that if any of the individual stages will fail, the aggregated result must be regarded as fail as well. A perfect match of an individual matching stage cannot compensate a fail of another stage. This aggregation schema is outlined in figure 3. 4
Our proposal has elements from matching approaches for DAML-S, which were
already introduced. A variation of the matching algorithm is to match
complete Service Profile descriptions as found in [
Furthermore, DAML-S specifications can be arbitrarily complex. By
splitting up the prolfie and determining the matches individually for the subparts,
the algorithm can identify matches between service requests and advertisements
more closely. The disadvantage that parts of the prolfie are ignored can be
compensated with the proper usage of user-denfied modules. For example, a module
that evaluates QoS statements could easily be added to the matching algorithm.
Another characteristic of our work is that we consider the direction of the
inheritance hierarchy between service requests and advertisements (”which concept
subsumes which one”). This aspect can be considered as an refinement of existing
matchmaking approaches as found in [
The matchmaker ATLAS [
The matching of service descriptions is also addressed in other fields, which
are not related with Web services or DAML-S. As an example, we refer to a
work where conceptual graphs (CG) are used to describe services in the PhD
thesis of Arno Puder [
As already mentioned, some approaches also propose the integration of
DAMLS descriptions with the UDDI standard, which we have introduced as an
application scenario for the matching algorithm ([
We have shown that individual elements of the DAML-S upper ontology can be used to provide a nfie grained ranking of matching results rather than aflt subsumption reasoning for the service prolfie description as a whole unit. Also this work indicates the potential to provide even nfier grained ranks with considering more elements of DAML-S.
For further research this efild offers many opportunities: we plan to discuss the complexity of the algorithm, and to denfie a procedure for the creation of DAML-S descriptions. Other activities will focus on testing the algorithm to find an optimal weighting of the matching stages, and to identify more relevant elements of DAML-S for matchmaking. As the very next step, this work will be updated with the successor of DAML-S, which is based on OWL.
The authors wish to thank Kurt Geihs, and Gregor Rojec-Goldmann for many fruitful discussions.