基于关系数据库的RDF数据存储
学校：
院系：
专业：
班级：
姓名：
学号：
指导教师：
教师职称：
完成日期：
摘要
语义网的发展，引发了对RDF(Resource Description Framework,资源描述框架)的研究热潮。RDF 用来描述语义网中的资源，它是用来描述元数据的数据。随着RDF应用的发展，对于海量RDF数据的存储和查询也提出了更高的要求。W3C组织提出了的SPARQL查询语言草案，被视为未来语义网查询语言的发展方向。SPARQL 的半结构化查询方式与RDF 的半结构化特性完美地结合起来。
本论文对RDF与SPARQL进行了深入研究，设计了使用关系数据库来进行RDF数据存储与查询的解决方案方案。
存储方面，将RDF数据结合SPARQL查询语言的格式设计存储结构，方便查询语言进行匹配，利用编码机制存储数据节省了存储空间。
查询方面，将用户提交的SPARQL查询语言转换成等价的SQL语言，提交给关系数据库进行查询，最后将查询结果返回给用户。本文详细分析了SPARQL 基本图模式，可选图模式，值限制图模式和并图模式，并针对现有的关于查询图模式匹配顺序的分歧，提出了自己的观点以及论据。最后采用查询操作树将SPARQL查询语言正确转换成SQL语句，并提出了值限制图模式的转换算法。
关键词：RDF、SPARQL、SQL、存储结构、数据处理
ABSTRACT
With the development of semantic Web,worldwide attention has been profoundly obtained to the research boom of RDF(Resource Description Framework)that is the data for describing metadata and is used to describe Web resources in semantic Web. The storage and query of massive amount of RDF data,as the RDF application developed,demands for higher requirements.The draft of SPARQL query language provided by W3C organization is considered as the future development trend for semantic Web query language.The semi-structured query methods is able to be perfectly combined with the semi-structured characteristics of RDF, of SPARQL.
This paper is deeply engaged in the research of RDF and SPARQL has designed solutions of utilizing Relation Database for storing and querying RDF data.
In storage, the pattern of designing storage structure of combining RDF data with SPARQL query language is able to facilitate the matching for query language. Encoding mechanism used to store data saves storage space.
In query, the SPARQL query language submitted by users is initially transformed to equivalent SQL language and subsequently delivered to Relation Database for query, finally the query results have been returned to the users. This paper analyzes the basic SPARQL graph patterns, optional graph patterns, map mode and restricted mode.Own opinion as well as its argument has been proposed by detailed analyzing the structure of query map mode and aiming at the recent differences corresponding to the matching sequences of query map mode.Ultimately, Operation tree has been introduced to transform complex SPARQL query language to SQL language and conversion algorithm has been proposed to convert value limit pattern.
Key Words：RDF、SPARQL、SQL、Storage Structure、Data Processing
1. 绪论 (5)
1.1 研究的背景 (5)
1.2 研究的现状 (6)
1.3 研究主要内容 (7)
2. RDF数据存储的介绍 (7)
2.1 RDF基本概述 (7)
2.2 RDF基本模型 (7)
2.3 RDF存储模式 (8)
2.4 RDF存储语言 (9)
3.RDF存储方法分析 (10)
3.1 使用DFS方法存储三元组 (10)
3.2 使用BFS方法存储三元组 (11)
3.3 使用相同谓词值优先的方法改进 (12)
3.4 使用索引提高效率 (13)
4.实验准备 (14)
4.1 RDF数据集 (14)
4.2 RDF 查询 (15)
5.实验结果与分析 (17)
5.1 存储效率实验 (17)
5.2 查询效率实验 (17)
结论 (19)
致谢 (19)
参考文献 (20)
1.1 研究的背景
近年来，万维网（World Wide Web）的信息以惊人的速度增长，涉及的领域不断的扩大，包括生物科学，社会科学等一系列学科的内容，为人们提供了更多的可共享、可传递的信息，但是，数据量的激增导致人们获取所需信息的难度加大。万维网的创始人Tim Berners-Lee通过W3C（World Wide Web Consortium）于2000年提出了语义网(Semantic Web)的概念，即通过为网上的各种数据提供明确的语义，实现信息在语义层上的互操作，使计算机能够理解其所存储和传输的信息，自动处理数据，极大地帮助人们完成选择和鉴别信息数据的工作。语义网已经被看成是关于下一代互联网的发展方向，逐渐成为研究的热点。
语义网的核心是使用机器来理解Web 上的信息。这就需要为机器提供描述Web上数据的模型。RDF（Resource Description Framework，资源描述框架）是W3C 在可扩展标记语言XML 基础之上开发出来的一种元数据描述框架，是一个为描述Web元数据而建立的标准。RDF 提供的语义模型可用来描述网络上的任何资源以及资源类型，这就为资源描述提供了一种通用的表示框架。RDF同时提供了灵活的机制允许用户可以依据实际的情况，自定义某个应用领域内知识、资源的表示规则和语义信息，使得用户可以使用自定义的词汇表描述任何资源。RDF提供了一种通用的框架，即由资源，属性，属性值组成的三元组结构。在RDF中一个拥有若干属性和对应的属性值的对象成为资源，使用URI 对其进行标识。我们可以通过语句对资源进行描述。语句的结构为RDF 三元组形式，即主语（subject）—谓语（predicate）—宾语（object）三元组。其中主语为要描述的资源，谓语为资源的属性，宾语为属性对应的具体值。随着RDF 作为对资源的描述广泛并成功的应用于多个领域，对于RDF 的存储与查询的需求也越来越多。由于关系数据库技术已经十分成熟，人们倾向于利用关系数据库来存储RDF数据。
简而言之，RDF 使用属性以及属性值来描述资源，具体表现形式为RDF 三元组。但是，在有些语句中，会使用特定的值来增强对属性的约束，例如：有时候需要表示该属性所描述的资源是某一种特定资源，用来描述这种特定资源类的属性需要增加一些额外的约束，比如父类子类、取值范围等等，但RDF并不具
备这样的能力，RDF 模型只是提供了一种机制来描述元数据，它并没有定义任何应用领域的语义，定义专门领域的资源属性及其语义需要借助于其它手段来进行补充。这些类和属性所形成的特定词汇就可以使用RDF schema 来描述。
RDF schema 是RDF 的扩展，它通过提供一些原语来定义类、属性、类与属性之间的隶属关系等，来增强对资源语义的进一步描述。RDF schema比较类似于一些面向对象的程序设计语言，比如允许类组织成层次结构，一个资源可以是一个或多个类的实例。但在某些方面又不尽相同，比如它对类和属性的描述属于扩展的性质，不是强制性的。RDF Schema 本身也是一种元数据，也是以RDF 资源集的形式存在的，并且RDF Schema 产生的词汇描述也是RDF图，遵循RDF规则。因此，RDF解析软件可以把RDF schema 正确地解释成RDF图。RDF schema 定义了资源的种类，还有资源的属性及其之间的关系。元数据的含义被机器理解和共享是很必要的，在这方面本体(Ontology)起了相当重要的作用，本体实际上是一种共享的词汇，一般描述了某个领域的重要概念，以及概念间的关系。RDF schema就被视作一种简单的本体语言。RDF已被广泛地应用在各个领域，例如：用于协助搜索引擎更好地查找资源，对网站、图书馆中的内容及其关系进行分类和描述，以及智能软件代理中用作知识表示、共享和交换等等。随着RDF的应用日益广泛，对于RDF的存储与查询的需求也提出了更高的要求。1.2 研究的现状
资源描述框架RDF是描述Web上资源的通用语言。世界上很多大学和科研组织都在从事RDF的研究。美国国防部高级计划研究署支持开发的DAML，是语义web 活动的主要推动力，其建立在RDF之上，以描述逻辑为基础，成功实现了语义的机器可读。Jena 是目前最流行的构建语义网应用的ava框架，它是由HP实验室开发的，可以处理本体，RDF数据，推理机制，存储等功能，支持包括SPARQL在内的多种查询语言。Jena开发的ARP与希腊国家计算机研究所开发的VRP是RDF解析的两大主要开源工具。Sesame使用自己的RDF数据源模型，并部分支持SPARQL查询功能。RDFstore用于解析、存储和管理RDF。国内关于语义网的研究起步比较晚，但也有不少高校和科研机构致力于这方面的内容。江苏省“语义web语言及支撑软件技术基础研究”项目组研究开发了面向RDF数据的FIRTREE系统和ROMQS系统。其中FIRTREE 系统的主要功能
是RDF的向前推理，ROMQS系统研究的是SPARQL的非强制匹配问题。复旦大学在RDF数据基于关系型数据库的存储方面做了研究。武汉大学董慧教授主导的“基于本体的数字图书馆检索模型研究”项目实现了本体检索、本体基于逻辑的领域知识检测推理和基于关系的蕴涵知识发现推理和可视化的功能。
1.3 研究主要内容
本文的研究重点是：一、学习资源描述框架RDF与查询语言SPARQL，在这个基础上实现一个基于关系型数据库的RDF 数据存储与查询系统。二、由于RDF 的语义性与SPARQL不具有推理性的特点，进行推理与敏感数据的研究。
三、设计SPARQL查询语言与SQL语句之间的转换算法来支持基于关系型数据库的RDF数据的查询。
本文的内容安排如下：第二章主要介绍资源描述框架RDF 的基本概念和表现形式，RDF数据的存储方式，基于RDF数据的查询语言，W3C推荐标准SPARQL 查询语言的结构；第三章介绍RDF的推理，敏感数据以及本系统采用的RDF在关系型数据库中的存储方法。第四章具体介绍SPARQL到SQL的转换方法。第五章根据前两章的内容给出系统的具体实现和系统的存储以及查询模块的功能进行验证。最后一章是对目前工作的总结与未来工作的展望。
1.RDF数据存储的介绍
2.1 RDF基本概述
随着各种信息资源的不断增加，网络上的信息量以惊人的速度增长，主要以支持文本内容搜索和浏览的web模型已经不能适应如此海量的信息处理交换。语义网需要一种新的资源模型以支持对海量的web信息资源以及服务的统一访问。传统的XML数据模型可以用于数据的描述和交换，但是XML缺乏对语义信息的表达。因此，W3C采用了新的数据模型资源描述框架（resource description framework）RDF以及RDF Schema来描述网络上的信息资源。RDF模型是一种对网络资源描述的通用语言，它描述网络中资源对象与资源对象的关系，可以被计算机程序识别。RDF是基于XML的描述语言，可以通过XML来表达RDF。
2.2 RDF基本模型
资源描述框架（resource discription framework）简称RDF，是描述web上资源信息的语言。RDF对信息的表示不仅可以用于查看资源同时还可以被应用程序处理。它提供了一种通用的框架，这种资源描述框架可以使资源信息在程序间传递，交换而同时又不丧失其语义。资源是指在web上可以通过统一资源标示符标识的所有事物。RDF的基本思想是通过统一资源标示符（Uniform resource ide identifier，URI）来标识web上得资源，用简单的属性（property）以及属性值（value）来描述资源。通过主谓宾的语法形式将资源，属性，属性值连接在一起，形成完整的资源描述。其中主语对应所要描述的事物资源，谓语对应唯一的属性标识，宾语对应着属性值，其中宾语可以是资源或者文字，当宾语是资源的时候这个描述表示资源与资源的关系，如果宾语是文字这个宾语就是对资源属性的描述。对资源的描述就是对资源的属性以及属性值的声明。我们将这种声明称为陈述（statement）。陈述的基本结构为“主语-谓语-宾语”的三元组，也可以称为“资源-属性-属性值”的三元组。
RDF模型可以采用不同的语法形式来描述，但是大多情况下都是用XML 来刻画。XML（Extensible Markup Language）可扩展标记语言。XML是internet 环境中依赖于内容并且跨平台的技术。是处理结构化文档信息的有力工具。XML 是一种简单的数据存储语言。使用一系列简单的标记来描述数据。其特点是简单，易于掌握和使用。
2.3 RDF存储模式
随着RDF数据的广泛应用，其数据规模也日益庞大，RDF图的规模甚至达到数千万个节点。而且不同的RDF数据可以通过一些链接的方法合并成一个数据集，所以在实际应用中，我们经常会面对内存空间不足以载入所有RDF数据的情况，这导致了我们需要频繁的在外存和内存间交换数据来完成数据处理，从而使得数据交换成为整个处理过程的瓶颈。若使用文件存储，则每次数据读取都要将文件整个的读入，大大降低了效率。所以使用数据库存储是必然的选择。在存储的后台方面，使用关系数据库更有利于数据存储。因为关系数据库具有相当简单的结构，能很好的适应于RDF数据简单的数据模型。
但在关系数据库中，所有的数据都被存放在一个或若干个表中，一定程度上破坏了图的结构。在执行查询的时候，需要取出大量的数据来重构图，尤其在处
理复杂查询的时候，需要对表进行多次自联接运算(self-join)，显著的降低效率。所以现在使用关系数据库来存储RDF数据的主要问题在于，采用何种顺序或者结构将三元组放入数据库中，而且所采用的方法对存储以及查询的效率有何影响。不同方法在读取速度，存储开销，查询速度等方面各优劣。
现存的存储方法主要有以下两大类别：
（1）按照文件结构逐条存储三元组。逐行读取文件，并且直接按照文件中的顺序存储三元组。在数据库中的排列顺序仅和三元组在文件中的排列顺序有关。
（2）按照逻辑结构切割图并存储。将文件读入内存，还原成图之后使用一定的分割算法把图切分后将子图存入数据库。三元组在数据库中的排列顺序和节点在图中的逻辑顺序有关。
第一种方法典型的代表是RDF数据存储部分，这类方法的优描一遍文件就可以完成存储过程。不足在于所有数据都存放在若干张很大的表中，并且相邻数据之间没有一定的逻辑关系，所以每次查询操作都可能导致需要对整张表进行自联接运算，查询和搜索效率比较低下。
第二种方法按照分割算法的不同，切割后的子图可能是路径、树或者较小的RDF图，比起前一种方法该方法开销较大。由于这类方法按照一定的逻辑关系建立起图的索引，每次查询都只需要在一个较小的候选子图集中进行搜索比较，查询的效率比前一种方法高。
本文的主要贡献在于：1)提出了三种不同的存储方法，并且从理论分析了其不同的存储效率，2)收集了不同规模的RDF数据集，并且针对数据设计了若干个不同复杂度的查询，3)在此基础上对不同的存储方法进行实验，得出其实际存储和查询效率。
本文剩余章节组织如下，第二章介绍本文所使用的数据及其来源，并且设计了若干个查询来测试性能，第三章主要介绍了一种存储RDF数据的基本方法，并且做出相应分析，第四章为相关实验及其结论。
2.4 RDF存储语言
SPARQL是DAWG根据上述需求和目标制定的一种基于RDF元组的查询语言，它是从之前的rdfDB、RDQL和SeRQL 等查询语言发展而来的。SPARQL
具有一些新的特性，得到了一些包括jena在内的RDF数据库系统的支持。与之前的RDF查询语言相比SPARQL增加了两个新的特性：第一，SPARQL支持多种复杂查询的模式构建；第二，SPARQL提供了多种结果模式。
SPARQL 是基于图的匹配的查询语言，最基本得图模型是简单图模型，即三元组图模型，它与RDF三元组类似，但是在主语，谓语，宾语的位置上都可能出现变量。例如?person dc:name ?name，这是一个简单的三元组图模式，其中主语person与宾语name都是变量，其表示查询所有人的姓名。SPARQL的语法与SQL 的语法类似。SPARQL 的基本图模式就是将查询语句中多有的三元组模式连在一起，结果必须满足语句中所有的三元组模式，通过组合基本的三元组模式，以及运用SPARQL中的关键字GRAPH、FILTER 、OPTIONAL、UNION 等，可以到包含命名图模式，组图模式，值约束图模式，可选图模式，并图模式的复杂图模式。并且可以通过上述图模式的嵌套定义得到更为复杂的查询图模式以满足更复杂的需求。与SQL类似，SPARQL还支持限制结果数量和结果排序的功等能。
在结果集方面，为了满足不同的需求，SPARQL提供了四种不同格式的结果集。SELECT 查询返回的是全部或者部分匹配变量的绑定，及相应的XML 文件；DESCRIBE查询返回的是一张描述查询变量或者指定资源的RDF图；ASK 查询的作用是通知用户查询模式是否存在相应的匹配，其结果也是XML文件；CONSTRUCT 查询返回一张满足查询的子图，同时输出RDF 文件。
3.RDF存储方法分析
由于RDF的本质是含有语义信息的图，因此大多数的查询语句也必然包含一定的语义信息。因此在存储的过程中尽量保留这样的信息显然可以提高查询的效率。但是过多的保留这样的信息会导致算法复杂性的提高，在面对大规模数据的时候缺乏灵活性。
3.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 G
s.push(v.child);
v ← s.pop();
图2.1 DFS方法算法
3.2 使用BFS方法存储三元组
使用DFS方法可以减少存储的开销，但是在遍历过程中，节点被重复访问多次，一定程度上影响了算法的效率，而使用BFS(广度优先)的方法可以减少这一开销，BFS分割算法如图2.2，数据结构和DFS方法相同，其中l为单向的队列：
BFS(G)
while(V)
v←V.pick_up_random();
while(v)
v.visited();
for all v’s children
store 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方法。
3.3 使用相同谓词值优先的方法改进
使用BFS和DFS的方法能显著减少图切割和还原的时间开销，两种方法在还原整个RDF图时有着一些优势，但是对于特定的查询，例如取具有给定特定谓词值的三元组，需要对整张数据表进行自连接(self-join)才能得到结果。这里在前两节的基础上使用相同谓词值优先(SVFS)的方法来改进。即在每次遍历过程中，都只把谓词的值相同的三元组存放入同一个数据库的块(block)中。其算法过程如图2.3，图中p为当前遍历中的谓词值，即只存储谓词值和p相等的三元组。
该方法相比于BFS方法多了一层循环While(p)，假设G中有k种谓词，那么遍历次数为2k+1，可得算法时间复杂度为O(2k||E||)。由于k∈[1, ||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 v’s children
store 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方法算法
3.4 使用索引提高效率
根据上一节所述，在使用SVFS的情况下，每一次遍历的结果都集中存储在一个或若干个块中，由此可得，块与块之间唯一的区别在于其包含的三元组的谓词。所以在谓词上建立索引是最直接有效的方法，本节介绍一种使用哈希(hash)和树型结合的索引。索引分为两步：字符串的映射和索引树的建立。
字符串映射使用特定算法将不同的字符串映射到一个等长的二进制数上，算法时间复杂度为O(n)。根据得到的数，定义两个字符串A、B之间的距离D:
D = （A^B）所得二进制串中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 索引树结构
当查询到达的时候，也将查询中的谓词哈希到一个二进制数，并且从根节点开始往下查询。每次只选择相匹配的子女节点递归的执行查询，当所有子女节点都不匹配时终止查询并返回。若到达叶节点则取出相应的块并返回。
4.实验准备
根据上一章所述，现有的方法无论采用何种方式，都有明显的缺陷，如果同时采用两种方法的优点，即可达到平衡开销，使得处理各种数据都能有较好的效果。本章介绍实验的设计，包括数据集的选择和使用，查询语句的示例及其说明。
4.1 RDF 数据集
系统采用两种数据进行性能测试，分别是真实世界数据和模拟生成的数据。所有的数据都使用RDF/XML 语法格式存放于文件中。
其中真实数据的概况如表4.1：
表4.1 真实世界数据
数据名 文件大小 三元组数量 实体数量
Semantic web-related
bibliography[8]
229KB 3,400 1,100 Polling data[9]
1MB 20,000 3,350 WordNet Nouns[10] 9.6MB 300,000 8,9000
表中实体指的是该RDF 文档所描述的对象。三种数据集在图的密度等方面具有不同的属性:
Semantic web-related bibliography 数据中实体具有较少的属性，并且实体间联1111110111010101101111000011100011100111110110101001000
0001100000
系较少，图密度低。
●Polling data中实体属性较多，但实体间互相独立，即RDF图中不包含环，
图密度中等。
●WordNet Nouns数据中几乎所有实体均处在一个或多个环上，实体属性较多，
图密度大。
模拟生成数据采用LUBM[11]随机生3成的高校数据，不同的数据集概况如表4.2：
表4.2 模拟生成数据
数据编号
文件大小(KB) 三元组数量实体数量
1 2,314 21,793 5,534
2 3,762 33,239 8,275
LUBM生成的数据共有五种实体，并且相互之间联系紧密，图中存在大量的环，但实体平均属性较少，图密度中等。
4.2 RDF 查询
从LUBM生成的数据来看，一个典型的RDF图可能包含有环，长路径以及子女数目较大的树。RDF查询的过程实际上是一个子图匹配的过程。因此本文设计了以下各类查询，通过查询不同形状的子图来测试。相对应的后台数据库表的一个元组结构为[ID,S,P,O]，ID为三元组的序号，S、P、O分别代表三元组的主体、谓词和客体，S、P、O字段均为字符串。查询语句使用SPARQL表达。具体如表4.3：
表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 ?z}
Q3 选取给定导师的本科生
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 ?z}
Q6 选取出版物、其作者和工作部门
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则是路径，这四个查询都比较复杂，需要多次的连接和索引，因
此可以很好的衡量查询的效率。
5.实验结果与分析
为了测试系统的实际性能，我们使用上一章中提到的所有数据集进行测试。系统使用C++语言实现，在eclipse CDT环境下编译运行。实验均在Ubuntu 7.04下进行，机器配置为2.33G Intel Core2due的CPU以及512MB的物理内存，后台数据库为PostgreSql 8.2。
5.1 存储效率实验
实验结果如图4.1所示：
由图可知，虽然在上一章中BFS和DFS的算法有着一定的差距，但结果表明两者相差不大。而SVFS和上两种方法有着显著差异，原因是算法本身需要更多的时间来执行，而且SVFS只把相同谓词的三元组放入同一个块，带来了额外的读写开销。但从图中数据可得，随着数据集的增大，以及图密度的增长，这种差异在逐渐减小。数据的测试结果表明，SVFS方法的存储效率和RDF图中谓词的数量直接相关。
图4.1 数据载入实验结果
5.2 查询效率实验
本节实现并测试了第三章所列举的七个查询语句，查询所用数据集为LUBM 的模拟数据，查询实验结果如图4.2所示：
从图中结果可知：对于简单的查询如Q1，仅需对数据库做一次扫描便可以得到结果，不需要进行连接操作，因此查询时间的增长基本保持线性。对于略为复杂，需要进行连接运算的Q2和Q3，这两个查询在图结构上类似，查询开销也较为接近，总体来看Q2略比Q3耗时。和Q1相比，Q2和Q3随着数据增长，其查询代价增长比较明显。Q4、Q5、Q6和Q7的查询语句都比较复杂，涉及多次连接运算，所以在时间开销上明显大于前几个查询，但是随着数据量的成倍增长，其时间开销增长速度较慢，在LUBM3和LUBM4上的查询结果证明了这一点。
图5.2数据查询结果
不同的存储方法对查询效率的影响也可以从图中得出，对于最简单的查询Q1，存储的方法和查询效率关系不大。在Q2和Q3上，两者的差距依然不大。但在复杂的查询中如Q4到Q7中，两者差距加大，尤其是在LUBM2上的差距最为明显。可见不同的三元组存放顺序确实会影响最后的查询效率。
结论
随着语义网的发展，越来越多的组织和科研机构开展了对RDF（Resource Description Framework，资源描述框架）的研究工作。随着研究的深入，RDF应用出现在了更多的领域。这就对RDF数据的存储与查询提出了更高的要求。好的存储方案能够大大节省存储空间同时也能够提高查询效率。查询也对存储存在着相关的需求。
本论文对RDF数据的存储与查询进行了深入的研究。首先对资源描述框架RDF进行了详细的描述，然后对不同的RDF 存储结构进行了分析比较，并对W3C标准的RDF查询语句SPARQL进行了详细介绍。最后在这些内容的基础上设计并实现了一个基于关系型数据库的RDF数据存储查询系统。整个系统主要包括RDF存储与查询两个方面的内容。存储方面，根据SPARQL查询语句的特点组织RDF三元组，并通过对主、谓、宾字段上的内容进行编码的方式来减少存储空间的占用。查询方面，首先将用户提交的SPARQL查询语句转换为等价的SQL语句，然后将转换好的SQL提交给关系型数据库进行查询，最后将查询结果返回给用户。本文详细介绍了SPARQL查询中的基本图模式，值限制图模式，可选图模式和并图模式，并针对现有的查询匹配顺序存在的分歧提出自己的观点。
致谢
时光如梭，转眼间临近毕业。这是我人生最难忘的一段时光，在这里我付出了许多，也收获了许多，自己也成长沉稳了。
我要感谢各位辛勤付出的老师将我引入学术的殿堂，使我一次次地战胜自我、超越自我，不断跨上新的台阶。
也要感谢与我一起拼搏奋斗的师兄弟姐妹们，感谢你们在论文写作过程中给予的无私帮助和不断鼓励，感谢你们陪我一起度过了大学美好的人生时光。
还要感谢我的家人和朋友，是你们最后关头的帮助与激励，是你们长期一如既往的贴心与体谅。
最后，更要衷心地感谢为评阅本论文而付出辛勤劳动的老师们!您们，辛苦了！
参考文献
[1]刘谱.高扩展的RDF数据存储系统研究[D].华中科技大学,2012.
[2]朱敏.基于HBase的RDF数据存储与查询研究[D].南京大学,2013.
[3]杨琴.基于关系数据库的RDF存储与查询的研究与实现[D].电子科技大学,2010.
[4]秦冬生.基于云计算的RDF数据存储系统的研究[D].合肥工业大学,2013.
[5]项灵辉.基于图数据库的海量RDF数据分布式存储[D].武汉科技大学,2013.
[6]易雅鑫,宋自林,尹康银.RDF数据存储模式研究及实现[J].情报科学,2007,08.
[7]吴琴霞,张志鸿.语义Web中RDF元数据的存储与管理[J].微计算机信息,2007,33.
[8]吴德龙.基于存储优化模型的RDF数据查询机制研究[D].华中科技大学,2011.
[9]张伟奇.基于关系型数据库的RDF存储引擎[D].天津大学,2012.
[10]熊力,顾进广,项灵辉.基于列式数据库的RDF数据分布式存储[J].数学的实践与认识,2014,05.
[11]陈光仪.基于关系数据库的本体存储研究[D].中南大学,2009.
[12]艾国辉.基于关系数据库的XML数据存储方法的研究与实现[D].哈尔滨工程大学,2008.
[13]杜方,陈跃国,杜小勇.RDF数据查询处理技术综述[J].软件学报,2013,06.
[14]项灵辉,顾进广,吴钢.基于图数据库的RDF数据分布式存储[J].计算机应用与软件,2014,11.
[15]王世醒.基于MapReduce的大规模RDF图并行推理方法的研究[D].南昌大学,2014.
[16]佟强,张富,程经纬,马宗民.RDF在关系数据库中的存储研究[J].东北大学学报(自然科学版),2015,03.
[17]王北辰.基于结构化索引的RDF数据存储及查询方法的研究与实现[D].北京交通大学,2013.
[18]卢传耀.基于面向文档的NoSQL数据库的RDF数据存储实现[J].电子技术与软件工程,2013,22.
[19]朱敏,程佳,柏文阳.一种基于HBase的RDF数据存储模型[J].计算机研究与发展,2013,01.
[20]胥正川.基于关系数据库的XML数据存储、更新和检索[D].复旦大学,2003.
[21]王星,宋金玉,陈爽,陈萍.基于列数据库的RDF数据管理实现[J].计算机技术与发展,2012,06.
[22]袁平鹏,刘谱,张文娅,吴步文.高可扩展的RDF数据存储系统[J].计算机研究与发展,2012,10.
[23]詹火木.基于关系数据库的XML存储和查询的研究[D].重庆大学,2008.
[24]金浩.RDF元数据查询和存储的研究[D].华东师范大学,2008.
[25]余诗权,谢冬青.基于关系数据库的XML数据转换架构[J].计算技术与自动化,2006,02.
[26]许丽,杨旭清.基于关系数据库的RDFS存储研究[J].电脑与电信,2008,03.