Алгоритмы эффективной обработки MOLAP-кубов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Кудрявцев, Юрий Александрович

• Кудрявцев, Юрий Александрович
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Кудрявцев, Юрий Александрович

1 Введение б

§ 1 Объект исследования и актуальность темы.

§ 2 Цели и задачи исследования

§ 3 Научная новизна.

§ 4 Положения, выносимые на защиту.

§ 5 Апробация результатов работы.

§ 6 Содержание работы.

2 OLAP

2.1 История Задачи

§ 1 12 Признаков OLAP Данных.

§ 2 FASMI тест.

2.2 Многомерные кубы, определение и свойства

§ 1 Пример.

§ 2 Измерения.

§ 3 Иерархии и агрегирование.

2.3 Виды запросов к кубам.

§ 1 Точечные запросы (Point queries).

§ 2 Интервальные запросы. (Range queries).

§ 3 Обратные запросы. (Iceberg queries).

§ 4 Intelligent Roll-Up запросы.

2.4 Хранение и эффективный расчет OLAP-кубов.

§ 1 Представление нулевых данных.

§ 2 Взрыв данных

§ 3 Материализация представлений

2.5 Общие стратегии вычисления кубов.

§ 1 Способы хранения.

§ 2 Классификация алгоритмов хранения MOLAP-данных

2.6 OLAP и статистические базы данных.

3.1 Требования к многомерным моделям данных.

3 Анализ существующих алгоритмов

3.2 Алгоритм Dwarf.

§ 1 Виды избыточностей структуры куба.

§ 2 Структура куба.

§ 3 Выполнение различных типов запросов.

§ 4 Сложность

§ 5 Виды сжатия.

§ 6 Вывод.

3.3 Многопозиционное агрегирование массивов для вычисления кубов.

§ 1 Пример Вычислений.

3.4 Аппроксимирующие алгоритмы.

§ 1 Вейвлеты.

3.5 Алгоритм Bottom-Up Computation.

3.6 Алгоритм Star-Cubing.

3.7 Condensed Cube.

3.8 Quotient Cube.

§ 1 Разбиение на классы ячеек.

§ 2 QC-Trees.

§ 3 Выполнение различных типов запросов.

4.1 Некоторые определения из теории решеток.

§ 1 Частично-упорядоченное множество, решетка.

§ 2 Описание решеток. Изомофизм решеток. Оператор замыкания.

4 Математическая модель OLAP-данных

4.2 Математическая модель OLAP-кубов.

§ 1 Общие определения. Меры, измерения, операторы в многомерном пространстве.

§ 2 Операторы в Space(r).

§ 3 Классы эквивалентности решетки куба.

§ 4 Замыкания и замкнутые решетки кубов.

5.1 Map-Reduce: парадигма параллельных вычислений.

§ 1 Map/Reduce на многопроцессорных машинах.

§ 2 Map/Reduce и OLAP.

5 Алгоритм вычисление замкнутых кубов с использованием

Map-Reduce

5.2 Предложенный алгоритм.

§ 1 Общий подход к вычислениям

§ 2 Алгоритм создания замкнутого MOLAP-куба на многопроцессорном сервере.

§ 3 Результаты экспериментов.

Введение диссертации (часть автореферата) на тему «Алгоритмы эффективной обработки MOLAP-кубов»

§ 1. Объект исследования и актуальность темы

Термин OLAP (Online Analytical Processing) был введен в 1993 Эдгаром Коддом [Cod93]. Цель OLAP систем - облегчение анализа данных. Кодд сформулировал 12 признаков OLAP-данных, и большинство современных OLAP средств отвечают этим постулатам. Однако 12 признаков в дальнейшем трансформировались в 4 ключевых определения, сформулированные Найджелом Пендзом (см. [РепОБЬ]), на которые теперь ссылаются при определнии OLАР-систем.

FASMI-тест. OLAP-система должна быть:

• Fast - быстрой, обеспечивать почти мгновенный отклик на большинство запросов

• Shared - многопользовательской, должен существовать механизм контроля доступа к данным, а также возможность одновременной работы многих пользователей

• Multidimensional - многомерной, данные должны представляться в виде многомерных кубов.

• Information - данные должны быть полны с точки зрения аналитика, т.е. содержать всю необходимую информацию.

Окончательную формулировку термина предложила в 1995 группа исследователей во главе с Джимом Греем [GBLP95], проанализировав создававшиеся тогда пользовательские приложения баз данных, и предложив расширение языка SQL - оператор CUBE. Этот оператор отвечает в SQL за создание многомерных кубов. Концепция многомерного представления данных является, наряду с моделью транзакций, одной из самых известных идей Кодда. В этой работе исследователи указали ряд эвристических рекомендаций по реализации новой структуры данных.

