Complexity and composition of synthesized web services

ABSTRACT

The paper investigates fundamental decision problems and composition synthesis for Web services commonly found in practice. We propose a notion of synthesized Web services (ASTs) to specify the behaviors of the services. Upon receiving a sequence of input messages, an AST issues multiple queries to a database and generates actions, in parallel; it produces external messages and database updates by synthesizing the actions parallelly generated. In contrast to previous models for Web services, ASTs advocate parallel processing and (deterministic) synthesis of actions. We classify ASTs based on what queries an AST can issue, how the synthesis of actions is expressed, and whether unbounded input sequences are allowed in a single interaction session. We show that the behaviors of Web services supported by various prior models, data-driven or not, can be specified by different AST classes. For each of these classes we study the non-emptiness, validation and equivalence problems, and establish matching upper and lower bounds on these problems. We also provide complexity bounds on composition synthesis for these AST classes, identifying decidable cases.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Serge Abiteboul , Victor Vianu , Brad Fordham , Yelena Yesha, Relational transducers for electronic commerce, Journal of Computer and System Sciences, v.61 n.2, p.236-269, Oct. 2000 [doi>10.1006/jcss.2000.1708]
• 3: Foto N. Afrati , Manolis Gergatsoulis , Theodoros G. Kavalieros, Answering Queries Using Materialized Views with Disjunctions, Proceedings of the 7th International Conference on Database Theory, p.435-452, January 10-12, 1999
• 4: Foto Afrati , Chen Li , Prasenjit Mitra, Rewriting queries using views in the presence of arithmetic comparisons, Theoretical Computer Science, v.368 n.1-2, p.88-123, December, 2006 [doi>10.1016/j.tcs.2006.08.020]
• 5: Daniela Berardi , Diego Calvanese , Giuseppe De Giacomo , Richard Hull , Massimo Mecella, Automatic composition of transition-based semantic web services with messaging, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 6: D. Berardi, D. Calvanese, G.D. Giacomo, M. Lenzerini, and M. Mecella. Automatic service composition based on behavioral descriptions. Int. J. Cooperative Inf. Syst., 14(4):333--376, 2005.
• 7: Business Process Execution Language for Web Services version 1.1 (BEPL4WS), 2004. http://www.ibm.com/developerworks/library/specification/ws-bpel/
• 8: D. Calvanese, G.D. Giacomo, M. Lenzerini, and M. Y. Vardi. Rewriting of regular expressions and regular path queries. JCSS, 64(3):443--465, 2002.
• 9: Diego Calvanese , Giuseppe De Giacomo , Moshe Y. Vardi, Decidable containment of recursive queries, Theoretical Computer Science, v.336 n.1, p.33-56, 25 May 2005 [doi>10.1016/j.tcs.2004.10.031]
• 10: S. Chaudhuri and M.Y. Vardi. On the equivalence of recursive and nonrecursive datalog programs. JCSS, 54(1):61--78, 1997.
• 11: S Cosmadakis , P Kanellakis, Parallel evaluation of recursive rule queries, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.280-293, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15421]
• 12: Alin Deutsch , Liying Sui , Victor Vianu, Specification and verification of data-driven Web applications, Journal of Computer and System Sciences, v.73 n.3, p.442-474, May, 2007 [doi>10.1016/j.jcss.2006.10.006]
• 13: Alin Deutsch , Liying Sui , Victor Vianu , Dayou Zhou, Verification of communicating data-driven web services, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142364]
• 14: Oliver M. Duschka , Michael R. Genesereth, Answering recursive queries using views, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.109-116, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263674]
• 15: 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]
• 16: Xiang Fu , Tevfik Bultan , Jianwen Su, Conversation protocols: a formalism for specification and verification of reactive electronic services, Theoretical Computer Science, v.328 n.1-2, p.19-37, 29 November 2004 [doi>10.1016/j.tcs.2004.07.004]
• 17: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 18: Ç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]
• 19: Georg Gottlob , Christos Papadimitriou, On the complexity of single-rule datalog queries, Information and Computation, v.183 n.1, p.104-122, May 25, 2003 [doi>10.1016/S0890-5401(03)00012-9]
• 20: Alon Y. Halevy, Theory of answering queries using views, ACM SIGMOD Record, v.29 n.4, p.40-47, Dec. 2000 [doi>10.1145/369275.369284]
• 21: Richard Hull , Jianwen Su, Tools for composite web services: a short overview, ACM SIGMOD Record, v.34 n.2, June 2005 [doi>10.1145/1083784.1083807]
• 22: Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
• 23: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 24: A. Muscholl and I. Walukiewicz. A lower bound on Web services composition. In FoSSaCS, 2007.
• 25: OWL-S: Semantic Markup for Web Services, 2004. http://www.w3.org/Submission/OWL-S/.
• 26: M. Pistore , P. Traverso , P. Bertoli , A. Marconi, Automated Synthesis of Composite BPEL4WS Web Services, Proceedings of the IEEE International Conference on Web Services, p.293-301, July 11-15, 2005 [doi>10.1109/ICWS.2005.27]
• 27: Semantic Web Services Framework (SWSF) Version 1.1, 2005. http://www.daml.org/services/swsf/1.1/.
• 28: M. Spielmann. Abstract State Machines: Verification Problems and Complexity. PhD thesis, RWTH , 2000.
• 29: Marc Spielmann, Verification of relational transducers for electronic commerce, Journal of Computer and System Sciences, v.66 n.1, p.40-65, 01 February 2003 [doi>10.1016/S0022-0000(02)00029-6]
• 30: Web Services Conversation Language (WSCL) 1.0, 2002. http://www.w3.org/TR/wscl10/.
• 31: Web Services Description Language (WSDL) 1.1, 2001. http://www.w3.org/TR/wsdl.
• 32: S. Yu. Regular languages. In Handbook of Formal Languages, volume 1. Springer, 1996.

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:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

General Terms:
Design, Languages, Theory, Verification

Keywords:
complexity, composition, data-driven web services