[發明專利]基于PME圖模型的一對一型PSJ聚集查詢方法

有效

• 申請號: 201711208879.9
• 申請日: 2017-11-27
• 公開（公告）號: CN108121765B
• 公開（公告）日: 2020-07-17
• 發明（設計）人: 陳嶺;王俊凱
• 申請（專利權）人: 浙江大學
• 主分類號: G06F16/2455
• 分類號: G06F16/2455
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 胡紅娟

本發明公開了一種基于PME圖的一對一型PSJ聚集查詢方法。具體步驟包括：1)首先利用PME圖模型將一對一型PSJ建模為一個樹狀PME圖；2)其次基于動態規劃思想先計算出子樹的聚集值概率分布，然后在子樹的結果上計算出整棵樹的聚集值概率分布；3)在計算概率分布的過程中，引入生成函數方法，并基于分治策略計算多個生成函數的乘積。本發明充分考慮一對一型PSJ的依賴關系，在PME圖模型的基礎上，解決了一對一型PSJ的COUNT查詢和SUM查詢問題，在數據庫、聯機分析處理以及數據倉庫中具有廣闊的應用前景。

技術領域

本發明涉及概率型相似性連接(Probabilistic Similarity Join，PSJ)的聚集查詢領域，具體涉及基于概率互斥圖(Probabilistic Mutual Exclusion Graphs，PME圖)模型的一對一型PSJ聚集查詢方法。

背景技術

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

PSJ查詢基于相似性度量函數，能夠將相似的元組連接起來，有效解決了不確定性數據的連接問題。按照映射約束的不同，PSJ可分為三類：一對一型PSJ、一對多型PSJ和多對多型PSJ。然而，PSJ查詢的原始結果通常為一組帶概率的連接，這組連接并不滿足映射約束。從這組PSJ連接中選取出部分連接，使其滿足映射約束，則該部分連接同時出現的狀態稱為一個可能世界，該可能世界的概率為該部分連接同時出現的聯合概率。在PSJ連接上執行聚集查詢，實質上是對所有可能世界求聚集值。但是，PSJ連接的可能世界數量眾多，基于PSJ的聚集查詢面臨挑戰。

在PSJ上做聚集查詢的方法較少。部分方法通過限制連接條數或者劃定概率閾值來減少可能世界數量，但是這些方法不但丟失了大量信息，而且不考慮映射約束。有方法在考慮映射約束的情況下，基于動態規劃思想解決了一對一型PSJ的聚集查詢問題。但是該方法需逐個計算聚集值的概率，效率較低，因此在一對一型PSJ上做聚集查詢的方法仍存在較大優化空間。

發明內容

本發明的目的是提供一種基于PME圖模型的一對一型PSJ聚集查詢方法，該方法能夠在保證查詢信息質量的前提下，極大地提升聚集值的計算效率，縮短一對一型PSJ聚集查詢時間。

為實現上述目的，本發明提供的技術方案為：

本發明實施方式提供了一種基于PME圖模型的一對一型PSJ聚集查詢方法，包括以下步驟：

(1)基于PME圖模型，將PSJ作為頂點，互斥關系作為邊，構造樹狀PME圖，所述樹狀PME圖包括葉子極大團、中間極大團以及根極大圖，基于聚集查詢謂詞條件為所述樹狀PME圖的頂點添加屬性；

(2)基于步驟(1)，計算所述樹狀PME圖的聚集值概率分布。

上述技術方案中，采用概率互斥圖模型為PSJ建模，無需劃定概率閾值，也無需限定連接條數，保全了數據之間的依賴關系，能夠保證查詢信息的質量。

為了更準確對PSJ構造樹狀PME圖，在構造樹狀PME圖前，采用Kruskal算法刪除PSJ構成的二分圖中的回路，構造所述PSJ的最大生成樹，并基于所述最大生成樹構造所述樹狀PME圖。

所述基于聚集查詢謂詞條件為頂點添加屬性包括：為滿足COUNT查詢謂詞條件的頂點增加標志屬性；為滿足SUM查詢謂詞條件的頂點增加求和屬性，具體的步驟為：

刪除不滿足聚集查詢謂詞條件的私有頂點，其他頂點都保留；