4store源码解析系列(5)–查询流程概述

  • Post author:
  • Post category:IT
  • Post comments:0评论

前言

从这一篇的系列文章开始,我们将展开4store的查询研究。在这一篇中,我们将先介绍一下查询的整体流程,然后通过一个简单例子来阐述流程中涉及的一些基本问题。

流程概述

Query处理

SPARQL是一种用于RDF上的查询语言,其语法可以详见文档中的说明。4store中,使用Rasqal RDF Query Library作为其SPARQL查询语句的语法解析器,运用了Rasqal在query构造、执行顺序以及变量绑定(binding)等诸多内容的解析功能。但是,Rasqal只提供了对于query的分析功能,具体根据分析所得的语法树、变量绑定、嵌套搜索结构等信息来执行查询操作,则是由4store来完成的。

目前,Rasqal提供了对SPARQL 1.0的完全支持,但对SPARQL 1.1仅提供部分支持。

基本流程

4store使用了CS模型来应对查询需求。其中,server端是存储数据端,提供了一种通用的三元组和资源的检索服务;client端直接处理外部查询请求,通过解析查询语句、构造三元组查询顺序、处理查询结果等步骤来完成请求。

overview

client端操作流程,具体来说分成如下几步:

1. 使用Rasqal解析查询语句;

2. 进一步分析Rasqal的解析结果中的嵌套结构,并根据嵌套块关系压缩图结构;

3. 分块执行三元组的查询请求;

4. 对查询结果进行块内的合并;

5. 执行块之间的join、union等操作;

6. 获取结果集中三元组对应的资源内容,组合资源内容后将其格式化输出。

实例分析

4store中,处理查询这部分的逻辑需要经过非常多的分支条件判断,且每个分支所执行的内容都较为零碎。这对我们阅读理解其源码,以及展示查询流程都带来了很大的挑战。为了能够让大家在一开始对4store的查询流程有比较通透的理解,本文将先从最简单的例子出发,来一步步解释整个查询的过程。

实例内容

我们使用的测试数据为foaf(friend of a friend),foaf中总共包含143条三元组关系。

SPARQL查询语句如下:

PREFIX foaf: <http://xmlns.com/foaf/0.1/>
SELECT ?name
WHERE {
[] foaf:name ?name
}

查询结果

这条查询语句的含义也十分清晰,查询foaf中所有三元组关系,得到其中关系为foaf:name的那部分三元组,并返回三元组中客语(objective)。使用如上所示的SPARQL语句查询,我们可以得到如下所示的17条返回结果,每条结果包含一列name域的值。

count ?name
0 “Phil McCarthy”
1 “Tim Berners-Lee”
2 “Damian Steer”
3 “Jan Grant”
4 “Sean B. Palmer”
5 “Morten Frederiksen”
6 “Libby Miller”
7 “Bijan Parsia”
8 “Dave Beckett”
9 “Dan Connolly”
10 “Eric Miller”
11 “Norm Walsh”
12 “Jo Walsh”
13 “Matt Biddulph”
14 “Jim Hendler”
15 “Edd Dumbill”
16 “Dan Brickley”

查询流程

那么,从我们输入这样一条SPARQL到结果产出,具体经历了哪些流程呢?接下来我们将带大家一步步揭开4store查询的神秘面纱。

Rasqal解析

首先,通过Rasqal解析上述查询语句,我们可以得到如下基本信息:

query verb: SELECT
data graphs: []
named variables: [variable(name)]
anonymous variables: [anon-variable(bnodeid1)]
projected variable names: name

