關系數據庫不可用空值的查詢與處理

郭詠科　毛宇光　向日鋒

摘要：在流式大數據系統測試過程中，測試數據集越真實，得到的測試報告越可信。然而真實大量的流式數據并不容易獲取，因此需要一種方法能夠產生大量符合真實場景特征的數據。這些特征包括數據屬性相關性、數據時序相關性、數據流的流速變化等等。在流式大數據環境下，數據的時序相關性與流速變化尤為重要。本文提出了一種適用于流式大數據系統測試的數據生成方法，以真實場景的數據集作為種子數據，對種子數據采用最大互信息系數描述數據屬性間的相關性，改進了Prim算法對屬性列集合進行分組，在盡量保證屬性列強相關的前提下提高生成效率，接著提出了一種時序模型選擇策略，保證生成的數據在時序上的相關性，提出了雙層滑動窗口的方法控制流數據輸出速度。最后，本文比較了提出的方法與其他流數據生成方法的生成效率。

關鍵詞：流式大數據生成；非線性相關性；時序相關性；流速控制

中圖分類號：TP311文獻標識碼：A

Abstract：In the process of streaming big data system testing，the more real test data sets，the more reliable the test report can be obtained.However，real data is not easy to obtain，so a method is needed to generate a large number of data with real scenario features.Thesefeatures include data attribute correlation，data temporal sequence correlation and the rates of streaming data.In the streaming big data environment，the data temporal sequence correlation and the rates of streaming dataare especially important.In this paper，we present amethod forstreaming big data generation，using real scenario streaming data as the seed data，using the maximum mutual information coefficient to describe the correlation between the data attributes，putting forward acprim algorithm to partition the attribute group，improve efficiency in the premise of ensuring that the attributes arestrong related.according to the different characteristics of each attribute group，using different temporal sequence model to ensure that the data generated hold temporal sequence correlation，a double sliding window method is proposed to control thedegree of parallelism and the output speed of the streaming data.Finally，this paper compares the proposed method with other streaming data generation methods for generating efficiency.

Key words：streaming data generation；nonlinear correlation；temporal sequence correlation；velocity control

1簡介

流式大數據廣泛存在于社交網絡、金融服務等領域，越來越多的流式大數據處理系統應運而生，為了保證此類系統的性能滿足設計需求，需要對其進行相應的性能測試。Yahoo開發了云服務測試套件YCSB，用來對云服務進行基礎測試，目標是進行云數據服務系統的性能比較[1]；Ruirui Lu等人提出了測試套件StreamBench，描繪了流式系統的性能測試框架，比較全面地對流式大數據系統進行了測評[2]；詹劍鋒等人提出了大數據測試基準BigDataBench，其基準測試程序覆蓋了多個大數據應用領域[3]。然而諸如此類的測試套件，重點關注的是負載的全面性，在輸入數據集的選擇問題上考慮得不夠全面。進行流式大數據系統的測試，輸入到系統的數據與真實場景下的數據特征越吻合，得到的測試結果越準確，因此需要一種能夠保持數據真實特征的大數據仿真生成方法。

在流數據和流數據庫仿真生成方面近年來有很多豐碩成果，Eric等人提出了DBMS測試套件MyBenchmark以及數據生成工具[4]，把一組查詢操作作為輸入，能夠生成數據庫實例，同時用戶還能控制生成負載的特征。由于保持了大量數據依賴、數據分布等內層特征，數據生成的速度不是很高。Joseph等人提出了一種合成數據形式化的描述語言SDDL[5]，能夠并行生成具有某些約束和簡單用戶定義函數的數據，但是沒有考慮到數據的分布特征，不能生成滿足例如高斯分布等復雜概率分布的數據。Kenneth等人將數據表的生成轉換成圖的遍歷過程[6]，能夠保證比較好的屬性依賴和概率分布，由于重點保持屬性依賴，使得數據的并行化程度不高，在生成數據表規模比較龐大或者依賴關系比較復雜的時候生成速度比較慢。華東師范大學的顧伶等人提出了通用數據生成框架PSUG，使用標準均方關聯度量計算屬性間相關性，使用隱式狄利克雷模型模擬數據流前后的主題相關性，開發了數據生成工具Chronos，能夠生成滿足流數據庫測試套件的數據[7][8]，但是Chronos使用的標準關聯度是一個線性的相關性度量指標，對于具有非線性關系的屬性關聯不能準確地描述，同時對于不存在主題的純數字型數據，該生成方法無法滿足生成的數據在時序上的相關性。流式大數據的屬性依賴關系以及其固有流式特征都與傳統的數據庫和流數據庫有所不同。錢宇華等人研究了大數據環境下的數據相關性度量指標的優缺點[9][10]，同時指出在大數據環境下，數據之間的相關性一般都是非線性的。Reshef等人提出了最大互信息系數，證明了該度量指標對非線性相關性能進行比較準確的刻畫[11]。endprint

