[發明專利]一種海量不完整數據存儲及操作方法

在審

• 申請號: 201611081152.4
• 申請日: 2016-11-30
• 公開（公告）號: CN106599112A
• 公開（公告）日: 2017-04-26
• 發明（設計）人: 王妍;楊鈞;李俊;吳陽;宋寶燕
• 申請（專利權）人: 遼寧大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 沈陽杰克知識產權代理有限公司21207
• 代理人: 羅瑩

1.一種海量不完整數據存儲及操作方法，其特征在于，包括如下步驟：

(1)在海量不完整數據存儲時，對完整數據和不完整數據分別進行壓縮存儲，其實現步驟如下：

(1.1)對于一個海量數據庫系統，經過統計后獲得頻繁使用的數據操作語句，即查詢語句中WHERE后出現的謂詞，將這些謂詞分為確定性謂詞Def_Val和不確定謂詞Undef_val；

(1.2)獲得所有確定性謂詞和不確定謂詞后，在壓縮存儲時將每一條元組所滿足的不確定謂詞的屬性值和確定性謂詞作為索引存儲于數據中，同時將元組存放到相應的待壓縮緩存塊中；當某一緩存塊裝滿后，將其按順序進行壓縮存儲，并在數據庫中存儲元組所在壓縮文件地址；

索引表包括如下字段屬性：Id、Tp_Id、Undef_val_I……Undef_val_i、Def_Val、Block_Id、Delet_Flag、Com_Flag；

其中Id為索引序號；Tp_Id為元組序號；字段Undef_Val_i為當前元組第i個不確定謂詞的屬性值；字段Def_Val以位編碼形式存儲當前元組所滿足的確定性謂詞；

Block_Id為當前元組所在緩存塊的序號；

Delet_Flag為刪除標志位,數據需要刪除則置為1,否則為0；

Com_Flag為數據元組完整性標志位,元組時完整的則置為1,否則為0；

壓縮文件地址表包括如下字段屬性：Block_Id、Address；其中，Block_Id為當前元組所在緩存塊的序號，字段Address為緩存塊壓縮后對應的壓縮文件；

對于n個確定性謂詞Q₁,Q₂,。。。,Q_n，設當前元組的字段Def_Val的位編碼為B₁B₂……B_n，若當前元組滿足條件Q_i，則Bi＝1，否則Bi＝0；若數據需要刪除，則令Delet_Flag＝1，否則置為0；對m個謂詞Q₁,Q₂,……,Q_m,若Q_i的值都存在，則Com_Flag＝1；否則Com_Flag＝0；

(1.3)通過將索引表和壓縮文件地址表在屬性Block_Id上的連接能夠得到完整的索引文件；不同Def_Val值對應不同的緩存塊，也就對應不同的壓縮文件地址；當某一緩存塊壓縮存儲后，將為Block_Id賦一個新的值，相同的Def_Val值可以對應不同的緩存塊和壓縮文件地址；

(1.4)海量不完整數據D*，假設D*包含m條元組，n個屬性；進行壓縮處理后，得到索引文件和壓縮數據；假設索引文件包含i條元組j個屬性，則i≥m且j≤n；對于D*的每一條元組t，首先計算t所滿足的確定性謂詞的Def_Val值和Com_Flag的值，將t寫入為該Def_Val分配的待壓縮緩存塊BlockDef_Val，com_Flag中，將t的不確定查詢條件的屬性值Undef_vals,Def_Val,Block_IdDef_Val,Com_Flag,，Delet_Flag＝0,Com_Flag插入索引表；如果Blockdef_Query,Com_Flag滿足指定元組數，采取一種壓縮算法將Blockdef_Query,Com_Flag進行壓縮；將Block_IdDef_Query,Com_Flag和AddressDef_Query,Com_Flag寫入地址表；對索引文件采用K-OF-N進行編碼，最后可以得到壓縮數據K，壓縮索引文件T和編碼字典M；采用K-OF-N編碼對索引文件進行壓縮；

(2)基于海量不完整數據的壓縮存儲，完成海量不完整數據的查詢操作，其實現步驟如下：

(2.1)首先需通過查詢條件來生成查詢索引：查詢索引的生成規則是：將查詢語句用Undef_Query和Def_Query來表示；

(2.2)①若查詢索引中只存在Def_Query,則直接在壓縮索引文件中根據Def_Query進行選擇操作；

②若查詢索引中存在Undef_Query，則需要根據Undef_Query在編碼字典中找到對應的編碼；

(2.3)在壓縮索引文件中進行選擇和投影操作；

(2.4)解壓查詢結果；

(3)基于海量不完整數據的壓縮存儲，完成海量不完整數據的刪除操作，其實現步驟如下：

(3.1)將刪除解析成刪除索引；

(3.2)①如果不確定謂詞存在，則在編碼字典中找其對應編碼，接著對壓縮索引文件T刪除標志位等于0，完整性標志位等于1的元組進行選擇操作，然后把刪除標志位置為1，對選擇結果在Address進行投影，解壓縮對應的Address壓縮包，按刪除語句進行元組刪除，將未刪除的元組導入壓縮緩存，完成后進行壓縮；

②如果確定性謂詞存在和不確定謂詞不存在，按Def_Val值對T中完整性標志位等于1的元組進行選擇操作，然后刪除標志位置為1，對選擇結果在Address上進行投影，對Address所對應的壓縮包直接刪除；當刪除標志位等于1的元組超過一個界限，整體刪除，接著刪除對應的編碼字典,得到結果；

(4)基于海量不完整數據的壓縮存儲，完成海量不完整數據的修改操作，其實現步驟如下：

(4.1)首先利用查詢算法查詢到需要修改的Address_Set；

(4.2)將相對應的壓縮包解壓后導入數據庫，進行修改操作，獲得操作元組Tp_ID_SET集合；

(4.3)將沒有操作的元組導回之前的壓縮包；將操作的元組導入其Update_Buffer_{Def_Query,Com_Flag},到達一定數量后壓縮，通常為150個；(4.4)索引文件T中Tp_ID屬于Tp_ID_SET的元組進行修改，包括Def_Query,Com_Flag,Undef_Query,Block_ID；

(4.5)修改編碼字典；

(5)基于海量不完整數據的壓縮存儲，完成海量不完整數據的插入操作，其實現步驟如下：

(5.1)對于每一個需要插入的元組，首先計算其Def_Query，Com_Flag；

(5.2)①如果是完整的，將t寫入待壓縮緩存塊Block_{Def_Query,Com_Flag}；

②如果是不完整的，則將將t寫入多個待壓縮緩Block_{Def_Query,Com_Flag}；

(5.3)緩存塊滿后整體進行壓縮，得到Block_Id_{Def_Query,Com_Flag}和Address_{Def_Query,Com_Flag}；

(5.4)在原來的編碼字典中插入該元組的信息；

(5.5)根據編碼字典在壓縮索引文件中插入新的元組。