[發(fā)明專利]多個(gè)連續(xù)top-k關(guān)鍵詞查詢結(jié)果更新方法、系統(tǒng)、存儲(chǔ)介質(zhì)及終端

有效

• 申請(qǐng)?zhí)枺?/td>: 201710909356.0
• 申請(qǐng)日: 2017-09-29
• 公開（公告）號(hào): CN109582698B
• 公開（公告）日: 2021-08-13
• 發(fā)明（設(shè)計(jì)）人: 許延偉
• 申請(qǐng)（專利權(quán)）人: 上海寬帶技術(shù)及應(yīng)用工程研究中心
• 主分類號(hào): G06F16/2455
• 分類號(hào): G06F16/2455;G06F16/28;G06F16/22
• 代理公司: 上海光華專利事務(wù)所(普通合伙) 31219
• 代理人: 徐秋平

本發(fā)明提供一種多個(gè)連續(xù)top?k關(guān)鍵詞查詢結(jié)果更新方法、系統(tǒng)、存儲(chǔ)介質(zhì)及終端，包括以下步驟：將每個(gè)關(guān)鍵詞基于關(guān)系數(shù)據(jù)庫在先元組查詢的備選網(wǎng)絡(luò)表示為一個(gè)以新元組為根節(jié)點(diǎn)的網(wǎng)絡(luò)樹；通過自上向下合并近似邊的方式將所有的網(wǎng)絡(luò)樹合并為一個(gè)以新元組為根節(jié)點(diǎn)的根樹；自上向下逐層計(jì)算所述根樹中的連接，并根據(jù)連接之間的相似性進(jìn)行合并查詢，以獲取多個(gè)連續(xù)top?k關(guān)鍵詞基于新元組的查詢結(jié)果。本發(fā)明的多個(gè)連續(xù)top?k關(guān)鍵詞查詢結(jié)果更新方法、系統(tǒng)、存儲(chǔ)介質(zhì)及終端有效地提高了關(guān)系數(shù)據(jù)庫中多個(gè)連續(xù)top?k關(guān)鍵詞搜索的效率；降低了搜索處理過程中對(duì)關(guān)系數(shù)據(jù)庫的頻繁訪問；降低了搜索處理過程中的服務(wù)器內(nèi)存消耗。

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

本發(fā)明涉及信息處理的技術(shù)領(lǐng)域，特別是涉及一種多個(gè)連續(xù)top-k關(guān)鍵詞查詢結(jié)果更新方法、系統(tǒng)、存儲(chǔ)介質(zhì)及終端。

背景技術(shù)

關(guān)系數(shù)據(jù)庫是建立在關(guān)系模型基礎(chǔ)上的數(shù)據(jù)庫，借助于集合代數(shù)等數(shù)學(xué)概念和方法來處理數(shù)據(jù)庫中的數(shù)據(jù)。現(xiàn)實(shí)世界中的各種實(shí)體以及實(shí)體之間的各種聯(lián)系均用關(guān)系模型來表示。標(biāo)準(zhǔn)數(shù)據(jù)查詢語言SQL就是一種基于關(guān)系數(shù)據(jù)庫的語言，這種語言執(zhí)行對(duì)關(guān)系數(shù)據(jù)庫中數(shù)據(jù)的檢索和操作。關(guān)系模型由關(guān)系數(shù)據(jù)結(jié)構(gòu)、關(guān)系操作集合、關(guān)系完整性約束三部分組成。

