基于壓縮的海量不完整數(shù)據(jù)近似查詢方法

王　妍　劉賡浩　王俊陸　宋寶燕

1(遼寧大學信息學院　沈陽　110036)

2　　　(東北大學信息與工程學院　沈陽　110819)

(wang_yan@lnu.edu.cn)

?

基于壓縮的海量不完整數(shù)據(jù)近似查詢方法

王妍1,2劉賡浩1王俊陸1宋寶燕1

1(遼寧大學信息學院沈陽110036)

2(東北大學信息與工程學院沈陽110819)

(wang_yan@lnu.edu.cn)

A Compression-Based Approximate Query Method for Massive Incomplete Data

Wang Yan1,2, Liu Genghao1, Wang Junlu1, and Song Baoyan1

1(SchoolofInformation,LiaoningUniversity,Shenyang110036)

2(SchoolofInformationScienceandEngineering,NortheasternUniversity,Shenyang110819)

AbstractWith the explosive increase of data, incomplete data are widespread. Traditional methods of data repair will cause high processing cost for mass data, and cannot be fully restored. Thus the approximate querying on these huge amounts of incomplete data for meeting the given requirements attracted greater attention from academics. Therefore, this paper proposes an approximate query method for massive incomplete data based on compression. Tagging the missing attribute value field and finding out the frequent query conditions, this method compresses these data based on the statistical frequent query conditions, and establishes the corresponding indexes. According to the attribute partition rules, index files are compressed again in order to further save storage space. In the stage of query, this method uses encoding dictionary to make selection and projection operations on the index compression files for getting approximate query results of incomplete data in the end. Experimental results show that this method can quickly locate the position of incomplete data compression, improve the query efficiency, save the storage space, and ensure the integrity of the query results.

Key wordsincomplete data; approximate query; data compression; index; encoding dictionary

摘要隨著數(shù)據(jù)的爆炸式增加，不完整數(shù)據(jù)普遍存在，傳統(tǒng)的數(shù)據(jù)修復方法對于海量數(shù)據(jù)處理代價過高，且不能徹底修復，在這些不完整的海量數(shù)據(jù)上進行滿足給定需求的近似查詢引起了學術界的關注.因此，提出一種基于壓縮的海量不完整數(shù)據(jù)近似查詢方法，該方法對屬性值缺失字段進行標記，根據(jù)頻繁查詢條件對標記后的數(shù)據(jù)進行壓縮，并建立對應索引；根據(jù)屬性劃分對索引文件再次壓縮以節(jié)省存儲空間，采用編碼字典對索引壓縮文件進行選擇和投影操作，最終獲得不完整數(shù)據(jù)的近似查詢結果.實驗表明，該方法能夠快速定位不完整數(shù)據(jù)的壓縮位置，提高了查詢效率，節(jié)省了存儲空間，并且保證了查詢結果的完整性.

關鍵詞不完整數(shù)據(jù)；近似查詢；數(shù)據(jù)壓縮；索引；編碼字典

隨著信息技術的發(fā)展，數(shù)據(jù)規(guī)模不斷增加，尤其是在以計算機和互聯(lián)網(wǎng)為基礎的應用中數(shù)據(jù)更是以指數(shù)形式增長.而在海量數(shù)據(jù)帶來豐富信息的同時，也帶來許多質(zhì)量問題，這些問題嚴重地制約著數(shù)據(jù)的應用價值[1-2].其中，數(shù)據(jù)缺失是一個常見的現(xiàn)象.不合理地處理缺失數(shù)據(jù)將造成錯誤結果，甚至是嚴重的損失[3].因此，如何有效存儲和管理有屬性值缺失的海量數(shù)據(jù),即海量不完整數(shù)據(jù)，是研究的重中之重.

近幾年來，許多學者對海量不完整數(shù)據(jù)的處理進行了研究.現(xiàn)有的方法在對海量不完整數(shù)據(jù)進行操作之前，需要對其進行數(shù)據(jù)清洗[4-7]，然后再對清洗后的“干凈”數(shù)據(jù)進行壓縮存儲[8-11]和管理.然而，對于海量數(shù)據(jù)而言，先進行數(shù)據(jù)清洗再操作數(shù)據(jù)有很多弊端.首先，基于數(shù)據(jù)的海量性，數(shù)據(jù)清洗的代價將會非常大；其次，清洗的結果會受到很多因素的影響，可能會引入新的“噪聲”導致清洗結果并不準確；此外，數(shù)據(jù)清洗還會產(chǎn)生時效性問題，結果就是很多時效數(shù)據(jù)將失去意義.因此，我們的工作就是越過數(shù)據(jù)清洗直接對海量不完整數(shù)據(jù)進行壓縮存儲以及管理，而現(xiàn)有的壓縮算法都是對完備數(shù)據(jù)的壓縮，所以我們要設計一種新的適用于不完整數(shù)據(jù)的壓縮算法，以及與其相對應的查詢算法.由此可見，針對海量不完整數(shù)據(jù)的壓縮與查詢處理方法的研究是十分必要的[12].

針對上述問題，本文提出了一種基于壓縮的海量不完整數(shù)據(jù)近似查詢方法(compression-based approximate query for massive incomplete data, AQ-MI),該方法可以快速地定位查詢數(shù)據(jù)的壓縮位置，提高查詢效率，還能夠大幅度地減少存儲空間，并且保證查詢結果的完整性.本文的主要貢獻有3點：

