多维数据及时态数据索引研究

摘要

随着计算机科学的发展和计算机应用的广泛化，计算机中处理的数据越来越复杂。相应地对各种复杂数据的处理也成为了计算机科学中的热点问题。在复杂数据中多维数据类型和时态数据类型的应用非常广泛。多维数据可以分为两类，一类是其本身意义是多维的，比如空间数据；另一类虽然本身并不是多维的，但是在实际应用中把它看做多维处理却更加自然和方便。多维数据的应用必将随着应用的深入越来越广泛。时态数据广义上也可看作是一类多维数据，但是时态数据有其自身的特点，比如独有的时态变元等。时态数据在电子政务，证卷，银行，保险等多个商业领域都有重要意义。而现有商业数据库中的关系数据索引并不适应多维数据和时态数据的存取，从而使得多维数据和时态数据的索引研究具有理论和应用价值。 本文对多维索引和时态索引进行了深入研究，其主要贡献如下： ●本文系统地综述了现有多维索引的研究状况，并通过分析主要多维索引的特点和不足之处，提出了一种新的多维点索引：DHPR—Tree。其基本结构基于R*—Tree，通过兄弟叶节点均匀机制增加了整个索引的负载，延缓了叶节点的分裂；通过叶节点动态重构机制有效减少了叶节点层乃至整个索引结构的重叠区域；通过引入并改进虚拟外包矩形的概念，大大增加了节点的扇出；还通过引入动态有效维机制大大减少了多维下节点内的冗余信息，进一步提高了节点特别是高层节点多维情况下的扇出。 ●本文给出了DHPR—Tree详细的查询算法和更新算法，并给出算法解释和流程图，对其中复杂的算法还给出了例子。然后为多维数据设计了系统详细的实验，通过大量实验，可以证明DHPR—Tree在多种分布的数据中都能保持范围查询和点查询的高效性，并且结构紧凑，物理利用率高，同时其维护代价仍然是可控制的。 ●本文给出了一个时间期间集合上的数学框架。本文基于时间期间的内在特性，研究了时间期间集合上的数学关系，提出了时态等价关系和时态拟序关系，由此引出了时间期间集合上的时态线序和时态线序划分的概念，并提出了两种对于索引结构非常有意义的划分方法，即最小线序划分和最长线序划分。还分别给出了得到这两种线序划分的算法，其正确性证明和时间复杂度分析。 ●本文对时态数据及时态索引进行了研究。针对传统关系模型表达能力不足，不适合时态数据的缺陷，本文将时态信息结合到面向对象数据模型。本文通过分析时态对象数据的特点，提出了时态对象数据模型Toqdm，并在时态对象数据模型和其时态类图的基础上，通过对时间期间集合上时态等价关系的应用，得到了时态数据摘要Tosum。然后结合时态数据摘要和时间期间集合上的线序划分算法，提出了时态对象索引Todim，并给出了其查询和更新算法。最后通过仿真实验和基本评估表明了所提出时态对象索引的可行性和有效性。

目录

文摘

英文文摘

声明

第1章 引言

1.1研究背景和意义

1.2研究内容和创新点

1.3本文的结构

第2章 索引技术理论基础

2.1索引概述

2.1.1索引的作用

2.1.2索引的结构

2.1.3索引度量标准

2.2几种主要索引介绍

2.2.1 B+-Tree索引

2.2.2 Hash索引

2.2.3 位图索引

2.3主要索引分类

2.3.1按键值有序与否分类

2.3.2按聚簇与否分类

2.3.3按稠密与否分类

2.3.4按同时索引键值数量分类

2.3.5索引分类图

第3章 基于R*-Tree的多维点索引DHPR-Tree的设计

3.1多维索引研究概述

3.2多维点索引DHPR-Tree的提出

3.3 DHPR-Tree的分析与设计

3.3.1增加节点扇出

3.3.2减小节点MBR重叠面积

3.3.3增加索引物理利用率

3.4 DHPR-Tree的静态结构

3.4.1定义索引结构

3.4.2扩充有效维概念

3.5 DHPR-Tree的动态特性

3.5.1 mbr和vbr的转换

3.5.2节点有效维动态计算方法

3.5.3节点扇出动态计算方法

3.6小结

第4章 DHPR-Tree的实现与验证

4.1 DHPR-Tree的查询算法

4.2 DHPR-Tree的插入算法

4.3实验设计

4.3.1实验设置

4.3.2实验数据及其产生

4.3.3查询及其产生

4.3.4产生数据时的考虑

4.4实验结果与分析

4.4.1二维实验结果及分析

4.4.2多维实验结果及分析

4.5小结

第5章 时态对象数据索引研究

5.1时态索引研究概述

5.1.1按照索引时间方法分类

5.1.2按照索引时间类型分类

5.1.3按照索引数据模型分类

5.2时态对象数据模型

5.2.1时态类与时态类图

5.2.2时态对象数据模型

5.2.3时态对象数据摘要

5.3时态对象索引模型

5.3.1时态线序矩阵

5.3.2时态线序划分

5.3.3时态对象索引模型

5.4时态对象数据操作

5.4.1时态数据查询

5.4.2时态索引更新

5.5实验及分析

5.5.1实验环境与基本数据

5.5.2仿真结果与基本评估

5.6小结

第6章 结束语

参考文献

附 录：攻读博士学位期间发表的论文和著作

致 谢