时态数据的聚合查询及应用

摘 要：在SQL结构化查询语言中，所有针对数据表某列或多列的数据分析统称为聚合查询。基于传统的关系数据库管理系统（RDBMS）的基础上，对时态数据的聚合查询问题进行了深入的分析，通过引入时态聚合子区间的概念，并定义与之相匹配的数据结构，设计实现了一种时态数据的聚合查询算法。实际应用表明，该算法可行、有效。

关键词：时态数据；聚合查询；时态聚合子区间

中图分类号： TP311.13 文献标识码 A 文章编码：2095-2163（2015）03-

Aggregate Query and Application of Temporal Data

Huang Xiongbo

（Department of Electronic and Information Engineering， Foshan Professional Technical College， Foshan Guangdong 528137， China）

Abstract： In the SQL structured query language， all the data in a column or columns of data analysis are collectively referred to as the aggregate query. Based on traditional relational database management system（RDBMS） ， aggregation queries of temporal data is analyzed. After that， by introducing temporal aggregation sub interval， the paper defines the data structure to match the aggregate query algorithm， also designs and implementations a temporal data. The practical application shows that the algorithm is feasible and effective.

Keywords： Temporal Data； Aggregate Query； Temporal Aggregation Sub Interval

0引 言

作为关系数据管理系统（RDBMS）的标准语言，SQL（Structured Query Language）结构化查询语言提供了共同的数据存取语言和接口标准，从而使得异种数据库系统之间的互操作成为了可能[1]。从功能上划分，SQL结构化查询语言有三种类型的语句：数据定义语句（DDL，data definition language）、数据操纵语句（DML，data manipulation language）及数据控制语句（DCL，data control language）。其中，数据定义语句用于对基本表、视图、索引、模式等数据对象进行定义及修改；数据操纵语句用于数据的查询、插入、删除及修改等操作；而数据控制语句则用于用户对数据库存取权限的安全控制[2]。

在SQL的数据操纵语句中，经常需要对数据表中的某列或多列数据进行诸如求最大值、最小值或平均值的统计分析，而这些统计分析则统称为聚合查询。鉴于现有的时态信息应用系统往往是在RDBMS的基础上进行构建的[3-5]，且RDBMS并没有提供对应的时态聚合函数，据此，本文将深入分析时态数据的聚合查询问题，通过引入时态聚合子区间的概念，并定义相匹配的数据结构，进而设计实现了一种可行、有效的时态聚合查询算法。

1问题描述

1.1 时态数据的聚合查询问题

如表1所示，SQL结构化查询语言提供了一系列的聚合函数来完成数据表的相关统计分析[6]。

表1 SQL的聚合函数

Tab.1 The SQL aggregate function

序号 函数格式 功能说明

1 COUNT（*） 计算元组的个数

2 COUNT（<列名>） 对某一属性的值进行个数计算

3 SUM（<列名>） 求某一数值型属性的总和

4 AVG（<列名>） 求某一数值型属性的平均值

5 MAX（<列名>） 求某一属性值的最大值

5 Min（<列名>） 求某一属性值的最小值

在时态信息处理系统中，由于各个时态元组具有不同的时间生命周期，这使得相应的聚合统计分析变得尤为复杂。下面将结合表2所示的时态工资数据表来加以说明。

表2 时态工资数据表

Tab.2 Temporal salary data table

编号 工资 有效开始时间 有效结束时间

01 2 000 2003.01 2005.04

01 2 500 2005.05 2008.04

01 3 200 2008.05 2010.09

02 2 800 2004.02 2007.10

02 4 000 2007.11 2009.09

03 3 800 2009.03 2010.06

如表2所示，为了减少时态数据的冗余存储，各个时态元组都添加了时间生命周期的约束，为此，时态聚合查询应在各个元组标识（如表2中的“编号”）均具有单一属性值的某一时间区间（或时刻）上进行才具有实际意义。还应指出的是，由于表2的时态工资数据表选用了月份为时间粒度，且每个时态元组的有效开始时间与有效结束时间构成了一个闭合的时间区间，故时间区间[2008.01，2008.04]与[2008.05，2010.01] 在区间点"2008.04"与"2008.05"上是连续的。

例1：计算表2中2008年3月的工资总和。

例2：统计表2中2008年3月的员工总人数。

1.2 独立的时态聚合子区间

