面向移动区域的移动对象数据库研究

论文摘要

移动对象数据库是管理移动点和移动区域的位置和范围的复杂系统。当前涉及移动区域的时空应用(火灾模拟、海啸监控等)越来越多,然而移动对象数据库研究多集中于移动对象位置管理,因此迫切需要针对移动区域的移动对象数据库进行深入的研究。本论文针对面向移动区域的移动对象数据库关键问题进行了系统深入的研究。论文首先系统研究了移动对象的时空语义。时空语义是构建数据模型乃至整个移动对象数据库的基础。首先对时空变化进行了系统分类,提出了一套完备的时空变化描述方法,该方法以对象标识和描述符为基础,通过对象级时空变化和属性级时空变化来描述时空变化。其中对象级时空变化是显式的,而属性级时空变化是隐式的。在时空语义研究的基础上,我们提出了新的基于抽象数据类型和约束数据库理论的对象关系数据模型——网格划分模型(Grid Partition Model,GPM)。GPM以时空关系和时空元组来表示移动对象,以扩充的关系代数操作作为时空关系的查询操作。移动对象的时空数据和时空变化以时空数据类型和演化拓扑类型来表示,时空数据和时空变化的查询则通过这些类型上的操作来实现。论文详细讨论了GPM模型的数据结构、查询操作和语言以及GPM使用单元网格对移动区域复杂外形进行建模的算法,并提供了模型参数用于表示建模的精度。模拟实验验证了该建模方法的有效性。为了支持基于GPM的时空查询,论文针对基于TPR树的预测时空查询提出了时空选择查询和连接查询的代价模型,用于预测查询的磁盘访问代价。这些代价的计算仅与数据集以及TPR自身的设置参数相关,而与实际TPR树底层的数据分布和结构无关,从而简化了代价的计算。在不同规模模拟数据集上的实验表明,这些代价模型能够有效预测时空查询在TPR上执行时的访问代价。在上述代价模型的基础上,本文提出了一种基于TPR树和grid file索引结构的混合索引方法,并分析了各自的预测时空查询代价。移动区域模拟数据集上的实验和分析表明其中一种混合索引结构在查询性能上明显优于已有的单独索引结构,能够有效支持移动区域的预测时空查询。在GPM模型和时空查询研究的基础上,本论文提出了移动对象数据库管理系统的原型实现方案,并在对象关系数据库管理系统上实现了原型系统。为了实现复杂的空间操作,文中提出了基于逆时针有向三角形的空间操作实现方法,并给出了各种移动区域空间操作的实现算法。论文进一步分析了在开源PostgreSQL数据库上实现基于GPM的移动对象数据库管理系统的数据处理流程,表明GPM模型是易于实现的。与已有的研究相比较,本文的新贡献在于:(1)针对面向移动区域的移动对象数据库,提出了一套系统完备的研究方法和实现框架,包括:时空语义、数据模型和建模方法、时空查询和索引方法以及数据库实现原型。弥补了已有研究工作中的缺失。(2)提出了一种显式的对象级时空变化与隐式的属性级时空变化相结合的时空语义描述方法,克服了已有研究缺乏完备性的缺点(缺少对主题属性连续变化的研究),从理论上保证了时空变化的完备性描述。(3)提出了一个新的基于抽象数据类型和约束数据库理论的数据模型GPM。GPM可以有效表示和查询移动区域和移动点的各种时空变化,可以使用类型扩展的方法顺利地转换到对象关系数据库管理系统上实现,解决了已有数据模型难以实现的困难。GPM创新性的利用单元网格获取移动区域的离散和连续表示。(4)提出了针对预测时空查询的代价分析模型以及混合索引结构,弥补了目前移动对象数据库研究中的空白。(5)提出了针对移动区域建模的实现原型,改进了基于逆时针有向三角形的空间操作实现方法。该方法可以有效地实现各种复杂空间操作,避免了直接基于顶点坐标计算各种空间操作的值时对效率的影响。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景
• 1.1.1 空间数据库
• 1.1.2 时态数据库
• 1.1.3 移动对象数据库
• 1.2 移动对象数据库研究现状
• 1.2.1 移动对象建模和数据模型
• 1.2.2 索引方法和查询处理
• 1.2.3 精确性和不确定性管理
• 1.2.4 实现原型
• 1.2.5 新方向和存在的问题
• 1.3 论文概述
• 1.4 论文的组织
• 第2章 移动对象的时空语义
• 2.1 引言
• 2.2 时空变化的类型
• 2.3 移动区域的时空变化
• 2.4 一种时空变化的形式化表示方法
• 2.4.1 对象级时空变化
• 2.4.2 属性级时空变化
• 2.4.2.1 空间描述符
• 2.4.2.2 主题属性描述符
• 2.4.3 移动对象和时空变化的形式化表示
• 2.5 小结
• 第3章 移动区域的建模和查询
• 3.1 引言
• 3.2 移动区域的建模需求
• 3.3 网格划分模型
• 3.3.1 数据类型和操作
• 3.3.1.1 空间数据类型和操作
• 3.3.1.2 时态数据类型和操作
• 3.3.1.3 时空数据类型和操作
• 3.3.1.4 连续基本数据类型和操作
• 3.3.1.5 演化拓扑类型和操作
• 3.3.1.6 类型系统综述
• 3.3.2 时空联系
• 3.3.2.1 离散时空联系
• 3.3.2.2 连续时空联系
• 3.3.3 模型实现
• 3.3.3.1 移动区域的建模
• 3.3.3.2 数据结构和算法
• 3.4 查询类型和语言
• 3.4.1 查询操作和查询类型
• 3.4.2 查询语言
• 3.5 实验评估
• 3.5.1 实验设置
• 3.5.2 结果分析
• 3.6 小结
• 第4章 时空查询的代价模型和索引结构
• 4.1 引言
• 4.2 一种预测时空查询的代价模型
• 4.2.1 相关工作
• 4.2.2 代价分析模型
• 4.2.3 实验评估
• 4.3 一种针对移动区域的混合索引结构
• 4.3.1 相关工作
• 4.3.2 基于TPR树和网格索引的混合索引结构
• 4.3.3 实验评估
• 4.4 小结
• 第5章 移动对象数据库实现原型
• 5.1 引言
• 5.2 传统时空数据库系统实现结构概述
• 5.2.1 完全型实现结构
• 5.2.2 层次型实现结构
• 5.2.3 扩展型实现结构
• 5.3 一种移动对象数据库实现原型
• 5.3.1 实现体系结构
• 5.3.2 原型实现细节
• 5.3.3 实验评估
• 5.4 小结
• 第6章 结束语
• 6.1 论文工作总结
• 6.2 未来工作展望
• 参考文献
• 攻读博士学位期间发表的学术论文
• 致谢