《武汉工程大学学报》  2008年02期 98-101   出版日期：2008-02-28   ISSN:1674-2869   CN:42-1779/TQ

---

基于时间变元绑定的双时态索引模型研究


0引言双时态数据库是在传统的数据库基础上加上有效时间和事务时间维的时态数据库，它既保存了数据库变迁的历史，又保存了现实世界的真实的数据属性.然而双时态数据库中的数据容量也是海量的，如果没有有效的数据管理方法，双时态数据的时态信息优势将被超大的数据访问代价所抵消.因此如何快速访问到时间数据是时态数据库中的一个重要研究课题.几种主要的双时态索引技术有Ｒtree系列空间索引、GRtree（Generalize R tree）和4Rtree［1］索引技术.Ｒ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），它是指时态数据库中的用户观察数据库的时间，可有多种选择.第2期李晓林，等：基于时间变元绑定的双时态索引模型研究
武汉工程大学学报第30卷
定义1设时间区间I=［t1，t2］，则时间区间的绑定如下：
IbindRt=［t1，t2］bindRt=［tbind1Rt，tbind2Rt］=
［t1，t2］当为Ground时间凸区间时
［t1，Rt］当为Now时间凸区间时（1）由式（1）可见，对于Ground时间区间的绑定是没有改变原来的时间凸区间的，而Now时间区间的绑定是将Now用参考时间取代即可.本文时间变元Now绑定是采用了用户观察数据库的时间即Rt是等于时间区间的上限的.如下式：IbindRt=［t1，t2］bindRt=［tbind1Rt，tbind2Rt］=［t1，t1］
式中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×Type
f（r）=f（〈Vt→，Vt←，Tt→，Tt←，id〉）=
〈Vt→，Vt→，Tt→，Tt→，id，1〉ifVt←=Now∧Tt←=UC
〈Vt→，Vt→，Tt→，Tt←，id，2〉ifVt←=Now∧Tt←≠UC
〈Vt→，Vt←，Tt→，Tt→，id，3〉ifVt←≠Now∧Tt←=UC
〈Vt→，Vt←，Tt→，Tt←，id，4〉ifVt←≠Now∧Tt←≠UC由数据变换函数的定义可知，f是双射函数，其中Type中的元素是用于记录数据变换函数中原像的数据类型.3查询变换及其实现方式数据变换后，在变换后的数据域上的查询也要经过一定的变换才能操作.时态查询语言主要包括时间点的查询和时间区间的查询，所以查询变换分为基于时间点的查询变换和基于时间区间的查询变换.3.1基于时间点的查询变换时间点的查询可以分为三种［8，9］，其一是查找当前概念中世界的当前状态，记为Q1；第二种是查找当前概念中世界的过去状态，记为Q2；第三种是查找以往概念中关于世界的过去状态，记为Q3.如图1所示.图1点查询的分类：Q1、Q2和Q3
Fig.1Timeslice queries Q1、Q2 and Q3由图1可知，Q1选择查询有效时间区间与Now相交且事务时间到Now的元组.因此在DCT中Q1选择元组所要满足查询条件为：
（Vt→≤Now∧Vt←≥Now）∧（Tt→≤Tt←∧Tt←=UC）在基于时间变元绑定的双时态数据存储中，由于［t1，t2］bindRt=［t1，t1］当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）在基于时间变元绑定的双时态数据存储中，由于［t1，t2］bindRt=［t1，t1］当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）在基于时间变元绑定的双时态数据存储中，由于［t1，t2］bindRt=［t1，t1］当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基于时间区间的查询变换区间查询是指对有效时间和事务时间范围的查询，通常也称为矩形交叉查询.元组（Vt→q，Vt←q，Tt→q，Tt←q）∈T×T×T×T表示相交查询域，其中T表示时间域，查询条件为Vt→q≤Vt←q，Tt→q≤Tt←q且Tt←q≤CT.在DCT中区间查询的条件是：［（Vt→≤Vt←q∧Vt←≥Vt→q）∧（Tt→≤Tt←q∧Tt←≥Tt→q）］由文献［10］的双时态数据上的相交查询结果的定义，可以知道区间查询变换到Dpoint上应满足的查询条件为：
［（Vt→≤Vt←q∧Vt←≥Vt→q）∧（Tt→≤Tt←q∧Tt←≥
Tt→q）∧GetType（）=4］
∨［（Vt→≤Vt←q∧Vt←≥Vt→q）∧（Tt→≤Tt←q∧Tt←=Tt→）∧GetType（）=3］
∨［（Vt→≤Vt←q∧Vt←=Vt→）∧（Tt→≤Tt←q∧Tt←≥Tt→q）∧GetType（）=2］
∨［（Vt→≤Vt←q∧Vt←=Vt→）∧（Tt→≤Tt←q∧Tt←=Tt→）∧GetType（）=1］（7）式（7）中搜索元组在Dpoint中表现为位于（0，Tt←q，0，Vt←q）区域内的点、平行于Tt轴并与（Tt→q，Tt←q，0，Vt←q）区域相交的线段、平行于Vt轴并与（0，Tt←q，Vt→q，Vt←q）区域相交的线段和与（Tt→q，Tt←q，Vt→q，Vt←q）相交矩形.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的绑定参考时间以适应不同的需求.