如前所述，为使时态聚合查询有意义，则应从聚合查询时间区间与各相关时态元组中析出一系列独立的时态聚合子区间，在这些子区间中，要求各个元组标识均具有单一的属性值。

例3：在表2中，若需要对[2008.01，2010.01]的时间区间进行相关的聚合查询，试析出独立的时态聚合子区间。

依题意，聚合查询的时间区间为[2008.01，2010.01]，由于析出的独立时态聚合子区间要求其内含的各个元组标识均具有单一的属性值，结合表2中“编号”为"01"、"02"及"03"的员工工资变化情况，可得到如表3所示的4个独立的时态聚合子区间。

表3 例3所对应的独立时态聚合子区间

Tab.3 In 3 cases the independent sub interval temporal aggregation

序号

时态聚合子区间

区间起点 区间终点

1 2 500 4 000 Null 2008.01 2008.04

2 3 200 4 000 Null 2008.05 2009.02

3 3 200 4 000 3 800 2009.03 2009.09

4 3 200 Null 3 800 2009.10 2010.01

从表3中易知，各个时态聚合子区间就形如RDBMS中的一个快照，因而可以在这些子区间中进行相关的聚合查询。

2 时态数据聚合查询算法的设计与实现

2.1 算法的设计原理

时态聚合查询的核心就是析出一系列独立的时态聚合子区间，并写入对应的时态元组的属性值，为了提高查询性能，子区间的析出与属性值的写入应在同一次的SQL查询中进行。

根据这一设计目标，时态聚合查询算法的实现过程为：首先定义时态元组属性值（内含元组标识、属性值）、时态聚合子区间（内含区间的开始时间、结束时间、时态元组属性值）2个结构体，其中，时态元组属性值是以子结构体的形式嵌入至时态聚合子区间的结构体中；随后通过SQL语言检索出所有与聚合查询时间区间有交集的时态元组，并对检索结果按照元组标识进行分组及排序；进一步，在已有的时态聚合子区间的基础上遍历处理SQL检索结果，且根据各个时态元组的有效开始时间及有效结束时间不断地调整时态聚合子区间的个数、开始时间、结束时间及其对应的时态元组属性值；最后在一系列独立的时态聚合子区间上进行各种聚合查询。

仍以例3为例介绍算法的工作原理。在表2中，“编号”为"01"、"02"及"03"的员工其工资有效时间区间与聚合查询时间区间[2008.01，2010.01]与交集的时态元组分别为，[2005.05，2008.04] [2008.05，2010.09]、[2007.11，2009.09]、[2009.03，2010.06]。

（1）处理第1组交集[2005.05，2008.04] [2008.05，2010.09] ：由于区间点"2008.04"（"2008.05"）把聚合查询时间区间分成了2个时间子集，故此时可如图1所示创建[2008.01，2008.04]和[2008.05，2010.01]2个时态聚合子区间，并写入对应的时态元组属性值。

图1 编号为"01"的员工其时态元组所对应的时态聚合子区间

Fig.1 From the number "01" employee corresponds to the sub interval temporal aggregation

（2） 处理第2组交集[2007.11，2009.09] ：在图1的基础上插入区间点"2009.09"（"2009.10"），得到了如图2所示的3个时态聚合子区间，同时更新受影响的时态元组属性值。

图2 编号为"01"和"02"的员工其时态元组所对应的时态聚合子区间

Fig.2 From the number "01" and "02"employee corresponds to the sub interval temporal aggregation

（3） 处理第3组交集[2009.03，2010.06] ：在图2的基础上插入区间点"2009.02"（"2009.03"），得到了如图3所示的4个时态聚合子区间，此外，各个时态聚合子区间所对应的时态元组属性值均以有序（如从小至大）的形式进行写入，以便提升其后进行的诸如MAX、MIN等聚合查询的运算效能。

图3 编号为"01"、"02"及"03"的员工其时态元组所对应的时态聚合子区间

Fig.3 From the number "01"，"02" and "03"employee corresponds to the sub interval temporal aggregation

从图1～图3可知，任一时态元组的时间交集（记作 与已有的各个时态聚合子区间（记作 ）的插入调整有以下3种情况[7]：

（1） 不新增时态聚合子区间

若 成立时，则不新增时态聚合子区间，且 所内含的时态元组属性值也不需作调整；而当 成立时，则不新增时态聚合子区间，但应把 内含的时态元组属性值写进 中去。

（2） 新增1个时态聚合子区间

