庞亚君

摘   要：我们的生活中几乎所有的事物都或多或少的具有时态特征，时态数据的处理已经成为当前重要的研究热点之一。时态信息处理在电子商务、数据挖掘、信息提取、电力系统、医疗系统、时空和多媒体信息技术以及网络应用等方面发挥着越来越重要的作用。另一方面，为了提高互联网的智能程度，语义网的不断发展。资源描述框架（RDF）作为语义网实现的基础，因此大量时态RDF格式的数据涌入网络。截止到目前为止，并没有针对时态RDF数据的有效存储方案。在原有时态RDF模型的基础之上， 分析了传统RDF存储方式在时态RDF数据存储上的可行性并提出了一种新的存储方案。

关键词：时态RDF;时态数据库;语义网;时态数据存储

中图分类号：TP311                                                文献标识码：A

（College of Computer Science and Technology， Nanjing University of Aeronautics and Astronautics， Nanjing， Jiangsu 210000，China）

Abstract：Almost everything in our life has more or less temporal features. The temporal data processing， has become one of the important research hotspot at present. The processing of temporal information play an increasingly important role in electronic commerce，data mining， information extraction， power system， medical system， spatial information technology and multimedia and network applications. On the other hand， in order to improve the intelligence of the internet， the semantic network continues to develop，the resource description framework（RDF） is the basis for the implementation of the semantic network， so a large number of temporal RDF format data are poured into the network. Up to now， there is no effective storage scheme for temporal RDF data. Based on the original temporal RDF model，this paper analyzes the feasibility of traditional RDF storage mode in temporal RDF data storage，and proposes a new storage scheme.

Key words：temporal RDF;temporal database;semantic web;temporal data storage

隨着时态数据与语义网的不断发展，越来越多时态RDF格式的数据涌入网络。在对时态RDF的早期研究中Buraga等人提出了一个基于 RDF 模型网站关系的时空表示法，并定义了 TRSL（Timed Raise Specification Language，时态性增强规范语言），使用 XML（eXtensible Markup Language，可扩展标记语言）表示区间时态逻辑的一系列不同操作[1]。Gutierrez 首次提出了时态 RDF 的语法语义以及查询语言[2]，但只是针对限定三元组。Andrea 等人补充了非限定三元组的语法语义[3]。Geetha等人针对海量 RDF 存储和语义网大量历史数据存储的问题提出了一个基于语义的时态视图机制[4]。时态

RDF 由于其独特的语义支持和推理机制，通常应用于人工智能领域，如 Mohamed Gaha等人将时态 RDF 运用到电力系统中[5]，并通过实验给出了存储以及查询性能。

时态RDF在语义搜索、电力系统等方面发挥的作用越来越大，且网络中时态RDF格式数据也越来越多，但与此相矛盾的是，针对时态RDF数据存储的研究相对甚少。因此，对几种时态RDF不同的存储方式以及存储算法进行对比分析，提出了一种切实可行的时态RDF数据存储方案。

1   时态RDF模型

目前对RDF的时态扩展主要有两个方式，一个是时间标签法，一个是版本更新发。时态标签法就是给产生变化的三元组添加时间标签;版本更新法即每当三元组发生变化时，时态RDF图会被更新，不必关心过去状态的时态RDF图存在何处，只需要记录更新后的时间快照即可。两者在处理时态信息时各有优势，版本更新法可以更有效的获取事务时间，而在获取有效时间时通常使用时态标签法。当时态信息越多也就是RDF图更新频率越快时，那么产生的新版本也会越多，不断记录更新后的RDF图无疑增加了查询的复杂度，而时间标签法保留了RDF原有的可扩展性。因此现有的时态RDF模型都是采用时态标签法进行时态扩展。

Gutiérrez在对RDF的时态扩展中采用时间点的方式，但是因为时间区间的表示方式同样可以表达时间点。例如一个区间[t1，t2]且t1≤t2，表示从t1到t2之间的一段时间，而当t1 = t2时，此时时间区间就变为一个时间点t1或t2。图1为一个时态RDF实例图，每条边上都由一个时间区间表示三元组的有效时间，其中[0，NOW]表示三元组自文档创建直到当前时间一直有效。

2   时态RDF存储策略

2.1   时态RDF数据映射方式

随着各大厂商对关系型数据库管理系统的不断开发与升级，利用关系型数据库管理RDF数据成为研究RDF存储的主要方向。将RDF格式的数据映射到关系型数据库中大致可以分为三种方式：直接映射、垂直映射以及属性表映射。下面分别就着几种映射方式在时态RDF存储中的应用进行分析和对比并提出了一种新的存储方式。

（1）直接映射方式

直接映射的存储方式就是在TimeDB[6]建立一张表格，将所有的三元组以及有效时间标签直接插入，因为时态RDF数据的有效时间标签表示的是一个RDF三元组在现实世界中真实存在的时间，因此，直接映射的存储方式能够很好的保持时态RDF数据的语义完整性，且在查询过程中很大程度上减少了连接操作。但是将所有的三元组以（S，P，O）：T的方式存储在一张庞大的表格中，每次进行查询操作的时候都要对整个表格进行遍历，效率十分低下。对于不断增加直至海量的时态RDF数据，这种存储模式显然不能很好的胜任。