1) 提出一種面向海量不完整數(shù)據(jù)的壓縮策略，利用頻繁查詢條件索引法，在被標記數(shù)據(jù)壓縮時將每一元組所滿足的不確定條件和確定性條件作為索引存儲于索引表中.采用屬性值缺失字段標記策略，對帶有標記的字段進行重復壓縮，以保證查詢結果的完整性和可信性.還提出了一種基于Attr-1的索引文件壓縮方法，進一步減少存儲空間.

2) 提出一種無解壓近似查詢方法，查詢時分析查詢語句，對索引壓縮文件進行相應的選擇和投影操作，根據(jù)獲得的被標記數(shù)據(jù)壓縮地址，最終得到近似查詢結果.

3) 設計了詳細的性能評估實驗，實驗結果表明AQ-MI算法可以快速地定位查詢數(shù)據(jù)的壓縮位置，提高查詢效率，還能夠大幅度地減少存儲空間，并且保證查詢結果的完整性.

1相關工作

文獻[4-7]是常見的對不完整數(shù)據(jù)的清洗方法.文獻[4]采用基于記錄刪除的數(shù)據(jù)清洗策略，在查詢之前先刪除不完整的記錄，再在“干凈的”數(shù)據(jù)庫上進行計算查詢，雖然得到唯一確定的結果，但丟失了部分有價值的信息.文獻[5-7]采用基于數(shù)據(jù)填充的數(shù)據(jù)清洗策略，在查詢之前用一定值去填充屬性值缺失的字段，從而使信息完備化，然而這種方法只是在一定程度上補以主觀的估計值，不一定完全符合客觀事實，而且對缺失值不正確的填充往往將新的噪聲引入數(shù)據(jù)，使查詢產(chǎn)生錯誤的結果.

對海量數(shù)據(jù)的壓縮，最常見的方法是基于編碼字典的壓縮[8-10]，這類方法采用按列存儲的思想對數(shù)據(jù)進行壓縮，將對原始數(shù)據(jù)的查詢轉化為對壓縮編碼位的操作.文獻[8-9]是對串表壓縮算法LZW進行改進，主要思想是利用較短的碼字表示較長的字符串來實現(xiàn)壓縮.文獻[10]應用一種對稱編碼SVC，進一步減短對應碼字長度，提高測試數(shù)據(jù)的壓縮效果.采用這種編碼字典方法可以實現(xiàn)不解壓直接查詢，提高了效率，但是增加了匹配字典和維護字典的代價，不適用于更新頻繁的系統(tǒng).文獻[11]提出一種海量數(shù)據(jù)壓縮存儲結構，在數(shù)據(jù)壓縮時，為每條元組計算相應的索引項，該方法雖然在查詢時可以提高效率，但對于海量數(shù)據(jù)而言，索引的規(guī)模也很大，即增加了大量額外的存儲空間.

就目前的海量不完整數(shù)據(jù)的存儲和管理方法而言，很多方面都存在弊端.現(xiàn)有方法都是對原始數(shù)據(jù)進行數(shù)據(jù)清洗后，再在完備數(shù)據(jù)上進行壓縮和查詢，然而對海量數(shù)據(jù)的清洗存在清洗代價大、清洗結果不準確以及時效性差等問題.因此，本文提出AQ-MI方法，越過數(shù)據(jù)清洗直接對海量不完整數(shù)據(jù)進行壓縮和查詢，該方法可以快速地定位查詢數(shù)據(jù)的壓縮位置，提高查詢效率，還能夠大幅度地減少存儲空間，并且保證查詢結果的完整性.

2定義和數(shù)據(jù)結構

2.1相關定義

由于對海量數(shù)據(jù)的操作需要較高的時間和空間代價，因此有查詢類型少、查詢語句簡單固定、更新和刪除頻率低等特點.我們的目的是改善使用頻繁的數(shù)據(jù)操作的響應時間.假設對于一個海量數(shù)據(jù)庫應用，經(jīng)過統(tǒng)計后可以獲得頻繁使用的數(shù)據(jù)操作語句，即查詢語句中WHERE后出現(xiàn)的查詢條件，將這些查詢條件分為確定性查詢條件和不確定查詢條件.

定義1. 確定性查詢條件Def_Query.查詢下發(fā)前已經(jīng)確定的查詢條件，一般為頻繁使用的固定范圍查詢，這類查詢大多是查詢某一屬性值是否超過設定的閾值，如“Temperature>35”.確定性查詢條件的屬性名和屬性值固定，作為一個整體出現(xiàn).

定義2. 不確定查詢條件Undef_Query.查詢下發(fā)前不能完全確定的查詢條件，一般為頻繁使用的不固定等值查詢，這類查詢大多是查詢某一屬性值是否存在于記錄中，如“Username=***”.不確定查詢條件的屬性名固定，屬性值可變.

2.2基本數(shù)據(jù)結構

經(jīng)過統(tǒng)計獲得所有確定性查詢條件和不確定查詢條件后，在壓縮存儲時將每一條元組所滿足的不確定查詢條件的屬性值和確定性查詢條件作為索引存儲于數(shù)據(jù)庫中，同時將元組存放到相應的待壓縮緩存塊中.當某一緩存塊裝滿后，將其按順序進行壓縮存儲，并在數(shù)據(jù)庫中存儲元組所在壓縮文件地址.索引表結構和壓縮文件地址表結構分別如圖1和圖2所示:

Fig. 1　Structure of index table.圖1　索引表結構

Fig. 2　Structure of compressed file address table.圖2　壓縮文件地址表結構

圖1中，Id為索引序號，Tp_Id為元組序號，字段Undef_Val_i為當前元組第i個不確定查詢條件的屬性值.字段Def_Query以位編碼形式存儲當前元組所滿足的確定性查詢條件.對于n個確定性查詢條件Q1,Q2,…,Qn，設當前元組的字段Def_Query的位編碼為B1B2…Bn，若當前元組滿足條件Qi，則Bi=1；否則Bi=0.

