海量RDF数据的管理.pdf

海量RDF数据的管理.pdf

《海量RDF数据的管理.pdf》由会员分享，可在线阅读，更多相关《海量RDF数据的管理.pdf（16页珍藏版）》请在冰点文库上搜索。

6海量海量RDFRDF数据数据的的管理管理邹磊，陈跃国1.语义网和语义网和RDF数据数据语义网是万维网之父蒂姆伯纳斯-李（TimBerners-Lee）在1998年提出的概念，它提供了一种在不同的应用和个体之间共享和重用数据的整体框架1，其核心是构建以数据为中心的网络，即WebofData。

我们将目前的万维网称之为WebofPages。

众所周知，万维网是利用超链接技术将不同的文档链接起来，从而方便用户的浏览和文档的共享。

例如HTML文档的语法在于告诉浏览器按照何种格式来显示该文档，而并不是告诉计算机文档中的数据分别表示什么语义信息。

语义网的核心是让计算机能够理解文档中的数据,以及数据和数据之间的语义关联关系，从而使得机器可以更加智能化地处理这些信息。

因此我们可以把语义网想象成是一个全球性的数据库系统，也就是我们通常所提到的WebofData。

由于语义网技术涉及面较广，本文仅涉及语义网框架中的一项核心概念RDF（ResourceDescriptionFramework，资源描述框架）。

RDF是一种数据模型，是由W3C组织的ResourceDescriptionFramework工作组为了构建一个综合性的框架来整合不同领域的元数据，实现Web上互相交换元数据，促进网络资源的自动化处理而提出的。

随着因特网的发展和信息的丰富，对元数据的研究逐步深入，出现了多种元数据标准，如DC3（DublinCore）、PICS5（PlatformofInternetContentSelection）等等。

这些元数据描述、组织和重新整理了网络信息，使得用户可以更方便地利用网络数据。

RDF6是W3C于1999年提出的一个解决方案，并于2004年2月正式成为W3C推荐标准。

RDF的目标是为元数据在Web上的各种应用提供一个基础架构，使应用程序能够在Web上互相交换元数据，促进网络资源的自动化处理。

RDF的基本数据模型包括了三个对象类型，资源（Resource）、属性（Property）及陈述（Statements）。

资源资源：

所有能够使用RDF表示的对象都称之为资源，包括所有网络上的信息、虚拟概念、现实事物等等。

资源以唯一的URI（统一资源标识UniformResourceIdentifiers，通常使用的URL是它的一个子集）来表示，不同的资源拥有不同的URI。

属性属性：

属性描述资源的特征或资源间的关系。

每一个属性都有其意义，用于定义资源在属性上的属性值（PropertyValue）、描述属性所属的资源形态、和其他属性或资源的关系。

陈述陈述：

一条陈述包含三个部分，通常称之为RDF三元组。

其中主体一定是一个被描述的资源，由URI来表示。

客体表示主体在属性上的取值，它可以是另外一个资源（由URI来表示）或者是文本。

总的来说，RDF是语义网框架中的基础数据模型。

要实现从WebofPages到语义网所提出的WebofData的转变，构建海量和分布式的RDF数据集是一项重要而且是不可或缺的步骤，为此W3C组织提出了LinkedOpenData（LOD）项目7将各个零散的RDF数据集链接起来从而构成未来语义网7的基础。

目前的LOD项目已经从2009年的89个数据集增长到2012年的325个数据集，总规模超过了250亿条三元组。

RDF数据的获取和构建目前有人工编辑，和基于信息抽取方法构建和基于Web2.0的协同编辑三种方法。

传统的人工编辑只限定于单个领域的小规模RDF数据的构建；基于目前信息抽取技术，可以实现自动地从大规模非结构化数据中抽取和构建开放领域的RDF数据。

例如Barton8抽取自MIT图书馆数据，YAGO9和DBpeida10都是从维基百科上通过信息抽取的方法来构建RDF数据集合；另外利用类似于维基百科的协同编辑方法，由一个网络社区的用户共同构建一个RDF数据集也是构建高质量RDF数据的一种可行的方法，典型的项目例如Freebase11等。

2.RDF数据管理研究现状数据管理研究现状目前海量RDF数据的存储和查询的方案分为两种：