（2）垂直映射方式

垂直映射方式就是以属性为中心，将同种属性的三元组存储在一张以属性名称命名的表格中，对于一个用户的几种不同属性，在每一个属性表中，其有效时间区间都进行了存储，当属性不断增加的时候，那么同一个有效时间区间要进行大量重复的存储。虽然垂直映射的存储方式在存储传统RDF数据时，可以有效的减少由于属性名重复出现的空间浪费现象，但是对于时态RDF数据来说，有效时间标签的重复存储会造成更大程度的存储空间

浪费。

（3）属性表映射方式

虽然属性表映射方式在处理传统RDF数据时，很好地解决了频繁自连接操作的问题，却不适用于时态RDF数据的存储。主要原因是没有很好的办法存放有效时间标签。比如当插入三元组的有效时间区间与其对应属性表中的有效时间区间不同时，只能通过再添加新的属性类表来实现，这对于海量时态RDF数据的处理显然是不现实的。

（4）本体实例分别存储方式

综合考虑到以上三种存储方式的优缺点，提出了一种本体实例分别存储的存储模型。时态数据处理除了要对时态数据合理存储之外，还要注重时态知识推理部分。对于时态RDF来说，即以时态RDF语义蕴含为理论基础的推理机制，在将一个时态RDF三元组插入到数据库中的时候，同时要将其蕴含的非直接声明的时态三元组一并插入。考虑到时态RDF推理中所涉及到的三元组主要以本体类型方式存在（例如谓语包含rdfs：SubclassOf以及rdfs：SubpropertyOf等属性的三元组），因此将本体与实例分别存储的方式会使得时态RDF数据的存储更加具有层次性。这种存储方式相较于直接映射方式更加具有层次性，且本体和实例信息分别存储在一定程度上解决了直接映射方式数据表过于庞大、效率低下的问题;而对于属性表映射和垂直映射方式来说，这种存储方式解决了数据表过多，连接操作频繁的问题，且更好的保证了時态RDF语义的完整性。详细的模型设计在3.2中给出。

2.2   存储模型设计

2.2.1   存储结构

由于时态RDF的时态特性是针对三元组的，比如某一三元组（s，p，o），其时态性并不是说主语、谓语或者宾语在某一段时间有效，这显然不符合实际。时态RDF是说这个三元组整体的有效时间区间，因此在存储时态RDF数据时，只有与三元组有关的存储才涉及时间特性，而对于RDF资源表、文字类型属性表等不涉及时间特性。若是将所有的类型都以时态表的形式存储，会造成很大程度的空间浪费。而且现有的时态数据库应用系统都是以在传统关系型数据库的基础之上增加时态中间件实现的，因此时态数据库具有向上兼容特性，在支持时态查询语言的同时，传统SQL语言也被支持，所以同时创建时态表和非时态表是可行的。

另外，系统将本体信息与实例存储在不同的表格中，因为本体信息需要被经常访问，将之与实例数据存储在一起，效率低下，且这种存储模式使得结构更为清晰，其中rdf：type类型也同本体信息一起存储，否则单独建立一个表格会增加连接操作，影响存储性能。具体的存储模型设计如图2所示：

2.2.2   存储规则

规则1（时态RDF类资源映射）：将形式化名称集合定义为N，命名空间为Ns，URI集合定义为U，那么对于集合RDF类资源C来说，存在映射Re：U→N∪Ns。

每一个时态RDF资源都以形式化名称和命名空间URI的格式存储在Class_Table表中。

规则2（时态RDF属性类资源）：对于属性资源集合P来说，都包含文字型属性值PL和PU非文字型 ，对于非文字型映射规则同定义1相同，而对于每个文字型属性值p∈PL来说，存在映射Rp：p→L，其中L为文字标签集合。文字类型属性资源存储在表格Literals中。而非文字类型的属性资源则存储相应的资源名，同Class_Table相连接。

规则3（有效时间区间映射）：给定时间区间集合Tl和时间点集合Tp，那么对于每一个时态RDF三元组的有效时间区间t∈Tl来说，存在映射Rt：t →{（t1，t2）|t1，t2∈Tp}。也就是说，对于时态RDF三元组的时间标签，要以起止时间和终止时间分别存储为两列的方式存储在关系表中。

另外對于时态RDF数据到数据库中的映射还有如下规则：

规则4（推理规则存储）：不同于一般的时态数据，时态RDF具有语义特性，所以要建立一个Rule_Table存放用于推理规则以及个三元组之间的关系。

规则5（非时态RDF三元组的存储）：虽然时态数据库TimeDB的向上兼容特性允许同时创建时态表和非时态表，但是为了减少连接操作，对于RDF三元组一直认为是时态类型，对于非时态类型的三元组时间区间默认用[0，Now]表示一直有效，对于只给定年份的有效时间区间，默认从一月一日开始到十二月三十一日结束（即XXXX-01-01到XXXX-12-31）。

2.3   存储算法

