Data mining-based fragmentation of XML data warehouses

ABSTRACT

With the multiplication of XML data sources, many XML data warehouse models have been proposed to handle data heterogeneity and complexity in a way relational data warehouses fail to achieve. However, XML-native database systems currently suffer from limited performances, both in terms of manageable data volume and response time. Fragmentation helps address both these issues. Derived horizontal fragmentation is typically used in relational data warehouses and can definitely be adapted to the XML context. However, the number of fragments produced by classical algorithms is difficult to control. In this paper, we propose the use of a k-means-based fragmentation approach that allows to master the number of fragments through its k parameter. We experimentally compare its efficiency to classical derived horizontal fragmentation algorithms adapted to XML data warehouses and show its superiority.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: Torsten Grust , Hagen Höpfner , Arantza Illarramendi , Stefan Jablonski , Marco Mesiti , Sascha Müller , Paula-Lavinia Patranjan , Kai-Uwe Sattler , Myra Spiliopoulou , Jef Wijsen, Current Trends in Database Technology - EDBT 2006: EDBT 2006 Workshop PhD, DataX, IIDB, IIHA, ICSNW, QLQP, PIM, PaRMa, and Reactivity on the Web, Munich, ... Papers (Lecture Notes in Computer Science), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 3: K. Aouiche, P.-E. Jouve, and J. Darmont. Clustering-based materialized view selection in data warehouses. In 10th East-European Conference on Advances in Databases and Information Systems (ADBIS 06), Thessaloniki, Greece, volume 4152 of LNCS, pages 81--95. Springer, September 2006.
• 4: S. Azefack, K. Aouiche, and J. Darmont. Dynamic index selection in data warehouses. In 4th International Conference on Innovations in Information Technology (Innovations 07), Dubai, United Arab Emirates. IEEE Computer Society, November 2007.
• 5: L. Bellatreche and K. Boukhalfa. An Evolutionary Approach to Schema Partitioning Selection in a Data Warehouse. In 7th International Conference on Data Warehousing and Knowledge Discovery (DaWaK 05), Copenhagen, Denmark, volume 3589 of LNCS, pages 115--125. Springer, 2005.
• 6: Kevin Beyer , Don Chambérlin , Latha S. Colby , Fatma Özcan , Hamid Pirahesh , Yu Xu, Extending XQuery for analytics, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066215]
• 7: Angela Bonifati , Alfredo Cuzzocrea, Efficient Fragmentation of Large XML Documents, Proceedings of the 18th international conference on Database and Expert Systems Applications, September 03-07, 2007, Regensburg, Germany [doi>10.1007/978-3-540-74469-6_53]
• 8: A. Bonifati, A. Cuzzocrea, and B. Zinno. Fragmenting XML Documents via Structural Constraints. In 10th East European Conference on Advances in Databases and Information Systems (ADBIS 06), Thessaloniki, Greece, Local Proceedings, pages 17--29, 2006.
• 9: Angela Bonifati , Ugo Matrangolo , Alfredo Cuzzocrea , Mayank Jain, XPath lookup queries in P2P networks, Proceedings of the 6th annual ACM international workshop on Web information and data management, November 12-13, 2004, Washington DC, USA [doi>10.1145/1031453.1031464]
• 10: S. Bose and L. Fegaras. XFrag: A query Processing Framework for Fragmented XML Data. In 8th International Workshop on the Web and Databases (WebDB 05), Baltimore, Maryland, pages 97--102, 2005.
• 11: K. Boukhalfa, L. Bellatreche, and P. Richard. Fragmentations Primaire et Dérivée : Etude de Complexité, Algorithmes de Sélection et Validation sous Oracle 10g. In 4èmes journées francophones sur les Entrepôts de Données et l'Analyse en ligne (EDA 08), Toulouse, France, volume B-4 of RNTI, pages 123--139. Cépaduès, June 2008.
• 12: D. Boukraa, R. BenMessaoud, and O. Boussaïd. Proposition d'un Modèle physique pour les entrepôts XML. In Atelier Systèmes Décisionnels (ASD 06), 9th Maghrebian Conference on Information Technologies (MCSEAI 06), Agadir, Morocco, 2006.
• 13: O. Boussaïd, R. BenMessaoud, R. Choquet, and S. Anthoard. X-Warehousing: An XML-Based Approach for Warehousing Complex Data. In 10th East-European Conference on Advances in Databases and Information Systems (ADBIS 06), Thessaloniki, Greece, volume 4152 of LNCS, pages 39--54. Springer, 2006.
• 14: A. S. Darabant and A. Campan. Semi-supervised learning techniques: k-means clustering in OODB Fragmentation. In Second IEEE International Conference on Computational Cybernetics (ICCC 04), Vienna, Austria, pages 333--338. IEEE Computer Society, 2004.
• 15: Anindya Datta , Krithi Ramamritham , Helen M. Thomas, Curio: A Novel Solution for Efficient Storage and Indexing in Data Warehouses, Proceedings of the 25th International Conference on Very Large Data Bases, p.730-733, September 07-10, 1999
• 16: R. L. de Carvalho Costa and P. Furtado. Data Warehouses in Grids with High QoS. In 8th International Conference on Data Warehousing and Knowledge Discovery (DaWaK 06), Krakow, Poland, volume 4081 of LNCS, pages 207--217. Springer, 2006.
• 17: Valerie FIOLET , Bernard TOURSEL, Progressive Clustering for Database Distribution on a Grid, Proceedings of the The 4th International Symposium on Parallel and Distributed Computing, p.282-289, July 04-06, 2005 [doi>10.1109/ISPDC.2005.41]
• 18: M. Gertz and J.-M. Bremer. Distributed XML Repositories: Top-down Design and Transparent Query Processing. Technical report, Departement of Computer Science, University of California, USA, 2003.
• 19: M. Golfarelli, D. Maio, and S. Rizzi. Vertical fragmentation of views in relational data warehouses. In Settimo Convegno Nazionale su Sistemi Evoluti Per Basi Di Dati (SEBD 99), Como, Italy, pages 19--33, 1999.
• 20: N. Gorla and P. W. Y. Betty. Vertical Fragmentation in Databases Using Data-Mining Technique. International Journal of Data Warehousing and Mining, 4(3):35--53, 2008.
• 21: Marouane Hachicha , Hadj Mahboubi , Jérôme Darmont, Expressing OLAP operators with the TAX XML algebra, Proceedings of the 2008 EDBT workshop on Database technologies for handling XML information on the web, March 25-25, 2008, Nantes, France [doi>10.1145/1416691.1416703]
• 22: G. Holmes, A. Donkin, and I. Witten. Weka: A machine learning workbench. In Second Australia and New Zealand Conference on Intelligent Information Systems, Brisbane, Australia, 1994.
• 23: A. Koreichi and B. L. Cun. On data fragmentation and allocation in distributed object oriented databases. Technical report, PRiSM, Versailles University, France, 1997.
• 24: H. Ma and K.-D. Schewe. Fragmentation of XML Documents. In XVIII Simpósio Brasileiro de Bancos de Dados, Manaus, Amazonas, Brasil, pages 200--214. UFAM, 2003.
• 25: H. Ma, K.-D. Schewe, S. Hartmann, and M. Kirchberg. Distribution Design for XML Documents. In 3rd International Conference on Electronic Commerce Engineering (ICECE 03), Hangzhou, China, pages 1007--1012. International Academic Publisher/World Publishing Corporation, 2003.
• 26: J. MacQueen. Some Methods for classification and Analysis of Multivariate Observations. In 5th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, USA, pages 281--297. University of California Press, 1967.
• 27: H. Mahboubi and J. Darmont. Benchmarking XML data warehouses. In Atelier Systèmes Décisionnels (ASD 06), 9th Maghrebian Conference on Information Technologies (MCSEAI 06), Agadir, Morocco, 2006.
• 28: H. Mahboubi and J. Darmont. Enhancing XML Data Warehouse Performance by Fragmentation. Technical report, Technical report, ERIC, University of Lyon 2, France, 2008.
• 29: H. Mahboubi, M. Hachicha, and J. Darmont. XML Warehousing and OLAP. Encyclopedia of Data Warehousing and Mining, Second Edition. IGI Publishing, August 2008.
• 30: D. Munneke, K. Wahlstrom, and M. K. Mohania. Fragmentation of multidimensional databases. In 10th Australasian Database Conference (ADC 99), Auckland, New Zealand, pages 153--164, 1999.
• 31: S. B. Navathe, K. Karlapalem, and M. Ra. A Mixed Fragmentation Methodology for Initial Distributed Database Design. Journal of Computer and Software Engineering, 3(4), 1995.
• 32: Amin Y. Noaman , Ken Barker, A horizontal fragmentation algorithm for the fact relation in a distributed data warehouse, Proceedings of the eighth international conference on Information and knowledge management, p.154-161, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.319972]
• 33: Stelios Paparizos , Yuqing Wu , Laks V. S. Lakshmanan , H. V. Jagadish, Tree logical classes for efficient evaluation of XQuery, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007579]
• 34: D. Pham, S. Dimov, and C. Nguyen. An Incremental K-means algorithm. Journal of Mechanical Engineering Science, 218(7):783--795, 2004.
• 35: Jaroslav Pokorný, XML Data Warehouse: Modelling and Querying, Proceedings of the Baltic Conference, BalticDB&IS 2002, p.267-280, January 2002
• 36: Pascal Wehrle , Maryvonne Miquel , Anne Tchounikine, A Model for Distributing and Querying a Data Warehouse on a Computing Grid, Proceedings of the 11th International Conference on Parallel and Distributed Systems (ICPADS'05), p.203-209, July 20-22, 2005 [doi>10.1109/ICPADS.2005.35]
• 37: N. Wiwatwattana, H. V. Jagadish, L. V. S. Lakshmanan, and D. Srivastava. X^3: A Cube Operator for XML OLAP. In 23rd International Conference on Data Engineering (ICDE 07), Istanbul, Turkey, pages 916--925, 2007.
• 38: M.-C. Wu and A. P. Buchmann. Research Issues in Data Warehousing. In Datenbanksysteme in Buro, Technik und Wissenschaft, pages 61--82, 1997.
• 39: Ji Zhang , Wei Wang , Han Liu , Sheng Zhang, X-warehouse: building query pattern-driven data, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062786]
• 40: Y. Zhang and O. Orlowska. On fragmentation approaches for distributed database design. Information Sciences, 1(3):117--132, 1994.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration

General Terms:
Performance

Keywords:
XML data warehouses, clustering, fragmentation, k-means, performance