圖2中，Block_Id為當前元組所在緩存塊的序號，字段Address為緩存塊壓縮后對應的壓縮文件地址.

通過將索引表和地址表在屬性Block_Id上的連接便能夠得到完整的索引文件.值得注意的是，不同Def_Query值對應不同的緩存塊，也就對應不同的壓縮文件地址.而當某一緩存塊壓縮存儲后，將為Block_Id賦一個新的值，因此相同的Def_Query值也可能對應不同的緩存塊和壓縮文件地址.

3基于壓縮的海量不完整數(shù)據(jù)近似查詢算法

3.1不完整數(shù)據(jù)的標記

傳統(tǒng)的數(shù)據(jù)清洗方法很難將不完整數(shù)據(jù)徹底清洗干凈，還會造成信息損失，降低效率.因此，我們希望不對原始數(shù)據(jù)清洗，直接進行存儲和管理，以此來避免信息的損失.實際上，只要能在數(shù)據(jù)庫中把完整的和不完整的分量標識出來，并在查詢回答中正確地保持標識，那么無論是完整的還是不完整的信息，只要它符合查詢條件，都將保留在查詢結果中，信息丟失問題自然不存在.

根據(jù)上述思想，在預處理階段，掃描一次原始數(shù)據(jù)D，將屬性值缺失的字段用“*”進行標記，標記后的數(shù)據(jù)記為D*.一個簡單例子如表1所示，用標記“*”來區(qū)分數(shù)據(jù)庫的完整和不完整分量.

Table 1Area Temperature Information Table with “*” Mark

表1　用“*”標記的地區(qū)溫度信息表TempInfo

假設查詢語句:

SELECTPlace,Temperature,Duration

FROMTempInfo

WHERETemperature>19

ANDDuration>8.

則查詢結果如表2所示：

Table 2　Query Result

如表2所示，被“*”標記的字段為屬性值缺失字段，它可以滿足任何查詢條件，因此在查詢計算中可以正確地保持標記語義，使得查詢結果可信有意義.

3.2D*數(shù)據(jù)的壓縮存儲

在對原始數(shù)據(jù)掃描標記后，獲得D*數(shù)據(jù)，根據(jù)統(tǒng)計的頻繁查詢條件壓縮數(shù)據(jù)至不同壓縮文件并建立對應索引，然后壓縮索引文件來進一步節(jié)省存儲空間.因此，在壓縮存儲階段，分為對D*數(shù)據(jù)的壓縮和對索引文件的壓縮.

3.2.1D*數(shù)據(jù)的壓縮

對于海量不完整數(shù)據(jù)D*，假設D*包含m條元組，n個屬性.進行壓縮處理后，得到索引文件和壓縮數(shù)據(jù).假設索引文件包含i條元組、j個屬性，則i≥m且j?n.圖3是D*數(shù)據(jù)的壓縮示意圖：

Fig. 3　The process of D*data compression.圖3　D*數(shù)據(jù)壓縮示意圖

對于D*的每一條元組t，首先計算t所滿足的確定性查詢條件的Def_Query值，將t寫入為該Def_Query分配的待壓縮緩存塊BlockDef_Query中，然后將t的不確定查詢條件的屬性值Undef_Vals和Def_Query作為索引項存儲于數(shù)據(jù)庫索引表中，同時在索引表中記錄元組t所在的待壓縮緩存塊BlockDef_Query的序號Block_IdDef_Query.若緩存塊BlockDef_Query已滿，則采用某一壓縮算法對BlockDef_Query進行壓縮.在壓縮存儲的同時，將獲得該壓縮文件的地址AddressDef_Query，最后把Block_IdDef_Query和AddressDef_Query序?qū)懭氲刂繁?下面舉一個簡單的例子，如表3所示：

Table 3　Area Temperature Information Table

表3為地區(qū)溫度信息表，假設不確定查詢條件為Place=***；確定性查詢條件為Temperature>35，Duration>5.則經(jīng)過計算可得元組1的Def_Query值為10，元組2的Def_Query值為01.因此這2條記錄將分別壓縮至2個壓縮文件，它們的索引表和地址表連接后所得索引文件內(nèi)容如表4所示.

Table 4　Example 1 of Index File

對于標記為“*”的屬性值缺失字段，它可能是任何值，那么就應該滿足任何查詢條件，為了保證查詢結果可信有意義，需要對含有屬性標記有“*”的元組進行重復壓縮.即對于含有“*”標記字段的元組t，可能會計算得出2個甚至多個Def_Query值，則需要將t分別寫入為這些Def_Query值分配的多個待壓縮緩存塊BlockDef_Query中，后續(xù)的處理過程同未含有標記字段的元組.

對表3的例子進行修改，如表5所示：

Table 5Area Temperature Information Table with “*” Mark

表5　用“*”標記的地區(qū)溫度信息表

如果將上述例子中的信息表修改為如表5所示，則元組2的Def_Query值為01或者11，因此需要將該元組同時壓縮至01和11對應的2個壓縮文件中.其索引文件如表6所示：

Table 6　Example 2 of Index File

3.2.2D*數(shù)據(jù)的壓縮優(yōu)化

在統(tǒng)計確定性查詢條件時，可能會出現(xiàn)許多冗余條件，比如經(jīng)統(tǒng)計，頻繁使用的查詢條件有：Temperature>35和Temperature>55.如此將會使得索引表中屬性Def_Query的位編碼字段長度增加1 b，那么多個條件的集合對應的位編碼將會更加冗余.如此一來，不僅會增加索引文件的存儲空間，還會降低查詢計算的效率.

