关系数据库支持的不确定时间序列存储

2019-11-18左良利

计算机技术与发展 2019年11期

王玙，左良利

(南京航空航天大学计算机科学与技术学院，江苏南京 211106)

0 引言

随着传感检测、位置定位和隐私保护等领域的不断研究，数据的不确定性得到了越来越多的重视。把这种按照时间戳先后顺序排列的记录值的数据记为时间序列[1-3](time series)，而在每个时间戳上序列的值是多个称之为不确定时间序列(uncertain time series)。在解决不确定时间序列的诸多问题中，如对时间序列的持久化[4]，降维，聚类[5]，相似性匹配[6-8]等研究工作，推动了数据分析技术的不断成熟。不确定时序的存储是其他方面的基石。文献[9]结合不确定时间的特点，提出了UK-Means算法来计算初始距离的期望结果。文献[10]提出在大规模时序数据库中通过匹配能找到已知的序列集合。文献[11]提出用随机变量描述成不确定时间序列，并提出基于DTW[12]和欧氏距离的PBRQ(probabilistic bounded range query，概率性有界范围查询)和PRRQ(probabilistic ranking range query，概率性排序范围查询)。文献[13]等基于两个不确定时间序列所在的时间点的距离方差是相同的假设，提出了PROUD算法，利用统计学方法进行剪枝来减少计算代价。

上述研究都是围绕不确定时间序列的应用目的而展开的，对其相似性匹配，聚类研究也只是刚刚起步，但是对于不确定时间序列在关系数据库上存储的研究[14]少之又少。文献[15]提出一种LittleTable的关系型存储模型，通过在两个维度上对表结构进行聚类，按照时间戳来划区表示以提高时间序列的检索效率，并且针对时序数据的写入特点，削弱了一致性功能，使其大大提高了数据的写入能力。

1 不确定时间序列

不确定时间序列的不确定性表示为每个时间戳的数据点可能有多个观察值，在这个时间戳上的值可能由一系列的样本点组成，这些样本点分布的不同也构成了不确定时间序列模型的不同。

1.1 离散型模型表示

每个时间戳的取值以离散的形式分布，这些离散的点有两种方法处理：一是将所有的离散点记录存储下来；二是这些离散点以一定的概率出现，服从某种离散分布(如二项分布、泊松分布等)。离散模型表示见图1。

图1 离散模型表示

1.2 连续型模型表示

将不确定时间序列的每个时刻观测到的点看作是某种连续型的随机变量，服从某种已知的连续型概率分布(如正太分布、均匀分布等)。那么该时序某时刻数据点就可以形式化表示成某种概率分布函数(probability distribution function)。

2 不确定时间序列存储方法

2.1 不确定时间序列数据模型

不确定时间序列是一个多元嵌套结构,定义如下：

uncertain_timeseries=(timestamp,tags1, …tagsi,>)

其中：

(1)timestamp：时间戳表示采集数据的时间点。

(2)tags1…tagsi：维度表示该序列数据的归属，属性表明由哪个设备/模块产生。一般该条序列的维度值不会随时间变化，仅供查询使用。

(3)field：指标代表数据的测量值，随着时间变化而变化，一条序列中的指标可能有多个，其测量值就会有多个。

(4)：测量值，由指标测量的值来表示该值的范围，当该值带有不确定因素，则probability∈(0,1)，若该值是确定的值，则probability=1。

需要说明的是，上述离散型模型表示的是不确定离散型时间序列，而对于不确定的连续型时间序列，其表述方式大致相同，数据模型中嵌套的二元组形式替换成三元组，即将概率值替换为方差和均值即可。但这并不是文中的研究重点，故不再叙述。

2.2 存储规则

首先，存储的过程支持对多条时序数据进行存储，需要对不同的不确定时序数据进行分类存储，将各条序列的维度信息与属性信息一一对应，并将其相关的数据元信息完整存储。接下来通过上述过程提出一系列不确定时序数据到关系模型的存储规则，步骤如图2所示。

图2 存储示意

文中根据时序数据不同属性的用法对其进一步建立二维关系表，有如下规则：

规则1：在对时间戳数据值进行数据结构表示时，根据2.1节将属性值分为指标和维度属性，这两种数据结构表示是不一样的。维度值的数据结构是以哈希表来表示的，而指标值可能会产生不确定数据，以离散时间序列为例，其数据结构依然是键值对来表示，只不过该表中相应的键是指标属性，而值又是一个哈希表来表示数据的不确定性，即嵌套的键值对分别表示数据及其发生的概率。当该数据为确定性时，为了保证一样的数据结构表示，则规定确定性的数据发生概率为1。为了方便表述，在接下来的规则中以键值对或者节点来表示该数值。

规则2：维度表的建立，采取系统默认的主键自增策略。当维度队列中维度节点不存在其对应的维度表，则新创建该维度表并新插入行；否则继续查找对应表中是否有同一个维度，相同的话则忽略，不同则新插入行。例如，对于同一个维度的传感器产生的时序数据，此时不需要每次收集都记录该维度属性数据，目的是为了避免数据冗余。

当不存在则创建维度表的语句：CREATE TABLE tags_Table {id INT AUTO-INCREAMENT，node.k1VARCHAR,…,node.knVARCHAR,PRIMARY KEY(“id”)}，而当进行添加维度表的INSERT TABLE TagsTable{node.v1…node.vn}。

规则3：指标表的建立，当时序数据中有多个指标属性，则对应多个表，而该序列的时间戳作为主键，对应tags_tables中的主键作为该表的外键。将指标属性分开存储的目的是为了方便查询和节省空间，因为数据值是随着时间而不断生成的，将所有指标放在同一个表中，会使得存储表过大，并且，在后期优化中也不允许将多个指标属性存储在一个表中。针对查询单个指标属性的场景，也不会造成查询结果集过大的问题。

