支持有效时间的时态RDF数据的不一致性分析

张燕超

摘 要：资源描述框架（RDF）是一个元数据模型，是由W3C建立的基础设施，使得Web上的数据机器可读。近年来，语义网的快速发展和RDF的普遍应用，产生了大量的含有时态信息的RDF数据，并涉及到各个方面领域的关键数据。时态RDF数据的一致性能提高时态RDF数据的准确性，时态数据的一致性检测和恢复也有助于提高数据库系统的可靠性和高效性，对于时态信息处理也能提供可靠的保证，也能提高时态信息处理的效率。研究了对传统RDF引入时间信息的建模方式，通过添加有效时间的时间标签的方式构建了支持有效时间的时态RDF模型，在此基础上对时态RDF数据存在的不一致性情况进行了分析和研究，并提出了相关的检测和修复的算法。

关键词：时态数据模型；有效时间；时态数据的不一致性

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

Abstract： The resource description framework （RDF） is a metadata model，the infrastructure established by the W3C，which makes the data machines on Web readable.In recent years，the rapid development of semantic web and the widespread application of RDF have produced a lot of RDF data containing temporal information and related key data in various fields.Consistent performance of temporal RDF data to improve the accuracy of temporal RDF data，temporal data consistency detection and recovery also helps to improve the reliability and efficiency of the database system，the temporal information processing can also provide a reliable guarantee，also can improve the efficiency of temporal information processing.This paper presents a modeling way of introducing the time information of traditional RDF，temporal RDF models support valid time through constructing the time tag time effective way，inconsistency on the basis of temporal RDF data are analyzed and studied，and put forward the related detection and repair algorithm.

Key words：temporal data model；effective time；inconsistency of temporal data

1 引 言

資源描述框架RDF（resource description framework）是由万维网协会W3C提出的一个语义框架[1]，被广泛应用在描述语义网[2]中的各类海量数据，可以用三元组（主语、谓语、宾语）的形式来描述语义网上的任何数据。

随着计算机技术和信息技术的深入发展，语义网中的时态RDF数据也在快速的累积中，RDF数据的涉及到各个领域，而这些RDF数据常常带有时间信息。时态信息在信息系统中扮演着日益重要的角色，因此，对于RDF数据进行时态数据建模具有重要意义，时态RDF数据的一致性检测和恢复也有助于提高时态RDF数据库系统的可靠性和高效性[3]，特别是对电子商务、数据挖掘、决策支持系统等信息系统有着越来越重要的意义和保障[4-6]。

时态数据的一致性研究中文献[7，8]都是基于关系数据库的多版本来进行，文献[7]需要追溯过去的版本中的所有的不一致性数据，操作复杂耗时。提出了一种方法来检测和修复多时态多版本XML数据库中因为追溯更新导致数据不一致性。因为支持多时态多版本XML，要恢复数据库的一致性要通过纠正过去所发生的所有错误和不一致性。文献[8]对于时态RDF数据提出了新的框架，确定一个子类的一阶一致性约束，利用调度理论有效的映射到约束图来解决问题。这个方法优于普通的近似启发式算法，但是是对一个子类做出的约束，并不能更好的包含所有时态RDF图，应该一步推广一致性约束。这篇文献是针对于查询中出现不确定性的结果进一步做一致性检测和恢复，存储的数据本身就会还有不一致性和不正确性。文献[9]提出了时态XML的一致性要求，并提出了环路检测来检测和修复存在的不一致性数据，算法思路比较严谨。但是考虑数据不一致性很不全面，分类太简单，现实生活中的数据一定会更复杂。因为RDF的特殊性，并不适用于时态RDF数据的一致性分析。

对传统的RDF三元组进行了时态扩充，通过增加有效时间的时间标签来进行建模，针对有效时间的现实意义提出了时态RDF数据存在的不一致性，并对每一类的不一致性提出了检测和修复的方法，并通过实验验证了算法的实施性。

2 时态RDF模型

国内外学者提出了多种类型的时态数据库模型，其中主要是基于关系模型的时态关系数据库以及相应的查询语言[10]。除了关系模型，Chawathe首次提出了管理历史的半结构化数据[11]，他扩展了交换对象模型，使它可以表示更新，借助“增量（deltas）”来跟踪它们。Claudio Gutierrez[12]首次提出了对于时态RDF数据模型的建立，时间RDF三元组的基础上添加时间标签来实现数据的时态性，如（s，p，o）：[T]，其中T就是时态信息。后续的时态RDF模型的研究都是在此时态RDF数据模型的基础上进行更多的语义和时间信息的表达上的扩展[13，14]，例如时态信息[T]更新为[n：T]，表示在T时间内这个时态RDF三元组真存在n次，还有进行双时态扩展，同时支持有效时间和事务时间。还有更多的时态和语义的逻辑分析与推理，基本都停留在理论上的分析。

2.1 有效时间标签

对RDF数据引入时间信息，要对RDF模型进行时态信息的扩展，就要考虑一下几个方面的问题，再选择其中比较合适和符合实际应用条件的模式。

