下载文档原格式
基于时间变元绑定的双时态索引模型研究李晓林;刘莉【摘要】在基于点方法的双时态索引算法基础上,引入了时间变元绑定的形式化描述,扩充了其索引的双时态数据,使由于时间变元绑定而导致数据错误的双时态索引问题得以解决,给出了相应的数据变换和查询变换模型,并指出了其实现方式.【期刊名称】《武汉工程大学学报》【年(卷),期】2008(030)002【总页数】4页(P98-101)【关键词】双时态索引;时间变元绑定;数据变换;查询变换【作者】李晓林;刘莉【作者单位】武汉工程大学计算机科学与工程学院,湖北,武汉,430074;武汉工程大学计算机科学与工程学院,湖北,武汉,430074【正文语种】中文【中图分类】TP3110 引言双时态数据库是在传统的数据库基础上加上有效时间和事务时间维的时态数据库，它既保存了数据库变迁的历史，又保存了现实世界的真实的数据属性.然而双时态数据库中的数据容量也是海量的，如果没有有效的数据管理方法，双时态数据的时态信息优势将被超大的数据访问代价所抵消.因此如何快速访问到时间数据是时态数据库中的一个重要研究课题.几种主要的双时态索引技术有R-tree系列空间索引、GR-tree(Generalize R tree)和4R-tree[1]索引技术.R-tree系列空间索引因为不能有效解决带有效时间变元NOW和事务时间变元UC的双时态数据情况，所以并不能直接用于索引双时态数据.而GR-tree虽然能有效的处理含时间变元NOW和UC的双时态数据，又可以处理一般的双时态数据，但其算法的实现还有待于现有DBMS内核的扩展.4R-tree的索引效果与GR-tree相当，该方法实现方式可分为：基于支持R-tree索引的DBMS和基于不支持R-tree索引的DBMS[2](即借助时态中间件)，但两种实现方式都需要一个在4棵R-tree之上的实现层来执行其插入、删除和查询算法.文献[3]提出了一种基于点的双时态索引算法，这种算法不仅继承了R*-tree的优点，又能有效的索引含时间变元的双时态数据，更有实验证明该算法在磁盘I/O访问次数和CPU使用率的性能上高出最大时间戳R*-tree(利用可能时间的最大值来代替事务和有效时间的不确定值)的20倍以上.但是这种算法不足之处在于：只能索引满足Vt→<Vt←，Tt→<Tt←条件的双时态数据，但是现实中满足Vt→=Vt←或Tt→=Tt←条件的双时态数据也是广泛存在的，例如教师工资系统中，李明从2007的7月份起职称由讲师升为副教授，工资也从原来的1 300涨到1 700，这时在教师工资数据库中插入元组(李明，副教授，1 700，2007-07，Now，2007-09-18，UC)表示这条信息，但随后马上发现李明的工资是从6月份调整的，数据库中会用(李明，副教授，1 700，2007-07，Now，2007-09-18，2007-09-18)、(李明，副教授，1 700，2007-06，Now，2007-09-18，UC)两个元组来表示这次的修改，其中前一条记录表示原来信息的删除，后一条表示目前的状况，如果在原算法中发现这种数据，势必导致索引错误.为了使此算法更具一般性，本文在原有算法的基础上引入了时态变元绑定形式化描述，扩充了索引的双时态数据类型，并改进了相应的索引模型，最后说明了其实现方式并给出了下一步研究的方向与任务.1 时间变元绑定1.1 双时态数据类型双时态数据有两个时间维组成：有效时间(Valid Time)和事务时间(Transaction Time)[4]，有效时间指的是指一个对象(事件)在现实世界中发生并保持的那段时间，或者该对象在现实世界中为真的时间.事务时间是指一个数据库对象进行操作的时间，是一个事实储存在数据库中的时间，它记录着对数据库修改和更新的各种操作对应于现有事务或现有数据库状态变迁的历史.目前使用比较广泛是TQuel的四个时间戳模式：(Vt→，Vt←，Tt→，Tt←)[5]，它们分别表示有效时间的起始、终止时间和事务时间的起始、终止时间.当有效时间的终止值不确定的时候，可以用Now来表示有效时间的终止，而事务时间的终止值不确定时，就用UC来表示事务时间的终止，且双时态数据的时态约束条件为：Vt→≤Vt←，Tt→≤Tt←且Tt→≤CT(Current Time).根据有效时间和事务时间的终止值是否为不确定值，按四个时间戳为坐标围成的双时态域可将双时态数据分为固定矩形、增长矩形、固定楼梯形和增长楼梯形四种类型.1.2 时间区间绑定时间区间根据是否含有变元Now可分为：Now时间区间和Ground时间区间[6，7]，前者表示时间区间中含有时间变元Now；后者表示时间区间中不含有时间变元.下面时间区间绑定的定义中要用到一种特殊的时间：参考时间(Reference Time 简称Rt)，它是指时态数据库中的用户观察数据库的时间，可有多种选择.定义1 设时间区间I=[t1，t2]，则时间区间的绑定如下：(1)由式(1)可见，对于Ground时间区间的绑定是没有改变原来的时间凸区间的，而Now时间区间的绑定是将Now用参考时间取代即可.本文时间变元Now绑定是采用了用户观察数据库的时间即Rt是等于时间区间的上限的.如下式：式中t2=Now.那么绑定后双时态域对应的变换为固定矩形、平行于Vt轴的线段、平行于Tt轴的线段和点.在固定矩形这种双时态数据类型中，由于Vt→=Vt←或Tt→=Tt←，存在一种退化了固定矩形，其双时态域表现为点、平行于Vt轴的线段或则平行于Tt轴的线段.并且经过时间区间的绑定，其双时态域不变，那么这些特殊的固定矩形势必跟其他几种双时态数据类型发生混乱，造成索引错误.解决这个问题的最简单有效的方法就是引入一个变量来记录时间变元绑定前的双时态数据类型.2 双时态数据变换以上描述了时态变元绑定的思想，下面给出其形式化、规范化定义.首先给出双时态数据的定义，然后给出双时态数据变换的函数.定义2 已知时间点域T，元组指针域为ID，具有变元的双时态数据DCT和基于点的双时态域Dpoint的定义如下：DCT≌ {〈Vt→，Vt←，Tt→，Tt←，id〉∈T×(T∪{Now})×T×(T∪{UC})×ID|(Vt←=Now∨Vt→≤Vt←)∧(Tt←=UC∨Tt→≤Tt←)}(2)Dpoint≌ {〈Vt→，Vt←，Tt→，Tt←，id〉∈T×T×T×T×ID|(Vt→≤Vt←)∧(Tt→≤Tt←)}(3)式(2)中双时态域DCT含有时间变元Now和UC，而Dpoint是不含时间变元的.下面介绍从双时态域DCT到不含时间变元Dpoint的数据变换函数.定义3 令r∈DCT，类型Type={1，2，3，4}，那么从双时态域DCT到不含时间变元Dpoint的数据变换函数为：f∶DCT→Dpiont×Typef(r)=f(〈Vt→，Vt←，Tt→，Tt←，id〉)=由数据变换函数的定义可知，f是双射函数，其中Type中的元素是用于记录数据变换函数中原像的数据类型.3 查询变换及其实现方式数据变换后，在变换后的数据域上的查询也要经过一定的变换才能操作.时态查询语言主要包括时间点的查询和时间区间的查询，所以查询变换分为基于时间点的查询变换和基于时间区间的查询变换.3.1 基于时间点的查询变换时间点的查询可以分为三种[8，9]，其一是查找当前概念中世界的当前状态，记为Q1；第二种是查找当前概念中世界的过去状态，记为Q2；第三种是查找以往概念中关于世界的过去状态，记为Q3.如图1所示.图1 点查询的分类：Q1、Q2和Q3Fig.1 Timeslice queries Q1、Q2 and Q3 由图1可知，Q1选择查询有效时间区间与Now相交且事务时间到Now的元组.因此在DCT中Q1选择元组所要满足查询条件为：(Vt→≤Now∧Vt←≥Now)∧(Tt→≤Tt←∧Tt←=UC)在基于时间变元绑定的双时态数据存储中，由于当t2=Now∨UC，替换过来元组所要满足的查询条件为：[(Vt→ ≤CT∧Vt←>CT)∧Tt←=Tt→∧GetType()=3]∨[(Vt→≤CT∧Vt←=Vt→)∧Tt←=Tt→∧GetType()=1](4)由式(4)中的Tt←=Tt→可知，搜索元组在Dpoint中表现为点和线，且该点是位于区域(0，Now，0，Now)内的，线是平行于Vt轴并与Vt=CT相交的.其中GetType()函数是用来确认点和线是由含变元双时态域中的增长楼梯形和增长矩形变换而来.而Q2选择查询的是有效时间包括过去的某个时间点h且事务时间到Now的元组.因此在DCT中Q2选择元组所要满足的查询条件为：(Vt→≤h∧Vt←≥h)∧(Tt→≤Tt←∧Tt←=UC)在基于时间变元绑定的双时态数据存储中，由于当t2=Now∨Uc，替换过来元组所要满足的查询条件为：[(Vt→ ≤h∧Vt←≥h)∧Tt←=Tt→∧GetType()=3]∨[(Vt→≤h∧Vt←=Vt→)∧Tt←=Tt→∧GetType()=1](5)由式(5)中的Tt←=Tt→可知，搜索元组在不含变元的双时态域中表现为点和线，且该点是位于区域(0，Now，0，h)内的，线是平行于Vt轴并与Vt=h相交的.其中GetType()函数是用来确认点和线是由含变元双时态域中的增长楼梯形和增长矩形变换而来.而Q3选择查询有效时间区间包括过去的某个时间点h 1且事务时间区间也包括过去的某个时间点h 2的元组.因此在DCT中Q3选择元组所要满足的查询条件为：(Vt→≤h 1∧Vt←≥h 2)∧(Tt→≤h 2∧Tt←≥h 2)在基于时间变元绑定的双时态数据存储中，由于当t2=Now∨UC，替换过来元组所要满足的查询条件为：[(Vt→≤h 1∧Vt←≥h 1)∧(Tt→≤h 2∧Tt←≥h 2)∧GetType()=4]∨[(Vt→≤h 1∧Vt←≥h 1)∧(Tt→≤h 2∧Tt←=Tt→)∧GetType()=3]∨[(Vt→≤h 1∧Vt←=Vt→)∧(Tt≤h 2∧Tt←≥h 2)∧GetType()=2]∨[(Vt→≤h 1∧Vt←=Vt→)∧(Tt→≤h 2∧Tt←=Tt→)∧GetType()=1](6)由式(6)可知，搜索元组在Dpoint中囊括了所有类型，其中点是位于区域(0，h 2，0，h 1)内的，线是平行于Tt轴且与Tt=h 2相交的或平行于Vt轴并与Vt=h 1相交，而搜索元组对应的矩形是与点(h 2，h 1)相交的.3.2 基于时间区间的查询变换区间查询是指对有效时间和事务时间范围的查询，通常也称为矩形交叉查询.元组表示相交查询域，其中T表示时间域，查询条件为且在DCT中区间查询的条件是：由文献[10]的双时态数据上的相交查询结果的定义，可以知道区间查询变换到Dpoint上应满足的查询条件为：[(Vt→∨[(Vt→≤V∧Vt←≥V)∧(Tt→≤T∧Tt←=Tt→)∧GetType()=3]∨[(Vt→≤V∧Vt←=Vt→)∧(Tt→≤T∧Tt←≥T)∧GetType()=2]∨[(Vt→≤V∧Vt←=Vt→)∧(Tt→≤T∧Tt←=Tt→)∧GetType()=1](7)式(7)中搜索元组在Dpoint中表现为位于区域内的点、平行于Tt轴并与区域相交的线段、平行于Vt轴并与区域相交的线段和与相交矩形.3.3 实现方式进行查询变换后，双时态数据域不存在增长楼梯形和增长矩形这些不规则形状，因此可以直接支持基于R-tree索引的DBMS.譬如本模型可以直接利用Oracle Spatial来完成对含时态变元的双时态数据的管理.这样不仅可以继承了Oracle Spatial提供的R*-tree索引的优点，有效的解决了索引带有效时间变元NOW和事务时间变元UC的双时态数据情况，并且与GR-tree和4R-tree相比，本算法只需要在现有的空间索引技术上进行逻辑的查询变化即可，而不需要对现在的DBMS内核进行扩展.4 结语对文献[3]模型的一种改进方法，主要解决了当录入数据库中的数据由于某种原因发生错误后及时更正的双时态数据索引问题.此外还需要对模型做进一步研究，下一步的研究工作有两点：(1)将有效时间变元Now和事务时间变元UC分别进行绑定，研究处理时间变元的最合理算法.(2)将时态变元绑定从数据变换函数中独立出来，方便修改Now的绑定参考时间以适应不同的需求.参考文献：[1]Bliujute. R，Jensen C S，Saltenis S，et al. R-Tree Based Indexing of Now-Relative Bitemporal Data[A]. Proceedings of 24rd International Conference on Very Large DataBases(VLDB’98)[C].New York： MorganKaufmann Publishers，1998，345-356.[2]康向锋，汤庸，叶小平，等.一种基于时态中间件的高效双时态索引模型[J].计算机科学，2005，32(9)：91-95.[3]Stantic. B，Khanna.S，&Thornton.J. An Efficient Method for Indexing Now-Relative Bitemporal Data[A]. Klaus-Dieter Schewe and Hugh E. Williams，Proceedings of the 15th Australasian database conference[C]. Dunedin New Zealand.：Australian Computer Society， 2004，113-122.. [4]汤庸，汤娜，叶小平.时态信息处理技术研究综述[J].中山大学学报(自然科学版)，2003，42(4)：5-9.[5]Snodgrass R T. Temporal Database[J].IEEE Computer，1986，19(9)：35-42.[6]王路帮，叶小平，邢鸿雁，等.时间变元now的绑定算法[J].中山大学学报(自然科学版)，2004，43(增刊)：152-154.[7]王路帮.时态数据库中的时间变元及其绑定[J].浙江大学学报(理学版)，2006，33(6)：662-666.[8]Torp K，Jensen C S，Snodgrass R T. Stratum Approaches to Temporal DBMS Implementation[A]. Proceedings of the 1998 International Symposium on Database Engineering & Applications[C].Cardiff Wales：IEEE Computer Society，1998，4-13.[9]Stantic B， Thornton J， Sattar A. A Novel Approach to Model Now in Temporal DataBase[A]. 10th International Symposium on Temporal Representation and Reasoning and Fourth International Conference on Temporal Logic(TIME-ICTL2003)[C].cairns Australia：IEEE Computer Society，2003，174-180.[10]汤庸.时态数据库导论[M].北京：北京大学出版社，2004，139-144.。
—42—基于Quadtree 和Hash 表的移动对象全时态索引李 东，彭宇辉，殷江龙(华南理工大学计算机科学与工程学院，广州 510640)摘 要：为解决大量移动对象位置频繁更新所带来的性能下降问题，提出一种基于改进的Quadtree 和Hash 表的QH 全时态索引结构。
这种新的索引结构可以支持移动对象全时态索引，在Hash 表中通过存储移动对象指针来支持移动对象标识查询，并对Quadtree 的叶子节点采用适时合并的方法来防范分支太深而造成的查询效率低下。
实验证明，QH 索引与TPR-tree 相比，移动对象的更新效率更高、对象标识查询较优、范围查询性能相近。
关键词：移动对象；索引结构；范围查询Past, Current and Future Positions Index of Moving ObjectBased on Quadtree and Hash TableLI Dong, PENG Yu-hui, YIN Jiang-long(Institute of Computer Science and Engineering, South China University of Technology, Guangzhou 510640)【Abstract 】Traditional index structures do not work well on moving objects because of the need of frequently updating the index which leads to the poor performance. This paper presents a novel indexing structure based on Quadtree and Hash table, namely the QH-index which can index the past, present and future positions of moving object and can support moving object’s range queries and point queries which include the object identifier based query. Merging timely the corresponding nodes to degrade the depth of the tree can guarantee the query efficiency. Experiments show that the QH-index gains much better performance in updating and in querying by the object identifier than those of the TPR-tree, and the efficiency of range query is no less than that of TPR-tree.【Key words 】moving object; index structure; range query计 算 机 工 程 Computer Engineering 第35卷 第7期ol.35 No.7 2009年4月A V pril 2009术与数据库· 文章编号：1000—3428(2009)07—0042—04文献标识码：A中图分类号：TP311·软件技1 概述由于移动对象不断地产生大量的时空信息，因此如何有效地管理这些动态信息一直是被广泛关注的研究课题。
索引类型和索引方法索引类型和索引方法是数据库中用于提高查询效率和数据存储的技术。
在数据库中，索引是指在列或者多个列上创建的特殊结构，用来加快数据的检索速度。
本文将详细介绍索引类型和索引方法，包括它们的定义、分类和使用方法。
1.索引类型索引类型是指在数据库中创建索引所使用的算法或结构。
不同的索引类型适用于不同的场景，常见的索引类型包括：1.1B树索引：B树索引是最常用的索引类型之一，通常用于关系型数据库中。
B树索引通过使用二叉树的结构，在每个节点上存储多个索引值，以便快速地定位数据。
B树索引适合于范围查询和精确查找，但是在更新和插入数据时需要维护索引结构，会影响性能。
1.2哈希索引：哈希索引将索引列的值通过哈希函数计算得到索引值，然后将索引值与数据的地址关联存储。
哈希索引适合于等值查询，因为它可以直接计算出需要查找的数据的地址，查询速度非常快。
但是，哈希索引不支持范围查询，而且在数据量变化时需要重新计算哈希函数。
1.3全文索引：全文索引通常用于文本内容的，比如文章、邮件和网页等。
全文索引将文本内容进行分词，并建立索引表，以便用户可以根据关键词快速定位到相关的文本。
全文索引需要消耗较大的存储空间，并且需要进行词典、分词等复杂操作。
1.4空间索引：空间索引用于地理位置相关的数据查询，如地图、位置坐标等。
空间索引将地理位置数据以树状结构组织存储，并提供了丰富的地理位置查询功能，如范围查询、最近邻查询等。
空间索引的建立和查询需要使用专门的地理位置算法和数据结构。
2.索引方法索引方法是指在具体的数据库系统中，根据索引类型实现的具体算法和策略。
常见的索引方法包括：2.1顺序扫描：顺序扫描是最简单的索引方法，它直接遍历数据表的每一行，并进行逐一比对。
顺序扫描的优点是实现简单，不需要额外的索引结构，但是在大数据量的情况下会降低查询效率。
2.2二分查找：二分查找是一种快速查找算法，适用于有序数据表和B树索引。
在二分查找中，通过比较要查找的值与中间值的大小关系，从而将查找范围逐步缩小到目标值。
index方法Index法（也称作索引方法），是一种利用符号来组织数据的技术，它可以提高存取数据的效率。
在计算机中，索引方式可用于快速地检索和保存相关信息，所以被广泛应用于搜索引擎索引，数据库索引，文档索引等等。
索引的主要作用就是让搜索或读取的工作变得更加简单快捷，在一大堆的信息中，能够快速准确的找到需要的部分。
一般情况下，索引的建立需要大量的时间和空间，但是却可以提高读取时的效率。
索引方法有众多的分类，其中最常用的索引方法包括：哈希索引、全文索引、B索引和 R索引等等。
哈希索引（Hash Index）是一种分布式的索引方法，它将存储在文件中的数据依据特定的函数转换成另外一种存储形式，以便更快速的检索所需要的信息。
它可以使查询由慢变快，而且在大数据量的情况下也有良好的扩展性。
全文索引（Full Text Index）也是一种索引方法，它可以对文本文档中的关键字进行索引，从而更快的搜索出需要的信息。
通常情况下，如果文档比较大，就会需要使用全文索引，以节省时间。
B索引（B-Tree Index）是一种高效率的索引方法，它以“B”的结构存储字符系数，并利用“B”的层次结构来分类和检索数据，从而提高对大量的数据的检索效率。
R索引（R-Tree Index）是一种被广泛使用的空间索引方法，它可以更有效的检索出空间中的数据，比如地图数据等等。
它的主要优势在于，它可以非常快速的检索出空间范围内的数据，比如搜索一个指定范围内的房源信息等等。
Index法在计算机领域有着广泛的应用，它可以让我们更快速的检索出需要的信息，同时还可以提高文件的存取效率，节省大量的空间和耗费的时间。
不过，Index法也有其局限性，有时候如果不熟悉某个特定索引方法，或者缺乏对索引方法的理解，就可能遇到很多问题，从而影响应用的效率。
总之，Index法是一项重要的技术，它可以提高检索信息和存取文件的效率，因此被广泛应用于计算机领域。
需要注意的是，Index 法也有其局限性，理解掌握基本的 Index法非常重要，以便在实践中有效的应用。
