太阳城集团

  • / 9
  • 下载费用:30 金币  

一种大规模知识图谱复杂路径查询的视图物化方法.pdf

摘要
申请专利号:

CN201611023978.5

申请日:

2016.11.17

公开号:

太阳城集团CN106779150A

公开日:

2017.05.31

当前法律状态:

实审

有效性:

审中

法律详情: 实质审查的生效IPC(主分类):G06Q 10/04申请日:20161117|||公开
IPC分类号: G06Q10/04(2012.01)I 主分类号: G06Q10/04
申请人: 同济大学
发明人: 黄震华; 程久军; 向阳
地址: 200092 上海市杨浦区四平路1239号
优先权:
专利代理机构: 上海科律专利代理事务所(特殊普通合伙) 31290 代理人: 叶凤
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

太阳城集团CN201611023978.5

授权太阳城集团号:

|||

法律状态太阳城集团日:

太阳城集团2017.06.23|||2017.05.31

法律状态类型:

实质审查的生效|||公开

摘要

本发明涉及一种大规模知识图谱复杂路径查询的视图物化方法,包括以下3个模块:1)复杂路径查询的视图选择;2)复杂路径查询的视图存储;3)复杂路径查询的视图维护。复杂路径查询的视图选择模块实现预物化的复杂路径查询集识别、基于视图的复杂路径查询代价评估以及基于代价的复杂路径查询视图选取。复杂路径查询的视图存储模块实现基于内存列式的复杂路径查询视图存储组织以及复杂路径查询视图计算。复杂路径查询的视图维护模块实现基于删除数据集的视图更新、视图自动扩展以及基于插入数据集的视图更新。与现有技术相比,本发明具有良好的异构平台间移植能力以及显著提高大规模知识图谱复杂路径查询效率等优点。

权利要求书

1.一种大规模知识图谱复杂路径查询的视图物化方法,其特征在于,包括以下3个模
块:
1)复杂路径查询的视图选择;
2)复杂路径查询的视图存储;
3)复杂路径查询的视图维护。
2.根据权利要求1所述的一种大规模知识图谱复杂路径查询的视图物化方法,其特征
在于,所述的复杂路径查询的视图选择过程如下:
1)预物化的复杂路径查询集识别;
2)基于视图的复杂路径查询代价评估;
3)基于代价的复杂路径查询视图选取。
3.根据权利要求1所述的一种大规模知识图谱复杂路径查询的视图物化方法,其特征
在于,所述的复杂路径查询的视图存储过程如下:
1)基于内存列式的复杂路径查询视图存储组织;
2)复杂路径查询视图计算。
4.根据权利要求1所述的一种大规模知识图谱复杂路径查询的视图物化方法,其特征
在于,所述的复杂路径查询的视图维护过程如下:
1)基于删除数据集的视图更新;
2)视图自动扩展;
3)基于插入数据集的视图更新。

说明书

一种大规模知识图谱复杂路径查询的视图物化方法

技术领域

本发明涉及一种大规模知识图谱复杂路径查询的视图物化方法,属于计算机应用
技术领域。

背景技术

在大数据时代,知识图谱是用来组织和可视化大数据的一种重要工具,旨在描述
和刻画真实世界中存在的各种实体以及实体间的关系,通常用有向图来组织和表示。图中
的节点表示实体,而图中的边则由关系构成,关系用来连接两个实体,刻画它们之间的关
联。

通常,我们用G(E,R)来表示知识图谱,其中E={ei}为所有实体组成的集合,R={r
<ei,ej>}为实体间关系的集合,r<ei,ej>表示实体ei到ej的关系。不难看出,在多数情况下,r
<ei,ej>≠r<ej,ei>。与现有的研究工作类似,我们将知识图谱G用资源描述框架RDF
(Resource Description Framework)三元组的集合来表示,即G(E,R)={(ei,r,ej)}。目前
比较主流的知识图谱包括Freebase、YAGO、Dbpedia、Internet Movie Database等。

复杂路径查询是深度分析和挖掘知识图谱,进而发现知识图谱隐含线索与规律的
重要手段,目前成为知识图谱理论及技术领域的一个研究热点和重点。目前,学术界和工业
界通常用Datalog语言来表达知识图谱上的复杂路径查询。一条复杂路径查询CQ可以用一
个Datalog语言规则集合表示,例如CQ用如下4条规则组成的集合来表达:

规则1:P(x,r,y):-a(x,r1,y);

规则2:P(x,r,z):-P(x,r,z)∧P(y,r,z);

规则3:Q(x,v,y):-a(x,r,y)∧P(x,r,z);

规则4:P(x,v,y):-b(x,w,y)∧Q(x,v,z)。