針對這個問題，本文的優(yōu)化策略是將有包含關系的確定性條件進行削減，剔除掉被包含的條件，只保留最大滿足條件.如上述例子的2個條件，只保留Temperature>35.這將大大減少索引編碼的長度，節(jié)省了存儲空間，同時，在查詢索引匹配時效率也將更高.雖然這樣處理會使得最終的查詢結果是近似的(包含精確結果)，但對于海量數(shù)據(jù)而言，快速地返回滿足需求的近似結果是值得提倡的[13].

3.2.3基于Attr-1的索引文件壓縮

根據(jù)D*數(shù)據(jù)的壓縮過程可知，為了提高查詢效率，D*數(shù)據(jù)的每個元組都建立了一條或多條索引，不僅如此，索引表的字段Undef_Val_i數(shù)量未知，它是由不確定查詢條件來確定的，因此索引表可能是一張寬表，如此不論是從元組數(shù)量還是從屬性數(shù)量上都增加了額外的存儲空間.為了進一步減少存儲空間，對索引文件進行壓縮.而為了不增加除了D*數(shù)據(jù)查詢時的解壓耗時，對索引文件采用編碼字典方式進行壓縮，以便后期的無解壓查詢.

對于D*數(shù)據(jù)的索引文件T，假設T包含n個屬性，共有m條元組.對于屬性Ai中出現(xiàn)的所有候選值，按照壓縮模式中Ai對應的編碼模式調(diào)用不同的編碼方法.T中所有屬性經(jīng)壓縮處理后，得到編碼字典和索引壓縮文件.圖4是索引文件的壓縮示意圖：

Fig. 4　The process of index file compression.圖4　Attr-1索引文件壓縮示意圖

如圖4所示，索引文件中屬性Def_Query的值已經(jīng)是位編碼類型，因此無需對該屬性進行壓縮編碼，僅僅對索引文件表的其他Attr-1個屬性依據(jù)壓縮模式配置文件進行編碼，而屬性Def_Query的所有數(shù)據(jù)則直接拷貝到索引壓縮文件末尾，即屬性Def_Query對應的數(shù)據(jù)不出現(xiàn)在編碼字典中.

在壓縮編碼時候，不同屬性可以采用不同的編碼方式，而且還要兼顧存儲空間和查詢效率，因此采用K-of-N編碼(K-of-Nencoding)[14].假設壓縮模式配置文件規(guī)定索引文件的全部屬性(除Def_Query)的編碼方式皆為K-of-N編碼，對表6所示的索引文件進行壓縮編碼，得到的編碼字典如表7～11所示：

Table 7　Example of Encoding Dictionary for Id

Table 8　Example of Encoding Dictionary for Tp_Id

Table 9　Example of Encoding Dictionary for Place

Table 10　Example of Encoding Dictionary for Block_Id

Table 11　Example of Encoding Dictionary for Address

表6所示的索引文件壓縮后對應的索引壓縮文件如表12所示：

Table 12　Example of Index Compression File

表7至表12的例子只是為了解釋壓縮原理，并不能很好地顯示出壓縮效果.而實際中的數(shù)據(jù)值往往占據(jù)很大的存儲空間，比如某字段值為@addr4031331963，此時將其壓縮編碼為001就會明顯顯示出壓縮的效果.

3.2.4海量不完整數(shù)據(jù)D*壓縮算法

如算法1所示為海量不完整數(shù)據(jù)D*的壓縮算法，壓縮過程包括2個階段:1)將不完整數(shù)據(jù)D*根據(jù)確定性和不確定查詢條件進行壓縮并建立對應的索引;2)通過壓縮模式配置文件對階段1生成的索引文件進行壓縮，以進一步減少存儲空間.

算法1. 海量不完整數(shù)據(jù)D*壓縮算法.

輸入:海量不完整數(shù)據(jù)D*、索引壓縮模式配置文件C;

輸出:壓縮數(shù)據(jù)K、索引壓縮文件T、編碼字典M.

① for each元組t∈Rdo

② if (t不包含被標記字段)

③ 計算t所滿足的確定性查詢條件的Def_Query值;

④ 將t寫入為該Def_Query分配的待壓縮緩存塊BlockDef_Query中，設定其序號為Block_IdDef_Query;

⑤ else

⑥ 計算t所滿足的多個Def_Query值;

⑦ 將t重復寫入這些Def_Query對應的待壓縮緩存塊BlockDef_Query中，設定其序號為Block_IdDef_Query;

⑧ end if

⑨ 將t的不確定查詢條件的屬性值Undef_Vals，Def_Query，Block_IdDef_Query插入數(shù)據(jù)庫索引表;

⑩ if (BlockDef_Query已滿)

根據(jù)算法1的描述可知，階段1以元組為單位對D*數(shù)據(jù)進行計算并進行壓縮，因此時間復雜度為O(N)；階段2分別以屬性和元組為單位，對索引文件進行了一次掃描，2次掃描分別生成了編碼字典和索引壓縮文件，因此時間復雜度為O(N).所以，海量不完整數(shù)據(jù)D*的壓縮算法時間復雜度為O(N).

3.3壓縮后D*數(shù)據(jù)的近似查詢

3.3.1近似查詢

所謂近似查詢，體現(xiàn)在2個方面：1)在統(tǒng)計頻繁確定性查詢條件時，為了節(jié)省存儲空間并且提高查詢效率，將被包含的確定性條件剔除，如此在查詢時便會得到包含精確結果的近似查詢結果；2)在查詢結果中帶有*標記的不完整數(shù)據(jù).由于索引的存在可以快速獲得滿足查詢條件的壓縮文件地址集合，因此在查詢處理階段，主要工作就是對索引壓縮文件的無解壓查詢，其本質(zhì)就是通過對查詢語句的解析，將對原始數(shù)據(jù)的查詢轉化為對壓縮編碼位的選擇和投影操作.

