一种改进的概率数据库模型及其概率最近邻居查询问题研究

摘要

在目前的信息时代里，不确定数据的地位和作用越来越大。虽然传统的关系数据库模型具有灵活存取、逻辑结构和物理结构相对独立等众多优点，但它无法处理这些不完整的、不确定的数据。为了处理这些数据，1996年Dev和Sarkalar提出了一种概率数据模式以及概率数据库模型，但是这种概率数据模式和概率数据库模型存在着诸多缺点，因此我们需要扩展传统关系数据模式，处理概率方面的不确定性数据，以描述动态的世界，建立一个新型的概率数据模式——PDS(Probabilistic Data Schema)概率数据模式。 我们在PDS概率数据模式中引进对象属性、静态属性、动态属性和概率属性概念，并提出由上述属性联合构成元组；在此基础上定义了该模型中元组演算的一些基本操作，从而形成了PDS概率数据库理论体系，使其具有处理不确定数据的能力。 概率数据库中存储移动对象，R树索引是目前最实用的移动对象索引机制，但是由于R树索引的查找以及更新性能低下，因此我们建立了一个R树索引和Hash索引相结合的混合结构——PRI(Probabilistic R-Tree Index)树索引结构。性能分析表明，采用PRI树索引结构的动态更新性能大大高于R树索引。 不确定性是传感器数据库中的常见问题，而如何准确查询不确定数据是当前研究的热点。概率最近邻居查询能够描述不确定数据，概率最近邻居查询能够准确描述不确定数据，本文提出了基于分支界限的概率最近邻居算法和基于Delatmay三角化的概率最近邻居查询算法，并分别给出两种算法的性能分析。

目录

文摘

英文文摘

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

第1章绪论

1.1课题的研究背景

1.2国内外研究现状

1.2.1概率数据模式和概率数据库模型

1.2.2移动对象索引结构

1.2.3最近邻居查询和概率最近邻居查询

1.3课题的研究目标、研究内容和创新点

1.4本文的结构

第2章概率数据模式

2.1不确定数据

2.2概率理论基础

2.3常见的概率数据模式

2.3.1 Barbara，Garcia-Molina，Porter框架([BGP]框架)

2.3.2 Dey，Sarkar框架([DS]框架)

2.3.3 ProbView框架

2.4本章小结

第3章PDS概率数据库模型及应用

3.1 PDS概率数据模式

3.2 PDS概率数据库模型

3.3 PDS概率数据库模型关系运算

3.3.1合并操作

3.3.2概率选择、概率投影、概率连接

3.3.3并、交、差运算

3.4 PDS概率数据库模型的应用

3.4.1数据库更新

3.4.2数据库查询

3.5本章小结

第4章一种混合的索引结构——PRI树

4.1 R树

4.1.1 R树的逻辑结构

4.1.2 R树的查找算法

4.1.3 R树的动态维护

4.2一种混合的索引结构|——PRI

4.2.1 PRI树的逻辑结构

4.2.2 PRI树的查找算法

4.2.3 PRI树的动态维护

4.3本章小结

第5章概率最近邻居查询算法及其改进

5.1最近邻居问题

5.2不确定数据以及概率最近邻居问题

5.3基于分支界限算法

5.3.1记载阶段

5.3.2剪枝阶段

5.3.3分支界限阶段

5.4基于Delaunay三角化算法

5.4.1 Delaunay三角化理论基础

5.4.2基于Delaunay三角化算法

5.5性能分析

5.5.1基于分支界限算法

5.5.2基于Delaunay三角化算法

5.6本章小结

第6章总结与展望

6.1全文总结

6.2研究展望

参考文献

致谢

攻读学位期间发表的学术论文目录