{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T16:35:23Z","timestamp":1781109323789,"version":"3.54.1"},"reference-count":37,"publisher":"IGI Global Scientific Publishing","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,4,1]]},"abstract":"<p>The ability of web services to build and integrate loosely-coupled systems has attracted a great deal of attention from researchers in the field of the automatic web service composition. The combination of different web services to build complex systems can be carried out using different control structures to coordinate the execution flow and, therefore, finding the optimal combination of web services represents a non-trivial search effort. Furthermore, the time restrictions together with the growing number of available services complicate further the composition problem. In this paper the authors present an optimal and complete algorithm which finds all valid compositions from the point of view of the semantic input-output message structure matching. Given a request, a service dependency graph which represents a suboptimal solution is dynamically generated. Then, the solution is improved using a backward heuristic search based on the A* algorithm which finds all the possible solutions with different number of services and runpath. Moreover, in order to improve the scalability of our approach, a set of dynamic optimization techniques have been included. The proposal has been validated using eight different repositories from the Web Service Challenge 2008, obtaining all optimal solutions with minimal overhead.<\/p>","DOI":"10.4018\/jwsr.2012040101","type":"journal-article","created":{"date-parts":[[2013,1,9]],"date-time":"2013-01-09T15:55:32Z","timestamp":1357746932000},"page":"1-20","source":"Crossref","is-referenced-by-count":28,"title":["An Optimal and Complete Algorithm for Automatic Web Service Composition"],"prefix":"10.4018","volume":"9","author":[{"given":"Pablo","family":"Rodriguez-Mier","sequence":"first","affiliation":[{"name":"University of Santiago de Compostela, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manuel","family":"Mucientes","sequence":"additional","affiliation":[{"name":"University of Santiago de Compostela, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juan C.","family":"Vidal","sequence":"additional","affiliation":[{"name":"University of Santiago de Compostela, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manuel","family":"Lama","sequence":"additional","affiliation":[{"name":"University of Santiago de Compostela, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"2432","reference":[{"key":"jwsr.2012040101-0","doi-asserted-by":"crossref","unstructured":"Aiello, M., Benthem, N., & Khoury, E. (2008, July). Visualizing compositions of services from large repositories. In Proceedings of the 10th IEEE Conference on e-Commerce Technology and the Fifth IEEE Conference on Enterprise Computing, e-Commerce and e-Services (pp. 359-362). Washington, DC: IEEE Computer Society.","DOI":"10.1109\/CECandEEE.2008.149"},{"key":"jwsr.2012040101-1","author":"G.Alonso","year":"2004","journal-title":"Web services: Concepts, architectures and applications"},{"issue":"4","key":"jwsr.2012040101-2","first-page":"247","article-title":"A genetic programming approach to support the design of service compositions.","volume":"21","author":"L.Aversano","year":"2006","journal-title":"International Journal of Computer Systems Science & Engineering"},{"key":"jwsr.2012040101-3","doi-asserted-by":"crossref","unstructured":"Bansal, A., Blake, M. B., Kona, S., Bleul, S., Weise, T., & Jaeger, M. C. (2008). WSC-08: Continuing the Web services challenge. In Proceedings of the 10th IEEE Conference on e-Commerce Technology and the Fifth IEEE Conference on Enterprise Computing, e-Commerce and e-Services (pp. 351-354). Washington, DC: IEEE Computer Society.","DOI":"10.1109\/CECandEEE.2008.146"},{"key":"jwsr.2012040101-4","unstructured":"Burstein, M., Hobbs, J., Lassila, O., Mcdermott, D., Mcilraith, S., & Narayanan, S. \u2026Sycara, K. (2004). OWL-S: Semantic markup for Web services. Retrieved from http:\/\/www.w3.org\/Submission\/OWL-S\/"},{"key":"jwsr.2012040101-5","unstructured":"Christensen, E., Curbera, F., Meredith, G., & Weerawarana, S. (2001). Web Services Description Language (WSDL) 1.1. Retrieved from http:\/\/www.w3.org\/TR\/wsdl"},{"issue":"1","key":"jwsr.2012040101-6","first-page":"76","article-title":"Web service modeling ontology.","volume":"1","author":"J. D.de Bruijn","year":"2005","journal-title":"Applied Ontology"},{"key":"jwsr.2012040101-7","unstructured":"Georgetown University. (2005). Introducing the Web service challenge. Retrieved from http:\/\/ws-challenge.georgetown.edu\/ws-challenge\/TechDetails.htm"},{"key":"jwsr.2012040101-8","unstructured":"Georgetown University. (2008a). Challenge results. Retrieved from http:\/\/cec2008.cs.georgetown.edu\/wsc08\/downloads\/ChallengeResults.rar"},{"key":"jwsr.2012040101-9","unstructured":"Georgetown University. (2008b). WSC results. Retrieved from http:\/\/cec2008.cs.georgetown.edu\/wsc08\/downloads\/WSCResult.pdf"},{"key":"jwsr.2012040101-10","doi-asserted-by":"crossref","unstructured":"Ghafarian, T., & Kahani, M. (2009, July). Semantic web service composition based on ant colony optimization method. In Proceedings of the First International Conference on Networked Digital Technologies (pp. 171-176). Washington, DC: IEEE Computer Society.","DOI":"10.1109\/NDT.2009.5272126"},{"key":"jwsr.2012040101-11","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"jwsr.2012040101-12","doi-asserted-by":"crossref","unstructured":"Hashemian, S., & Mavaddat, F. (2006). A graph-based framework for composition of stateless Web services. In Proceedings of the European Conference on Web Services (pp. 75-86). Washington, DC: IEEE Computer Society.","DOI":"10.1109\/ECOWS.2006.2"},{"key":"jwsr.2012040101-13","doi-asserted-by":"crossref","unstructured":"Hennig, P., & Balke, W.-T. (2010, July). Highly scalable Web service composition using binary tree-based parallelization. In Proceedings of the IEEE International Conference on Web Services (pp. 123-130). Washington, DC: IEEE Computer Society.","DOI":"10.1109\/ICWS.2010.45"},{"key":"jwsr.2012040101-14","unstructured":"Hoffmann, J., Bertoli, P., & Pistore, M. (2007). Web service composition as planning, revisited: In between background theories and initial state uncertainty. In Proceedings of the 22nd National Conference of the American Association for Artificial Intelligence (pp. 1013-1018). Palo Alto, CA: AAAI."},{"key":"jwsr.2012040101-15","doi-asserted-by":"crossref","unstructured":"Jiang, W., Zhang, C., Huang, Z., Chen, M., Hu, S., & Liu, Z. (2010, July). QSynth: A tool for QoS-aware automatic service composition. In Proceedings of the IEEE International Conference on Web Services (pp. 42-49). Washington, DC: IEEE Computer Society.","DOI":"10.1109\/ICWS.2010.38"},{"key":"jwsr.2012040101-16","doi-asserted-by":"crossref","unstructured":"Klusch, M., Gerber, A., & Schmidt, M. (2005). Semantic Web service composition planning with OWLS-Xplan. In Proceedings of the AAAI Fall Symposium on Semantic Web and Agents, Arlington, VA. Palo Alto, CA: AAAI.","DOI":"10.1109\/WI-IATW.2006.68"},{"key":"jwsr.2012040101-17","doi-asserted-by":"crossref","unstructured":"Kona, S., Bansal, A., Blake, M. B., & Gupta, G. (2008, September). Generalized semantics-based service composition. In Proceedings of the IEEE International Conference on Web Services (pp. 219-227). Washington, DC: IEEE Computer Society.","DOI":"10.1109\/ICWS.2008.118"},{"issue":"5","key":"jwsr.2012040101-18","first-page":"1","article-title":"A comparative illustration of AI planning-based Web services composition.","volume":"5","author":"D.Lee","year":"2005","journal-title":"SIGecom Exchanges"},{"key":"jwsr.2012040101-19","doi-asserted-by":"publisher","DOI":"10.4018\/jwsr.2005100103"},{"key":"jwsr.2012040101-20","doi-asserted-by":"publisher","DOI":"10.4018\/jwsr.2006040101"},{"key":"jwsr.2012040101-21","doi-asserted-by":"publisher","DOI":"10.4018\/jwsr.2009092301"},{"key":"jwsr.2012040101-22","doi-asserted-by":"publisher","DOI":"10.4018\/jwsr.2007010101"},{"key":"jwsr.2012040101-23","doi-asserted-by":"crossref","unstructured":"Oh, S., Lee, J.-Y., Cheong, S.-H., Lim, S.-M., Kim, M.-W., & Lee, S.-S. \u2026Sohn, M. M. (2009, July). WSPR*: Web-service planner augmented with A* algorithm. In Proceedings of the IEEE Conference on Commerce and Enterprise Computing (pp. 515-518). Washington, DC: IEEE Computer Society.","DOI":"10.1109\/CEC.2009.13"},{"key":"jwsr.2012040101-24","unstructured":"On, B., & Larson, E. (2005). BF*: Web services discovery and composition as graph search problem. In Proceedings of the IEEE International Conference on e-Technology, e-Commerce and e-Service (pp. 784-786). Washington, DC: IEEE Computer Society."},{"issue":"10","key":"jwsr.2012040101-25","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/944217.944233","article-title":"Service-oriented computing.","volume":"46","author":"M.Papazoglou","year":"2003","journal-title":"Communications of the ACM"},{"key":"jwsr.2012040101-26","doi-asserted-by":"crossref","unstructured":"Pistore, M., Barbon, F., Bertoli, P., Shaparau, D., & Traverso, P. (2004). Planning and monitoring web service composition. In C. Bussler & D. Fensel (Eds.), Proceedings of the 11th International Conference on Artificial Intelligence: Methodology, Systems and Applications (LNCS 3192, pp. 106-115).","DOI":"10.1007\/978-3-540-30106-6_11"},{"key":"jwsr.2012040101-27","doi-asserted-by":"publisher","DOI":"10.1007\/s12065-010-0042-z"},{"key":"jwsr.2012040101-28","doi-asserted-by":"publisher","DOI":"10.4018\/jwsr.2010040105"},{"key":"jwsr.2012040101-29","doi-asserted-by":"crossref","unstructured":"Shiaa, M., Fladmark, J., & Thiell, B. (2008, July). An incremental graph-based approach to automatic service composition. In Proceedings of the IEEE International Conference on Services Computing (pp. 397-404). Washington, DC: IEEE Computer Society.","DOI":"10.1109\/SCC.2008.141"},{"key":"jwsr.2012040101-30","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2004.06.005"},{"key":"jwsr.2012040101-31","author":"S.Weerawarana","year":"2005","journal-title":"Web services platform architecture: SOAP, WSDL, WS-Policy, WS-Addressing, WS-BPEL, WS-Reliable Messaging, and more"},{"key":"jwsr.2012040101-32","doi-asserted-by":"crossref","unstructured":"Weise, T., Bleul, S., Comes, D., & Geihs, K. (2008, June). Different approaches to semantic Web service composition. In Proceedings of the Third International Conference on Internet and Web Applications and Services (pp. 90-96). Washington, DC: IEEE Computer Society.","DOI":"10.1109\/ICIW.2008.32"},{"key":"jwsr.2012040101-33","doi-asserted-by":"crossref","unstructured":"Weise, T., Bleul, S., Kirchhoff, M., & Geihs, K. (2008, July). Semantic Web service composition for service-oriented architectures. In Proceedings of the 10th IEEE Conference on e-Commerce Technology and the Fifth IEEE Conference on Enterprise Computing, e-Commerce and e-Services (pp. 355-358). Washington, DC: IEEE Computer Society.","DOI":"10.1109\/CECandEEE.2008.148"},{"key":"jwsr.2012040101-34","doi-asserted-by":"crossref","unstructured":"Wu, B., Li, Y., Wu, J., & Yin, J. (2011). AWSP: An automatic Web service planner based on heuristic state space search. In Proceedings of the IEEE International Conference on Web Services (pp. 403-410). Washington, DC: IEEE Computer Society.","DOI":"10.1109\/ICWS.2011.20"},{"key":"jwsr.2012040101-35","doi-asserted-by":"publisher","DOI":"10.4018\/jwsr.2011040103"},{"key":"jwsr.2012040101-36","doi-asserted-by":"crossref","unstructured":"Yan, Y., Xu, B., & Gu, Z. (2008). Automatic service composition using AND\/OR graph. In Proceedings of the 10th IEEE Conference on e-Commerce Technology and the Fifth IEEE Conference on Enterprise Computing, e-Commerce and e-Services (pp. 335-338). Washington, DC: IEEE Computer Society.","DOI":"10.1109\/CECandEEE.2008.124"}],"container-title":["International Journal of Web Services Research"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=70387","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T23:48:14Z","timestamp":1654127294000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/jwsr.2012040101"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2012,4,1]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,4]]}},"URL":"https:\/\/doi.org\/10.4018\/jwsr.2012040101","relation":{},"ISSN":["1545-7362","1546-5004"],"issn-type":[{"value":"1545-7362","type":"print"},{"value":"1546-5004","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4,1]]}}}