关系数据库的实体间关系提取方法的研究

王嘉庆 杨卫东 何亦征

1(复旦大学计算机科学与技术学院 上海 201203)2(中国航空无线电电子研究所 上海 200233)

0 引 言

关系数据库作为一种物理模型，出于自身模式、软件限制、数据库设计考虑等多方面因素，普遍存在缺乏语义的问题。数据库中存储着大量数据，人工添加语义关系耗时耗力[1]。因此提出了各种从关系数据库中自动提取语义信息，构建知识图谱中RDF三元组的方法。

目前，众多相关学者和机构已经关注于这一领域[2-3]，W3C提出了直接映射法，定义了将关系数据库映射为RDF图的简单映射规则，可将数据资源转换为机读格式。文献[4]中的方法注重于映射的自动发现，使用基于上下文的方法，利用已有的本体网络，构建起数据库到本体的映射关系。D2R Map[5]，以及在其基础上进一步改进的DB2OWL[6]均利用了外部的SQL查询语句，利用SQL中涉及的表格和属性构建RDF。R2RML[7]、D2RQ[8]则在SQL语句之外加入了特殊映射语言，允许在构建的映射规则上进行人工修改和补充。Triplify[9]与数据库发布后的网页应用交互，将关系数据库转为连接数据发布。

上述基于规则的转换方法主要考虑数据库结构信息的转换，较少研究数据库实体间关系的发现，导致其转换结果未能完全展现数据库中蕴含的语义信息，最终生成的RDF中存在冗余实体，也缺失了部分实体间关系。基于规则的转换方法对图1中关系数据库表的转换结果如图2所示。表示Movie表与Actor表间多对多关系的MovieActor属性被转换为MovieActor实体，造成了冗余，表示Director表与Movie表之间一对多关系的DirectorID属性被转换为Movie实体的属性，缺失了对该关系的表达。

图1 关系数据库表示例

图2 基于规则的转换方法构造的实体关系图

针对上述问题，本文提出了一种新的关系数据库到RDF的构造方法，使用基于随机森林算法发现和提取的实体间语义关系提升RDF结果的质量。该方法构建融合了数据库模式和数据内容的特征向量，设计并实现了基于随机森林的实体间语义关系发现算法，发现实体间潜在的语义关系，并基于发现的语义关系，提出了关系数据库的一般转换规则与多对多、一对多等实体语义关系的特殊转换规则，完善了RDF中对关系的表达，减少了RDF中的冗余。

该方法对图1中数据库转换结果如图3所示。虚线代表发现的实体间语义关系。图1中表示多对多关系的MovieActor表被转换为Movie实体与Actor实体间的Movie-has-Actor关系，Movie中表示一对多关系的DirectorID属性被转换为Movie实体与Director实体间的Director-of-Movie的一对多关系。与图2对比可以看出，图3中发现的实体间多对多、一对多等语义关系有效地连接了各个实体，减少了最终结果的冗余。

图3 实体间关系提取方法构造的实体关系图

1 整体流程

本文提出的实体间关系发现与转换方法的基本流程如图4所示。

图4 实体间关系发现转换方法的流程图

整个构建过程可被分为实体间语义关系发现和实体间语义关系转换两部分。

在语义关系发现部分，主要发现了数据库中可以表示为实体的表，以及实体间的潜在语义关系。首先，从关系数据库中抽取关系模式和内容数据，利用模式特征构建和内容特征构建，组成数据库关系特征向量。然后，利用数据库内已有的关系，使用随机森林算法对特征向量进行训练获得模型。最后，使用模型对潜在语义关系进行判断，其判断结果被存储为Table-Graph。Table-Graph是本文定义的用于描述数据库语义关系的图。关系数据库模型主要由一系列关系模式及关系模式间的引用关系组成，若将关系模式作为节点，将关系模式之间的引用关系作为图中的有向线段，这样的图即可用于对关系数据库模型的描述。

在语义关系转换部分，通过对Table-Graph的分析，区分出数据库中用于表示关系的表和表示实体的表，对多对多、一对多等关系进行转换，并给出一系列规则来描述如何将数据库中的实体、属性、关系及数据转换到RDF中。

本方法侧重于数据库内实体间语义关系的发现工作，因此将关系模式信息和RDF转换分离进行，使用Table-Graph作为中间结果。这样的好处是可以更好地评估整个关系数据库内部的实体关系，同时，若实体间关系发现部分加入了新的规则，不会影响到实体间关系的转换部分。

2 实体间关系发现

在关系数据库中，由于数据库软件自身的限制，或者是设计人员在构建时缺乏数据库相关知识，数据库模型存在缺乏语义的问题[10]。因此在实体间关系转换之前，先要发现关系数据库模型中的潜在语义关系。

