面向大规模RDF图数据的SPARQL并行查询方法

摘要

本发明涉及RDF图数据处理，为提供一种对大规模RDF图数据的高效并行查询处理方法，减少磁盘读写次数，提高查询效率，为此，本发明采用的技术方案是，面向大规模RDF图数据的SPARQL并行查询方法，包括下列步骤：1)使用整体同步并行BSP模型描述RDF图数据；2)使用资源的URI来标记；3)对于RDF图数据集中的每一条三元组；4)对于3)中的每一条边e，使用URI_r作为e_r的标记；5)获得用户提交的查询请求q₀；6)选择不同的传播路径，并行传播；7)利用贪心算法评估q_i-1中的每条子句所包含的信息量；8)重复6)和7)，直到所有子句都经过绑定。本发明主要应用于图数据处理。

主权项

一种面向大规模RDF图数据的SPARQL并行查询方法，其特征是，包括下列步骤：面向大规模RDF图数据的SPARQL并行查询方法，包括下列步骤：1)使用整体同步并行BSP（Bulk Synchronous Parallel字头缩写）模型描述RDF图数据，RDF图数据中的每一个资源都被具体为一个可执行计算的BSP中的计算单元；2)使用资源的URI来标记每一个与该资源对应的计算单元；3)对于RDF图数据集中的每一条三元组：主语计算单元S,谓语P,宾语计算单元O，建立主语计算单元S到宾语计算单元O的有向边e，使用谓语P的URI作为e的标记，并将e的相关信息保存在主语计算单元S的本地数据域中；4)对于3)中的每一条边e，建立一条方向相反的边e_r，使用URI_r作为e_r的标记，其中URI为谓语P的URI，并将e_r的相关信息保存在宾语计算单元O的本地数据域中；5)获得用户提交的SPARQL查询请求q₀，分析q₀，利用贪心算法评估q₀中每条子句分别包含的信息量，将包含信息量最多的子句tp_i，i为计数器，初始时i=1，作为首要待处理子句，将q₀发送给tp_i的主语计算单元S，若S是未知变量，则发送给宾语计算单元O；6)S或O接收到q_i‑1时，在正向边或反向边中查找满足tp_i的可能解的集合E_i，并根据E_i中的信息对q_i‑1中的变量进行绑定，得到部分绑定后的查询q_i，由于可能出现多个互不矛盾的绑定可能，所以存在多个不同的q_i，每个q_i根据所包含信息的不同，选择不同的传播路径，并行传播；7)i=i+1，利用贪心算法评估q_i‑1中的每条子句所包含的信息量，将包含信息量最多的子句tp_i作为首要待处理子句，将q_i‑1发送给tp_i的主语计算单元S，若S是未知变量，则发送给宾语计算单元O；8)重复6)和7)，直到所有子句都经过绑定，且各个子句绑定变量时没有出现冲突，如果得到多于0个查询结果，则返回这些结果。