存储算法根据遍历对象的不同分为两种：一种直接按照RDF/XML文档的组织顺序，逐条将解析出的时态RDF三元组插入数据;第二种是对时态RDF图中的节点进行遍历，分为广度优先遍历和深度优先遍历。

定义1：给定时态RDF图G（V，E），其中V表示图中所有节点的集合，E表示所有边的集合，且E=P∪T，P表示时态RDF图边上所有谓词节点的集合，T表示所有有效时间标签集合。

由于在时态RDF图中不存在孤立的节点，也就是说图G中节点的个数|V|要小于G中边的个数|E|，因此使用深度优先遍历访问节点时，时间复杂度O（E 2/|V|），而广度优先遍历算法的时间复杂复杂度为O（|E|/|V|）比较两种算法的时间复杂度可知，BFS的方法要优于DFS的方法，因此本文也选用BFS算法对时态RDF图进行遍历，部分代码实现如下，其中l表示单向队列：

while（V）

//从任意节点开始

while（v）

v.visited（）;

for all v′s children

store all the triples have subject v and timestamp t;

if（v.child.isVisited（）==false）

l.push（v.child）;

if（v.parent==null）

V.remove（v）;

v←l.pop（  ）;

3   实   验

3.1   实验内容

实验内容分为两个部分，一是对存储模型的验证，二是对存储算法的验证。第一个实验通过三个复杂度不同的查询语句在统一数据集上进行验证，对其查询时间进行分析，其中Q1与Q2查询语句针对实例信息，Q3针对本体信息，且Q2要比Q1更为复杂。第二个实验通过在三个不同规模的数据集上使用不同遍历算法得到的数据载入时间进行对比分析。

3.2   实验数据及实验环境

由于目前时态RDF模型尚未形成标准等原因，没有可供使用的现成的时态RDF数据集，因此我们选用两种不同规模的现实世界数据以及一组模拟数据真实数据分别采用Semantic web-related bibliography[7]数据集和Polling data[8]数据集以及采用LUBM[9]随机生成的高校数据。RDF三元组的有效时间标签生成遵循两个要求：第一是每个有效时间区间的中点在1-1000之间随机生成，然后在高斯分布中获取有效时间区间的大小。

3.3   实验结果及分析

通过三种遍历方式分别在三个规模不同的数据集上数据载入时间的对比可以看出，采用存储算法要比直接读取时态RDF文档逐条存取的方式更加高效，且BFS遍历方式要比DFS遍历方式表现更优，更加验证了本文采用BFS遍历算法的高效性。

通过图表可以看出，由于Q1查询语句相对简单，没有涉及到过多的表连接操作，因此两种存储模型差距不大;对于Q2语句来说，由于直接存储的方式存储三元组的表格只有一张，而本文的存储模型通过本体表和实例表分别存储时态RDF三元组数据，表连接操作耗时较多，因此对于查询语句较为复杂的时候并没有太大的优势;Q3是针对本体信息的查询，在使用本文的存储模型时，直接访问本体信息表，而传统存储方式需要遍历整个三元组表，因此在对于本体信息查询的时候，本文提出的存储模型更加高效。

4   结   论

目前，时态RDF数据存储技术的研究还处于起步阶段，在传统RDF存储技术的研究基础之上，将不同的映射方式在时态RDF数据存储上的应用进行分析与对比，并提出了一种本体实例分别存储的映射方式，就两种存储算法进行分析讨论，选定了较为高效的DFS遍历算法，最终通过关系表的设计，提出了一种时态RDF数据存储方案，并通过实验证明了存储模型的高效性。

参考文献

[1]    BURAGA S，CIOBANU G. A RDF-based model for expressing spatio-temporal relations between web sites[C]// International Conference on Web Information Systems Engineering. IEEE Computer Society，2002：355—361.

[2]    GUTIERREZ C ， HURTADO C ， VAISMAN R . Temporal RDF[J].Lecture Notes in Computer Science， 2005， 3532：93—107.

[3]    PUGLIESE A，UDREA O，SUBRAHMANIAN V S. Scaling RDF with time[C]// International Conference on World Wide Web. ACM，2008：605—614.

[4]   MANJUNATH G，BADRINATH R，SAYERS C，et al. Temporal views over RDF data[C]// International Conference on World Wide Web. ACM，2008：1131—1132.

[5]    GAHA M，ZINFLOU A，BOUFFARD A，et al. Temporal RDF system for power utilities[C]// SEMAPRO 2015：The Ninth International Conference on Advances in Semantic Processing，2015.

[6]   SLIVINSKAS G，JENSEN C S，SNODGRASS R T. Adaptable query optimization and evaluation temporal middleware[P]. ACM，2002.

[7]    University of Georgia semantic web-related bibliography[EB/OL].

http：//www.arches.uga.edu/～vstaub/GlobalInfoSys/project/ontology/Could_have_been.rdf

[8]    U.S. presidential polling data[EB/OL]. http：//www.mindswap.org/～kendall/ev/allpolls.rdf

[9]    GUO Y，PAN Z，HEFLIN J. LUBM：a benchmark for OWL knowledge base systems[M]//Elsevier Science Publishers，2005.