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