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

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