3.3.2選擇操作

基于本文提出的壓縮和查詢處理方法的特殊性，在無解壓查詢時可能涉及到的選擇操作僅是對屬性Undef_Vals和屬性Def_Query的等值操作，因此對其他操作不做贅述.依舊以K-of-N編碼為例，假設要進行的等值操作為Undef_Val_i=X，X的編碼為xnxn-1…x2x1，待比較數(shù)據(jù)的編碼為anan-1…a2a1.等值操作規(guī)則如下：

K-of-N編碼由于采用了N位中有K位為1的規(guī)則，因此只需要知道這些為1的編碼位具體是哪些位，就可以唯一地確定一個編碼.假設X的編碼xnxn-1…x2x1中，xi1xi2…xik為編碼為1的位，則在待比較的編碼中，只有編碼ai1ai2…aik對應的編碼也全部為1，才是和B相等的數(shù)據(jù).該操作要處理的編碼位為K位，以上過程可形式化地表示為

(1)

同理可得不等值操作的形式化表示為

(2)

需要注意的是，屬性Def_Query本身就是位編碼形式，因此K-of-N編碼的選擇操作規(guī)則不適用于屬性Def_Query.因為Def_Query的值是由若干確定性查詢條件生成的，所以需要比較每一位才能知道是否等值.假設要進行的等值操作為Def_Query=X，X的編碼為xnxn-1…x2x1，待比較數(shù)據(jù)的編碼為anan-1…a2a1.等值操作規(guī)則如下：

對于待比較編碼anan-1…a2a1，如果其上所有編碼位上的編碼與X的編碼xnxn-1…x2x1一一對應地全部相同，那么該編碼就與X的編碼相等.操作規(guī)則形式化描述為

(3)

同理可得不等值操作的形式化表示為

(4)

3.3.3投影操作

由于采用了按列壓縮和存儲的基本思想，因此對索引壓縮文件的投影操作相對來說比較簡單.投影操作在所有的選擇操作結束后執(zhí)行，選擇操作結束后獲得滿足選擇條件的元組集合.對于索引壓縮文件來說，僅是對屬性Address進行投影操作，因此，對于元組集合中的每一條元組對應的屬性Address，在編碼字典中查找對應的原始數(shù)據(jù)值，在這些原始值集合中去掉重復的數(shù)據(jù)，就得到投影操作的最終結果.

3.3.4海量不完整數(shù)據(jù)D*查詢算法

在進行無解壓查詢時，需要由查詢條件來構造查詢索引.查詢索引構造方法如下：首先分析查詢語句，將其查詢條件用不確定查詢條件和位編碼形式的確定性查詢條件來表示.如此，原查詢語句的查詢條件就轉化為由Undef_Query和Def_Query組成的查詢索引.

如果查詢索引中只存在Def_Query，則直接以Def_Query對索引壓縮文件進行選擇操作，對得到的選擇結果在屬性Address上做投影操作即可得到滿足查詢條件的D*數(shù)據(jù)的壓縮地址集合，根據(jù)地址集合解壓文件后即可得到查詢結果.如果查詢索引中存在Undef_Query，則需要在編碼字典中找到Undef_Query對應的編碼，然后對索引壓縮文件進行后續(xù)操作.海量不完整數(shù)據(jù)D*查詢算法如算法2所示：

算法2. 海量不完整數(shù)據(jù)D*查詢算法.

輸入:查詢語句Q、編碼字典M、索引壓縮文件T、壓縮數(shù)據(jù)K;

輸出:查詢結果Result.

① 解析查詢語句Q，得到Undef_Query和Def_Query構造查詢索引X;*選擇操作*

② if (Undef_Query≠Null)

③ for eachUndef_Val∈Undef_Querydo

④ 在編碼字典M中查找對應的編碼;

⑤ 采用式(1)(2)對T進行選擇操作;

⑥ end for

⑦ end if

⑧ if (Def_Query≠Null)

⑨ 采用式(3)(4)對T進行選擇操作;

⑩ end if

根據(jù)算法2的描述可知，在選擇操作中，最好情況下對Def_Query進行選擇操作，時間復雜度為O(1)；最壞情況下對Undef_Query中的多個條件進行選擇操作，時間復雜度為O(N)，因此選擇操作時間復雜度為O(N).在投影操作中，需要對編碼字典進行一次掃描，所以投影操作時間復雜度為O(N).最后根據(jù)查詢到的地址集合將查詢結果依次解壓出來，時間復雜度為O(N).所以，海量不完整數(shù)據(jù)D*的查詢算法時間復雜度為O(N).

3.4不完整數(shù)據(jù)多重壓縮的優(yōu)化

根據(jù)2.2.1節(jié)的描述，在對含有*標記的屬性的元組進行壓縮的時候，會涉及到同一元組的多重壓縮.在只有1個*屬性滿足確定性查詢條件的情況下，該元組重復壓縮至2個壓縮文件；2個*屬性分別滿足2個確定性查詢條件時，將增加至4個壓縮文件,如此便呈現(xiàn)指數(shù)增長，將會大大增加壓縮的代價.

針對這個問題，本文采用基于屬性重要性的主客觀權重分配策略.在對原始數(shù)據(jù)進行壓縮存儲之前，首先對全部屬性進行主觀權重分配并設定閾值，即根據(jù)專家經(jīng)驗主觀評估各屬性之間的相對重要程度，相對重要的屬性分配相對較高權重.設定閾值為γ，則權重大于γ的屬性為重要屬性.在壓縮階段，只有當*標記的屬性權重大于閾值時才進行多重編碼，否則只對元組編碼一次即可.

