知识图谱是人工智能的重要基石,其目前主要有RDF图和属性图两种数据模型,在这两种数据模型之上有数种查询语言.RDF图上的查询语言为SPARQL,属性图上的查询语言主要为Cypher.10年来,各个社区开发了分别针对RDF图和属性图的不同数据管理方法,不统一的数据模型和查询语言限制了知识图谱的更广泛应用.KGDB(knowledge graph database)是统一模型和语言的知识图谱数据库管理系统:(1)以关系模型为基础,提出了统一的存储方案,支持RDF图和属性图的高效存储,满足知识图谱数据存储和查询负载的需求;(2)使用基于特征集的聚类方法解决无类型实体的存储问题;(3)实现了SPARQL和Cypher两种不同知识图谱查询语言的互操作性,使其能够操作同一个知识图谱.在真实数据集与合成数据集上进行的大量实验表明:KGDB与已有的知识图谱数据库管理系统相比,不仅能够提供更加高效的存储管理,而且具有更高的查询效率.KGDB平均比gStore和Neo4j节省了30%的存储空间,基本图模式查询上的实验表明:在真实数据集上的查询速度普遍高于gStore和Neo4j,最快可提高2个数量级.
Knowledge graph is an important cornerstone of artificial intelligence, which currently has two main data models: RDF graph and property graph. There are several query languages on these two data models. The query language on RDF graph is SPARQL, and the query language on property graph is mainly Cypher. Over the last decade, various communities have developed different data management methods for RDF graphs and property graphs. Inconsistent data models and query languages hinder the wider application of knowledge graphs. KGDB is a knowledge graph database system with unified data model and query language. (1) Based on the relational model, a unified storage scheme is proposed, which supports the efficient storage of RDF graphs and property graphs, and meets the requirement of knowledge graph data storage and query load. (2) Using the clustering method based on characteristic sets, KGDB can handle the issue of untyped triple storage. (3) It realizes the interoperability of SPARQL and Cypher, which are two different knowledge graph query languages, and enables them to operate on the same knowledge graph. The extensive experiments on real-world datasets and synthetic datasets are carried out. The experimental results show that, compared with the existing knowledge graph database management systems, KGDB can not only provide more efficient storage management, but also has higher query efficiency. KGDB saves 30% of the storage space on average compared with gStore and Neo4j. The experimental results on basic graph pattern matching query show that, for the real-world dataset, the query efficiency of KGDB is generally higher than that of gStore and Neo4j, and can be improved by at most two orders of magnitude.
知识图谱是人工智能的重要基石, 是新一代人工智能由感知走向认知的重要基础设施[
关系数据库数十年来的发展, 证实了统一的数据模型和查询语言是数据管理技术发展的关键.目前, 知识图谱数据库管理的问题是数据模型、存储方案和查询语言不统一.为此, 我们研发了统一模型和语言的知识图谱数据库管理系统——KGDB(knowledge graph database)
KGDB使用统一的存储方案, 可以支持存储RDF图和属性图两种不同的数据模型; 根据实体的类型进行分块存储, 同时运用基于特征集的聚类方法处理无类型实体, 使之可以归入某一语义相近的类型; 分别提供RDF图和属性图上的查询接口, 可以使用SPARQL和Cypher查询语言对同一知识图谱进行操作, 即允许两种查询语言的互操作.KGDB遵循“统一存储”-“兼容语法”-“统一语义”的技术路线: 在底层存储, 使用相同的存储方案处理不同的知识图谱数据模型; 在查询表达上, 兼容两种面向不同知识图谱数据模型的语法完全不同的查询语言; 而在查询处理上, 将两种语法不同的查询语言对齐到统一的语义, 进而使用相同的查询处理方法.
KGDB的总体架构如
KGDB总体架构图
Architecture of KGDB
(1) 在用户输入层, 用户可输入RDF图数据或者属性图数据;
(2) 在系统处理阶段, 分为两部分: ①经过存储关系转化, 依据存储方案将数据转化为以类型聚类的关系表, 将原始的知识图谱数据进行基于关系的存储; ②查询处理部分, 可以允许用户使用两种查询语言对同一知识图谱进行操作;
(3) 在用户界面层, 用户可以查看规范格式的图模式查询的结果.
现有的知识图谱数据库管理系统因其面向的数据模型的不同, 提出了不同的存储方法.对于RDF图的存储, 可以分为三大类: (1)直接利用RDF三元组的特性进行存储, 例如三元组表(triple table)、水平表(horizontal table)等; (2)根据RDF图数据展现的数据类型特征进行存储, 例如属性表(property table)、垂直划分(vertical partitioning)[
知识图谱三元组数据与关系数据的最大不同是其模式的灵活性, 这给传统的存储和查询处理提出了新问题.为此, 提出了一种基于特征集聚类的处理方法, 根据实体的谓语组进行类型聚类, 并将无类型实体数据依据其关系特征, 归入某类型中, 从而解决知识图谱的统一存储问题.
在查询语言方面, 现有的知识图谱数据库管理系统因面向的数据模型不同, 使用不同的查询语言进行查询处理: SPARQL是RDF图上的查询语言, Cypher是属性图上的主要查询语言.两种查询语言具有不同的语法, 阻碍了在统一存储方案上的查询互操作.为此, 进行SPARQL和Cypher语言的语义对齐, 使之可以操作同一个知识图谱, 而无需区别知识图谱的数据模型.
真实数据集和合成数据集上的大量实验表明: KGDB能够高效地进行知识图谱数据的存储管理和查询处理, 优于现有RDF数据库gStore和属性图数据库Neo4j.
本文的主要贡献如下:
(1) 以关系模型为基础, 提出统一的知识图谱存储方案, 根据数据的类型进行聚类, 支持两种知识图谱主流数据模型(RDF图和属性图)的高效存储; 使用字典编码方法减少数据的存储空间, 满足知识图谱数据的存储和查询负载需求;
(2) 使用基于特征集的聚类方法, 将无类型实体归入谓语组相似的数据类型中, 解决无类型实体数据的存储问题, 使统一存储模型能够应对灵活多变的半结构化数据;
(3) 兼容RDF图数据模型的查询语言SPARQL和属性图数据模型的主流查询语言Cypher的查询语法, 进行两种查询语言的语义对齐, 实现两种查询语言的互操作, 可使用两种语言操作同一个知识图谱;
(4) 在合成数据集和真实数据集上进行大量实验, 分别与现有的RDF图数据管理系统和属性图数据管理系统进行对比实验, 实验结果验证了KGDB统一的存储方案和统一语义的查询处理的有效及高效性.
本文第1节介绍相关工作.第2节介绍预备知识.第3节描述KGDB使用的统一RDF图和属性图的存储模型.第4节阐述查询语言互操作的方法.第5节在真实数据集和合成数据集上进行实验.第6节对全文总结.
随着知识图谱的发展, 各种知识图谱存储方案和查询处理方法不断涌现, 本节将分别介绍两种知识图谱数据模型的现有存储方案及查询方法.知识图谱数据规模的不断增长, 对存储和查询提出更高要求, 分布式知识图谱管理系统成为研究热点之一[
(1) 直接利用RDF三元组特性
三元组表(triple table)将数据对应存储到一个3列结构的表中, 采用三元组表存储方案的代表是3store[
直接利用RDF三元组特性的存储方案最直观简单, 但是存在着诸如稀疏性、空值等空间利用的问题.同一主语对应的谓语可能会有很多, 不同主语之间关联的谓语差异远高于预期, 即使同一类型的主语其谓语差异也不容忽视, 这类存储方案建立的关系表会有很多位置存为空值, 稀疏的关系表严重降低存储性能.
(2) 依据RDF数据语义信息
特征集(characteristic sets, 简称CS)[
依据RDF数据语义信息的存储方案虽然更加精确, 能够利用语义信息优化存储, 但是目前没有见到基于关系的存储方案, 且大多数方案仅有原型系统, 成熟度不足.关系数据库发展至今, 在事务管理、可扩展性等方面的研究基础相对稳固, 基于关系的存储方案可以获得更多的支持.
(1) 基于关系的存储方案
SQLGraph[
因属性图的半结构化数据特征, 上述基于关系的属性图存储方案的灵活度不能完全满足属性图的存储要求, 关系表一旦建立, 修改其结构的代价巨大.而对于如今知识图谱高达数十亿点边结构的数据规模, 需要更加灵活的方案来提高其存储效率.
(2) 基于文档的存储方案
MongoDB[
基于文档的属性图存储方案常被应用在分布式环境下, 而相对于单机环境, 分布式对数据的存储提出了更高的要求, 而使用文件进行大规模数据的存储效率不足以满足数据规模日益增长的属性图的存储和查询要求.目前, 知识图谱的存储方案基本都面向某一种类型的知识图谱并且成熟度不足.为此, 有必要面向知识图谱的两种主流数据模型开发统一的、基于关系的高效存储方案.
Blazegraph[
Neo4j[
目前, 两种知识图谱数据模型拥有各自的查询语言、语法和语义, 虽然在具体的系统上分别进行了优化设计, 但不利于知识图谱查询的多样性, 故亟需研发一种既支持SPARQL又支持Cypher、具有语义互操作能力的系统.
本节将详细介绍相关背景知识, 包括RDF图和属性图的定义.
符号列表
List of notations
符号 | 含义 | 符号 | 含义 |
RDF图 |
三元组分类 | ||
属性图 |
实体特征集 | ||
三元组 | 实体簇统计信息 | ||
属性图点模式 | 两个实体簇 |
||
属性图边模式 | 属性图顶点、边到标签映射 | ||
三元组有限集合 | 属性到属性值的映射 | ||
匹配 | 获取RDF图中边的标签 |
例1:
RDF图示例
An RDF graph example
例2:
属性图示例
A property graph example
本节主要介绍统一的知识图谱存储方案, 此方案基于关系模型实现对RDF图和属性图的兼容表示.之后, 根据所提出的存储方案, 采用基于特征集的聚类算法处理无类型数据, 以更好地支持知识图谱数据存储..
统一存储方案按照实体的类型将其存储到对应顶点类型表
RDF图数据中有3种不同类型的三元组, 下面给出三元组分类的定义.
根据定义3以及例1和例2, 将
对于RDF三元组
属性图因其对顶点和边上的属性提供内置的支持, 在将其映射到统一存储模型时相对容易, 应用下列规则将属性图数据映射到统一存储模型上.
在属性图中, 顶点关系表中的id值仅起到标识作用, 而不具有实际意义; 而RDF图中id表示对应实体的URI, 具有实际意义.为了进行统一的表示, 将实体
例3:根据上述的存储方案, 将
知识图谱统一存储方案
Unified storage scheme for knowledge graph
知识图谱数据根据所提出的统一存储方案, 依据实体和关系的类型进行分别存储.在示例的知识图谱中未给出边属性, 因此边表中的property列为空值.属性图和RDF图对实体或者关系的类型信息均提供了内置的支持, 属性图由标签指定, RDF图由内置的rdf: type指定.这种根据类型对顶点和边进行划分并进行分别存储管理的方式是相对合理的, 能够在一定程度上解决现有知识图谱存储方案中存在的数据冗余与数据稀疏问题.
在建立关系表之后, 各种操作都将以关系表名为基本对象, 给出操作关系表的函数: 存储模型建立的关系表集合是
在知识图谱中, 两节点之间有可能存在多种谓语关系, 即多重属性.对于多重属性的存储问题, KGDB使用第3.1节中介绍的方法, 针对单个主语实体, 存储多个属性键值对, 其中, 属性键对应不同的谓语关系, 属性值对应同一个实体.大多数现有的知识图谱数据存储方案使用字典编码的方法, 将URI或者字面量映射到整数标识符, 即id.映射表有效地实现了字符串到id之间的转换, 并将数据库的空间开销降至最低.KGDB采用了与大多数现有知识图谱存储方案类似的字典编码方法, 压缩存储方案所需的空间资源.
上一节介绍的统一存储模型中, 利用顶点和边的类型对知识图谱数据进行划分, 并存储到相应的顶点表和边表中.但此方案并没有考虑无类型的实体的存储.对于无类型的实体, 基本的存储方案将所有无类型的实体等同对待, 所有无类型的实体存储在一个关系表中.这种统一存储的方法, 一方面在处理无类型实体数量较多的数据集时, 将导致单个关系表过大, 降低查询的效率; 另一方面, 无类型的实体之间并没有关联, 无语义信息, 这与将相同或靠近语义的实体存储在相近空间的初衷相悖.
对于未指定类型的实体, 基于特征集的聚类算法, 将其划分到一个最相近的给定类别中.层次聚类算法可以根据某种距离函数给出结点之间的相似性, 并按照相似度逐步将结点进行合并, 当达到某一条件时, 合并终止.在本节中, 将给出实体的特征集、特征集的距离等定义, 用于测定实体之间的相似性, 从而解决无法对无类型实体进行存储的问题.
RDF图中使用多个三元组来描述一个实体所拥有的特征.实体的特征集[
例4:在某个RDF数据集中, 描述《老人与海》这本书的实体
实体簇
其中,
其中,
●
●
●
根据公式(4), 两个簇之间的距离等于不同时出现在两个簇中的属性所对应的出现次数之和.属性的出现次数可以说明该属性对簇的重要程度, 如对于书籍类型的实体来说, 其所在的簇中作者和标题属性所对应的数值较高.以属性次数的加和作为簇间距离, 可以衡量两个簇之间的相似程度.
基于实体特征集、包含多个实体的簇的特征集统计信息以及簇间距离的定义, 可以对基本的统一存储方案进行优化.基于层次聚类算法, 提出一种基于实体类型的实体聚类算法, 将未给定类型的实体通过聚类的方法划分到一个已知的类型中.
对于实体
为了将两个实体簇进行合并, 需要计算两个实体簇之间的距离, 并找到距离最相近的两个实体簇进行合并.下面给出寻找距离最近实体簇下标的函数: 对于实体簇集合
在聚类的过程中, 将每个实体作为一个单独的簇, 并根据实体的特征集的相似程度自底向上进行簇的合并操作.合并过程中, 需要保证不对两个包含不同类型实体的簇进行合并.
算法1给出了基于特征集的实体聚类算法, 根据实体的特征集进行层次聚类, 可以将实体按照所拥有的特征划分到不同的簇中, 每个簇内的实体属性相似, 即每个簇内的实体趋近于拥有相同的类型.算法首先将实体类型相同的实体合并到一个簇中, 将每个未指定类型的实体各自作为一个单独的簇(第2行~第8行), 根据簇间的距离
输入: 实体集合
输出: 实体簇集合
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
例5:下面通过一个例子对聚类的过程进行说明.
在聚类开始时, rdf: type为书籍的实体有
●
●
●
已知rdf: type为电影的实体有
●
●
●
最后, 没有rdf: type的实体
●
●
故簇
未指定类型的实体
下面给出算法1的正确性证明及复杂度证明.
证明: 算法1首先将根据数据集中数据本身的特点进行数据类型归类: 若实体
算法1的时间复杂度由两部分组成: (1) 算法经过
SPARQL是RDF图上的查询语言, Cypher是属性图之上的主要查询语言.两种不同的查询语言在语法上有较大差异, KGDB以第3节所介绍的统一的存储方案为基础, 建立在存储方案之上的查询过程, 可以使用两种不同的查询语言查询同一个知识图谱, 从而达到查询语言互操作的目的.在文献[
知识图谱查询处理的最基本算子即是基本图模式匹配查询(basic graph pattern, 简称BGP), 这类查询可以看作子图匹配或者子图同构查询.已有的各种知识图谱查询语言均以子图匹配作为核心算子.虽然图数据上的子图匹配查询算法已有很多, 但却缺少同时具备系统性和高效性的面向大规模知识图谱的子图匹配查询处理算法.KGDB基于SPARQL和Cypher语言处理子图匹配查询, 需要建立起两种语言的联系, 将同样的查询意图转化为不同的两种查询表达式, 同时保障两种查询语言处理结果的正确性与高效性.
在本节中将会用到关系代数中的几个经典算子, 如
首先, 给出RDF图基本图模式匹配查询的形式化定义.
(1)
(2) (
(3)
例6:
基本图模式查询示例
A basic graph pattern matching query example
最简单的SPARQL查询语句包括两个部分: SELECT关键字引导的结果子句和WHERE关键字引导的约束子句.KGDB根据SPARQL查询语句的语法进行语义解析, 生成语义树.根据SPARQL查询语句中每部分的语义, 使用下面的转换规则自底向上构建关系代数形式的查询语义树.
对应的, SPARQL语句到查询语义的转化算法如下.
输入: 查询中的三元组集合
输出: 图模式匹配查询的结果关系
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
算法2遍历SPARQL查询中涉及的三元组, 针对不同类型的三元组做出不同的应对措施, 最终形成关系代数表示的查询语义.与存储方案相似, 查询处理也将三元组
证明: 算法2遍历SPARQL查询中涉及的所有三元组, 并根据每条三元组
解决方案, 即给出正确的关系表的连接列表
算法2的时间复杂度由两部分组成: (1)为了生成关系表的连接列表
与SPARQL查询处理类似, 首先给出属性图上的模式匹配查询的形式化定义.
(1) 对点模式
(2) 对于长度为
a)
b) (
(3) 对于长度为
a)
b) (
c)
d) [[
e)
则对于Cypher查询
其中, 表示包的合并.
与SPARQL查询语句相似, 最简单的Cypher查询也主要包括两个部分: MATCH关键字引导的约束子句和RETURN关键字引导的结果子句.KGDB使用下列转换规则对Cypher语句进行处理.
可以看出: 对照KGDB统一的存储模型, Cypher语义的转化相较SPARQL更加容易, SPARQL需要进行三元组的分类, 根据具体分类来进行关系代数的映射; 而Cypher直接根据查询中每一部分的所属集合即可确定语义.
证明: 基本的Cypher语句中的MATCH子句的转化在规则10和规则11中完成, RETURN子句的转化在规则12中定义.规则10和规则11分别针对MATCH子句中的点模式和边模式进行约束转换: (1) 当遇到带标签的点模式
例7:
Cypher图模式匹配查询举例
A basic pattern matching query example for Cypher
语义对齐
Semantic alignment
在统一的存储模型之上提供两种查询语言接口, 可以在解决具体问题时为使用者提供更多选择, 进行两种查询语言的语义对齐, 实际上是对两种语言的扩展.
例8:对于
(1) SPARQL查询转化
运用第4.1节介绍的规则, 转化SPARQL查询语句的过程如下.
a) 对三元组
b) 对三元组
c) 对三元组
d) 对结果子句中的所有变量, 即
至此, 该条SPARQL语句成功转换为
(2) Cypher查询转化
运用第4.2节介绍的规则, 转化Cypher查询语句的过程如下.
a) 对点模式
b) 对Cypher语句中的边模式
c) 对RETURN子句中的所有变量, 即
根据本节介绍的SPARQL和Cypher查询语言相应的查询语句转化规则, 能够将两种查询语言转化为相同的使用关系代数表达的抽象语义树(查询语言的语义对齐方法的正确性分析在定理2和定理3中分别给出), 使得KGDB在兼容两种语法完全不同的查询语言的前提下统一了查询的语义.这为查询处理后面的优化过程提供了便利, 并为用户在同一个知识图谱上的查询提供了更多选择.
本节在合成数据集和真实数据集上验证统一存储方案的高效性和和查询语言的互操作性, 并且与RDF三元组库gStore[
本文使用的实验平台为单节点服务器, 节点配置主频为2.5GHz的Intel(R) Xeon(R) Platinum 8255C八核处理器, 其内存大小为32GB, 硬盘大小为100GB, 使用Linux 64-bit CentOS 7.6操作系统.
KGDB以开源属性图数据库AgensGraph为后端.使用的Neo4j版本为4.1.0社区版, 使用neosemantics插件4.0.0.1版本, 以在Neo4j中支持RDF图的存储, 使用的gStore版本为0.7.2.本文进行三个系统的存储效率的对比实验, 并在KGDB和gStore系统上进行SPARQL基本图模式查询对比实验, 在KGDB和Neo4j上进行Cypher查询对比实验.从存储空间、存储时间和查询效率上进行系统的全面评估.
本文使用的数据集包括LUBM[
数据集
Datasets
数据集 | 元组数 | 顶点个数 | 边个数 | 文件大小 |
LUBM10 | 1 316 700 | 207 429 | 630 757 | 208M |
LUBM20 | 2 782 126 | 437 558 | 1 332 030 | 441M |
LUBM30 | 4 109 002 | 645 957 | 1 967 309 | 651M |
LUBM40 | 5 495 742 | 864 225 | 2 630 657 | 871M |
LUBM50 | 6 890 640 | 1 082 821 | 3 298 814 | 1.1G |
DBpedia | 23 445 441 | 2 257 499 | 6 876 041 | 3.1G |
在LUBM数据集上执行的查询来自LUBM提供的14个标准查询中的8个(即Q1~Q6, Q11和Q14).其中,
● Q1~Q3和Q14为不涉及推理的SPARQL查询: (1) Q1输入数据量大, 选择度高; (2) Q2为涉及3个实体的三角查询; (3) Q3查询涉及的类型数据量大; (4) Q14输入数据量大, 选择度低;
● Q4~Q6和Q11为涉及到推理的查询.
gStore并不支持RDF图上的推理功能, 而Neo4j也仅仅可以需要通过插件的方式支持推理功能.同样的, KGDB也尚未支持推理查询, 故本文仅在gStore和KGDB上进行推理查询返回空结果的查询效率对比实验.LUBM数据集中涉及推理的查询可以简单分为4类: (1)Q4~Q9涉及到subClassOf层次类型; (2)Q5包含subPropertyOf层次关系, 查询中包含的内容需要借助本体信息才可直接执行; (3)Q6~Q10需要进行层次类型推理, 即查询中涉及的实体层次类型关系在本体信息中也未直接给出; (4)Q11~Q13需要进行更加复杂的关系推理, 即除了subClassOf和subPropertyOf关系之外的关系推理.本文在LUBM数据集上的实验部分在4类推理查询中各选择一个进行比较实验.因为缺乏DBpedia数据集上的查询模板, 本文设计了4个包含不同数据量的查询(记为Q_dbp1~Q_dbp4).Q_dbp2~Q_dbp4的基本结构相同, 不同的只是数据量的大小: Q_dbp4数据量最大, 达到数百万条; 而Q_dbp2最小.
本节在3个方面进行实验结果比较, 包括存储时间、存储空间和SPARQL或Cypher的查询效率.以下实验结果中, 每个查询测试均进行3次取平均值, 避免随机误差.
如
存储时间、存储空间实验结果
Results for data insertion and storage space
在存储处理过程中, KGDB仅需要一次无类型实体聚类过程, 即可多次进行数据集的存储, 在存储过程中, 不需要复杂的转换过程.对应的, gStore需要进行字符串与id的转换、VS树的建立等等过程, Neo4j需要进行类型到标签的转化等等过程.
如
在本文的实验中, 仅计算单个数据库在装载知识图谱前后的空间变化.如果将系统空间要求计算在内, Neo4j的知识图谱存储所需空间会更大.
查询效率实验分别在LUBM合成数据集和DBpedia真实数据集上进行.在LUBM数据集上, 采用了4个基本查询和4个涉及推理的查询.在DBpedia上, 设计了4个查询, 其中: Q_dbp1输入数据量大, 选择度高; Q_dbp2~ Q_dbp4具有相同的结构, 数据量依次增大.在同样的语义下, 分别构造SPARQL和Cypher查询语句, 并在对应系统上进行实验.
(1) SPARQL查询效率实验.
gStore是RDF图数据库, 使用SPARQL作为其查询语言, 可以支持大规模RDF知识图谱的数据管理任务.KGDB与gStore系统的SPARQL查询效率对比实验结果如
在LUBM数据集上的KGDB和gStore的SPARQL查询效率实验结果
Query efficiency experimental results on LUBM by SPARQL for KGDB and gStore
LUBM提供的标准查询Q2是选取的4个不涉及推理的查询中最为复杂的, 在gStore系统上将会引起系统错误, 不能够直接执行.为了公平比较, 没有进行查询的改写.对于查询Q1和Q3, 其基本结构是一致的, 区别在于涉及的实体的数据量不同, Q3的输入数据量更大.而相较而言, KGDB可以在Q3上呈现出平缓的查询时间增长趋势, 说明KGDB可以应对大规模知识图谱上的查询, 数据量的增长不会导致查询效率的降低.对于查询时间最长的Q14, 该查询涉及的实体数量巨大, 在LUBM50上, 查询结果将需返回数十万条数据.在这一查询上, KGDB和gStore的查询时间可以达到同一数量级.
如
在LUBM数据集上的KGDB和gStore的SPARQL推理查询效率实验结果
Inference query efficiency experimental results on LUBM by SPARQL for KGDB and gStore
如
在DBpedia数据集上的KGDB和gStore的SPARQL查询效率实验结果
Query efficiency experimental results on DBpedia by SPARQL for KGDB and gStore
(2) Cypher查询效率实验.
Neo4j是属性图数据库, 使用Cypher作为查询语言, 支持完整的ACID规则, 可以更加快速地处理连接数据.下面将进行KGDB和Neo4j系统的Cypher查询效率对比实验.
如
在LUBM数据集上的KGDB和Neo4j的SPARQL查询效率实验结果
Query efficiency experimental results on LUBM by SPARQL for KGDB and Neo4j
对于最复杂的三角查询Q2, KGDB的查询速度慢于Neo4j.这是因为Neo4j的存储方式使之查询结点之间的连接变得容易, 而不需要像KGDB这种关系数据库, 执行耗时的连接(JOIN)操作.但是, KGDB相较于Neo4j拥有更多优势: (1)KGDB不需要单独的插件, 原生的支持RDF图和属性图的统一存储, 并在存储过程中, 比Neo4j需要更短的存储时间和更小的存储空间, 同时管理多个知识图谱更加容易; (2)KGDB同时支持SPARQL和Cypher查询语言, 允许两个查询语言在同一知识图谱上的互操作.
在DBpedia数据集上的实验结果表明(如
在DBpedia数据集上的KGDB和Neo4j的Cypher查询效率实验结果
Query efficiency experimental results on DBpedia by Cypher for KGDB and Neo4j
从LUBM上的实验结果随数据量增长呈现的趋势上来看: KGDB在数据量不断增长后, 相较Neo4j的优势逐渐变小, 但查询时间仍然低于Neo4j.在最复杂的查询上(Q2)也可以得出相似的结论, 即: 随着需要遍历的数据量增大, Neo4j查询时间的增长幅度相较KGDB小, 但这种增长不会带来数量级的变化.而在DBpedia上的实验结果表明: 因为真实数据集所表现出的半结构化和稀疏性, 查询涉及数据量的增长将会为KGDB带来优势.
本文研发了统一模型和语言的知识图谱数据库管理系统KGDB.
(1) 统一存储: 支持存储RDF图和属性图数据, 使用字典编码, 提高存储效率, 节省存储空间, 使用基于特征集的聚类方法, 解决无类型实体的存储问题, 使得具有相近语义的实体存储在同一关系表中, 提高查询效率;
(2) 互操作语法层: 进行两种数据模型之上的查询语言SPARQL和Cypher的语义对齐, 即对同一知识图谱, 使用两种查询语言都可以得到相同的查询结果, 达到查询语言互操作的目的;
(3) 统一语义层: SPARQL和Cypher两种查询语言可以通过转换规则, 转化为关系代数表示的相同的抽象查询语义树.
真实数据集和合成数据集上的实验验证了KGDB系统的存储效率和查询效率, 实验结果表明: KGDB在真实数据集上普遍优于gStore和Neo4j;而在合成数据集上, KGDB可以与gStore和Neo4j达到相同数量级.
本文只讨论了单机系统上的知识图谱管理问题, 随着知识图谱数据规模的不断增大, 分布式知识图谱管理系统将成为研究热点.在后续工作中, 我们将会讨论分布式环境下知识图谱的统一存储方案和查询处理方法.
1) SPARQL查询
(1) Q1
{?
?
http://www.Department0.University0.edu/GraduateCourse0};]]>
(2) Q2
{?
?
?
?
?
?
(3) Q3
{?
?
http://www.Department0.University0.edu/AssistantProfessor0};]]>
(4) Q4
{?
X ub:worksFor 〈http://www.Department0.University0.edu〉.]]>
?
?
?
(5) Q5
{?
X ub:memberOf 〈http://www.Department0.University0.edu〉};]]>
(6) Q6
(7) Q11
{?
X ub:subOrganizationOf 〈http://www.University0.edu〉};]]>
(8) Q14
2) Cypher查询
(1) Q1
(
-[takesCourse]→
(
uri:‘http://www.Department0.University0.edu/GraduateCourse0’})]]>
(2) Q2
(
(
(
(3) Q3
(
-[publicationAuthor]→
(
uri:‘http://www.Department0.University0.edu/AssistantProfessor0’})]]>
(4) Q14
(
1) SPARQL查询
(1) Q_dbp1
a
〈
?
(2) Q_dbp2
(3) Q_dbp3
(4) Q_dbp4
2) Cypher查询
(1) Q_dbp1
a:AdministrativeRegion{
(2) Q_dbp2
(3) Q_dbp3
(4) Q_dbp4
本文由“支撑人工智能的数据管理与分析技术”专刊特约编辑陈雷教授、王宏志教授、童咏昕教授、高宏教授推荐.
Wang X, Zou L, Wang CK, Peng P, Feng ZY. Research on knowledge graph data management: A survey. Ruan Jian Xue Bao/Journal of Software, 2019, 30(7): 2139-2174(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5841.htm [doi: 10.13328/j.cnki.jos.005841]
王鑫, 邹磊, 王朝坤, 彭鹏, 冯志勇. 知识图谱数据管理研究综述. 软件学报, 2019, 30(7): 2139-2174. http://www.jos.org.cn/1000-9825/5841.htm [doi: 10.13328/j.cnki.jos.005841]
Zou L, Özsu MT, Chen L. gStore: A graph-based SPARQL query engine. The VLDB Journal, 2014, 23(4): 565-590.
https://neo4j.com/docs/developer-manual/current/]]>
https://dgraph.io/]]>
https://hugegraph.github.io/hugegraph-doc/]]>
Abadi DJ, Marcus A, Madden SR. Scalable semantic Web data management using vertical partitioning. In: Klas W, ed. Proc. of the 33rd Int'l Conf. on Very Large Data Bases. Vienna: VLDB Endowment, 2007. 411-422.
Bornea MA, Dolby J, Kementsietsidis A. Building an efficient RDF store over a relational database. In: Ross K, ed. Proc. of the 2013 ACM SIGMOD Int'l Conf. on Management of Data. New York: ACM, 2013. 121-132.
Moerkotte G, Neumann T. Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins. IEEE Trans. on Data Engineering, 2011, 984-994.
Anagnostopoulos I, Mamoulis N,
Anyanwu K, Kim H,
http://janusgraph.org/]]>
https://www.tigergraph.com/]]>
Zou L, Peng P. A survey of distributed RDF data management. Journal of Computer Research and Development, 2017, 54(6): 1213-1224(in Chinese with English abstract).
邹磊, 彭鹏. 分布式RDF数据管理综述. 计算机研究与发展, 2017, 54(6): 1213-1224.
Wang TT, Rong CT, Lu W. Survey on technologies of distributed graph processing systems (in Chinese with English abstract). Ruan Jian Xue Bao/Journal of Software, 2018, 29(3): 569-586. http://www.jos.org.cn/1000-9825/5450.htm [doi: 10.13328/j.cnki.jos.005450]
王童童, 荣垂田, 卢卫. 分布式图处理系统技术综述. 软件学报, 2018, 29(3): 569-586. http://www.jos.org.cn/1000-9825/5450.htm [doi: 10.13328/j.cnki.jos.005450]
Harris S, Gibbins N. 3store: Efficient bulk RDF storage. In: Volz R, ed. Proc. of the 1st Int'l Workshop on Practical and Scalable Semantic Systems. Sanibel Island: CEUR-WS. org, 2004. 81-95.
Pan Z, Heflin J. DLDB: Extending relational databases to support semantic Web queries. In: Volz R, ed. Proc. of the 1st Int'l Workshop on Practical and Scalable Semantic Systems. Sanibel Island: CEUR-WS. org, 2004. 109-113.
Wilkinson K. Jena property table implementation. In: Smart PR, ed. Proc. of the 2nd Int'l Workshop on Scalable Semantic Web Knowledge Base Systems. Athens, 2006. 35-46.
Abadi DJ, Marcus A, Madden SR. SW-Store: A vertically partitioned DBMS for semantic Web data management. VLDB Journal, 2009, 18(2): 385-406.
Yuan P, Liu P, Wu B,
Neumann T, Weikum G. RDF-3X: A RISC-style engine for RDF. Proc. of the VLDB Endowment, 2008, 1(1): 647-659.
Weiss C, Karras P, Bernstein A. Hexastore: Sextuple indexing for semantic Web data management. Proc. of the VLDBEndowment, 2008, 1(1): 1008-1019.
Kim H, Ravindra P,
Sun W, Fokoue A, Srinivas K. SQLgraph: An efficient relational-based property graph store. In: Sellis T, ed. Proc. of the 2015 ACM SIGMOD Int'l Conf. on Management of Data. New York: ACM, 2015. 1887-1901.
https://bitnine.net/documentations/manual/agens_graph_developer_manual_en.html]]>
Chodorow K. MongoDB: The Definitive Guide: Powerful and Scalable Data Storage. O'Reilly Media, Inc. , 2013.
https://www.blazegraph.com/]]>
https://virtuoso.openlinksw.com/]]>
http://rdf4j.org/]]>
Neumann T, Weikum G. RDF-3X: A RISC-style engine for RDF. Proc. of the VLDB Endowment, 2008, 1(1): 647-659.
https://franz.com/agraph/allegrograph/]]>
http://graphdb.ontotext.com/]]>
https://tinkerpop.apache.org/docs/3.4.8/reference/]]>
http://orientdb.org/]]>
https://github.com/opencypher/cypher-for-apache-spark]]>
Gutierrez C, Hurtado CA, Mendelzon AO. Foundations of semantic Web databases. Journal of Computer and System Sciences, 2011, 77(3): 520-541.
Francis N, Green A, Guagliardo P. Cypher: An evolving query language for property graphs. In: Das G, ed. Proc. of the 2018 Int'l Conf. on Management of Data. New York: ACM, 2018. 1433-1445.
Guo Y, Pan Z, Heflin J. LUBM: A benchmark for OWL knowledge base systems. Web Semantics: Science, Services and Agentson the World Wide Web, 2005, 3(2-3): 158-182.
http://wiki.dbpedia.org/About]]>