Semantics-based composition-oriented discovery of Web services

ABSTRACT

Service discovery and service aggregation are two crucial issues in the emerging area of service-oriented computing (SOC). We propose a new technique for the discovery of (Web) services that accounts for the need of composing several services to satisfy a client query. The proposed algorithm makes use of OWL-S ontologies, and explicitly returns the sequence of atomic process invocations that the client must perform in order to achieve the desired result. When no full match is possible, the algorithm features a flexible matching by returning partial matches and by suggesting additional inputs that would produce a full match.

REFERENCES

• 1: Akkiraju, R., Farrell, J., Miller, J., Nagarajan, M., Schmidt, M.-T., Sheth, A., and Verma, K. 2005. Web service semantics—WSDL-S technical note (version 1.0). http://lsdis.cs.uga.edu/library/download/WSDL-S-V1.pdf.
• 2: Álvares, P., Bañares, J., and Ezpelata, J. 2005. Approaching Web service coordination and composition by means of petri nets. The case of the nets-within-nets paradigm. In Proceedings of the International Conference on Service-Oriented Computing (ICSOC). Lecture Notes in Computer Science, vol. 3826, Springer, 185--197.
• 3: Andrews, T., Curbera, F., Dholakia, H., Goland, Y., Klein, J., Leymann, F., Liu, K., Roller, D., Smith, D., Thatte, S., Trickovic, I., and Weerawarana, S., 2003. Business process execution language for Web services (version 1.1). http://www-106.ibm.com/developerworks/library/ws-bpel.
• 4: Lerina Aversano , Gerardo Canfora , Anna Ciampi, An Algorithm for Web Service Discovery through Their Composition, Proceedings of the IEEE International Conference on Web Services, p.332, June 06-09, 2004 [doi>10.1109/ICWS.2004.23]
• 5: Bansal, S. 2002. Matchmaking of Web services based on the DAML-S service model. Master thesis. University of South Carolina.
• 6: Sharad Bansal , Jose M. Vidal, Matchmaking of web services based on the DAML-S service model, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860728]
• 7: Battle, S., Bernstein, A., Boley, H., Grosof, B., Gruninger, M., Hull, R., Kifer, M., Martin, D., McIlraith, S., McGuinness, D., Su, J., and Tabet, S. 2005. Semantic Web service ontology (SWSO). W3C member submission. http://www.w3.org/Submission/SWSF-SWSO/.
• 8: Benatallah, B., Hacid, M.-S., Rey, C., and Toumani, F. 2003. Request rewriting-based Web service discovery. In Proceedings of the International Symposium on Wearable Computers (ISWC). Lecture Notes in Computer Science, vol. 2870. Springer, 242--257.
• 9: Rachid Hamadi , Boualem Benatallah, A Petri net-based model for web service composition, Proceedings of the 14th Australasian database conference, p.191-200, February 01, 2003, Adelaide, Australia
• 10: Berardi, D., Calvanese, D., Giacomo, G. D., and Mecella, M. 2005. Composition of services with nondeterministic observable behaviour. In Proceedings of the International Conference on Service-Oriented Computing (ICSOC). Lecture Notes in Computer Science, vol. 3826. Springer, 520--526.
• 11: Berners-Lee, T., Hendler, J., and Lassila, O. 2001. The semantic Web. Sci. Amer.
• 12: Andrea Bracciali , Antonio Brogi , Carlos Canal, A formal approach to component adaptation, Journal of Systems and Software, v.74 n.1, p.45-54, January 2005 [doi>10.1016/j.jss.2003.05.007]
• 13: Brogi, A., Corfini, S., and Popescu, R. 2005. Composition-oriented service discovery. In Software Composition, Lecture Notes in Computer Science 3628, T. Gschwind et al., Eds., Springer, 15--30.
• 14: Luca de Alfaro , Thomas A. Henzinger, Interface automata, Proceedings of the 8th European software engineering conference held jointly with 9th ACM SIGSOFT international symposium on Foundations of software engineering, September 10-14, 2001, Vienna, Austria
• 15: de Bruijn, J., Bussler, C., Domingue, J., Fensel, D. Hepp, M., Keller, U., Kifer, M., Kõnig-Ries, B., Kopecky, J., Rubin, L., Lausen, H., Oren, E., Polleres, A., Roman, D., Scicluna, J., and Stollberg, M. 2005. Web service modeling ontology (WSMO) (W3C member submission). http://www.w3.org/Submission/WSMO/.
• 16: Giorgio Gallo , Giustino Longo , Stefano Pallottino , Sang Nguyen, Directed hypergraphs and applications, Discrete Applied Mathematics, v.42 n.2-3, p.177-201, April 27, 1993 [doi>10.1016/0166-218X(93)90045-P]
• 17: Seyyed Vahid Hashemian , Farhad Mavaddat, A Graph-Based Approach to Web Services Composition, Proceedings of the The 2005 Symposium on Applications and the Internet, p.183-189, January 31-February 04, 2005 [doi>10.1109/SAINT.2005.4]
• 18: Kavantzas, N., Burdett, D., and Ritzinger, G. 2004. Web service choreography description language version 1.0. W3C working draft. http://www.w3.org/TR/2004/WD-ws-cdl-10-20040427/.
• 19: Kawamura, T., Blasio, J. D., Hasegawa, T., Paolucci, M., and Sycara, K. 2004. Public deployment of semantic service matchmaking with UDDI business registry. In Proceedings of the 3rd International Semantic Web Conference (ISWC). Lecture Notes in Computer Science, vol. 3298. Springer, 752--766.
• 20: Kifer, M., Lara, R., Polleres, A., Zhao, C., Keller, U., Lausen, H., and Fensel, D. 2004. A logical framework for Web service discovery. In Proceedings of the Workshop on Semantic Web Services: Preparing to Meet the World of Business Applications (ISWC), vol. 119. CEUR Hiroshima, Japan.
• 21: Kochut, K. J. and Yi, X. 2004. Specification and analysis of service oriented distributed systems using coloured petri nets: Models, algorithms and tools. Tech, Rep., University of Georgia, Computer Science Department.
• 22: Kritikos, K. 2005. Extending OWL for QoS-based Web service description and discovery. In Proceedings of the IBM Ph.D. Symposium at the International Conference on Service-Oriented Computing (ICSOC), A. Hanemann, Ed. 73--78.
• 23: Lei Li , Ian Horrocks, A Software Framework for Matchmaking Based on Semantic Web Technology, International Journal of Electronic Commerce, v.8 n.4, p.39-60, Number 4/Summer 2004
• 24: METEOR-S Team. 2004. METEOR-S: Semantic Web services and processes. http://lsdis.cs.uga.edu/projects/meteor-s/.
• 25: Mokhtar, S. B., Georgantas, N., and Issarny, V. 2005. Ad hoc composition of user tasks in pervasive computing environment. In Software Composition. Lecture Notes in Computer Science, vol. 3628, T. Gschwind et al., Eds. Springer.
• 26: Navas-Delgado, I., Sanz, I., Aldana-Montes, J. F., and Berlanga, R. 2005. Automatic generation of semantic fields for resource discovery in the semantic Web. In Proceedings of the 16th International Conference on Database and Expert Systems Applications (DEXA). Lecture Notes in Computer Science, vol. 3588. Springer.
• 27: OWL-S Coalition. 2004. OWL-S 1.1 release. http://www.daml.org/services/owl-s/1.1/.
• 28: Massimo Paolucci , Takahiro Kawamura , Terry R. Payne , Katia P. Sycara, Semantic Matching of Web Services Capabilities, Proceedings of the First International Semantic Web Conference on The Semantic Web, p.333-347, June 09-12, 2002
• 29: Papazoglou, M. and Georgakopoulos, D. 2003. Service-Oriented Computing. Commun. ACM 46, 10, 25--28.
• 30: Rajasekaran, P., Miller, J. A., Verma, K., and Sheth, A. P. 2005. Enhancing Web services description and discovery to facilitate composition. In Semantic Web Services and Web Process Composition. Lecture Notes in Computer Science, vol. 3387, J. Cardoso and A. Sheth, Eds. Springer, 55--68.
• 31: Kaarthik Sivashanmugam , John A. Miller , Amit P. Sheth , Kunal Verma, Framework for Semantic Web Process Composition, International Journal of Electronic Commerce, v.9 n.2, p.71-106, Number 2/Winter 2004-5
• 32: Srinivasan, N., Paolucci, M., and Sycara, K. P. 2004. An Efficient Algorithm for OWL-S Based Semantic Search in UDDI. In Proceedings of the International Workshop on Semantic Web Process Composition (SWSWPC), 96--110.
• 33: UDDI. 2000. The UDDI technical white paper. http://www.uddi.org/.
• 34: W. M. P. van der Aalst , A. H. M. ter Hofstede, YAWL: yet another workflow language, Information Systems, v.30 n.4, p.245-275, June 2005 [doi>10.1016/j.is.2004.02.002]
• 35: W3C. 2001a. Simple object access protocol (SOAP) 1.2 (W3C working draft. 17) Dec. 2001. http://www.w3.org/TR/2001/WD-soap12-part0-20011217/.
• 36: W3C. 2001b. Web service description language (WSDL) 1.1. http://www.w3.org/TR/wsdl.
• 37: Jian Yang, Web service componentization, Communications of the ACM, v.46 n.10, October 2003 [doi>10.1145/944217.944235]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

General Terms:
Algorithms

Keywords:
OWL-S ontologies, Web service composition, Web service discovery, matchmaking algorithms