每次查詢之后，對查詢結果的屬性進行客觀權重分配并反饋給初始主觀權重進行調(diào)整.假設查詢結果為n個屬性對應的m條元組記錄，則大體過程如下.

1) 采用m×n階特征值矩陣對查詢結果進行聚類如式(5)所示：

(5)

2) 計算得到特征值矩陣的*余子式，保證數(shù)據(jù)集的完備性；

3) 采用最大最小法建立模糊相似關系如式(6)所示：

(6)

4) 利用模糊等價閉包法求出模糊等價矩陣并確定分類數(shù)目；

5) 依次求出刪除各屬性后的分類數(shù)目以確定各屬性的重要性；

6) 根據(jù)重要性的大小確定各屬性的權重分配，若某屬性刪除后分類數(shù)目沒有發(fā)生變化，則表明該屬性在查詢結果的整體性評價中是不必要的；

7) 將本次查詢得到的部分屬性客觀權重反饋給初始主觀權重進行動態(tài)調(diào)整，以便于新增數(shù)據(jù)的壓縮優(yōu)化.

采用基于屬性重要性的主客觀權重分配策略將在很大程度上減少壓縮耗時以及存儲空間，同時也保證了重要屬性在查詢結果中的正確性和完整性.

4實驗及其分析

本節(jié)通過實驗來驗證本文提出的基于壓縮的不完整數(shù)據(jù)近似查詢方法AQ-MI的性能.實驗主要分為壓縮率實驗、查詢效率實驗、優(yōu)化對比實驗和信息丟失比實驗4個部分.將AQ-MI與壓縮處理技術中典型的字典壓縮算法LZW[9]和索引壓縮算法PI[11]在壓縮率以及查詢效率2方面進行了對比分析，又將AQ-MI與數(shù)據(jù)清洗技術中典型的基于元組刪除法RWD[4]和基于數(shù)據(jù)填充法MIBOI[5]在查詢結果信息丟失比例方面進行了對比分析，最終給出實驗結果.

4.1實驗設置

本實驗中采用的數(shù)據(jù)為TPC-H Benchmark[15]生成工具DBGen生成的Lineitem表.DBGen按照主鍵L_OrderKey值遞增順序產(chǎn)生帶有隨機屬性值缺失字段的Lineitem記錄.

4.2壓縮率實驗

在這個實驗中，采用壓縮率(compression rate,CR)來衡量不同方法的壓縮效果.首先對壓縮率進行如下定義：壓縮率即壓縮后數(shù)據(jù)與壓縮前數(shù)據(jù)的比值.

由CR定義可知，CR越小說明壓縮效果越好.設定Lineitem表的屬性數(shù)量固定為16，記錄數(shù)量不斷增加.3種壓縮方法的CR如圖5所示:

Fig. 5　Experiment result of CR.圖5　CR實驗結果圖

圖5顯示了3種壓縮方法的CR.從圖5中可以看出，CR與數(shù)據(jù)大小的變化沒有什么明顯的關系，隨著原始數(shù)據(jù)從100 MB增大至2 GB，各個壓縮方法的CR基本保持穩(wěn)定.由CR定義可知各個壓縮方法的CR公式：

CRPI=(索引文件大小+壓縮數(shù)據(jù)大小)原始數(shù)據(jù)大??；

CRLZW=(編碼字典大小+壓縮數(shù)據(jù)大小)原始數(shù)據(jù)大?。?/p>

CRAQ-MI=(編碼字典大小+索引壓縮文件大小+壓縮數(shù)據(jù)大小)原始數(shù)據(jù)大小.

顯然地，PI的CR最大，其次是AQ-MI和LZW.這是由于PI將原始數(shù)據(jù)壓縮的同時建立了索引文件，雖然這樣能夠提升查詢效率，卻增加了額外的存儲空間.而LZW壓縮效果最佳，這是因為它壓縮后的數(shù)據(jù)僅僅多了一個編碼字典.本文提出的AQ-MI比LZW多出一個索引壓縮文件，因此CR稍大，但是僅僅犧牲一點存儲空間卻換來了查詢效率的提高是值得的.

4.3查詢效率實驗

在這個實驗中，對3種壓縮方法的壓縮數(shù)據(jù)進行查詢的效率測試，即查詢時間測試.主要考察在數(shù)據(jù)大小固定時，3種方法分別進行壓縮后數(shù)據(jù)的查詢執(zhí)行情況，以驗證各個算法的實時性能.設定Lineitem表的記錄數(shù)量固定為700萬條，大小為1 GB，查詢條件數(shù)量不斷增加.3種方法的查詢效率如圖6所示：

Fig. 6　Experiment result of query efficiency.圖6　查詢效率實驗結果圖

圖6顯示了3種壓縮方法將1 GB的原始數(shù)據(jù)壓縮后，在不同查詢條件數(shù)目下的查詢時間.從圖6中可以看出，隨著查詢條件數(shù)量從2個增加到5個，各方法壓縮后數(shù)據(jù)的查詢時間都在增加.其中，LZW的查詢時間最長，其次是AQ-MI和PI.這是因為LZW在查詢時需要先分析查詢條件，然后對壓縮數(shù)據(jù)做選擇和投影操作，其查詢時間會隨著操作條件的增加而增加.PI在壓縮時就建立了對應壓縮地址的索引，分析并得到滿足查詢條件的索引，就可以快速地返回查詢結果.本文提出的AQ-MI比PI多了一步無解壓查詢索引壓縮文件，雖然也需要做選擇和投影操作，但不論查詢條件數(shù)量多少，大多數(shù)情況下僅需要對屬性Def_Query做一次選擇操作，對屬性Address做一次投影操作即可，然后得到D*數(shù)據(jù)壓縮地址就可以快速返回查詢結果.

