公开(公告)号：CN102332009A

公开(公告)日：2012-01-25

申请号：CN201110259125.2

申请日：2011-09-02

Applicant: 北京大学

Inventor： 许坤 ,  赵东岩 ,  邹磊 ,  贾爱霞

IPC: G06F17/30

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

公开(公告)号：CN102332009B

公开(公告)日：2013-09-04

申请号：CN201110259125.2

申请日：2011-09-02

Applicant: 北京大学

Inventor： 许坤 ,  赵东岩 ,  邹磊 ,  贾爱霞

IPC: G06F17/30

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