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

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

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

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

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

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