4.4優(yōu)化對比實驗

在這個實驗中，對本文所提方法AQ-MI和優(yōu)化后方法AQ-MI′進行對比測試.主要考察采用壓縮優(yōu)化策略前后的壓縮效果.設定Lineitem表的屬性數(shù)量固定為16，記錄數(shù)量固定為700萬條，大小為1 GB，Def_Query數(shù)量不斷增加.AQ-MI和AO-MI′的CR如圖7所示：

Fig. 7　Experiment result of optimization comparison of CR.圖7　CR優(yōu)化對比實驗結果圖

圖7顯示了AQ-MI和AO-MI′的CR.從圖7可以看出，隨著Def_Query數(shù)目從2個增加到5個，AQ-MI和AO-MI′的CR都在增大，但是顯然AQ-MI的CR增長幅度更大，這是因為AQ-MI在對含有*標記的屬性的元組進行壓縮的時候，只要有1個*屬性滿足Def_Query，就會讓該元組的壓縮次數(shù)增加1倍，雖然屬性值缺失字段是隨機產(chǎn)生的，CR并不會呈現(xiàn)指數(shù)增長，但Def_Query數(shù)量的增多自然會導致壓縮效率的降低.相對地，AQ-MI′的CR雖然也在增長，但明顯遠遠低于AQ-MI，這是由于其采用了基于屬性重要性的主客觀權重分配策略，權重高于閾值的屬性僅僅是少數(shù)，CR自然就比AQ-MI低了.查詢同理，CR低，索引文件的元組數(shù)量就少，從而減少了查詢時的投影操作以及字典匹配操作，查詢效率自然就高，這里不再贅述.在實際應用中，對海量數(shù)據(jù)的操作需要較高的時間和空間代價，一般情況下查詢類型較少，而本文的壓縮優(yōu)化正適用于數(shù)據(jù)量大，確定性查詢條件多的情況，且Def_Query數(shù)目越多優(yōu)化效果越明顯.

4.5信息丟失比實驗

在這個實驗中，采用信息丟失比(information loss ratio,ILR)來對本文提出的AQ-MI方法和主流數(shù)據(jù)清洗方法RWD，MIBOI在信息保持方面的性能進行比較.首先對信息丟失比進行如下定義：所有滿足查詢條件但丟失的屬性值所有滿足查詢條件的屬性值.

由ILR定義可知，ILR越小說明信息保持性能越好.設定對Lineitem表的查詢條件不變，數(shù)據(jù)記錄數(shù)量不斷增加.3種方法的ILR如圖8所示：

Fig. 8　Experiment result of ILR.圖8　ILR實驗結果圖

圖8顯示了3種方法的ILR.從圖8中可以看出，隨著原始數(shù)據(jù)從100 MB增大至2 GB，RWD查詢結果的ILR最高，其次是MIBOI，而本文提出的AQ-MI沒有信息丟失.這是因為RWD是基于記錄刪除的清洗方法，在查詢之前將屬性值缺失的記錄刪除，這樣雖然能查詢得到唯一確定的結果，但是丟失了很多有價值的信息，尤其是在原始數(shù)據(jù)中含有很多不完整數(shù)據(jù)的情況下丟失比更大.MIBOI是基于數(shù)據(jù)填補的清洗方法，在查詢預處理階段是以不完備數(shù)據(jù)聚類的結果為基礎進行缺失數(shù)據(jù)的填補，雖然能夠得到一個完備的信息表，但一些填補的數(shù)據(jù)不一定符合客觀事實，即與缺失的真實數(shù)據(jù)不一致，這就可能導致查詢結果缺少了本該包含的信息，但至少它的ILR比直接刪除記錄的RWD要低很多.而本文提出的AQ-MI方法在預處理階段只是掃描數(shù)據(jù)庫并標記屬性值缺失字段，在后續(xù)的壓縮存儲過程中，對有標記字段的元組進行多重壓縮，保證了查詢結果的完整性和可信性.

5結束語

傳統(tǒng)的數(shù)據(jù)修復方法對于海量數(shù)據(jù)處理代價過高，且不能徹底修復，為了實現(xiàn)在不完整的海量數(shù)據(jù)上進行滿足給定需求的近似查詢，提出了一種基于壓縮的海量不完整數(shù)據(jù)近似查詢方法AQ-MI.該方法對屬性值缺失字段進行標記，根據(jù)頻繁查詢條件對標記后的數(shù)據(jù)進行壓縮，并建立對應索引；根據(jù)屬性劃分對索引文件再次壓縮以節(jié)省存儲空間，采用編碼字典對索引壓縮文件進行選擇和投影操作，最終獲得不完整數(shù)據(jù)的近似查詢結果.實驗表明:與現(xiàn)有的壓縮查詢處理方法相比，AQ-MI不僅能在很大程度上減少存儲空間，還能夠提高查詢效率.此外，它對不完整信息的處理與現(xiàn)有的數(shù)據(jù)清洗方法相比，更能保證查詢結果的完整性.

參考文獻

[1]Li Jianzhong, Liu Xianmin. An important aspect of big data: Data usability[J]. Journal of Computer Research and Development, 2013, 50(6): 1147-1162 (in Chinese)(李建中, 劉顯敏. 大數(shù)據(jù)的一個重要方面: 數(shù)據(jù)可用性[J]. 計算機研究與發(fā)展, 2013, 50(6): 1147-1162)

