Towards the composition of stateful and independent semantic web services

ABSTRACT

Most of the work on automated semantic Web service composition has focused so far on two main levels of composition i.e., functional level and process level composition (respectively FLC and PLC from now). The former level of composition considered Web services as atomic components that can be executed in a single request-response step whereas the latter level studies in more details the protocol and the behavioural features of Web services. Since PLC i.e., a time and particularly space consuming level of composition makes difficult the scalability of composition-based applications, it seems interesting to restrict the composition of stateful but (only) independent Web services. Such a restriction make possible the composition of a large number of Web services in industrial scenarios, the whole with convincing results. In this paper we suggest to study the advantages to apply FLC together with β-composition in order to perform an automated end to end composition of stateful and independent services. In particular we focus on computational complexity results concerning the two models of composition i.e., the well-known PLC vs. the newest FLC+β-composition. Moreover we prove that FLC is an interesting and necessary level of composition to significantly reduce computational complexity not only in space but also in time.

REFERENCES

• 1: Berners-Lee, T., Hendler, J., Lassila, O.: The semantic web. Scientific American 284(5) (May 2001) 34--43
• 2: Franz Baader , Werner Nutt, Basic description logics, The description logic handbook: theory, implementation, and applications, Cambridge University Press, New York, NY, 2003
• 3: Smith, M. K., Welty, C., McGuinness, D. L.: Owl web ontology language guide. W3c recommendation, World Wide Web Consortium (February 2004)
• 4: Sycara, K. P., Paolucci, M., Ankolekar, A., Srinivasan, N.: Automated discovery, interaction and composition of semantic web services. J. Web Sem 1(1) (2003) 27--46
• 5: Ankolenkar, A., Paolucci, M., Srinivasan, N., Sycara, K.: The owl services coalition, owl-s 1.1 beta release. Technical report (July 2004)
• 6: Fensel, D., Kifer, M., de Bruijn, J., Domingue, J.: Web service modeling ontology (wsmo) submission, w3c member submission. (June 2005)
• 7: Sivashanmugam, K., Verma, K., Sheth, A., Miller, J.: Adding semantics to web services standards. In: the 1st International Conference on Web Services. (2003) 395--401
• 8: Evren Sirin , Bijan Parsia , James Hendler, Filtering and Selecting Semantic Web Services with Interactive Composition Techniques, IEEE Intelligent Systems, v.19 n.4, p.42-49, July 2004 [doi>10.1109/MIS.2004.27]
• 9: Klusch, M., Fries, B., Khalid, M., Sycara, K.: Owls-mx: Hybrid owl-s service matchmaking. In: AAAI Fall Symposium Series. (November 2005)
• 10: Berardi, D., Calvanese, D., Giacomo, G. D., Lenzerini, M., Mecella, M.: Automatic service composition based on behavioral descriptions. Int. J. Cooperative Inf. Syst. 14(4) (2005) 333--376
• 11: Srini Narayanan , Sheila A. McIlraith, Simulation, verification and automated composition of web services, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511457]
• 12: Pistore, M., Traverso, P., Bertoli, P.: Automated composition of web services by planning in asynchronous domains. In: ICAPS. (2005) 2--11
• 13: Lécué, F., Léger, A.: A formal model for semantic web service composition. In: ISWC the 5th International Semantic Web Conference. (November 2006) 385--398
• 14: Traverso, P., Pistore, M.: Automated composition of semantic web services into executable processes. In: International Semantic Web Conference. (2004) 380--394
• 15: Marconi, A., Pistore, M., Traverso, P.: Implicit vs. explicit data-flow requirements in web service composition goals. In: ICSOC. (2006) 459--464
• 16: Pistore, M., Marconi, A., Bertoli, P., Traverso, P.: Automated composition of web services by planning at the knowledge level. In: IJCAI. (2005) 1252--1259
• 17: Richard Hull , Michael Benedikt , Vassilis Christophides , Jianwen Su, E-services: a look behind the curtain, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-14, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773154]
• 18: Xiang Fu , Tevfik Bultan , Jianwen Su, Analysis of interacting BPEL web services, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988756]
• 19: John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 20: Çagdaş Evren Gerede , Richard Hull , Oscar H. Ibarra , Jianwen Su, Automated composition of e-services: lookaheads, Proceedings of the 2nd international conference on Service oriented computing, November 15-19, 2004, New York, NY, USA [doi>10.1145/1035167.1035203]
• 21: 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
• 22: Dörfler, W.: The cartesian composition of automata. Mathematical Systems Theory 11 (1978) 239--257
• 23: Aysu Betin-Can , Tevfik Bultan , Xiang Fu, Design for verification for asynchronously communicating Web services, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060853]
• 24: Jyotishman Pathak , Samik Basu , Robyn Lutz , Vasant Honavar, Parallel Web Service Composition in MoSCoE: A Choreography-Based Approach, Proceedings of the European Conference on Web Services, p.3-12, December 04-06, 2006 [doi>10.1109/ECOWS.2006.30]
• 25: Jr., E. M. C., Grumberg, O.: Model Checking. The MIT Press (1999)
• 26: Bertoli, P., Hoffmann, J., Lécué, F., Pistore, M.: Integrating discovery and automated composition: from semantic requirements to executable code. In: ICWS. (2007)
• 27: Calude, C., Calude, E., Khoussainov, B.: Deterministic automata: Simulation, universality and minimality. Ann. Pure Appl. Logic 90(1--3) (1997) 263--276
• 28: Sirin, E., Parsia, B., Wu, D., Hendler, J. A., Nau, D. S.: Htn planning for web service composition using shop2. J. Web Sem. 1(4) (2004) 377--396
• 29: McIlraith, S. A., Son, T. C.: Adapting golog for composition of semantic web services. In: KR. (2002) 482--496
• 30: Zhang, R., Arpinar, I. B., Aleman-Meza, B.: Automatic composition of semantic web services. In: ICWS. (2003) 38--41

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures

General Terms:
Theory

Keywords:
complexity results, composition, semantic web, web service