前言
从这一篇的系列文章开始，我们将展开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端直接处理外部查询请求，通过解析查询语句、构造三元组查询顺序、处理查询结果等步骤来完成请求。
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]查询四元组的数量和值，依次写入到消息中。
在我们这个例子中，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等等分支细节的内容，让读者们能关注整体的查询流程。在之后的源码解析系列文章中，我们会再对这些暂时被我们忽略的问题展开具体讨论。
由 udpwork.com 聚合
|
评论: 0
|
要! 要! 即刻! Now!