本文在此基礎上提出一種適用于流式大數據系統測試的數據生成方法，在盡可能保證數據屬性相關性的同時，加入流式數據的時序性特征，同時還能控制流數據的流速。本文最后也進行了效率方面的檢測，證明了該數據生成方法的有效性。

本文的結構如下：第2節介紹數據生成方法的整體框架，第3節介紹參數設置方法，第4節介紹相關性控制方法，第5節介紹流速控制方法，第6節介紹實驗。

2框架結構概述

本節對數據生成方法的框架進行簡要的描述，如圖1所示，整個框架分為3個部分：參數設置模塊、相關性控制模塊、流速控制模塊。

參數設置模塊以種子數據作為輸入，提取屬性列的信息，生成數據描述文件，定義參數對后續生成的數據的特征進行校正，不同的參數組合可以代表不同的應用場景下數據的不同特點。相關性控制模塊任務是計算數據屬性間的相關性系數，對屬性集合進行劃分，劃分后得到的屬性組擁有類似高內聚低耦合的特征。提出時序模型選擇策略對于每個屬性組進行時序相關性的分析，得出回歸方程用作數據生成。流速控制模塊定義內層滑動窗口保證并行生成的數據在整個時間序上的相關性，定義外層滑動窗口控制數據流輸出速率。

3參數設置

本節介紹數據生成方法的參數設置。本文方法定義了四個參數：最大相關性忽略系數c；時序相關回歸階數r；時間分段T；數據流速S。

最大相關性忽略系數c是在數據屬性組劃分階段，終止搜索下一個屬性所參考的變量。取值范圍在0.2～0.4，屬性相關性在0.2以下說明屬性之間相關性極低，在0.2～0.4之間相關性較低。該參數越小，允許忽略的相關性越少，因此分解出的屬性組越少，并行化程度越低；相反，分解出的屬性組越多，并行化程度越高。對于僅僅需要進行壓力或者負載測試的系統來說，該參數設置大一些，忽略數據屬性之間一些不必要的相關性；對于某些具備數據挖掘功能的系統來說，該參數應設置小一些，盡量保存數據屬性之間的相關性，使得數據挖掘性能能夠得到展現。

時序相關回歸階數r是在進行數據時序相關性分析階段，向前參考數據的個數，取值范圍在2～4。該參數越小，時序相關性越弱，但回歸公式越簡單，數據生成效率越高；相反，考慮的數據時序相關性越強，回歸公式越復雜，數據生成效率越低。對于類似股票流數據的場景，該參數應設置高一些，使得生成的數據與之前數據的關系盡可能精準一些；而對于類似車載物聯網系統來說，其前后的流數據相關性不是特別重要，該參數可以設置低一點。

時間分段T描述的就是某一個周期下不同數據流速的段數以及時長，是一個自然數的集合，即T={t1，t2，t3……}。該參數元素個數越小，流速越平穩，數據流越穩定；相反，流速變化越頻繁，數據流波動越大。例如銀行系統，每天早7點之前和晚7點之后，系統負載較小，早7點到11點和下午2點到7點為高峰，負載較大，則可以將整個數據流分為4段，即t1=12（晚7點到第二天早7點）；t2=4（早7點到早11點）；t2=3（早11點到下午2點）；t4=5（下午2點到下午7點）。

