XCraft: boosting the performance of active XML materialization

ABSTRACT

An active XML (AXML) document contains tags representing calls to Web services. Therefore, retrieving its contents consists in materializing its data elements by invoking the embedded service calls in a P2P network. In this process, the result of some service calls can be used as input of other calls. Also, usually several peers provide each requested Web service, and peers can collaborate to invoke these services. This often implies a huge search space of many equivalent materialization alternatives, each with different performance. In this paper, we model AXML documents from a workflow perspective and propose a dynamic cost-based optimization strategy to efficiently materialize them, considering the volatility of a typical P2P scenario. Our strategy enables the optimizer, called XCraft, to get more up-to-date information on the status of the peers, and to deliver partial results earlier. Based on a service-oriented algebra of plan operators, we exploit P2P collaboration to delegate both execution and optimization control. Our tests with an XCraft prototype show important performance gains w.r.t. a centralized approach, whilst the optimizer also achieved to drastically reduce the size of the search space.

REFERENCES

• 1: Serge Abiteboul , Omar Benjelloun , Bogdan Cautis , Ioana Manolescu , Tova Milo , Nicoleta Preda, Lazy query evaluation for Active XML, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007596]
• 2: Serge Abiteboul , Angela Bonifati , Grégory Cobéna , Ioana Manolescu , Tova Milo, Dynamic XML documents with distribution and replication, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872821]
• 3: S. Abiteboul, I. Manolescu, and E. Taropa. A framework for distributed XML data management. In EDBT, pages 1049--1058, 2006.
• 4: ActiveXML home page. At www.activexml.net.
• 5: Boualem Benatallah , Marlon Dumas , Quan Z. Sheng, Facilitating the rapid development and scalable orchestration of composite web services, Distributed and Parallel Databases, v.17 n.1, p.5-37, January 2005 [doi>10.1023/B:DAPD.0000045366.15607.67]
• 6: J. Blythe , S. Jain , E. Deelman , Y. Gil , K. Vahi , A. Mandal , K. Kennedy, Task scheduling strategies for workflow-based applications in grids, Proceedings of the Fifth IEEE International Symposium on Cluster Computing and the Grid (CCGrid'05) - Volume 2, p.759-767, May 09-12, 2005
• 7: Tracy D. Braun , Howard Jay Siegel , Noah Beck , Lasislau L. Bölöni , Muthucumara Maheswaran , Albert I. Reuther , James P. Robertson , Mitchell D. Theys , Bin Yao , Debra Hensgen , Richard F. Freund, A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems, Journal of Parallel and Distributed Computing, v.61 n.6, p.810-837, June 2001 [doi>10.1006/jpdc.2000.1714 ]
• 8: Junwei Cao , Stephen A. Jarvis , Subhash Saini , Graham R. Nudd, GridFlow: Workflow Management for Grid Computing, Proceedings of the 3st International Symposium on Cluster Computing and the Grid, p.198, May 12-15, 2003
• 9: E. Deelman, J. Blythe, Y. Gil, C. Kesselman, G. Mehta, K. Vahi, K. Blackburn, A. Lazzarini, A. Arbree, R. Cavanaugh, and S. Koranda. Mapping Abstract Complex Workflows onto Grid Environments. J. Grid Comput., 1(1):25--39, 2003.
• 10: Anastasios Gounaris , Rizos Sakellariou , Norman W. Paton , Alvaro A. A. Fernandes, Resource Scheduling for Parallel Query Processing on Computational Grids, Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing, p.396-401, November 08-08, 2004 [doi>10.1109/GRID.2004.55]
• 11: Optimization Techniques for Data-Intensive Decision Flows, Proceedings of the 16th International Conference on Data Engineering, p.281, February 28-March 03, 2000
• 12: Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999 [doi>10.1145/344588.344618]
• 13: M. Lemos and M. A. Casanova. On the complexity of process pipeline scheduling. In SBBD, pages 57--71, 2006.
• 14: L. A. Meyer, D. Sheftner, J. Voeckler, M. Mattoso, M. Wilde, and I. Foster. An opportunistic algorithm for scheduling workflows on grids. In VECPAR, 2006.
• 15: Tova Milo , Serge Abiteboul , Bernd Amann , Omar Benjelloun , Fred Dang Ngoc, Exchanging intensional XML data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872793]
• 16: OWL-S: Semantic Markup for Web Services. At http://www.w3.org/Submission/OWL-S/.
• 17: Pegasus home page. At http://pegasus.isi.edu.
• 18: G. Ruberg and M. Mattoso. XCraft: A dynamic optimizer for the materialization of active XML documents. COPPE/UFRJ Tech. Report ES-709/07, http://www.cos.ufrj.br/~gruberg/xcraft_rt.pdf, 2007.
• 19: N. Ruberg, G. Ruberg, and I. Manolescu. Towards cost-based optimization for data-intensive Web service computations. In SBBD, pages 283--297, 2004.
• 20: ACM SIGMOD Record articles database. Available at http://acm.org/sigmod/record/xml/.
• 21: W. M. P. Van Der Aalst , A. H. M. Ter Hofstede , B. Kiepuszewski , A. P. Barros, Workflow Patterns, Distributed and Parallel Databases, v.14 n.1, p.5-51, July 2003 [doi>10.1023/A:1022883727209 ]
• 22: Patricia Kayser Vargas , Inês de Castro Dutra , Vinicius Dalto do Nascimento , Lucas A. S. Santos , Luciano C. da Silva , Cláudio F. R. Geyer , Bruno Schulze, Hierarchical submission in a Grid environment, Proceedings of the 3rd international workshop on Middleware for grid computing, p.1-6, November 28-December 02, 2005, Grenoble, France [doi>10.1145/1101499.1101513]
• 23: William van Dorst, The Quintessential Linux Benchmark: All about the "BogoMips" number displayed when Linux boots, Linux Journal, v.1996 n.21es, Jan. 1996
• 24: The W3 Consortium. At http://www.w3.org/.
• 25: Marek Wieczorek , Radu Prodan , Thomas Fahringer, Scheduling of scientific workflows in the ASKALON grid environment, ACM SIGMOD Record, v.34 n.3, September 2005 [doi>10.1145/1084805.1084816]