在上面所给的4条规则中,“:-”的左边部分称作规则的头部,右边部分称作规则的
规则体。x,y,z表示实体,r,v,w表示关系。在规则体中,a和b为知识图谱中存在的已知的RDF
三元组事实,称作静态谓词;而在规则头部中,P和Q为复杂路径查询CQ所要得到的RDF三元
组事实,称作查询谓词。

目前,国内外有一些知名的实验室团队在做这类的研究工作并取得了较好的应用
成果,例如加州大学洛杉矶分校(University of California,Los Angeles)的Alexander
Shkapsky团队、阿姆斯特丹自由大学(VU University Amsterdam)的Jacopo Urbani团队、
牛津大学(University of Oxford)的Bernardo Cuenca Grau团队、卡拉布里亚大学
(University of Calabria)的Valeria Fionda团队、中国人民大学的X.Zhang团队以及同
济大学的Y.Xiang团队等。

然而我们发现,在大数据时代,知识图谱的规模非常巨大,里面包含着海量的实体
和关系。因此,如果每次复杂路径查询均从零开始处理,其必导致查询的太阳城集团代价极大。而
且当多个用户同时提交复杂路径查询时,系统的处理效率将非常低,其响应速度将非常慢。

发明内容

本发明的目的就是为了克服上述现有技术存在的缺陷,而提出一种大规模知识图
谱复杂路径查询的视图物化方法。该方法首先识别用户频繁提交的复杂路径查询集合,并
基于代价的方式选取与复杂路径查询集合相关的视图进行物化;其次,基于内存列式的组
织策略将待物化的复杂路径查询视图进行计算和存储;最后,当知识图谱动态变化时,对复
杂路径查询视图自动进行增量更新和高效维护。在实际应用中,本发明能够显著提高大规
模知识图谱上复杂路径查询的效率以及降低多用户并发查询的系统响应太阳城集团。

本发明的目的可以通过以下技术方案来实现:

1.一种大规模知识图谱复杂路径查询的视图物化方法,其特征在于,包括以下3个
模块:

1)复杂路径查询的视图选择;

2)复杂路径查询的视图存储;

3)复杂路径查询的视图维护。

2.根据权利要求1所述的一种大规模知识图谱复杂路径查询的视图物化技术,其
特征在于,所述的复杂路径查询的视图选择过程如下:

1)预物化的复杂路径查询集识别;

2)基于视图的复杂路径查询代价评估;

3)基于代价的复杂路径查询视图选取。

3.根据权利要求1所述的一种大规模知识图谱复杂路径查询的视图物化技术,其
特征在于,所述的复杂路径查询的视图存储过程如下:

1)基于内存列式的复杂路径查询视图存储组织;

2)复杂路径查询视图计算。

4.根据权利要求1所述的一种大规模知识图谱复杂路径查询的视图物化技术,其
特征在于,所述的复杂路径查询的视图维护过程如下:

1)基于删除数据集的视图更新;

2)视图自动扩展;

3)基于插入数据集的视图更新。

与现有技术相比,本发明具有以下优点:

1、能够显著提高大规模知识图谱上单个复杂路径查询的效率;

2、能够显著降低多个复杂路径查询并发执行的系统响应太阳城集团;

3、具有良好的异构平台间的移植能力。

附图说明

图1为本发明的技术架构图。

具体实施方式

下面结合附图和具体实施例对本发明进行详细说明。

实施例

1、复杂路径查询的视图选择实施方法

(1)预物化的复杂路径查询集识别

由于知识图谱上的可以提交的不同复杂路径查询的数量巨大,因此在现实应用
中,不可能物化所有的复杂路径查询视图,而且有些复杂路径查询不是经常需要提交,因此
也没必要对它们进行物化处理。为此,本发明首先需要识别预物化的复杂路径查询集,主要
通过以下3个步骤来具体实施:

步骤1:获取最近一个太阳城集团周期(例如一个星期)用户在系统中提交的所有复杂路
径查询集合CQS={CQ1,…,CQn},其中每个查询CQi(1≤i≤n)对应一个Datalog语言规则集
DLi;

步骤2:对于复杂路径查询集合CQS,计算CQS的最小超查询msQ,即它所对应的
Datalog语言规则集

步骤3:基于步骤1和步骤2分别得到的CQS和msQ,构造查询空间格Θ(msQ,CQS,π),
其中π表示子集关系,即如果CQ1πCQ2,那么有查询空间格Θ(msQ,CQS,π)构造过
程如下:

步骤3.1:初始化队列L为空,并将msQ放入L中;

步骤3.2:将msQ作为Θ(msQ,CQS,π)的根节点;

步骤3.3:循环如下操作,直到L为空为止:

1)从L中取出第一个元素FQ;

2)记FQ所对应的Datalog语言规则集为DLf,获取只比DLf少一条规则的k=|DLf|个
子集