若 成立时，则新增1个时态聚合子区间，即把 拆分为 和 ，同时把 所对应的时态元组属性值写进新调整的 和 中去；同理，若 成立，则应把 拆分为 和 ，同时把 所对应的时态元组属性值写进新调整的 和 中去。

（3） 新增2个时态聚合子区间

若 成立时，则新增2个时态聚合子区间，即把 拆分为 、 和 ，同时把 所对应的时态元组属性值写进新调整的 、 和 中去。

2.2 算法的设计实现

综上所述，可以设计如下的时态聚合查询算法。

算法名称 时态聚合查询算法

输入：时态数据表Temporal_Table、聚合查询区间[Query_Start， Query_End]、聚合函数名称 Aggregate_Style

输出：在各个时态聚合子区间上的聚合查询结果

（1）相关初始化

（1.1）定义保存时态元组属性值的结构体

struct Attrib_Information

{

char ID[20]；// 标识时态元组的ID

float score； // 时态元组对应的数值型属性值

}

（1.2）定义保存时态聚合子区间的结构体

struct Temporal_Aggregation_Interval

{

DateTime AI_S；

//时态聚合子区间的开始时间

DateTime AI_E；

//时态聚合子区间的结束时间

struct Attrib_Information Value[]；

//Value动态数组，其类型为Attrib_Information结构体

}

（1.3）定义时态元组属性值写入过程

procedure Write_AI（float tempscore，struct Temporal_Aggregation_Interval tempNode）

{

int position=Binary_Search（tempscore，tempNode）；

// Binary_Search为折半查询函数，返回tempscor数值在tempNode.Value中的插入位置

DataMove（tempNode.Value，position，1）；

//把tempNode.Value数组的元素从position位起整体后移1位

tempNode.Value[position]=tempscore；

//把tempscore值插入至tempNode.Value数组的position位

}

（1.4）赋初值

struct Temporal_Aggregation_Interval Node[]；

//Node动态数组，其类型为Temporal_Aggregation_Interval结构体

Node[0].AI_S = Query_Start；

Node[0].AI_E = Query_End ；

（2）检索与聚合查询的时间区间有交集的时态元组，并对检索结果分组及排序

select * from Temporal_DataTable where not（VT_S> Query_End OR Query_Start> VT_E） GROUP by ID ASC→Rs

（3）遍历处理查询结果，析出时态聚合子区间，并写入对应的时态元组的属性值

for i=0 to Rs.RecordSet.count-1

//遍历处理有交集的时态元组

begin

for（j=0 to Length（Node）-1）

// Length（Node）为动态数组时态聚合子区间的长度

begin

if （Rs.RecordSet[i].VT_S<= Node[J].AI_S） and

（Node[J].AI_E<= Rs.RecordSet[i].VT_E） then

begin

Write_AI（Rs.RecordSet[i].Value， Node[J]）；

//把时态元组属性值Rs.RecordSet[i].Value写进

时态聚合子区间Node[J]中去

end；

if （（Node[J].AI_S < Rs.RecordSet[i].VT_S） and （ Rs.RecordSet[i].VT_S< Node[J].AI_E）） and （Node[J].AI_E <= Rs.RecordSet[i].VT_E） then

begin

temp= Node[J].AI_E；

Node[J].AI_E= Rs.RecordSet[i].VT_S；

Node[J+1].AI_S= Rs.RecordSet[i].VT_S；

Node[J+1].AI_E= temp；

//新增1个时态聚合子区间Node[J+1]

Write_AI（Rs.RecordSet[i].Value， Node[J]）；

Write_AI（Rs.RecordSet[i].Value， Node[J+1]）；

end；

if （（Node[J].AI_S < Rs.RecordSet[i].VT_E） and （Rs.RecordSet[i].VT_E < Node[J].AI_E）） and （Rs.RecordSet[i].VT_S <= Node[J].AI_S） then

begin

Node[J].AI_E= Rs.RecordSet[i].VT_E；

Node[J+1].AI_S= Rs.RecordSet[i].VT_E；

Node[J+1].AI_E= Rs.RecordSet[i].VT_S；

Write_AI（Rs.RecordSet[i].Value， Node[J]）；

Write_AI（Rs.RecordSet[i].Value， Node[J+1]）；

end；

if （（Node[J].AI_S < Rs.RecordSet[i].VT_S） and （Rs.RecordSet[i].VT_E < Node[J].AI_E）） then

begin

//新增2个时态聚合子区间Node[J+1]和Node[J+2]

