【AIDL专栏】基于图的RDF知识图谱数据管理

RDF and Semantic Web

知识图谱（Knowledge Graph）在2012年由Google推出，目前采用的数据标准是RDF（Resource Description Framework，资源描述框架）。RDF最早在Semantic Web中提出，因此在讲RDF之前，首先回顾一下Semantic Web。

Tim Berners-Lee在提出传统Web时，也提出了Semantic Web。传统Web通过超链接将文档连接起来，便于文档的共享和浏览，而Semantic Web关注的是数据，不是文档。本质区别在于，文档（如邮件、日记、博客等）是非结构化数据，人可以理解，但机器难以理解。Semantic Web则希望用结构化方法，在数据关联时，关联数据不是传统的html文档，而是满足一定标准的结构化数据。通常认为结构化数据的意思是，同时给出数据及其描述，典型的例子是关系表，关系表中每个单元格的数据一定在某列上，这个列名就是数据描述。Semantic Web希望采用结构化数据使所有网络上的信息都是机器可理解的。

看一个简单的例子，上图是传统的html，内容是讲论文作者的头衔和相关信息，但机器难以理解。稍加改动，加入一些semantic tag（语义标签）。

Semantic tag的标准很多，工业界支持的包括RDFa、Microformat（微格式）等。加入semantic tag的作用在于，将以上两个html放到浏览器中，在人看来没有任何区别，但Google的结构化数据测试工具可以从第二个html中试图抽取按照semantic tag标注的数据。

这样的好处是可以从大量文档中通过semantic tag抽取结构化数据，比NLP等技术简单很多，但比较耗人工，需要用户在写html时就将结构化信息标注出来。下面来探讨这样做对用户有何帮助。

Google、百度等进行信息检索后，会生成一个摘要，供用户判断结果是否是需要的。如果网页中有semantic tag标注的结构化数据，搜索引擎会根据这些结构化数据产生文档摘要，而不是采用从多个句子中抽出一些重要句子组成摘要的传统方法。上图是Google提供的例子，摘要中有几项是按传统方法产生的，但这个人的工作单位、职位、住址等重要信息是根据网页中的结构化数据产生的。可以想象，如果一个淘宝卖家将产品的好评度、价格、出货量等最重要的数据用semantic tag进行结构化，至少在Google搜索引擎里产生的摘要更加精确地表示了网页内容，便于用户点击。沃尔玛的英文在线商品网站以及亚马逊都采用了这种方式，但中文方面目前还没有。

再来看Facebook。Facebook有大量的活跃用户，这些用户会发布一些照片或个人信息。Facebook基于此构建了Social Graph，用户、用户的照片、毕业学校、居住城市等都是这个图中的结点。2013年Facebook发布了Graph Search功能，帮助用户通过更加自然的方式去访问Social Graph。例如，当用户查询“My friends who live in Canada”，“My friends”是Social Graph上的一些结点，“live in Canada”的用户也是一些点，将这两部分取交集就能得到需要的ID。这是将自然语言转化为结构化查询，在Social Graph中去查。

再进一步，如果查询“Photos of my friends who live in Canada”，返回的就不是用户ID，而是他们上传到Facebook的照片，很显然用到了用户到照片的关联。在结构化查询的部分又加了一层，即这些人的照片。这就是用结构化方式来表达语义。

Semantic We或知识图谱的研究主要是两个方面。一个是表达能力（Expressiveness），语义网中有很多标准，从最开始的RDF、RDFS到OWL等，表达能力越来越强；另一方面是可扩展性（Scalability），系统不能只在很小的数据量运行，也要能支持大数据。很多知识图谱应用都是在这两个方面进行折衷，包括Apple Siri、Google Knowledge Graph和IBM Waston系统，下面举几例有趣的应用。

2011年，IBM Watson在问答类节目《危险边缘》上击败了两位人类年度总冠军。

EVI公司发布了一个自然语言问答系统，输入查询问题会直接给出答案而不是网页。例如当查询“Where is the capital of U.S.”，会直接回答“Washington, D.C.”。该公司2012年被亚马逊收购。

这是Google在2012年发布知识图谱的页面，查询Obama，除了得到网页访问，还有他的名字、毕业院校、亲人等信息，这背后就是一个图谱。

学术界也有构建知识图谱工作，典型的是Yago和DBPedia，这两个都是开源且open domain的知识图谱。

上文提到的可扩展性，主要是有两点。第一，数据量要足够大，Semantic Web研究仅在小数据下做应用是不够的。Freebase被Google收购时，其知识图谱数据量大概是25亿，成为整个Google Knowledge Graph的核心。Yago和DBPedia也有接近10亿的规模。第二是系统如何对这样大的数据进行管理。

