（計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)論文）網(wǎng)絡(luò)安全olap分析中數(shù)據(jù)立方體技術(shù)的研究與實(shí)現(xiàn).pdf

國(guó)防科學(xué)技術(shù)大學(xué)研究生院碩士學(xué)位論文 摘要 互聯(lián)網(wǎng)正在成為國(guó)家關(guān)鍵信息基礎(chǔ)設(shè)施，事關(guān)國(guó)家和全社會(huì)的根本利益。隨 著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，針對(duì)網(wǎng)絡(luò)信息系統(tǒng)的惡意攻擊正向著分布化、規(guī)?；?復(fù)雜化、間接化等趨勢(shì)發(fā)展。因此迫切需要研究新的技術(shù)以實(shí)現(xiàn)對(duì)大規(guī)模網(wǎng)絡(luò)信 息系統(tǒng)的安全態(tài)勢(shì)進(jìn)行實(shí)時(shí)、準(zhǔn)確的感知、監(jiān)控和分析。如何在復(fù)雜的海量監(jiān)測(cè) 數(shù)據(jù)中對(duì)當(dāng)前的網(wǎng)絡(luò)安全狀態(tài)進(jìn)行獲取、理解，發(fā)現(xiàn)潛在的變化趨勢(shì)，從而把握 大規(guī)模網(wǎng)絡(luò)的宏觀安全態(tài)勢(shì)，是我們研究工作的出發(fā)點(diǎn)。 聯(lián)機(jī)分析處理( o l a p ) 技術(shù)是實(shí)現(xiàn)對(duì)大規(guī)模網(wǎng)絡(luò)監(jiān)測(cè)數(shù)據(jù)進(jìn)行近實(shí)時(shí)綜合分析 的重要手段。o l a p 通過(guò)對(duì)信息的多種可能的觀察形式進(jìn)行快速、穩(wěn)定一致和交互 性的存取，允許管理決策人員對(duì)數(shù)據(jù)進(jìn)行深入觀察，具有極大的分析靈活性。 數(shù)據(jù)立方體的有效計(jì)算是支撐o l a p 分析的關(guān)鍵。只有預(yù)先計(jì)算數(shù)據(jù)立方體 的全部或部分，才能大幅度降低查詢響應(yīng)時(shí)間，提供聯(lián)機(jī)分析處理的性能。如何 在存儲(chǔ)容量、計(jì)算能力的限制下，尋找到計(jì)算部分?jǐn)?shù)據(jù)立方體的可伸縮的辦法， 在數(shù)據(jù)立方體的時(shí)空開銷和查詢響應(yīng)性能之間進(jìn)行微妙的折中，是本文工作的核 心問(wèn)題。 基于網(wǎng)絡(luò)安全態(tài)勢(shì)的感知、監(jiān)控和分析對(duì)實(shí)時(shí)性的需求，本文研究了數(shù)據(jù)流 上的聯(lián)機(jī)分析處理。數(shù)據(jù)流上數(shù)據(jù)立方體的計(jì)算其時(shí)空條件更加苛刻，研究有限 時(shí)空條件下數(shù)據(jù)流立方體的部分物化方法，是本文工作的重點(diǎn)。 本文的主要工作概述如下： 1 介紹了數(shù)據(jù)立方體的基本概念和模型定義，討論了數(shù)據(jù)立方體的實(shí)現(xiàn)方案， 對(duì)各種數(shù)據(jù)立方體計(jì)算算法做了總結(jié)和深入分析。 2 分析了數(shù)據(jù)流上的聯(lián)機(jī)分析處理的特點(diǎn)，總結(jié)了數(shù)據(jù)流立方體的設(shè)計(jì)需求， 提出了多層次傾斜窗口模型，在有限的時(shí)空條件下通過(guò)時(shí)間維有效的壓縮了數(shù)據(jù) 流立方體的體積。 3 提出了一種新的數(shù)據(jù)流立方體部分物化方法一基于d w a r f 結(jié)構(gòu)的多維數(shù)據(jù) 流立方體框架s t r e a m d w a r f ，并給出相應(yīng)的計(jì)算算法，包括增量更新算法和查詢算 法，并對(duì)算法進(jìn)行實(shí)現(xiàn)，給出實(shí)驗(yàn)測(cè)試結(jié)果。 4 研究開發(fā)了基于s t a r o l a p 平臺(tái)的網(wǎng)絡(luò)安全態(tài)勢(shì)分析系統(tǒng)，實(shí)現(xiàn)了對(duì)海量 網(wǎng)絡(luò)安全監(jiān)測(cè)數(shù)據(jù)的多維多層次、近實(shí)時(shí)的綜合分析。 關(guān)鍵詞：數(shù)據(jù)立方體，0 l a p ，數(shù)據(jù)流立方體，s t r e a m d w a r f ，網(wǎng)絡(luò)安全態(tài)勢(shì) 惑知 第i 頁(yè) 國(guó)防科學(xué)技術(shù)大學(xué)研究生院碩士學(xué)位論文 a b s t r a c t i n t e m e th a sb e c o m et h ek e yi n f o r m a t i o nf a c i l i t yo fo u rc o u n t r y w i t ht h er a p i d d e v e l o p m e n to fi n t e r n e tt e c h n o l o g y , v i c i o u sa t t a c k sa g a i n s tn e t w o r ki n f o r m a t i o ns y s t e m t e n dt ob ed i s t r i b u t e d , c o m p l i c a t e d ，i n d i r e c ta n ds c a l a b l e t h u si t si m p e n d i n g l y r e q u i r e d t or e s e a r c hf o rn e w t e c h n o l o g yt oa c c u r a t e l ya c q u i r e ，m o n i t o ra n da n a l y z et h es e c u r i t y s i t u a t i o no fl a r g es c a l en e t w o r ks y s t e mi nr e a lt i m e f i g u r i n go u tm e t h o d st oa c q u i r ea n d i n t e r p r e tc u r r e n ts e c u r i t ys t a t eo ft h en e t w o r ka n dd i s c l o s et h eu n d e r l y i n gc h a n g e st o g r a s pt h eg e n e r a ls e c u r i t ys i t u a t i o ni sw h e r eo u rs t u d yb e g i n s o n l i n ea n a l y t i c a lp r o c e s s i n g ( o l a p ) i sa ni m p o r t a n tt e c h n o l o g yt od oi n t e g r a t e d a n a l y s i so nt h em a s s i v ea n dc o m p l i c a t e dn e t w o r km o n i t o r i n gd a t a b yr a p i d ，c o n s i s t e n t a n di n t e r a c t i v ea c c e s so fi n f o r m a t i o nf r o mv a r i o u sp o s s i b l ev i e w p o i n t s ，o l a pa l l o w s t h ea n a l y s t st oo b s e r v ed a t ai nd e p t h ，p r o v i d i n gg r e a t ef l e x i b i l i t y e f f i c i e n tc o m p u t a t i o no fd a t ac u b ei st h ek e yt os u p p o r to l a pa n a l y s i s t og e t o l a p c a p a b i l i t y , w eh a v et op r e c o m p u t et h ew h o l eo ra tl e a s tp a r t i a ld a t ac u b ei no r d e r t or e d u c et h eq u e r yr e s p o n s et i m e t h ec o r ep r o b l e mo fo u rs t u d yi st of i n do u ts c a l a b l e t e c h n i q u e s t oc o m p u t ep a r t i a ld a t ac u b eu n d e rr e s t r a i n t so fs t o r a g es p a c ea n d c o m p u t a t i o np o w e rt og e tab a l a n c eb e t w e e nd a t ac u b e sc o m p u t a t i o n & s t o r a g ec o s ta n d q u e r yr e s p o n s et i m e s i n c et h ea c q u i r e m e n t ，m o n i t o r i n ga n da n a l y s i so fn e t w o r ks e c u r i t ys i t u a t i o ni s o f t e nr e q u i r e dt ob ed o n ei nr e a lt i m e ，w ep r o c e e dt ot h es t u d yo fo n l i n ea n a l y t i c a l p r o c e s s i n go nr a p i dc h a n g i n gs t r e a m s w i t hs t r e a m s ，t h ed a t ac u b ec o m p u t a t i o nh a sa m o r er i g o r o u sr e s t r i c to nc o m p u t a t i o nt i m ea n ds t o r a g es p a c e s t u d y i n gp a r t i a l m a t e r i a l i z a t i o nt e c h n i q u e so fs t r e a mc u b eu n d e rr e s t r a i n t si st h ee m p h a s e so fo u rw o r k w es u m m a r i z eo u rw o r ka sf o l l o w f i r s t b a s i c c o n c e p t so fd a t a c u b ea r ei n t r o d u c e dw i t hd i s c u s s i o no fi t s i m p l e m e n t a t i o ns c h e m e sf o l l o w e d s e c o n d ，t h ec h a r a c t e r i s t i c so fo n l i n ea n a l i t i c a lp r o c e s s i n go nd a t as t r e a m s ，a n d t h ed e s i g nr e q u i r e m e n t so fs t r e a mc u b ea r ea n a l y z e d t h e nah i e r a r c h i c a lt i l t e dw i n d o w m o d e l ，w h i c hd e c r e a s e st h es i z eo fs t r e a mc u b et oa d a p tt ot h ec o m p u t a t i o na n ds t o r a g e c o n s t r a i n t s ，i sp r o p o s e d t h i r d ，an e wm e t h o df o rp a r t i a lm a t e r i a l i z a t i o no fs t r e a mc u b e ，ad w a r f - b a s e d s t r e a mc u b ef r a m e w o r kc a l l e ds t r e a m d w a r f , i sp r o p o s e d t h e c o r r e s p o n d i n g c o m p u t a t i o na l g o r i t h m s ，i n c l u d i n gi n c r e m e n t a lu p d a t ea l g o r i t h ma n dq u e r ya l g o r i t h m ， a r ed e v e l o p e d t h e nt h ea l g o r i t h m sa r ei m p l e m e n t e da n dt e s t i n gr e s u l t sa r ep r e s e n t e d a tl a s t ，ap r o t o t y p ef o rn e t w o r ks e c u r i t ys i t u a t i o na n a l y s i s ，w h i c hi sb a s e do n s t a r o l a pp l a t f o r ma n di sc a p a b l eo fm u l t i d i m e n s i o n a l m u l t i 1 e v e la n di n t e g r a t e d 第i i 頁(yè) 國(guó)防科學(xué)技術(shù)大學(xué)研究生院碩士學(xué)位論文 a n a l y s i so nt h em a s s i v en e t w o r km o n i t o r i n gd a t ai nr e a lt i m e ，i sd e v e l o p e d k e yw o r d s ：d a t ac u b e ，o l a p , s t r e a mc u b e ，s t r e a m d w a r f ，n e t w o r k s e c u r i t ys i t u a t i o na w a r e n e s s 第i i i 頁(yè) 國(guó)防科學(xué)技術(shù)大學(xué)研究生院碩士學(xué)位論文 表目錄 表2 1b u c 算法的偽代碼【1 4 】1 9 表2 2 按效益選擇物化視圖算法的偽代碼2 4 表2 3b p u s 算法的偽代碼2 4 表3 1 u p d a t e s t r e a m d w a r f 算法的偽代碼3 6 表3 2 u p d a t e d w a r f c u b e 算法的偽代碼3 7 表3 3q u e r y d w a r f c u b e 算法的偽代碼3 8 表4 1c u b e 元素定義4 6 表4 2d i m e n s i o n 元素定義4 7 表4 3j o i n 元素定義4 8 第1 i i 頁(yè) 國(guó)防科學(xué)技術(shù)大學(xué)研究生院碩士學(xué)位論文 圖目錄 圖1 1o l a p 體系結(jié)構(gòu)2 圖2 1 超市銷售數(shù)據(jù)立方體1 1 圖2 2 雪花模式13 圖2 3 數(shù)據(jù)立方體s a l e s 計(jì)算示圖1 5 圖2 4 立方體格圖1 6 圖2 5處理樹16 圖2 6b u c 處理樹2 0 圖2 7b u c 戈0 分。2 0 圖3 1時(shí)間域的多粒度劃分系列3 0 圖3 2 多層次傾斜窗口模型示意圖31 圖3 3d w a r f 子樹的元組一3 4 圖3 4d w a r f 子樹結(jié)構(gòu)3 4 圖3 5 更新后的d w a r f 子樹3 4 圖3 6 精簡(jiǎn)后的d w a r f 子樹3 5 圖3 7d w a r f 子樹粒度閾值的影響3 8 圖3 8 數(shù)據(jù)偏斜s k e w 對(duì)d w a r f 性能的影響一3 9 圖4 1s t a r o l a p 分層結(jié)構(gòu)4 2 圖4 2s t a r o a l p 實(shí)現(xiàn)框架：4 3 圖4 3 歷史數(shù)據(jù)多維分析5 0 圖4 4 流量曲線圖51 第1 v 頁(yè) 獨(dú)創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是我本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研 究成果盡我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他入已 經(jīng)發(fā)表和撰寫過(guò)的研究成果，也不包含為獲得國(guó)防科學(xué)技術(shù)大學(xué)或其它教育機(jī)構(gòu)的學(xué) 位或證書而使用過(guò)的材料與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文 中作了明確的說(shuō)明并表示謝意 學(xué)位論文題目 學(xué)位論文作者 學(xué)位論文版權(quán)使用授權(quán)書 本人完全了解國(guó)防科學(xué)技術(shù)大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定本人授權(quán)國(guó) 防科學(xué)技術(shù)大學(xué)可以保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子文檔，允 許論文被查閱和借閱；可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索， 可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文 ( 保密學(xué)位論文在解密后適用本授權(quán)書) 學(xué)位論文題目 學(xué)位論文作者 作者指導(dǎo)教師簽名： 塾! 塾! 圣日期：沁年1 2 月l8 日 國(guó)防科學(xué)技術(shù)大學(xué)研究生院碩士學(xué)位論文 第一章緒論 1 1 研究背景 互聯(lián)網(wǎng)正在成為國(guó)家關(guān)鍵信息基礎(chǔ)設(shè)施，事關(guān)國(guó)家和全社會(huì)的根本利益。隨 著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，針對(duì)網(wǎng)絡(luò)信息系統(tǒng)的惡意攻擊正向著分布化、規(guī)模化、 復(fù)雜化、間接化等趨勢(shì)發(fā)展。據(jù)估計(jì)，目前大約有5 8 ，0 0 0 多種已知病毒，它們的 存在嚴(yán)重地威脅著網(wǎng)絡(luò)信息系統(tǒng)的安全。著名的紅色代碼蠕蟲病毒在因特網(wǎng)上傳 播的最初9 小時(shí)內(nèi)就感染了超過(guò)2 5 萬(wàn)個(gè)計(jì)算機(jī)系統(tǒng)，造成的損失以每天2 億美元 的速度增長(zhǎng)，最終高達(dá)2 6 億美元。諸如此類的蠕蟲病毒以及d d o s 攻擊、惡意 代碼、僵尸網(wǎng)絡(luò)和網(wǎng)絡(luò)入侵等安全事件層出不窮，突顯出了現(xiàn)有網(wǎng)絡(luò)防御能力的 嚴(yán)重不足。因此迫切需要研究新的技術(shù)以實(shí)現(xiàn)對(duì)大規(guī)模網(wǎng)絡(luò)信息系統(tǒng)的宏觀安全 態(tài)勢(shì)進(jìn)行實(shí)時(shí)、準(zhǔn)確的感知、監(jiān)控和分析。 現(xiàn)有的網(wǎng)絡(luò)防護(hù)設(shè)施如n e t f l o w 采集器、i d s 入侵檢測(cè)系統(tǒng)、v d s 病毒檢測(cè) 系統(tǒng)、v s c a n n e r 漏洞掃描器和f i r e w a l l 防火墻等為獲取網(wǎng)絡(luò)的宏觀安全態(tài)勢(shì)提供 了不同的數(shù)據(jù)來(lái)源，但各種來(lái)源的數(shù)據(jù)結(jié)構(gòu)、內(nèi)容各異，難以對(duì)其進(jìn)行準(zhǔn)確的理 解。由于大規(guī)模網(wǎng)絡(luò)監(jiān)測(cè)數(shù)據(jù)的海量性，使得數(shù)據(jù)采集一般基于抽樣的方法，而 有用的數(shù)據(jù)往往淹沒在大量無(wú)用的數(shù)據(jù)中，使其在采樣時(shí)經(jīng)常被遺漏，從而造成 了數(shù)據(jù)的不完整性。這些問(wèn)題給網(wǎng)絡(luò)安全態(tài)勢(shì)的精確感知帶來(lái)了挑戰(zhàn)。如何在復(fù) 雜的海量監(jiān)測(cè)數(shù)據(jù)中對(duì)當(dāng)前的網(wǎng)絡(luò)安全狀態(tài)進(jìn)行獲取、理解，發(fā)現(xiàn)潛在的變化趨 勢(shì)，從而把握大規(guī)模網(wǎng)絡(luò)的宏觀安全態(tài)勢(shì)，是我們研究工作的出發(fā)點(diǎn)。 聯(lián)機(jī)分析處理( o l a p ) 技術(shù)是實(shí)現(xiàn)對(duì)大規(guī)模網(wǎng)絡(luò)監(jiān)測(cè)數(shù)據(jù)進(jìn)行近實(shí)時(shí)綜合分析 的重要手段。o l a p 通過(guò)對(duì)信息( 如網(wǎng)絡(luò)安全監(jiān)測(cè)數(shù)據(jù)) 的多種可能的觀察形式進(jìn)行 快速、穩(wěn)定一致和交互性的存取，允許管理決策人員( 如網(wǎng)絡(luò)安全管理人員) 對(duì) 數(shù)據(jù)進(jìn)行深入觀察。o l a p 展現(xiàn)在用戶面前的是一幅幅多維視圖。一旦多維的數(shù)據(jù) 立方體模型建立完成，用戶可以快速地從各個(gè)分析角度獲取數(shù)據(jù)，也能動(dòng)態(tài)的在 各個(gè)角度之間切換或者進(jìn)行多角度綜合分析，具有極大的分析靈活性。 o l a p 是一個(gè)復(fù)雜的系統(tǒng)，它從外部數(shù)據(jù)源提取數(shù)據(jù)，在多維數(shù)據(jù)庫(kù)中組織多 維數(shù)據(jù)，并提供復(fù)雜的前端分析工具從多維數(shù)據(jù)庫(kù)中提煉出對(duì)決策有價(jià)值的信息。 一般o l a p 系統(tǒng)的體系結(jié)構(gòu)如圖1 1 所示。 o l a p 系統(tǒng)的實(shí)現(xiàn)問(wèn)題包括上述體系結(jié)構(gòu)的各個(gè)方面，包括多維數(shù)據(jù)庫(kù)模型的 建立，數(shù)據(jù)源的抽取、轉(zhuǎn)換和加載( e t l ) ，多維數(shù)據(jù)的聚集計(jì)算等。本文關(guān)注的 是o l a p 系統(tǒng)實(shí)現(xiàn)的核心問(wèn)題：數(shù)據(jù)立方體( 即多維數(shù)據(jù)集) 的計(jì)算( 也稱為多 維數(shù)據(jù)的聚集、物化) 。 第1 頁(yè) 國(guó)防科學(xué)技術(shù)大學(xué)研究生院碩士學(xué)位論文 9 9 9 攆紛數(shù)搦j ! 竄= 日曰 曰囿印 努籟衍忽源 ，其中： ( 1 ) d 是維的集合，d = 矗，吐，吐，以一i ，一( 面d ，0 f n 一1 ) 表示第i 個(gè)維， 其值域?yàn)閐 o m ( d ，1 ，值域中不同值的個(gè)數(shù)c ( d i ) 稱為維的基數(shù)。 ( 2 ) m 是度量的集合，m = , n o ，m 1 ，腳2 ，州) ，n , ，( 研f m ，0 i k 一1 ) 表示第i 第1 1 頁(yè) 國(guó)防科學(xué)技術(shù)大學(xué)研究生院碩士學(xué)位論文 個(gè)度量，其值域?yàn)閐 o m ( m i ) 。維集和度量集是不相交的，即d n m = 。 ( 3 ) e 是數(shù)據(jù)立方體中單元的集合，e = ，p 。，p ：，p p 一。 ，p = 兀：c ( z ) 。 ( 4 ) v 表示一對(duì)一的映射關(guān)系，1 ，：d m ，也就是說(shuō)，在各個(gè)維上設(shè)定一個(gè)值 后，存在唯一的度量單元與之對(duì)應(yīng)。 ( 5 ) a 是維的屬性的集合，彳= a o ，口”，a n l ，其中a i ( t l t 彳，0 - i n - 1 ) 表示 第i 個(gè)屬性的名字，其值域?yàn)閐 o m a ( i ) 。 ( 6 ) f 是一個(gè)一對(duì)多的映射關(guān)系，f ：d 寸a 。也就是說(shuō)：每給定一個(gè)維名，存在 多個(gè)屬性名與之對(duì)應(yīng)，此時(shí)維名代表了一個(gè)維表。對(duì)于任何兩個(gè)不同的維，它們 對(duì)應(yīng)的屬性集是不相交的，即v f ，f ，則f ( d j ) n f ( d ，) = 矽。 ( 7 ) h 表示多對(duì)一的映射關(guān)系，h ：a 。專a ，a i 和a j 是某個(gè)維d i 上的屬性。也就 是維的屬性之間存在函數(shù)依賴關(guān)系，并且相對(duì)來(lái)說(shuō)，屬性a i 是細(xì)粒度，屬性a i 是 粗粒度。 顯然，上述數(shù)據(jù)立方體的七元組定義本質(zhì)上是一個(gè)多維空間中的定義。任取維 值乩，吐，以一。的組合，根據(jù)映射v 的定義，存在e 。e ，使得，v ( d o ，研，以。) = e ，； 反過(guò)來(lái)，若e ，e 是數(shù)據(jù)立方體空間中的一個(gè)單元，根據(jù)映射v 的定義，存在維值 d 。，4 ，d n l 的組合，使得e ，= v ( d 。，d l ，d n 1 ) ，這里的d i 表示維d i 的一個(gè)取值。e i 取0 或k 元組形式，0 表示在給定的維值組合上，沒有產(chǎn)生我們感興趣的度量數(shù)據(jù)， k 元組( x ，x 2 ，x 。) 與度量集m = m 。，m 2 ，m 對(duì)應(yīng)，也就是說(shuō)，如果x i 是k 元 組的第i 個(gè)成員，那么x i 是m i 在e i 下的聚合。 對(duì)應(yīng)于上述的多維數(shù)據(jù)立方體模型，有一套完備的代數(shù)操作，使用戶能從多個(gè) 角度，多側(cè)面地觀察數(shù)據(jù)立方體中的數(shù)據(jù)，從而深入地了解包含在數(shù)據(jù)中的信息。 下面我們描述施加給數(shù)據(jù)立方體的三個(gè)主要的代數(shù)操作： ( 1 ) 切片( s l i c e ) 在數(shù)據(jù)立方體中選定兩個(gè)維，固定其它維的取值，在選定的兩個(gè)維上各取一個(gè) 區(qū)間，這就是數(shù)據(jù)立方體的切片。切片的結(jié)果是一個(gè)二維的“平面。 ( 2 ) 切塊( d i c e ) 在數(shù)據(jù)立方體中選定三個(gè)維，固定其它維的取值，在選定的三個(gè)維上各取某一 個(gè)區(qū)間，這就是數(shù)據(jù)立方體的切塊。切片的結(jié)果是一個(gè)三維的“空間”。從另一 個(gè)角度來(lái)講，切塊可以看成是在切片的基礎(chǔ)上，進(jìn)一步確定某一個(gè)維的區(qū)間得到 的片段體，即多個(gè)切片的疊合。 ( 3 ) 旋轉(zhuǎn)( r o t a t e ) 數(shù)據(jù)立方體反映的是多維空間，而用戶習(xí)慣于觀察二維平面上的數(shù)據(jù)，因此， 第1 2 頁(yè) 國(guó)防科學(xué)技術(shù)大學(xué)研究生院碩士學(xué)位論文 對(duì)于數(shù)據(jù)立方體的分析，用戶只能次觀察兩個(gè)維。旋轉(zhuǎn)即改變維的顯示方向， 使用戶能夠觀察指定的維，允許用戶從多個(gè)側(cè)面進(jìn)行快速，一致和交互的數(shù)據(jù)存 取。 2 1 3數(shù)據(jù)立方體的實(shí)現(xiàn)方案 在邏輯上，數(shù)據(jù)立方體以多維方式組織數(shù)據(jù)，并提供一套完備的多維代數(shù)操 作，用以操作數(shù)據(jù)立方體。但物理實(shí)現(xiàn)上，數(shù)據(jù)立方體既可以基于多維數(shù)據(jù)庫(kù)技 術(shù)，也可以建立在關(guān)系數(shù)據(jù)庫(kù)技術(shù)之上。多維型數(shù)據(jù)立方體是近年來(lái)應(yīng)多維分析 的要求而產(chǎn)生的，它以多維數(shù)據(jù)庫(kù)為核心，直接支持?jǐn)?shù)據(jù)的多維視圖，多維數(shù)據(jù) 庫(kù)在數(shù)據(jù)存儲(chǔ)，檢索以及綜合上有著關(guān)系數(shù)據(jù)庫(kù)不可比擬的優(yōu)勢(shì)。但是，多維型 數(shù)據(jù)立方體在適應(yīng)維數(shù)動(dòng)態(tài)變化，數(shù)據(jù)變化，大數(shù)據(jù)量和軟硬件能力等方面趕不 上關(guān)系型數(shù)據(jù)立方體。關(guān)系型數(shù)據(jù)立方體以廣泛應(yīng)用的關(guān)系數(shù)據(jù)庫(kù)技術(shù)為基礎(chǔ)， 使用關(guān)系表存儲(chǔ)數(shù)據(jù)立方體的數(shù)據(jù)，在技術(shù)成熟度以及各方面的適應(yīng)性上較之多 維型數(shù)據(jù)立方體占有優(yōu)勢(shì)，是目前常用的數(shù)據(jù)立方體實(shí)現(xiàn)方案。 但是，關(guān)系型數(shù)據(jù)立方體也有它固有的缺點(diǎn)，即數(shù)據(jù)立方體提供的多維模型 和多維代數(shù)操作必須轉(zhuǎn)換成相應(yīng)的關(guān)系表和s q l 查詢。一種折中的數(shù)據(jù)立方體實(shí) 現(xiàn)方案是綜合上述兩種數(shù)據(jù)立方體實(shí)現(xiàn)方案的長(zhǎng)處，采用關(guān)系數(shù)據(jù)庫(kù)存儲(chǔ)海量的 基表數(shù)據(jù)，采用多維數(shù)據(jù)庫(kù)存儲(chǔ)聚集數(shù)據(jù)，這就是混合數(shù)據(jù)立方體。對(duì)于混合數(shù) 據(jù)立方體來(lái)說(shuō)，它可以迅速?gòu)木奂蝎@取信息，但如果鉆取到事實(shí)表，那么響應(yīng) 速度比較慢。 圖2 2 雪花模式 應(yīng)該說(shuō)，關(guān)系型結(jié)構(gòu)能夠較好的適應(yīng)多維數(shù)據(jù)的表示和存儲(chǔ)。關(guān)系數(shù)據(jù)庫(kù)將 數(shù)據(jù)立方體的多維結(jié)構(gòu)組織成兩類表，一類是事實(shí)表( f a c tt a b l e ) ，用來(lái)組織度量值 以及各個(gè)維的編碼值，事實(shí)表往往很大；另一類是維表( d i m e n s i o nt a b l e ) 分布在事 第1 3 頁(yè) 國(guó)防科學(xué)技術(shù)大學(xué)研究生院碩士學(xué)位論文 實(shí)表的劇圍，用以組織觀察和分析度量信息時(shí)所使用的維信息，相對(duì)于事實(shí)表來(lái) 說(shuō)，維表比較小。對(duì)于每一個(gè)維來(lái)說(shuō)，有一個(gè)表用來(lái)存儲(chǔ)該維的元數(shù)據(jù)，即維的 描述信息，包括維的層次屬性以及其它屬性等。事實(shí)表通過(guò)每一個(gè)維的編碼值和 周圍的維表聯(lián)系在一起，該結(jié)構(gòu)被稱之為“星型模式 ，采用這樣的結(jié)構(gòu)能夠體現(xiàn) 數(shù)據(jù)的多維特征，圖2 2 所示的就是一個(gè)星型模式的例子。 2 2 數(shù)據(jù)立方體計(jì)算技術(shù) 快速響應(yīng)查詢需預(yù)計(jì)算數(shù)據(jù)立方體。本節(jié)和下一節(jié)2 3 節(jié)我們研究數(shù)據(jù)立方體 的計(jì)算技術(shù)。完整數(shù)據(jù)立方體的計(jì)算是其他改進(jìn)、優(yōu)化的數(shù)據(jù)立方體的基礎(chǔ)。2 2 1 節(jié)我們考察完整數(shù)據(jù)立方體的各種計(jì)算算法，總結(jié)了其中的各種優(yōu)化策略。2 2 2 節(jié)我們討論了計(jì)算稀疏數(shù)據(jù)立方體和冰山立方體的經(jīng)典算法b u c 。隨著基本關(guān)系 中維數(shù)的增加和元組數(shù)的大量增長(zhǎng)，完整數(shù)據(jù)立方體帶來(lái)了巨大的時(shí)空開銷，難 以適應(yīng)應(yīng)用的需求。減少數(shù)據(jù)立方體的體積和計(jì)算時(shí)間有兩個(gè)基本途徑：一是只 物化一部分最常用的視圖的所有元組，這涉及到物化視圖選擇問(wèn)題，我們?cè)? 3 節(jié) 討論；二是物化立方體的全部視圖的部分元組，即2 2 3 節(jié)所討論的壓縮數(shù)據(jù)立方 體。 2 2 1 完整數(shù)據(jù)立方體的優(yōu)化計(jì)算 2 2 1 1c u b e 算子 j i mg r a y 提出了數(shù)據(jù)立方體( c u b e ) 算子c u b eb y 7 j 用于表示一組g r o u p b y 操作，即它計(jì)算c u b eb y 子句中各屬性的所有可能組合所對(duì)應(yīng)的g r o u pb y 。 下面的例2 1 表示了一個(gè)數(shù)據(jù)立方體計(jì)算。 例2 1 考慮一個(gè)關(guān)系表s a l e s ( e m p l o y e e ，p r o d u c t ，c u s t o m e r ，q u a n t i t y ) ，其數(shù)據(jù)立 方體查詢： s e l e c te m p l o y e e ，p r o d u c t ，c u s t o m e r , s u m ( q u a n t i t y ) a sa m o u n t f r o ms a l e s c u b eb y e m p l o y e e ，p r o d u c t ，c u s t o m e r 對(duì)c u b e b y 的屬性e m p l o y e e ，p r o d u c t 和c u s t o m e r 的所有組合所對(duì)應(yīng)的8 個(gè) g r o u pb y 進(jìn)行求和聚集計(jì)算，臣l j ( e m p l o y e e ，p r o d u c t ，c u s t o m e r ) 、( e m p l o y e e ， p r o d u c t ) 、( e m p l o y e e ，c u s t o m e r ) 、( p r o d u c t ，c u s t o m e r ) 、( e m p l o y e e ) 、( p r o d u c 0 、 ( c u s t o m e r ) 和a l l ( i i i g r o u pb y 屬性為空的那個(gè)聚集) ，一個(gè)g r o u pb y 也被稱 作一個(gè)小方體( c u b o i d ) ，這個(gè)c u b e 的計(jì)算結(jié)果如圖2 3 。一般地，對(duì)于含1 1 個(gè)屬 性的c u b eb y ，將要計(jì)算2 n 個(gè)不同的g r o u pb y 。 第1 4 頁(yè) 國(guó)防科學(xué)技術(shù)大學(xué)研究生院碩士學(xué)位論文 s t a t e s i d e m p l o y e e p r o d u c tc u s t o m e r q u a n t i t y 1ol12 2o l 04 3io13 i d e m p l o y e e p r o d u c t ：c u s t o m e ra m o u n t la l la l la l l9 20a l la l l 6 301a l l6 4 o1l 2 5ol 04 6oa l ll2 7oa l lo 4 81a l la l l 3 910a l l3 1 01 ol3 1 11a ul3 1 2a l lla l l6 1 3a l l1l2 1 4a l llo4 i 5a l loa l l3 1 6a l l013 1 7a l la l lls 1 8 a l l a l lo 4 圖2 3 數(shù)據(jù)立方體s a l e s 計(jì)算示圖 2 2 1 2 立方體格 聚集函數(shù)c o u n t 、s u m 、m i n 、m a x 和a v g 是代數(shù)的，即它們具有一個(gè)關(guān) 鍵的特征：較詳細(xì)的聚集( 即較多維上的) 可以用來(lái)計(jì)算不那么詳細(xì)的聚集( 即較少 維上的) ，這個(gè)特征導(dǎo)致在c u b e 的所有g(shù) r o u pb y 上形成了一個(gè)格( 一種偏序關(guān) 系) ?？紤]數(shù)據(jù)立方體中的兩個(gè)分組g 1 和g 2 ，如果可以使用g 2 的結(jié)果來(lái)計(jì)算g l ， 那么g l 依賴于g 2 ，記為g ，g ：。例如，用g r o u pb ya ，b 的結(jié)果可以計(jì)算g r o u p b y a ，因此，( 4 ) ( a ，b ) 。偏序關(guān)系揭示了關(guān)于數(shù)據(jù)立方體中各個(gè)g r o u pb y 之間計(jì)算時(shí)的一種依賴關(guān)系。我們以立方體格( c u b el a t t i c e ) 來(lái)表示這種依賴關(guān)系。 立方體格的形式化描述是( 厶) ，l 表示元素( 即g r o u pb y ) 的集合，表示元 素依賴關(guān)系。對(duì)于立方體格( 厶) 中的任意兩個(gè)元素a 和b ，口 b 表示a b ，且 a b 。元素a 的祖先，父母，兒子和子孫的定義如下： a n c e s t o r ( a ) = 6 i 口6 ) p a r e n t ( a ) = 6i 口 6 ，1 3 c ，a c ，c b ) c h i l d ( a ) = 6j b 口，1 3 c ，b c ，c = n 在這里，參數(shù)n 被稱作一個(gè)劃分的最小支持度( m i n i m u ms u p p o r t ) 。如果n 取1 ， 那么，冰山數(shù)據(jù)立方體就是原來(lái)的數(shù)據(jù)立方體。 第1 8 頁(yè) 國(guó)防科學(xué)技術(shù)大學(xué)研究生院碩士學(xué)位論文 在b u c 算法中，輸入變量i n p u t 是事實(shí)表的全部或者它的一個(gè)劃分，它的每 條元組記錄了各個(gè)維的取值以及相應(yīng)的度量值，d i m 是聚集計(jì)算的初始維，輸出是 滿足最小支持度的聚集結(jié)果。 表2 1b u c 算法的偽代碼【1 4 i p r o c e d u r eb o t t o m u p c u b e ( i n p u t , d i m ) g i o b a l s ： c o n s t a n ta u r ad i m s ：維的數(shù)目 c o n s t a n tc a r d i n a l i t y n u m d i m s ：每個(gè)維的基數(shù) c o n s t a n tm i n s u p ：最小支持度 o u t p u t r e c ：輸出記錄 d a t a c o u n t n u m d i m s ：每個(gè)維的各個(gè)劃分包含的元組數(shù)目 m e t h o d ： l ：a g g e r g a t e ( i n p u t ) ；p l a c e sr e s u l ti no u t p u t r e c 2 ：i fi n p u t c o u n t ( ) 一lt h e n o p t i m i z a t i o n w r i t e a n c e s t o r s ( i n p u t 0 ，d i m ) ；r e t u r n ； 3 ：w r i t eo u t p u t r e c ； 4 ：f o rd = d i m ；d n u m d i m s ；d + + d o 5 ：l e tc = c a r d i n a l i 夠 d 】； 6 ：p a r t i t i o n ( i n p u t ，d ，c ，d a t a c o u n t d ) ； 7 ：l e t k = o ： 8 ：f o ri = 0 ；i = m i n s u pt h e n t h eb u c s t o p sh e r e 1 1 ：o u t p m r e c d i m d = i n p u t k d i m d ； 1 2 ：b o t o m u p c u b e ( i n p u t k k + c 】，( 1 + 1 ) ； 1 3 ：e n d i f 1 4 ：k + = c ： 1 5 ：e n df o r 16 ：o u t p u t r e c d i m d = a l l ； 1 7 ：e n d f o r b u c 算法的偽代碼如表2 1 所示。第一步是對(duì)輸入數(shù)據(jù)i n p u t 進(jìn)行聚集計(jì)算( 第 l 行) ，并且輸出聚集結(jié)果( 第3 行) 。對(duì)于d i m 到n u m d i m s 之間的每一個(gè)維d ( 第4 行) ，在維d 上對(duì)輸入數(shù)據(jù)i n p u t 做劃分( 第6 行) ，執(zhí)行完劃分過(guò)程后，數(shù)組d a t a c o u n t 記錄了維d 的每一個(gè)不同的取值所對(duì)應(yīng)的劃分包含的元組數(shù)目。對(duì)于得到的每一 個(gè)劃分( 第8 行) ，如果劃分滿足最小支持度( 對(duì)于完全數(shù)據(jù)立方計(jì)算，這總是正確 的，因?yàn)樽钚≈С侄葹? ) ，那么以這個(gè)劃分作為參數(shù)遞歸調(diào)用b o t t o m u p c u b e 過(guò)程， 在這個(gè)劃分上計(jì)算維d + l 到n u m d i m s 之間的聚集。當(dāng)遞歸過(guò)程返回的時(shí)候，以維 d 上的下一個(gè)劃分繼續(xù)遞歸調(diào)用b o t t o m u p c u b e 過(guò)程。當(dāng)處理完維d 上的所有劃分 后，在下個(gè)維d + l 上重復(fù)上述的整個(gè)過(guò)程。 第1 9 頁(yè) 國(guó)防科學(xué)技術(shù)大學(xué)研究生院碩士學(xué)位論文 5 怒c d 4 a b c6 a b d8 a c d1 2 b c d t 3 a b7 a c9 a d 1 l b c 1 3 b d1 5 c d 乞乏 2 a1 0 b1 4 c1 6 d 心彥 l a l l 圖2 6b u c 處理樹 圖2 6 表示了b u c 算法的一棵處理樹，數(shù)字表示了b u c 算法訪問(wèn)各個(gè)g r o u p b