A Logical Reasoning Approach to Automatic Composition of Stateless Components

• Autorzy: Hashemian S.V. , Mavaddat F.
• Języki publikacji: EN

Abstrakty

EN

Reusing available software components in developing new systems is always a priority, as it usually saves a considerable amount of time, money, and human effort. Since it might not always be possible to find a single component that provides the sought functionality, an ideal scenario for software reuse would be to build a new software system by composing existing components based on their behavioral properties. In this paper we take advantage of logical reasoning to find a solution for automatic composition of stateless components. Stateless components are components with a simple two step behavior: they receive all their inputs at the same time, and then return the corresponding outputs also at the same time. We provide concrete algorithms to find possible component compositions for a requested behavior. We then validate the returned compositions using composition algebraic rules. Composition algebra is a minimal process algebra that is specifically designed for this validation. In order to understand the functionality of the proposed approach in realistic situations, we also study some of the experimental results obtained by implementing the algorithm and running it on some test cases.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 89, nr 4
• Strony: 539--577
• Opis fizyczny: bibliogr. 39 poz., tab., wykr.

Twórcy

autor

Hashemian S.V.

autor

Mavaddat F.

• David R. Cheriton School of Computer Science University of Waterloo Waterloo, Ontario, Canada,

Bibliografia

• [1] Aiello, M., Papazoglou, M. P., Yang, J., Carman, M., Pistore, M., Serafini, L., Traverso, P.: A Request Language for Web-Services Based on Planning and Constraint Satisfaction, TES '02: Proceedings of the Third International Workshop on Technologies for E-Services, Springer-Verlag, 2002.
• [2] de Alfaro, L., Henzinger, T.: Interface automata, Proceedings of the 8th European Software Engineering Conference held jointly with 9th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/SIGSOFT FSE), 2001.
• [3] Andrews, T., Curbera, F., Dholakia, H., Goland, Y., Klein, J., Leymann, F., Liu, K., Roller, D., Smith, D., Thatte, S., Trickovic, I., Weerawarana, S.: Business Process Execution Language for Web Services (Version 1.1), http://tinyurl.com/odlpa, 2003.
• [4] Aydoğan, R., Zirtiloğlu, H.: A Graph-Based Web Service Composition Technique Using Ontological Information, ICWS '07: Proceedings of the 2007 IEEE International Conference onWeb Services, IEEE Computer Society, 2007.
• [5] Banks, J., Carson, J. S., Nelson, B. L., Nicol, D. M.: Discrete-Event System Simulation (3rd Edition), Prentice Hall, 2000.
• [6] ter Beek, M., Bucchiarone, A., Gnesi, S.: A Survey on Service Composition Approaches: From Industrial Standards to Formal Methods, Technical report, 2006.
• [7] ter Beek, M., Bucchiarone, A., Gnesi, S.: Formal Methods for Service Composition, Annals of Mathematics, Computing and Teleinformatics, 1(5), 2007, 1-10.
• [8] Berardi, D., Calvanese, D., Giacomo, G. D., Lenzerini, M., Mecella, M.: Automatic Composition of Eservices That Export Their Behavior, Proceedings of the First International Conference on Service-Oriented Computing (ICSOC), 2003.
• [9] Brachman, R., Levesque, H.: Knowledge Representation and Reasoning, Morgan Kaufmann, 2004.
• [10] Brogi, A., Corfini, S., Aldana, J. F., Delgado, I. N.: Automated Discovery of Compositions of Services Described with Separate Ontologies, Proceedings of the Forth International Conference on Service-Oriented Computing (ICSOC), 2006.
• [11] Brogi, A., Corfini, S., Popescu, R.: Flexible Matchmaking of Web Services Using DAML-S Ontologies, Proceedings of the Second International Conference on Service-Oriented Computing (ICSOC) (short paper), 2004.
• [12] Brogi, A., Popescu, R.: Towards Semi-automated Workflow-Based Aggregation of Web Services, Proceedings of the Third International Conference on Service-Oriented Computing (ICSOC), 2005.
• [13] Choi, N., Song, I.-Y., Han, H.: A Survey on Ontology Mapping, SIGMOD Records, 35(3), 2006, 34-41.
• [14] Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms, The MIT Press and McGraw-Hill Book Company, 1989.
• [15] Dustdar, S., Schreiner, W.: A Survey on Web Services Composition, International Journal of Web and Grid Services (IJWGS), 1(1), 2005, 1-30.
• [16] Fujii, K., Suda, T.: Dynamic Service Composition Using Semantic Information, ICSOC '04: Proceedings of the 2nd International Conference on Service Oriented Computing, ACM Press, 2004.
• [17] van Glabbeek, R. J.: Notes on the Methodology of CCS and CSP, Theoretical Computer Science, 177(2), 1997, 329-349.
• [18] Hashemian, S. V., Mavaddat, F.: A Graph-Based Approach to Web Services Composition, Proceedings of the 2005 IEEE/IPSJ International Symposium on Applications and the Internet (SAINT), 2005.
• [19] Hashemian, S. V., Mavaddat, F.: Composition Algebra: Process Composition Using Algebraic Rules, Preliminary Proceedings of the Third International Workshop on Formal Aspects of Component Software (FACS), September 2006.
• [20] Hashemian, S. V., Mavaddat, F.: A Graph-Based Framework for Composition of Stateless Web Services, Proceedings of the 4th European Conference on Web Services (ECOWS), 2006.
• [21] Hashemian, S. V., Mavaddat, F.: Automatic Composition of Stateless Components: A Logical Reasoning Approach, FSEN '07: Proceedings of the IPM International Symposium on Fundamentals of Software Engineering, Springer, 2007.
• [22] Hoare, C. A. R.: Communicating Sequential Processes, Prentice/Hall International, 1985.
• [23] Kona, S., Bansel, A., Gupta, G.: Automatic Composition of SemanticWeb Services, ICWS '07: Proceedings of the 2007 IEEE International Conference on Web Services, IEEE Computer Society, 2007.
• [24] Laukkanen, M., Helin, H.: Composing Workflows of Semantic Web Services, Proceedings of the Workshop on Web-Services and Agent-based Engineering, 2003.
• [25] Limthanmaphon, B., Zhang, Y.: Web Service Composition with Case-Based Reasoning, ADC '03: Proceedings of the 14th Australasian Database Conference, Australian Computer Society, Inc., 2003.
• [26] Milner, R.: Communication and Concurrency, Prentice Hall, 1989.
• [27] Oh, S.-C., On, B.-W., Larson, E. J., Lee, D.: BF*: Web Services Discovery and Composition as Graph Search Problem, EEE '05: Proceedings of the 2005 IEEE International Conference on e-Technology, e-Commerce and e-Service, IEEE Computer Society, 2005.
• [28] Peer, J.: A PDDL based Tool for Automatic Web Service Composition, PPSWR' 04: Proceedings of Second International Workshop on Principles and Practice of Semantic Web Reasoning, 2004.
• [29] Peer, J.: Web Service Composition as AI Planning - a Survey, Technical report, University of St. Gallen, Switzerland, 2005.
• [30] Rahm, E., Bernstein, P. A.: A Survey of Approaches to Automatic Schema Matching, The VLDB Journal, 10(4), 2001, 334-350.
• [31] Rao, J., Küngas, P., Matskin, M.: Application of Linear Logic to Web Service Composition, Proceedings of the International Conference on Web Services (ICWS), 2003.
• [32] Rao, J., Su, X.: A Survey of Automated Web Service Composition Methods, SWSWPC '04: Proceedings of the First International Workshop on Semantic Web Services and Web Process Composition, Springer, 2004.
• [33] Shin, D.-H., Lee, K.-H.: An Automated Composition of Information Web Services based on Functional Semantics, WSCA '07: Proceedings of the IEEE Workshop on Web Service Composition and Adaptation, IEEE Computer Society, 2007.
• [34] Srivastava, B., Koehler, J.: Web Service Composition - Current Solutions and Open Problems, Proceedings of ICAPS'03 Workshop on Planning for Web Services, 2003.
• [35] StrikeIron, Inc.: StrikeIron, Extending Your SOA, http://www.strikeiron.com, 2006.
• [36] Tang, X., Jiang, C., Ding, Z.: Automatic Web Service Composition Based on Logical Inference of Horn Clauses in Petri Net Models, ICWS '07: Proceedings of the 2007 IEEE International Conference on Web Services, IEEE Computer Society, 2007.
• [37] Traverso, P., Pistore, M.: Automated Composition of Semantic Web Services into Executable Processes, ISWC '04: Proceedings of the Third International Semantic Web Conference, Springer, 2004.
• [38] Weisstein, E. W.: Multiset; From MathWorld-A Wolfram Web Resource, http://mathworld.wolfram.com/Multiset.html, 2002.
• [39] Zhang, R., Arpinar, I. B., Aleman-Meza, B.: Automatic Composition of Semantic Web Services, ICWS '03: Proceedings of the 2003 International Conference on Web Services, 2003.