并行数据库数据分布策略及查询算法研究

	并行数据库数据分布策略及查询算法研究
	文明波; 丁治明
专业	计算机软件与理论
导师	丁治明
	2010-06-01
学位授予单位	中国科学院研究生院
学位	硕士
学位授予地点	北京
关键词	并行数据库
摘要	数据库系统是作为数据的计算机化管理而产生的，从上世纪 70 年代关系模型出现之后，关系型数据库逐渐成为主流并延续到现在。随着时代的发展，数据模型日益复杂，数据规模也不断扩大，传统单机串行关系数据库系统逐渐无法处理海量的复杂数据，查询效率急剧降低。在移动对象数据库（MOD）项目中，我们发现随着数据量的增长，MOD 系统查询响应时间越来越长，直至让人无法忍受。为实现对海量对象有效存储、查询和管理，我们设计实现了并行数据库原型系统——PD 系统，在此过程中研究了并行数据库系统中的一些关键问题，取得了丰硕的成果。并行数据库系统与传统串行数据库系统最大的差别在于数据的分布存储和操作的并行执行，因此是并行数据库系统的关键所在。其中数据分布策略对系统性能具有重要影响，较差的数据分布策略可能会导致系统中出现严重的数据偏斜、操作偏斜等偏斜问题，从而极大的降低系统整体的加速比；并行操作算法对系统响应时间具有直接影响，没有高性能的并行查询算法，并行数据库系统必定不能实现高效查询；与此同时，数据的存储模式与并行操作算法是息息相关的，应将两者作为一个整体来考察和研究。并行查询算法是并行数据库中最为核心的问题，而并行查询算法中又以并行连接算法最为复杂和昂贵，此外连接运算也是查询操作中常用运算。在串行系统中连接已经成为系统性能的瓶颈，并行环境下由于数据的分布存储和连接运算所要求的数据集中之间的矛盾，使连接运算对系统的瓶颈作用更为严重，因此连接运算一直是分布/并行数据库系统领域的研究热点，但直到目前为止很少有简洁而有效的数据分布策略和并行连接算法来解决此问题。本文在PD系统已有的研究成果上，进一步研究了并行数据库系统的数据分布策略和并行操作算法，以期利用面向查询的数据分布策略和与之适应的并行操作算法来提高并行数据库系统的性能。本文首先简要介绍了并行数据库系统的发展历程、系统架构、关键问题、数据分布策略和并行算法等研究背景资料，然后通过对PD系统架构和其中并行查询执行步骤的分析，建立了系统响应时间的数学模型，以此为基础提出了表的查询模式和表间关联度的概念。利用上述两个概念提出了一种新的数据分布策略— —面向查询的数据库数据分布策略（SODDS），并设计了与 SODDS 数据分布策略相适应的并行操作算法库。最后搭建了实验系统，进行了一些比对试验，验证了SODDS和相关并行操作算法的有效性。
学科领域	数据库
语种	中文
内容类型	学位论文
URI标识	http://ir.iscas.ac.cn/handle/311060/2350
专题	基础软件国家工程研究中心
推荐引用方式 GB/T 7714	文明波,丁治明. 并行数据库数据分布策略及查询算法研究[D]. 北京. 中国科学院研究生院,2010.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
并行数据库数据分布策略及查询算法研究 .（573KB）			开放获取	使用许可	请求全文