[發(fā)明專利]一種面向不確定數(shù)據(jù)的概率查詢質(zhì)量優(yōu)化方法

在審

• 申請?zhí)枺?/td>: 201710039240.6
• 申請日: 2017-01-19
• 公開（公告）號: CN106897375A
• 公開（公告）日: 2017-06-27
• 發(fā)明（設(shè)計）人: 高云君;苗曉曄;周琳琳;陳剛;郭素
• 申請（專利權(quán)）人: 浙江大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州求是專利事務(wù)所有限公司33200
• 代理人: 邱啟旺

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)庫查詢處理技術(shù)，特別是一種面向不確定數(shù)據(jù)的概率查詢質(zhì)量優(yōu)化方法。

背景技術(shù)

不確定數(shù)據(jù)的產(chǎn)生源于許多現(xiàn)實(shí)生活中的應(yīng)用，如傳感器輸入噪聲、無線傳輸錯誤、數(shù)據(jù)集成中數(shù)據(jù)錯漏等。因此，在數(shù)據(jù)庫領(lǐng)域中，不確定數(shù)據(jù)查詢(如概率Skyline計算、概率k最近鄰查詢、概率Top-k查詢等)處理已受到了廣泛關(guān)注。

在不確定數(shù)據(jù)庫中，一般概率查詢返回的查詢結(jié)果是結(jié)果概率非零的對象。而數(shù)據(jù)集的不確定性會傳播給查詢結(jié)果，所以用戶很難得到預(yù)期精準(zhǔn)無誤的查詢結(jié)果。低質(zhì)量的查詢結(jié)果也很難幫助用戶進(jìn)行正確決策，因此需要對數(shù)據(jù)集進(jìn)行清洗以降低不確定性，從而提高查詢結(jié)果的質(zhì)量。

眾所周知，數(shù)據(jù)清洗是提高質(zhì)量的有效途徑，但同時也是一個費(fèi)時費(fèi)力且代價高昂的過程，尤其在大數(shù)據(jù)環(huán)境下，想要清洗所有的不確定數(shù)據(jù)更是不切實(shí)際。目前針對不確定數(shù)據(jù)的建模和查詢處理問題，國內(nèi)外學(xué)者已經(jīng)做出了一些工作，但這些工作還存在局限性：(1)查詢算法中沒有考慮用戶資源有限的情況；(2)數(shù)據(jù)清洗算法中沒有面向概率Skyline查詢和概率k最近鄰查詢的有效算法。

發(fā)明內(nèi)容

針對上述不足，本發(fā)明提供一種面向不確定數(shù)據(jù)的概率查詢質(zhì)量優(yōu)化方法，以解決在用戶資源有限的條件下，在清洗數(shù)據(jù)的同時，盡可能地提高查詢質(zhì)量。

本發(fā)明解決其技術(shù)問題采用技術(shù)方案的步驟如下：一種面向不確定數(shù)據(jù)的概率查詢質(zhì)量優(yōu)化方法，該方法包括如下步驟：

步驟(1)：給定概率查詢φ(q,S)，q是查詢對象，S是不確定數(shù)據(jù)集，對于不確定數(shù)據(jù)集中結(jié)果對象集構(gòu)建ASI索引；維護(hù)一個最大的查詢結(jié)果質(zhì)量及相應(yīng)的清洗對象集合；

步驟(2)：基于用戶給定的清洗預(yù)算，通過剪枝策略在不確定數(shù)據(jù)集中找到候選的清洗對象集合，并將候選清洗對象集合放入清洗對象集合列表中；

步驟(3)：對于步驟(2)中得到的清洗對象集合列表中的集合，計算其查詢期望質(zhì)量，并更新維護(hù)的最大查詢結(jié)果質(zhì)量及相應(yīng)的清洗對象集合，利用期望質(zhì)量單調(diào)性更新清洗對象集合列表；

步驟(4)：重復(fù)步驟(3)直到清洗對象集合列表為空；

步驟(5)：返回最終的最大查詢結(jié)果質(zhì)量及相應(yīng)的清洗對象集合，對期望質(zhì)量最大的清洗對象集合進(jìn)行清洗，完成了概率查詢的質(zhì)量優(yōu)化。

進(jìn)一步的，所述構(gòu)建ASI索引的具體步驟如下：

ASI索引是一個哈希表，以結(jié)果對象集R為鍵值，每個結(jié)果對象集存儲其相應(yīng)的結(jié)果元組集r；對每個r，存儲概率值Pr(r)，以及概率向量概率向量中每一項(xiàng)表示結(jié)果元組集r相對于數(shù)據(jù)對象o的關(guān)聯(lián)概率P(o,r)；

利用ASI索引能夠直接計算出每個結(jié)果對象集的概率，使得計算查詢期望質(zhì)量時無需遍歷所有可能世界。

進(jìn)一步的，所述步驟(2)中通過剪枝策略在不確定數(shù)據(jù)集中找到候選清洗對象集合具體如下：如果不確定數(shù)據(jù)集中的對象成為結(jié)果對象的概率為0，那么對象能夠被剪枝；反之，不確定數(shù)據(jù)集中的對象加入到候選清洗對象集合中。

進(jìn)一步的，所述步驟(3)中計算其查詢期望質(zhì)量具體步驟如下：

給定對象集合O_c，針對每一個O_c清洗后可能變成的集合T_c，計算變成T_c的概率Pr(T_c)，再計算出清洗成T_c后的對應(yīng)的查詢質(zhì)量κ(φ|T_c)，O_c的查詢期望質(zhì)量則利用公式計算得到；

所述步驟(3)中更新清洗對象集合列表采用如下三種清洗對象優(yōu)選算法中的一種：

(3.1)B&B算法，算法步驟包括：

(3.1.1)清洗對象集合列表用堆實(shí)現(xiàn)，表示一棵分支界限樹；

(3.1.2)彈出堆頂對象集合O，若該集合的清洗代價不大于給定預(yù)算值且未訪問過，則

計算其期望質(zhì)量，并記錄最大期望質(zhì)量及對應(yīng)對象集合；若該集合的清洗代價大于給定

預(yù)算值，則將O的未被訪問且未被剪枝的第i個子集O_i加入堆中且O_i滿足|O_i|＝|O|-1；

(3.1.3)若堆不為空，則返回步驟(3.1.2)執(zhí)行，若堆為空，結(jié)果元組記錄最大期望質(zhì)

量及對應(yīng)對象集合，算法結(jié)束；