一种是将三元组数据映射成关系数据库中的表结构，利用现有的RDBMS（关系数据库系统）来完成面向RDF查询检索；另外一种是基于图结构的存储方式。

因为RDF数据本身就是基于图结构的，因此可以利用图数据库中的操作来完成对于RDF数据的查询。

我们首先在2.1节介绍面向RDF的查询语言SPARQL,同时引入一个SPARQL查询的例子。

在2.2节中将详细介绍基于关系模型的存储和检索RDF数据的几种代表性的方法。

2.3节将介绍现有基于图模型的RDF数据的管理方法。

2.1SPARQL查询语言查询语言SPARQL查询语言是由W3C的“RDFDataAccess”工作组（DAWG）开发的一种面向RDF数据的查询语言，目前已经成为W3C的RDF查询语言的推荐标准。

SPARQL语言与目前关系数据库中的SQL语言是很相近的，这方便了用户对于SPARQL语言的使用。

例如在SPARQL语法中，也是在SELECT部分指定查询变量，在WHERE部分指定查询条件，而查询条件通常由三元组来构成，其中三元组的某一项或者某几项可以由变量来表示。

我们用一个例子来介绍SPARQL，具体的语法细节请参考文献20。

主体属性客体y:

Abraham_LincolnhasName“AbrahamLincoln”y:

Abraham_LincolnBornOnDate“1809-02-12”y:

Abraham_LincolnDiedOnDate1865-04-15y:

Abraham_LincolnDiedIny:

Washington_D.Cy:

Washington_D.ChasName“WashingtonD.C.”y:

Washington_D.CFoundYear1790y:

United_StateshasName“UnitedStates”y:

United_StateshasCapitaly:

Washington_D.Cy:

United_Statesrdf:

typeCountryy:

Washington_D.Crdf:

typey:

cityy:

Reese_Witherspoonrdf:

typey:

Actory:

Reese_WitherspoonBornOnDate“1976-03-22”y:

Reese_WitherspoonBornIny:

New_Orleans,_Louisianay:

Reese_WitherspoonhasName“ReeseWitherspoon”y:

New_Orleans,_LouisianaFoundYear1718y:

New_Orleans,_Louisianardf:

typey:

cityy:

New_Orleans,_LouisianalocatedIny:

United_StatesPrefix:

y=http:

/en.wikipedia.org/wiki/图1RDF例子8图1给出了一个RDF数据集的例子。

假设我们需要在上面的RDF数据中查询“在1809年2月12日出生，并且在1865年4月15日逝世的人的姓名？

”这个自然语言的问题，可以表示成如图2的SPARQL语句。

SELECT?

name/查询返回的变量值WHERE?

m?

name./查询条件?

m“1809-02-12”.?

m“1865-04-15”.图2SPARQL查询的例子我们也可以将RDF和SPARQL分别表示成图的形式。

例如在RDF中，主体和客体可以分别表示成RDF图中的节点，一条RDF三元组可以表示成一条边，其中属性是边的标签。

SPARQL语句同样可以表示成一个查询图。

图3显示了上例所对应的RDF图和SPARQL查询图结构。

回答SPARQL查询本质上就是在RDF图中找到SPARQL查询图的子图匹配的位置，这就是基于图数据库的回答SPARQL查询的理论基础。

hasNameBornOnDateDiedOnDateDiedIn“AbrahamLincoln”“1809-02-12”“1865-04-15”http:

/en.wikipedia.org/wiki/Abraham_Lincolnhttp:

/en.wikipedia.org/wiki/Washington_D.C.FoundYear“1790”“WashingtonD.C.”hasNamehttp:

/en.wikipedia.org/wiki/United_StateshasCapitalhttp:

/en.wikipedia.org/wiki/Countryrdf:

typehttp:

/en.wikipedia.org/wiki/Cityrdf:

typehttp:

/en.wikipedia.org/wiki/Reese_Witherspoonhttp:

/en.wikipedia.org/wiki/New_Orleans,_LouisianalocatedInhttp:

/en.wikipedia.org/wiki/Actor“1976-03-22”BornOnDaterdf:

typeBornInFoundYear“1718”rdf:

