嵌入式空间数据库理论与技术研究
Study on the Theories and Technologies of Embedded Spatial Database Management System
嵌入式空间数据库作为一项将在未来各种空间信息应用领域(包括军事)中占重要地位的理论与技术,还没有得到充分的研究,虽然欧美发达国家已开始重视.本文对嵌入式空间数据库进行了较为全面、深入的研究,主要内容包括:(1)全面系统地总结了嵌入式空间数据库的相关概念、研究现状及该领域存在的问题,尤其是澄清了与EDBMS相关的、常被混淆或误用的概念.详细分析了嵌入式空间数据库的主要特点和特殊需求.(2)在分析了传统空间数据库系统各种体系结构的优缺点及两种典型EDBMS的体系结构的基础上,提出了实现嵌入式空间数据库的三种方案:基于文件进行扩展,基于关系型EDBMS进行扩展,基于非关系型EDBMS进行扩展.并设计了能提供关系数据库访问接口与普通调用接口的统一的空间扩展结构.总结分析了嵌入式空间数据库系统与传统空间数据库系统的体系结构的共性与差别.(3)对比分析了DBMS的5种逻辑模型的优缺点,并得出最适合采用REDBMS建立ESDBMS的结论.根据ESDBMS的特点提出了扩展其逻辑数据模型应该遵循的原则:简洁性、完备性和标准化,并根据该原则设计、实现了ESDBMS的空间数据类型和空间算子.(4)详细解析了数据存储和索引在ESDBMS的逻辑和物理层之间的映射关系,刻画了从磁盘存储到ESDBMS的逻辑视图的转换过程,揭示了数据存储和索引的本质.设计了一个能够自动支持应用数据类型变化的动态可扩展存储结构,使ESDBMS表现出了一定的智能性.针对嵌入式空间数据库的应用特点,提出并实现了ESDBMS的三级空间索引策略,即基于分层扩展R树为比例尺集合、图幅集合建立的一级索引,基于格网和改进四叉树索引分别为点和线、面建立的二级索引和第三级的基于增量联合索引的图幅内细节分层.(5)详细分析了ESDBMS空间查询处理的特点,在此基础上提出了ESDBMS的空间查询的代价制约因素,即访问代价、存储代价和计算代价,并提出了ESDBMS空间查询的三步处理策略.第一步利用对象的MBR执行空间连接,得到一个包含所有最终结果和一部分不满足连接谓词的额外对象对儿的候选集;第二步应用空间对象的更精确的(激进和保守)近似确认一部分结果,并排除一部分不满足连接谓词的近似对儿,以减少精炼阶段需要调度到内存的对象精确几何信息的数量和执行精确计算的数量,从而同时降低I/O代价和CPU代价;第三步遍历新候选集,读取其中对象的精确几何信息,执行空间查询条件判定.鉴于空间连接在ESDBMS的操作中的重要地位,重点研究了高效处理空间连接的算法,提出了基于三重近似的空间连接过滤策略:首先用空间对象的MBR执行连接,得到结果集的一个超集-候选集,然后通过对象的保守近似识别过滤候选集中的错误命中(即对象对儿的MBR相交但其本身并不相交),最后用对象的激进近似识别出一部分必定满足连接谓词的对象对儿.通过实验论证了空间对象的保守和激进近似应该与对象的MBR一起存储在空间索引中,并分析了近似对空间连接性能的影响.(6)针对嵌入式应用环境资源受限和空间连接精炼步骤高代价的特点,提出了一个寻找空间连接过程中最佳的数据页调度序列的新算法,即搜索最好的N-释放-K序列,理论上它能够最小化磁盘I/O代价,并详细描述了该算法的实现思路与过程.(7)针对本文讨论的部分主要内容与算法分别进行了实验,包括:原型系统、EDBMS的空间数据类型和空间算子扩展实验、ESDBMS的三级空间索引性能实验、OPAS新算法性能实验,证明了本文论述内容的正确性和可行性.
- 作者:
- 马亚明
- 学位授予单位:
- 解放军信息工程大学
- 专业名称:
- 地图制图学与地理信息工程
- 授予学位:
- 博士
- 学位年度:
- 2011年
- 导师姓名:
- 华一新
- 中图分类号:
- P208
- 关键词:
- 嵌入式;空间数据库管理系统;体系结构;空间数据库模型;空间算子;动态扩展存储结构;三级空间索引;空间查询优化;空间连接;页访问调度序列
- Embedded;Spatial Database Management System;Architecture;Spatial Database Model;Spatial Operator;3 Level Spatial Index;Spatial Query Optimizing;Spatial Join;Page Access Scheduling Sequence