一种大规模数据集上的关系查询方法

摘要

本发明公开了一种大规模数据集上的关系查询方法，属于语义网领域。本方法为：1)计算语义数据有向图G中只包含同一种标签的连通子图；2)合并连通子图，将有向图G划分为若干子图；3)计算合并后的每一子图中最强连通子图C，并计算其二部图；4)将所有子图C的最短路径存储到一路径集合RS中；5)记录划分的每一子图中具有标签非冗余路径的两个点的标签，得到每一子图的标签集合；6)利用标签集合判断有向图G中是否存在符合查询条件的路径；如果有，则返回查询路径结果；否则，在子图之间进行遍历，根据集合RS确定可到达目标节点的子图，然后利用该子图的标签集合返回查询路径结果。本发明支持海量数据的关系查询，并且扩展性强。

主权项

一种大规模数据集上的关系查询方法，其步骤为：1)提供或建立语义数据图的语义数据有向图；2)针对语义数据有向图中每一种标签，计算只包含同一种标签的连通子图；3)对步骤2)得到的连通子图进行合并，将所述语义数据有向图划分为若干子图；4)计算步骤3)合并后的每一子图中最强连通子图C，并计算其二部图，得到进入C的边界点集合S1和从C出去的边界点集合S2；5)对于每一最强连通子图C，利用基于标签的最短路径搜索方法计算S1中每个点到S2中每个点的最短路径，将所有最强连通子图的所述最短路径存储到一路径集合RS中；6)记录步骤3)划分的每一子图中具有标签非冗余路径的两个点的标签，得到每一子图的标签集合；7)利用所述标签集合判断语义数据有向图中是否存在符合查询条件的路径；如果有，则返回查询路径结果；否则，在子图之间进行遍历，根据所述路径集合RS确定可到达目标节点的子图，然后利用该子图的标签集合返回查询路径结果。