Semantic Web在刚提出时非常不成功，核心问题是“没米下锅”。因此W3C在09年开始推动Linked Open Data项目，每个人像构建自己的网站一样构建自己知识图谱的数据集，数据集之间通过类似“超链接”的概念关联起来，只不过这里是链接结构化数据。通过网络的作用，Linked Open Data cloud自然膨胀起来。如图是2014年ISWC会议统计的数据集。

通过一个爬虫爬到了1091个数据集，triples数目超过250亿甚至接近上千亿

在很多行业，数据收集是知识图谱构建的重要问题。现在做医疗知识图谱的创业公司、国家项目、研究人员有很多，因为医疗生物领域最先定义了本体的标准，比如关于心脏病本体的定义就非常详细。实际上Semantic Web就是定义了一些标准，如果这些标准被行业接受，就可以用来构建数据。金融领域做知识图谱也比较火，因为金融数据定义的标准也非常明确，比如一个上市公司哪些信息是必须开放的，是有明确格式的。

接下来看数据的管理问题。像Freebase这样具有25亿数据量的庞大图谱，不能仅存放在云平台上，还需要进行查询、推理等其他应用，这背后就是数据管理的问题。

RDF Introduction

首先简单介绍RDF的数据格式。数据库中表达语义最核心是两个方面，实体和实体关系，它们是物理世界的信息映射到信息世界的关键。例如下图中Abraham-Lincoln是实体，本身带有一定的属性。Abraham-LincoIn和Washington-DC之间的关系就是实体关系。

数据库中另一个重要概念是E-R图（Entity Relationship Diagram，实体-关系图）。这是一个概念模型，主要作用是沟通应用的需求方与数据库设计者之间的桥梁。关系数据库的一个核心问题就是如何将E-R图概念根据具体的用户需求映射到一个关系表当中。

RDF描述实体和实体关系，同时又是一种实现标准。因为在RDF中，所有的实体和实体属性都可以用SPO数据模型表示，也就是主谓宾的表示。比如实体Abraham-Lincoln有三个属性，就表示为三个谓词，每个谓词的值写在后面。

有时候实体之间的关系，比如braham-LincoIn和Washington-DC之间的关系，也可以用这样的三元组表示。

也就是说，RDF用统一的模型表示了所有实体、属性和实体关系，不像关系数据库中一对一、一对多、多对多的关系要分别考虑如何映射到表中。这些概念在RDF中统统简化，使得RDF从建模方面更加简单。RDF是天然的图数据，所有实体可以看作点，实体间的关系可以看作边。

RDF Graph

数据库研究的特点是需要建模。建模分两方面，一方面对数据本身建模，比如RDF；另一方面是查询。数据库中的查询是结构化的，需要用如SQL这样机器理解的查询，而不是自然语言查询。SPARQL是面向RDF的结构化查询语法规则，由很多三元组构成（具体语法可参考PPT）。

上图就是一个SPARQL查询，里面有一些“?”符号，代表变量，即需要找的数据。这个语句是要查询一个人，出生地是1718年建立的一个城市，出生时间是1976年。这种查询也可以表达成查询图（Query Graph）。

Centralized System

问题是已有三元组数据集，如何回答SPARQL查询语句，特别是当三元组有上亿甚至数十亿时如何处理。现实应用中就是这样，特别是生物领域的数据，经常达到十亿或百亿。可能想象的方案是用关系数据库来表达，因为已有的三元组本身就能存到关系数据库的表中，然后将SPARQL转换到SQL，运用目前的关系数据库系统如Oracle、MySQL等来回答这样的查询。

但对于任何关系数据库系统，用一张表存下这样大量的数据都很有挑战，并且还要做查询。进行上文所述的查询需要的SQL语句如下

这样的语句含有很多join，而关系数据库中join的查询是最慢的，非常耗时。但工业界不会放弃产品链成熟的关系数据库市场，因此IBM和Oracle等公司将RDF作为产品的组件，依旧用关系数据库做底层，但不采用一张大表这种简单形式，而是用多张表的形式存，使转换到SQL更简单。

如何设计关系表结构来使存储和查询效率更高? 有三种做法：第一个做法是属性表（Property Tables），将实体按照不同的种类进行聚类，每一类用一张关系表存，表的每一列表示一个属性，同一类实体的属性是类似的。这样就将整个RDF数据分成不同的表。

采用这种方法查询一个出生时间为1976年、出生地为1718年建立的城市的人，可以翻译成如下的SQL语句：