數據流速S描述的是時間分段T上的數據流速，S同樣是一個自然數的集合，元素個數與T一致。2012年的新年新浪微博的單秒最大數據條數達到了4萬條， 2016年11月11日，天貓購物節支付寶的交易峰值也只有16萬條數據/秒，根據互聯網用戶每年25%的增長趨勢，本文將其取值范圍設置在0～200000條數據/秒。S中元素的值越大，數據輸出得越快。假設s1代表晚上5點之前的流速，s2代表晚上7點之后的流速，則對于上述銀行系統，朝九晚五的特點使得系統的數據流速在晚上7點之后明顯小于5點之前（s1s2）；相反對于微博系統，上班族下班，數據流速在晚上7點之后可能又遠遠大于晚上5點之前（s1s2）。

4相關性控制

本節介紹數據相關性控制方法，對于保證生成的數據符合真實數據特征具有重要作用。首先分析其兩兩之間的最大互信息相關系數（MIC），得到相關系數圖，接著改進了Prim算法進行屬性列集合的劃分，使得保持數據屬性列強相關的同時增加并行化來增加數據生成效率，最后給出一種時序模型選擇策略，對不同特征的屬性列集合采取不同的時序模型進行擬合，得到回歸方程或方程組用作后續數據生成。

41屬性相關性

屬性相關性是指擁有多個屬性的一批數據，其屬性之間的關聯程度。在大數據相關分析中，MIC可以度量任何函數形式的相關性，具有通用性。同時，如果兩組不同形式、擁有相同MIC取值的數據，當給它們同等程度的噪音，MIC的取值仍然保持相等。流式大數據環境下，對數據的生成速度有要求，生成算法計算的復雜度越低越好，同時大數據復雜多樣、噪聲數據很多，算法的魯棒性同樣重要。表1是MIC與其他相關性度量指標的對比，可以看出MIC更加適合流式大數據的環境。

由于MIC具有對稱性，即MIC（A，B） = MIC（B，A），因此對于具有N個屬性的數據集，計算后能夠得到一個N個節點的帶權無向完全圖，圖中的邊的權值代表兩個屬性列之間的相關系數。當兩個屬性列之間的相關性比較小時，應該將它們單獨生成，而相關性比較大的幾個屬性列必須作為整體一起生成，所以可以對屬性列相關系數圖進行劃分，把相關性大的屬性列劃到同一組，以提高并行度，進而提高數據生成的整體效率。

圖的最小生成樹算法以圖中連線權值為參考，生成一條包含所有節點的序列，由于本文進行屬性列分組時也需要參考連線權值，所以可以通過加入終止條件的辦法，讓算法提前結束，獲得序列的一條子序列，子序列中包含的節點就被分為同組。普利姆算法（Prim算法）和克魯斯卡爾算法（Kruskal算法），是最基本的兩種圖最小生成樹算法，分別適用于稠密圖和稀疏圖。帶權無向完全圖屬于稠密圖，因此本文對Prim算法進行改進，提出一種附加終止條件的Prim算法——cPrim算法劃分屬性列集合。endprint

cPrim算法思想：從任意一個頂點出發，尋找與其相連的邊集合中權值最大的邊，如果該邊的權值仍然小于等于最大相關性忽略系數c，則直接將該節點單獨分為一組；如果不小于c，找出最大權值邊對應的節點，將該節點納入出發節點集合，再從出發節點集合出發尋找最大權值的邊，不斷循環，直到所有節點被分成了若干組。假定最大相關性忽略系數c為0.2，下面以圖2為例，簡單介紹算法步驟。

圖2（a）為劃分之前的關聯關系圖。隨機從一個節點出發（例如1號節點），與其相連的邊上的權值為0.1、0.1、0.2，均小于等于c，故直接將1號節點單獨分為一組，如圖2（b）所示。

再從剩下的2，3，4號節點中隨機選取一個（例如3號節點），與其相連邊最大權值為0.5，大于c，那么將4號節點納入{3}，如圖2（c）所示。

繼續尋找從3，4號節點出發的最大權值的邊，是2號與4號節點的連接邊，權值為0.3，大于0.2，將2號節點納入{3，4}。整個屬性集合被分成了2組：{1}，{2，3，4}，如圖2（d）所示。

假定的最大相關性忽略系數c為0.4，根據算法可以將屬性集合分為3組：{1}，{2}，{3，4}。

