一种有效的关系数据库压缩方法

海量关系中经常存在小值域属性,关系不仅在这些属性上的互不相同的值的数量很小,而且在这些属性的组合上的值域也很小.因此,海量关系在这些属性上有很多重复的组合值.一种提高数据库的存储和查询效率的重要方法就是消除这些重复取值.为此,提出了拆分压缩技术,它将海量关系拆分成两种较小的关系,其中一种关系的属性由小值域属性组组成,而另一种关系的属性是海量关系的其他属性.该方法的关键是小值域属性组的识别问题.在证明了这个问题的NP-完全性后,给出了两种在海量关系中识别小值域属性组合的算法,并在此基础上提出了海量关系拆分压缩技术,讨论了压缩关系的查询处理方法.实验结果表明,拆分压缩技术可以取得较好的压缩效果,并可以提高数据库查询处理的整体性能.

An Efficient Compression Method of Relational Database

There usually are many attributes, called small-range attributes, with small number of different values in massive relations. The number of combination values of these attributes is also very few in massive relations so that there are a lot of repeated combination values of these attributes in massive relations. It is important to remove the repeated combination values to improve the efficiency of storing and querying massive relations. A compression method for removing the repeated combination values is proposed in this paper. To compress a massive relation, the method partitions the relation into two small relations: one consists of the small-range attributes and the other consists of the rest attributes. The key problem is to identify the small-range attributes. The NP-hardness of this problem is proved, and two approximate algorithms are proposed to solve this problem. The compression algorithms and the query processing based on the compressed method are also discussed. Experimental results show that the compression method has high compression ratio and enhances the query processing performance.