1.版本化和时间标签化：版本化就是当RDF数据有更改时，通过快照的方式保存更改前后的RDF数据库状态。加入时间的方法很简便，但是会造成数据冗余，产生大量的重复的RDF数据信息，存储空间的开销也会增大，对于跨版本的查询操作复杂需要查询多个RDF数据表中的数据消耗时间。时间标签化就是直接对RDF三元组添加时间戳，对于每一个改变的三元组加上时间标签，保留了RDF中分布式和可扩展性的特点，添加了时间信息，只是数据的结构比版本化的复杂。带时间标签的RDF数据模型只要增加和修改更改的数据，增长方式会远小于版本化的时态RDF模型，可以消除大部分的时态RDF数据冗余。

2.事务时间和有效时间：事务时间是捕捉并保存每次操作前后的RDF数据的变化，对于在过去时间段存储的RDF数据只能方便查询。有效时间是用来模拟现实世界中RDF数据存在的状态，对于RDF数据的每个时间阶段的状态可以保存也可以进行任意的修改，发现过去一段时间的RDF数据有错误可以直接更改数据的有效时间。两者以不同的方式来展现RDF数据的动态性，保存的都是有更新的数据，数据冗余度会大大降低，存储需要的空间也会缓慢增长。

综上所述可以通过添加时间标签来扩展时态信息，来建立时态RDF模型，用时间标签来标记RDF数据三元组，且表示有效时间。以下就是时态RDF模型的基本定理：

定义1.一个时态RDF数据的组成分为两部分，时间标签和RDF三元组，用符号表示（s，p，o）：[t].（s，p，o）：[t1，t2]表示{（s，p，o）：[t]|t1≤ t≤ t2}。其中spo代表RDF三元组中的主体、谓词和客体。t是一个自然数，用来代表时间，表示在t时刻s的p属性值为o是有效的。

添加有效时间区间的时间标签来进行时间信息的扩充，模拟现实世界中RDF数据每个时间段的存在状态，保留了数据的动态性，也简化了时态RDF数据结构。

定义2.有效时间区间[start，end]中，start+1≤end，单位时间设为1；

为了表示时间上的连续，即使使用秒数作为单位时间在现实中时间也是不连续的，为了下文的使用方便和自然，将单位时间设为1，t和t + 1两个时刻就表示是时间上的连续。

3 时态RDF的不一致性

尽管现在从语义网上提取信息的技术有了很大的进步，例如DBpedia、Freebase、YAGO等都是采用自动化提取技术，但是产生的RDF知识库仍然面临着存在大量的噪音和与事实不一致的问题，这些不一致性的数据一般用不确定的数据来概括，需要添加一些额外的一致性约束。本节就是针对添加了有效时间标签的RDF数据模型，根据有效时间的现实意义，分析时态RDF数据存在的不一致性，并对存在的所有类型的不一致性进行检测与修复。

3.1 生命区间的定义

定义3 节点的生命区间lifespan ：一个节点的生命区间是这个节点的所有入边和出边的有效时间的并集的最大集合。在只有（s，p，o）[start，end]一条数据的情况下，s是父节点，o是子节点，lf[start，end]就是节点s和节点o的生命区间。

s节点的p属性值为O在[start，end]时间都有效，证明s节点和o节点是存在的，因此，计算节点的生命区间要包含节点的所有出边和所有入边的有效时间。

算法1 计算节点的生命区间

输入：节点的URI（唯一性）

计算生命区间时输入节点node，通过遍历这个节点的所有的出边入边，计算所有边的有效时间的并集的最大集合，也就是找到最早的开始点和最晚的结束点。算法的复杂度是O（n），n是存储的时态RDF数据记录的条数，要计算时态RDF数据中所有节点的生命区间，则是节点数*n。

3.2 三元组重复的不一致性

主体、属性、客体都是相同的，即RDF三元组是一样的，表示为（s，p，o）[T1]和（s，p，o）[T2]，其中T1和T2只要有重合的部分就是存在不一致性。

有效时间区间是唯一确定的，如果有重叠其中一个有效时间区间一定是与事实不符存在不一致性的。对于T1和T2的关系是间断的，可以解释为在T1和T2这两个时间段内s的p属性值为o，但是在T1和T2间隔的时间内这个信息失效了，所以不存在不一致性。

检测存在数据库中的时态RDF数据是否存在上述的不一致性，每一条时态RDF记录进行逐一匹配，发现有相同的时态RDF三元组且时间上并不是有间隔的就说明存在不一致性。用R代表（s，p，o）[start，end]）是一条时态RDF数据记录，Ri表示第i条记录，Ri+1就是下一条记录。

算法2 检测时态RDF数据是否存在三元组重复的不一致性

修复重复三元组不一致性，首先在时态RDF数据库中的记录中匹配（s，p，o）三元组，找到三元组完全一样的时态RDF数据记录，再通过比较两个时间区间的起始时间点R1.start、R2.start和结束时间点R1.end、R2.end，计算出要修改的时间区间，对一条记录的兩个时间点进行修改，再删除另外一条记录。

3.3 生命区间的不一致性

