消除規范關系連接冗余的二次排序算法研究

劉黎志 ，張 威

1.智能機器人湖北省重點實驗室（武漢工程大學），湖北 武漢 430205；

2.武漢工程大學計算機科學與工程學院，湖北 武漢 430205

消除規范關系連接冗余的二次排序算法研究

劉黎志1，2，張 威1，2

1.智能機器人湖北省重點實驗室（武漢工程大學），湖北 武漢 430205；

2.武漢工程大學計算機科學與工程學院，湖北 武漢 430205

使用MapReduce框架對規范的一對多關系實體進行連接操作時，一方實體的各個屬性會在連接的結果中產生大量冗余.通過對二次排序算法進行優化，重新定義Map階段的分區過程、Shuffle階段的排序及分組過程，使得Map階段的輸出為包含一方實體屬性值和多方實體排序值的組合鍵及包含多方實體屬性值的集合.Reduce階段將組合鍵進行分解，提取一方實體的主碼作為HBase表的行健，并將組合鍵中一方實體的各個屬性值及多方實體屬性值集合分別寫入HBase表中對應的列，從而既實現了連接的語義，又消除了冗余.實驗證明，優化后的算法可以消除一方實體屬性值在連接結果中的冗余，提高了對連接結果的查詢效率.

MapReduce；連接冗余；二次排序；HBase

MapReduce在對規范的一對多關系進行連接操作時，一方關系的各個屬性值會在連接的結果中產生大量的冗余，為消除冗余，可利用HBase表的稀疏存儲特性，將一方關系的各個屬性值只存儲一次，同時將其對應的多方關系進行按列多次存儲.實現的過程可借鑒二次排序算法的思想，讓一方和多方關系在Map端進行連接后，輸出的Key既包含一方關系……