- Semantic Web services provide semantically enhanced service descriptions which allow the development of automated service discovery and composition. Yet, an efficient semantic-based service discovery remains a major open challenge towards a wide acceptance of semantic Web services. In this paper we present a fully-automated matchmaking system for discovering sets of OWL-S Web services capable of satisfying a given client request.
Web services are internet-based, self-describing and
platform-independent application components published using
standard interface description languages (WSDL [
The only accepted standard for service discovery is UDDI
[
The development of semantics-based service discovery mechanisms constitutes a major open challenge in this context, and it raises several important issues. One of them is the ability of coping with different ontologies, as different services are typically described in terms of different ontologies. Another important feature is the capability of discovering service compositions rather than single services. Indeed it is often the case that a client query cannot be fulfilled by a single service, while it may be fulfilled by a suitable composition of services. Last, but not least, efficiency is obviously an important objective of service discovery mechanisms.
In this perspective, we described in [
In this paper we develop the methodology proposed in [
The rest of the paper is organised as follows. Sections II and III are devoted to present the discovery system. In Section II we define the data structure we use to collect information about ontology concepts, services and their dependencies, while in Section III we describe the search algorithm for discovering Web service compositions. A first prototype of the discovery system is presented in Section IV. Finally, related work is discussed in Section V, while some concluding remarks are drawn in Section VI.
In order to store the knowledge derived from the preprocessing of ontologies and service descriptions, we need a data structure capable of suitably representing service and data dependencies. The hypergraph seems to be a good candidate as dependencies can be naturally modelled by means of hyperedges.
According to [
In this context, the vertices of the hypergraph correspond to the concepts defined in the ontologies employed by the analysed service descriptions, while the hyperedges represent relationships among such concepts. More precisely, an hyperedge has one of the following three types: • E⊂ = (D, {c}, nil) – subConceptOf relationship. Let c be a concept defined in an ontology O and let D ∈ O be the set of the (direct) subconcepts of c. Then, there is a E⊂ hyperedge from D to c. • E≡ = ({e}, {f }, sim) – equivalentConceptOf relationship. Let e, f be two concepts defined in two separate ontologies and let sim be the similarity between e and f , i.e., the probability that e is (semantically) equivalent to f . If sim is above a given similarity threshold, there is a E≡ hyperedge from e to f labelled by sim. • ES = (I, O, s) – intra-service dependency . Let s be (a profile of) a service and let I be the set of inputs that s requires to produce the set O of outputs. Then, there is a ES hyperedge from I to O labelled by s.
It is worth noting that the proposed hypergraph automatically models other important aspects regarding the registrypublished services and ontologies. The hypergraph models an extended notion of subConceptOf between two concepts c, d defined in two given ontologies. More specifically, c is subConceptOf d (hereafter, c 7→ d) if and only if there exists a path from c to d which consists of subConceptOf relationships (E⊂ hyperedges) and/or equivalentConceptOf relationships (E≡ hyperedges). Moreover, the hypergraph directly represents the inter-service dependencies . Indeed, there is a interservice dependency between two services s and t if the head of a s-labelled ES hyperedge and the tail of a t-labelled ES hyperedge share (at least) a concept. Note that there is a interservice dependency between s and t also if there exist two concepts cs and ct such that cs 7→ ct, cs belongs to the head of the s-labelled ES hyperedge and ct belongs to the tail of the t-labelled ES hyperedge.
In the following subsections we describe how subConceptOf relationships, equivalentConceptOf relationships and intraservice dependencies can be determined.
Semantic Fields [
In order to build Semantic Fields, namely to find relationships between ontologies, we firstly compute the similarity between pairs of concepts and next we calculate the distance between pairs of ontologies (i.e., how similar two ontologies are). Mappings between concepts can be determined by means of different ontology matching tools, which check whether two concepts are equivalent with a given probability.
Since the results depend on the employed matching tools,
we have hence developed a framework for adapting existent
matching tools and combine them in order to improve the
obtained results. In the framework instance used in this paper
we combine the results of individual matchers which
analyses the similarity between pairs of concepts with different
strategies: (1) name similarity: compares the names of the
provided concepts, (2) data type similarity: compares the
types of the provided concepts, and establishes a similarity
value depending on the possibility of producing each type
from another type by casting, (3) WordNet similarity: checks
whether the two concepts are synonyms in WordNet [
The calculus of mappings is done between pairs of ontologies, hence if we have N ontologies then we have to calculate N 2 − N matrixes. Assuming that the mapping between two ontologies is a symmetric relationship we need to calculate (N 2 − N )/2 matrixes. Yet, our tool calculates the similarity matrixes between the new ontology and all the previously published ontologies when the new one is registered. Thus, each insertion only requires N − 1 calculations.
Once the mappings between two different ontologies are established, the distance between the ontologies is calculated by making use of some ontology distance measurements. Given a matrix with the similarity between pairs of concepts of two ontologies (O1 and O2), we can make use of several measurements based on the definitions of distance in different contexts. First, we define the directed distance (DD) between them (as it is an asymmetric measure):
DD(O1, O2) = Pc∈Concepts(O1) max(mappings(c, O2)) #Concepts(O1)
D(O1, O2) = min(DD(O1, O2), DD(O2, O1))
We can calculate the distance (which is a symmetric measure) between two ontologies (D) in different ways (see for example the second formula) depending on the distance concept used. These measures allow us to establish how similar two ontologies are, and in this way to know whether it will be necessary to include the already calculated similarities between their concepts to solve the problem of determining the user Semantic Field.
Let us suppose that we have the set of registered ontologies in Figure 1, in which the edge values mean the already calculated distance between pairs of ontologies. Let us assume that the user selects the EconomyDomain ontology, which covers his intended domain, and sets up a distance threshold of 2. In this example the Semantic Field will be composed of the ontologies at a distance less than this value, which are those included in the dotted rectangle of Figure 1, i.e., event, hotel and e-commerce .
Semantic Fields have been implemented as a configurable tool1 (SemFiT) which can be used directly through a Web Service or Web forms for registered users. The Semantic Field Tool suitably configured to be employed by the matchmaking algorithm provides the following methods: • startSession() returns an identifier for the user session, which will be necessary in other methods; • insertOntology(string ontologyU RI, int sessionId) inserts a new ontology (if not already present) in the user session. This process includes the calculation of the mappings and distances among the inserted ontology and all the ontologies previously inserted. This calculation implies the use of the framework for ontology matching, and creating a set of similarity matrixes which contain the similarity between concepts of pairs of ontologies (a value between 0 and 1 indicating the probability of two concepts of being the same semantic concept); • getOntologies(int sessionId)
returns the ontologies which belong to the user session; • searchEquivalentConcepts(string concept, string ontologyU RI, float minSimilarity, int sessionId) taking into account the user Semantic Field (the ontologies in which he/she is interested in) this method analyses the similarity matrixes (between pairs of ontologies in his/her Semantic Field) for finding relationships between concepts. Concepts with a similarity value greater that minSimilarity are considered equivalent concepts; • searchParentsForConcept(string ontologyU RI, string concept, int sessionId) searches in the ontology hierarchy for parents of the given concept, returning a set of vectors with concept, ontology and similarity value. Since the search of hierarchical relationships is a time consuming task, the hierarchy is precalculated from the OWL file by means of the Jena2 parser and stored in an internal database of SemFiT; • searchChildrenForConcept(string ontologyU RI, string concept, int sessionId) searches in the ontology hierarchy for children of the given concept, returning a set of vectors with concept, ontology and similarity value. This method makes use of the pre-calculated hierarchy as well.
As described above, an intra-service dependency is a hyperedge connecting two sets of nodes, respectively representing the inputs and the outputs of a service. Yet, a service may behave in different ways and features different functionalities. Consider, for instance, a simple service s which inputs a and produces as output b or c (i.e., a choice process). s can behave in two different ways, namely, as a service s1 which inputs a and yields b and as a service s2 which inputs a and yields c. Hence s exposes two different profiles, which correspond to the different intra-service dependencies ( {a}, {b}, s1) and ({a}, {c}, s2).
The intra-service dependencies of an OWL-S described service can be determined by analysing its process model, which details the complete behaviour of the service. We present next the recursive function DataDep, initially invoked over the root composite process of a service s, which determines all the intra-service dependencies ( I, O) of s.
• DataDep(atomic(A)) = {(A.inputs, A.outputs)}; • DataDep(ifThenElse(P1, P2)) = {(I1, O1)|(I1, O1) ∈ DataDep(P1)} ∪
{(I2, O2)|(I2, O2) ∈ DataDep(P2)} • DaStaDep(choice(P1, ..., Pk))
= ik=1 {(I, O)|(I, O) ∈ DataDep(Pi)} • DataDep(sequence(P1, ..., Pk)) = DataDep(split(P1, ..., Pk)) = DataDep(split+join(P1, ..., Pk)) = DaStaDep(aSny-order (P1, ..., Pk)) = {( ik=1 Ii, ik=1 Oi)|(Ii, Oi) ∈ DataDep(Pi)} • DataDep(iterate(P )) = DataDep(choice(P , sequence(P, P ), ..., sequence(P, ..., P ))) | {z }
Alt(P )
Before defining Alt(P ), we need to specify some assumptions. The proposed algorithm for discovering semantic Web services works on ontology types. As a consequence, the algorithm checks whether an output (i.e., a type) can be produced by some available service, while it does not take care of how many times such output can be produced. This assumption allows us to expand the iterate process into a choice of sequences, where each sequence is a possible iterated execution of P . Alt(P ), which is defined below, computes how 1available at http://khaos.uma.es/semanticfields/ 2http://jena.sourceforge.net/ many times the process P has to be executed in order to yield all the outputs producible by its atomic process children. • Alt(atomic(A)) = 1 • Alt(ifThenElse(P1, P2)) = Alt(P1) + Alt(P2) • Alt(choice(P1, ..., Pn)) = Alt(P1) + ... + Alt(Pn) • Alt(sequence(P1, ..., Pn)) = Alt(any-order (P1, ..., Pn)) = Alt(split(P1, ..., Pn)) = Alt(split+join(P1, ..., Pn)) = max(Alt(P1), ..., Alt(Pn)) • Alt(iterate(P )) = 0
Let us consider, for example, the HotelService, whose root is a repeat-until composite process, illustrated in Figure 2. Alt(chooseOperation) returns two, indeed, chooseOperation has to be executed twice in order to yield all the outputs producible by its children. Hence, DataDep(HotelService) returns three profiles: H1, which inputs {state, city} and produces {infoHotel}, H2, which inputs {hotel, beginDate, lastDate, creditCard, contactInformation} and produces {accomodationFee, hotelInvoice}, and H3, which inputs {state, city, hotel, beginDate, lastDate, creditCard, contactInformation} and produces {infoHotel, accomodationFee, hotelInvoice}.
Note that DataDep is a recursive function and that if an iterate process has an iterate-typed ancestor Q, DataDep first expands Q and then P . That is why we set Alt(iterate(P )) = 0 in the pseudocode above. It is also worth observing that the definition of DataDep(iterate(P )) is suitable when P has to be executed at least one (i.e., iterate instantiated as repeat-until ) as well as when P may be skipped (i.e., iterate instantiated as repeat-while ). In the latter case, the definition of DataDep(iterate(P )) has to be expanded by adding a nop branch to the choice among all possible iterate executions of P .
After describing how data and service dependencies are determined, we can introduce in this subsection the AddService function, which updates the hypergraph whenever a new service s is added to the registry.
Generally speaking, AddService firstly adds to the hypergraph the concepts defined in the ontologies employed by s and next, it draws the hyperedges representing the subConceptOf relationships, the equivalentConceptOf relationships and the intra-service dependencies between the newly added ontology concepts. Note that AddService does not affect the efficiency of the matching process, as the hypergraph construction is completely query independent and can be precomputed off-line before query time.
The behaviour of AddService can be summarised by the following pseudo-code, where sessionID is the session number assigned to AddService by the startSession method of SemFiT. 1. AddService(hypergraph H = (V, E), service s, int sessionID) 2. forall ontology O ∈/ getOntologies(sessionID) referred by s do 3. insertOntology(O, sessionID); 4. forall concept c in O do 5. Add c to V ;
For each ontology O employed by s (line 2), the AddService inserts O (if not already present) into the Semantic Field identified by sessionID (line 3). Next, for each concept c ∈ O (line 4), it adds c to the hypergraph (line 5) and determines the (possibly empty) sets of the parents and children of c by invoking the searchParentsForConcept and searchChildrenForConcept methods of the SemFiT. Then, for each parent a of c (line 6), AddService adds (if a ∈ V ) a E⊂ hyperedge (c, a, nil) to E (lines 7–9), while for each child concept b of c (line 10), it inserts (if b ∈ V ) a E⊂ hyperedge (b, c, nil) to E (lines 11–13). Next, it determines the (possible empty) set of the equivalent concepts of c by invoking the searchEquivalentsForConcept method of SemFiT, which returns those concepts above a given similarity threshold, i.e., the minSimilarity parameter. For each equivalent concept e of c (lines 14–15) AddService adds to E (if e ∈ V ) the two E≡ hyperedges (c, e, similarity) and (e, c, similarity) (lines 16– 18). Note that all the concepts in the ontologies employed by s will be included in the hypergraph, independently of whether they directly occur in the specification of (some process in) s. Finally, AddService inserts to the hypergraph a ES hyperedge (In, On, sn) for each intra-service dependency returned by DataDep (namely, for each profile n of s) (lines 19–20).
We present next an example which illustrates the behaviour of the AddService function. Let us consider an empty registry where we want to add two OWL-S described services: HotelService, which allows a client to search for and/or to reserve hotels, and ConferenceService, which allows a client to register to academic events. Their process models, which employ three different ontologies (hotel, e-commerce and event), are shown in Figure 2.
Let us consider first the HotelService. AddService inserts to the hypergraph all the concepts defined in the hotel and e-commerce ontologies (the light gray and dark gray ellipses in Figure 3) together with the subConceptOf and the equivalentConceptOf relationships returned by SemFiT. Note, for example, the subConceptOf relationships between hotel#city and hotel#physicalLocation, and between e-commerce#creditCard and e-commerce#paymentMethods as well as the equivalentConceptOf relationships between e-commerce#invoice and hotel#invoice. At this point, the AddService inserts also the intra-service dependencies of HotelService computed by the DataDep function, i.e., the ES hyperedges H1, H2 and H3 in Figure 3. Next, also ConferenceService is added to the registry. AddService inserts to the hypergraph the concepts defined in the event ontology, the subConceptOf and equivalentConceptOf relationships computed by SemFiT, as well as the intra-service dependencies of ConferenceService. The resulting hypergraph is shown in Figure 3.
It is worth observing that some of the equivalentConceptOf relationships found by SemFiT appear due to the similarity between the syntax of the compared concepts (e-commerce#invoice – hotel#invoice, hotel#physicalLocation – event#location and hotel#city – event#city), while other mappings are the result of applying searches in wordNet (e.g., event#startDate – hotel#beginDate and event#endDate – hotel#lastDate). In this last case, the similarity does not derive from direct synonyms in wordNet, but from the tokens that compose the words. Finally, event#dateTime and hotel#date are similar because of their syntax and their structure (both have children that have same similarity).
The discovery algorithm takes as input a client query specifying the set of inputs and outputs of the desired service (composition). As we will describe in Section IV, the formulation of the query is eased by a suitable interface that displays the available concepts with an expandable tree structure. Next, the search algorithm explores the hypergraph, by performing a depth-first visit, in order to discover the (compositions of) services capable of satisfying the client request.
The discovery algorithm is synthesised by the following recursive function QuerySolver which inputs five parameters: the hypergraph H, the client query Q, the set composition of the services selected so far (initially empty), the set neededOutput of the outputs to be generated (initially the query outputs), and the set availableOutput of the outputs available (initially the query inputs).
In the pseudo-code listed below, Input(s) denotes the inputs of the service s, that is, the set {i|∃(I, O, s) ∈ ES ∧ i ∈ I} as well as Output(s) denotes the outputs of s, namely {o|∃(I, O, s) ∈ ES ∧ o ∈ O}. We also remind you that 7→ denotes the extended subConceptOf relationship. 1. QuerySolver(hypergraph H, query Q, set composition, 2. set neededOutput, set availableOutput) 3. if (neededOutput = ∅) then return composition 4. else 5. out = extract(neededOutput); 6. S = {s|out ∈ Output(s) ∨ (∃c ∈ Output(s)|c 7→ out)}; 7. if (S = ∅) then fail 8. else 9. forall service s in S do 10. composition0 = composition ∪ {s}; 11. availableOutput0 = availableOutput ∪ Output(s); 12. neededOutput0 = {x|x ∈ neededOutput ∪ Input(s) 13. ∧ @a ∈ availableOutput0 : 14. a = x ∨ a 7→ x}; 15. QuerySolver(H, Q, composition0, 16. neededOutput0, availableOutput0);
If neededOutput = ∅, i.e., there are no outputs to be generated, QuerySolver returns the set composition of the services found (line 3), which satisfies the functional client query. Otherwise (line 4) QuerySolver withdraws an output out from the set neededOutput (line 5) and computes the set S of the services which produce (a sub concept of) out (line 6). If S is empty, that is, out cannot be generated by any registrypublished service, then QuerySolver fails (line 7) since the query cannot be fulfilled. Otherwise (line 8) for each service s which generates (a sub concept of) out (line 9), QuerySolver adds s to composition (line 10), updates availableOutput by adding the outputs of s (line 11), and updates neededOutput by adding the inputs of s and by removing the concepts that are now available (lines 12–14). Next, QuerySolver continues recursively (lines 15–16).
The complexity of QuerySolver belongs to the N P space as it determines all the possible solutions by visiting the hypergraph non-deterministically. We have tested QuerySolver on a small repository containing ten services only, as there are few available SWSs on the Web as the SWS area is emerging now. Anyway, the average reply-time of QuerySolver is 0.2 seconds. We imagine that in the future many SWSs will exist, thus, we intend to improve efficiency by operating in the following directions: • to reduce the large number of services taken into account by the QuerySolver by introducing a suitable service pre-selection phase (e.g., using UDDI to filter services not belonging to certain service categories), and by selecting services which produce a needed output with respect to some heuristics (e.g., the number and/or on the quality of the produced outputs) in order to consider the “most promising” services only. • to introduce caching and indexing techniques in order to sensibly decrease the QuerySolver reply-time.
Let us continue the example introduced in subsection IID. Consider now a client wishing to plan its participation in an international conference by registering to the conference and by booking his hotel accomodation, and receiving the conference and hotel confirmations. The client query may be composed by the following parameters: • inputs – hotel#hotel, event#internationalConference, e-commerce#creditCard , e-commerce#contactInformation • output – e-commerce#invoice , e-commerce#registrationReceipt.
As one may note, neither HotelService nor ConferenceService satisfies the given query by itself. Yet, the query can be fulfilled by suitably composing the two available services. QuerySolver takes as parameters the hypergraph depicted in Figure 3, the query inputs (i.e., availableOutput) and the query outputs (i.e., neededOutput), while composition is an empty set. Suppose that QuerySolver withdraws e-commerce#invoice from neededOutput. QuerySolver creates two compositions, represented by the hyperedges {H2} and {H3} respectively, as the profiles {H2} and {H3} of HotelService both produce hotel#hotelInvoice, which is a subConceptOf e-commerce#invoice (i.e., the former is linked to the latter by means of E⊂ and E≡ hyperedges). Consider composition {H2}. QuerySolver adds to neededOutput hotel#beginDate and hotel#lastDate, since they do not belong to the query inputs. Suppose that, at its second invocation, QuerySolver withdraws e-commerce#registrationReceipt from neededOutput, which is produced by both the profiles C1 and C2 of ConferenceService. QuerySolver creates then the following compositions: {H2, C1} and {H2, C2}. While the first one fulfills the query, as all the needed outputs are now available, the second one fails, as e-commerce#bankAccount cannot be produced by any registry-published service. When all instances of QuerySolver terminate, the functional analyser returns to the client two successful compositions: {H2, C1} and {H3, C1}.
Figure 4 presents the high-level architecture of SAM. AddService and QuerySolver are Java applications which implement the AddService function (Subsection II-C) and the discovery algorithm (Section III). AddService makes use of the CMU OWL-S API 3 for parsing OWL-S descriptions. 3http://www.daml.ri.cmu.edu/owlsapi/
is the local repository where SAM stores service descriptions, ontologies and the dependency hypergraph (Section II). A JDBC-ODBC bridge allows the Java applications to access the repository, implemented as a relational (MS Access, for this first prototype) database. It is worth noting that we do not introduce Java classes to represent ontologies, profiles, concepts and dependencies in order to avoid loading in memory space-consuming Java objects. Indeed, AddService and QuerySolver perform ontological reasoning and hypergraph handling by means of database invocations. As described in Subsections II-A and II-C, the Java Semantic Field Application (i.e., SemFiT) supports AddService to process ontologies and data dependencies.
Finally, we have provided SAM with a suitable Web interface, which allows clients to submit a new service to the system as well as to query the discovery algorithm. Figure 5 shows a screenshot of the system interface. In its left panel the interface provides a tree view of the available ontologies to help the client in specifying its query. The input and output concepts selected by the client are shown in the query inputs and query outputs panels on the right part of the interface. By clicking on the Submit query button, the client queries the discovery algorithm which returns the result in the bottom panel of the interface. Moreover, the client can submit a new service to the system by means of the Submit service button, after providing the service URL.
AddService and QuerySolver are Java servlets which run on Apache Tomcat. To develop the Web interface we employed the Google Web Toolkit, which is a Java development framework that allows to deploy AJAX applications and complex Web interfaces by using the Java language. Google Web Toolkit then translates the Java code to browser-compliant JavaScript and HTML.
Figure 5 catches the Web interface as it appears after submitting the query described in Subsection III-A. Indeed, the results panel lists the two successful compositions which satisfy the example query. Note the result syntax [S1(P11 , . . . , P1n1 ), . . . , Sn(Pn1 , . . . , Pnnn )] where Si denotes the service name and Pi1 , . . . , Pini denote the atomic processes of the selected profile of Si.
The discovery of semantic Web services has been firstly
addressed by Paolucci et al. in [
In [
Moreover, it is worth mentioning the METEOR-S project
[
As composing services requires to cope with different
ontologies, several other works have been recently proposed
to address the issues of ontology merging and alignment. For
instance, it is worth mentioning [
In this paper, we have presented a new fully-automated matchmaking system for discovering (compositions of) OWLS semantic Web services capable of satisfying a given client request. The proposed system is the first one – at the best of our knowledge – that addresses three main issues of the semantic service discovery domain, namely, compositionoriented discovery, crossing different ontologies and efficiency. We have also presented a first Web-accessible prototype of our discovery system.
Our plan for future work includes the development of fresh
indexing and/or ranking techniques (as search engines do
for Web pages) in order to sensibly improve the efficiency
of our system. A second line of our future work is to
enhance our discovery system by employing a behavioural
analyser module, which analyses the behavioural information
advertised in the (OWL-S) service descriptions to determine
whether the candidate services (selected by the functional
analyser) can really be composed together and satisfy the
query without dead-locking, in the line of [