创建指标表的语法：CREATE TABLE metric_Node.k_Tables{timestamp INT，tags_id INT，1S VARCHAR,…,nsVARCHAR,PRIMARYKEY(“timestamp”)，FOREIGN KEY(tags_id) REFERENCE tags_table}。

规则4:观察值的表示，表示在接受应用设备的数据都统一表示。这样会使存储的数据格式不一致造成处理差异。无论是确定或者不确定性的指标值都统一化表示，以JSON序列化格式进行存储，这样提取出来可以供许多语言进行解析，从而达到数据处理的一致性。

规则5:时间戳转换，在收集到每个时间序列时，都会包含一个时间类型。关系型数据库存储采用INT类型来保存UNIX时间戳更合适，因为各个数据库提供的日期时间函数是不同的，很难在SQL查询指令中进行协调，故采用INT类型表示UNIX时间戳。

规则6:在进行处理时，不存在任何属性值为空，以保证算法的严谨性，在采集数据中规定每个属性都可以准确地描述，避免将时序数据存入关系模型中含有空值(NULL)。

规则7:在将非结构化数据转换成层次结构时，不确定时序数据在实际应用中特殊的表达形式，具有多个同级属性，这也规定了在进行树型结构表示时，最多只有三层结构。如果不满足此结构，则不属于该时序数据类型。

规则8:在队列中存储的数据节点的Key属性值，都是以某一规则进行有序排列的。因为关系模型中是二维表结构，而表结构中的属性是有序的，因此，在每次取出进行建表时都会以某一个排序函数进行排序。

规则9:在将时序数据转换结构化过程中，规定树型节点中有且只有一个代表时间戳的节点，避免多值混乱存储。

规则10:在将时序数据各属性数据转换成关系表时，关系表对应命名方法，文中采取的是驼峰型命名规则。例如数据源关系表命名为tags_Table，而属性命名为length_MetricValue等，以此类推。

规则11:在实际应用中收集的时序数据都属于常用的基本类型，需要对其进行基本的数据类型转换。由于大多数基本数据类型到SQL数据类型都有联系，因此转换起来十分简单。例如，Integer型数据对应SQL数据类型的INTEGER，同理，float转换成FLOAT，string转换成CARCHAR，time转换成TIME，date转换成DATE。

2.3 存储算法

针对上述提出的存储规则，将非结构化的时序数据进行建模，并提出存储方法。本节基于前两节的内容进一步提出存储方法，利用XML的树型结构层次结构，将其进行结构化表示，然后将各个不确定时序之间属性的关系定义清楚，并遍历不确定时间序列的结构化模型，并根据不同结构类型找出维度属性与指标属性，提出主要的存储算法。为了更好地叙述算法，引入了几个简单的关于队列操作的辅助函数。函数queuepush(q,node)将node元素添加到q队列。函数queuepoll(q)是将取出q队列中的队尾元素从队列中删除，返回的是取出的node节点。

存储算法：

输入：Uncertain TimeSeries Point

输出：Relation database Scchema

root=ConvertTree(uncertainTSPoint);

Initq(q1),Initq(q2),Initq(q3);

node Timenode

for(node:queuePoll(q1).childNode){

if(node.value=DateTime){

Timenode=node;}

else if(node.hasChild){//指标

String value="";

for(int i=0;i

value=node(i).getkey+","+node(i).value;}

TempNode=new TempNode();

queuepush(q3,TempNode);}

else {queuepush(q2,node);}}//维度

while(!empty(q2)){

根据规则3，创建tags_Tabls }

/q2重新赋值

if(!empty(q2) && TimeNode!=null

&& !empty(q3)){

while(!empty(q2)&& queuePoll(q3){

for(int i=0;i

根据规则2、4，创建metric_Tables}

queuePoll(q3)}}

3 实验

到目前为止，并没有一个公认的标准方法评价不确定时序数据存储到关系模型的效果，要检验文中提出的存储策略与算法的可行性，关键是对结果进行等价的验证。存储系统如图3所示，该系统分别对人工查询和数据库查询语句检验的结果进行对比，若查询的结果与最初加噪的数据集相同，即证明了存储的有效性。

图3 存储系统

3.1 实验数据及实验环境

为了构造不确定时间序列数据符合原始时间序列数据的特征，采取的策略是随机生成概率值δ进行人工加噪，以表示不确定时间序列，δ的取值范围为0到1。并且，若该时间点的δ值总和不为1，则应该继续生成该点的离散值，并且采取误差值在0.5ε到1.5ε，使确定值上下浮动并且对应的概率值累计为1。通过这种方式，使在时间点上的不确定数据与真实采集的不确定数据更加相似。在实际收集数据时，由于外界不可控因素产生误差，影响因子也随之变化，但是大部分的采集值是精确的。因此，采取随机性地标记时间点上的值是能够有效反映出不确定时间序列。文中研究的是时间序列各个时间点上的不确定性，所以每一类的时间间隔都是相等的。

UCR数据集是时间序列分析中应用广泛的测试数据集，文中采用UCR数据库中的数据作为输入数据，主要选取的数据集(见表1)：Synthetic Control(Syn_Ctrl)，Gun-point(Gun)，OSU Leaf(Leaf)，CBF，Face(all)(Face)。在原始数据的基础上，以离散均匀分布加入噪声进行干扰，将其存储的序列变成不确定时间序列进行存储。

实验环境见表2。