[發(fā)明專(zhuān)利]一種基于查詢計(jì)劃的聯(lián)邦型RDF系統(tǒng)Top-K查詢與優(yōu)化方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010977090.5
• 申請(qǐng)日: 2020-09-17
• 公開(kāi)（公告）號(hào): CN112100209B
• 公開(kāi)（公告）日: 2022-09-27
• 發(fā)明（設(shè)計(jì)）人: 葛寧超;彭鵬;秦拯;李明道;王青;張吉昕
• 申請(qǐng)（專(zhuān)利權(quán)）人: 湖南大學(xué)
• 主分類(lèi)號(hào): G06F16/2453
• 分類(lèi)號(hào): G06F16/2453;G06F16/27
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.一種基于查詢計(jì)劃的聯(lián)邦型RDF系統(tǒng)Top-K查詢與優(yōu)化方法，其主要特征是：

(1)基于同源歸并的查詢分解與數(shù)據(jù)源定位方法

定義集合D＝{D₁,D₂,D₃,...,D_n}表示一個(gè)聯(lián)邦型RDF系統(tǒng)有n個(gè)RDF數(shù)據(jù)源，對(duì)于每個(gè)RDF數(shù)據(jù)源D_i離線提取其所有謂詞m個(gè)，形成謂詞集合P(Di)＝{P₁,P₂,P₃,...,P_m}，不同的RDF數(shù)據(jù)源的謂詞集合之間可能存在交集，因此對(duì)于一個(gè)謂詞可能有多個(gè)RDF數(shù)據(jù)源；定義一個(gè)Hash映射集合HP,S存儲(chǔ)聯(lián)邦型RDF系統(tǒng)中所有關(guān)系謂詞及其對(duì)應(yīng)的RDF數(shù)據(jù)源集合，其中每一個(gè)映射元素P_k,S表示一個(gè)謂詞P_k的RDF數(shù)據(jù)源為集合S；

對(duì)于兩個(gè)不同的謂詞P_i和P_j，當(dāng)它們的RDF數(shù)據(jù)源H(P_i)＝H(P_j)時(shí)：①RDF數(shù)據(jù)源個(gè)數(shù)|H(P_i)|＝1；②RDF數(shù)據(jù)源個(gè)數(shù)|H(P_i)|＞1，且R_S(P)表示包含謂詞P的所有三元組主體集合，R_O(P)表示包含謂詞P的所有三元組客體集合，則表示包含謂詞P_i和P_j的兩個(gè)三元組可以合并為一個(gè)子查詢，該子查詢的RDF數(shù)據(jù)源為H(P_i)；

(2)基于代價(jià)模型和動(dòng)態(tài)規(guī)劃的最優(yōu)查詢計(jì)劃生成方法

對(duì)于聯(lián)邦型RDF數(shù)據(jù)系統(tǒng)中任意一個(gè)謂詞P_i，定義包含該謂詞的三元組總個(gè)數(shù)為Sum(P_i)＝card(σ_P＝Pi(D))；包含該謂詞的三元組中不同的主體個(gè)數(shù)為Subject(P_i)＝card(dom[π_S(σ_p＝pi(D))])；包含該謂詞的三元組中不同的客體個(gè)數(shù)為Object(P_i)＝card(dom[π_O(σ_p＝pi(D))])；表示包含謂詞P_i的三元組前連接基數(shù)，表示包含謂詞P_i的三元組后連接基數(shù)；則對(duì)于一個(gè)子查詢中兩個(gè)相連的三元組，設(shè)它們的謂詞分別為P₁、P₂，P₁的客體與P₂的主體相連，則其查詢代價(jià)為：

不同的子查詢執(zhí)行策略決定了子查詢的連接順序，而不同的子查詢連接順序的連接代價(jià)相差巨大；對(duì)于兩個(gè)子查詢Q₁和Q₂，它們的最小連接代價(jià)為：

其中M表示兩個(gè)子查詢相連三元組的主體取值個(gè)數(shù)，N表示對(duì)應(yīng)的客體取值個(gè)數(shù)；對(duì)于用戶提交的Top-K查詢語(yǔ)句Q，經(jīng)過(guò)查詢分解后得到一系列子查詢{Q₁,Q₂,Q₃,...,Q_n}，這些子查詢的最優(yōu)執(zhí)行計(jì)劃采用動(dòng)態(tài)規(guī)劃算法生成；

(3)基于深度優(yōu)先和子圖剪枝的查詢計(jì)劃執(zhí)行方法

根據(jù)最優(yōu)查詢計(jì)劃執(zhí)行子查詢的過(guò)程中依然有更進(jìn)一步的優(yōu)化策略：①將前序子查詢的查詢結(jié)果作為后序子查詢的values子句，縮小后序子查詢子圖匹配范圍，進(jìn)而提高查詢效率；②針對(duì)Top-K查詢特點(diǎn)，當(dāng)執(zhí)行完包含排序變量的子查詢后，采用深度優(yōu)先執(zhí)行策略對(duì)當(dāng)前查詢結(jié)果進(jìn)行剪枝，選取前K條數(shù)據(jù)作為后序子查詢的values子句，大幅度縮小所有后序子查詢子圖匹配范圍。