算法偽代碼：

42時序相關性

數據的時序相關性是指帶有時間戳的一組數據，其前后數據屬性值的關聯關系。在流式大數據環境下，數據的時序性非常關鍵，缺少了時序的流式數據就喪失了數據挖掘特別是趨勢預測的意義。本小節提出一種時序模型選擇策略，針對不同特點的屬性組采用不同的時序模型進行回歸方程的擬合。

屬性分組劃分完之后，首先將屬性組分為2類：單屬性組和多屬性組。

對于單屬性組，首先判斷其是否平穩，即序列是否圍繞某個固定值上下波動或者序列的標準差是否保持不變。若平穩，則采用經典的自回歸移動平均（ARMA）模型進行擬合，形式為：

Xt=Φ1Xt-1+…+ΦpXt-p+εt-…-θqεq（5）

其中Xt是需要估計的下一個值，Xt-1～Xt-p是回歸參考的屬性數據，εt是當前噪聲，εt-1～εt-p是回歸參考的噪聲數據，Φ1～Φp以及θ1～θq為回歸參考數據的參數。

若非平穩，則采用自回歸滑動平均（ARIMA）模型進行擬合。ARIMA模型是針對非平穩的單變量時間序列的，其基本思想是將一個非平穩的時間序列通過一次或者多次差分轉換成平穩序列再進行擬合。一般來說，一階差分可以使有線性趨勢的序列變得平穩；二階差分可以使有曲線趨勢的序列變得平穩。ARIMA模型形式為：

其中Δd是指經過了d階差分，其他參數同ARMA模型的參數。

對于多屬性組，采用自向量回歸（VAR）模型進行擬合。VAR模型針對的是多變量的時間序列，擬合之前需要觀察數據VAR模型根模散點是否均落在單位圓內來的判斷序列是否平穩，若不平穩，首先差分成平穩序列再進行擬合，模型形式為：

Xt=Φ1Xt-1+…+ΦpXt-p+βYt+εt（7）

其中Xt～Xt-p為內生變量向量，Yt是外生變量向量，改變量是指除了參與，εt是當前噪聲向量，Φ1～Φp以及β為回歸參考數據的參數。對所有屬性組進行擬合得到回歸方程，用作數據生成。

5流速控制

本節描述一種雙層滑動窗口的方法，控制流數據流速。滑動窗口的概念最先出現在計算機網絡中，通訊雙方約定一個能夠接受的窗口大小，每次只發送和接收指定窗口大小的內容，防止數據溢出。

為了保證流數據整體的時序性，必須在增加并行度時進行控制，定義內層滑動窗口，窗口大小為時序相關回歸階數r，維護著最新的r個數據，如圖3所示，有2個線程分別生成屬性a和屬性b，c。

當屬性組需要增加并行化時，不直接通過隨機數生成器生成種子，而是將窗口內的r個數據當作新線程的種子數據，如圖4所示。因為回歸方程帶有一定的噪聲，因此在當前窗口基礎上生成的后續數據和以這批數據作為新種子生成的數據不會完全一樣，同時保證了一個屬性組在整個時間序列上的相關性。

為了控制數據流流速，定義外層滑動窗口，外層窗口大小為當前時間段T上的流速S，輸出數據時，以恒定的速率輸出窗口內數據，需要流速加大時，就增大窗口大小；需要流速減小時，就減小窗口大小。如圖5所示，T1階段流速為500條/秒，T2階段流速為5000條/秒。

6實驗

本節介紹實驗，驗證提出的方法生成的數據滿足預設的速率要求；數據屬性之間的相關性仍然保持；最終生成的數據與種子數據的分布基本一致。此外，實驗還比較了本文方法與PSUG[7]和文獻[13]提出方法的數據生成效率。

61實驗設置

實驗配置為：4核酷睿i7處理器，主頻3.4 GHz，內存16 GB，硬盤存儲1 TB。

初始參數設置：最大相關性忽略系數c為0.2，時序相關回歸階數r為2，運行總時間30分鐘，分為3段，即t1=10、t2=10、tz=10，流速分別為500條/秒，10000條/秒，50000條/秒，即s1=500、s2=10000、sz=50000，3個時間段總計分別生成30W，600W，3000W條數據。實驗的種子數據為10000條帶有時間戳的新浪微博數據，經過清洗之后每條數據包含“微博文本長度”，“轉發數”，“評論數”，“點贊數”4個屬性。