temp= Node[J].AI_E；

Node[J].AI_E= Rs.RecordSet[i].VT_S；

Node[J+1].AI_S= Rs.RecordSet[i].VT_S ；

Node[J+1].AI_E= Rs.RecordSet[i].VT_E；

Node[J+2].AI_S= Rs.RecordSet[i].VT_E ；

Node[J+2].AI_E= temp；

Write_AI（Rs.RecordSet[i].Value， Node[J]）；

Write_AI（Rs.RecordSet[i].Value， Node[J+1]）；

Write_AI（Rs.RecordSet[i].Value， Node[J+2]）；

end；

end；

end.

（4）在各个时态聚合子区间Node中执行相应的时态聚合查询

for（i=0 to Length（Node）-1）

begin

case Aggregate_Style='count'

result_count=Length（Node[i].Value）；

case Aggregate_Style='sum'

begin

result_sum=0；

for（j=0 to Length（Node[i].Value）-1）

result_sum =Node[j].Value+ result_sum；

end；

case Aggregate_Style='avg'

begin

result_sum=0；

for（j=0 to Length（Node[i].Value）-1）

result_sum =Node[j].Value+ result_sum；

result_avg= result_sum/ Length（Node[i].Value）；

end；

case Aggregate_Style= 'max'

result_max= Node[i].Value[Length（Node[i].Value）-1]；

case Aggregate_Style= 'min'

result_min= Node[i].Value[0]；

end；

3 应用实例与性能测试

3.1 实验环境

为了验证算法的有效性，本文对上述时态工资表的聚合查询进行了的设计与实现。实验的硬件环境为惠普ProDesk 490 G2 MT商用台式机（CPU：i5-4570 4*3.2GHz；内存：4GB DDR3 1600 ），软件环境及开发工具为Windows 8.1+ Embarcadero Delphi 2010，程序的运行界面如图4所示。

图4 时态聚合的程序界面

Fig.4 The temporal aggregation query program interface

3.2 性能测试

由于算法的计算耗时主要集中在时态聚合子区间的析出与时态属性值的写入，为此，这里随机地往表2中追加了1.2万名员工、共11万条的时态工资元组数据，并按照时态子区间的析出数量进行分组的性能测试[8]，测试结果如表4所示。

表4 时态聚合查询的计算耗时（单位：μs）

Tab.4 The time-consuming computation of temporal aggregate query （unit： μs）

序号 时态子区间的析出数量 时态子区间的析出耗时 时态属性值的写入耗时 小计

1 100 4.53 0.31 4.84

2 200 6.11 0.53 6.64

3 500 15.34 0.89 16.23

从表4可知，虽然算法的计算耗时随着时态聚合子区间析出数量的增加而增加，但其计算耗时仍然维持在较低的μs等级里，故算法具有较好的应用场合。事实上，在表2的时态工资表中，由于其时间粒度为月份，因而析出500个时态聚合子区间就意味着聚合查询时间区间至少覆盖了41年（500/12 ≈41）多的工资数据。

4结束语

本文分析了时态数据的聚集查询问题，并设计实现了一种可行、有效的时态聚集查询算法。下一步的主要工作有，设计高效的时态索引技术和优良的数据结构进而改善现有算法的计算效能，同时研究时态聚合子区间的并行析出方法，以便更好地提升算法的负载能力。

参考文献：

[1] 王珊，萨师煊.数据库系统概论（第4版）[M].北京：高等教育出版社，2006：78-129.

[2] 沈钧毅，侯迪，冯中慧，等.数据库系统原理[M].西安： 西安交通大学出版社，2014：32-70.

[3] 黄雄波.电子病历中时态数据库的分析与设计[D]. 广州：华南理工大学，2007.

[4] 黄雄波，陈章，岳喜顺.电子病历中重叠时态数据的分析与消除[J]·计算机技术与发展，2009，18（3）：235-238·

[5] 黄雄波，张荣荣.一种改进的时态数据模型的设计与应用[J].计算机时代，2014，33（7）：1-3·

[6] 施伯乐，丁宝康，汪卫.数据库系统教程 [M]. 第3版. 北京：高等教育出版社，2008：74-115.

[7] 徐洁磐.离散数学及其在计算机中的应用[M].北京：人民邮电出版社，2008：1-62.

[8] 黄雄波，陈章，徐小增.电子病历中时态数据的过滤运算研究[J].计算机应用与软件，2009，26（12）：117-120·