資源描述：
《數(shù)據(jù)倉庫中基于位圖索引查詢優(yōu)化的研究》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。
1、Athesis(dissertation)submittedtoZhengzhouUniversityforthedegreeofMaster18S72黽§TheResearchofQueryOptimizationBasedonBitmapIndicesforData"勻rehouseByxiaoChengSupervisor：Prof．yumeiChaiComputerSoftwareandTheorySchoolofInformationEngineeringMay2010／二原創(chuàng)性聲明lIIll
2、lltl1111111IIIIIIIIIIIIY1833856本人鄭重聲明：所呈交的學位論文，是本人在導師的指導下，獨立進行研究所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的科研成果。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標明。本聲明的法律責任由本人承擔。學位論文作者：手呈噸日期：刀fD年籮月弓fEl學位論文使用授權聲明本人在導師指導下完成的論文及相關的職務作品，知識產(chǎn)權歸屬鄭州大學。根據(jù)鄭州大學有關保留、使用學位論文的規(guī)定，同意學校保留或
3、向國家有關部門或機構(gòu)送交論文的復印件和電子版，允許論文被查閱和借閱；本人授權鄭州大學可以將本學位論文的全部或部分編入有關數(shù)據(jù)庫進行檢索，可以采用影印、縮印或者其他復制手段保存論文和匯編本學位論文。本人離校后發(fā)表、使用學位論文或與該學位論文直接相關的學術論文或成果時，第一署名單位仍然為鄭州大學。保密論文在解密后應遵守此規(guī)定。學位論文作者：平呈司毛日期：加f。年羅月弓『日摘要索引是數(shù)據(jù)倉庫查詢優(yōu)化的重要技術，主要包括樹形索引和位圖索引。其中位圖索引因為其結(jié)構(gòu)簡單，并且硬件支持二進制位運算效率很高，被廣泛應用
4、在數(shù)據(jù)倉庫中。在屬性的基數(shù)(該屬性可能的取值數(shù))低的情況下，位圖索引已經(jīng)被證明是十分高效的。但在基數(shù)比較高的情況下，位圖索引需要占用大量的存儲空間。位圖索引往往被認為只有在屬性基數(shù)較低情況下才適合使用。為了克服這個難題，現(xiàn)今研究者們已經(jīng)提出了很多方法，包括編碼，壓縮，bin。其中bin位圖索引可以有效的降低高基數(shù)時位圖占用的空間。這種索引不像簡單位圖索引那樣建立在每一個不同的屬性值上，而是建立在一個個的屬性范圍上。但它同時也帶來了另一個難題，就是候選檢查。候選檢查往往占用大部分的查詢時間。采用傳統(tǒng)多維查
5、詢算法，對各屬性進行查詢的順序不同，可能對總候選檢查數(shù)目產(chǎn)生重大影響。本文給出兩個定理，證明了影響排序的兩個因素。并據(jù)此提出一種基于權值排序算法，通過在執(zhí)行查詢前對各屬性查詢進行排序，使總的候選檢查的數(shù)目盡可能少。理論分析和實驗表明，此排序算法可以明顯減少總候選檢查數(shù)目，優(yōu)化了傳統(tǒng)多維查詢算法。但是排序的傳統(tǒng)多維查詢算法并不能減少查詢的第一維所需的候選檢查數(shù)目，實驗表明第一維所需的候選檢查數(shù)目往往占總候選檢查數(shù)目的大部。通過預掃描(推遲候選檢查)可以有效解決這個問題，但是進行預掃描需要額外的花費，即要掃
6、描更多的索引，這個代價是不能忽視的?？紤]到預掃描一定維數(shù)后，繼續(xù)預掃描將不會明顯的減少總的候選檢查數(shù)目，本文在排序的基礎上提出動態(tài)預掃描算法，目標是在預掃描屬性數(shù)目和總的候選檢查數(shù)目中找出一個合理的平衡點，以提高查詢效率。理論分析和實驗結(jié)果表明，動態(tài)預掃描算法取得了良好的效果。關鍵字：數(shù)據(jù)倉庫位圖索引Binning編碼壓縮多維查詢AbstractIndexisanimportantqueryoptimizationtechniquefordatawarehouse,whichincludingtreei
7、ndexesandbitmapindexes．Bitmapindexiswidelyusedinthedatawarehousebecauseofitssimplestructureanditshighefficiencyoflogicoperation．Bitmapindexhasproventobeveryefficientwinllowattributecardinalities(thenumberofdistinctvalues)．However,forhigh-cardinalityattri
8、butes，bitmapindexrequirestoomuchstorage．Therefore,bitmapindexisoftenthinktobeunsuitableforhigh-cardinalityattributes．Researchershaveprovidedalotofstrategiestosolvethisproblem，includingcoding,compression，bin．Bitmapindex謝tll