潜在语义关系可由数据库模式推断而来，例如图1中Movie表中有DirectorID字段，而Director表中存在ID字段，那么这两个字段之间很有可能有语义关系。但是，仅仅通过数据库模式判断常常存在大量的假阳性问题。例如图1中Movie表有ID字段，Actor表亦有ID字段，仅通过数据库模式判定，会认为二者间具有语义关系，但事实上这两者并不相关。因此引入内容数据进行判断，Actor的ID字段内容与Movie的ID字段内容差异较大，判断二者并无语义关系，从而减少判断的假阳性问题。本文融合了数据库模式和数据内容构建特征向量，用于发现潜在的语义关系。

从关系数据库到Table-Graph的步骤如下：1) 根据数据库模式和数据库内容实例构建特征向量；2) 使用分类算法对特征进行学习训练；3) 使用训练出的模型对所有语义关系进行判定，检测其是否成立，构成最终的Table-Graph。

为了方便讨论，将数据库表记为T,数据库表的属性记为a，待判定的语义关系记为IND(a1,a2)，其中a1∈T1，a2∈T2且T1≠T2。如果IND(a1,a2)成立，将a1称为依赖属性，将a2称为引用属性。

2.1 实体间关系特征构建

2.1.1属性名称相近度特征

由于数据库属性名称命名存在不规范现象，为了提高评判的精准性，本文对属性名称进行规范化后构建词集，使用词集判定IND(a1,a2)中属性名称的相近度。该算法伪码描述如算法1所示。

算法1属性名称相似度特征

Input：属性名称a1、a2，表名T1，T2

Output：词集相似度特征R1、R2

1S1←split(a1),S2←split(a2),R1←1.0,R2←1.0

2 ifS1equalS2then

3 returnR1,R2

4 end if

5S1←S1∪split(T1),S2←S2∪split(T2)

6S1←S1∪headof(T1),S2←S2∪headof(T2)

7S1←S1-stopWord,S2←S2-stopWord

8R1=length(S1∩S2)/length(S1)

9 R2=length(S1∩S2)/length(S2)

10 returnR1,R2

该算法包括以下步骤：

1) 复合词组拆分，使用符号分析器split函数，将属性名称字符串根据连接符、大小写、数字等将复合词组拆成单独的单词集合。若拆分后的词集相同，则直接返回属性A1到属性A2，属性A2到属性A1的词集相似度均为1.0。

2) 将表名归入单词集合，对表名进行同样的复合词组拆分，使用用headof函数，取表名首字母组成表名缩写，将拆分后的表名词组和表名首字母缩写一并归入词集，然后从词集中去除id、key等常见stopWord。

3) 计算词集的交集对(a1,a2)各自词集的覆盖情况，作为一项特征归入接下来的计算。

2.1.2数据类型匹配特征

同一数据在不同表格中可能有多种存储形式，例如电话号码，在一个数据库表格中存储为vchar类型，而在另一数据库表格中存储为Integer类型。为了提高语义关系发现的召回率，本文结合文献[11]中提到的方法，根据数据类型之间相互转换的情况定义了相似度表格判定属性间的数据类型匹配程度。表1展示了部分数据类型间的匹配特征矩阵。

表1 数据类型相似度表

2.1.3数据库关系特征

在数据库中已经存在的语义关系IND(ai,aj)包含了数据库所涉及领域的语义，因此可以对潜在的IND(a1,a2)的推断提供信息，主要有以下三种情况：

1) 被引用中的依赖：该特征计算IND(ai,a1)已经成立的次数。通常，一个依赖属性不会在其他IND中作为引用属性出现，即不会出现依赖传递的情况。IND(ai,a1)出现的次数越多，IND(a1,a2)成立的可能性越小。

2) 多重引用：该特征计算IND(ai,a2)已经成立的次数。从对现有数据库的分析中得知，引用属性通常被多个属性依赖着。IND(ai,a2)出现的次数越多，IND(a1,a2)成立的可能性越大。

3) 多重依赖：该特征计算IND(a1,ai)已经成立的次数。根据现有的实验分析，同一属性通常不会出现多重依赖关系。若已有IND(a1,ai)成立，则IND(a1,a2)成立的可能性下降。

2.1.4数据库内容交集特征

在绝大多数情况下，引用属性覆盖了依赖属性的大部分取值，而依赖属性是引用属性的一个随机取样。这里使用属性a1、a2的值交集情况作为判定IND(a1,a2)成立的特征。设d1、d2是属性a1、a2的中独特值的集合，使用文献[12]中的Jaccard系数进行判定：

2.1.5数据库内容实例特征

描述同一实体的属性的数据内容通常有相似的分布情况，这里使用属性a1、a2的值的分布情况作为判定IND(a1,a2)成立的特征。使用Wilcoxon rank-sum算法[16]进行随机性测试，判定属性a1、a2的值的分布情况是否相同。该算法不要求对比的属性具有相同数量的值，适合计算IND(a1,a2)属性值的分布相似特征。

