[碩士論文精品]不確定性數據的查詢分析處理

華南理工大學畢業(yè)設計（論文）任務書茲發(fā)給軟件學院06級4班學生區(qū)鉞堅畢業(yè)設計（論文）任務書，內容如下1畢業(yè)設計（論文）題目不確定性數據的查詢分析處理2應完成的項目（1）2010年3月1日前擬定提綱并提交開題報告（2）2010年5月15日前完成論文初稿（3）進行與論文題目相關的調研工作并收集相關的資料（4）2010年6月1日前參考外文文獻資料并提交外文翻譯譯文3參考資料以及說明（1）崔斌，盧陽基于不確定數據的查詢處理綜述J計算機應用2008，281127292731（2）周傲英，金澈清，王國仁，李建中不確定性數據管理技術研究綜述J計算機學報，2009，01116（3）李建中，于戈，周傲英不確定性數據管理的要求與挑戰(zhàn)中國計算機學會通訊2009，54615（4）申德榮，于戈，寇月，聶鐵錚可能世界內數值型不確定數據匹配模型計算機應用研究2008726072611（5）RCHENG,YXIA,SPRABHAKAR,RSHAH,ANDJSVITTEREFFICIENTINDEXINGMETHODSFORPROBABILISTICTHRESHOLDQUERIESOVERUNCERTAINDATAINVLDB,PAGES876887,2004（6）YTAO,RCHENG,XXIAO,WKNGAI,BKAO,ANDSPRABHAKARINDEXINGMULTIDIMENSIONALUNCERTAINDATAWITHARBITRARYPROBABILITYDENSITYFUNCTIONSINPROCEEDINGSOFTHE31STINTERNATIONALCONFERENCEONVERYLARGEDATABASESVLDB05,PAGES922933VLDBENDOWMENT,2005（7）HUAM,PEIJ,ZHANGW,ETALRANKINGQUERIESONUNCERTAINDATAAPROBABILISTICTHRESHOLDAPPROACHCPROCEEDINGSOFTHE2008ACMSIGMODINTERNATIONALCONFERENCEONMANAGEMENTOFDATANEWYORKACMPRESS,2008,6736864本畢業(yè)設計（論文）任務書于2010年2月5日發(fā)出，應于2010年6月10日前完成，然后提交畢業(yè)考試委員會進行答辯。專業(yè)教研組（系）、研究所負責人審核年月日指導教師簽發(fā)年月日畢業(yè)設計（論文）評語畢業(yè)設計（論文）總評成績畢業(yè)設計（論文）答辯負責人簽字年月日摘要I摘要不確定性數據是許多應用固有的，這些應用包括經濟、軍事、物流、金融、電信等等。由于這些應用的重要性和不確定性數據的快速增長積累，分析大量的不確定性數據已經成為一個重要的任務并且吸引著數據庫社區(qū)越來越多的關注。不確定性數據的種類是豐富多彩的，例如關系數據庫、流數據和移動物體。根據場景和數據特征的不同，研究者研究出許多不同的數據模型。所有這些模型的核心思想都來源于可能世界模型。每個可能世界模型包含大量的可能世界實例，這些可能世界實例的概率總和為1。然而，由于可能世界實例的數量遠遠大于不確定數據庫的規(guī)模，這就使得從所有可能世界實例中得到中間結果然后合并得出最終結果的方法是不可行的。應用傳統(tǒng)的查詢方法來處理不確定數據的查詢會使得結果集出現偏差從而無法滿足用戶的需求。因此，必須要使用排序和剪枝等啟發(fā)式技術來減少計算開銷從而提高效率。本論文首先介紹了各種各樣的數據模型；其次，介紹了基于不確定性數據的TOPK和SKYLINE查詢，包括查詢的定義、一些例子以及算法；然后，介紹了一些不確定性數據的處理；最后，介紹了兩種索引技術PTI和UTREE，PTI是用來管理一維不確定性數據的，UTREE則擴展了PTI，使之能夠用來對多維不確定對象進行索引。關鍵詞不確定性數據數據模型TOPK查詢SKYLINE查詢PTI索引UTREE索引ABSTRACTIIABSTRACTUNCERTAINDATAAREINHERENTINSOMEIMPORTANTAPPLICATIONS,INCLUSIVEOFECONOMY,MILITARY,LOGISTIC,FINANCEANDTELECOMMUNICATION,ETCDUETOTHEIMPORTANCEOFTHOSEAPPLICATIONSANDTHERAPIDLYINCREASINGAMOUNTOFUNCERTAINDATACOLLECTEDANDACCUMULATED,ANALYZINGLARGECOLLECTIONSOFUNCERTAINDATAHASBECOMEANIMPORTANTTASKANDHASATTRACTEDMOREANDMOREINTERESTFROMTHEDATABASECOMMUNITYUNCERTAINDATAHASMANYDIFFERENTSTYLES,SUCHASRELATIONALDATA,STREAMINGDATA,ANDMOVINGOBJECTSACCORDINGTOSCENARIOSANDDATACHARACTERISTICS,LOTSOFDATAMODELSHAVEBEENDEVELOPEDALLTHOSEMODELSCOMEFROMTHECOREPOSSIBLEWORLDMODELTHATCONTAINSAHUGENUMBEROFTHEPOSSIBLEWORLDINSTANCESWITHTHESUMOFPROBABILITIESEQUALTO1HOWEVER,THENUMBEROFTHEPOSSIBLEWORLDINSTANCESISFARGREATERTHANTHEVOLUMEOFTHEUNCERTAINDATABASE,MAKINGITINFEASIBLETOCOMBINEMEDIALRESULTSGENERATEDFROMALLOFPOSSIBLEWORLDINSTANCESFORTHEFINALQUERYRESULTSUSINGTRADITIONALQUERYINGMETHODSONUNCERTAINDATAWILLBIASTHEANSWERSET,ANDHENCECANNOTSATISFYUSERSNEEDSTHUS,SOMEHEURISTICTECHNIQUES,SUCHASORDERING,PRUNING,INDEXING,MUSTBEUSEDTOREDUCETHECOMPUTATIONCOSTFORTHEHIGHEFFICIENCYTHISPAPERFIRSTLYINTRODUCESALLKINDSOFDATAMODELSSECONDLY,WEINTRODUCESTOPKQUERIESANDSKYLINEQUERIESBASEDONUNCERTAINDATA,INCLUDINGTHEIRDEFINITIONS,SOMEEXAMPLESANDALGORITHMSTHENTHEPROCESSINGOFUNCERTAINDATAISINTRODUCEDATLASTWEINTRODUCESTWOKINDSOFINDEXINGTECHNOLOGY,PTIANDUTREE,PTIISUSEDFORMANAGINGONEDIMENSIONUNCERTAINDATAWHILEUTREEEXTENDSPTITOINDEXMULTIDIMENSIONALUNCERTAINOBJECTSKEYWORDUNCERTAINDATA,DATAMODEL,TOPKQUERIES,SKYLINEQUERIES,PTI,UTREE目錄III目錄摘要IABSTRACTII第一章引言111不確定性數據的研究背景112不確定性數據的分類113不確定性數據產生的原因214不確定性數據的查詢分析處理的關鍵問題與挑戰(zhàn)215不確定性數據的查詢分析處理的內容與目標316本章小結3第二章不確定性數據的模型521可能世界模型522概率數據庫模型623不確定對象模型824針對關系型數據825針對半結構化數據模型826數據流模型927針對多維數據模型928概率數據庫和不確定對象模型的相互轉換929本章小結9第三章不確定性數據的查詢1131基于不確定性數據的TOPK查詢1132UTOPK查詢12321UTOPK查詢的定義12322UTOPK查詢舉例12323UTOPK查詢算法分析1333UKRANKS查詢15331UKRANKS查詢的定義15332UKRANKS查詢舉例16目錄IV333UKRANKS查詢算法分析1634PTK查詢18341PTK查詢定義18342PTK查詢舉例18343PTK查詢的算法1935PKTOPK查詢23351PKTOPK查詢定義23352PKTOPK查詢舉例2336PSKYLINE查詢24361PSKYLINE查詢定義24362PSKYLINE查詢舉例24363針對PSKYLINE查詢的算法2537針對四種TOPK查詢的算法2638本章小結26第四章不確定性數據的分析處理2741世系分析2742數據流分析2743非確定性數據庫中空值處理2744關系代數處理2845數據挖掘2946本章小結29第五章索引技術3151概率閾值索引PTI技術31511PTI的定義31512PTI應用舉例3152UTREE索引技術33521概率約束區(qū)域（PCR）33522UCATALOG的引入34523保守功能盒CFB36524UTREE的結構以及特點36525應用UTREE索引來進行概率范圍查詢37目錄V53本章小結37第六章總結與展望3861總結3862展望38參考文獻39致謝42第一章引言1第一章引言11不確定性數據的研究背景近年來，在許多現實的應用中，例如傳感器網絡與射頻識別電子標簽、互聯(lián)網數據、基于位置服務、電信服務、數據挖掘應用、金融服務，數據的不確定性普遍存在，不確定性數據UNCERTAINDATA扮演著關鍵角色。隨著技術的進步和人們對數據采集和處理技術理解的不斷深入，不確定性數據得到了廣泛的重視。不確定數據在一些重要應用領域中是固有存在的，如傳感器網絡和移動物體追蹤。在不確定數據上使用傳統(tǒng)的查詢方法會使查詢結果出現偏差，不能滿足用戶的需求。由于真實世界應用中數據固有的不確定性，以及相關應用系統(tǒng)需求的增加，針對不確定數據管理的研究已經成為數據庫技術研究中一個新的熱點。不確定性數據的表現形式多種多樣，它們可以以關系型數據、半結構化數據、流數據或移動對象數據等形式出現。不確定性數據的產生原因比較復雜?？赡苁窃紨祿旧聿粶蚀_或是采用了粗粒度的數據集合，也可能是為了滿足特殊應用目的或是在處理缺失值、數據集成過程中而產生的。不確定性數據管理技術的典型框架模型定義、預處理與集成、存儲與索引和查詢分析處理。而查詢分析處理是不確定性數據管理的最終目標。查詢類型非常豐富，例如關系查詢操作、數據世系、XML處理、流數據查詢、TOPK查詢、SKYLINE查詢、OLAP分析、數據挖掘等。盡管可以分別針對各個可能世界實例計算查詢結果，再合并中間結果以生成最終查詢結果，但由于可能世界實例的數量遠大于不確定數據庫的規(guī)模，該方法并不可行。因此，必須采用排序、剪枝等啟發(fā)式技術優(yōu)化處理，以提高效率。另外，由于輸入數據具有不確定性，查詢結果也往往是近似結果。不確定性數據查詢分析處理的研究工作在很多方面都得到了很好的發(fā)展，包括數據集成、索引技術、半結構化數據、世系分析、關系代數處理、數據流分析、TOPK查詢、SKYLINE查詢、聯(lián)機分析處理和數據挖掘等。12不確定性數據的分類目前，有關非確定數據的定義和分類還沒有嚴格的定義，TRIO中將數據分為EXACT和INEXACT兩種1。有關INEXACT數據的描述又有多種，如不確定的數據、概率數據、模糊集數據、近似數據、不完備數據和不精確數據等。MOTRO2將不確定信息分為不確定和不精確兩類。不確定是指屬性值的可信性，概率是指屬性取某一值的概率。不完備的數據是指有信息丟失。不精確數據是指數據的取值可能是集合中的數據之一。文獻2中除了將非確定的數據定義為不確定和不精確數據外，還包括不完備、模糊、不一致、不明確。其中除了不明確為語義模糊概念外，其他都涵蓋了TRIO中的定義。本科畢業(yè)論文2申德榮等人3把不確定數據分為七類RANGE、OR_SET、PROBABILITY、UNKNOWN、NEGATIVE、VAGUE、FUZZY。其中的前五類屬于數值型的不確定性。13不確定性數據產生的原因不確定性數據的產生原因比較復雜。周傲英等人4認為原因有原始數據本身不準確或是采用了粗粒度的數據集合，也可能是為了滿足特殊應用目的或是在處理缺失值、數據集成過程中而產生的。HUA等人5認為不確定性數據在各個應用中出現的原因包括不完整的數據、設備的缺陷、數據傳輸延遲或者丟失。14不確定性數據的查詢分析處理的關鍵問題與挑戰(zhàn)與傳統(tǒng)的確定性數據相比，不確定性數據引入了概率維，而這個概率的引入使得查詢、分析、處理的各個環(huán)節(jié)都都面臨著巨大的挑戰(zhàn)。李建中等人6提到了五方面的挑戰(zhàn)。1差異顯著的數據模型傳統(tǒng)數據模型無法準確描述不確定性數據，可能世界（POSSIBLEWORLD）模型是描述不確定性數據的通用模型。該模型包含若干個可能世界實例，在各個實例中，一部分元組存在，剩余元組不存在?？赡苁澜鐚嵗陌l(fā)生概率等于實例內元組的概率乘積和實例外元組的不發(fā)生概率的乘積之積。所有可能世界實例的發(fā)生概率之和等于1。2急劇攀升的問題復雜度管理不確定性數據所面對的最直接的挑戰(zhàn)，就是相對于數據庫規(guī)模呈指數倍的可能世界實例的數量?！傲_列可能世界實例，計算基于該實例的查詢結果，整合各實例的查詢結果生成最終的答案”的處理方式顯然是不可行的，迫切需要結合各種剪枝、排序等技術以快速計算查詢結果。3非同一般的概率維不確定性數據比確定性數據多了一個概率維，這就導致了查詢、索引、處理工程、處理結果都大受影響。概率維度不是普通的維度，它的出現改變了傳統(tǒng)的數據處理模式。首先，部分查詢定義可能擁有概率參數，例如PTK查詢（一種TOPK查詢）需要一個概率參數P，僅返回成為TOPK成員的概率超過P的元組集合5。其次，傳統(tǒng)的索引技術（例如B樹、R樹等）無法有效索引不確定性數據，需要開發(fā)新的索引技術。再次，處理過程需要充分考慮概率因素，許多算法在執(zhí)行過程中會優(yōu)先考慮高概率的元組。最后，查詢結果也會包含概率信息。4多樣的數據形態(tài)半結構化數據（XML）、流數據、多維數據和空間數據等數據形式都會受到概率引入第一章引言3的影響。5豐富的查詢類型在不確定性數據環(huán)境下，由于引入了概率維度，查詢的種類反而會增加。元組的概率維度值從側面反映了該元組的重要程度，因而影響著查詢的定義。15不確定性數據的查詢分析處理的內容與目標與在確定數據上查詢不同，不確定數據上的研究工作將概率引入到數據模型中來衡量不確定對象成為結果集中元素的可能性。不確定性數據的表現形式多種多樣，它們可以以關系型數據、半結構化數據、流數據或移動對象數據等形式出現。由于問題定義和數據模型的不同，不確定數據上的查詢類型也多種多樣。目前，根據應用特點與數據形式差異，研究者已經提出了多種針對不確定數據的數據模型。這些不確定性數據模型的核心思想都源自于可能世界模型?？赡苁澜缒Ｐ蛷囊粋€或多個不確定的數據源演化出諸多確定的數據庫實例，稱為可能世界實例，而且所有實例的概率之和等于1。盡管可以首先分別為各個實例計算查詢結果，然后合并中間結果以生成最終查詢結果，但由于可能世界實例的數量遠大于不確定性數據庫的規(guī)模，這種方法并不可行。因此，必須運用排序、壓縮、剪枝、驗證等啟發(fā)式技術設計新型算法，以提高效率。本文介紹了不確定性數據的查詢分析處理各個方面的知識。包括以下幾個方面。1不確定性數據的分類、模型以及不確定性數據產生的原因。2基于不確定性數據的TOPK查詢和PSKYLINE查詢3各種查詢分析處理技術。4PTI和UTREE兩種索引技術。目前，基于不確定性數據的研究比較多，這方面的資料也比較多。但是，很多資料都是就不確定性數據的某一個方面進行闡述的，要從整體上把握不確定性數據需要閱讀大量的文獻。文獻4提出了不確定性數據管理技術的典型框架模型定義、預處理與集成、存儲于索引和查詢分析處理，并且介紹了不確定性數據各個方面的知識，是一篇綜述不確定性數據管理技術研究的文章。但是，文中說得比較簡單，如果沒有一定的基礎是很難理解的。本文的主要目的就是讓讀者能夠快速的了解上面介紹到的內容，從而盡快從整體上把握不確定性數據。因此，本文盡量把別人的研究成果解釋得詳細一些，能夠舉例子說明的就舉例子說明，需要計算的則把計算過程也描述出來，對于他們提出的一些定理能夠證明的則給出證明。16本章小結本章介紹了不確定性數據的研究背景和分類、不確定性數據產生的原因、不確定性數本科畢業(yè)論文4據的查詢分析處理的關鍵問題與挑戰(zhàn)、本文的內容以及目標。第二章不確定性數據的模型5第二章不確定性數據的模型根據應用場景的不同，數據模型是多種多樣的，目前就已經提出了多種數據模型，其中可能世界模型POSSIBLEWORLDMODEL7,8是最核心的，并衍生出多種應用相關的模型，特別是針對關系型數據、半結構化數據、流數據和多維數據的模型。21可能世界模型可能世界模型7,8從一個不確定性數據庫演化出很多確定的數據庫實例稱為可能世界實例，而且所有實例的概率之和為1。每個可能世界實例出現的概率為該實例中所有元組的概率與不在該實例中的元組不出現的概率的乘積。不確定性數據的種類較多，例如關系型數據、半結構化數據、流數據、移動對象數據等，盡管存在許多與數據類型緊密相關的數據模型，但是這些模型最終都可以轉化為可能世界模型?？赡苁澜缒Ｐ褪窃诓淮_定性數據管理領域，最常用的模型?？紤]下面的表格所示的一個簡單例子。表21不確定性表元組概率T104T203T305上表描述了一個不確定性表包含3個元組，每個元組是否出現在某個可能世界實例都有一個概率。因為3個元組，每個元組都可能出現或者不出現在某個可能世界實例，所以總共有8個可能世界實例。如下表表22可能世界實例可能世界概率PW1021PW2T1014PW3T2009PW4T3021PW5T1,T2006PW6T1,T3014PW7T2,T3009PW8T1,T2,T3006從表22可以看出1所有實例的概率之和為1?？梢酝ㄟ^將概率這一列的值加起來驗證一下02101400902100601400900612每個可能世界實例出現的概率為該實例中所有元組的概率與不在該實例中的元組不出現的概率的乘積。本科畢業(yè)論文6例如，可能世界PW1的概率為T1、T2、T3都不出現的概率的乘積PPW11T11T21T3060705021再如，可能世界PW5的概率為T1、T2出現但T3不出現的概率的乘積PPW5T1T21T30403050063每個元組出現在所有可能世界的概率總和等于它本身的概率。如PT1PPW2PPW5PPW6PPW801400601400604PT2PPW3PPW5PPW7PPW800900600900603PT3PPW4PPW6PPW7PPW802101400900605JIAN等人9介紹了從可能世界模型派生出的概率數據庫22和不確定對象23兩種模型，并且給出一種方法相互轉換這兩種模型。22概率數據庫模型概率數據庫（PROBABILISTICDATABASE）包含了有限數目的不確定性表。不確定性表T（UNCERTAINTABLE）包含一系列的元組，這些元組的出現概率PRT0。生成規(guī)則（GENERATIONRULE）明確了一系列的互斥元組，這些元組的概率加起來小于等于1，并且在一個可能世界實例，每個生成規(guī)則最多只能出現一個元組。假設所有的元組最多只能出現在一個生成規(guī)則R，對于那些沒有出現在任何R的元組，讓它門構成一個規(guī)則RT，因此，一個不確定性數據表是由一系列生成規(guī)則構成的。一個生成規(guī)則的概率（PROBABILITY）由這個規(guī)則里面所有元組的概率和，表示為PRPRTRRT一個生成規(guī)則的長度LENGTH就是這個規(guī)則的元組的數目，表示為|R|。單一規(guī)則（SINGLETONRULE）長度為1的生成規(guī)則，即|R|1。多元組規(guī)則（MULTIRULE）長度大于一的生成規(guī)則，即|R|1。依賴元組出現在多元組規(guī)則的元組。獨立元組不是依賴元組的元組。一個可能世界W就是T的一個子集，使得對每一個生成規(guī)則TR如果PRR1則|RW|1；如果PRR1則|RW|1。表示所有可能世界實例。對于一個不確定表T，它的生成規(guī)則集合為T，他的所有可能世界實例的數目就是那些概率為1的生成規(guī)則的長度與那些概率不為1的生成規(guī)則的長度加1的和的乘積。表示為1|1PR,|1PR,|RRRRRRWTT可能世界的存在概率（EXISTENCEPROBABILITY）每個可能世界出現的概率。公式為第二章不確定性數據的模型7|,1|,PR1PRPRWRRWRRTTRWRW假設在一個概率數據庫里面有下面這個不確定性表T表23不確定性表元組概率T103T204T305T410T508T602它的生成規(guī)則為（R1T2T3，R2T5T6）。根據生成規(guī)則的概率公式可知PRR1PRT2PRT30405090，進一步，1PRWW。24針對關系型數據針對關系模型的擴展最為常見，包括PROBABILISTICTABLE10、PROBABILISTICORSETTABLE11、PROBABILISTICORSETTABLE11、PROBABILISTICCTABLE12等。PROBABILISTICTABLE就一個針對關系型數據的模型。它以一個獨立的概率字段表示元組的概率，且各元組之間獨立。一個特定的數據庫實例也即可能世界實例的概率等于其所包含的元組的概率乘積和其所不包含的元組的不發(fā)生概率的乘積。PROBABILISTICTABLE能夠描述存在級不確定性，而PROBABILISTICORSETTABLE則傾向于描述屬性級不確定性。在PROBABILISTICORSETTABLE中，元組的屬性值被描述為多個候選值之間的“或”關系，可視為離散概率密度函數。PROBABILISTICORSETTABLE10,11則是上述兩種模型的綜合體。部分學者也將PROBABILISTICORSETTABLE命名為XRELATION，它包含若干XTUPLE無存在級不確定性或者MAYBEXTUPLE有存在級不確定性13,14。PROBABILISTICCTABLE模型的定義與PROBABILISTICORSETTABLE模型比較類似，不同之處在于它是從CTABLE衍生出來的。25針對半結構化數據模型半結構化數據模型SEMISTRUCTUREDDATAMODEL能有效描述缺乏嚴格模式結構的數據。半結構化數據通?？梢杂梦臋n樹來描述。DEKHTYAR等人提出了一種管理概率半結構化數據PROBABILISTICSEMISTRUCTUREDDATA的方法，該方法以關系數據庫技術為基礎，支持豐富的代數查詢。更多的工作則是直接以文檔樹形式描述不確定性半結構化數據，例如P文檔PDOCUMENTMODEL、概率樹模型、PXML模型、PRXML模型等。第二章不確定性數據的模型926數據流模型在數據流模型中，數據到達的速度極快、數據規(guī)模極大，僅能夠開發(fā)一次掃描算法，使用有限內存在線計算查詢結果。在不確定性數據流UNCERTAINDATASTREAM，或PROBABILISTICDATASTREAM中，各元組具有不確定性。27針對多維數據模型OLAP提供了一種多維數據分析手段，能夠快速得到復雜的查詢統(tǒng)計結果。OLAP中數據立方DATACUBE的基本元素是CUBOID。在確定性多維數據模型中，各個事實FACT必定屬于某一個立方體中。但對于處理不精確數據的應用而言，各事實可能無法被準確地定位到立方體中。例如，考慮一個有關汽車銷售的多維數據模型，它包括兩個維度CITY與AUTOMOBILE，分別表示購車城市與車體型號。CITY維度是一個三級層次結構，國家省市。若僅僅知道某輛“奔馳車”是從“浙江北部城市”購買的話，由于“浙江北部城市”包含多個城市，該條記錄是不確定性數據，無法存放到事實表中去。28概率數據庫和不確定對象模型的相互轉換在離散的情形下，不確定對象模型和概率數據庫模型是等價的?？梢允褂孟旅娴姆椒▉韺⒉淮_定對象轉化為概率表。對于不確定對象U中的每一個實例U，創(chuàng)建一個元組TU,它的概率為FU。對每一個不確定對象UU1,UL,創(chuàng)建一個生成規(guī)則LUUUTTR1。在所有的情形，一個概率表總是可以使用一系列的不確定對象來表示的。方法如下為不確定表T中的每一個元組T創(chuàng)建一個實例UT,它的概率密度函數為FUTPRT。對于一個生成規(guī)則RRMRTT1,創(chuàng)建一個不確定對象UR，它包含所有與元組TR1,TRM對應的實例UTR1,UTRM。進一步，如果MIRIT11PR則創(chuàng)建另外一個實例U，它的概率密度函數為MIRITUF1PR1，然后把U添加到不確定對象UR。由于任意兩個生成規(guī)則里面沒有相同的元組，所有構建出來的所有不確定對象不會有共同的實例。29本章小結本章介紹了幾種不確定性數據的模型。其中可能世界模型是應用的最廣泛的模型。所有的數據模型都可以從可能世界模型衍生。但是可能世界實例的數量會隨著元組的數目的增加而呈指數式增長，這就導致可能世界實例的數量遠遠大于數據庫的規(guī)模?？赡苁澜缒Ｐ途哂幸韵滤膫€方面的特點1所有實例的概率之和為1。2每個可能世界實例出現的概率為該實例中所有元組的概率與不在該實例中的元組本科畢業(yè)論文10不出現的概率的乘積。3每個元組出現在所有可能世界的概率總和等于它本身的概率。4有N個元組就有2N個可能世界實例。第三章不確定性數據的查詢11第三章不確定性數據的查詢查詢分析處理是不確定性數據管理的最終目標。查詢類型非常豐富，例如TOPK查詢、PSKYLINE查詢、流數據查詢等。盡管可以分別針對各個可能世界實例計算查詢結果，再合并中間結果以生成最終查詢結果，但由于可能世界實例的數量遠大于不確定數據庫的規(guī)模，該方法并不可行。因此，必須采用排序、剪枝等啟發(fā)式技術優(yōu)化處理，以提高效率。另外，由于輸入數據具有不確定性，查詢結果也往往是近似結果。31基于不確定性數據的TOPK查詢面向確定性數據庫的TOPK查詢的定義非常清晰返回RANKING函數值最大的K個元組。但是在不確定性數據庫上根據應用的不同可以存在多種定義方法。目前，基于不確定性數據的TOPK查詢主要有UTOPK15、UKRANKS15、PTK5、PKTOPK16四種。接下來的四個小節(jié)將介紹這四種查詢，包括它們的定義、舉例說明以及相關的算法。對這四種查詢的舉例都是基于下面這個不確定性表的。考慮下面這個不確定性表T，它包含六個元組，每個元組都有一個分數和概率屬性。表31不確定性表元組分數概率T19503T29004T38005T47810T58708T67002生成規(guī)則（T2T3，T5T6）因為T2和T3是互斥的，并且PR2,3PT2PT3040509T2T5T3T4T6。所有可能世界實例及其概率如下表本科畢業(yè)論文12表32所有可能世界實例32UTOPK查詢321UTOPK查詢的定義文獻15提出了UTOPK和UKRANKS兩種基于不確定性數據的查詢，其中UTOPK查詢的定義如下定義1UNCERTAINTOPKQUERYUTOPK）令D為一個不確定數據庫，它的可能世界空間為PWPW1,PWN令TT1,TM為一系列長度為K的元組矢量，對于每個TIT（1）TI中的所有元組是按照得分函數F排名的，（2）TI是非空可能世界PWTPWI的TOPK查詢結果?；贔的UTOPK查詢返回TT，其中PRMAXARGIITPWWTTWT。UTOPK查詢返回一個長度為K的元組矢量，它在所有可能世界中的發(fā)生概率最大。當我們要求TOPK返回的所有元組都來自同一個可能世界的時候，使用UTOPK查詢是適合的。322UTOPK查詢舉例考慮31節(jié)的例子PT1,T2PW1PW2012PT1,T5PW3PW50144PT1,T3PW4003PT1,T4PW60006PT2,T5PW70224PT2,T4PW80056PT5,T3PW9028PT3,T4PW10007PT5,T4PW110056可能世界實例概率按分數排名的TOP2W1T1,T2,T4,T50096T1,T2W2T1,T2,T4,T60024T1,T2W3T1,T3,T4,T5012T1,T5W4T1,T3,T4,T6003T1,T3W5T1,T4,T50024T1,T5W6T1,T4,T60006T1,T4W7T2,T4,T50224T2,T5W8T2,T4,T60056T2,T4W9T3,T4,T5028T5,T3W10T3,T4,T6007T3,T4W11T4,T50056T5,T4W12T4,T60014T4,T6第三章不確定性數據的查詢13PT4,T6PW120014因為在所有可能世界實例出現的概率總和為最大，所有UTOP2返回的結果為，它們出現在W9。從這個例子可以看出，UTOPK返回的結果集中的元組必須同時出現在某個可能世界實例。另外，這些元組在所有元組的排名不需要在前K個位置，在這里，T5排在第三，T3排在第四，都不是在前二。323UTOPK查詢算法分析3231UTOPK查詢算法1文獻15基于可能世界語義提出了解決TOPK查詢的不確定數據模型。在該模型中，每個元組屬于數據庫的概率被稱為置信度，產生規(guī)則是任意的邏輯公式用來確定有效的世界，每個可能世界是元組的聯(lián)合。通過假設世界中存在的元組可以根據元組的置信度以及產生規(guī)則計算世界的概率。該文獻提出了基于搜索空間的方法來處理UTOPK查詢與UKRANKS查詢。各元組首先按照RANKING函數從大到小進行排序，然后不斷地構造搜索空間，縮小空間的范圍，最終獲得查詢結果。為了說明算法，引入了搜索狀態(tài)SL表示一個長度為L的元組向量，根據得分函數在一個或多個可能世界中成為TOPL結果。假設D是目前從數據庫中訪問的元組數，SL的概率PSLPRSLISL，D），其中ISL，D）表示在已訪問的元組中而不在SL中的元組。將SL轉變?yōu)镾LI，下標I表示該向量最后的可見元組所在的位置。對于UTOPK查詢，使用OPTUTOPK算法，該算法的基本思想1設置一個以搜索狀態(tài)概率優(yōu)先級排序的隊列Q，初始化時插入S0,0，概率PS0,01。2）當Q不為空時不斷執(zhí)行下面操作從Q中彈出SL,I；如果LK時返回SLI，否則根據I和D的比較情況選擇下一個要訪問的元組T；分別對T可以加入和不加入SLI兩種情況，將SL1，I1和SL，I1插回Q。3232UTOPK查詢算法2文獻17在基于可能世界語義上提出一種高效的方法來處理UTOPK和UKRANKS兩種TOPK查詢。為了簡化問題，作者首先假設各個元組是獨立的，也就是如果有N個元組則有2N個不同的可能世界實例。為了處理TOPK查詢，按照排名逐個檢索元組，并且盡可能快的停止檢索。這里作者提出了掃描深度SCANDEPTH）的概念，掃描深度N就是保證結果正確所必須要掃描的元組的最小數目。定義2掃描深度（SCANDEPTH）假設在不確定數據庫D里面有T1,TN這些已經排序的元組。對于UTOPK和UKRANKS查詢，掃描深度N就是最小的N使得下面的描述成立對于任意的D，D的前N個元組與D在相同的排序準則是一樣的，在D上的查詢結果與在D上的查詢結果是一樣的。用W|DI來表示從DI生成的一個可能世界實例，它的概率為PRW|DI。對于KI，令SI表示從DI生成的包含K個元組的可能世界，即，|PRMAXARG|IKWIDWS，令IPRSI|DI。本科畢業(yè)論文14作者提出的算法框架是一個個元組檢索，當I從K遞增到N的過程中，計算SI。最后取SI作為結果集，此時SI對于的I是最大的。引理1|MAX|PRNIKTDWI證明令|MAXTTIII。顯然，|PR|PRIITDWTDW，因此，|MAX|PRNIKTDWI。另一方面，考慮任意T，令|MAXTTIII，根據定義，對于任意的I有|PR|PRITDWTDW。因此可以得出|MAX|PRNIKTDWI使用引理1使得我們不需要枚舉所以可能世界并且計算最大的總概率，我們只需要計算最大的I以及與其對應的SI，而這個SI就是UTOPK查詢的結果。因此，UTOPK查詢的問題就轉化為對于IK,K1,N，計算I以及與其對應的SI。實際上，只要我們確定剩下的I不可能大于目前已經找到的I，那么我們就可以停止處理了。引理2對于一個單一選擇的數據庫D和任意的NIK，SI包含了DI中置信度最大的K個元組，并且IIJIJSDTJSTJITPTP1證明因為PRW|DI是兩個因子的乘積，在W中的所有元組出現的概率以及剩余的所有元組不出現的概率，當W包含K個置信度最大的元組時這兩個因子都會取得最大值。只要知道了SI，那么I也就知道了。引理3對于一個單一選擇的數據庫D和一個UTOPK查詢，掃描深度就是最小的N使得NIIIINITPTP111,MAXMAX（31）證明我們首先證明，當31發(fā)生的時候，必須要再檢索元組了。這是因為31的左邊是檢索了N個元組之后找到的最好的答案；而31的右邊是PRW|DI的上邊界，對于任意的W和任意的IN。其次，我們證明如果31不成立，那么我們肯定還沒有到達掃描深度。這個條件是緊湊的。這保證了我們的算法不會檢索多余N個元組。我們首先證明下面的斷言如果我們檢索了K個置信度大于等于1/2的元組，那么31必定成立。考慮第一次檢索了K個這樣的元組，例如檢索完TS。因為這K個在DS置信度最大的元組必定是置信度大于等于1/2的K個元組。結合引理2，我們有SITIPTIPSISI11,MAXMAX1。進一步地，因為31的左邊從不變小并且31的右邊從不變大，當我們檢索了N個元組的時候，31第三章不確定性數據的查詢15依然成立。我們構造另外一個不確定數據庫D，它的前N個元組與D是一樣的，而其余元組的置信度為1，我們討論一定可以從D中找到比D更好的UTOPK結果如果31沒有成立的話。因為31沒有成立，所以在D和D的前N個元組中必定有L。從結果可以看出UKRANKS查詢返回結果包含K個元組，但這K個元組不一定會出現在某個可能世界實例中，并且某個元組可以在結果集出現多次，如本例的T5。333UKRANKS查詢算法分析3331UKRANKS查詢算法1文獻15除了給出UTOPK算法（見323）外，還給出UKRANKS查詢算法。對于UKRANKS查詢使用OPTUKRANKS算法，該算法的基本思想是在計算排名I時，對于一個新來的元組T，計算其在所有可能世界在排名I上出現的概率PT,I；如果PT,I比目前答案的概率大，并且比將未見元組考慮進來時的概率也大，那么T是結果集中排名為I的元組。3332UKRANKS查詢算法2文獻17除了介紹給出UTOPK算法以外，還介紹了使用一個動態(tài)編程的算法來處理UKRANKS查詢。這個算法是基于下面這個簡單的知識的一個元組TI排名在第J個位置的第三章不確定性數據的查詢17概率依賴于前面的I1個元組有J1個元組出現，而不管這J1個元組是什么。令D為一個單選擇的不確定數據庫。對于NIJ1，令RI,J為DI中一個可能世界有J個元組的概率，即，JWIJIDWR|,|PR。我們同樣定義R0,01。顯然，TI在隨機生成的可能世界中排名J的概率為1,1JIIRTP。因此，在不確定數據庫D中的UKRANKS查詢結果為TXJ，使得對于J1,K，有MAXARG1,1JIINIJRTPJX（32）這樣剩下的任務就是計算RI,J了，它由下面的公式得出,00,10,1,11,1,OTHERWISEJIIFJIIFRTPRTPRJIIJIIJI（33）公式33的正確性是顯而易見的為了從DI中取得J個元組，要么就選擇TI然后從DI1中選擇J1個元組，要么不選擇TI然后從DI1中選擇J個元組。檢索每個元組TI時，對于J0,1,MINI,K，算法使用33來計算RI,J。根據（32），這同樣保存了目前找到的最好的答案XJ。為了計算RI,J，只需計算RI1,J，在計算過程中，需要的空間為OK。最后，得出掃描深度N有如下特性，使得能夠在得出結果的時候停止，只需要從元組表里檢索N個元組，這是最少的。引理4對于一個單選擇不確定數據庫D和一個UKRANKS查詢，掃描深度N就是最小的N使得對于J1,K下面這條公式成立10,1,1JLLNNIJJIIRRTP（34）證明因為34的左邊是當前排在J位置最好的結果，有足夠的證據證明，對于任意D，假設它的元組為T1,TN,TN1,TN,34的右邊是TI排在第J（J1,K個位置的概率的上邊界，而這個上邊界是可以獲得的。首先，對于任意IN，考慮TI成為從D中隨機生成的世界第J個元組的概率。令S為TN1,TI1中有S個元組出現的概率（如果IN1則01，有LNJLJLLJNJLLJNIIRLRLRTPTDWJ,0101101MAX,|PR最后一條不等式之所以成立時因為110JSS。因此，在得到正確的結果之前我們最多需要訪問N個元組。其次，我們證明對于任意的J，總有一個D能夠達到這個上邊界。令PTN1PTN1，且LNJLRL,10MAXARG。考慮元組TNJL，它出現在D中隨機生成的可能世界的第J個位置的概率為RN,L。因此，為了避免出錯，我們最少需要訪問N個元組。因為對于每一個元組和KJ1我們可以在OK）時間內檢查不等式34，所以下面的本科畢業(yè)論文18定理成立。定理2對于一個單選擇不確定數據庫，我們的算法能夠在檢索N個元組之后得出UKRANKS查詢的結果，時間開銷為ONK，空間開銷為OK）。3333算法1與算法2的比較對于各個元組都是獨立的情況下，算法1與算法2的比較如下表34兩種UKRANKS查詢算法比較時間空間算法1N2KNK算法2NKK34PTK查詢341PTK查詢定義文獻5提出了PTK查詢。給定一個閾值P，PTK返回所有在可能世界實例中成為TOPK的總概率超過閾值P的元組。其公式表示如下PR,|,PTTTTTPQANSWERKQ要理解這條公式的意義，還必須要了解作者提出的其他相關的概念。一個TOPK查詢表示為QK（P，F），包含一個謂詞P，一個等級排序函數F，和一個整型K0。QK（W）表示TOPK在可能世界W上查詢Q返回的元組集合，它包含K個元組。PTK在一個不確定表T的查詢包括一個TOPK查詢Q和一個概率閾值P0假設給定的閾值P為039則，PT2返回的結果為假設給定的閾值P為05則，PT2返回的結果為從本例可以看出，PTK查詢返回的結果所包含的元組個數與閾值P有關，P越大，那么符合條件的元組就越少，返回結果的元組個數就越少。343PTK查詢的算法文獻5提出了PTK查詢的定義，并且給出了一個高效的算法首先，根據謂詞P去掉不確定表T中不符合P的元組并且對各個元組按照得分函數F進行排序；然后對PT中的每個元組T計算它的壓縮統(tǒng)治集以及該統(tǒng)治集的子集概率；接著，計算T成為TOPK的概率PRKT，如果PRKT超過閾值P則輸出T；最后利用T來對未計算的元組進行剪枝，如果剩下未計算的所有元組都不能滿足閾值P則退出循環(huán)。在介紹該算法的時候，作者首先假設各個元組是獨立的，并且已經按照得分函數進行排列。如果各個元組不是獨立的，那么可以通過把產生規(guī)則中的元組壓縮為一個規(guī)則元組；如果各個元組不是按照得分函數進行排序的，那么可以按照某種方法對一個元組的壓縮統(tǒng)治集進行排序。要理解該算法，除了要知道341提到的各個概念之外，還必須要理解統(tǒng)治集、規(guī)則元組壓縮、通過共享前綴來減少掃描、剪枝技術等概念及其相關的定理、推論?？紤]在一個不確定表T進行TOPK查詢QKP，F。滿足查詢謂詞的元組集合表示為|TRUETPTTTTPPT同樣是不確定表，它里面的各個元組依然包含概率，進一步，T中的生成規(guī)則R除去不在PT中的元組，然后映射到PT。因此，PTK查詢就是從PT）中找出TOPK概率超過閾值的元組。3431統(tǒng)治集PT包含了所有滿足查詢的元組、元組的概率以及生成規(guī)則。去除不在PT的元組不會影響TOPK查詢結果。因此，,TPPQANSWERTPQANSWER。我們在TOPK查詢的時候只需要考慮PT。在PT中的一個元組T是否成為TOPK查詢結果只受那些排列在T前面的元組的影響。統(tǒng)治集（DOMINANTSET）對于PT中的一個元組T，它的統(tǒng)治集就是PT中所有排在T前面的元組的集合。表示為|TTTTSFTPT定理3統(tǒng)治集屬性THEDOMINANTSETPROPERTY對于一個元組TT，PRPR,TTKSQKTQT。本科畢業(yè)論文203432基本的案例在基本的案例當中，作者假設所有的元組是獨立的，LT1TN是PT中的所有元組并且是按照得分函數進行排序的。一個元組出現在一個可能世界的第J個位置當且僅當它的統(tǒng)治集有J1個元組出現。位置概率POSITIONPROBABILITY在一個可能世界中一個元組出現在第J個位置的概率，表示為PRTI,J。子集概率PRSTI,J在一個可能世界中STI出現J個元組的概率。10,PR，且0,PRJ（NJ0）。一個元組出現在一個可能世界的第J個位置的概率等于該元組出現的概率乘以該元組的統(tǒng)治集有J1個元組出現在該可能世界的概率，公式為1,PRPR,PRJSTJTITII（35）顯然，一個元組TI的TOPK概率為這個元組出現在第1,2,3K個位置的概率和，表示公式為KJTIKJIIKJSTIJTT111,PRPR,PRPR（36）顯然，當KI的時候，一個元組TI成為TOPK的概率等于它本身的概率，也就是PRPRIIKTT。定理4對于|,1TJI，有1元組TI的統(tǒng)治集STI出現0個元組的概率為TI1不出現的概率與TI1的統(tǒng)治集出現0個元組的概率的乘積，公式為1111PR1PR10,PR0,PR1IJIITTITTSSI2元組TI的統(tǒng)治集STI出現J個元組的概率為TI1出現的概率與TI1的統(tǒng)治集出現J1個元組的概率的乘積與TI1不出現的概率與TI1的統(tǒng)治集出現J個元組的概率的乘積的和，公式為PR1,PRPR1,PR,PR1111ITITTITJSTJSJSII運用定理2來計算各個元組成為TOPK的概率要求各個元組是獨立的，時間復雜度為OKN），N是不確定表T里面的元組的個數。定理4是一種基本的情形，所有的元組都是獨立的，如果元組之間不是獨立的，那么在計算元組T的TOPK概率時就要考慮T與生成規(guī)則R的關系了。3433規(guī)則元組的壓縮在計算元組T的TOPK概率時，