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

有效

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

1.一種基于PME圖模型的一對一型PSJ聚集查詢方法，包括：

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

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

所述步驟(2)包括：

(2-1)對于所述葉子極大團，在出現父親頂點和不出現父親頂點兩種情況下，分別計算以所述葉子極大團為根的子樹的聚集值條件概率分布；

(2-2)基于步驟(2-1)，對于所述中間極大團，在出現父親頂點和不出現父親頂點兩種情況下，分別計算以所述中間極大團為根的子樹的聚集值條件概率分布；

(2-3)基于步驟(2-2)，對于所述根極大團，在出現一個私有頂點和不出現私有頂點兩種情況下，分別計算整棵樹的聚集值條件概率分布；

(2-4)合并步驟(2-3)中兩種情況下的聚集值條件概率分布的生成函數，得到整棵樹的聚集值概率分布的總生成函數，然后將所述總生成函數還原為離散序列，得到整棵樹的聚集值概率分布；

所述步驟(2-1)包括：

當出現父親頂點v_f情況下，計算所述葉子極大團為根的子樹T_leaf的聚集值條件概率分布的生成函數如公式(1)所示：

當不出現父親頂點v_f情況下，計算所述葉子極大團為根的子樹T_leaf的聚集值條件概率分布的生成函數如公式(2)所示：

其中，F表示頂點的屬性，p(v_{p_i})表示第i個私有頂點v_{p_i}的概率，p(v_f)表示父親頂點v_f的概率，m表示所述葉子極大團中私有頂點的總個數。

2.如權利要求1所述的基于PME圖模型的一對一型PSJ聚集查詢方法，其特征在于，在構造樹狀PME圖前，采用Kruskal算法刪除PSJ構成的二分圖中的回路，構造所述PSJ的最大生成樹，并基于所述最大生成樹構造所述樹狀PME圖。

3.如權利要求1所述的基于PME圖模型的一對一型PSJ聚集查詢方法，其特征在于，所述基于聚集查詢謂詞條件為頂點添加屬性包括：

為滿足COUNT查詢謂詞條件的頂點增加標志屬性；

為滿足SUM查詢謂詞條件的頂點增加求和屬性。

4.如權利要求3所述的基于PME圖模型的一對一型PSJ聚集查詢方法，其特征在于，所述基于聚集查詢謂詞條件為頂點添加屬性的具體步驟為：

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

若聚集查詢為COUNT查詢，為剩余的所有頂點增加一個屬性F，表示是否滿足謂詞條件，針對頂點v，若頂點v滿足謂詞條件，那么F＝1，否則F＝0；

若聚集查詢為SUM查詢，為剩余的所有頂點增加一個屬性F，表示求和屬性值的大小，針對頂點v，若頂點v滿足謂詞條件，那么F等于頂點v對應的PSJ連接的求和屬性值，否則F＝0。

5.如權利要求1所述的基于PME圖模型的一對一型PSJ聚集查詢方法，其特征在于，當COUNT查詢時，在為頂點添加屬性后，還需要對屬于同一極大團的私有頂點進行合并。

6.如權利要求1所述的基于PME圖模型的一對一型PSJ聚集查詢方法，其特征在于，所述步驟(2-2)包括：

當出現父親頂點v_f情況下，計算所述中間極大團為根的子樹T_mid的聚集值條件概率分布的生成函數如公式(3)所示：

當不出現父親頂點v_f情況下，計算所述中間極大團為根的子樹T_mid的聚集值條件概率分布的生成函數如公式(4)所示：