[發明專利]一種針對窗口函數range方式的窗口采樣算法

在審

• 申請號: 201810354967.8
• 申請日: 2018-04-19
• 公開（公告）號: CN108710641A
• 公開（公告）日: 2018-10-26
• 發明（設計）人: 王曉玲;屈穩穩;宋光旋
• 申請（專利權）人: 華東師范大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海藍迪專利商標事務所(普通合伙) 31215
• 代理人: 徐筱梅;張翔

本發明公開了一種針對窗口函數range方式的窗口采樣算法，該方法充分利用數據間的關聯，查詢時首先對數據庫中存在的大量數據進行隨機采樣，然后在采樣數據上計算每行數據的窗口函數值并連同置信區間一并返回用戶。本發明對窗口函數的計算流程做出優化，在保證結果精度的前提下降低查詢響應的時間開銷，大大提高了窗口函數的執行效率，在大數據應用上表現優異。

技術領域

本發明屬于數據庫中的數據分析領域，具體來說，是檢索數據庫中的數據，以結構化查詢語言(SQL)中的窗口函數的方式對這些數據進行數據查詢和統計分析。本發明利用統計采樣的方法對窗口函數的計算過程提出了一種新的優化策略。

背景技術

隨著社會對數據的越來越重視，政府和企業信息化程度的提高，各行各業積累了大量的數據。但是數據量的增長并不一定會為政府和企業帶來價值。如何利用數據，從數據中挖掘出有價值的信息是數據分析的重中之中。數據庫是政府和公司存儲公司的常用工具，其優秀和高效的性能為政府和公司的數據存儲和查詢提供了有力的支持。然后數據量的增大、數據復雜性的增長，給繼續保持數據庫的高可用性提出了巨大的挑戰。使用傳統的數據庫尤其是關系型數據庫分析大數據不僅僅效率低下，而且能夠提供的分析功能也有很多局限。

大數據時代的數據分析和傳統意義的分析有巨大的區別，不再是基于結構化、關系型的數據，而且往往僅取數據的某個子集來進行分析以及預測。為了支持這類的應用，數據庫在其本身的特性之上做出了很多擴展，使其不僅支持傳統的數據存儲，也添加了對數據分析的支持。而窗口函數就是這樣的一種新特性。窗口函數，也被稱為分析函數，最初是作為SQL-99的擴展被提出來，在之后的SQL-2003正式成為一種新的特性。

但是傳統的窗口函數執行效率底下，當窗口中的數據達到數以萬計的情況下數據庫往往難以給出有效的查詢結果。因此，亟待得到一種有效的解決方法。

發明內容

本發明的目的在于針對大數據環境下的數據分析，對窗口函數的計算提供一種針對窗口函數range方式的窗口采樣算法，從而保證數據庫在大數據分析應用中的可用性。由于采樣本身存在不確定性，和原始數據的統計分析結果可能存在一定誤差，本發明同時針對給定的采樣率給出了置信區間的計算方式。

為了實現對數據庫窗口函數功能特性的拓展，本發明提出了一種基于采樣的優化算法。算法的依據在于Range方式建立的窗口具有邏輯上的相關性，能夠保證采樣后的數據統計特征和原始數據的統計特征有關聯，并根據這種關聯給出了置信區間的計算方式。具體實施步驟如下：

S1：對表中的數據進行隨機采樣，保證表中的所有數據被等概率地取到；

S2：從采樣后的表中獲取到分區P′，原始的分區使用P進行表示；分區的劃分以SQL語句中的partition key為依據；分區P和P′的大小相同，區別在于P′分區內的數據為采樣后的數據，小于原始的數據量，從而降低了窗口函數的計算量；

S3：對P′中的數據進行排序，排序按照SQL語句中sort key為依據；由于數據量的減少，在此步驟中花費的時間也相應減少。

S4：在分區P′上建立采樣窗口；針對的range方式確立的窗口；對于采樣后的數據，直接建立窗口；而對于缺失的數據r，使用查找算法找到離其最近的采樣數據sr；將sr所在的窗口作為當前的計算窗口；

S5：對于每一個采樣窗口，初始化窗口的上下界和窗口的轉移值；

S6：對每條數據應用adjust_transfunc函數來更新結果得到最終的轉移值；然后將每個窗口的轉移值添加到結果之中；adjust_transfunc是對原本的窗口函數的調整；

S7：回到S4，迭代進行計算，直到所有數據計算結束；

S8：利用公式(1)，計算在當前采樣率下的置信區間；