高性能數(shù)據(jù)立方體及其語義研究.pdf

1、數(shù)據(jù)立方體技術是聯(lián)機分析處理的主要手段。隨著數(shù)據(jù)規(guī)模的擴大和維數(shù)的增加，數(shù)據(jù)立方體的操作代價急劇增加，需要進行優(yōu)化處理。目前數(shù)據(jù)立方體的研究包括：物化、索引、近似、壓縮、約簡以及聯(lián)機聚集等。
　　 形式概念分析理論(FCA)是以形式化的概念和概念層次為基礎的數(shù)學分析工具。研究發(fā)現(xiàn)，概念格作為FCA的核心結構與數(shù)據(jù)立方體格都基于序結構，并且以數(shù)據(jù)倉庫中的基本表作為形式背景，F(xiàn)CA理論中與概念相對應的等價特征組與數(shù)據(jù)立方體的覆蓋等價

2、類對數(shù)據(jù)單元具有相同的劃分結果。本文將FCA和概念格理論引入數(shù)據(jù)立方體的研究，進行高性能數(shù)據(jù)立方體及其語義研究。研究表明，F(xiàn)CA及相關理論的引入，為數(shù)據(jù)立方體研究提供了一個新的有力的分析工具，利用該工具可以從數(shù)據(jù)內部特性入手，實現(xiàn)結構簡單、體積較小且性能較優(yōu)的數(shù)據(jù)立方體，并使數(shù)據(jù)立方體語義的理解更深刻，更易于實現(xiàn)。主要的研究工作如下：
　　 (1)提出基于形式概念格結構表達的數(shù)據(jù)立方體。
　　 首先對數(shù)據(jù)立方體與形式概念

3、格進行相關分析，以概念格結構表達數(shù)據(jù)立方體，提出聚集概念和聚集概念格結構(ACL)。ACL是一種完全的數(shù)據(jù)立方體結構，由于其內具有相同聚集值的若干單元用一個聚集概念表示，因此能實現(xiàn)與商立方體相同的約簡。另外，ACL結構中概念間的泛化和例化關系反映了約簡后數(shù)據(jù)之間的層次關聯(lián)，可表達比商立方體更清晰的數(shù)據(jù)立方體語義關系。
　　 其次，在ACL基礎上，本文提出約簡聚集概念結構(RAC)?；谛问礁拍罘治隼碚撝蠫偏序關系的性質研究發(fā)現(xiàn)，

4、由于基本表的完備性，基本表中各個元組與ACL結構中的對象概念一一對應，因此基本表可以看作是所有對象概念的集合。RAC結構對ACL進一步約簡，去除所有對象概念和特殊概念(Ω，null)。與基本表聯(lián)合，RAC仍然是完全的立方體結構，但能實現(xiàn)比商立方體和ACL結構更大的約簡，且仍能保持所有非對象聚集概念之間的語義關系。
　　 第三，基于形式概念分析理論中M偏序集的性質，提出基于ACL和RAC高效的查詢方法。該方法利用屬性概念內涵m"確

5、定在ACL和 RAC上的查詢搜索路徑，避免全范圍的搜索，查詢效率較高。
　　 最后，對形式背景進行討論，將概念格的屬性約簡理論應用于數(shù)據(jù)立方體，通過合并相對必要屬性、刪除絕對不必要屬性實現(xiàn)形式背景的簡化，最終實現(xiàn)數(shù)據(jù)立方體相關操作的簡化。
　　 (2)研究形式背景的屬性蘊含關系，采用關系系統(tǒng)存儲，提出基于屬性蘊含的約簡聚集概念數(shù)據(jù)立方體結構(RAC-AI)。
　　 根據(jù)形式概念分析理論，研究形式背景中描述概念格的

6、兩類非平凡屬性蘊含：前提是偽內涵的蘊含和前提是真前提的蘊含。研究通過屬性蘊含而不再依賴概念格結構確定概念內涵。在RAC結構基礎上，提出兩種基于屬性蘊含的約簡聚集概念數(shù)據(jù)立方體結構(RAC-AI)：基于前提是偽內涵和基于前提是真前提的RAC-AI結構。RAC-AI結構摒棄RAC復雜的概念格結構，增加屬性蘊含表，記錄形式背景中所有非平凡的蘊含，并采用主流的關系系統(tǒng)存儲所有非對象聚集概念。理論分析和實驗結果表明，RAC-AI體積小，結構簡單，

7、構建和增量維護代價較低，查詢響應速度也較快，是目前綜合性能較優(yōu)的數(shù)據(jù)立方體。
　　 (3)數(shù)據(jù)立方體語義關系的挖掘和應用直接影響聯(lián)機分析處理的各種操作。本文研究基于FCA和概念格理論的數(shù)據(jù)立方體語義操作實現(xiàn)。
　　 首先討論形式背景的凈化和約簡，消除形式背景中的冗余信息?，F(xiàn)有的數(shù)據(jù)立方體語義研究都未考慮對數(shù)據(jù)本身進行約簡，大量冗余信息的存在干擾了對語義的理解和發(fā)現(xiàn)。
　　 其次，利用形式概念分析的M偏序集理論，將

8、M偏序關系作為生成概念分層的一種啟發(fā)式的規(guī)則，形成屬性級別的概念分層語義，而現(xiàn)有的概念分層一般只進行到維級別。
　　 第三，利用M偏序關系和非平凡的屬性蘊含，實現(xiàn)數(shù)據(jù)立方體單元之間的上卷和下鉆語義操作。通過分析等價特征組上界和下界的特性，獲得等價特征組的結構，實現(xiàn)具有相同聚集值單元之間的上卷和下鉆語義操作。利用非平凡的屬性蘊含獲取任意概念的父概念和子概念的內涵，實現(xiàn)不同聚集值單元的上卷和下鉆語義操作。該方法不依賴任何特殊結構，實

9、現(xiàn)從數(shù)據(jù)立方體任意單元出發(fā)的上卷和下鉆操作，重復這個過程，能在數(shù)據(jù)立方體格中漫游，而不必生成完整的數(shù)據(jù)立方體。現(xiàn)有的數(shù)據(jù)立方體上卷和下鉆語義操作一般只進行到視圖級別，能達到單元級別的一般要依賴復雜特殊的結構實現(xiàn)。
　　 (4)范圍查詢是應用于多維數(shù)據(jù)立方體的有效的分析工具，預計算技術是提高范圍查詢響應速度的一種方法。本文在現(xiàn)有prefix sum技術和分塊技術基礎上，提出基于前綴區(qū)域的不規(guī)則方體的分塊方法PRC，這種分塊方法利于