[2]Aste M, Boninsegna M, Freno A, et al. Techniques for dealing with incomplete data: A tutorial and survey[J]. Pattern Analysis and Applications, 2015, 18(1): 1-29

[3]Dai J. Rough set approach to incomplete numerical data[J]. Information Sciences, 2013, 241(12): 43-57

[4]Kolahi S, Lakshmanan L V S. On approximating optimum repairs for functional dependency violations[C]Proc of the 12th Int Conf on Database Theory. New York: ACM, 2009: 53-62

[5]Wu Sen, Feng Xiaodong, Shan Zhiguang. Missing data imputation approach based on incomplete data clustering[J]. Chinese Journal of Computers, 2012, 35(8): 1726-1738 (in Chinese)(武森, 馮小東, 單志廣. 基于不完備數(shù)據(jù)聚類的缺失數(shù)據(jù)填補方法[J]. 計算機學報, 2012, 35(8): 1726-1738)

[6]Chen Zhikui, Lü Ailing, Zhang Qingchen, et al. A new algorithm for imputing missing data based on distinguishing the importance of attributes[J]. Microelectronics and Computer, 2013, 39(7): 2630-2631 (in Chinese)(陳志奎, 呂愛玲, 張清辰. 基于屬性重要性的不完備數(shù)據(jù)填充算法[J]. 微電子學與計算機, 2013, 39(7): 2630-2631)

[7]Chen Yuxin, Cheng Xu, Zhao Peng, et al. Process missing information for massive sparse data storage in cloud environment[J]. Journal of Computer Research and Development, 2012, 49(Suppl): 316-322 (in Chinese)(陳郁馨, 程序, 趙鵬, 等. 云環(huán)境中一種面向海量稀疏數(shù)據(jù)存儲的缺失值處理方法[J]. 計算機研究與發(fā)展, 2012, 49(增刊): 316-322)

[8]Xu Xia, Ma Guangsi, Yu Tao. Research and improvement on LZW lossless compression algorithm[J]. Computer Technology and Development, 2009, 19(4): 125-127 (in Chinese)(許霞, 馬光思, 魚濤. LZW無損壓縮算法的研究與改進[J]. 計算機技術與發(fā)展, 2009, 19(4): 125-127)

[9]Nandi U, Mandal J K. Modified compression techniques based on optimality of LZW code (MOLZW) [J]. Procedia Technology, 2013, 10: 949-956

[10]Liang Huaguo, Jiang Cuiyun, Luo Qiang. Test data compression and decompression using symmetry-variable codes[J]. Journal of Computer Research and Development, 2011, 48(12): 2391-2399 (in Chinses)(梁華國, 蔣翠云, 羅強. 應用對稱編碼的測試數(shù)據(jù)壓縮解壓方法[J]. 計算機研究與發(fā)展, 2011, 48(12): 2391-2399)

[11]Zhao Kai, Li Jianzhong, Luo Jizhou. Storage and operation of massive data compression based on predication index[J]. Computer Science, 2005, 32(9): 86-90 (in Chinese)(趙鍇,李建中,駱吉洲. 基于謂詞索引的海量數(shù)據(jù)壓縮存儲及數(shù)據(jù)操作算法[J]. 計算機科學, 2005, 32(9): 86-90)

[12]Arenas M, Pérez J, Reutter J. Data exchange beyond complete data[J]. Journal of the ACM, 2011, 60(4): 83-94

[13]Nair R. Big data needs approximate computing: Technical perspective[J]. Communications of the ACM, 2014, 58(1): 104-104

[14]Wong H K T, Liu H F, Olken F, et al. Bit transposed files[C]Proc of the 11th Int Conf on VLDB. San Francisco: Morgan Kaufmann, 1985: 448-457

[15]Transaction Processing Performance Council(TPC). TPC BENCHMARKTMH (Decision Support) Standard Specification Revision 2.17.1[EBOL]. (2014-11-13) [2015-05-13]. http:www.tpc.orgtpchdefault.asp

Wang Yan, born in 1978. PhD candidate and associate professor. Student member of China Computer Federation. Her main research interests include massive data query technology, sensing data processing, big data management, etc.

Liu Genghao, born in 1990. Master candidate. Student member of China Computer Federation. His main research interests include massive data query technology, etc.

Wang Junlu, born in 1988. Master and assistant engineer. Student member of China Computer Federation. His main research interests include database theory and techniques, big data processing techniques and massive data processing techniques, etc.

Song Baoyan, born in 1965. PhD and professor. Senior member of China Computer Federation. Her main research interests include database theory and techniques, RFID event stream processing techniques, big data management and graph data management, etc.

中圖法分類號TP391

通信作者：宋寶燕(bysong@lnu.edu.cn)

基金項目：國家自然科學基金項目(61472169,61472072)；國家科技支撐計劃基金項目(2012BAF13B08)；國家“九七三”重點基礎研究發(fā)展計劃前期研究專項基金項目(2014CB360509)；遼寧省科學事業(yè)公益研究基金項目(2015003003)；遼寧省工業(yè)攻關及成果產(chǎn)業(yè)化計劃項目(2012216007)

收稿日期：2015-06-30；修回日期：2015-11-06

This work was supported by the National Natural Science Foundation of China (61472169，61472072), the National Key Technology Research and Development Program of China (2012BAF13B08), the National Basic Research Program of China (973 Program) (2014CB360509), the Science Commonweal Research Foundation of Liaoning Province (2015003003), and the Industrial Research and Production Industrialization Program of Liaoning Province (2012216007).