2.2 实体关系发现模型训练

在获取特征之后，需要对每个特征进行估值，以决定其在对新数据集进行处理时所占的权重。本文从已有IND的数据库中构建数据库模式特征和内容特征，组成特征向量，使用了scikit-learn[13]提供的随机森林算法对特征进行有监督的学习，训练相应的模型,以获得特征的权重。在训练好模型后，对需要进行转换的数据库中所有的IND(ai,aj)进行判定，分离出成立的IND(a1,a2)，构建Table-Graph。其中特别处理了以下情况：

1) 空表格。若已有的IND(a1,a2)中的a1或a2中没有内容，因为无法从属性中提取实体，所以该IND(a1,a2)视为不成立。

2) 被引用的依赖属性。该情况中的特征已在2.1节中剔除，但存在例外情况，当已有的IND(a1,a2)和IND(a2,a3)均成立时，则IND(a1,a3)视为成立。

3) 一对一关系。当两个主键一一对应时，则IND(a1,a2)和IND(a2,a1)均视为成立。

2.3 生成Table-Graph

为了表示数据库中各个表之间的关联，发掘出数据库内蕴含的语义信息，本文提出Table-Graph。Table-Graph是用于描述数据库语义关系的有向图，将数据库表作为图中的元素，数据库表间引用关系作为图中的边，从而表示数据库表间的关联，为接下来的实体间关系转换提供指导。

若将原关系数据库模型形式化地表示为T(A,D,F)，其中T为数据库表；A为组成该表的属性集合；D为属性域的集合；F代表属性间的约束关系，包括主键、外键及其他完整性约束。为了方便，给定以下函数：

PK(T)：表示T的主键，为一属性组。

FK(T)：表示T的外键，为一属性组。

IND(a1,a2)：当其为真时，表示来自T1表的a1属性，引用了来自T2表中的a2属性。

那么，将Table-Graph所有元素的集合记为V，所有有向边的集合记为E。假设有两个元素a1∈T1，a2∈T2，且IND(a1,a2)为真，则a1∈V，a2∈V，且(a1,a2)∈E。

在分辨出所有成立的IND(a1,a2)后，可以按以下步骤自动生成Table-Graph：

1) 将所有T(A,D,F)构成元组，作为元素加入图中。元组内容为T中所有属性A，元素命名使用T的名称。

2) 对所有为真的IND(a1,a2)，在图中将a1和a2这两个元素连接起来，由a1指向a2。

对图1中数据库生成的Table-Graph如图5所示。

图5 Table-Graph示例

3 实体间关系转换

在获得了Table-Graph后，可利用一些著名且普遍出现的关系数据库模式，例如经常出现的多对多关系、一对多关系，为转换结果提供额外的转换信息。接下来介绍Table-Graph的一般转换规则以及这几类关系的特殊转换规则。

3.1 一般转换规则

根据W3C的直接映射规则规定，本文针对Table-Graph的一般转换规则如下：

1) 利用2.1节中提到的属性名称词集构建方法，去除Table-Graph中各属性的冗余部分，如数据库表名缩写、连接符等。但若数据库属性词集只含有常见后缀，则不去除。例如：若属性名为DirectorID，则将其化简为Director；若属性名为ID，则保持属性名仍为ID。

2) 对Table-Graph中每一元素的主键生成一个RDF实体，其URI由表格名称和主键名称组成，用符号“=”连接主键名称和主键内容。例如在Actor表中，属性ID值为11的条目将被转换为实体。

3) 为上面的每一个实体增加一个rdf:type，它的值来自数据库库关系图元素的名称。例：rdf:type。

4) 对Table-Graph元素的各个非主键属性生成RDF三元组。用符号“#”连接数据库元素名和属性名作为这一关系的名称，它的值来自Table-Graph该属性的值。如上述的Actor表中有Name属性，则会生成三元组Marry。

5) 对一般的实体间关系，根据上面的第一步生成两个实体，使用依赖属性的Table-Graph元素名加-rel-加依赖属性名的方法作为这一关系的名称。若Actor表有一age属性，依赖于另一张Date表中属性year，则这一关系转换的RDF三元组为：。

3.2 特殊转换规则

在关系数据库模型中，有时一些表格并不代表实体，而是作为邻接表存在，属于对关系的一种表示，因此在最终的RDF结果中不应转为实体。与文献[14]不同，本文对这些关系的转换无需现有的本体网络参与，而是利用Table-Graph，提出了针对实体间关系的特殊转换规则：

