範圍查詢近似總和之動態資料方體

The Dynamic Data Cubes for Approximate Range-Sum Queries

陳佳揚(Chia-Yang Chen)

指導教授 ： 劉俞志

元智大學/資訊學院/資訊管理學系/碩士(2002年)

摘要

在OLAP系統中，常使用多維度的設計來檢視資料庫中彙總的資料，這種多維度呈現資料的結構便是所謂的資料方體(data cube)。然而，由於資料庫系統持續發展與使用時間的增長，所需建構資料方體的空間也隨之增大，連帶影響多維度資料分析系統於範圍查詢的效能。許多研究針對範圍值的查詢提出各種資料方體總和值儲存結構，以改善其在更新與查詢時的時間成本。這些方法多著重在範圍查詢精確結果之計算，但是，在一般決策性之資料分析上往往僅需要大約值即可，耗費成本的精確值計算並不符合效益需求。
因此，本研究針對範圍查詢下之總和近似值，應用前置總和(Prefixed Sum)與方體切割之觀念，提出新的資料儲存模式，此方法主要在應用樹狀結構的層狀架構與動態更新特性，預儲資料方體之總和查詢值，以改善資料方體所需之儲存空間與使用者在範圍查詢時之時間成本及資料更新成本。此外，我們並針對此法提出修正，使其可適用於稀疏性資料方體，並可透過資料結構的設定提供精確值與近似值之混合查詢技術及其他聚合函數的查詢。

關鍵字

範圍總和近似值 ； 範圍查詢 ； 資料方體

並列摘要

In OLAP systems, the multi-dimension design is frequently utilized to view the queried results in the database. This multi-dimensional structure is so- called “Data Cube”. Owing to growing up of historical data , efficiency of answering range query is one topic of database systems. Most of literatures are focused on querying accurate values regardless of approximations. However, approximate results are sufficient to support analysis of some decision support systems and accurate results are inefficient.
This article presents new data structures which combine the prefix sum model and the recursive method to save the storage and shorten the update time. In the structures, we can support a dynamic environment for users to query and update data. Furthermore, we amend some defects to make the structure suitable for the sparse data cube, and could provide accurate and approximate mixed query technologies by the proper settings of the data structure. Other aggregate functions, such as Min and Max, could fit this amended structure.

並列關鍵字

Range Approximate Sum Query ； Range Query ； Data Cubes

參考文獻

[1.] J. Gray, A. Bosworth, A. Layman, and H. Pirahesh. “Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals”, In Proc. IEEE Intl. Conf. on Data Engineering, pages 152—159,1996.

[7.] S. Geffner, D. Agrawal, A. El Abbadi, and T. Smith. “Relative prefix sums: An efficient approach for querying dynamic OLAP data cubes”. In Proc. 15th ICDE Conf., pages 328-335, 1999.

[9.] M. Riedewald, D. Agrawal, and A. El Abbadi. “pCube Update-effcient online aggregation with progressive feedback and error bounds”, In Proc. Int. Conf. SSDBM, pages 95-108, 2000.

[12.] Y. Zhao, P. M. Deshpande, and J. F. Naughton. “An Array-Based Algorithm for Simultaneous Multidimensional Aggregates”. In Proc. of the ACM SIGMOD Conference on the Management of Data, pages 159-170, 1997

[13.] V. Harinarayan, A. Rajaraman, J. D. Ullman, “Implementing Data Cubes Efficiently”. ACM SIGMOD, pages 205-216, 1996.