CUBE представляет собой обобщение операторов GROUP BY по всем возможным комбинациям измерений с разными уровнями агрегации данных. Каждая сгруппированная таблица относится к группе ячеек, описываемых кортежами из измерений, по которым формируется куб. Оператор, расширяющий SQL, называется CUBE BY (синтаксис такой же, как и у GROUP BY).

Дальнейшее развитие OLAP-операций в SQL привело к тому, что в стандарт SQL'99 был включен набор операторов для работы с OLAP-данными (запросы grouping set, rollup by, cube by, window by, rank, rownum и пр.).

В реализации подобных OLAP-приложений возникает ряд проблем, прежде всего связанных с экспоненциальным увеличением объема данных, которые необходимо хранить или рассчитывать.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Кудрявцев, Юрий Александрович

6. Заключение

Рассматриваемая тема актуальна и востребована. Существует большое число промышленных систем, использующих различные идеи и методы работы с OLAP-данными. Тема анализа данных сейчас актуальна в связи с возрастанием объема хранящихся данных. И создание инструментов, призванных помочь пользователю анализировать данные, - актуальное направление научных исследований. Результаты работы

• проведена классификация существующих алгоритмов, выделены следующие группы алгоритмов синтаксические, семантические и аппроксимирующие, для каждой группы алгоритмов приведены примеры наилучших на момент написания работы алгоритмов, указаны условия применимости и оптимальные задачи для каждого из алгоритмов

• разработана формальная математическая модель OLAP данных на базе теории решеток, на введенной модели доказана оптимальность (с точки зрения классов эквивалентности) представления OLAP-кубов замкнутыми решетками по введенному отношению покрытия

• для задачи создания замкнутых решеток OLAP-кубов предложен алгоритм, использующий парадигму Map/Reduce.

• создан прототип алгоритма на технологиях Apache Hadoop (многомашинный кластер) и Stanford Phoenix (использование map/reduce для многопроцессорных серверов), проведены эксперименты, показывающие преимущества данного алгоритма по отношению к уже существующим.

Апробация результатов работы Основные результаты работы докладывались и обсуждались на следующих конференциях:

1. Конференции Syrcodis, Москва, 2006

2. Трижды на семинаре московской секции ACM SIGMOD (2005, 2007, 2008)

3. 1ой международной конференции 'Бизнес-Информатика', Зеленоград, 2007

4. Дважды на конференции 'Корпоративные Базы Данных', Москва, 2007, 2009

5. На семинаре 'Проблемы современных информационно-вычислительных систем' под управлением Васенина В.А. 2008

6. Неоднократно на семинаре 'Технологии баз данных' под управлением Кузнецова С.Д. и Маркова A.C., Москва, 2004-2008

7. Конференции 'Бизнес-Аналитика на современном предприятии', Москва, 2008

8. Конференции 'Advances in Databases, Knowledge, and Data Applications', Канкун, Мексика, 2009

Основные научные результаты работы опубликованы в:

1. 'Applying Map-Reduce Paradigm for Parallel Closed Cube Computation', Kuznetsov Sergei, Kudryavcev Yury, Advances in Databases, Knowledge, and Data Applications, DBKDA '09, pages 62 - 67

2. 'Математическая модель OLAP-кубов', Кузнецов С.Д., Кудрявцев ЮА.,'Программирование', №5 2009

3. 'Efficient algorithms for MOLAP data storage and query processing', Yuri Kudryavcev, Syrcodis, 2006 Сборнике тезисов конференции Syrcodis 2006

4. 'OLАР-технологии: обзор решаемых задач и исследований', Ю.Кудрявцев, Бизнес-Информатика, апрель 2008, Междисциплинарный научно-практический журнал, Госудаственный Университет — Высшая Школа Экономики, страницы 66-79, апрель 2008

5. Сборнике работ молодых ученых факультета ВМиК МГУ 2005 (работа награждена дипломом второй степени)

Список литературы диссертационного исследования кандидат физико-математических наук Кудрявцев, Юрий Александрович, 2009 год

1. JI.65. Фукс JI. Частично упорядоченные линейные системы. Мир, 1965.

2. Г.81. Гретцер Г. Общая теория решеток. Мир, 1981.

3. Г.84. Биркгоф Г. Теория решеток. Наука, 1984.

4. AFEA06. Shah Arun, Novy Robert F., Ertl, and Robert A. Allocation measures and metric calculations in star schema multi-dimensional data warehouse. United States Patent 7,080,090, July 2006.

