GMX: an XML data partitioning scheme for holistic twig joins

ABSTRACT

As traditional partitioning strategies do not serve well for semistructured data, partitioning and distributing heterogeneous XML documents onto a parallel cluster system have lead to such an intricacy issue for maintaining good query processing performance. In this paper, we propose a grid metadata model for XML that gives a conceptual view to partition XML data, specifically for holistic twig joins processing. The proposed model adopts a cost-based model and facilitates a set of partition refinement methods for workload balancing purpose. The model has features of reducing the workload variance significantly on the cluster system, duplicating XML data necessarily to avoid data dependency among cluster nodes, and exploiting inter query parallelism and intra query parallelism. We evaluate the effectiveness of our proposed model in the experiment that our data partitioning method has better workload balance and has an impact on better parallel speed up performance as well.

REFERENCES

• 1: Niagara Query Engine. http://www.cs.wisc.edu/niagara.
• 2: Stanford University Infolab. http://infolab.stanford.edu/pub/movies/dtd.html.
• 3: Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of the 18th International Conference on Data Engineering, p.141, February 26-March 01, 2002
• 4: Toshiyuki Amagasa , Kentarou Kido , Hiroyuki Kitagawa, Querying XML Data using PC Cluster System, Proceedings of the 18th International Conference on Database and Expert Systems Applications, p.5-9, September 03-07, 2007 [doi>10.1109/DEXA.2007.118]
• 5: J.-M. Bremer and M. Gertz. On Distributing XML Repositories. In International Workshop on the Web and Databases (WebDB), pages 73--78, 2003.
• 6: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 7: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 8: R. Hockney and M. Berry. Public International Benchmarks for Parallel Computers. Technical report, PARKBENCH Committee on Parallel Benchmarks, 1994.
• 9: Kentarou Kido , Toshiyuki Amagasa , Hiroyuki Kitagawa, Processing XPath Queries in PC-Clusters Using XML Data Partitioning, Proceedings of the 22nd International Conference on Data Engineering Workshops, p.114, April 03-07, 2006 [doi>10.1109/ICDEW.2006.120]
• 10: Ying Guang Li , Stéphane Bressan , Gillian Dobbie , Zoé Lacroix , Mong Li Lee , Ullas Nambiar , Bimlesh Wadhwa, XOO7: applying OO7 benchmark to XML query processing tool, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502614]
• 11: Kevin Lü , Yuanling Zhu , Wenjun Sun, Parallel Processing XML Documents, Proceedings of the 2002 International Symposium on Database Engineering & Applications, p.96-105, July 17-19, 2002
• 12: Rizos Sakellariou , John R. Gurd, Compile-time minimisation of load imbalance in loop nests, Proceedings of the 11th international conference on Supercomputing, p.277-284, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263811]
• 13: Albrecht Schmidt , Florian Waas , Martin Kersten , Michael J. Carey , Ioana Manolescu , Ralph Busse, XMark: a benchmark for XML data management, Proceedings of the 28th international conference on Very Large Data Bases, p.974-985, August 20-23, 2002, Hong Kong, China
• 14: Pang-Ning Tan , Michael Steinbach , Vipin Kumar, Introduction to Data Mining, (First Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 15: Nan Tang , Guoren Wang , Jeffrey Xu Yu , Kam-Fai Wong , Ge Yu, WIN: An E.cient Data Placement Strategy for Parallel XML Databases, Proceedings of the 11th International Conference on Parallel and Distributed Systems, p.349-355, July 20-22, 2005 [doi>10.1109/ICPADS.2005.298]
• 16: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms

Keywords:
XML data partition, holistic twig joins, parallel query processing