type005008004003006001007002“UnitedStates”hasName“ReeseWitherspoon”hasName009010011012013014015016017?

m“1809-02-12”?

name“1865-04-15”BornOnDateDiedOnDatehasName（a）RDF图（b）SPARQL查询图图3RDF图和SPARQL查询图2.2基于关系数据模型基于关系数据模型的方法的方法由于RDBMS在数据管理方面的巨大成功以及成熟的商业软件产品，同时RDF数据的三元组模9型可以很容易映射成关系模型，因此大量研究者尝试了使用关系数据模型来设计RDF存储和检索的方案21,22,23。

根据所设计的表结构的不同，相应的存储和查询方法也各异，下面介绍几种经典的方法。

简单三列表简单三列表一种最为简单的将RDF数据映射到关系数据库表的方法是构建一张只有三列表（Subject，Property，Object），将所有的RDF三元组都放在这个表中。

给定一个SPARQL查询，我们设计查询重写机制将SPARQL转化为对应的SQL语句，由关系数据库来回答此SQL语句。

例如我们可以将图2中的SPARQL查询转换为图4中的SQL语句。

SELECTT3.SubjectFROMTasT1,TasT2,TasT3WHERET1.Property=“BornOnDate”andT1.Object=“1809-02-12”andT2.Property=“DiedOnDate”andT2.Object=“1865-04-15”andT3.Property=“hasName”andT1.Subject=T2.SubjectandT2.Subject=T3.subject图4转换以后的SQL查询虽然这种方法具有很好的通用性，但最大的问题是查询性能差。

首先这张三列表的规模可能非常庞大。

如图4所示的SQL语句中有多个表的自连接操作，将严重地影响其查询性能。

水平存储水平存储文献24中提到的水平方法（HorizontalSchema）是将一个RDF主体（subject）表示为数据库表中的一行。

表中的列包括该RDF数据集合中所有的属性。

这种的策略的好处在于设计简单，同时很容易回答面向某单个主体的属性值的查询，如图5所示。

hasNameBornOnDateDiedOnDateDiedInFoundYearrdf:

typehasCapitallocatedInSubjectAbrahamLincoln1809-02-121865-04-15y:

Washington_D.Cy:

Abraham_LincolnWashingtonD.C.1790y:

cityy:

Washington_D.CUnitedStatesy:

countryy:

Washington_D.Cy:

United_StatesReeseWitherspoon1976-03-22y:

actory:

Reese_WitherspoonbornIny:

New_Orleans,_Louisiana1718y:

cityy:

United_Statesy:

New_Orleans,_Louisiana图5.水平存储10根据图5表的结构，为了回答图2中的SPARQL查询，可以转换为下面的SQL语句。

与图4比较，下面的SQL语句没有耗时的连接操作，因此其查询效率要远高于图7中的SQL语句。

SELECThasNamefromTWHEREBornOnDate=“1809-02-12”andDiedOnDate=“1865-04-15”.图6水平存储上的SQL查询然而这种水平存储方法的缺点也是很明显的24,25：

其一，表中存在大量的列。

一般来讲属性数目会比主体和属性值的个数少很多，但是还是有可能超过当前数据库能够承受的数量。

其二，表的稀疏性问题。

通常一个主体并不在所有的属性上有值。

相反，主体仅仅在极少量的属性上有值。

然而由于一个主体存成一行，那么表中将存在大量空值。

空值不仅增加了存储负载，而且带来了其他的问题，比如增大了索引大小，影响查询效率，文献24,25,26详述了空值带来的问题。

其三，水平存储存在多值性的问题。

一个表中列的数量是固定的，这就使得主体在一个属性上只能有一个值。

而真实数据往往并不符合这个限制条件。

其四，数据的变化可能带来很大的更新成本。

在实际应用中，数据的更新可能导致增加属性或删除属性等改变，但是这就涉及到整个表结构的变化，水平结构很难处理类似的问题。

属性表属性表属性表是将三元组根据属性分类，每一类采用水平存储策略的数据库表。

属性表在继承了水平存储策略优势的基础上，又通过对相关属性的分类避免了表中列数过多等问题。

Jena227,28中使用属性表以提高对RDF三元组的查询效率。

研究者提出了两种不同的属性表，其一称为聚类属性表（clusteredpropertytable），另一类称为属性类别表（property-classtable）。

