標(biāo)記立方體技術(shù)研究.pdf

1、聯(lián)機(jī)分析處理和Skyline（輪廓）查詢技術(shù)是對(duì)海量數(shù)據(jù)進(jìn)行分析以輔助決策的重要技術(shù)。數(shù)據(jù)安全以及快速響應(yīng)是它們的兩個(gè)重要需求。解決快速響應(yīng)問(wèn)題的一種方法是采用立方體技術(shù)，把所有可能的某類(lèi)查詢結(jié)果組合成某種立方體，通過(guò)事先預(yù)計(jì)算并物化，達(dá)到無(wú)需再計(jì)算而即時(shí)響應(yīng)查詢的效果。解決安全問(wèn)題的一種途徑是利用安全數(shù)據(jù)庫(kù)完善的安全保護(hù)機(jī)制，以標(biāo)記來(lái)區(qū)分用戶和數(shù)據(jù)敏感度。因此，研究標(biāo)記安全數(shù)據(jù)庫(kù)下的立方體的安全以及立方體的計(jì)算、更新和存儲(chǔ)等關(guān)鍵問(wèn)題具

2、有重要意義。
　　為了迅速響應(yīng)Skyline查詢，提出了標(biāo)記Skyline立方體概念。在標(biāo)記安全數(shù)據(jù)庫(kù)中用戶和表中元組都打有安全標(biāo)記。當(dāng)用戶的標(biāo)記支配元組的標(biāo)記時(shí)該用戶才可以讀取該元組。這使得不同標(biāo)記的用戶看到的數(shù)據(jù)集即處理對(duì)象是不同的，處理結(jié)果也隨之不同。這與常規(guī)環(huán)境下有明顯差異。將所有不同標(biāo)記用戶的Skyline查詢結(jié)果組成標(biāo)記Skyline立方體可以直接響應(yīng)不同標(biāo)記用戶的查詢。除了從多維角度考察數(shù)據(jù)之外，在標(biāo)記安全數(shù)據(jù)庫(kù)中，

3、還存在著從多用戶角度考察數(shù)據(jù)的要求，即不同用戶的數(shù)據(jù)立方并不相同。為此，提出了由所有不同標(biāo)記用戶對(duì)應(yīng)的數(shù)據(jù)立方組成的標(biāo)記數(shù)據(jù)立方體概念。在標(biāo)記Skyline立方體和標(biāo)記數(shù)據(jù)立方體概念基礎(chǔ)上，進(jìn)一步提出了標(biāo)記立方體模型，一方面產(chǎn)生受安全數(shù)據(jù)庫(kù)保護(hù)的立方體，另一方面建立了源表元組與立方體元組之間安全標(biāo)記的映射關(guān)系，使源表的安全設(shè)置在立方體中得到合理體現(xiàn)，不會(huì)泄露源表機(jī)密。
　　為了提高標(biāo)記Skyline立方體的計(jì)算效率，提出了高效算法

4、SLSC?，F(xiàn)有計(jì)算Skyline立方體的算法沒(méi)有考慮標(biāo)記特征，而用現(xiàn)有計(jì)算單一 Skyline的算法獨(dú)立計(jì)算每個(gè)Skyline進(jìn)而得到整個(gè)立方體的方式的效率難以令人滿意。SLSC算法基于共享策略，利用標(biāo)記支配關(guān)系所蘊(yùn)含的點(diǎn)集包含關(guān)系，通過(guò)迭代實(shí)現(xiàn)計(jì)算結(jié)果共享。理論分析和實(shí)驗(yàn)結(jié)果表明，該算法提高了效率，尤其當(dāng)標(biāo)記等級(jí)數(shù)增大時(shí)，效果顯著。
　　為了提高標(biāo)記Skyline立方體的更新效率，提出了增量更新算法BUI和BUD。標(biāo)記Skyli

5、ne立方體包含的數(shù)據(jù)量大，更新比較復(fù)雜。當(dāng)少量源數(shù)據(jù)發(fā)生變化時(shí)，重新計(jì)算整個(gè)立方體代價(jià)較大。BUI和BUD算法針對(duì)標(biāo)記Skyline立方體的特點(diǎn)，采用自底向上的方式遍歷受影響的標(biāo)記，在已有立方體基礎(chǔ)上進(jìn)行增量更新。理論分析和實(shí)驗(yàn)結(jié)果表明，這些算法顯著提高了更新效率。
　　高效存儲(chǔ)是標(biāo)記數(shù)據(jù)立方體至關(guān)重要的問(wèn)題。為有效縮減標(biāo)記數(shù)據(jù)立方體的存儲(chǔ)尺寸，提出了緊湊存儲(chǔ)方案。現(xiàn)實(shí)生活中數(shù)據(jù)往往是稀疏的，加上標(biāo)記支配關(guān)系蘊(yùn)含的元組集包含關(guān)系，