基于R-树的空间数据库查询技术研究

摘要

空间数据库技术是当前数据库领域的一个研究热点。在国内外也开始应用于许多不同领域。 但空间数据具有数据量巨大，结构复杂，属性数据与空间数据密切相关，并随其反映的地理特性不同而具有不同的数据类型等特点。由于空间数据量的庞大，以及空间对象、空间查询的高度复杂性，空间数据库的查询效率是衡量空间数据库性能的重要指标。实际应用也对空间数据库的查询性能提出了迫切要求。 本文从研究空间数据库查询技术的基础入手，重点进行了基于空间聚类的R-树索引技术、基于R-树的空间连接索引和基于不均匀空间对象的空间连接精处理的研究，并在此基础上设计并实现了基于GIS的空间数据查询试验系统。 在基于空间聚类的R-树索引技术的研究中，总结了现有R-树的算法特点，提出了面向R-树的混合空间聚类算法，并分别在动态环境和静态环境中实现了基于该混合空间聚类算法的动态R-树与静态R-树，同时分别将其与现有动态R-树和静态R-树进行了性能对比测试研究，论证了本文所提出的基于混合空间聚类的R-树在查询性能方面具有明显的优势。 在基于R-树的空间拓扑方向连接索引的研究中，首先介绍了空间对象间的连接关系及其判断准则，随后给出了空间连接索引的概念及基于R-树的空间连接方法，提出了基于R-树的空间拓扑方向连接索引的概念及其建立过程。空间连接索引的建立过程实际上是对参与空间连接查询的数据集进行的过滤处理的过程。空间拓扑方向连接索引是在建立连接索引的过程中加入了拓扑约束与方向约束，文中重点讨论了拓扑约束与方向约束的一些规则，以及这些规则如何应用于基于R-树的拓扑方向空间连接索引的建立过程，并在最后研究了基于R-树的距离约束规则，使得本文的空间连接索引可建立在拓扑、方向与距离关系及其任意组合的基础上，增强了基于R-树空间连接索引的完整性与灵活性。 基于不均匀空间对象的空间连接精处理主要是对空间连接查询处理的精炼阶段研究的研究。在对参与连接的数据集已经建立了空间连接索引的前提下，针对实际存储空间对象的各页面大小不均匀的特点，提出了基于不均匀空间对象的实现空间连接精处理的聚类分区-分区排序-页面排序三步策略。页面的聚类分区问题实际上是图的分区问题，而对各聚类分区的排序问题则实际上是图论中的货郎担问题。本文采用遗传算法分别实现了页面聚类分区及分区排序，并提出了一些确定最终页面访问顺序的规则，最后通过实验与现有的空间连接处理算法进行了对比测试，论证了该算法的可行性和先进性。 GIS空间数据查询试验系统主要是在分析当前空间数据查询处理软件并应用本文研究成果的基础上设计并基本实现的。系统的主要功能包括基本图文互查、点查询、区域查询、最近邻查询和空间连接查询，其中空间连接查询主要包括空间拓扑连接查询、空间方向连接查询、空间距离连接查询及其相互间的任意组合。

目录

文摘

英文文摘

原创性声明和关于学位论文使用授权说明

第一章绪论

1.1课题研究背景

1.2空间数据库及其查询研究的基本问题

1.2.1空间数据及属性数据分析

1.2.2空间模型分析

1.2.3空间数据库设计

1.2.4空间数据操作

1.2.5空间数据访问方法

1.2.6其它技术问题

1.3空间数据库查询技术的国内外研究现状

1.3.1空间数据模型和表达

1.3.2空间数据访问方法

1.3.3空间连接查询

1.3.4空间查询其它技术

1.4本文主要研究内容及方法

1.5论文的组织结构

第二章空间数据库查询概述

2.1空间数据库及其查询的特点

2.2空间数据访问方法

2.2.1格网型空间索引

2.2.2 BSP树空间索引

2.2.3 KDB树空间索引

2.2.4 R-树及其变种

2.2.5 CP-树

2.3点查询与区域查询

2.3.1数据集未排序且没有空间索引

2.3.2数据集具有空间索引

2.3.3使用空间填充曲线散列

2.4最近邻查询

2.4.1两遍算法

2.4.2一遍处理算法

2.5空间连接查询

2.5.1嵌套循环连接方法

2.5.2树匹配策略

2.5.3基于分块的空间归并连接方法

2.5.4空间哈希连接方法

2.6.5种子树连接方法

2.5.6槽索引空间连接方法

2.5.7常用空间连接算法的性能比较

2.6空间查询优化

2.7空间数据库查询语言

2.8本章小结

第三章基于空间聚类的R-树索引技术

3.1空间索引设计原则

3.2 R-树生成算法

3.2.1 R-树插入算法

3.2.2R-树删除算法

3.2.3 R-树查询算法

3.3R-树性能分析

3.4空间聚类

3.5面向R-树的混合空间聚类算法

3.5.1 HCR算法基本原理

3.5.2 HCR算法实现方法

3.6 HCR算法在动态环境中的实现

3.7 HCR算法在静态环境中的实现

3.8本章小结

第四章基于R-树的拓扑方向连接索引

4.1空间连接关系

4.2空间连接索引

4.2.1空间连接索引概述

4.2.2基于R-树的空间连接

4.3基于R-树的拓扑方向连接索引

4.4空间对象与其MBR间的拓扑方向映射

4.4.1空间对象与其MBR间的方向映射关系

4.4.2空间对象与其MBR间的拓扑映射关系

4.5 MBR与其R-树父节点间的拓扑方向映射关系

4.5.1 MBR与其R-树父节点间的方向映射关系

4.5.2 MBR与其R-树父节点间的拓扑映射关系

4.6 RTDJI实现

4.6.1 RTDJI实现算法

4.6.2 RTDJI计算实例

4.6.3 RTDJI代价模型

4.7基于R-树的距离连接约束

4.8本章小结

第五章基于不均匀对象的空间连接精处理

5.1空间对象间空间关系的判断

5.1.1空间对象间拓扑关系判断计算

5.1.2空间对象间方位关系计算

5.1.3空间对象间距离关系计算

5.2空间连接精处理与遗传算法

5.2.1空间连接精处理

5.2.2遗传算法

5.3页面聚类分区

5.3.1基本概念

5.3.2基于GA的PCG分区

5.4聚类排序

5.4.1 TSP问题

5.4.2基于GA的聚类分区顺序确定

5.5页面访问顺序的确定

5.6实验结果

5.7本章小结

第六章GIS空间数据查询试验系统设计与实现

6.1现有流行空间数据库系统空间查询分析

6.1.1 MapInfo SpatialWare

6.1.2 ESRI SDE

6.1.3 QL/G空间数据库原型系统

6.1.4空间数据选件

6.1.5空间数据刀片

6.2 GIS空间数据查询试验系统设计

6.2.1设计内容

6.2.2系统总体结构设计

6.2.3系统功能设计

6.3系统实现

6.3.1 MapX概述

6.3.2系统实现界面

6.3.3空间查询实例

6.4本章小结

第七章结束语

7.1主要研究工作和创新性成果

7.2后续应开展的研究工作

参考文献

致谢

攻读学位期间完成的论文和参加的科研情况

发表和撰写的论文

参加的主要科研项目