[發(fā)明專利]一種基于角色組合的最優(yōu)組查詢方法

在審

• 申請?zhí)枺?/td>: 201710395866.0
• 申請日: 2017-05-25
• 公開（公告）號: CN108932274A
• 公開（公告）日: 2018-12-04
• 發(fā)明（設(shè)計）人: 秦小麟;郭成蓋;王寧;鄭偉;項哲慧;周楊淏
• 申請（專利權(quán)）人: 南京航空航天大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明涉及一種基于角色組合的最優(yōu)組查詢方法，屬于計算機數(shù)據(jù)庫管理系統(tǒng)中偏好查詢技術(shù)領(lǐng)域。本發(fā)明致力于從數(shù)據(jù)全集中選出n(n＞1)個元組組成最優(yōu)組對象。本發(fā)明首先提出了新的組對象量化模型角色組合。其中角色組合由n個角色構(gòu)成；角色以包含不同屬性權(quán)重的向量表示，等價于Top?k查詢中的效用函數(shù)。其次在角色組合的基礎(chǔ)之上，先對數(shù)據(jù)全集進行輸入剪枝，每一角色只保留n個候選元組；之后組合內(nèi)角色依次選定一個元組構(gòu)成候選組對象，查詢借助角色組合對候選組合進行評分，遍歷所有組合后返回評分最高的組合。組對象的評分等于組內(nèi)成員在對應(yīng)角色下評分之和。本發(fā)明廣泛適用于查詢最優(yōu)對象為包含多個個體的組對象的應(yīng)用場景，如任務(wù)分配、球隊創(chuàng)建等。

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

本發(fā)明公開了一種基于角色組合的最優(yōu)組查詢方法，具體涉及從數(shù)據(jù)庫中選擇n(n＞1)個元組組成最優(yōu)組合的查詢方法，屬于計算機數(shù)據(jù)庫管理系統(tǒng)中偏好查詢技術(shù)領(lǐng)域。

背景技術(shù)

隨著移動互聯(lián)網(wǎng)、物聯(lián)網(wǎng)等技術(shù)的發(fā)展，數(shù)據(jù)的產(chǎn)生來源更多，數(shù)據(jù)的產(chǎn)生速度更快，針對特定查詢，其候選對象的數(shù)據(jù)量更大。面向規(guī)模更大的數(shù)據(jù)，如何依據(jù)用戶查詢條件，從候選數(shù)據(jù)中更快更準(zhǔn)確的查詢到結(jié)果顯得愈加重要。更快更準(zhǔn)的獲取到用戶希望的數(shù)據(jù)，可以提升用戶對系統(tǒng)的體驗感，對系統(tǒng)提升用戶粘性至關(guān)重要，十分值得深入研究

偏好查詢^[1]是數(shù)據(jù)庫領(lǐng)域的研究熱點之一，組查詢是偏好查詢的新的分支之一。組查詢致力于協(xié)助用戶從數(shù)據(jù)集中選擇組合對象而非單個對象，現(xiàn)有專利發(fā)明中只存在基于Top-k 或Skyline的查詢處理方法，但這些方法只能返回單個對象，無法適用于組查詢。針對組查詢，近年來數(shù)據(jù)庫學(xué)術(shù)領(lǐng)域做出的一些突破，組合查詢算法最核心的任務(wù)是設(shè)定組合優(yōu)劣判定的標(biāo)準(zhǔn)。Zhang等^[2]提供了一種”logic+SQL”框架，本質(zhì)上是對結(jié)果設(shè)定閾值，所有未達(dá)到閾值條件的候選集合均被剔除出最終結(jié)果集；Li等^[3]將每個候選組合通過聚合函數(shù)聚合為一個向量，之后求出所有候選向量中的Skyline結(jié)果集，其中聚合函數(shù)給定了三類：求和(SUM)、最小值 (MIN)、最大值(MAX)。Im等^[4]組合是對文獻(xiàn)[3]的縱向擴展，其優(yōu)劣判定標(biāo)準(zhǔn)通文獻(xiàn)[5]的一樣，不過聚合函數(shù)只用了求和(SUM)一類，除此之外給出了一些優(yōu)化準(zhǔn)則，提升了算法求解結(jié)果集的效率；Liu等^[5]分析了[3-4]中存在用戶最滿意的候選組合可能不在最終的查詢結(jié)果集中，首次提出了組支配的概念G-Skyline，基于組支配進行組優(yōu)劣的判斷并返回最終的查詢結(jié)果集。

雖然現(xiàn)有[2-5]可用于解決組查詢問題，但這些處理算法均存在查詢結(jié)果集規(guī)模不可控的缺陷。文獻(xiàn)[2]基于SQL語句，只能設(shè)定一些簡單的比較固定的閾值條件，其查詢結(jié)果集規(guī)模不可控；已有學(xué)者的研究在數(shù)據(jù)維度高數(shù)據(jù)量大的情況下，結(jié)果集規(guī)模不可控^[6]，然而文獻(xiàn)[3-5] 均基于Skyline算子，則這些算法均存在結(jié)果集規(guī)模不可控的缺陷。

上文中提到的專利申請情況如下：

[1]一種面向任意段數(shù)據(jù)的Top-k查詢方法(申請日期：2012-07-24，授權(quán)號：CN102799681 B)

[2]基于雙閾值的分布式Top-|K|查詢方法(申請日期：2014-04-28，授權(quán)號：CN103984707 B)

[3]一種基于云計算環(huán)境的分布并行Skyline查詢方法(申請日期：2011-10-25，授權(quán)號：CN 102314521 B)

上文中提到的文獻(xiàn)來源于如下的期刊：

[1]Kieβling W.Foundations of Preferences in Database Systems.[C].VLDB2002，Proceedings of，International Conference on Very Large Data Bases，August20-23，2002，Hong Kong，China. 2002：311-322.