[發(fā)明專利]基于屬性級(jí)不確定性模型的一對(duì)多型PSJ聚集查詢方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201711208820.X
• 申請(qǐng)日: 2017-11-27
• 公開（公告）號(hào): CN108073689A
• 公開（公告）日: 2018-05-25
• 發(fā)明（設(shè)計(jì)）人: 陳嶺;王俊凱
• 申請(qǐng)（專利權(quán)）人: 浙江大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 杭州天勤知識(shí)產(chǎn)權(quán)代理有限公司 33224
• 代理人: 胡紅娟

本發(fā)明公開了一種基于屬性級(jí)不確定性模型的一對(duì)多型PSJ聚集查詢方法，包括：1)首先利用屬性級(jí)不確定性模型為PSJ建模；2)在建模結(jié)果上，基于動(dòng)態(tài)規(guī)劃思想提出聚集查詢方法：先計(jì)算出PSJ子集的聚集值概率分布，然后在子集的結(jié)果上計(jì)算出PSJ全集的聚集值概率分布。本發(fā)明充分考慮一對(duì)多型PSJ的依賴關(guān)系，結(jié)合屬性級(jí)不確定性模型，解決了在一對(duì)多型PSJ上難以執(zhí)行COUNT查詢和SUM查詢的問題，在數(shù)據(jù)庫、聯(lián)機(jī)分析處理以及數(shù)據(jù)倉庫中具有廣闊的應(yīng)用前景。

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

本發(fā)明涉及概率型相似性連接(Probabilistic Similarity Join，PSJ)的聚集查詢領(lǐng)域，具體涉及基于屬性級(jí)不確定性模型的一對(duì)多型PSJ聚集查詢方法。

背景技術(shù)

連接聚集查詢?cè)跀?shù)據(jù)庫、聯(lián)機(jī)分析處理以及數(shù)據(jù)倉庫中應(yīng)用廣泛，此類查詢通常先采用連接操作將多張關(guān)系表合并起來，然后再執(zhí)行聚集運(yùn)算。然而，由于信息時(shí)代數(shù)據(jù)爆炸式增長(zhǎng)，數(shù)據(jù)本身的不確定性以及數(shù)據(jù)采集和集成過程中引入的不確定性，導(dǎo)致大量數(shù)據(jù)具有不完整性和模糊性。不確定性數(shù)據(jù)的存在常常使得多表之間無法連接，進(jìn)而導(dǎo)致基于連接操作的聚集查詢失敗。

PSJ查詢基于相似性度量函數(shù)，能夠?qū)⑾嗨频脑M連接起來，有效解決了不確定性數(shù)據(jù)的連接問題。按照映射約束的不同，PSJ可分為三類：一對(duì)一型PSJ、一對(duì)多型PSJ和多對(duì)多型PSJ。然而，PSJ查詢的原始結(jié)果通常為一組帶概率的連接，這組連接并不滿足映射約束。從這組PSJ中選取出部分連接，使其滿足映射約束，則該部分連接同時(shí)出現(xiàn)的狀態(tài)稱為一個(gè)可能世界，該可能世界的概率為該部分連接同時(shí)出現(xiàn)的聯(lián)合概率。在PSJ上執(zhí)行聚集查詢，實(shí)質(zhì)上是對(duì)所有可能世界求聚集值。但是，PSJ的可能世界數(shù)量眾多，基于PSJ的聚集查詢面臨挑戰(zhàn)。

在PSJ上做聚集查詢的方法較少。部分方法通過限制連接條數(shù)或者劃定概率閾值來減少可能世界數(shù)量，但是這些方法不但丟失了大量信息，而且不考慮映射約束。

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

本發(fā)明的目的是提供一種基于屬性級(jí)不確定性模型的一對(duì)多型PSJ聚集查詢方法，該方法能夠?qū)σ粚?duì)多型PSJ建模，并基于模型有效地計(jì)算一對(duì)多型PSJ的COUNT值和SUM值概率分布，進(jìn)而縮短計(jì)算時(shí)間，提高查詢效率。

為實(shí)現(xiàn)上述目的，本發(fā)明提供的技術(shù)方案為：

一種基于屬性級(jí)不確定性模型的一對(duì)多型PSJ聚集查詢方法，包括以下步驟：

(1)利用屬性級(jí)不確定性模型為一對(duì)多型PSJ建模，形成PSJ全集的建模結(jié)果；

(2)基于所述建模結(jié)果，采用動(dòng)態(tài)規(guī)劃思想，計(jì)算PSJ子集的聚集值概率分布，并基于所述PSJ子集的聚集值概率分布的結(jié)果，計(jì)算得PSJ全集的聚集值概率分布。

所述步驟(1)包括：

(1-1)為PSJ多端的每一條元組構(gòu)造一條虛擬連接，確保互斥連接的概率和為1；

(1-2)為滿足COUNT查詢謂詞條件的PSJ增加標(biāo)志屬性，為滿足SUM查詢謂詞條件的PSJ增加求和屬性；

(1-3)采用屬性級(jí)不確定性模型對(duì)PSJ建模，將多端的每一條元組建模為一條屬性級(jí)不確定性元組，組成屬性級(jí)不確定性元組全集，形成PSJ全集的建模結(jié)果。

作為優(yōu)選，所述步驟(1-2)包括：

若聚集查詢?yōu)镃OUNT查詢，則為PSJ增加一個(gè)屬性F，表示所述PSJ是否滿足謂詞條件，如果若所述PSJ滿足謂詞條件，那么F＝1，否則F＝0；

若聚集查詢?yōu)镾UM查詢，則為PSJ增加一個(gè)屬性F，表示所述PSJ求和屬性值的大小，若所述PSJ連接滿足謂詞條件，那么F等于所述PSJ的原始求和屬性值，否則F＝0。

所述計(jì)算PSJ子集的聚集值概率分布包括：