关联数据的动态链接维护研究

[摘要]　分析关联数据集之间链接的动态性，在此基础上探讨三种动态链接维护方法。基于WOD－LMP协议的方法要求链接双方都遵守WOD―LMP协议。基于更新通知的方法适用于目标数据集具有数据更新通知机制的情况，需要针对目标数据集的数据更新通知机制采取相应的更新数据获取方法。基于主动监测机制的方法对目标数据集的要求较低，只需要提供SPARQL查询接口或支持RDF堆下载即可。

[关键词]　关联数据　动态链接　链接维护　WOD-LMP协议　更新通知

1　引言

关联数据(1inked data)是指根据一定的原则进行组织并到Web上的数据，它遵循RDF和SPARQL标准并包含与外部数据之间的链接(1ink)，可以直接通过HTTP／URI机制进行获取。一些政府数据和学术资源已被转换为关联数据，部分图书馆也在进行这方面的尝试。通过链接将不同的数据集关联起来，是关联数据技术应用最大的价值所在。大量已公开的关联数据集彼此之间已经建立了各种类型的链接(下文中的数据集指的是关联数据集，数据集之间的链接指的是数据集资源之间的链接)，一些综合性的数据集更是成为其他众多应用系统和数据集的链接对象，例如，从LOD云图中可以发现，链接到DBpedia的数据集多达63个。随着数据集的不断增多，不同数据集之间的链接关系将会越来越复杂。任何一个数据集的状态发生变化，哪怕是单个三元组层面上的变化，都可能导致与之相链接的其他数据集发生访问故障，因此，数据集之间的链接关系建立之后，对这些动态变化的链接(即动态链接)进行及时、有效的自动维护，是发挥关联数据的作用、体现关联数据价值的重要保证。

2　链接的动态性分析

链接的动态性是指数据集之间的链接状态是动态变化的。数据集的动态性直接决定了链接的动态性，数据集之间链接类型的多样性则在一定程度上增强了链接的动态性。

2.1　数据集的动态性

根据资源的更新频率和幅度来划分，数据集大致有静态、准静态、半动态、天然动态等几种类型，其动态性依次增强。静态型数据集基本不再变化但可能偶尔有所更新，动态性最弱。天然动态型数据集的更新频率和幅度都较大，更新的类型也较多，动态性最强，例如，2008年10月至2009年5月，Dbpedia中person类资源增加、移动、删除的数量分别多达49 325、2 841、20 561，此外还有很多资源被修改。

2.2　链接类型的多样性

链接类型一般与资源类型有关，通过对DBpedia、DBLP、Geo Names等数据集的分析发现，常见的资源类型主要有person、place、work、species、organization等，相应地，也存在多种不同的链接类型，如表1所示：

表1仅列出最常用的几种链接类型。实际上，数据集之间的链接类型还有很多，可来自已知的词汇表和元素集，如dc：isPartOf、dc：isReferencedBy、SCOVO：di―mension等，也可以来自自定义的词汇表和元素集。

2.3　链接的动态性

链接的动态性与数据集的动态性之间有直接的关系，可从宏观与微观两个层面来分析。

2.3.1　宏观层面设源数据集为s、目标数据集为D，链接的动态变化情况如表2所示：

其中“s―D链接”表示s至D的整体链接情况，由s中所有资源到D中所有资源的全部链接构成。

2.3.2　微观层面设s中存在一个资源si，D中存在一个资源Dj，链接的动态变化情况如表3所示：

其中“不变”是指sj至Dj的有向链接(用si―Dj链接表示)保持不变，“消失”是指因si发生变化所引起的si―Dj链接不复存在，“断链”是指因Dj发生变化所引起的si―Dj链接不复存在，“Dj移动”是指出于某种考虑重新为Dj分配URI，“Dj修改”是指在不改变URI的情况下对Dj的属性及其值进行增、删、改等操作。

链接的动态性与链接类型的多样性之间也有一定的关系。s至D的链接类型越多，则链接个数也可能越多，从而导致：①当D中有资源被删除或被移动时，出现断链的机会也越多；②当s中的资源被删除或修改时，出现链接消失的可能性也越大。

3　动态链接维护方法

关联数据链接的状态主要有5种：初态、不变、消失、断链、新链接。S―D链接建立后，需要采取一定的方法对其进行维护，包括及时修补断链、删除已消失的链接、建立新链接等。

3.1　基于WOD-LMP协议的动态链接维护

WOD-LMP协议(web of data link maintenance pro。toc01)是专用的关联数据链接维护协议，该协议的消息传递机制允许用5种方法在s和D之间传递5类消息，其中linkNotification()方法用来将s生成的S―D链接信息传递给D，linkDeletionNotification()方法用来将s删除的SD链接信息传递给D，ehangeNotifica.tion()方法用于D将s所订阅资源的变化情况通知S，getChanges()方法用于s从D中获取所有更新数据。

