基于属性划分存储结构的并行联机分析处理操作算法研究
|
摘要
数据仓库是存储供查询和决策分析使用的集成化和历史化数据的
仓库，通过提供联机分析处理应用，为复杂数据分析和高层决策提供
有效支持。联机分析处理（OLAP）是数据仓库系统的最主要应用之一，
OLAP的性能直接影响数据仓库系统的性能。本文以计算机机群
计算并行系统为并行计算环境，充分利用了一种新的高效存储结
构——属性划分存储结构的特点，提出了一组基于属性划分存储
结构的并行OLAP操作算法。所有并行操作算法已经用于我们自行
研制的并行数据仓库管理系统。理论分析和实验证明，并行算
法具有很高的效率和加速比。
Data Warehouse is a large repository of integrated and historicized
information, which is available for complicated querying and analyzing.
Data Warehouse supports on-line analysis processing (OLAP) for decision
making. OLAP is one of the most important operations in Data Warehouse,
and the efficiency of OLAP has important effect on the performance of
Data Warehouse system. A new set of parallel algorithms for OLAP
operations are proposed in this paper. The algorithms utilize sufficiently
the character of the parallel attribute partition storage structure new
proposed storage structure for Data Warehouse system. The algorithms
have been used in a parallel data warehouse system. Theoretical analysis
and experimental results show that algorithms are very efficient.
仓库，通过提供联机分析处理应用，为复杂数据分析和高层决策提供
有效支持。联机分析处理（OLAP）是数据仓库系统的最主要应用之一，
OLAP的性能直接影响数据仓库系统的性能。本文以计算机机群
计算并行系统为并行计算环境，充分利用了一种新的高效存储结
构——属性划分存储结构的特点，提出了一组基于属性划分存储
结构的并行OLAP操作算法。所有并行操作算法已经用于我们自行
研制的并行数据仓库管理系统。理论分析和实验证明，并行算
法具有很高的效率和加速比。
Data Warehouse is a large repository of integrated and historicized
information, which is available for complicated querying and analyzing.
Data Warehouse supports on-line analysis processing (OLAP) for decision
making. OLAP is one of the most important operations in Data Warehouse,
and the efficiency of OLAP has important effect on the performance of
Data Warehouse system. A new set of parallel algorithms for OLAP
operations are proposed in this paper. The algorithms utilize sufficiently
the character of the parallel attribute partition storage structure new
proposed storage structure for Data Warehouse system. The algorithms
have been used in a parallel data warehouse system. Theoretical analysis
and experimental results show that algorithms are very efficient.
引文
1 王珊．数据仓库技术与联机分析处理．科学出版社，1999．
2 李建中，孙文隽．并行关系数据库管理系统引论．科学出版社，1998．
3 李建中，王珊．数据库系统原理．电子工业出版社，1999．
4 Inmon，W．H．，Building the Data Warehouse．John Whiley，1992．
5 Codd，E．F．，Codd，S．B．,and Salley，C．T．，“Providing OLAP (on-line analytical processing)to useranalysis：an IT mandate，Technical Report， E．F．Codd and Associates，1993．
6 Erickson，C．G．，“Multidimensional and the data warehouse”,in The Data Warehousing Conference，Orlando．FL．February．1995．
7 Colliat，G．,"OLAR, relational and multidimensional database systems”, Technical Report，Arbor Software Corporation．Sunnyvale，CA．
8 Li，C．and Wang，X．S．，“A data model for supporting on-line analytical processing”，in Proccedings of Information and Knowledge Management，Baltimore，MD，1996．
9 R．Agrawal，A．Gupta，S．Sarawagi，ModelingMultidimensional Database [C]．ICDE’97
10 Luca Cabibbo，Riccardo Torlone，Querying Multidimensional Databases [C]．DBPL’97
11 Mare Gyssens．L．V．S．LAK shmanan．A Foundation for Multidimensional Databases[C]．VLDB’97
12． Lehner．Modeling Large Scale OLAP Scenariosl[C]．EDBT’98
White,C., "Data warehouse: what's in a name?", Database Programming and Design, Mar. 1996, 9(3) :53-54
13 Hong, J., "The construction and application of a data warehouse", China Computer Users, 1996,20:6-11
14 dom J., "Research problems in data warehousing", in Proceedings of the 4th International Conference on Information and Knowledge Management. Baltimore, Maryland, Nov. 1995． 25-30
15 Gray,J., Bosworth, A., Layman, A., and Pirahesh,H., "Data cube: a relational aggregation operator generalizing group-by, crosstabs. and subtotals", Proceedings of IEEE Data Eng., Nwe Orleans, 1996．
16 grawal, R., et al., "On the computation of multidimensional aggregates", in Proceedings of VLDB, Mumbai. India, Sept. 1996．
17 Harinarayanan, V., Rajaraman, A., and Ullman, J.D., "Implementing data cubes efficiently", in Proceedings of SIGMOD, 1996, pp 205-216．
18 Ross, K.A. and Srivastava, D., "Fast Computation of Sparse Datacubes", in Proceedings of VLDB, 1997, pp. 116-125．
19 Zhao, Y., Deshpande, P.M., and Naughton, J.F, "An array-based algorithm for simultaneous multidimentional aggregates", in Proceedings of SIGMOD, 1997, pp 159-170．
20 Chaudhuri, S., and Shim, K., "Including Group-By in Query Optimization", in Proceedings of VLDB, 1994, pp 354-366．
21 Gupta, A., Harinarayan, V., and Quass, D., "Aggregate-Query Processing in Data Warehousing Environments", in Proceedings of VLDB,
1995, pp 358-369．
22 effrey Scott Vitter ,Min Wang Approximate computation of multidimensional aggregates of sparse data using wavelets in Proceedings of the 1999 ACM SIGMOD international conference on Management of data Pages 193-204
23 Sin Yeung Lee, Tok Wang Ling, HuaGang Li Hierarchical compact cube for Range-Max Queries,in proceedings of vldb 2000 pp.232-241
24 H. Gupta, V. Harinarayan, A. Rajaraman, and J. Ullman,Index Selection for OLAP. In Proceedings of ICDE. pages 208-219． Burmingham, UK. April 1997．
25 M-C. Wu , A.P. Buchmann ,Encoded Bitmap Indexing for Data Warehouses. In proceedings of ICDE98
26 P. Furtado and P. Baumann .Storage of Multidimensional Arrays Based on Arbitrary Tiling In proceeding of ICDE99
27 Yannis Kotidis , Nick Roussopoulos, An alternative storage organization for ROLAP aggregate views based on cubetrees, sigmod'98
28 P. Deshpande, K. Ramasamy, A. Shukla, J.F. Naughton: Caching Multidimensional Queries Using Chunks. 1998． In Proc. ACM SIGMOD Conference, pp. 259-270． 1998．
29 Norbert Widmann, Peter Baumann: Performance Evaluation of Multidimensional Array Storage Techniques in Databases, Proceedings of the 1999 International Database Engineering and Applications Symposium,
Montreal, Canada, August 1999
30 Elena Baralis, Stefano Paraboschi, Ernest Teniente, "Materialized View Selection in a Multidimensional Database", in Proceedings of the 23rd VLDB Conference Athens, Greece, 1997．
31 Paolo Atzeni, Giansalvatore Mecca. Paolo Merialdo, " To Weave the Web", in Proceedings of the 23rd VLDB Conference Athens, Greece, 1997．
32 Dalian Quass, Jennifer Widom, " On-Line Warehouse View Maintenance", in Proceedings of ACM SIGMOD97 pp 393-404
33 Wilburt Juan Labio, Jun Yang, Yingwei Cui, Hector Garcia-Molina, Jennifer Widom. performance Issues Incremental Warehouse Maintenance ,in proceedings of V1DB 2000 pp 461-472
34 Yannis Kotidis and Nick Roussopoulos, a dynamic view management system for data warehouses in proceedings of sigmod 99 pp371-382
35 Wiener, J.L, Gupta,H., Labio,W.J. et al. "A system prototype for warehouse view maintenance", in Proceedings of ACM Workshop on Materialized Views: Techniques and Applications, Canada, 1996．
36 Inmon,W.H., "EIS and the data warehouse: a simple approach to building an foundation for EIS", Database Programming and Design,Nov. 1992,5(11) :70-73
37 Guo, Yi-bin, "The basic concepts and current development on data warehousing technique", PC World China, 1996,4(total 114) :26-31
38 Hammer，J．，Garcia-Molina，H．，Widom，J．，et al．，“The stanford data warehousing project”，IEEE Data Engineering Bulletin(Special Issue on Materialized Views and Data Warehousing)，June 1995，18(2) ：41-48
39 Jagadish，H．V．， Narayan，P．P．S．， Seshadri，S．， Sudarshan，S．， Kanneganti，R．，“Incremental Organization for Data Recording and Warehousing”，in Proceedings of VLDB，1997．
40 Yingwei Cui and Jennifer Widom practical Lineage Tracing in Data warehouse Technical report Department of Computer Science，Stanford university 1999
41 Andrey balmin Yannis Papakonstantinou Thnaos Papadimitriou．optimization of Hypothetical Queries in an OLAP Environment in proceeding of ICDE 2000
42 宋擒豹，沈钧毅，数据仓库体系结构研究，第十六届全国数据库 学术会议论文集，1999
43 陈海文，杨燕燕，邵维忠，数据仓库体系结构研究，第十四届全 国数据库学术会议论文集，四川大学出版社，1997。
44 刘欣，左，李通，杨璐，唐常杰 数据立方的聚集计算，第十六 届全国数据库学术会议论文集，1999
45 裴健，赵畅，柴玮，杨冬青，唐世渭 联机分析处理的数据立方体 的代数描述，第十六届全国数据库学术会议论文集，1999
46 王大威，李建中．基于并行属性划分存储结构的并行聚集算法．计算 机科学．2000，第27卷：178-181
47 S.Chaudhuri and K.Shim. Including groupby in query optimization. In Proceedings of the 20th International Conference on Very Large Databases, Pages 354-366,Chile, September 1994
48 S.Ceri and J.Widom. Deriving production rules for incremental view maintenance.In Proceedings of the Seventeenth International Conference on Very Large Databases, Pages 108-119, Spain, September 1991
49 J.Gray, A.Bosworth, A.Layman, and H.Pirahesh. Data cube: A relational aggregation operator generalizing group-by, cross-tal, and subtotal. In Proceedings of the Twelfth IEEE International Conference on Data Engineering, pages 152-159,New Orleans, LA, February 26-March 1 1996．
50 A.Gupta, V.Harinarayan, and D.Quass. Generalized projections: A powerful approach to aggregation. In Dayal et al.
2 李建中，孙文隽．并行关系数据库管理系统引论．科学出版社，1998．
3 李建中，王珊．数据库系统原理．电子工业出版社，1999．
4 Inmon，W．H．，Building the Data Warehouse．John Whiley，1992．
5 Codd，E．F．，Codd，S．B．,and Salley，C．T．，“Providing OLAP (on-line analytical processing)to useranalysis：an IT mandate，Technical Report， E．F．Codd and Associates，1993．
6 Erickson，C．G．，“Multidimensional and the data warehouse”,in The Data Warehousing Conference，Orlando．FL．February．1995．
7 Colliat，G．,"OLAR, relational and multidimensional database systems”, Technical Report，Arbor Software Corporation．Sunnyvale，CA．
8 Li，C．and Wang，X．S．，“A data model for supporting on-line analytical processing”，in Proccedings of Information and Knowledge Management，Baltimore，MD，1996．
9 R．Agrawal，A．Gupta，S．Sarawagi，ModelingMultidimensional Database [C]．ICDE’97
10 Luca Cabibbo，Riccardo Torlone，Querying Multidimensional Databases [C]．DBPL’97
11 Mare Gyssens．L．V．S．LAK shmanan．A Foundation for Multidimensional Databases[C]．VLDB’97
12． Lehner．Modeling Large Scale OLAP Scenariosl[C]．EDBT’98
White,C., "Data warehouse: what's in a name?", Database Programming and Design, Mar. 1996, 9(3) :53-54
13 Hong, J., "The construction and application of a data warehouse", China Computer Users, 1996,20:6-11
14 dom J., "Research problems in data warehousing", in Proceedings of the 4th International Conference on Information and Knowledge Management. Baltimore, Maryland, Nov. 1995． 25-30
15 Gray,J., Bosworth, A., Layman, A., and Pirahesh,H., "Data cube: a relational aggregation operator generalizing group-by, crosstabs. and subtotals", Proceedings of IEEE Data Eng., Nwe Orleans, 1996．
16 grawal, R., et al., "On the computation of multidimensional aggregates", in Proceedings of VLDB, Mumbai. India, Sept. 1996．
17 Harinarayanan, V., Rajaraman, A., and Ullman, J.D., "Implementing data cubes efficiently", in Proceedings of SIGMOD, 1996, pp 205-216．
18 Ross, K.A. and Srivastava, D., "Fast Computation of Sparse Datacubes", in Proceedings of VLDB, 1997, pp. 116-125．
19 Zhao, Y., Deshpande, P.M., and Naughton, J.F, "An array-based algorithm for simultaneous multidimentional aggregates", in Proceedings of SIGMOD, 1997, pp 159-170．
20 Chaudhuri, S., and Shim, K., "Including Group-By in Query Optimization", in Proceedings of VLDB, 1994, pp 354-366．
21 Gupta, A., Harinarayan, V., and Quass, D., "Aggregate-Query Processing in Data Warehousing Environments", in Proceedings of VLDB,
1995, pp 358-369．
22 effrey Scott Vitter ,Min Wang Approximate computation of multidimensional aggregates of sparse data using wavelets in Proceedings of the 1999 ACM SIGMOD international conference on Management of data Pages 193-204
23 Sin Yeung Lee, Tok Wang Ling, HuaGang Li Hierarchical compact cube for Range-Max Queries,in proceedings of vldb 2000 pp.232-241
24 H. Gupta, V. Harinarayan, A. Rajaraman, and J. Ullman,Index Selection for OLAP. In Proceedings of ICDE. pages 208-219． Burmingham, UK. April 1997．
25 M-C. Wu , A.P. Buchmann ,Encoded Bitmap Indexing for Data Warehouses. In proceedings of ICDE98
26 P. Furtado and P. Baumann .Storage of Multidimensional Arrays Based on Arbitrary Tiling In proceeding of ICDE99
27 Yannis Kotidis , Nick Roussopoulos, An alternative storage organization for ROLAP aggregate views based on cubetrees, sigmod'98
28 P. Deshpande, K. Ramasamy, A. Shukla, J.F. Naughton: Caching Multidimensional Queries Using Chunks. 1998． In Proc. ACM SIGMOD Conference, pp. 259-270． 1998．
29 Norbert Widmann, Peter Baumann: Performance Evaluation of Multidimensional Array Storage Techniques in Databases, Proceedings of the 1999 International Database Engineering and Applications Symposium,
Montreal, Canada, August 1999
30 Elena Baralis, Stefano Paraboschi, Ernest Teniente, "Materialized View Selection in a Multidimensional Database", in Proceedings of the 23rd VLDB Conference Athens, Greece, 1997．
31 Paolo Atzeni, Giansalvatore Mecca. Paolo Merialdo, " To Weave the Web", in Proceedings of the 23rd VLDB Conference Athens, Greece, 1997．
32 Dalian Quass, Jennifer Widom, " On-Line Warehouse View Maintenance", in Proceedings of ACM SIGMOD97 pp 393-404
33 Wilburt Juan Labio, Jun Yang, Yingwei Cui, Hector Garcia-Molina, Jennifer Widom. performance Issues Incremental Warehouse Maintenance ,in proceedings of V1DB 2000 pp 461-472
34 Yannis Kotidis and Nick Roussopoulos, a dynamic view management system for data warehouses in proceedings of sigmod 99 pp371-382
35 Wiener, J.L, Gupta,H., Labio,W.J. et al. "A system prototype for warehouse view maintenance", in Proceedings of ACM Workshop on Materialized Views: Techniques and Applications, Canada, 1996．
36 Inmon,W.H., "EIS and the data warehouse: a simple approach to building an foundation for EIS", Database Programming and Design,Nov. 1992,5(11) :70-73
37 Guo, Yi-bin, "The basic concepts and current development on data warehousing technique", PC World China, 1996,4(total 114) :26-31
38 Hammer，J．，Garcia-Molina，H．，Widom，J．，et al．，“The stanford data warehousing project”，IEEE Data Engineering Bulletin(Special Issue on Materialized Views and Data Warehousing)，June 1995，18(2) ：41-48
39 Jagadish，H．V．， Narayan，P．P．S．， Seshadri，S．， Sudarshan，S．， Kanneganti，R．，“Incremental Organization for Data Recording and Warehousing”，in Proceedings of VLDB，1997．
40 Yingwei Cui and Jennifer Widom practical Lineage Tracing in Data warehouse Technical report Department of Computer Science，Stanford university 1999
41 Andrey balmin Yannis Papakonstantinou Thnaos Papadimitriou．optimization of Hypothetical Queries in an OLAP Environment in proceeding of ICDE 2000
42 宋擒豹，沈钧毅，数据仓库体系结构研究，第十六届全国数据库 学术会议论文集，1999
43 陈海文，杨燕燕，邵维忠，数据仓库体系结构研究，第十四届全 国数据库学术会议论文集，四川大学出版社，1997。
44 刘欣，左，李通，杨璐，唐常杰 数据立方的聚集计算，第十六 届全国数据库学术会议论文集，1999
45 裴健，赵畅，柴玮，杨冬青，唐世渭 联机分析处理的数据立方体 的代数描述，第十六届全国数据库学术会议论文集，1999
46 王大威，李建中．基于并行属性划分存储结构的并行聚集算法．计算 机科学．2000，第27卷：178-181
47 S.Chaudhuri and K.Shim. Including groupby in query optimization. In Proceedings of the 20th International Conference on Very Large Databases, Pages 354-366,Chile, September 1994
48 S.Ceri and J.Widom. Deriving production rules for incremental view maintenance.In Proceedings of the Seventeenth International Conference on Very Large Databases, Pages 108-119, Spain, September 1991
49 J.Gray, A.Bosworth, A.Layman, and H.Pirahesh. Data cube: A relational aggregation operator generalizing group-by, cross-tal, and subtotal. In Proceedings of the Twelfth IEEE International Conference on Data Engineering, pages 152-159,New Orleans, LA, February 26-March 1 1996．
50 A.Gupta, V.Harinarayan, and D.Quass. Generalized projections: A powerful approach to aggregation. In Dayal et al.