在这一篇中，将对4store中涉及的查询结果处理的内容进行解析。查询结果处理主要包括triple的结果合并操作以及triple之上的block结果合并操作等。此外，关于4store实现的一些SPARQL关键字的处理逻辑，也会在这一篇中进行简单的说明。
查询结果的合并
triple查询结果的合并
这里讨论的是一个block之内的多条triple查询结果的合并问题。一个block之内的多条triple之间的关系有两种：
- 没有关系。比如，?x P0 O0和S1 P1 ?y.这两条triple之间是毫无关系的，因为他们之间没有变量的交集。
- 有关系。比如，?x P0 O0和?x P1 ?y.这两条triple就通过x变量连接起来了。
在4store中，结果合并操作在每执行完一条triple后就要执行一次。具体来说，合并主要的执行内容是将之前已有记录合并到新获取到的记录中。它是通过下面这个步骤进行的：
- 当前的block节点若有父节点，则从父节点中复制一份变量值，作为当前block的初始结果；若当前节点没有父节点，则block的初始结果是一个空集合；不妨设这个集合为R。
- 假如我们用集合N来存储一条triple执行返回的结果，N中只包含triple涉及的变量值。
- 接下来执行R和N的合并，4store中是将R的结果向N进行合并，完成合并后又进行如下集合操作R=U, U={}。
- 在合并时，会根据N和R中是否有变量交集来决定合并的策略。N和R中都要至少一个变量是有值，表示N和R是有交集的。
- 若N和R集合没有变量交集，则直接将R中所有的变量值添加到N后面，即可完成结果的合并。
- 若两者有交集，则将R和N分别按照两者有交集部分的变量值进行排序，我们在这里称这些变量为排序变量。然后，按行比较R和N中排序变量的值，剔除N中排序变量值与R不同的那些行。对于N与R中排序变量相同的行，则将R中除排序变量外的其他变量的值复制N中。需要注意的是，R中可能有多行的排序变量值是一样的，如果这些行都与N中的某行相同，那么N需要复制多行来跟这些重复行匹配。
实例分析
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
SELECT ?name, ?nick
WHERE {
?x rdf:type foaf:Person .
?x foaf:nick ?nick .
?x foaf:name ?name
}
查询结果如下：
| count | ?name | ?nick |
|---|---|---|
| 0 | “Libby Miller” | “libby” |
| 1 | “Sean B. Palmer” | “sbp” |
| 2 | “Morten Frederiksen” | “mortenf” |
| 3 | “Damian Steer” | “shellac” |
| 4 | “Jan Grant” | “jang” |
| 5 | “Dan Brickley” | “danbri” |
| 6 | “Norm Walsh” | “ndw” |
| 7 | “Jo Walsh” | “zool” |
| 8 | “Dan Connolly” | “DanC” |
| 9 | “Eric Miller” | “emiller” |
| 10 | “Eric Miller” | “em” |
这里有三条triple:
- Ta：?x rdf:type foaf:Person .
- Tb：?x foaf:nick ?nick .
- Tc：?x foaf:name ?name
需要进行如下三次的结果合并：
- 第一次合并，N和R集合没有变量交集的情况，又因为原来的R是空的，所以那么新的R直接就是N，即Ta执行后获取的变量x的值。
- 第二次合并，N和R集合的变量有交集，是变量x；首先分别将N和R按照变量x的值进行排序；然后逐行检查R和N，将N和R的结果合并；由于我们这次查询中R除了变量x以外没有其他变量，因此实际执行这次合并没有意义。
- 第三次合并，N和R集合的变量依旧有交集，是变量x；仍然是先对N和R按照变量x的值进行排序；然后逐行检查R和N，将N和R的结果合并；与第二次不同的是，这次R中除了排序变量x外，还有变量nick，需要将nick的值合并到N中；另外，注意到R中最后两行，排序变量的值是一样的，在合并时需要在N对应行先复制，然后再合并。
block查询结果的合并
在展开具体block查询结果合并操作的细节说明之前，我们先简要说明一下4store是按照什么顺序来执行triple查询和结果合并的，也就是我们通常所说的执行计划。
- 树状图结构的节点是有序号的，一个节点内的所有triple会按照一定顺序连续执行（关于一个bloick内的triple执行顺序，详见上一篇的“triple重排”这一节）。
- block序号在前的节点，先执行triple查询
- 在开始某个block查询之前，会先复制父节点的所有变量记录，作为这个节点内的triple查询结果合并的初始状态
- 执行所有节点的triple查询之后，再进行block间的查询结果合并
然后，我们再继续讨论如何执行block间的查询结果合并
- 按照block节点的顺序从后向前遍历，寻找有子节点的节点
- 将找到的这个节点与其子节点进行结果合并
- 需要注意的是，若这个节点有若干个子节点，则按照block节点的顺序从前往后的方式进行结果合并
按照block节点的顺序从后往前遍历寻找父节点的思路，是比较非常容易理解的。因为只有这样进行合并，才能与sparql的查询语句的语音相对应，我们需要先执行最底层的block节点的结果合并之后，再去执行上层block节点的查询结果合并。这一点就与我们的表达式计算是十分相似的。
那么，为什么在执行子节点合并的时候，有需要按照从前往后的顺序了呢？这是为了保证Optional节点能够在一个正确的相对位置进行结果合并，否则Optional节点将可能和错误的查询结果进行合并操作（待考证#TODO）。
接下来，我们将具体介绍每个类型的节点在执行查询结果合并时分别有什么特点，然后再通过一个实例来进一步解释整个问题。
查询结果合并的不同类型
JOIN
JOIN的逻辑与之前triple查询结果合并的逻辑基本是一样的，读者们也可以直接参考前面章节中步骤描述。首先，判断当前要合并block与之前的结果是否在变量上有交集。若没有交集，则直接将两者的结果合在一起，不需要做过滤。若前后block结果存在交集，即有“排序变量”，则需要先对两个block的查询结果按照排序变量进行排序，然后再用两个指针分别指向两个结果集合，然后从前往后对两个block的查询结果进行逐行扫描。当发现排序变量一致的行时，对结果进行替换。同时，也特别需要注意一个block中存在排序变量值连续相同的情况，此时需要复制另外一个block的对应行，再执行结果替换。
OPTIONAL
在4store中，称这种合并方式为LEFT_JOIN，与SQL中的概念是一致的。执行LEFT_JOIN的步骤，与JOIN有很多相似的地方。首先，也需要判断当前要合并block与之前的结果是否在变量上有交集。若没有交集，则直接将两者的结果合在一起，不需要做过滤。若前后block结果存在交集，即有“排序变量”，则按照如下步骤进行结果合并：
- 分别对两个block的查询结果，按照排序变量的值进行排序（不妨假定结果是从小到大排列的，两个结果结合分别为bf和bt）
- 用两个指针分别指向两个结果集合，不妨称为pf和pt；pf指向原始的block结果，而pt指向optional block的结果
- 比较pf和pt行对应的排序变量值，如果pf的值偏小，则继续保留pf行的内容，然后pf指向下一行
- 如果两者的值相同，则对结果进行合并
- 同时，也需要注意block中排序变量值重复的问题。
因为在OPTIONAL结果合并之后，再去重新收集当前添加的变量值，然后再处理这个节点对应的表达式检查，将是非常困难的。因此，我们在执行LEFT_JOIN之前，会先处理表达式检查。
UNION
UNION操作的逻辑实际是最为简单的，就是直接将两个block的结果集合进行相加，甚至都不会检查这两个查询结果集合中是否存在重复（需要进一步研究关于SPARQL语言中UNION的定义是否包含去重的；从集合的UNION操作来看，是需要去重的）。
下面是关于UNION操作的一个非常简单的例子
block A：
| count | ?a | ?b | ?c |
|---|---|---|---|
| 0 | a00 | b00 | null |
| 1 | a01 | b01 | null |
| 2 | a02 | b02 | null |
block B：
| count | ?a | ?b | ?c |
|---|---|---|---|
| 0 | a10 | null | c10 |
| 1 | a11 | null | c11 |
| 2 | a12 | null | c12 |
block A UNION block B：
| count | ?a | ?b | ?c |
|---|---|---|---|
| 0 | a00 | b00 | null |
| 1 | a01 | b01 | null |
| 2 | a02 | b02 | null |
| 0 | a10 | null | c10 |
| 1 | a11 | null | c11 |
| 2 | a12 | null | c12 |
4store中，定义UNION节点时是定义同一个Union Group下的节点的都为Union节点。一个Union Group内的节点是按照如上所示的方式进行查询结果合并的，合并之后的Union Group的查询结果还是需要跟其他的block进行JOIN类型的结果合并。为了完成以上操作，会先在Union Group中选择节点序号最大的节点最为Primary节点；在Union Group中的其他节点，会首先将结果与Primary节点进行UNION合并；然后，Primary节点收集了整个Union Group内的查询结果后，再与其他节点进行JOIN合并。
UNION节点内，若存在表达式也会先执行表达式检查，在执行之后的结果合并操作。
MINUS
MINUS合并操作如其名字所称，执行的集合减法操作，其执行操作与JOIN操作也有一些相似之处。
首先，判断当前要合并block与之前的结果是否在变量上有交集。若没有交集，则直接返回被减集合。若前后block结果存在交集，即有“排序变量”，则按照如下步骤进行结果合并：
- 分别对两个block的查询结果，按照排序变量的值进行排序（不妨假定结果是从小到大排列的，两个结果结合分别为bf和bt）
- 用两个指针分别指向两个结果集合，不妨称为pf和pt；pf指向被减的block结果，而pt指向MINUS block的结果
- 如果pf和pt行对应的排序变量值不相等，则保留pf行
- 如果两者的值相同，则跳过pf指向的行
实例分析
这里我们再次引入上一篇中树状结构压缩之后的结果，作为我们的分析实例。完成整个树状结构的block结果合并，需要涉及JOIN、OPTIONAL、UNION等类型的block结果合并操作。
在上面的实例中，因为经过了结构压缩，只剩下B0节点有子节点，然后在执行节点的合并操作时，按照其子节点序号从小大的顺序执行。首先是B3，B3和B4是UNION节点，且B3不是Primary的UNION节点，因此先执行 B4 = B3 UNION B4 ；然后是B4，B4是Primary的UNION节点，执行 B0 = B0 JOIN B4；接下来是B5，因为B5上有表达式C1，先执行表达式C1的检查，然后再执行 B0 = B0 LEFT_JOIN B5；最后还需要执行B0节点上的表达式C0的检查，才能将结果返回。
查询结果的处理
表达式处理
/** * rasqal_op: * @RASQAL_EXPR_AND: Expression for AND(A, B) * @RASQAL_EXPR_OR: Expression for OR(A, B) * ... * @RASQAL_EXPR_UMINUS: Expression for -A. * @RASQAL_EXPR_PLUS: Expression for +A. * @RASQAL_EXPR_MINUS: Expression for A-B. * @RASQAL_EXPR_STAR: Expression for A*B. * @RASQAL_EXPR_SLASH: Expression for A/B. * ... * @RASQAL_EXPR_SUM: Expression for LAQRS select SUM() aggregate function * @RASQAL_EXPR_AVG: Expression for LAQRS select AVG() aggregate function * @RASQAL_EXPR_MIN: Expression for LAQRS select MIN() aggregate function * @RASQAL_EXPR_MAX: Expression for LAQRS select MAX() aggregate function * ... * @RASQAL_EXPR_ISNUMERIC: Expression for SPARQL 1.1 isNUMERIC(expr) * @RASQAL_EXPR_YEAR: Expression for SPARQL 1.1 YEAR(datetime) * @RASQAL_EXPR_MONTH: Expression for SPARQL 1.1 MONTH(datetime) * @RASQAL_EXPR_DAY: Expression for SPARQL 1.1 DAY(datetime) * ... */
如上所示，Rasqal支持多种表达式类型的解析，据统计目前已经超过了90种。本文肯定无法对这些表达式都进行一一列举说明。只能对表达的基本形式、类型、使用场景以及4store的内部实现机制进行一些介绍。
目前来看，表达式主要在两个场景下被使用：
- Filter节点，通过表达式返回BOOL类型的结果来决定是否过滤当前行的内容。
- SELECT，将表达式的返回值作为一个变量返回。
4store并没有对Rasqal解析得到的表达式结构进行二次解析。在处理运算符时，直接访问Rasqal解析的表达式结构体。Rasqal表达式结构体的定义如下：
struct rasqal_expression_s {
rasqal_world* world;
int usage;
rasqal_op op;
struct rasqal_expression_s* arg1;
struct rasqal_expression_s* arg2;
struct rasqal_expression_s* arg3;
rasqal_literal* literal;
unsigned char *value;
raptor_uri* name;
raptor_sequence* args;
raptor_sequence* params;
unsigned int flags;
struct rasqal_expression_s* arg4;
};
typedef struct rasqal_expression_s rasqal_expression;
表达式可以是一元、二元以及三元的。常见的一元操作符包括：str()、strlen()、COUNT()、SUM()、AVG()、round()等；常见的二元操作符包括：+、-、*、/、substr等；常见的三元操作符包括：regex()、replace()等。根据操作符的类型以及参数的内容我们就能唯一确定这个表达式的处理方式。计算表达式的值是一个递归的过程，比如?x < 10 && ?y != 0 || strlen(?z) < 5这样的一个表达式，经过Rasqal的解析就变成了：
操作符”||“是最上层的操作符，将被作为最终的结果返回。但在计算操作符前，会分别先计算其参数对应的两个表达式的值。递归计算每个参数的值，然后执行操作符对应的操作，就是执行表达式的方式。
有许多表达式的计算，都要涉及变量的内容值。因此，在执行表达式计算之前往往需要获取根据变量的rid，向服务端请求资源值，然后才能继续表达式操作。
SPARQL关键字
ORDER BY
ORDER BY关键字支持升序和降序两种排序，在降序时需要显示标明DESC，而升序时query中是否标明ASCE是可选的。
ORDER BY操作是在在获取所有需要的四元组之后，根据rid获取资源数据之前的时候，开始执行的。执行ORDER BY时，会先获取rid对应的资源，然后再根据获取到的资源值，来对结果进行排序。
需要注意的是，ORDER BY排序时，支持使用多个变量作为排序的key。4store在处理一个变量和多个变量作为排序key时是不同的。前者会首先获取这以列中的所有rid，然后再向服务端发出批量资源检索的请求。而后者，4store则是十分暴力的方法，每次只检索一条rid对应的资源内容，逐条获取所有需要排序的资源值，然后再做排序操作。
4store区别化处理ORDER BY请求的设计虽然也可以理解，因为大多数情况下我们在使用ORDER BY时，都是对一个变量进行排序的。但是，多变量的这种处理方式还是太过潦草了，合并实现两种情况的处理应该也不会花费太多的时间的。
LIMIT
LIMIT关键字的实现是非常简单的：在最终获取资源信息并按行输出的过程中，进行记数。一旦记数超过了query中设定的limit值，则结束资源获取和信息输出的过程。
在这里，我们还要提的是另外一个LIMIT，它是4store特有的一个参数：soft_limit。soft_limit不是通过直接限制最终输出结果的数量来达到limit的目的的，而是通过限制每一次triple查询返回结果的数量来完成的。在默认情况下，用户并不设定soft_limit参数，soft_limit取默认值998。这就意味着一次triple查询一个segment最多只能返回998条数据。当query中有ORDER BY关键字时，soft_limit无效。因为排序需要先获得所有的数据，不能限制。
DISTINCT
DISTINCT关键字的含义是对query的结果进行去重，使得最终输出的结果不包含重复项。
因此，DISTINCT最为基本的处理方式是对最终的输出结果进行一个排序，然后去重。为了进一步提高处理效率，如果query是需要DISTINCT处理的，4store在处理完每一次triple查询之后也会执行排序与去重。
GROUP BY
这个关键字与我们在一般的关系数据库中用到的SQL中的GROUP BY在含义上是一致的。为了完成group by的功能，4store会在完成query的四元组检索之后，执行DISTINCT操作之前，先加入一个名为_group的新变量。当我们只使用一个变量进行group by操作时，_group变量保存的rid内容则与group by变量的内容是完全一致的。但当我们group by使用了多个变量时，则_group变量中的rid值是这几个变量的rid进行一些异或等位操作之后的值（这些操作虽然也并不完全保证能避免冲突，但概率相对来说还是非常非常低的）。得到所有_group变量对应的rid后，再对所有行按照_group变量的rid进行排序。
在输出结果时就可以根据_group变量来判断哪些行是同一个group的，而一些SUM、COUNT等算数统计操作也可以很方便的完成。
HAVING
从目前测试和代码上来看，4store并不支持HAVING关键字的处理。
由 udpwork.com 聚合
|
评论: 0
|
要! 要! 即刻! Now!