This document is an extended abstract on a PhD work that develops an e±cient, scalable, and stable Web service discovery engine. These qualities become important for discovery engines that serve as a software component in automated SOA technologies. Based on a profound formal speci¯cation, the approach is to capture design time discovery results and then use this knowledge for e±cient runtime discovery. The work is evaluated by a statistical time e±ciency comparison with other Web service discovery engines, and by a applicability study in realworld SOA applications.
1. pre-¯ltering as only the Web services that are usable for the corresponding goal template are potential candidates for the goal instance, and 2. minimal use of a reasoner for matchmaking because in certain situations the usability of a Web service for a goal instance can be directly inferred.
My work extends the approach for Web service discovery promoted by the WSMO framework with a re¯ned goal model and a rigid formalization for the functional aspects of Web service discovery. On this basis, the so-called Semantic Discovery Caching technique (short: SDC) caches the minimal knowledge in order to optimize the computational qualities of Web service discovery. 2.1
In contrast to an invocation request for a Web service, a goal formally describes a client objective of getting from the current state of the world into a state wherein the objective is satis¯ed. This provides an abstraction layer for facilitating problem-oriented Web service usage: the client merely speci¯es the objective to be achieved as a goal, and the system discovers, composes, and executes suitable Web services for solving this. The distinction of goal templates and goal instances allows to better support the goal formulation by clients (e.g. by form-based instantiation through a graphical user interface), and { more importantly { provides the foundation for the two-phase Web service discovery outlined above.
I consider functional aspects as the primary aspect for discovery: if a Web service does not provide the functionality for solving a goal, then it is not usable and other, non-functional aspects are irrelevant. For this, the possible solution for goals and possible executions of Web services are formally described by functional descriptions D = (§; ; IN ; Ápre; Áe® ); § is the signature, are domain ontologies, IN are the input variables, the precondition Ápre and the e®ect Áe® constraint the start- and end states. As the design time discovery result, the usability of a Web service W for a goal template G is expressed in terms of matching degrees (exact, plugin, subsume, intersect, disjoint ). A goal instance is de¯ned as a pair GI(G) = (G; ¯) with the corresponding goal template G and an input binding ¯ that is used to invoke a Web service W for solving GI(G). If W is usable for G under the degrees exact or plugin, then W is also usable for any GI(G); under the degrees subsume and intersect, additional matchmaking is required at runtime; if W is not usable for G it is also not usable for GI(G). 2.2
The main contribution of my work is the SDC technique as the solution for enabling e±cient, scalable, and stable Web service discovery. Its purpose is to improve the computational quality of the runtime discovery process by exploiting the relationships between goal templates, goal instances, and Web services.
The central element is the SDC Graph that provides an index structure for e±cient search of goal templates and usable Web services. It organizes goal templates with respect to their semantic similarity, and keeps the minimal knowledge on the usability of the available Web services. Two goal templates Gi and Gj are considered to be similar if they have at least one common solution; if this is given, then mostly the same Web services are usable for them. In consequence, the upper layer of a SDC graph is the goal graph that organizes goal templates in a subsumption hierarchy, and the lower layer is the usability cache that captures the minimal knowledge on the usability of the available Web services. Upon this cache structure, the discovery operations make use of inference rules between the similarity degree of goal templates and the usability degree of Web services.
For illustration, Figure 2 shows an example of an SDC graph along with the most relevant inference rules. This considers three goal templates: G1 for package shipment within Europe, G2 for Switzerland, and G3 for Germany. As each solution for G2 is also a solution of G1, their similarity degree is subsume; the same holds between G3 and G1. These relationships are expressed by directed arcs in goal graph. Besides the goal templates, let there be some Web services, among them e.g. W1 that provides package shipment within Europe, W2 throughout the whole world, W3 within the European Union, and W4 within the Commonwealth. Their usability degree for each goal template is explicated by directed arcs in the usability cache. This knowledge is e±ciently used for runtime discovery. Consider a goal instance for shipping a package from Munich to Berlin: its corresponding goal instance is G3; because W1, W2, and W3 are usable for G3 under the plugin degree, we know that each of them is usable for solving the goal instance without the need of a matchmaker during runtime discovery. Structure of an SDC Graph inference rules for subsume(G1; G2) (1) exact(G1; W ) ) plugin(G2; W ): (2) plugin(G1; W ) ) plugin(G2; W ): (3) subsume(G1; W ) ) exact(G2; W ) or (4) subsume(G1; W ) ) plugin(G2; W ) or (5) subsume(G1; W ) ) subsume(G2; W ) or (6) subsume(G1; W ) ) intersect(G2; W ) or (7) subsume(G1; W ) ) disjoint(G2; W ): (8) intersect(G1; W ) ) plugin(G2; W ) or (9) intersect(G1; W ) ) intersect(G2; W ) or (10) intersect(G1; W ) ) disjoint(G2; W ): (11) disjoint(G1; W ) ) disjoint(G2; W ):
The SDC graph during its life time are maintained by algorithms that handle the addition, removal, and modi¯cation of goal templates and Web services. Two re¯nements ensure that the SDC graph exposes sophisticated search properties: (1) the only similarity degree that occurs in the goal graph is subsume, and (2) the minimization of the usability cache in order to avoid redundancy. The SDC technique is implemented as a discovery component of the WSMX system, available at the SDC homepage: members.deri.at/»michaels/software/sdc/. 3
To demonstrate the achievable quality increase for Web service discovery, I have run several comparison test between the SDC-enabled runtime discovery and an engine that applies the same matchmaking techniques but does not make use of the cached knowledge. Table 1 shows a snapshot of the statistical prepared test results; details and the original test data are available from SDC homepage. This clearly shows that the SDC discovery is e±cient (the average time is always lower), scalable (the time for the SDC discovery remains the same for increasing numbers of Web services), and stable (the standard deviation is signi¯cantly smaller than the one of the comparison engine).
Another relevant aspect is the appropriateness of the assumptions that underly the conceptual model. For this, I have examined the applicability in realworld settings { e.g. in one of the world's largest SOA systems at telecommunication provider Verizon. In summary, there are many Web services that provide similar functionalities but di®er in the detailed usage conditions. Also, the usage requests posted by the consuming applications can be expressed in terms of goals; these can be organized in a ¯ne-grained subsumption hierarchy in the SDC graph so that its bene¯ts for e±cient runtime discovery can be exploited. Besides, the distinction of goal templates and goal instances has been regarded by practioneers as suitable way for realizing problem-oriented Web service usage. No. of WS 10
Very few existing works address the computational quality of Web service discovery techniques. I am not aware of any other approach that addresses this problem in a similar way. The following outlines the relationship to related research ¯elds; details are discussed in the publications listed below.
Semantic Web Service Discovery. Most works are only concerned with the matchmaking techniques. As a contribution to this end, my work is based on a formal model that describes requested and provided functionalities on the level of executions of Web services and solutions for goals (cf. Section 2).
Web Service Repository Indexing. Other approaches reduce the search space for discovery by indexing Web service repositories. Keyword-based categorization as already supported by UDDI is imprecise in comparison to the SDC graph. More sophisticated solutions create a search tree based on formal descriptions; this can achieve logarithmic search time, but { in contrast to SDC { still requires several matchmaking operations for each request.
Caching. Caching techniques are a well-established means for performance increase in several areas of computing. Respective studies show that caching can achieve the highest e±ciency increase if there are many similar requests. The SDC graph can be understood as a cache structure for Web service discovery.
Scalable Ontology Repositories. Works on scalable ontology reasoning infrastructures minimize the reasoning e®ort at runtime, e.g. by materalization and organization of the available knowledge at design time. However, such techniques can not replace the SDC technique because it de¯nes a speci¯c knowledge structure and algorithms for Web service discovery.
Stollberg, M. and Norton, B.: A Re¯ned Goal Model for Semantic Web Services. In Proc. of the 2nd International Conference on Internet and Web Applications and Services (ICIW 2007), Mauritius, 2007.
Stollberg, M.; Keller, U.; Lausen, H. and Heymans, S.: Two-phase Web Service Discovery based on Rich Functional Descriptions. In Proc. of the 4th European Semantic Web Conference (ESWC 2007), Innsbruck, Austria, 2007.
Stollberg, M.; Hepp, M., Ho®mann, J.: E±cient and Scalable Web Service Discovery with Caching. Submitted to 6th International Semantic Web Conference (ISWC 2007).