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