父节点s和子节点o连接的边e，但是这条边是有效时间Te超过了父节点的生命区间lf（s）就是存在不一致性。

只有主体s存在，主体s的p属性值为o的信息才会有意义，否则就是与事实不一致。

检测时态RDF数据是否存在生命区间的不一致性，要对每一个节点都要进行检测，对比节点的所有边的有效时间和节点的生命区间，有一个边的有效时间超过了节点的生命区间，这个节点就存在生命区间的不一致性，时态RDF数据就存在生命区间的不一致性。只有所有节点都不存在不一致性，时态RDF数据才不存在生命区间的不一致性。

4 實验结果

本节是对上文中提出的时态RDF数据的不一致性监测和修复上进行了实验验证，在LUBM（Lehigh University Benchmark）标准数据集的基础上随机生成有效时间添加时间标签，在对不同数量的数据集上分别进行了实验，并进行对比和说明，实验环境如表1所示。

LUBM是关于1000所高校的RDF数据，为了得到时态RDF数据，为每个RDF三元组随机生成整数来表示有效时间标签，分别对不同数量的数据进行不一致性检测和修复。

时态RDF数据存储在phpmysql的test数据库中，以共建立了三张表，其中URI表将所有的RDF三元中的s、p、o的URI用节点名ID表示。TRDF表中osp表示的是RDF三元组的主体、属性和客体。Start和end是有效时间的两个时间端点，随机生成时，要求end>start即可。Attribute and lifespan表中ID就是代表RDF三元组中的spo的URI对应的节点ID。生命区间是要计算的，初始化都为0。

首先检测500条时态RDF数据的不一致性，节点内容包括节点的ID和节点的生命区间lf.start和lf.end。首次计算节点的生命区间，集合节点的所有入边和出边的有效时间。在500条记录的基础上添加新的纪录就会产生不一致性。如图1所示增加500条后出现的不一致性条数，修改后就不会存在不一致性的数据。

每增加1 000条时态RDF数据，产生的每一种不一致性是在逐渐增加的，因此数据量很大时，对于存在的不一致性数据需要进行修复。生命区间的不一致性产生的数量最多也是因为一开始计算节点的生命区间只有500条时态数据，对于后续添加的有效时间又是随机产生，超过节点的生命区间的可能性也就很高了。

5 总 结

针对RDF三元组添加有效时间的时间标签来表示的时态RDF数据，并进行了在有效时间上的不一致性研究和分析，提出了两种类型的不一致性，分别是三元组重复的不一致性和生命区间的不一致性，对于两种类型的不一致性分别进行检测和修复。

未来工作：1.时态RDF数据会时常更新，对于每次更新都要进行检测和修复不一致性消耗太大，检测和修复不一致性算法的效率还有待提高。2.对于支持有效时间的时态RDF数据之间的推理、蕴含等内置函数和数据间关系和结构都没有讨论和研究。3.对有效时间的确定与验证没有进行讨论，对于不确定时间的处理也需要另行研究。

参考文献

[1] SWICK R R.Resource description framework（RDF）model and syntax specification W3C recommendation[M].[S1]：W3C Recommendation World Wide Web Consortium，2009.

[2] BERNERS-LEE T，HENDLER J，LASSILA O.The semantic Web.Scientific American，2001，284（5）：34—43

[3] HURTADO C，VAISMAN A.Reasoning with Temporal Constraints in RDF.In PPSWR Workshop，164—178，2006，4187：164-178.

[4] 汤庸.时态数据库导论[M].北京：北京大学出版社，2004

[5] 陈秀万，吴欢，李小娟，等.基于事件的土地利用时空数据模型研究[J].中国图象图形学报，2003：8（8）：957—963

[6] 辜炜东，汤庸，王路帮，等.事务数据库中的时态信息挖掘[J].计算机工程与应用，2004：40（18）：174—177

[7] BOHLEN M H，JENSEN C S，SNODGRASS R T.Evaluating and Enhancing the Completeness of TSQL2[R].TR 95-5.Computer Science Department，University of Arizona.

[8] DYLLA M，SOZIO M，THEOBALD M：Resolving Temporal Conflicts in Inconsistent RDF Knowledge Bases，2011.

[9] RIZZOLO F，VAISMAN A A.Temporal XML：modeling，indexing，and query processing [J].VLDB Journal，2008，17（5）：1179—1212.

[10] TANSEL A，CLIFFORD J，GADIA EDS S.Temporal Databases：Theory，Design and Implementation，Benjamin/Cummings，1993.

[11] CHAWATHE S，ABITEBOUL S，WIDOM J. Managing historical semistructured data[J]. Theory and Practice of Object Systems，1999，5（3）：143—162.

[12] Hurtado L C，Gutiérrez C，Vaisman A.Temporal RDF [J].2014.

[13] PUGLIESE A，UDREA O，SUBRAHMANIAN V S.Scaling RDF with time [C]// Proc of the 17th international conference on World Wide Web.2008：605—614.

[14] UDREA O，RECUPERO D R，SUBRAHMANIAN V S.Annotated RDF [J].ACM Trans on Computational Logic，2010，11（2）：10.