62實驗結果

圖7為生成的數據分布與種子數據分布的對比，其中生成數據的分布圖是由生成的數據隨機開始位置10000條連續的記錄產生的，由于無法確定提取的數據流處在整個數據流的位置，考察每個值出現的位置沒有意義，比較每個數據段上的數據量分布即可，可以看到生成的數據比較符合種子數據的數據分布，圖7只列出了“文本長度”和“轉發數”的數據分布對比，“評論數”和“點贊數”與“轉發數”類似。endprint

圖8為本文方法與其他方法的效率對比，與PSUG相比，兩種方法在屬性相關性分析方法策略上有所不同，但數據生成的速率本文方法大約為PSUG的2倍；與不保證時序相關的流數據表生成方法相比，本文提出的方法加入了數據時序性的特征，生成速度大約下降了20%，速度損失可以接受。

7總結和展望

本文提出了一種適用于流式大數據系統測試的數據生成方法，采用了更加適用于流式大數據系統的非線性相關系數MIC來描述數據屬性之間的相關關系，改進了Prim算法合理地劃分屬性集合；加入流式數據重要的時序性特征，盡可能保留了前后數據之間的相關性；提出了雙層滑動窗口的概念，能更好地控制數據輸出的速率。

本文的不足之處在于：自動化程度不高，不能運行時動態添加屬性；需要手動定義變量；數據時序相關性分析的參數需要手動賦值；整個數據流的流速變化比較突然，實際的應用系統中的數據流速變化應該比較平滑；不能支持非結構化類型的數據生成。

在未來的工作中，我們希望能夠將數據生成的預處理過程進一步自動化，挖掘數據流的流速變化規律，支持生成更多數據類型的數據。

參考文獻

[1]COOPER B F，SILBERSTEIN A.Benchmarking Cloud Serving Systems with YCSB[C].international IEEE SOCC，2010.

[2]LU Ruirui，WU Gang，XIE Bin.StreamBench：Towards Benchmarking Modern Distributed Stream Computing Frameworks[C].IEEE/ACM 7th International Conference on Utility and Cloud Computing.2014.

[3]ZHAN Jianfeng，GAO Wanling，WANG Lei.Big Data Bench：An Opensource Big Data Benchmark Suite[J].Chinese Journal Of Computers，2016，39（1）：196-211.

[4]LO Eric，CHENG Nick.Generating Databases for Query Workloads[J].VLDB.2010，3（1），848-855.

[5]HOAG J E，THOMPSON C W.A parallel generalpurpose synthetic data generator[C].SIGMOD.2007，36（1），19-24.

[6]HOUKJAR K，TORP K，WID R.Simple and realistic data generation[C].VLDB.2006，1243-1246.

[7]GU Ling，ZHOU Minqi.A Scalable Framework for Universal Data Generation in Parallel[C].6th TPCTC.2014.

[8]GU Ling，ZHOU Minqi.Chronos：An Elastic Parallel Framework for Stream Benchmark Generation and Simulation[C]，IEEE 31st International Conference on Data Engineering.2015.

[9]LIANG Jiye，FENG Chenjiao，SONG Peng.A Survey on Correlation Analysis of Big Data[J].ChineseJournal Of Computers，2016，39（1），1-18.

[10]QIAN Yuhua，CHENG Honghong，LIANG Xinyan.Review for Association Measures in Big Data[J].Journal of Data Acquisition and Processing，2015，30（6），1147-1159.

[11]RESHEF D N，RESHEF Y A，FINUCANE H K，et al.Grossman.Detecting Novel Associations in Large Data Sets[C].Science，2011，334（10），1518-1524.

[12]HU Bo，GUO Li.Practical statistical analysis method and technology[M].Beijing：Chemical Industry Press，2013.

[13]ARASU A，KAUSHIK R，LI Jian.Data Generation using Declarative Constraints[J].Acm Sigmod International Conference on Management of Data，2011，685-696.endprint