5. AS94. Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules. In Jorge B. Bocca, Matthias Jarke, and

6. Carlo Zaniolo, editors, Proc. 20th Int. Conf. Very Large Data Bases, VLDB, pages 487-499. Morgan Kaufmann, 12-15 1994.

7. BDJ+05. Douglas Burdick, Prasad Deshpande, T. S. Jayram, Raghu Ramakrishnan, and Shivakumar Vaithyanathan. Olap over uncertain and imprecise data. In VLDB, pages 970-981, 2005.

8. BGJ06. Michael H. Bohlen, Johann Gamper, and Christian S. Jensen.

9. Multi-dimensional aggregation for temporal data. In EDBT, pages 257-275, 2006.

10. BR99. Kevin Beyer and Raghu Ramakrishnan. Bottom-up computation of sparse and iceberg cubes. In SIGMOD, 1999.

11. BW01. Daniel Barbara and Xintao Wu. Loglinear-based quasi cubes. Journal of Intelligent Information Systems, 2001.

12. BYR08. Ricardo Baeza-Yates and Raghu Ramakrishnan. Data challenges at yahoo! In EDBT '08: Proceedings of the 11th international conference on Extending database technology, pages 652-655, New York, NY, USA, 2008. ACM.

13. Cas04. Alain Casali. Mining borders of the difference of two datacubes. In DaWaK, 2004.

14. CCL03a. Alain Casali, Rosine Cicchetti, and Lotfi Lakhal. Cube lattices: a framework for multidimensional data mining. 2003.

15. CCL03b. Alain Casali, Rosine Cicchetti, and Lotfi Lakhal. Extracting semantics from data cubes using cube transversals and closures. In SIGKDD, 2003.

16. CCLN06. Alain Casali, Rosine Cicchetti, Lotfi Lakhal, and Noel Novelli.1.ssless reduction of datacubes. In DEXA, pages 409-419, 2006.

17. CCLR05a. Bee-Chung Chen, Lei Chen, Yi Lin, and Raghu Ramakrishnan.

18. Prediction cubes. In VLDB '05: Proceedings of the 31st international conference on Very large data bases, pages 982-993. VLDB Endowment, 2005.

19. CCLR05b. Bee-Chung Chen, Lei Chen, Yi Lin, and Raghu Ramakrishnan. Prediction cubes. In VLDB, pages 982-993, 2005.

20. Cel06. Joe Celko. Analytics and OLAP in SQL. Morgan Kaufmann, 2006.

21. CNCL07. Alain Casali, Sébastien Nedjar, Rosine Cicchetti, and Lotfi Lakhal.

22. Convex cube: Towards a unified structure for multidimensional databases. In DEXA, pages 572-581, 2007.

23. DERC01. Raghu Dehne, Todd Eavis, and Andrew Rau-Chaplin. Coarse grained parallel on-line analytical processing (olap) for data mining. In ICCS, pages 589-598, 2001.

24. DG04. Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. OSDI '04, pages 137-150, 2004.

25. DMT+05. Burdick Doug, Deshpande Prasad M., Jayram T.S., Ramakrishnan Raghu, and Vaithyanathan Shivakumar. Olap over uncertain and imprecise data. In VLDB, 2005.

26. DPJ03. Curtis E. Dyreson, Torben Bach Pedersen, and Christian S.

27. Jensen. , Incomplete information in multidimensional databases. In Multidimensional databases: problems and solutions, pages 282309. IGI Publishing, Hershey, PA, USA, 2003.

28. Ear94. Robert J. Earle. Method and apparatus for storing and retrieving multi-dimensional data in computer memory. United States Patent 5,359,724, October 1994.

29. Eav03. Todd Eavis. Parallel relational olap. PhD thesis, Dalhousie University, Halifax, Nova Scotia, 2003. Adviser-Andrew Rau-Chaplin.

30. GBLP95. Jim Gray, Adam Bosworth, Andrew Layman, and Hamid Pirahesh.

31. Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals. Microsoft Lab, 1995.

32. GC97. Sanjay Goil and Alok Choudhary. High performance olap and data mining on parallel computers. Center of Parallel and Distributed Computing Technical Report TR-97-05, 1997.

33. GGL03. Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. Thegoogle file system. SIGOPS Oper. Syst. Rev., 37(5):29-43, December 2003.

34. GM05. Himanshu Gupta and Inderpal Singh Mumick. Selection of views to materialize in a data warehouse. IEEE Transactions on Knowledge and Data Engineering, 17(l):24-43, 2005.

