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

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

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

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

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

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

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

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

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

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