(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210660050.7 (22)申请日 2022.06.13 (71)申请人 天津大学 地址 300072 天津市南 开区卫津路9 2号 (72)发明人 冯帆　张小旺　 (74)专利代理 机构 天津市北洋 有限责任专利代 理事务所 12 201 专利代理师 李素兰 (51)Int.Cl. G06F 16/2453(2019.01) G06F 16/2455(2019.01) G06F 16/22(2019.01) (54)发明名称 基于递归索引树的克林闭包正则路径查询 优化方法 (57)摘要 本发明公开了一种基于递归索引树的克林 闭包正则路径查询优化方法， 步骤1、 对由(s,p, o)三元组构成的RDF数据图进行键值对转化处 理； 步骤2、 将字符串转化为编码数据； 步骤3、 进 行整个数据图的键值对存储； 步骤4、 对 克林闭包 进行细分， 具体 分为单谓词克林闭包和表达式克 林闭包； 步骤5、 遍历整个键值对存储， 通过将克 林闭包修饰的正则路径查询所需信息提取成递 归索引树等形式， 实现谓词及单谓词克林闭包和 表达式克林闭包这两种克林闭包形式的正则路 径查询。 与现有技术相比， 本发明极大地缩短了 克林闭包查询的执 行时间， 适 合广泛应用。 权利要求书1页 说明书6页 附图5页 CN 115062054 A 2022.09.16 CN 115062054 A 1.一种基于递归索引树的克林闭包正则路径查询优化方法， 其特征在于， 该方法包括 以下步骤： 步骤1、 对由(s,p,o)三元组构成的RDF数据图进行键值对转化处理， 将谓词p作为键， 主 语s和宾语o对作为 值； 步骤2、 将字符串转 化为编码数据； 步骤3、 进行整个数据图的键值对存储， 进而把整个数据图的键值对存储划分为多个数 据簇， 其中每 个数据簇用于存放具有相同谓词的主、 宾语对； 步骤4、 对克林闭包修饰的查询进行细分， 具体分为单谓词克林闭包和表达式克林闭 包； 步骤5、 首先， 遍历整个键值对存储， 对每个数据簇进行克林闭包的预处理， 即： 遍历整 个键值对存储， 对每个数据簇进 行克林闭包的预 处理， 其中最主要的就是单谓词克林闭包， 为其生成递归索引树， 方便后续的查询执行； 对表达式克林闭包， 获得其最大递归步数， 将 克林闭包的无穷匹配操作转化为有界递归， 从而降低克林闭包查询的复杂度； 其次， 实现谓 词及单谓词克林闭包和表达式克林闭包这两种克林闭包形式的正则路径查询， 将谓词生成 的答案和克林闭包生成的答案区分开来做连接操作， 通过规划结果表空间的方式来分割结 果， 对同一代生成的答案进行 标记， 区分开 来。 2.如权利要求1所述的一种基于壁心荧光图像灰度值的地面原油粘度预测方法， 其特 征在于， 所述RDF数据图包括社交关系RDF数据图、 生物信息RDF数据图或交通网络RDF数据 图。权　利　要　求　书 1/1 页 2 CN 115062054 A 2基于递归索引树的克林闭包正则路径查询优化方 法 技术领域 [0001]本发明涉及搜索技术领域， 具体涉及被克林闭包修饰的正则路径查询的优化方 法。 背景技术 [0002]资源描述框架(Resource  Description  Framework， 简记为RDF)是由万维网联盟   (W3C)开发的一种数据模 型， 用于表 示Web上的链接数据。 RDF图中一共有三种类型： IRIs、 空 节点和文字。 SPO每个部分的类型约束包括： (1)主语可以是IRI或空节点。 (2)谓词是IRI。 (3)宾语三种类型都可以。 IRI是URI或者URL的泛化和推广， 在整个网络或者图中唯一定义 了一个实体/资源， 和身份证号类似； 文字是字面量是带有数据类型 的纯文本， 空节点是没 有IRI和文字的资源， 或者说匿名资源。 元组(s,p,o)  称为RDF三元组， 其中： s是主语， p是谓 词(也称为属性)， o是宾语。 一个RDF  数据图G(V,E,L,Ψ)是一个有向的、 有标签的多重图， 其中： V是一组表 示实体和对象 的数据节 点， G(V,E,L,Ψ)是一组有向边， E表 示G中三元 组的 总数， L是一组谓词， Ψ是一个带有Ψ:E →L的标记函数。 令Q＝(x,r,y)是RDF图G(V,E,L,Ψ) 上的正则路径 查询， 其中： x,y∈V是变量， r是字母L上的正则表达式。 正则表达式r 递归定义 为 r:＝|ε||p||r/r||r*|， 其中p∈L， 其中， /表示路径的连接、 /表示或， *表示克林闭包， / 表示或。 [0003]正则路径查询Q在G上的评估结果是给定一个图G和一个正则路径查询Q，  RG＝ {(vi,vj)|(vi,vj)}两节点路径满足Q中的正则表达式r。 发明内容 [0004]为了克服现有技术存在的技术问题， 本发明提出了一种基于递归索引树的克林闭 包正则路径查询优化方法， 聚焦于被克林闭包修饰的正则路径查询， 通过数据预 处理， 将克 林闭包所需的结果以递归索引树的形式存放， 当执行克林闭包查询时可之 间从树上获取答 案分支。 [0005]本发明利用以下的技 术方案来实现： [0006]一种基于递归索引树的克 林闭包正则路径查询优化方法， 该 方法包括以下步骤： [0007]步骤1、 对由(s,p,o)三元组构成的RDF数据图进行键值对转化处理， 将谓词p作为 键， 主语s和宾语o对作为 值； [0008]步骤2、 将字符串转 化为编码数据； [0009]步骤3、 进行整个数据图的键值对存储， 进而把整个数据图的键值对存储划分为多 个数据簇， 其中每 个数据簇用于存放具有相同谓词的主、 宾语对； [0010]步骤4、 对克林闭包修饰的查询进行细分， 具体分为单谓词克林闭包和表达式克林 闭包； [0011]步骤5、 首先， 遍历整个键值对存储， 对每个数据簇进行克林闭包的预处理， 即： 遍 历整个键值对存储， 对每个数据簇进行克林闭包的预处理， 其中最主要的就是单谓词 克林说　明　书 1/6 页 3 CN 115062054 A 3