35. GRP06. Matteo Golfarelli, Stefano Rizzi, and Andrea Proli. Designing what-if analysis: towards a methodology. In DOLAP '06: Proceedings of the 9th ACM international workshop on Data warehousing and OLAP, pages 51-58, New York, NY, USA, 2006. ACM Press.

36. HFL+08. Bingsheng He, Wenbin Fang, Qiong Luo, Naga K. Govindaraju, and Tuyong Wang. Mars: A mapreduce framework on graphics processors. In PACT08: IEEE International Conference on Parallel Architecture and Compilation Techniques 2008, 2008.

37. HRU96. Venky Harinarayan, Anand Rajaraman, and Jeffrey Ulman. Implementing data cubes efficiently. SIGMOD, 1996.1. Kim.1. KL05.

38. Aaron Kimball. Google: Cluster computing and mapreduce:lecture 5 graph algorithms.

39. Owen Kaser and Daniel Lemire. Attribute value reordering for efficient hybrid olap. Elsevier Science, 2005.

40. KM99. H.J. Karloff and M. Mihail. On the complexity of view-selection problem. In PODS, 1999.

41. KMSB08. Aaron Kimball, Sierra Michels-Slettvet, and Christophe Bisciglia.

42. Cluster computing for web-scale data processing. In SIGCSE '08:

43. Proceedings of the 39th SIGCSE technical symposium on Computer science education, pages 116-120, New York, NY, USA, 2008. ACM.

44. Laks V.S. Lakshmanan and Mark Gyssens. A foundation for multidimensional databases. In VLDB, 1996.

45. G04. Xiaolei Li, Jiawei Han, and Hector Gonzalez. High-dimensional olap: A minimal cubing approach. In VLDB, 2004.

46. W03. Xiaolei Li, Dong Xin Jiawei, and Benjamin W. Wah. Star-cubing: Computing iceberg cubes by top-down and bottom-up integration. In VLDB, 2003.

47. Z03a. Laks V.S. Lakshmanan, Jian Peiz, and Yan Zhao. Qctrees: An efficient summary structure for semantic olap. In SIGMOD, 2003.

48. Z03b. Laks V.S. Lakshmanan, Jian Peiz, and Yan Zhaoy. Socqet: Semantic olap with compressed cube and summarization. In SIGMOD, 2003.

49. MMR91. F.M. Malvestuto, M. Moscarini, and M. Rafanelli. Suppressing marginal cells to protect sensitive information in a two-dimensional statistical table. ACM, 1991.

50. MPWOO. Soroush Momen-Pour and Alan Wagner. Parallel partitioned-cube algorithm. In PDPTA, 2000.

51. MVSV03. Andreas Maniatis, Panos Vassiliadis, Spiros Skiadopoulos, and Yannis Vassiliou. Advanced visualization for olap. In DOLAP '03,2003.

52. MVSV04. Andreas Maniatis, Panos Vassiliadis, Spiros Skiadopoulos, and Yannis Vassiliou. CPM: A cube presentation model for olap. 6th ACM International Workshop on Data Warehousing and OLAP,2004.

53. NCCL07. Sébastien Nedjar, Alain Casali, Rosine Cicchetti, and Lotfi Lakhal.

54. Emerging cubes for trends analysis in olapdatabases. In Song et al. SEN07., pages 135-144.

55. Pas02. Mosha Pasumansky. Multidimensional data ordering. United States Patent 6,460,026, October 2002.

56. Pen05a. Nigel Pendse. Olapreport: Database explosion, 2005.

57. Pen05b. Nigel Pendse. Olapreport: What is olap?, 2005.

58. PJ99a. Torben Bach Pedersen and Christian S. Jensen. Multidimensional data modeling for complex data. In ICDE, pages 336-345, 1999.

59. PJ99b. Torben Bach Pedersen and Christian S. Jensen. Multidimensional data modeling for complex data. In ICDE, pages 336-345, 1999.

60. PJ01. Torben Bach Pedersen and Christian S. Jensen. Multidimensional database technology. IEEE Computer, 34(12):40-46, 2001.

61. PJ05. Torben Bach Pedersen and Christian S. Jensen. Multidimensional databases. In The Industrial Information Technology Handbook, pages 1-13. 2005.

62. PJD99. Torben Bach Pedersen, Christian S. Jensen, and Curtis E.

63. Dyreson. Supporting imprecision in multidimensional databases using granularities. In SSDBM, pages 90-101, 1999.

64. PJD00. Torben Bach Pedersen, Christian S. Jensen, and Curtis E. Dyreson.

65. The treescape system: Reuse of pre-computed aggregates over irregular olap hierarchies. In VLDB, pages 595-598, 2000.