这里只有一个join语句，且join的两张表Person和City比原来的大表小很多，查询更高效。这说明设计不同的属性表结构会减少join的次数，尤其适合结构化的数据（这里的结构化指RDF每一类内的实体属性项类似）。缺点也很明显，比如Subject是一本书，有属性“作者”，通常一本书有N个作者，为满足第一范式就需要存N行，这又会导致其它属性项被重复，产生大量数据冗余，不满足第二范式，使数据库性能非常弱。还可能存在大量的NULL，因为RDF中同一类实体的属性项不一定一致，比如活人的diedOnDate属性值为NULL。

另外一个做法是Binary Tables，思路更为简单。将三元组根据不同的属性定义不同的表结构，一个谓词一张表，每个表结构就主、宾两列，并按照Subject排序。

好处是支持多值的属性，没有NULL，无需聚类，最主要的是对Subject列归并排序可以加速Subject-Subject joins（如T1.Subject=T2.Subject）。

第三种做法是Exhaustive Indexing，个人理解从某种角度上是对第二种做法的补充。显然加速Object-Subject joins以及Object-Object joins需要另外的排序。对于SPO三列，总共的组合只有6个：SPO、SOP、PSO、POS、OPS、OSP。Exhaustive Indexing是将一个表存六份，每一份按不同的组合排序。再看之前对一个人出生地的查询。

属性bornIn是常量放在前面，后面两个是查询项。采用这种PSO排序，当常量给定时满足查询的数据一定有范围（如图中红色部分所示），可转换为B+树上的范围查询，非常高效。之后可再按S或O进行排序，通过merge join加速查询。

Exhaustive Indexing可以加速所有可能的join操作，缺点是占用空间大。虽然有一些压缩备份表的策略，但总体还是比原表大。

以上三类方案核心仍是以关系数据库做支撑，将面向RDF的SPARQL查询转换成面向关系数据库的SQL查询，或求助于类似技术用关系数据库方案解决，只是在表的分割和索引构建方面有所差别。下面简单介绍我们自己的工作。

gStore: a graph-based SPARQL query engine

RDF是一个图，SPQRQL也是图，回答SPQRQL就是找到查询图（Query Graph）在数据图（Data Graph）上的匹配。

回答SPQROL就是找到绿色查询图在数据图中的红色匹配部分

我们构建一个基于图的系统gStore，其核心思想就是通过找到查询图的匹配（如图中红色部分）来完成对查询的回答。这个系统不依赖于关系数据库系统，而是通过邻接表（Adjacency List）直接存图数据本身。更多的技术细节可参考报告PPT。

我们开源了gStore系统，提供C++、Java、Python等接口，实际应用中可直接当作数据库使用。使用文档可参考https://github.com/Caesar11/gStore。

gStore系统结构

gAnswer: Natural Language Question Answering Over Knowledge Graph

gStore系统只能接收结构化查询，但知识图谱更多是面向使用自然语言查询的普通用户，所以需要一个更易于使用的用户界面来连接知识图谱。

我们做的一个工作是自然语言关键词问题。将自然语言转换成SPARQL或类似的子图查询，利用gStore系统回答自然语言查询。如上图，将自然语言转换成语义查询图（Semantic Query Graph），如果能找到匹配，就能得到答案。

Conclusions

图数据库是RDF知识库管理的一个可能方案。采用图数据库，尤其是子图匹配工具，解决了SPARQL查询的问题，从目前角度来说也解决了一部分自然语言问答的问题。

最后是一个开放性问题，知识图谱到底在什么产业上对普通用户有什么样的应用，这是大家可以考虑的。

Q&A

问1：gStore目前实现程度怎样？性能也想了解一下。

邹老师：gStore目前单机能处理10亿的RDF三元组，可以接收最新SPARQL1.1标准，覆盖85%以上的标准，增、删、改、union等操作都可以支持。现在也有一些企业应用项目，但数据集很小，三元组不到100万，对我们没有什么挑战。Github上有我们在Benchmark上的测试报告，大家可以参考。

问2：您是怎么做到将自然语言映射到数据库上进行查询？

邹老师：首先根据语法结构得到一个依赖树。之后系统需要两个输入，一个是实体字典，用于实体识别，另一个是关系短语字典，用于关系识别。假如有关系短语“(be) married to”和“play in”，要在依赖树中找到这两个关系。

找到关系后，根据语法结构找到两端的参数，作为两个点，每个关系表现成一条边。

将这两个结构拼起来就可以构成一个语义查询图。这种方式是以边为核心的（Edge First），我们正在研究以点为驱动（Node First）构建语义查询图，目标是一样的。