Framework for Web service query algebra and optimization

Abstract

We present a query algebra that supports optimized access of Web services through service-oriented queries. The service query algebra is defined based on a formal service model that provides a high-level abstraction of Web services across an application domain. The algebra defines a set of algebraic operators. Algebraic service queries can be formulated using these operators. This allows users to query their desired services based on both functionality and quality. We provide the implementation of each algebraic operator. This enables the generation of Service Execution Plans (SEPs) that can be used by users to directly access services. We present an optimization algorithm by extending the Dynamic Programming (DP) approach to efficiently select the SEPs with the best user-desired quality. The experimental study validates the proposed algorithm by demonstrating significant performance improvement compared with the traditional DP approach.

References

1. Alonso, G., Casati, F., Kuno, H., and Machiraju, V. 2003. Web Services: Concepts, Architecture, and Applications. Springer Verlag.
2. Aurrecoechea, C., Campbell, A., and Hauw, L. 1998. A survey of QoS architectures. ACM/Springer Verlag Multimed. Syst. J. 6, 3, 138--151.
3. Berardi, D., Calvanese, D., Giacomo, G. D., Hull, R., and Mecella, M. 2005. Automatic composition of transition-based semantic Web services with messaging. In Proceedings of the International Conference on Very Large Databases.
4. Bhatti, R., Bertino, E., and Ghafoor, A. 2005. A trust-based context-aware access control model for Web-services. Distrib. Para. Data. 18, 1, 83--105.
5. Casati, F., Shan, E., Dayal, U., and Shan, M. C. 2003. Business-oriented management of Web services. Commu. ACM 46, 10, 55--60.
6. Casati, F. and Shan, M. C. 2001. Definition, execution, analysis, and optimization of composite e-services. IEEE Data Eng. Bull. 24, 1, 29--34.
7. Chaudhuri, S. 1998. An overview of query optimization in relational systems. In Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. 34--43.
8. Dalvi, N., Sanghai, S., Roy, P., and Sudarshan, S. 2001. Pipelining in multi-query optimization. In Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems.
9. Dong, X., Halevy, A. Y., Madhavan, J., Nemes, E., and Zhang, J. 2004. Simlarity search for Web services. In Proceedings of the International Conference on Very Large Databases.
10. Du, W., Krishnamurthy, R., and Shan, M.-C. 1992. Query optimization in a heterogeneous DBMS. In Proceedings of the International Conference on Very Large Databases.
11. Fernandez, M. and Suciu, D. 1998. Optimizing regular path expressions using graph schemas. In Proceedings of the IEEE International Conference on Data Engineering. 14--23.
12. Florescu, D., Levy, A., Manolescu, I., and Suciu, D. 1999. Query optimization in the presence of limited access patterns. In Proceedings of the ACM SIGMOD International Conference on Management of Data.
13. Gillmann, M., Weikum, G., and Wonner, W. 2002. Workflow management with service quality guarantees. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 228--239.
14. Haas, L., Kossmann, D., Wimmers, E., and Yang, J. 1997. Optimizing queries across diverse data sources. In Proceedings of the International Conference on Very Large Databases.
15. Hamadi, R. and Benatallah, B. 2003. A petri net-based model for web service composition. In Proceedings of the 14th Australasian Database Conference on Database Technologies. 191--200.
16. Marchetti, C., Pernici, B., and Plebani, P. 2004. A quality model for multichannel adaptive information. In Proceedings of the International Conference on World Wide Web. New York, NY.
17. Mecella, M., Ouzzani, M., Paci, F., and Bertino, E. 2006. Access control enforcement for conversation-based Web services. In Proceedings of the International Conference on World Wide Web. 257--266.
18. Ouzzani, M. and Bouguettaya, B. 2004. Efficient access to Web services. IEEE Internet Comput. 37, 3.
19. Papadimitriou, C. H. and Yannakakis, M. 2001. Multiobjective query optimization. In Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems.
20. Papazoglou, M. P. 2003. Web services and business transactions. WWW 6, 1, 49--91.
21. Papazoglou, M. P., Traverso, P., Dustdar, S., Leymann, F., and Krämer, B. J. 2005. Service-oriented computing: A research roadmap. In Service-Oriented-Computing.
22. Papazoglou, M. P. and van den Heuvel, W. 2005. Web services management: A survey. IEEE Internet Comput. 9, 6, 58--64.
23. Ponnekanti, S. and Fox, A. 2002. SWORD: A developer toolkit for Web service composition. In Proceedings of the International Conference on World Wide Web.
24. Pu, K., Hristidis, V., and Koudas, N. 2006. A syntactic rule based approach to Web service composition. In Proceedings of the IEEE International Conference on Data Engineering.
25. Selinger, P., Astrahanand, M., Chamberlin, D., Lorie, R., and Price, T. 1979. Access path selection in a relational database management system. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 23--34.
26. Srivastava, U., Widom, J., Munagala, K., and Motwani, R. 2006. Query optimization over Web services. In Proceedings of the International Conference on Very Large Databases.
27. Straube, D. D. and Özsu, M. T. 1995. Query optimization and execution plan generation in object-oriented data management systems. IEEE Trans. Knowl. Data Eng. 7, 2, 210--227.
28. Systinet. 2004. Systinet server for Java. http://www.systinet.com/products/ssj/overview.
29. van Moorsel, A. 2001. Metrics for the internet age: Quality of experience and quality of business. Tech. rep., HP Labs.
30. Yerneni, Y., Li, C., Ullman, J., and Garcia-Molina, H. 1999. Optimizing large join queries in mediation systems. In Proceedings of the International Conference on Database Theory.
31. Yu, Q., Liu, X., Bouguettaya, A., and Medjahed, B. 2007. Deploying and managing Web services: Issues, solutions, and directions. The VLDB J., To appear.
32. Zeng, L., Benatallah, B., Ngu, A., Dumas, M., Kalagnanam, J., and Chang, H. 2004. Qos-aware middleware for web services composition. IEEE Trans. Softw. Eng. 30, 5, 311--327.

Index Terms

• Information systems

  • World Wide Web

    • Web applications

    • Web services