发明名称 |
一种大规模RDF图的ThetaJoin查询处理方法 |
摘要 |
本发明公开了一种大规模RDF图的ThetaJoin查询处理方法,包括了以下步骤:(1)采用伙伴内存分配的方式分配ID空间,对RDF常量数据进行保序编码。(2)建立数据字典,将RDF三元组数据转化为ID三元组,压缩存储并建立索引。(3)解析含ThetaJoin的SPARQL查询请求,将已知量转化为ID并将变量编码。(4)利用扩展的查询图模型对查询进行表示,查询分解划分星型子查询,为各星型子查询生成执行计划。(5)并行执行各个星型子查询,利用数据的分块和流水线提高并行度,并尽可能早的处理ThetaJoin。(6)将星型子查询内部的变量约束传递给相邻星型子查询,利用连接调度对中间结果执行连接运算,削减中间结果。(7)执行全连接,按照投影变量的顺序将查询结果返回给用户。 |
申请公布号 |
CN105955999A |
申请公布日期 |
2016.09.21 |
申请号 |
CN201610247087.1 |
申请日期 |
2016.04.20 |
申请人 |
华中科技大学 |
发明人 |
袁平鹏;金海;王涛 |
分类号 |
G06F17/30(2006.01)I |
主分类号 |
G06F17/30(2006.01)I |
代理机构 |
华中科技大学专利中心 42201 |
代理人 |
曹葆青 |
主权项 |
一种大规模RDF图的ThetaJoin查询处理方法,其特征在于,包括以下步骤:步骤1采用伙伴内存分配的方式分配ID空间,对RDF常量数据进行保序编码,使得数据的ID大小顺序与原始数据的大小顺序保持一致,并对分配的ID空间建立索引;步骤2建立原始数据与ID相互映射的数据字典,将RDF图数据转化为ID三元组数据进行压缩存储并建立索引;步骤3将用户提交的SPARQL查询语句交给SPARQL解析器,将查询语句中的已知量转化为ID,并对变量进行编码;步骤4将解析后查询语句中的变量、三元组模式、关系模式、表达式模式表示成查询图,对查询图进行优化,将查询图分解为多个星型子查询,为每个星型子查询生成相应的执行计划;步骤5并行的执行各个星型子查询,星型子查询内部利用数据的分块和基于块的流水线scan提高并行度,同时尽可能早的执行星型子查询内部的ThetaJoin;步骤6将星型子查询内部中间结果的变量约束信息传递给相邻的星型子查询,将模式的连接转化为块的连接,采用面向块的连接调度并发执行,削减中间结果;步骤7执行全连接,按照循环嵌套连接的方式执行ThetaJoin,按照投影变量的顺序收集结果集ID,转化为字符串,并输出最终结果返回给用户。 |
地址 |
430074 湖北省武汉市洪山区珞喻路1037号 |