基于集合運算的數(shù)據(jù)立方體結(jié)構(gòu)

摘要：提出一種新的數(shù)據(jù)立方體結(jié)構(gòu)，通過索引和集合的交并運算來獲得查詢結(jié)果，特別是在進行區(qū)域查詢時，避免了將區(qū)域分解為點后再依次進行點查詢的方式，從而在保持較少的磁盤空間和較好的點查詢響應速度的情況下，改善區(qū)域查詢的性能；同時給出其生成和查詢算法，并使用合成數(shù)據(jù)和實際數(shù)據(jù)進行了實驗驗證。

關鍵詞:數(shù)據(jù)倉庫； 數(shù)據(jù)立方體； 聯(lián)機分析處理； 區(qū)域查詢; 集合運算

中圖分類號：TP311文獻標志碼：A

文章編號：1001-3695(2007)11-0225-03

0引言

Date cube[1]是OLAP一個非常重要的操作符。雖然數(shù)據(jù)立方體預計算并保存查詢結(jié)果，能夠提高查詢響應速度，但也存在著很大的問題：占用巨大的磁盤空間、維護工作量大且不能很好地適用于高維的情況。到目前為止，研究者們提出了四類解決方法：a)部分視圖型數(shù)據(jù)立方體。在給定的存儲空間約束或維護時間約束下，有選擇地實例化數(shù)據(jù)立方體中的部分視圖，但查詢響應時間比數(shù)據(jù)立方體長。b)近似計算型數(shù)據(jù)立方體。利用柱狀圖和小波變換技術壓縮數(shù)據(jù)立方體，但得到的查詢結(jié)果是近似的。c)元組共享型數(shù)據(jù)立方體。例如condensed cube[2]、quotient cube[3]、封閉立方體[4]、FreeCube[5]，利用元組共享原理只實例化數(shù)據(jù)立方體視圖中的某些元組，對稀疏型數(shù)據(jù)立方體有很高的壓縮比，但查詢響應時間仍較長。d)特殊存儲結(jié)構(gòu)型數(shù)據(jù)立方體。采用R－tree或prefix tree結(jié)構(gòu)來組織數(shù)據(jù)立方體中的元組，如cubetrees[6]和dwarf[7]，然而維數(shù)越大，其查詢性能越不好。在上述四類方法中，元組共享型數(shù)據(jù)立方體具有較好的綜合性能：精確的查詢結(jié)果；很高的數(shù)據(jù)壓縮比；較短的查詢響應時間。然而它們在進行區(qū)域查詢時，將區(qū)域分解為點，然后進行點查詢，使得一個區(qū)域查詢相當于大量的點查詢，也就導致了查詢效率較低。為此，本文提出一種部分視圖的數(shù)據(jù)立方體的概念，在保持與它們類似的空間性能和點查詢響應速度的情況下，提高區(qū)域查詢的速度。

在該立方體結(jié)構(gòu)中進行查詢，其主要時間開銷來自于各維值基本元組索引集的交并運算。其中并運算只出現(xiàn)在區(qū)域查詢中。在其他的立方體存儲結(jié)構(gòu)中，對于區(qū)域查詢，都是對區(qū)域查詢條件中的區(qū)域部分進行分解，查詢每個點的聚集值，然后再匯總。隨著區(qū)間的維數(shù)增加和查詢區(qū)間的增大，區(qū)域查詢響應時間也就必然迅速增加。在本文提出的立方體結(jié)構(gòu)中的區(qū)域維上，先對各區(qū)間維值的基本元組索引集進行并運算，然后一次性地進行所有維集合的交運算。如果在某區(qū)域維的前一維上非all，那么對于該區(qū)域維的并運算也不需要，可以直接在前一維上找到這些區(qū)域維值相對應的序號，無論是并運算還是直接獲取這些元組序號，以及通過求補集的方法來求交集，都能夠明顯提高整個區(qū)域查詢的效率。這也就是該存儲結(jié)構(gòu)所特有的地方。

4結(jié)束語

本文提出的立方體結(jié)構(gòu)是一個部分數(shù)據(jù)立方體，它大大壓縮了數(shù)據(jù)立方體的體積，盡管只給出了部分視圖，但因為采用索引方式，可以較快地讀取數(shù)據(jù)；同時因為運用集合交并補運算，使得區(qū)域查詢有較好的查詢響應時間。筆者今后的主要工作是進一步優(yōu)化該結(jié)構(gòu)和算法，考慮如何在空間壓縮率和查詢性能上取得更好的平衡。例如在實例化視圖時，適當增加經(jīng)常用到的非相鄰維的方體，改進求交算法，在索引的情況下進行求交運算等，使得在能夠接受的空間壓縮條件下進一步提高查詢響應速度。

參考文獻:

[1]GRAY J， BOSWORTH A， LAYMAN A， et al. Data cube: a relational aggregation operator generalizing group－by， cross－tab， and sub－totals[C]//Proc of the 12th Int’l Conf on Data Engineering.New Orleans: [s.n.]， 1996:152－159.

[2]WANG Wei， FENG Jian－lin， LU Hong－jun， et al. Condensed cube: an effective approach to reducing data cube size[C]//Proc of the 18th Int’l Conf on Data Engineering. San Jose: [s.n.]， 2002:155－165.

[3]LAKSHMANAN L V S， PEI J， HAN J W. Quotient cube: how to summarize the semantics of a data cube[C]//Proc of the 23rd Int’l Conf on Very Large Data Bases.Hong Kong: [s.n.]，2002：778-789.

[4]李盛恩，王珊.封閉數(shù)據(jù)立方體技術研究［J］.軟件學報，2004，15(8):1165－1171.

[5]孫延凡，陳紅，王珊. FreeCube:有效減小Data Cube體積［J］.計算機科學，2003，30 (增刊):241-245.

[6]ROUSSOPOULOS N， KOTIDIS Y， et al. Cubetree: organization of and bulk incremental updates on the data cube[C]//Proc of SIGMOD’97. Tucson: ACM Press，1997:89-99.

[7]SISMANIS Y， DELIGIANNAKIS A， ROUSSOPOULOS N， et al.Dwarf: shrinking the PetaCube[C]//Proc of SIGMOD 2002. Madison: ACM Press， 2002:464-475.

[8]LAKSHMANAN L V S， PEI J， ZHAO Y. QC－trees: an efficient summary structure for semantic OLAP[C]//Proc of SIGMOD. San Diego: ACM press， 2003:64-75.

[9]GRAY J， BARKHATOV A. DBGen synthetic data generator for SQL tables and text files on Windows platforms[C]//GRAY J， SUNDARESAN P， ENGLERT S. Proc of SIGMOD. Minneapolis: ACM Press， 1994:243-252.

[10]HAHN C， WARREN S， LONDON J. Edited synoptic cloud reports from ships and land stations over the globe[EB/OL].http://cdiac.esd.ornl.gov/cdiac/ndps/ndp026b.html.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”