利用WOD-LMP协议可以实现关联数据的动态链接维护，其基本原理是：①外部数据监测模块监视位于D中的已订阅资源的变化情况。在初次建立S--~D链接时，该模块通过linkNotification()方法将s与D之间的链接情况通知D，其中包括订阅D中哪些资源(用子集Ds表示)的变化信息。每当接收到D发送来的changeNotification()通知，该模块则针对DS中被删除的资源，删除相应的断链；针对DS中被修改的资源，重新计算s与该资源的链接。②外部数据监测模块监视位于D中的非订阅资源的变化情况。该模块可以主动地利用getChanges()方法从D中获取在指定时间段内发生变化的资源集合C，并由链接维护模块重新计算s至C-DS中资源之间的链接。③本地数据监测模块动态监视s中的资源变化情况。当发现某个资源被删除时，通过linkDeletionNotification()方法将链接消失情况通知D。当发现某个资源被修改时，则由链接维护模块重新计算该资源与D中所有资源的链接，并通过linkDeletionNotification()方法和linkNotifieation()方法将链接变化情况通知D。如图1所示：

例如，s可向支持WOD―LMP协议的数据集省略发送如下链接通知：linkNotifica-tion(“省略／sparql”，LinkList.toLinks(“http：／／localhost：8080／resource／John Smith”，

“example.or／resource／John―H―Smith”，“owl：sameAs”，true)，表示与其资源省略∥resource／John―H―Smith建立了owl：sameAs类型的链接，其中参数值true表示订阅了该资源。当省略删除该资源时，向S发送通知：ehangeNotification(93，ChangeList.toChanges(“省略／resource／John H Smith”，“de1ete”)。S接收通知并删除断链后，再向省略发送如下链接删除通知：linkDeletionNotification(LinkList.toLinks(“http：／／localhost：8080／resource／John―Smith”，“省略／resource／John H Smith”，“owl：sameAs”)。

基于WOD-LMP协议的动态链接维护方法是较为理想的方法，但需要链接的双方都遵守相同的协议。此外，支持WOD-LMP协议的目标数据集需要保存、维护来自不同源数据集的订阅信息，并及时将订阅资源的变化情况反馈给源数据集，在一定程度上增加了目标数据集的负担。

3.2　基于更新通知的动态链接维护

3.2.1　Triplifv更新日志方法

该方法按年、月、日、时、分、秒等时间粒度来产生更新日志，形成嵌套的更新集，并为每个更新集提供一个URI，以便关联数据消费者使用。

3.2.2　sparqlPuSH方法　该方法通过sparqlPuSH接口对客户端提交的SPARQL请求进行登记，并将该请求提交给PuSH服务器。每当数据集发生变化时，sparqlPuSH接口自动重新运行所有已登记的SPARQL请求，并将结果集发生变化的SPARQL请求及其变化情况通知PuSH服务器，由PuSH服务器通过PubSub.Hubbub协议向所有相关的客户端发出广播通知。

3.2.3　DBPedia Live方法　DBPedia Live是DBpedia的扩展，用于解决Wikipedia每日数以万计的资源更新问题，为关联数据消费者实时提供Wikipedia最新的更新信息。

3.2.4　PingTheSemanticWeb方法　该方法采用了基于集中登记策略的更新通知机制。RDF数据拥有者可以在PingTheSemanticWeb.con平台上自己的RDF文档或RDF更新文档。用户可以导入这些以XML或N3／Turtle格式存在的RDF文档。

上述各种方法只是针对数据集的变化情况发出更新通知，其本身并不能解决数据集之间的动态链接维护问题。源数据集s可以利用这些方法来获取目标数据集D的更新数据，并在此基础上进行动态链接维护，基本原理如下(以Triplify更新日志方法为例，如图2所示)：

获取更新数据。选择合适的时间粒度，由外部数据监测模块通过HTrP协议从D的更新日志中获取所需的更新数据。

根据更新数据进行链接维护。更新数据中一般只包含新增资源和修改的资源。对于新增资源，链接维护模块需要考察s中所有资源与它们之间的关系，尝试建立新链接。对于修改的资源，虽然其在D中的URI不变，不会导致断链，但由于存在增加了新属性、删除或修改了原有属性等情况，需要重新计算s中所有资源与它们之间的链接。

对于更新数据中没有出现但已被删除或移动的资源，由外部数据监测模块定期测试s中客体指向D的所有三元组的连通情况，一旦发现断链即将该三元组予以删除。

本地数据监测模块动态监视s中的资源变化情况。发现某个资源被修改时，重新计算该资源与D中相应资源(即原有链接所指向的资源)或所有资源的链接。发现某个资源被移动时，保持原有的链接状态不变。对于被删除的资源，其与D的所有链接自动消失。

例如，当从支持Triplify方法的数据集http：／／wn／vw.省略中获取更新数据时，URI为省略／Triplify／update／201 1／Jan／03／2I／06／22的更新集将返回2011―01―03 21：06：22时更新的三个资源：

update：updatedResource 省略／resource／Tim Berners_Lee；

update：updatedResource example.or#resource／Christian Bizer；

update：updatedResource example.or#resource／Jennifer Bowen。

在进行链接维护时，可重新计算本地数据集中所有资源与上述三个资源之间的链接。

基于更新通知的动态链接维护方法不要求目标数据集遵循规定的链接维护协议，只要能以某种方法资源更新通知即可，在一定程度上降低了对目标数据集的要求。但该方法存在以下不足之处：①增加了源数据集一端的负担。外部数据监测模块需要针对不同目标数据集的更新通知方法，分别采取不同的对策来获取更新数据。目标数据集和更新通知方法越多，链接维护系统则越复杂。②链接维护系统的适应性较差。对于新的目标数据集，当其更新通知方法与系统已处理过的现有方法不同时，不能直接利用现有的系统来获取更新数据，需要对其进行相应的功能扩充。

3.3　基于主动监测机制的动态链接维护

如果目标数据集D既不遵循已知的链接维护协议(如WOD―LMP)，也没有更新通知机制，则源数据集S只能通过主动监测D中资源变化的方法来进行链接维护。Haslhofer等已进行了相关的研究，所提出的DSNotify方法可以检测和修复关联数据集之间的部分断链。该方法主要考虑由于D中资源的删除、移动所导致的断链情况，忽略了由于资源的修改所引起的链接变化情况。

基于主动监测机制的链接维护方法以DSNotifv方法为基础，同时考虑s和D中资源的增加、删除、修改、移动等情况，基本原理如图3所示：

3.3.1　D的本地化处理根据D所提供的批量访问接口，采用SPARQL查询方法或RDF堆下载方法来提取所有的资源。从每个资源中抽取描述性特征，生成特征向量，并将所有资源的URI及特征向量保存在本地特征向量文档中。

3.3.2　主动监测D的变化情况　定期从D中重新获取所有资源，通过与本地特征向量文档的比较来发现D中资源的变化情况。比较时，综合考虑新获取资源

的URI，以及新获取资源与特征向量文档中资源之间的余弦相似度值，从而判断D中资源的增加、删除、修改、移动等情况。

3.3.3　根据D的变化情况进行链接维护　对于新增资源和被修改的资源，重新计算S中所有资源与这些资源之间的链接。对于被删除的资源，在s中删除所有与之相关的断链。对于被移动的资源，通过修改s中相关三元组的客体值(即将客体值改为移动后的资源URI)来修复断链。

3.3.4　本地数据监测模块动态监视S中的资源变化情况基本过程和方法参见基于更新通知的动态链接维护方法的相应部分。

例如，2009年12月20日，笔者通过关联数据集http：／／moseley.省略的SPARQL端口http：／／api.省略／stores／moselev／services／sparql获取了其全部资源，共l 284个三元组，合计155个资源。2011年3月5日再次获取其全部资源，共1 268个三元组，合计153个资源。通过特征向量比较发现，资源http：／／moseley.省略／artist／david―wafing和http：／／moseley.dataincubator，org／artist／maureen已被删除。s端在监测到这一变化情况后，可删除与这些资源相关的断链。

基于主动监测机制的动态链接维护方法对目标数据集的要求较低，而且对不同的目标数据集可以采取基本相同的处理方法，具有较强的适应性。但如果目标数据集的资源数量太大，则源数据集端的存储负担和处理负担会较重。此外还需要解决如下问题：如果主动监测频率远远小于目标数据集的更新频率，则源数据集端不能及时获悉目标数据集的变化情况，从而导致在一定的时间间隔内可能有大量的断链存在，因此，需要采用适当的方法来评估目标数据集的更新频率，据此来调整主动监测频率。

4　结语

对动态链接进行及时、有效的维护，是维系数据集之间链接关系的重要手段。本文在分析链接动态性的基础上，对三种类型的动态链接维护方法的基本原理进行了描述。第一种方法较为理想，但需要链接双方都遵守WOD-LMP协议；第三种方法的适应性较强，只要目标数据集提供SPARQL查询接口或支持RDF堆下载即可；第二种方法的适应性较差，需要针对不同的更新通知机制采取相应的更新数据获取方法。目前的研究处于理论探讨和少量样本数据试验阶段，下一步的工作将围绕以下两个方面来进行：①实验研究。选定一个适合用来做实验的目标数据集，在建立了本地数据集与该目标数据集之间的链接后，分别利用上述三种方法对所建立的链接进行维护实验。②评价。系统运行一段时间后，对三种动态链接维护方法的效果进行比较、评价，并针对可能存在的问题进行新一轮的修改、实验、评价。