y:

New_Orleans,_Louisiana1718y:

cityPrefix:

y=http:

/en.wikipedia.org/wiki/SubjecthasNamey:

Abraham_Lincoln“AbrahamLincoln”BornOnDate1809-02-12DiedOnDate1865-04-15DiedIny:

Washington_D.CBornIny:

Reese_Witherspoon“ReeseWitherspoon”1976-03-22y:

Washington_D.Cy:

New_Orleans,_Louisianardf:

typey:

ActorSubjectFoundYearrdf:

typey:

United_StateslocatedIny:

Washington_D.C1790y:

cityy:

United_StateshasName“WashingtonD.C.”PeopleCityy:

United_States“UnitedStates”SubjecthasNamey:

Washington_D.ChasCapitalCountryrdf:

typeCountry图7.聚类属性表。

11聚类属性表将概念上相关的属性聚成一类，每一类定义一个单独的数据库表，使用水平方式存储这些三元组。

如果有一些三元组不属于任何一个类别，它们被放在一张剩余表（left-overtable）中。

在图5中，根据属性的相关性，将所有的属性聚类成三个类，每个类用一张水平表来存储。

同样的，根据图7给出的属性表结构，我们也可以将图3中的SPARQL查询转换成类似于图6的SQL语句。

属性类别表将所有的实体按照rdf:

type来分类，每一类用一个张水平表来表示。

这种组织方式要求每个实体都必须有一个rdf:

type属性。

属性表最主要的优点在于可以减少查询时主体-主体间的自连接代价，这样可以极大地提高查询效率。

属性表的另外一个优点在于由于与一个属性相关的属性值存储在一列中，就可以针对该列的数据类型设计一些存储策略来减少存储空间。

这样就避免了三元组存储策略中由于数据类型不同的属性值存储在一列中造成存储上的不便。

Jena2等的研究工作以及其他的一些研究工作证明了属性表的有效性，但属性表也有着先天性的缺陷，这使得除了某些特殊应用以外，属性表的应用并不广泛。

其一，文献29指出，虽然属性表对于某些查询能够提高查询性能，但是大部分的查询都会涉及多个表的连接或合并操作。

对聚类属性表而言，如果查询中属性作为变量出现，则会涉及多个属性表；对属性分类表而言，如果查询并未确定属性类别，则查询会涉及多个属性表。

在这种情况下，属性表的优点就较不明显了。

其二，RDF数据由于来源庞杂，其结构性可能较差，从而属性和主体间的关联性可能并不强，类似的主体可能并不包含相同的属性。

这时，空值的问题就出现了。

数据的结构性越差，空值的问题就越发明显。

其三，在现实中，一个主体在一个属性上可能存在多值。

这时，用RDBMS管理这些数据时就带来麻烦。

其中，前两个问题是相互影响的。

当一个表的宽度减小时，对结构性要求较低，空值问题得到缓解，但查询会涉及更多的表；而当表的宽度加大时，如果数据结构性不强，就会出现更多空值的问题29。

二元存储二元存储Abadi等人29以一种完全的分解存储模型（DSM30，DecomposedStorageModel）为基础，将DSM引入了语义网数据的存储，提出了垂直分割技术。

在垂直分割的结构下，三元组表被重写为N张包含两列的表，N等于RDF数据中属性的个数。

每一张表都以相对应的属性为表名，其第一列是所有在这个属性上有属性值的主体，第二列是该主体在这个属性上的值。

每一张表中的数据按照主体进行排序，从而能够迅速定位特定主体，而且将所有涉及主体-主体的表连接转换为可以迅速完成的排序合并连接（MergeJoin）。

在对存储空间限制较少时，也可以对属性值这一列建立索引或对每个表建立一个按照属性值排序的副本，以提高涉及对特定属性值的访问和属性值-主体、属性值-属性值连接的性能。

如图8中显示了将图1中的RDF数据集分解成8个二元表，并且每个二元表按照主体进行12排序。

hasNameSubjectObjecty:

Abraham_Lincoln“AbrahamLincoln”y:

Washington_D.C“WashingtonD.C.”y:

Reese_Witherspoon“ReeseWitherspoon”BornOnDateSubjectObjecty:

Abraham_Lincoln“1809-02-12”y:

Reese_Witherspoon“1976-03-22”DiedOnDateSubjectObjecty:

Abraham_Lincoln“1865-04-15”DiedInSubjectObjecty:

Abraham_Lincolny:

Washington_D.CFoundYearSubjectObjecty:

Washington_D.C1790y:

New_Orleans,_Louisiana1718rdf:

typeSubjectObjecty:

Washington_D.Cy:

cityy:

United_StatesCountryy:

Reese_Witherspoony:

Actory:

New_Orleans,_Louisianay:

cityBornInSubjectObjecty:

Reese_Witherspoony:

New_Orleans,_LouisianaLocatedInSubjectObjecty:

New_Orleans,_Louisianay:

United_StatesPrefix:

y=http:

/en.wikipedia.org/wiki/y:

United_States“UnitedStates”图8.二元垂直分割表相比较于三元组存储，这种二元存储方式有如下的优点：

由于属性名不再重复出现，因此有效地减少了存储空间。

在查询时，只需要处理涉及查询条件的表，从而有效地减少了I/O代价。

相比于属性表方式，垂直分割的优点在于以下几条。

垂直分割适应于多值数据。

如同三元组存储方式一样，当一个主体在一个属性上有多个属性值时，只需要将其存储为多行即可。

垂直存储也很适用于结构化较差的数据，如果一个主体未定义某个属性，那么这个记录就不会在这种存储方式中出现，避免了空值的产生。

二元存储技术不需要对属性进行聚类，就不需要寻找好的聚类算法。

在查询时，如果属性名被限定，那么查询的内容就不会出现在多个表中，减少了合并操作。

SW-Store29利用了垂直分割技术，更进一步的还减少了主体存储的冗余。

但垂直分割技术同样存在着缺点。

首先，这种存储方式增加了表连接的运算数。

即使这些连接都是时间代价较低的合并连接，总的运算代价也是不可忽略的。

其次，表的增多增加了数据更新的难度。

对一个主体的更新需要涉及多个表，就可能因为外存存储方式的影响增加I/O代价。

当表上存在索引时，更新代价更是相当昂贵。

另外，文献31,32认为在多个表中存储结构化不强的数据（如某些RDF数据集）会存在一些问题，将多个表返回的结果重构成一张视图所进行的运算可能代价较高。

他们建议将较稀疏、结构化较差的数据存储于一张表中，并对存储结构加以描述。

13全索引策略全索引策略如前所述，简单的三列表存储的缺点在于自连接次数较多。

为了提高简单三列表存储的查询效率，目前一种普遍被认可的方法是“全索引（exhaustiveindexing）”策略，例如RDF3x33和Hexastore34。

列举三列表的所有排列组合的可能性（6种），并且按照每一种排列组合建立聚集B+-树。

建立这样全索引的好处有两点：

其一，对于SPARQL查询中的每个查询三元组模式，都可以转换成对于某个排列组合上的范围查询。

例如?

m“1809-02-12”这个查询三元组模式，可以转换为对于（P,O,S）排列上的范围查询。

因为在（P,O,S）排列中，所有P,O为和“1809-02-12”的三元组都连在一起。

其二，全索引的好处在于可以利用归并连接（MergeJoin）降低连接的复杂度。

我们知道嵌套循环（NestedLoopJoin）连接的复杂度是O（|L1|*|L2|），这里|L1|和|L2|分别表示两个待连接列表的长度。

然而归并连接的复杂度是O（MAX（|L1|,|L2|）。

例如从（P,O,S）排列中可以得到满足?

m“1809-02-12”查询条件的?

m的取值，并且这些取值按照顺序进行排列。

同样的，从（P,O,S）排列中也可以得到满足?

m“1865-04-15”查询条件的?

m的取值，并且这些取值也按照顺序进行排列。

通过归并排序，我们可以很容易找到同时满足这两个查询条件的?

m的取值。

虽然用全索引策略可以弥补一些简单垂直存储的缺点，但三元存储方式难以解决的问题还有很多。

其一，不同的三元组其主体/属性/属性值可能重复，这样的重复出现会浪费存储空间。

其二，复杂的查询需要进行大量表