3)对于2)中获取的做如下两个判断:i)如果已在Θ(msQ,CQS,
π)中,那么在Θ(msQ,CQS,π)中直接增加条有向边,从DLf指向否则将加入Θ
(msQ,CQS,π)中,并增加条有向边,从DLf指向ii)如果那么将放入L
中;

步骤3.4:删除Θ(msQ,CQS,π)中所有不在CQS里面的叶子节点。

(2)基于视图的复杂路径查询代价评估

对于查询空间格Θ(msQ,CQS,π)中存在路径的两个复杂路径查询CQ1和CQ2,并且有
CQ1πCQ2。如果CQ2已完成视图物化,那么CQ1的查询结果可以从CQ2视图来计算,而没必要以大
规模知识图谱为输入参数从零开始计算。基于该策略,本发明通过如下5个步骤来具体实施
代价评估:

步骤1:获取CQ2视图所包含的RDF事实表F1,…,Fm,其中m为CQ2视图中事实表的个
数,并记X=(F1,…,Fm);

步骤2:通过从X=(F1,…,Fm)中进行有放回采样10000次,得到10000个采样样本数

步骤3:利用样本数据计算X的近似均值和标准差进而获取CQ2的数据分布
即其概率密度函数为:


步骤4:在CQ2视图上,重复如下操作3000次:以满足数据分布的方式,
从CQ2视图中抽取1/300比例的数据样本sCQ,计算从sCQ获取CQ1的太阳城集团代价timeC;记3000次
操作全部完成后所得出的太阳城集团代价分别为:timeC1,…,timeC3000;

步骤5:基于步骤4,获取从CQ2视图计算CQ1的太阳城集团代价为:


(3)基于代价的复杂路径查询视图选取

在(1)和(2)的基础上,本发明基于代价的方式从查询空间格Θ(msQ,CQS,π)中选
取若干个复杂路径查询视图进行物化,使得这些视图能够快速处理Θ(msQ,CQS,π)的叶子
节点,即CQS={CQ1,…,CQn}。本发明通过如下4个步骤来具体实施:

步骤1:初始化中间变量temp,令temp=CQS={CQ1,…,CQn};

步骤2:检测给定的空闲磁盘空间容量Ψ是否超过temp中复杂路径查询的视图大
小总和,如果超过,那么直接将temp中复杂路径查询的视图进行物化,然后退出程序,否则
执行步骤3;

步骤3:在temp中计算视图大小最小的两个复杂路径查询CQx和CQx,并在查询空间
格Θ(msQ,CQS,π)中获取CQx和CQy的最小共同父节点CQ’,即CQ’满足如下3个条件:1)CQxπ
CQ’,2)CQyπCQ’,3)Θ(msQ,CQS,π)中不存在一个复杂路径查询CQ”,使得CQxπCQ”及CQyπCQ”
成立,并且CQ’πCQ”;

步骤4:调整temp=temp∪{CQ’}-{CQx,CQy},并返回到步骤2。

2、复杂路径查询的视图存储实施方法

(1)基于内存列式的复杂路径查询视图存储组织

一旦对复杂路径查询视图完成选择之后,本发明对每个被选中的复杂路径查询视
图进行物化存储。首先,本发明对这些复杂路径查询视图的存储格式进行有效的安排和组
织,以便提高后面的视图计算效率。

不失一般性,对于每个复杂路径查询CQ,其所对应的Datalog语言规则集合为记为
DL={rule1,…,ruleh}。本发明首先获取这h条规则所包含规则头部的l个查询谓词P1,…,
Pl,然后针对每个查询谓词Pi(1≤i≤l),在内存中将其组织为一个RDF三元组的事实簇队列
List(Pi),而每个事实簇FC包含三部分内容:执行序号s、规则编号rn以及核心事实表FT。执
行序号s表示当前视图计算已进行到第s步,每一步执行一条规则;规则编号rn表示目前正
在执行第rn条规则,其中1≤rn≤l;核心事实表用来存储当前视图计算所产生的RDF三元组
事实。

对于每一步所产生的核心事实表FT,本发明采用基于内存的列式存储策略进行存
储组织。由于FT存储RDF三元组事实,因此,FT包含三个列c1,c2,c3,每个列为RDF三元组的一
个分量。首先对第一个列c1的取值从小到大进行排序并存储,然后,针对第一列中的相同
值,对第二个列c2的取值从小到大进行排序并存储,最后,针对第二列中的相同值,对第三
个列c3的取值从小到大进行排序并存储。

另外,为了提高内存空间的利用率,在列式存储过程中,本发明基于行程长度编码
(RLE:run-lengh encoding)策略对核心事实表FT中的每一列进行压缩处理,即针对每一列
ci(1≤i≤3),如果它上面的相同值出现了n次,那么本发明用来代替n次的重复存
储。

(2)复杂路径查询视图计算

