基于关系数据库的RDF数据存储.doc

基于关系数据库的RDF数据存储陶导1 钱卫宁2 魏芳1 周傲英21 (复旦大学计算机科学与工程系，上海 200433)2 (华东师范大学海量计算研究所，上海 200062)()摘要 在语义网中，信息以及信息之间的关系使用元数据和本体库来表示，RDF和RDF Schema是W3C规定的用于表示元数据和本体的标准1。由于RDF数据具有图的结构特点，存储和查询比较复杂，没有一个统一的标准，因此如何有效的存储和查询RDF数据成为了研究的一个热点。本文讨论了RDF数据存储的难点和问题所在，提出了一个存储RDF数据的算法。基于LUBM生成的数据，我们设计了不同复杂度和结构的查询，以检验不同算法的查询和存储效率。在模拟数据和真实数据上的存储实验表明，采用该算法可以提高效率。关键词 RDF存储；RDF查询；相同谓词值优先搜索RDF Data Storage on Relation DatabaseTao Dao1, Qian Weining2, Wei Fang1 and Zhou Aoying21 (Department of Computer Science and Engineering, Fudan University, Shanghai 200433) 2 (Institute of Massive Computing, Software Engineering Institute, East China Normal University, Shanghai 200062) Abstract In the semantic web, information and the relation between them is represented by metadata and ontology. The Resource Description Framework (RDF) and RDF Schema is the standard for representing this information. Due to RDF datas graph structure, the storage and query of RDF data is complex and theres no standard method for this. In this paper, we discuss the problems in the storage and describe an algorithm of RDF storage. We design several queries that have different complexity based on the LUBM to evaluate the efficiency of different algorithms. Experiment on the real world data and virtual data shows that the algorithm we described has higher efficiency.Keywords RDF storage; RDF query; Same Predicate value first search1.简介RDF(Resource Description Framework),是一种用于描述Web资源的标记语言，它使用简单的数据模型来描述复杂的实体和实体间的关系2。RDF数据具有图的结构，随着RDF数据的日益增加，如何存储RDF这种图结构的数据成为了较为普遍的研究方向。随着RDF数据的广泛应用，其数据规模也日益庞大，RDF图的规模甚至达到数千万个节点。而且不同的RDF数据可以通过一些链接的方法合并成一个数据集，所以在实际应用中，我们经常会面对内存空间不足以载入所有RDF数据的情况，这导致了我们需要频繁的在外存和内存间交换数据来完成数据处理，从而使得数据交换成为整个处理过程的瓶颈。若使用文件存储，则每次数据读取都要将文件整个的读入，大大降低了效率。所以使用数据库存储是必然的选择。在存储的后台方面，使用关系数据库更有利于数据存储。因为关系数据库具有相当简单的结构，能很好的适应于RDF数据简单的数据模型。但在关系数据库中，所有的数据都被存放在一个或若干个表中，一定程度上破坏了图的结构。在执行查询的时候，需要取出大量的数据来重构图，尤其在处理复杂查询的时候，需要对表进行多次自联接运算(self-join)，显著的降低效率。所以现在使用关系数据库来存储RDF数据的主要问题在于，采用何种顺序或者结构将三元组放入数据库中，而且所采用的方法对存储以及查询的效率有何影响。不同方法在读取速度，存储开销，查询速度等方面各优劣。现存的存储方法主要有以下两大类别：l 按照文件结构逐条存储三元组。逐行读取文件，并且直接按照文件中的顺序存储三元组。在数据库中的排列顺序仅和三元组在文件中的排列顺序有关。l 按照逻辑结构切割图并存储。将文件读入内存，还原成图之后使用一定的分割算法把图切分后将子图存入数据库。三元组在数据库中的排列顺序和节点在图中的逻辑顺序有关。第一种方法典型的代表是Jena4和Redland5的数据存储部分，这类方法的优描一遍文件就可以完成存储过程。不足在于所有数据都存放在若干张很大的表中，并且相邻数据之间没有一定的逻辑关系，所以每次查询操作都可能导致需要对整张表进行自联接运算，查询和搜索效率比较低下。第二种方法例如6,7。按照分割算法的不同，切割后的子图可能是路径、树或者较小的RDF图，比起前一种方法该方法开销较大。由于这类方法按照一定的逻辑关系建立起图的索引，每次查询都只需要在一个较小的候选子图集中进行搜索比较，查询的效率比前一种方法高。本文的主要贡献在于：1)提出了三种不同的存储方法，并且从理论分析了其不同的存储效率，2)收集了不同规模的RDF数据集，并且针对数据设计了若干个不同复杂度的查询，3)在此基础上对不同的存储方法进行实验，得出其实际存储和查询效率。本文剩余章节组织如下，第二章介绍本文所使用的数据及其来源，并且设计了若干个查询来测试性能，第三章主要介绍了一种存储RDF数据的基本方法，并且做出相应分析，第四章为相关实验及其结论。2.存储方法由于RDF的本质是含有语义信息的图，因此大多数的查询语句也必然包含一定的语义信息。因此在存储的过程中尽量保留这样的信息显然可以提高查询的效率。但是过多的保留这样的信息会导致算法复杂性的提高，在面对大规模数据的时候缺乏灵活性。2.1 使用DFS方法存储三元组DFS方法，即在存储时时用深度优先搜索方法来遍历RDF图，并且根据遍历结果来进行存储的方法，可以避免以上所述的缺点。该方法执行顺序如下：首先从外存逐行读取文件并构造XML树T。再根据三元组主体和客体的值将文件中冗余的相同节点合并，还原成RDF图G(V,E)，V代表所有的节点(主体和客体)集合，E代表所有的边集合(谓词)。最后使用深度优先(DFS)的方法遍历图并将遍历到的三元组存储入数据库。该方法的优点在于，对于原始的RDF图，该方法仅需一次遍历，就可以完成分割与存储。而且在遍历过程中，并不需要额外的空间来执行算法。分割算法如图2.1。图G包含节点集合V和边集合E，G使用邻接表的方式保留在内存，每个节点v都保存其子女和父亲节点的指针，并且设置访问标志位，s为临时存储节点的栈。由于每一次深度优先搜索都会把遍历到的边从E中删除，当所有边被删除之后，所有的节点也相应的被删除，所以DFS(v)最多会被调用|E|次。每次调用的时候都会执行一次相应边的删除，复杂度平均为|E|/|V|。算法总复杂度为O(|E|2 / |V|)。DFS(G)while(V)v V.pick_up_random();while(v)v.visited();if (v has non-visited child v)store the triple has subject v and object v;remove the triple from Gs.push(v.child);v s.pop();图2.1 DFS方法算法2.2使用BFS方法存储三元组使用DFS方法可以减少存储的开销，但是在遍历过程中，节点被重复访问多次，一定程度上影响了算法的效率，而使用BFS(广度优先)的方法可以减少这一开销，BFS分割算法如图2.2，数据结构和DFS方法相同，其中l为单向的队列：BFS(G)while(V)vV.pick_up_random();while(v)v.visited();for all vs childrenstore all the triples have subject v;if(v.child.is_visited() = false)l.push(v.child);if(v.parent = null)V.remove(v);v l.pop();图2.2 BFS方法算法算法包含三个循环， while(V)和while(v)保证算法遍历到每一个节点。对于一个节点v，v在被访问过一次后就不再入队列，因此内层的循环体实际执行次数为O(|V|)，最内部循环体中需要找到当前节点v的所有子女节点，该部分复杂度和子女数目成正比，其平均值为|E|/|V|，其时间复杂度为O(|E| / |V|)。所以在不考虑数据库读写时间的情况下，算法总复杂度为O(|E|)。由于RDF图不存在孤立点，可得|E| |V|，所以该方法优于DFS方法。2.3 使用相同谓词值优先的方法改进使用BFS和DFS的方法能显著减少图切割和还原的时间开销，两种方法在还原整个RDF图时有着一些优势，但是对于特定的查询，例如取具有给定特定谓词值的三元组，需要对整张数据表进行自连接(self-join)才能得到结果。这里在前两节的基础上使用相同谓词值优先(SVFS)的方法来改进。即在每次遍历过程中，都只把谓词的值相同的三元组存放入同一个数据库的块(block)中。其算法过程如图2.3，图中p为当前遍历中的谓词值，即只存储谓词值和p相等的三元组。该方法相比于BFS方法多了一层循环While(p)，假设G中有k种谓词，那么遍历次数为2k+1，可得算法时间复杂度为O(2k|E|)。由于k1, |E|，最差情况下复杂度会达到O(|E|2)。但是对于真实有意义的RDF数据，如本章开始所列举数据，k|E|。SVFS(G)While(p)p null;Reset all visited tag in V;while(V)v = V.pick_up_random();if (p = NULL & v has child v)p - (v,v)s predicate;while(v)v.visited();for all vs childrenstore all the triples have subject v and predicate p;if (v.child.is_visited() = false)l.push(v.child);if (v.parent = null)V.remove(v);v l.pop();图2.3 SVFS方法算法2.4 使用索引提高效率根据上一节所述，在使用SVFS的情况下，每一次遍历的结果都集中存储在一个或若干个块中，由此可得，块与块之间唯一的区别在于其包含的三元组的谓词。所以在谓词上建立索引是最直接有效的方法，本节介绍一种使用哈希(hash)和树型结合的索引。索引分为两步：字符串的映射和索引树的建立。字符串映射使用特定算法将不同的字符串映射到一个等长的二进制数上，算法时间复杂度为O(n)。根据得到的数，定义两个字符串A、B之间的距离D:D = （AB）所得二进制串中1的个数。现设共有m个哈希结果，将这所有m个值作为叶子节点由下至上建立树。建立算法如下：1) 在候选集M中选取D值最小的一组或若干组值(a,b)(c,d)(x,y)。M初始为字符串映射所得到的m个数的集合。2) 对每一对值进行合并，得到新的值A,C,X，新值成为原值的父亲节点，并且把原数从M中删除。合并方法为按位取与，A = a&b。3) 重复1)和2)直到候选集中仅存一个节点，将该节点做为索引树的根节点，算法结束。最后可得索引树如图2.5：图2.5 索引树结构当查询到达的时候，也将查询中的谓词哈希到一个二进制数，并且从根节点开始往下查询。每次只选择相匹配的子女节点递归的执行查询，当所有子女节点都不匹配时终止查询并返回。若到达叶节点则取出相应的块并返回。3.实验准备根据上一章所述，现有的方法无论采用何种方式，都有明显的缺陷，如果同时采用两种方法的优点，即可达到平衡开销，使得处理各种数据都能有较好的效果。本章介绍实验的设计，包括数据集的选择和使用，查询语句的示例及其说明。3.1 RDF数据集系统采用两种数据进行性能测试，分别是真实世界数据和模拟生成的数据。所有的数据都使用RDF/XML语法格式存放于文件中。其中真实数据的概况如表4.1：表4.1 真实世界数据数据名文件大小三元组数量实体数量Semantic web-related bibliography8229KB3,4001,100Polling data91MB20,0003,350WordNet Nouns109.6MB300,0008,9000表中实体指的是该RDF文档所描述的对象。三种数据集在图的密度等方面具有不同的属性:l Semantic web-related bibliography数据中实体具有较少的属性，并且实体间联系较少，图密度低。l Polling data中实体属性较多，但实体间互相独立，即RDF图中不包含环，图密度中等。l WordNet Nouns数据中几乎所有实体均处在一个或多个环上，实体属性较多，图密度大。模拟生成数据采用LUBM11随机生3成的高校数据，不同的数据集概况如表4.2：表4.2 模拟生成数据数据编号文件大小(KB)三元组数量实体数量12,31421,7935,53423,76233,2398,275LUBM生成的数据共有五种实体，并且相互之间联系紧密，图中存在大量的环，但实体平均属性较少，图密度中等。3.2 RDF 查询从LUBM生成的数据来看，一个典型的RDF图可能包含有环，长路径以及子女数目较大的树。RDF查询的过程实际上是一个子图匹配的过程。因此本文设计了以下各类查询，通过查询不同形状的子图来测试。相对应的后台数据库表的一个元组结构为ID,S,P,O，ID为三元组的序号，S、P、O分别代表三元组的主体、谓词和客体，S、P、O字段均为字符串。查询语句使用SPARQL表达。具体如表4.3：表4.3 查询语句示例序号查询语句Q1选取所有学习给定课程的学生SELECT DISTINCT ?x WHERE ?x ub:takesCourse Q2选取所有属于或为同一个部门工作的人SELECT DISTINCT ?x ?y WHERE ?x ub:worksFor ?z . ?y ub:memberOf ?zQ3选取给定导师的本科生SELECT DISTINCT ?x WHERE ?x rdf:type bm:GraduateStudent . ?x ub:advisor Q4选取上自己导师课程的学生SELECT DISTINCT ?x ?z WHERE ?x ub:takesCourse ?y . ?x ub:advisor ?z . ?z ub:teacherOf ?y Q5选取所有部门已经有的出版物SELECT DISTINCT ?y ?z WHERE ?x1 ub:name ?y . ?x1 rdf:type ub:Publication . ?x1 ub:publicationAuthor ?x2 . ?x2 ub:memberOf ?zQ6选取出版物、其作者和工作部门SELECT DISTINCT ?x ?y ?z WHERE ?x ub:publicationAuthor ?y . ?y ub:worksFor ?a . ?a ub:subOrganizationOf ?z Q7列举所有教授的个人信息和其著作名称SELECT DISTINCT ?x ?y1 ?y2 ?y3 WHERE ?x rdf:type ub:FullProfessor .?x ub:researchInterest Research6 .?x ub:name ?y1 . ?x ub:emailAddress ?y2 .?y3 ub:publicationAuthor ?x .表中列举了不同复杂度的查询。Q1为最简单的查询，查询速度仅和索引速度有关，不需要任何连接运算。Q2和Q3是较复杂的查询，最多需要一次连接运算，查询效率和三元组存放顺序有关。Q4代表了环状的图，Q5和Q7代表了树状的图，Q6则是路径，这四个查询都比较复杂，需要多次的连接和索引，因此可以很好的衡量查询的效率。4. 实验结果与分析为了测试系统的实际性能，我们使用上一章中提到的所有数据集进行测试。系统使用C+语言实现，在eclipse CDT环境下编译运行。实验均在Ubuntu 7.04下进行，机器配置为2.33G Intel Core2due的CPU以及512MB的物理内存，后台数据库为PostgreSql 8.2。4.1 存储效率实验实验结果如图4.1所示：由图可知，虽然在上一章中BFS和DFS的算法有着一定的差距，但结果表明两者相差不大。而SVFS和上两种方法有着显著差异，原因是算法本身需要更多的时间来执行，而且SVFS只把相同谓词的三元组放入同一个块，带来了额外的读写开销。但从图中数据可得，随着数据集的增大，以及图密度的增长，这种差异在逐渐减小。数据的测试结果表明，SVFS方法的存储效率和RDF图中谓词的数量直接相关。4.2 查询效率实验本节实现并测试了第三章所列举的七个查询语句，查询所用数据集为LUBM的模拟数据，查询实验结果如图4.2所示：从图中结果可知：对于简单的查询如Q1，仅需对数据库做一次扫描便可以得到结果，不需要进行连接操作，因此查询时间的增长基本保持线性。对于略为复杂，需要进行连接运算的Q2和Q3，这两个查询在图结构上类似，查询开销也较为接近，总体来看Q2略比Q3耗时。和Q1相比，Q2和Q3随着数据增长，其查询代价增长比较明显。Q4、Q5、Q6和Q7的查询语句都比较复杂，涉及多次连接运算，所以在时间开销上明显大于前几个查询，但是随着数据量的成倍增长，其时间开销增长速度较慢，在LUBM3和LUBM4上的查询结果证明了这一点。不同的存储方法对查询效率的影响也可以从图中得出，对于最简单的查询Q1，存储的方法和查询效率关系不大。在Q2和Q3上，两者的差距依然不大。但在复杂的查询中如Q4到Q7中，两者差距加大，尤其是在LUBM2上的差距最为明显。可见不同的三元组存放顺序确实会影响最后的查询效率。5.结论根据文章所述以及实验结果，使用简单的分割算法并按照三元组的方式存储RDF数据可以使得数据存储时间和查询时间的开销都较小。SVFS方法在遍历的过程中通过将相同谓词的三元组存放入同一个数据块中使得数据更加有序，从而提高查询的效率。在实际应用中，存储仅需一次，而查询可能会有很多次。使用SVFS方法可以平衡数据存储和查询的开销，达到总体效率的优化。图5.1 数据载入实验结果图5.2数据查询结果参 考 文 献1. Resource Description Framework (RDF) / W3C Semantic Web Activity, /TR/REC-rdf-syntax/2. RDF Semantics, /TR/rdf-mt/3. RDF/XML Syntax Specification, /TR/rdf-syntax-grammar4. Jeremy J.Carroll, Ian Dickinson, Chris Dollin. Jena: implementing the semantic web recommendations. Proceedings of the 13th international World Wide Web conference. May. 20045. Redland RDF Libraries, /6. Akiyoshi Matono, Toshiyuki Amagasa. A Path-based Relational RDF Database. Procee