[發明專利]一種層次關系數據上關鍵字檢索結果的聚合摘要方法有效

申請號：	201110150869.0	申請日：	2011-06-07
公開（公告）號：	CN102214216A	公開（公告）日：	2011-10-12
發明（設計）人：	何震瀛;胡昊;汪衛	申請（專利權）人：	復旦大學
主分類號：	G06F17/30	分類號：	G06F17/30
代理公司：	上海正旦專利代理有限公司 31200	代理人：	陸飛;盛志范
地址：	200433 ***	國省代碼：	上海;31
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	一種層次關系數據關鍵字檢索結果聚合摘要方法
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【說明書】：

技術領域

本發明屬于關系數據庫技術領域，具體涉及一種層次關系數據上關鍵字檢索結果的聚合摘要方法。

背景技術

近年來，關鍵字檢索作為從結構化或半結構化數據中提取所需信息的方法已被廣為接受。目前已有許多針對關鍵字檢索問題提出的檢索系統。但基于關系數據庫上的檢索系統更多致力于獲得包含所有關鍵字的元組或元組連接樹。簡單的將這些結果返回會造成信息冗余并且有時還會生成無意義的結果。此外，在許多數據庫中，具有層次關系的數據普遍存在，這對檢索結果信息整合具有指導作用。

對于檢索結果的進一步處理等工作包括打分方法和結果聚合已經有許多人在研究了。關系數據庫檢索結果的聚合問題現有的方法僅關注于一張表上的聚合操作。然而，實際應用中，信息會依據范式被分解成不同的部分存儲于多張表中。若簡單的將該方法應用于多張表的問題中會根據連接關系生成一張非常大的表，這是耗時且不實際的。另外，該方法中的屬性上并無層次關系。需要注意的是，也有另外的工作對聚合操作予以支持，但是，它需要由用戶指定在哪些屬性上進行聚合操作，這對于不熟悉數據庫模式的大多數用戶來講是十分困難的。而且，該工作中的聚合操作是對結果集進行聚合選擇（即計算元組數目或求最大最小值等），并非在此基礎上做信息整合。摘要問題現有的方法有基于貪心和隨機算法的兩種解決方案。

發明內容

本發明的目的是針對層次關系數據庫關鍵字檢索結果的聚合摘要問題，提出一種基于排序和剪枝的聚合摘要方法，以減少查詢代價，提升用戶體驗。

本發明提出的聚合摘要方法，利用層次關系的性質，結合最低上層最小覆蓋聚集的原則以及最大覆蓋原理的特征，對帶連接元組集進行按序連接，減少連接開銷，最后在摘要階段給出3個剪枝條件，既保證找出的結果是滿足貪心法的結果，又大大減小搜索空間，提高摘要效率。

首先對一些基本概念進行定義：

定義1.?劃分：設S是一個集合，????????????????????????????????????????????????。如果下列條件成立則稱為S的一個劃分：?①?,?②?對于任意Pi,，若，則PiPj為空集。

定義2.?聚集關系：設a={S₁,?S₂,…?,?S_n}是一個有限元組集族，元組是某關系數據庫中的每一條記錄，S_i(1≤?i?≤?n)是任意元組集合,≦是如下定義的二元關系：對于a中任意集合S_i和S_j，如果存在一個函數F：→S_j(是S_i的劃分)，則稱S_i和S_j滿足≦，記作S_i≦S_j，F稱為聚集函數。如果滿足下列條件則稱為a上的聚集關系：對于a中任意集合S_i和S_j，如果S_i≦S_j，?S_j≦S_i，則S_i=S_j。