对于每个待物化的复杂路径查询CQ:DL={rule1,…,ruleh},在(1)中所给的视图
存储组织的基础上,视图计算的任务是将第s步的执行规则编号rn所对应的核心事实表FT
的结果进行物化存储,其核心工作是求得FT所包含的所有RDF三元组事实。本发明通过如下
6个步骤来具体实施:

步骤1:在DL中获得与规则编号rn头部查询谓词P相关的规则集合
进而针对DL(P)中的每个规则rule’i(1≤i≤k)获取它的头部查询
谓词Pi,即rn表示为:P:-P1,P2,…,Pk;

步骤2:对于每个查询谓词Pi(1≤i≤k),获取它的事实簇队列List(Pi),进而获取
List(Pi)所包含的所有核心事实表FT(Pi);

步骤3:获取查询谓词P目前事实簇队列List(P)中所包含的所有核心事实表FT
(P);

步骤4:计算sumFT=FT(P1)∞FT(P2)∞…∞FT(Pi),其中∞表示自然连接操作;

步骤5:计算FT=sumFT-FT(P);

步骤6:在List(P)中增加一个新的事实簇nFC包含三部分内容:执行序号s、规则编
号rn以及核心事实表FT。

3、复杂路径查询的视图维护实施方法

当底层知识图谱的数据发生变化时,本发明物化的复杂路径查询视图也需要随之
动态更新,其增量维护过程如下:

(1)基于删除数据集的视图更新

假定本次知识图谱所删除的RDF三元组事实集合为Drdf={(x,r,y)},即对于Drdf中
的每一个事实(x,r,y),x和y之间现在不存在关系r。

基于集合Drdf中的每一个事实(x,r,y),本发明更新每个已物化的复杂路径查询
CQ。假定CQ相应的Datalog语言规则集DL中有k个规则rule1,…,rulek涉及(x,r,y),那么我
们首先获取这k个规则的头部查询谓词所对应的事实簇队列List(P1),…,List(Pk),然后按
List(P1),…,List(Pk)中的执行序号从小到大顺序遍历其核心事实表FT,并将FT中与(x,r,
y)相关的三元组事实删除。

(2)视图自动扩展

在(1)中,基于删除数据集Drdf中的每一个事实(x,r,y),本发明针对每个物化的复
杂路径查询CQ,从k个事实簇队列List(P1),…,List(Pk)删除与(x,r,y)相关的三元组事实。
然而,我们发现有些被删除的事实能够通过其它已物化的三元组事实来补全,并进行自动
扩展,具体实施如下:

本发明首先将在(1)中被删除的m个三元组事实按照删除的先后顺序进行排序,得
到deF=<(x1,r1,y1),…,(xm,rm,ym)>;然后针对每一个被删除三元组事实(xt,rt,yt)∈deF,
本发明按List(P1),…,List(Pk)中的执行序号从小到大顺序遍历其核心事实表FT,如果
(xt,rt,yt)能够通过FT中的其它三元组事实来推理出来,那么将(xt,rt,yt)添加进FT中。

(3)基于插入数据集的视图更新

假定本次知识图谱所插入的RDF三元组事实集合为Irdf={(x,r,y)},即对于Irdf中
的每一个事实(x,r,y),x和y之间现在存在关系r,而原来不存在该关系。基于集合Irdf中的
每一个事实(x,r,y),本发明更新每个已物化的复杂路径查询CQ:DL={rule1,…,ruleh},具
体实施如下:

步骤1:在DL中获取规则体与(x,r,y)匹配的第一个规则编号rna;

步骤2:将(x,r,y)在rna规则体中的计算结果写入头部查询谓词Pa的第一个事实簇
所对应的核心事实表FT(Pa)中;

步骤3:从规则编号rna开始,循环访问DL中每个规则所对应的规则编号rn’:P’:-
P1,…,Pk,并执行如下操作,记当前执行序号为s:

步骤3.1:对于每个查询谓词Pi(1≤i≤k),获取它的事实簇队列List(Pi),进而获
取List(Pi)的核心事实表FT(Pi)中由于(x,r,y)而新增的三元组事实nFT(Pi);

步骤3.2:获取查询谓词P’目前事实簇队列List(P’)的核心事实表FT(P’)中由于
(x,r,y)而新增的三元组事实nFT(P’);

步骤3.3:计算snFT=nFT(P1)∞nFT(P2)∞…∞nFT(Pi);

步骤3.4:计算nFT=snFT-nFT(P’);

步骤3.5:将nFT插入到执行序号为s所对应的List(P’)核心事实表中。

关 键 词:
一种 大规模 知识 图谱 复杂 路径 查询 视图 物化 方法
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
太阳城集团本文
本文标题:一种大规模知识图谱复杂路径查询的视图物化方法.pdf
链接地址:http://zh228.com/p-6019671.html
太阳城集团我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
葡京赌场|welcome document.write ('');