1) 多对多关系。在Table-Graph中，若有v∈V，v中仅包含属性e1和e2，且(e1,ei)∈E,(e2,ej)∈E,ei∈PK(vi)，ej∈PK(vj),则v只是用来描述vi和vj之间的多对多关系。对属性e1和e2无需提取RDF三元组，而是根据v中的每一元素内容构建一条RDF，其主体和客体分别是ei和ej对应的实体，而关系的命名法是v1-has-v2。例如图5中的MovieActor表,在转换为RDF可表示为：

2) 一对多关系。若有v1∈V，v2∈V，e1为v1中属性，e2为v2中属性，有(e1,e2)∈E,e1∉PK(v1)，e2∈PK(v2)，则存在e1到e2的多对一关系。这种多对一关系将被转换为RDF中的属性。这一RDF属性的命名法是v2-of-v1，RDF属性的domian为e2属性，RDF属性的range为v1中除e1外的其他属性。该属性转换后的客体将是v1对应的实体。例如图5中的Movie表中的DirectorID属性，则会转换为：

4 实验评估

4.1 实验评价指标

本节通过实验验证本文所提方法的有效性，使用综合评价指标(F-Measure)进行评估。假设方法返回的所有相关关系中正确的为TP，错误的为FP，所有领域专家人工发现正确的关系数为R，则综合评价指标定义如下：

4.2 实验分析

在实验数据方面，选用TPC-H、TPC-DS、MovieLens和AdventureWorks这四个数据集。表2列出了这些数据的表格数量、属性数量、元组数量和实体间关系数量等数据特征。

表2 实验数据特征

由于这些数据库没有标准的RDF转换后结果，因此采用去除数据库表间已有实体间关系构成新的数据集。在该数据集进行挖掘，将挖掘出的实体间关系与原数据集的实体间关系进行对照，以评估算法。

在实验部分，首先构建如表3所示的4个训练/测试集。保证来自同一数据库的实体间关系不会被用在同一数据库的验证过程中。

表3 训练/测试数据特征

然后使用文献[15]中的实体间关系预测办法(MLA)，对数据集进行提取，其对比结果如图6所示。接着使用本文的算法，对同一数据集进行提取，并对比提取结果。在MLA中提到了四种算法，这里选择与其中表现效果最好的J48进行对比。

图6 MLA与本文的提取结果的对比

可以看出，本文的方法在四个数据集上均获得了优于前者的效果，足以证明所提方法的有效性。特别的，在T2/D2和T4/D4这两个数据集上，由于这两个测试数据集中的关系数据库属性存在命名不规范现象，MLA的表现较明显地弱于本文所使用的方法，而本文使用词集构建的名称特征以及内容特征处理这一问题，获得了更好的效果。

此外，本文还对数据库内已存在实体间关系的情况进行了实验。不使用已有实体间关系，基于数据库划分数据集的实验结果如表4所示。而利用了数据库内已有实体间关系，使用交叉验证方法进行预测的实验结果如表5所示。平均预测准确度从0.78上升到0.87，可见引入同一数据库内的实体间关系能有效提升潜在实体间关系的预测效果，印证了数据库内可使用已有约束特征对实体间关系的预测效果这一假设。

表4 基于数据库层级的实验结果

表5 基于交叉验证的实验结果

在完成上述的外键发现后，本文按照2.3节中的方法构建Table-Graph，用邻接矩阵保存Table-Graph。根据3节中的数据库设计模式，分析Table-Graph，发现其中的实体间关系，并完成到RDF的转换。针对这一部分的测试，本文使用W3C RDB2RDF工作组提供的直接映射测试样例进行实验。该测试样例中提供了使用直接映射方法构建的三元组，因此适合进行评估对比。该文使用测试集D011进行展示，该测试样例不使用实体间关系发现的转换结果如图7所示，使用本文方法发现实体间多对多关系转换结果如图8所示。可以看出，发现的实体间关系减少了最终生成实体的数量，明确了其中潜含的语义关系，提升了最终生成RDF的质量。

图7 未发现实体间关系的转换结果示例

图8 发现多对多关系的转换结果示例

5 结 语

本文针对关系数据库到RDF的转换问题，在已有研究的基础上，提出了一种利用数据库中实体间关系发现与提取的方法。利用数据库模式和数据库内容构建特征，基于特征利用随机森林算法搜索潜在实体间关系，利用实体间关系的相互结构构建数据库到RDF的转换。经实验证明，该方法提升了发现数据库中各属性间的潜在关系的准确度，使用这些实体关系带来的数据库常见设计模式，发现其中潜藏的语义关系，能有效地减少最终生成RDF的冗余，提升了后续知识图谱构建的质量。

当然，本文还有一些可以改进与扩展之处。比如，可以考虑提取更多种类的实体间关系，如继承关系的提取，以进一步丰富最终结果的语义；另外，数据库查询的SQL语句中也存在一定的实体间关系，利用这些信息，亦可对实体间关系的提取问题产生积极的影响。