主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
骆吉洲,李建中.一种有效的关系数据库压缩方法.软件学报,2005,16(2):205-214
一种有效的关系数据库压缩方法
An Efficient Compression Method of Relational Database
投稿时间:2003-11-14  修订日期:2004-06-10
DOI:
中文关键词:  海量关系  压缩数据库  小值域属性组  NP-完全问题
英文关键词:massive relation  compressed database  small-range attributes’ combination  NP-complete problem
基金项目:Supported by the National Natural Science Foundation of China under Grant No.69873014 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2001AA444110 (国家高技术研究发展计划(863)); the Natural Science Foundation of Heilongjiang
作者单位
骆吉洲 哈尔滨工业大学,计算机科学与技术学院,黑龙江,哈尔滨,150001 
李建中 哈尔滨工业大学,计算机科学与技术学院,黑龙江,哈尔滨,150001
黑龙江大学,计算机科学与技术学院,黑龙江,哈尔滨,150080 
摘要点击次数: 3522
全文下载次数: 7653
中文摘要:
      海量关系中经常存在小值域属性,关系不仅在这些属性上的互不相同的值的数量很小,而且在这些属性的组合上的值域也很小.因此,海量关系在这些属性上有很多重复的组合值.一种提高数据库的存储和查询效率的重要方法就是消除这些重复取值.为此,提出了拆分压缩技术,它将海量关系拆分成两种较小的关系,其中一种关系的属性由小值域属性组组成,而另一种关系的属性是海量关系的其他属性.该方法的关键是小值域属性组的识别问题.在证明了这个问题的NP-完全性后,给出了两种在海量关系中识别小值域属性组合的算法,并在此基础上提出了海量关系拆分压缩技术,讨论了压缩关系的查询处理方法.实验结果表明,拆分压缩技术可以取得较好的压缩效果,并可以提高数据库查询处理的整体性能.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利