66. PJD01. Torben Bach Pedersen, Christian S. Jensen, and Curtis E. Dyreson.

67. Pre-aggregation for irregular olap hierarchies with the treescape system. In ICDE Demo Sessions, pages 1-3, 2001.

68. PK02. Jeffery S. Pinard and Katheryn Kemper. System for managing accounting information in a multi-dimensional database. United States Patent 6,397,195, May 2002.

69. Pro02. Anthony Charles Proctor. Apparatus and method for compound on-line analytical processing in databases. United States Patent 6,490,593, December 2002.

70. Pu05. Ken Q. Pu. Modeling, querying and reasoning about olap databases: A functional approach. DOLAP, 2005.

71. Raf03. Maurizio Rafanelli, editor. Multidimensional Databases: Problems and Solutions. Idea Group Publishing, 2003.

72. RP02. Srinivasan Sundar Raghavan and Rama Murthy Penumarti.

73. Dynamic recursive build for multidimensional databases and methods and apparatus thereof. United States Patent 6,405,208, June 2002.

74. SDRK02. Yannis Sismanis, Antonios Deligiannakis, Nick Roussopoulos, and Yannis Kotidis. Dwarf: Shrinking the petacube. In VLDB, 2002.

75. SEN07. II Yeal Song, Johann Eder, and Tho Manh Nguyen, editors.

76. Data Warehousing and Knowledge Discovery, 9th International Conference, DaWaK 2007, Regensburg, Germany, September 37, 2007, Proceedings, volume 4654 of Lecture Notes in Computer Science. Springer, 2007.

77. SGA97. Sunita Sarawagi, Ashish Gupta, and Rakesh Agrawal. Modeling multidimensional databases. IBM Research Report, 1997.

78. SHX04. Zheng Shao, Jiawei Han, and Dong Xin. Mm-cubing: Computing iceberg cubes by factorizing the lattice space. In Proceedings of the 16th International Conference on Scientific and Statitistical Database Management (SSDBM'), 2004.

79. SIA05. SI AM International Data Mining Conference. Cross Table Cubing: Mining Iceberg Cubes from Data Warehouses, April 2005.

80. SKK. Timos Sellis, Nikos Karayannidis, and Yannis Kouvaras. Cube file: A file structure for hierarchically clustered olap cubes.

81. SN06. Arun Shah and Robert F. Novy. Analytical server including metrics engine. United States Patent 7,031,953, April 2006.

82. SNE06. Arun Shah, Robert F. Novy, and Robert A. Ertl. Non-additive measures and metric calculation. United States Patent 7,072,897, July 2006.

83. SR04. Yannis Sismanis and Nick Roussopoulos. The polynomial complexity of fully materialized coalesced cubes. In VLDB, 2004.

84. SS94. Sunita Sarawagi and Michael Stonebreaker. Efficient organization of large multidimensional arrays. In Eleventh International Conference on Data Engeneering, 1994.

85. SS01. Sunita Sarawagi and Gayatri Sathe. Intelligent rollups in multidimensional olap data. In VLDB, 2001.

86. SV97. Timos Sellis and Panos Vassiliadis. A survey on logical models for olap databases. 1997.

87. Tho02. Erik Thomsen. OLAP Solutions: Building Multidimensional Information Systems Second Edition. Wiley Computer Publishing John Wiley & Sons, Inc., 2002.

88. TN01. Thomas R. Tortolani and Koorosh M. Nouri. Method and apparatus for accessing multidimensional data. United States Patent 6,317,750, November 2001.

89. VMB98. J. S. Vitter, Wang M., and B.Iyer. Data cube approximation and histograms via wavelets. In CIKM, 1998.

90. WFLY02. Wei Wang, Jianlin Feng, Hongjun Lu, and Jeffrey Xu Yu.

91. Condensed cube: An effective approach to reducing data cube size. In ICDe, 2002.

92. XSHL06. Dong Xin, Zheng Shao, Jiawei Han, and Hongyan Liu. C-cubing: Efficient computation of closed cubes by aggregation-based checking, icde, 0:4, 2006.

93. YJA03. Ge Yang, Ruoming Jin, and Gagan Agrawal. Implementing data cube construction using a cluster middleware: algorithms, implementation experience, and performance evaluation. Future Gener. Comput. Syst., 19(4):533-550, 2003.

94. ZDN97. Yihong Zhao, Prasad M. Deshpande, and Jeffrey F. Naughton.

95. An array-based algorithm for simultaneous multidimensional aggregates. In SIGMOD, pages 159-170, 1997.

96. Zha03. Yan Zhao. Quotient cube and qc-tree: Efficient summarizations for semantic olap, 2003.