[發明專利]近似查詢處理

有效

• 申請號: 201380075332.X
• 申請日: 2013-01-31
• 公開（公告）號: CN105103152A
• 公開（公告）日: 2015-11-25
• 發明（設計）人: Z.曹;L.焦;S.陳;M.王;M.郭
• 申請（專利權）人: 惠普發展公司;有限責任合伙企業
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 張凌苗;陳嵐

1.一種用于獲得針對在數據庫上的查詢的近似回答的方法，包括：

利用范式將所述查詢轉換成子查詢的集合；

生成針對所述子查詢中的每個的近似回答；以及

組合針對所述子查詢的近似回答以獲得針對所述查詢的近似回答。

2.如在權利要求1中所述的方法，其中所述范式是析取范式（DNF）。

3.如在權利要求1中所述的方法，其中生成針對所述子查詢中的每個的近似回答包括利用在所述數據庫中的采樣或者與所述數據庫相關聯的前k直方圖來生成針對所述子查詢中的每個的近似回答。

4.如在權利要求2中所述的方法，其中所述子查詢由運算符OR連接，并且所述組合基于加法定律。

5.如在權利要求3中所述的方法，其中利用在所述數據庫中的采樣或者與所述數據庫相關聯的前k直方圖來生成針對所述子查詢中的每個的近似回答進一步包括：

如果可以根據前k直方圖直接獲得針對子查詢的近似回答，那么使用前k直方圖來得到針對所述子查詢的初步近似回答，并且使用采樣來修改所述初步近似回答以便獲得針對所述子查詢的修改的近似回答；以及

如果不可以根據前k直方圖直接獲得針對子查詢的近似回答，那么使用采樣來獲得針對所述子查詢的初步近似回答，并且使用前k直方圖來修改所述初步近似回答以便獲得針對所述子查詢的修改的近似回答。

6.如在權利要求5中所述的方法，其中所述組合包括組合針對每個子查詢的所述修改的近似回答以獲得針對所述查詢的近似回答。

7.如在權利要求3中所述的方法，其中所述前k直方圖包括關于除了前k項的其余的值的統計信息。

8.一種用于獲得針對在數據庫上的查詢的近似回答的系統，所述系統包括：

處理器，其可適于執行存儲的指令；以及

存儲指令的存儲器設備，存儲器設備包括處理器可執行代碼，所述代碼當由處理器執行時可適于：

利用范式將所述查詢轉換成子查詢的集合；

生成針對所述子查詢中的每個的近似回答；并且

組合針對所述子查詢的近似回答以獲得針對所述查詢的近似回答。

9.如在權利要求8中所述的系統，其中所述范式是析取范式（DNF）。

10.如在權利要求8中所述的系統，其中所述存儲器設備存儲處理器可執行代碼，并且所述處理器可執行代碼可適于通過以下內容生成針對所述子查詢的近似回答：

利用在所述數據庫中的采樣或者與所述數據庫相關聯的前k直方圖來生成針對所述子查詢中的每個的近似回答。

11.如在權利要求9中所述的系統，其中所述子查詢由運算符OR連接并且所述組合基于加法定律。

12.如在權利要求10中所述的系統，其中所述處理器設備存儲處理器可執行代碼，并且所述處理器可執行代碼可適于利用在所述數據庫中的采樣或者與所述數據庫相關聯的前k直方圖以通過以下內容生成針對所述子查詢中的每個的近似回答：

如果可以根據前k直方圖直接獲得針對子查詢的近似回答，那么使用前k直方圖來得到針對所述子查詢的初步近似回答；并且使用采樣來修改所述初步近似回答以便獲得針對所述子查詢的修改的近似回答；以及

如果不可以根據前k直方圖直接獲得針對子查詢的近似回答，那么使用采樣來獲得針對所述子查詢的初步近似回答，并且使用前k直方圖來修改所述初步近似回答以便獲得針對所述子查詢的修改的近似回答。

13.一種包括代碼的非瞬時計算機可讀介質，所述代碼被配置成引導處理器：

利用范式將所述查詢轉換成子查詢的集合；

生成針對所述子查詢中的每個的近似回答；并且

組合針對所述子查詢的近似回答以獲得針對所述查詢的近似回答。

14.如在權利要求13中所述的非瞬時計算機可讀介質，其中所述范式是析取范式（DNF）。

15.如在權利要求13中所述的非瞬時計算機可讀介質，其中所述非瞬時計算機可讀介質包括被配置成引導處理器通過以下內容生成針對所述子查詢的近似回答的代碼：

利用在所述數據庫中的采樣或者與所述數據庫相關聯的前k直方圖來生成針對所述子查詢中的每個的近似回答。