这篇笔记来自于北大邹磊教授的知识图谱讲座
知识图谱的数据模型与查询语言（Data Models and Query Languages of Knowledge Graph）
视频地址：https://www.bilibili.com/video/BV1kv411i7A8
主要内容：
- RDF图数据模型与SPARQL查询语言？
- 属性图数据模型与Cypher查询语言
- TinkerPop图计算框架与Gremlin图遍历语言及遍历机
1. RDF图数据模型与SPARQL查询语言
资源描述框架（RDF）数据
- RDF是知识图谱数据的事实标准
- RDF是由W3C组织提出的一种描述资源概念模型的语言
- RDF是语义网的一个基石
语义网的目标是网络上的资源，是“机器可理解”（Machine understandable）
image.png
RDF发展简史
RDF发展简史
常见RDF图数据库系统
常见RDF图数据库系统
RDF数据示例
- RDF中任何实体都被称之为资源（Resource），用一个统一的国际化标识符（IRI，Internationalized Resource Identifier）来唯一标识；
- 资源的属性可以被定义
- 资源间关系可以被定义
RDF资源
- 现实世界中每个概念、实体和事件都可以对应一个资源，可以表示具体的事务，也可以是抽象的概念，以及属性
- 每个资源都用IRI（Internationalized Resource Identifier，国际化资源标识符）进行标识
- RDF允许引入不包含任何IRI标识的资源，被称为空白结点或者匿名资源，用于标识一种存在变量。空白结点不能用IRI来全局处理，所以为了区分不同的空白结点，RDF解析器一般会为每个空白结点分配一个系统生成的内部名。
国际化资源标识符IRI（Internationalized Resource Identifer）
IRI是一个用来标识资源的字符串，是数据集中资源的一个唯一的身份ID；当原始的IRI长度过长时，为了方便表达可以引入前缀（prefix）命名空间等方式来简化，以下是常见的前缀：
image.png
RDF三元组
每个资源的一个属性及属性值，或者它与其他资源的一条关系，都被表示成<主体，谓词，客体>的三元组形式，一个三元组又称为陈述
- 所谓主体，它是一个资源或者是一个空白节点；
- 所谓属性/谓词，是用来描述资源之间的语义关系，或者描述某个资源和属性值之间的关系；
- 所谓客体，它可以是一个资源，也可以是一个字面值，也可以是一个空白节点
RDF数据集（用集合方式来表示）
RDF数据集
RDF图（用图的方式来表示）
- 三元组的主体和客体就是RDF图中的一系列节点
- 一个谓词的资源标识符在同一张图里可能充当节点，也可能充当边
RDF字面值
在RDF的定义中，字面值只会出现在RDF三元组的客体中。有两种表达方式：
- 朴素文本（plain literals），也就是普通意义上的字符串
- 类别化文本（typed literals），可以指定某个字面值的数据类型，参考XML语法中数据类型定义的，包括xsd:integer, xsd:decimal等
RDF 空白节点
空白节点（Blank Node）是指没有统一资源标识符（IRI）同时在知识图谱数据集外部不需要直接访问的节点
空白节点的引入可以更加方便地表达多元关系和结构化的数据值
RDF Schema
RDF Schema（简称RDFS），用来表达实体与类别，以及类别之间、以及属性与属性之间、属性的定义域、值域之间的关系
RDF预定义了一些核心概念和核心属性，这些概念并不提供某个具体领域专用的类别和属性，但是RDFS为定义某个领域的本体概念提供了基础。
- 核心类
+ rdfs:Class：所有类的类
+ rdfs:Resource：所有资源的类
+ rdfs:Literal：所有字面值的类
+ rdfs:Property：所有属性的类
- 核心属性
+ rdf:type：连接一个资源和它属于的类别
+ rdfs:subClassOf：连接一个类别和它的父类
+ rdfs:subPropertyOf：连接一个属性和它的子属性
+ rdfs:domain：定义一个属性的作用域（它的主语的类别）
RDF Schema核心类和核心属性举例
RDF Schema核心类和核心属性举例
SPARQL查询语言
SPARQL查询语言简介
- SPARQL是W3C制定的RDF图数据的标准查询语言
- SPARQL从语法上借鉴了SQL，同样属于声明式查询语言
- SPARQL提供了强大的基于图匹配的查询功能，也包括可选匹配（OPTIONAL）、对结果的排序（ORDER BY）、去重（DISTINCT）和限定（LIMIT）及值约束条件（FILTER）等多种操作符，以及直接回答YES/NO的ASK查询等其他形式的查询。同时，SPARQL语句也具备增、删、改的功能
- 具体语法细节见SPARQL官网：https://www.w3.org/TR/rdf-sparql-query
SPARQL语法
- 命名空间：prefix foaf: http://xmlns.com/foaf/0.1/
- 数据集：FROM NAMED http://example.org/foaf/bobFoaf
- 查询方式：SELECT ?name ?bd
- 图模式：WHERE { ?p name ?name . ?p birthDate ?bd }
- 结果修饰：ORDER BY ?X
SPARQL命名空间
- PREFIX关键字是把前缀标签和IRI连接起来，一个有前缀的名称是由一个带前缀的标签和一个本地的名称所组成中，其中由冒号“:”来分开
- 常用的命名空间前缀与IRI的关系之前已经显示了
SPARQL数据集
- 一个SPARQL查询可以在包含一个或者多个RDF数据图的RDF数据集上执行
- 指定使用默认图用关键字FROM，而指定使用某个命名图用关键字FROM NAMED
SPARQL的六种查询方式
- 选择查询（SELECT查询），用来从RDF数据中选择出满足条件的值来构造一张关系表并返回
- 构造查询（CONSTRUCT查询），用来从RDF数据中选择出满足条件的值并用这些值按条件构造一个新的RDF数据
- 询问查询（ASK查询），用来从RDF数据中判定出RDF数据中是否有满足条件的值并返回True/False
- 描述查询（DESCRIBE查询），用来从RDF数据中选择出一个RDF数据图来描述某些特点的资源
- 插入语句（INSERT语句），向RDF数据中插入一个或者多个三元组
- 删除语句（DELETE语句），从RDF数据中删除一个或者多个三元组
SPARQL图模式
- 主要介绍选择（SELECT）语句，其中WHERE子句中表示查询语句的正文部分称为图模式
SELECT ?x ?name ?birth ?friend WHERE {
?x dbp:workplaces dbr:University_of_Glasgow.
{?x dbo:name ?name}
UNION
{?x rdfs:label ?name}
?x dbo:birthDate ?birth
FILTER(?birth = "1736-01-19"^^xsd:date )
OPTIONAL {
{?x dbo:influencedBy ?friend }
UNION
{?friend dbo:influencedBy ?x}
}
}
SPARQL三元组模式与基本图模式
- 一个三元组模式（Triple Pattern） t 定义为 t
%20%5Ctimes%20(V%20%5Cbigcup%20J)%20%5Ctimes%20(V%20%5Cbigcup%20J%20%5Cbigcup%20B%20%5Cbigcup%20L))
e.g. ?x workplace dbr:University_of_Glasgow
- 一个基本图模式（Basic Graph Pattern, BGP）的定义如下：一条三元组模式t是一个基本图模式；
e.g. ?x workplace dbr:University_of_Glasgow
?x dbo:name ?name
SPARQL图模式
一个图模式（Graph Pattern）是由下面递归定义的：
- 如果P是一个基本图模式，则P也是一个图模式；
；
，则{
} UNION {
}, {
}表示一个组图模式；
- 如果P是一个图模式，C是SPARQL中的FILTER过滤条件，则（P FILTER C）也是一个图模式
SPARQL组图模式、联合图模式
- 一个组图模式（Group Graph Pattern）如下递归定义：
- 如果P是一个图模式，则{P}是一个组图模式
- 如果P是一个组图模式，则P也是一个图模式
- 一个联合图模式（Union Graph Pattern）如下递归定义：
- 如果{
- 如果（
SPARQL操作符优先级
- 优先级从大到小分别是：(group)、UNION、AND、OPTIONAL、FILTER
- OPTIONAL操作符是左结合（left-associative）的
SPARQL图模式二叉数
SPARQL图模式二叉数.png
SELECT ?x ?name ?birth ?friend WHERE {
?x dbp:workplaces dbr:University_of_Glasgow.
{?x dbo:name ?name}
UNION
{?x rdfs:label ?name}
?x dbo:birthDate ?birth
OPTIONAL {
{?x dbo:influencedBy ?friend}
UNION
{?friend dbo:influencedBy ?x}
}
FILTER(?birth = "1736-01-19"^^xsd:date)
}
SPARQL结果修饰
- 排序（ORDER BY），用来对结果进行排序；
SELECT ?x ?label WHERE { ?x rdfs:label ?label } ORDER BY ?label
- 映射（PROJECTION），用来从结果中取若干变量组成新的结果；
SELECT ?label WHERE { ?x rdfs:label ?label }
- 去重（DISTINCT），用来只返回不同的结果；
SELECT DISTINCT ?label WHERE { ?x rdfs:label ?label }
- 偏移（OFFSET），用来使结果在指定的数量后开始；
SELECT ?label WHERE { ?x rdfs:label ?label } OFFSET 2
- 限定结果数量（LIMIT），用来对结果数量设置了上限；
SELECT ?label WHERE { ?x rdfs:label ?label } LIMIT 3
SPARQL语义--背景知识
关系模型回顾
- E.F. Codd于1969年提出关系数据理论，他因此获得1981年的ACM图灵关系理论是建立在集合代数理论基础上的，有着坚实的数学基础
- 早期代表系统
- System R：由IBM研制
- INGRES：由加州Berkeley分校研制
- 目前主流的商业关系型数据库系统
- Oracle，Informix，Sybase，SQL Server，DB2
- Access，Foxpro，Foxbase
关系基本概念
- 域（Domain）
- 一组值的集合，这组值具有相同的数据类型，如整数的集合、字符串的集合、全体学生的集合
- 笛卡尔积（Cartesian Product）
- 一组域
的笛卡尔积为：
={(
) |
}笛卡尔积的每个元素（
）称作一个n元组（n-truple）; 元组得每一个值
叫做一个分量（component）；若
的基数为
，则笛卡尔积的基数为
- 关系
- 笛卡尔积
上的关系，用R（
- 关系是笛卡尔积中有意义的子集，关系也可以表示为二维表
关系
关系代数运算概览
- 基本运算
- 一元运算
- 选择、投影、更名
- 多元运算
- 笛卡尔积、并、集合差
- 其他运算
连接、自然连接、外连接
关系运算——选择运算
- 在关系R中选择满足给定条件的元组（从行的角度）
={t | t
R, F(t) = true}
- F是选择的条件，
, F(t)要么为真，要么为假
- F的形式：由逻辑运算符连接算术表达式而成
- 逻辑表达式：
- 算术表达式：
，其中X，Y是属性名、常量、或者简单函数，
{
}
image.png
关系运算
关系运算——投影运算
关系运算——投影运算
关系运算——更名运算（相当于复制）
- 重命名关系的属性或关系自身
- 其所得到结果是和R一样的关系，只是在这个新关系被赋一个新的关系名字X；新关系的每列被重定义为
关系运算——并集运算
- 所有至少出现在两个关系中之一的元组集合
={
}
- 关系R和S进行并运算的前提是他们必须是相容的：
- 关系R和S必须是同元的，即它们的属性数目必须相同
- 对于Vi, R 的第i个属性的域必须和S的第i个属性的域相同
关系运算——并集运算
关系运算——差集运算
- 所有出现在一个关系而不在另一关系中的元组集合
- R - S = {
}
- 关系R和S进行并运算的前提是他们必须是相容的
关系运算——笛卡尔积运算
- 两个关系R, S, 其度分别为n, m, 则他们的笛卡尔积是所有这样的元组集合：元组的前n个分量是R中的一个元组，后m个分量是S中的一个元组
= {
}
image.png
关系运算——自然连接
- 在关系R和S中的在它们的公共属性B上相等的所有元组的组合，并去掉重复属性
={
}
关系运算——自然连接
关系运算
关系运算——外连接
- 为避免自然连接时因失配而发生的信息丢失，可以假定往参与连接的一方表中附加一个取值全为空值的行，它和参与连接的另一方表中的任何一个未匹配上的元组都能匹配，称之为外连接
- 外连接 = 自然连接 + 未匹配元组（悬挂元组）
- 外连接的形式：左外连接、右外连接、全外连接
- 左外连接 = 自然连接 + 左侧表中未匹配元组
- 右外连接 = 自然连接 + 右侧表中未匹配元组
- 全外连接 = 自然连接 + 两侧表中未匹配元组
SPARQL 语义
图模式的匹配
- 图模式P在RDF数据集D上的匹配集（表示未[P]
）会产生一系列匹配{
}
- 一个匹配
的一个部分映射函数，这里
表示查询中的变量，J、B、L分别表示资源标识符集合、空白节点集合和字面值
- 注意到SPARQL的查询语义是基于“包（Bag）”的，所以这些匹配当中是有可能有重复的
匹配的相互兼容
- 两个匹配
称为是相互兼容（compatible）的（表示为
~
）当且仅当如下成立：对所有变量
，它们的匹配值
是相等的，这里dom(
)表示在匹配
产生一个新的匹配；如果两个匹配
匹配集合的关系操作
{
}
= {
}
{
}
\
= {
}
图模式在RDF数据集上的执行结果
图模式P在RDF数据集D上的执行结果（表示为
）递归定义如下：
- 如果P是一个三元组模式t，
}，其中var(t)表示所有t中间的变量，
表示t中的变量用匹配
- 如果
；
- 如果
；
- 如果
，其中
；
- 如果P = (
}（如果条件C中的所有变量可以被匹配
），则
）
图模式的执行
一个图模式P 可以表示为二叉树的形式，所以执行图模式P查询结果的方法，最为直接的就是基于这颗二叉树采用自底到上的方式来执行。在执行的每一步，利用操作符AND、UNION、OPTIONAL 和FILTER对其左右儿子的输入
图模式的执行
SPARQL 1.1的新特性
- 2013年，SPARQL 1.1 被提出，其中引入了一些新特性，包括且不限于：
- 属性路径（Property Path）
- 联邦查询（Federated Query）
SPARQL 1.1 的属性路径
- 所谓属性路径（Property Path），就是找出RDF数据上两点间满足属性限制条件的路径。这个属性限制条件允许用属性组成的正则表达式来表达
SELECT ?x WHERE {dbr:James_Watt dbo:influenceBy* ?x}
SPARQL 1.1的联邦查询
- 所谓联邦查询（Federated Query），就是允许查询调用远程的其它SPARQL查询接口来与当前的结果进行组合
SELECT ?name WHERE {
dbr:James_Watt dbo:influenceBy ?person.
SERVICE https://dbpedia.org/sparql {
?person dbo:name ?name .}
}