隨著關(guān)系數(shù)據(jù)庫中存儲(chǔ)的文本數(shù)據(jù)的增加，簡單高效地從數(shù)據(jù)庫中查詢文本數(shù)據(jù)變得越來越重要。但是，傳統(tǒng)的結(jié)構(gòu)化查詢方法要求用戶掌握一定的結(jié)構(gòu)化查詢語言和數(shù)據(jù)庫模式的知識(shí)，從而極大地限制了其使用范圍。隨著互聯(lián)網(wǎng)的發(fā)展，越來越多的普通用戶需要訪問在線數(shù)據(jù)庫，這些用戶通常不具備結(jié)構(gòu)化查詢語言和數(shù)據(jù)庫模式的知識(shí)。隨著網(wǎng)絡(luò)搜索引擎的興起，關(guān)鍵詞查詢(Keyword Search)因?yàn)槠浜唵畏奖愕奶攸c(diǎn)得到了廣泛的使用。因此，在關(guān)系型數(shù)據(jù)庫中進(jìn)行關(guān)鍵詞搜索就成為一個(gè)很自然的需求。通過在關(guān)系數(shù)據(jù)庫中引入關(guān)鍵詞搜索，不僅使得更多的用戶可以在關(guān)系數(shù)據(jù)庫中查詢數(shù)據(jù)，而且使得在互聯(lián)網(wǎng)上發(fā)布數(shù)據(jù)庫內(nèi)容變得簡單易行，因而有著重大的理論意義與現(xiàn)實(shí)價(jià)值。近年來，關(guān)系數(shù)據(jù)庫中的關(guān)鍵詞搜索研究獲得了廣泛的關(guān)注，成為數(shù)據(jù)庫領(lǐng)域的研究熱點(diǎn)。

關(guān)系數(shù)據(jù)庫中關(guān)鍵詞搜索的結(jié)果是一組元組連接樹(Joined Tuple Tree，JTT)。JTT為數(shù)據(jù)庫中包含了關(guān)鍵詞的元組根據(jù)主外鍵引用關(guān)系連接起來的一個(gè)無環(huán)、無多重邊、無特定根節(jié)點(diǎn)的一個(gè)無向樹。每一個(gè)元組連接樹(JTT)都是一個(gè)關(guān)系代數(shù)表達(dá)式(Relational Algebra Expression)的結(jié)果。這種代數(shù)表達(dá)式被稱為備選網(wǎng)絡(luò)(CandidateNetwork，CN)。圖1所示即為一些備選網(wǎng)絡(luò)的示例。備選網(wǎng)絡(luò)的生成與關(guān)系數(shù)據(jù)庫模式以及關(guān)鍵詞在關(guān)系表中的實(shí)際分布有關(guān)，關(guān)系數(shù)據(jù)庫中top-k關(guān)鍵詞搜索的效率取決于如果快速有效地執(zhí)行這些生成的備選網(wǎng)絡(luò)從而找到關(guān)聯(lián)度最大的k的JTT作為搜索結(jié)果。

現(xiàn)有關(guān)系數(shù)據(jù)庫上的關(guān)鍵詞搜索系統(tǒng)主要包括基于數(shù)據(jù)圖(Data Graphbased)的方法和基于模式圖(Schema Graph-based)的方法。基于數(shù)據(jù)圖的方法的基本思想是在由數(shù)據(jù)庫中所有元組根據(jù)外鍵引用關(guān)系構(gòu)造的數(shù)據(jù)圖上尋找包含關(guān)鍵詞的子圖。基于模式圖的方法首先根據(jù)數(shù)據(jù)庫的模式將關(guān)鍵詞查詢“翻譯”為一系列的關(guān)系表的連接(Join)表達(dá)式，然后生成結(jié)構(gòu)化查詢語句交給關(guān)系數(shù)據(jù)庫管理系統(tǒng)去執(zhí)行生成查詢結(jié)果。

當(dāng)數(shù)據(jù)庫被更新以后，如何高效地維護(hù)top-k查詢結(jié)果是一個(gè)非常有挑戰(zhàn)性的工作。因?yàn)閿?shù)據(jù)庫更新不僅會(huì)導(dǎo)致新的查詢結(jié)果被生成和已有的查詢結(jié)果被刪除，而且已有查詢結(jié)果的關(guān)聯(lián)度也會(huì)被改變。若數(shù)據(jù)庫被持續(xù)更新時(shí)需要同時(shí)維護(hù)多個(gè)關(guān)鍵詞查詢的top-k結(jié)果，則面臨更大的挑戰(zhàn)。

連續(xù)top-k關(guān)鍵詞搜索的處理過程分為以下兩個(gè)步驟：

(1)在關(guān)鍵詞查詢提交到系統(tǒng)時(shí)為其計(jì)算初始的top-k結(jié)果，并保存計(jì)算結(jié)果后的CN的元組處理狀態(tài)。

(2)當(dāng)數(shù)據(jù)庫被改變以后更新top-k查詢結(jié)果。