bound variables: [variable(name)]
triples: [triple(anon-variable(bnodeid1), uri<http://xmlns.com/foaf/0.1/name>, variable(name))]
prefixes: [prefix(foaf as http://xmlns.com/foaf/0.1/)]
query graph pattern: 
    graph pattern[0]
        Basic(
            over 1 triple[
                triple(anon-variable(bnodeid1), uri<http://xmlns.com/foaf/0.1/name>, variable(name))
            ]
        )

这是一个SELECT类型的查询语句,涉及name和bnodeid1这两个变量,其中name是被投影到输出结果的,而bnodeid1是一个匿名变量,表示一个blank node。在4store中,匿名变量并没有被特别对待,被当做一般变量来处理。整个结构图中,总共就一条三元组查询语句需要执行。graph pattern实际是对所有triple查询语句的逻辑层次关系表达。在这个简单实例中,由于只有一条查询语句,graph pattern的结构是非常简单明了的。关于graph pattern的处理,我们将在之后的文章中具体展开说明。

按照Rasqal的解析,name属于bound型变量;但这并不意味着,在初始状态下name就是处于bound状态的。bound变量表明最终是要处于bound状态的。在英语中,单词bound是bind的过去分词,bind是一个“绑定”的动作行为,而bound是一个处于绑定的状态。对应于我们这里,bind表示去获取M, S, P以及O位置上变量对应rid值这一动作行为;而bound则是变量的一种状态描述,表征该变量当前已从服务端查询到rid值了。对应我们这个例子,name变量有一个bound域,在初始状态下它的值是0;在经过一次triple查询之后,name变量查询到了rid值,其bound状态就会变为1。变量的bound状态,在之后的结果合并、join等操作之后,也会继续传递下去。

针对现在这个简单例子,4store在得到Rasqal解析的这些query信息之后,实际已经能够开始检索任务的执行了。因为只有一条triple查询语句,就不会涉及多条triple查询语句之间关系嵌套、查询结果合并等问题,4store并不需要对query的信息额外制定一套执行计划。

triple查询

那么,4store是如何分析每一条triple查询语句,定位其实际查询内容,并最终把查询请求打包发送给backend处理的呢?

triple分析

4store首先逐个检查triple查询语句中的四元组的内容。此处,我先列举了其中关系比较密切的几个变量状态:bound、need_val、type。

  • bound属性的性质,在上一小节中我们就已经讨论了。
  • need_val的含义如其名称所示,表明该变量是需要返回检索值的。为什么变量需要返回的值呢?这只有两种可能:变量被project、变量关联着多条检索请求。need_val这个域的值是在graph pattern解析的时候确定的。但4store只能针对正常的查询逻辑,来解析某个变量是否need_val。若我们可以构造两条无关triple查询,且其中有一个没有实际用途但又是公用的变量时,则该变量的need_val域依旧会被置为1。
  • type属性,并不是一个显式声明的变量域,但却是变量的关键属性。URI变量,是有确定的rid的,可以作为triple检索的确定条件。其他一般变量,则需要根据变量的need_val域和bound域来确定其是在搜索中是否需要返回值。还有一些特定的rdf内置datatype变量,它们则会有各自唯一的type属性值。关于内置datatype变量的相关问题,在本文暂不展开。
model subject predicate object
value null bnodeid1 http://xmlns.com/foaf/0.1/name name
type null variable URI variable
bound no no no no
need_val no no no yes

如下图所示,bnodeid1是subject变量,bound和need_val域都为0,是一个无关变量;name是一个object变量,虽然bound域为0,但need_val是1,表明其在检索之后需要填值;而predicate位置则是由一个URI变量占了,每个URI可以通过hash唯一对应到一个rid;model位置,此处为null,它的值不影响查询,暂不讨论。

这次检查的主要是为了确定[M, S, P, O]中有哪几项在目前检索时是有确定值的,哪几项是有一些候选值的,哪几项是需要返回查询结果。在这个例子中,P的值是确定的,O的值是需要返回查询结果的,而S和M是无关的。一旦这些信息确定下来了,那么查询的类型也就可以得以确认。在这个例子中,我们有确定的P,而M、S以及O都是未知的,查询时需要返回所有符合条件的O。这是一个典型的bind by object的检索例子,flag中会将FS_BIND_BY_OBJECT位对应的值置为1。

消息构造

接下来,就把这些解析之后的信息进行编码。如下图所示,首先要构造一个消息头,说明消息的类型、长度以及发送的segment对象等。然后再将flag、limit等值依次写入消息内容,最后再将[M, S, P, O]查询四元组的数量和值,依次写入到消息中。

BIND_LIMIT_MSG

在我们这个例子中,mids、sids以及oids都为0,只有一个pids。

因为查询的是object,而subject是没有任何限制的。此时,我们原本根据subject来分开存储数据的逻辑就无法利用,只能将检索请求发送到每一个segment。若我们是在已知一个或者多个确定的subject下检索object或predicate等信息,则可以先按照subjects的segment归属来进行分类,然后再对每一类数据构造一个消息发送到其对应的segment中,让每个segment只处理与其相关的那部分搜索请求。

服务端处理

消息发送之后,backend服务端就收到了检索请求。根据收到的消息中的flags值和[M, S, P, O]的值数量,就可以确定出当前的检索任务需求。在这个例子中,已知P来求O,就可以先利用hash映射,找到当前检索predicate在predicate_list中的位置;根据predicate_list中记录的值,进一步定位到那棵以Object的rid作为主key的ptree;接着,遍历ptree中的每项值,将结果收集并返回;服务端最后再将收集到的object的rids编码发回给客户端,就圆满完成这一次triple检索任务了。

资源获取

客户端收到了检索到的object的rid列表之后,将name这个变量的bound域置为1,来表示当前该变量已经收到了来自服务端的rid数据。同时,如果我们这个例子中还有下一条的tripple检索,若在S, P, O中有包含变量name,则可以将name的rid值也发给服务端,作为新一次检索条件的一部分。

最后一步,将rid转化成对应存储的文本值。因为在4store中,资源的存储也是分segment的。因此,我们首先要先对rid分类,然后再将每类rid发送到对应的segment上进行资源的检索。资源检索主要涉及的是rhash,每个rid在rhash上找到对应的entry。根据entry上记录的标记位值和文本域内容等信息,再进一步从res.rhash.lex和res.rhash.prefixes文件中找到需要的文本值,拼接出原始存入的文本串内容。关于资源的检索,请同时参考我们系列文章的资源ID的存储中的内容。

篇后语

本文选用的例子是最为简单的一组,实际也是为了刻意避开graph pattern的解析优化、triple查询结果的合并、block查询结果的join等等分支细节的内容,让读者们能关注整体的查询流程。在之后的源码解析系列文章中,我们会再对这些暂时被我们忽略的问题展开具体讨论。

发表评论