基于本体的关系数据库关键词语义查询扩展方法

基于本体的关系数据库关键词语义查询扩展方法*

郗君甫，刘国华，唐军军，祁瑞丽，朱鹤

（燕山大学 信息科学与工程学院，河北 秦皇岛 066004）

摘 要：目前关系数据库关键词查询技术主要利用关键词的语法匹配，而没有利用数据之间的语义关系进行匹配，导致查询效果往往都不太令人满意。为了改善查询效果，结合本体概念，提出了基于本体的关系数据库关键词查询的语义查询扩展方法，把用户提交的查询关键词扩展为基于本体的语义关键词。实例分析表明，扩展后的语义关键词尽可能符合用户的真实意愿。 关键词：关键词；本体；概念树； 语义相似度 中图分类号：

0 引言

关系数据库上的关键词查询[1- 4]已成为数据库和信息检索领域的研究热点之一。关系数据库关键词查询(Keyword Query Over Relational Databases,KQORD)使得用户通过提交查询关键词来访问关系数据库，而无需了解数据库模式，也不用懂得书写SQL查询，也不需要学习和使用关系数据库的定制的查询界面。一般是基于关系数据库管理系统(RDBMS)提供的全文检索技术来实现的。这种访问方式仅仅采用语法匹配，而没有利用数据之间的语义关系(如同义词、上下位、转喻等)进行语义匹配，导致它们的查询效果(查全率和查准率)不太令人满意。

在信息检索领域，为解决这一问题，目前多采用查询扩展技术。查询扩展(Query Expansion, QE)，是公认的能够有效提高查全率的技术之一，其基本思想是利用与查询关键词相关的词语对查询进行修正和补充，以便找到更多的相关文档，提高查全率。然而在提高查全率的同时难以保证查准率[5]，根本原因在于，人们在现实生活中描述同样的对象或事件的用词存在多样性。为了解决这个问题，人们提出了基于本体的语义查询扩展方法，用概念来描述查询主旨，找到与查询语义相关的概念进行扩展[6]，筛选出那些语义相似度超过系统设定阈值的概念形成新的查询关键词(语义关键词)，此方法可有效的提高查询结果的查全率，并改善查准率[7]。

为了改善KQORD的查询效果，把信息检索领域的查询扩展技术应用到KQORD技术中，提出了基于本体的关系数据库关键词查询的语义查询扩展方法，把用户提交的查询关键词进行语义查询扩展，将其扩展为基于本体的语义关键词。实例分析表明，扩展后的语义关键词尽可能符合用户的真实意愿。将该方法应用到目前的关系数据库查询技术中，可使得KQORD转换成基于本体的关系数据库语义查询，为KQORD提高查询效果提供了一条新的方法和途径。

1 基本定义

所谓本体，通俗地讲，是用来描述某个领域甚至更广范围内的概念以及概念之间的关系，是概念和概念之间的集合[8]。目前，本体已经被广泛应用于语义网、知识工程、信息检索以及信息集成等方面。本体可表示为O(Cg,Rg,Hg),其中Cg是概念全集，即本体中的所有概念的集合，记为Cg{C1,C2,…,Cm}， Rg是概念和概念之间的关系集合， Hg是层次集合。一个领域本体可能会有很多层次结构(如父子关系、部分关系、相关关系等)，而父子关系是本体的最重要的层次结构，也是基于本体的查询处理最主要的层次结构[9]。父子关系是一个偏序的关系，具有传递性、自反性、反对称性等特点。如图1所示， ACM Classification System 1998分类系统作为计算机领域本体来描述DBLP数据库中的Papers表的Title属性，是一个父子关系的层次结构。

把本体看作概念树Ct(O)，如图1所示的概念树的根为最抽象的概念C(Root)。相关定义如下（定义8和定义12引自[10])： *国家自然科学基金（60773100），国家“十一五”科技支撑计划（2006BAK05BO2），河北省自然科学基金（F2009000475）。

定义1:关系数据库模式 假设关系数据库的模式，Sdb=(R,FK), R={R1,R2,…,Rk}是一组关系模式，FK是R中关系模式间引用关系的映射，FK:RR，如果FK(Ri)=Rj，记为RiRj1i , jn，它表示Rj一个外键引用了Ri主键。

定义2:数据库模式图 假设Gs=(V,E)表示模式Sdb=(R,FK)的关系数据库DB对应的模式图。Gs是一个有向图，将DB中的每一个关系模式Rk(1kn)看作是Gs的一个顶点，当且仅当关系模式RiGs，关系模式RjGs ,(RiRj) FK时，(Ri, Rj)E。

定义3:连接元组树 给定一个关系数据库DB的模式图Gs=(V,E)，T是以DB中的元组tl为结点的一棵树，其中tl(1lm)是关系rk(1km)中元组，关系rk(1km)是关系模式Rk(1kn)上的实例,如果(Ri,Rj)E且(titj)(rirj)，那么，(ti ,tj)是T的一条边，其中tiri, tjrj, (1i,jn)，称T为一棵连接元组树。

定义4:关键词查询 把关键词查询定义为查询函数f: KqTT,其中Kq是一个集合，其元素ki(1im)为关键词，TT是一个集合，其元素Ti(1in)为一个关键词查询结果。

定义5:关键词查询结果TT 关键词查询结果是OR语义，Kq是一个集合，其元素为ki(1im)为关键词，一个查询结果是至少含有Kq中一个ki(1im)且每个叶结点都至少含有Kq中一个ki(1im)的连接元组树。

定义6:叶子概念 概念树Ct(O)的层次网络树中自根向下，没有孩子的概念称为概念树的叶子概念,记为Ct(l)。如图1所示，“I.2.4.9 Ontology”为概念树的叶子概念。

定义7:概念深度 在概念树Ct(O)中，从概念树的根C(Root)到概念C的路径上的边数，记为Dep(C)。如图1所示，Dep(“H.2 Database Management”)=2 ,简写为Dep(H.2)=2。

定义8:概念集 基于概念树Ct(O)的概念集Cs由一组概念组成，记为Cs(C1,C2,…,Cn), Ci(1in)为Ct(O)中的概念,概念集Cs由用户提交的一个关键词查询Kq中的关键词ki(1im)转换成Ct(O)中的概念构成。

定义9:圆心点 概念集Cs内的Ci(1in)称为概念子树的圆心点。

定义10:半径 在概念树Ct(O)上从圆心点Ci到概念C的路径上的边数，半径的大小记为m。 定义11:概念子树 确定圆心点Ci的位置，找出半径为m内的满足概念子树构造算法的所有概念，所形成的树为概念子树，概念子树属于概念树，即所有的概念子树是概念树的一个子集。例如，图2所示，以(H.2)为圆心,m分别为0，1的概念子树。

定义12:最近公共祖先 概念树Ct(O)上的两个概念Ci和Cj,其最近的公共祖先记为LCA(Ci,Cj)，LCA(Ci,Cj)为在概念树中Ci和Cj的公共祖先中具有最大深度的概念。例如：如图1所示的概念树中，概念C(H.2.2)和C (H.2.4)的公共祖先有：C(H.2)、C(H)和C(Root), 在这三个公共祖先中Dep(H.2)=2，Dep(H)=1 , Dep(Root)=0,由此可知C(H.2)的深度最大，所以LCA(C(H.2.2),C(H.2.4))=C(H.2)。

RootACM CCS98H. InfomationSystems I. Computing Methodologies父子关系H.2.Database H.3 Information I.2 ArtificialManagement Storage RetrievalH.2.2 Physical H.2.4 Systems H.2.8 Database Design applicationH.2.2.1 AccessH.2.2.3 Recovery H.2.4.6 Query H.2.4.7 RelationalMethods and restart processingdatabaesH.3.3 InformationSearch and RetrievalH.3.3.3 QueryformulationI.2.4 Knowledge RepresentationFormalisms and MethodsI.2.4.9 Ontology

图1 ACM CCS98的计算机领域本体片段(概念树)

Fig 1 ACM CCS98’s Ontology fragment in Computer domain(Concept tree)

2基于本体的语义查询扩展方法

把用户提交的查询关键词扩展为基于本体的语义关键词的过程。

(1)查询关键词转换为概念集 把用户提交的一个查询关键词Kq中的关键词ki(1im)通过Ontology模块转换成本体中的概念集。

(2)构造概念子树 对概念集中的各个概念进行语义扩展，生成概念子树，即概念子树由一组概念构成。

(3)生成语义关键词 提出了一种新的语义相似度计算方法，对概念子树中的概念进行语义相似度计算，并对语义相似度计算值进行排序，依据top-k策略筛选扩展结果，并将扩展结果和用户提交的查询关键词ki合并成语义关键词。 2.1 查询关键词转换为概念集

将用户提交的查询关键词Kq中的关键词ki(1im)转换成概念树相对应的概念集是指把一个关键词查询Kq中的关键词ki通过概念抽取器转换为概念集相对应的概念Cj,假如没有相对应的概念，就不进行相应关键词ki到概念树中概念的相应转换。例2.1：假如,一个关键词查询Kq (“Database Management”)对应图1所示的概念树的概念集为Cs=(“H.2 Database Management”)，构造概念子树先得确定概念子树的圆心点，即将提交的一个查询关键词Kq中的关键词ki(1im)转换成概念集。 2.2 构造概念子树

2.2.1 构造概念子树的理论依据

依据文献[10]中提出的计算本体(即概念树)上任意两个概念的相似度的公式：

Sim(Ci,Cj)2Dep(LCA(Ci,Cj))Dep(Ci)Dep(Cj) (1)

其中Sim(Ci,Cj)为概念树上的任意两个概念Ci和Cj,语义相似度(概念语义间的相似情况)，LCA(Ci,Cj)为概念Ci和Cj的最近公共祖先，Dep(LCA(Ci,Cj))为概念Ci和Cj的最近公共祖先的深度， Dep(Ci)概念Ci在概念树中的深度。

由公式(1)可知当概念树中的任意两个概念Ci和Cj的最近公共祖先LCA(Ci,Cj)为概念树的根概念的时候，概念Ci和Cj语义相似度值为零。在概念树中只要任意两个概念Ci和Cj的最近公共祖先LCA(Ci,Cj)不为概念树的根概念的时候，它们的语义相似度值就不为零，构造的概念子树上圆心概念与其它概念的语义相似度值不为零。如图2(b)所示，当m=1的概念子树时，利用公式(1),可得到圆心与其它概念之间的语义相似度值，见表1。

表1 语义相似度表

概念对 语义相似度

Tab.1 Table of semantic similarity

(H.2, H) (H.2, H.2.2) (H.2, H.2.4) 0.67 0.80 0.80

(H.2, H.2.8)

0.80

2.2.2 构造概念子树的方法

通过简单的例子说明概念子树的构造过程：以例2.1为例，用户提交的查询关键词Kq (“Database Management”)转换成的概念集Cs=(“H.2 Database Management”)，简写为Cs=( “H.2” )，概念C(H.2)为构造的概念子树的圆心。当系统设定m=0时，概念子树的半径为零，此时概念子树只有圆心点构成，如图2(a)所示；当系统设定m=1时，概念子树的半径为1，依据构造概念子树的算法生成概念子树，如图2(b)所示的概念子树的实例。为了使基于本体的语义查询扩展后，生成的语义关键词集，尽可能的符合用户的真实意愿，通过设定m的值，来构造概念子树。

H. InformationSystemsH.2 Database ManagementH.2.2 Physical DesignH.2 Database ManagementH.2.4 SystemsH.2.8Database application

(a)m=0 (b)m=1

图2 概念子树的实例

Fig 2 The example of concept subtree

构造概念子树算法的简单描述如下：

(1) 确定概念集Cs中Ci在概念树上的位置，不是概念树Ct(O)根概念的情况下，才进行构造，即先

确定概念子树的圆心点Ci(1in) (2) 确定半径m(系统设定)

(3) 首先构造概念树Ct(O)上的概念到圆心点半径为1的所有概念，即以Ci为圆心，半径为1的概

念子树 (4) 确定概念子树中有那些概念为属于根概念和叶子概念 (5) 只对不是根和叶子的概念进行扩展

(6) 以Ci为圆心，半径为2的所有概念，即以Ci为圆心，半径为2的概念子树 (7) 重复步骤4

(8) 重复步骤5，半径自动加1

(9) 直到所有被扩展的概念不满足条件(5)或者半径大小等于m时,结束

2.3 生成语义关键词

对概念子树中的概念进行语义相似度计算，根据语义相似度计算值进行排序，并依据top-k策略筛选扩展结果，将扩展结果和用户提交的查询关键词ki合并成新的查询关键词(语义关键词)。语义相似度计算公式在此环节中至关重要，主要是为了满足根据用户输入的k值，依据top-k策略筛选扩展结果，生成语义关键词集中拥有语义关键词的个数。基于公式(1)，考虑其它因素，提出了一种新的语义相似度计算公式，在2.3.1详细描述。 2.3.1 语义相似度计算公式

语义相似度公式是对概念子树中的圆心与其它概念进行语义相似度计算的标准，其应该考虑三个因素：

1)概念重合度：由概念子集构造的概念子树，当两棵或多棵子树中的概念有重合时，表明此概念与概念子树的圆心点语义相似度越大，简称概念重合度，t为该概念重合的个数，用P(Cj)表示。

PCj1ln1ln1t

2)概念有向边的密度：文献[11]提到概念层次树的区域密度问题。概念层次树中整体区域密度是一个固定的值，但是不同地方区域密度是不同的，该处的概念细化也越大，对应有向边的权重也就越大。此概念与概念子树的圆心点语义相似度越大，用S(Cj)表示圆心概念Cj与d个有向边的密度。

SCjdegree(Ci)degreeCj2degreeO

其中Ci为概念子树的圆心概念，Cj为同一概念子树上的除圆心概念之外的其它概念,degree(Ci)表示圆心概念在概念层次网络树的度，degree(Cj)分别为概念子树中除圆心概念外其它概念在概念层次网络树的度，而degree(O)表示概念树Ct(O)的度。

3)概念信息量：概念子树中除圆心概念外其它概念的信息量I(Cj)。I(Cj)=概念被标注的元组数量nj/概念子树中所有概念被标注的所有元组的数量N, I(Cj)越大说明被越多的元组标注[12]，在数据库现程度越大。

njICjln1

N基于以上三个因素，提出语义相似度公式：

Simm(Ci,Cj)(2Dep(LCA(Ci,Cj))Dep(Ci)Dep(Cj))qP(Cj)S(Cj)I(Cj) (2)

其中圆心概念Ci与概念子树上的其它概念Cj计算语义相似度计算公式，P(Cj)为概念Cj重合度，S(Cj) 为概念Cj有向边的密度，I(Cj)为概念Cj的信息量，q为阈值(可调节参数)，默认为2,为调节参数，默认为1。

2.3.2 利用语义相似度计算公式生成语义关键词集

语义查询扩展的目的是为了找到与提交的查询关键词Kq中的关键词ki(1im)语义主旨相关的概念

进行扩展，对概念子树中的概念进行语义相似度计算，并对经语义相似度计算后生成的结果进行排序，根据用户需求，依据top-k策略筛选扩展结果，生成语义关键词。

3 实例验证及分析

基于本体的关系数据库关键词查询的语义查询扩展方法，为关系数据库关键词查询提高查询效果提供了一条新的方法和途径。但是，目前对于基于关键词查询语义扩展方法，如何衡量生成的语义关键词集的好坏和查询扩展效率的高低，没有一系列标准的测试数据集和基准测试查询，而在IR领域，有一系列的标准数据集和基准测试查询(TREC)。

利用ACM Classification System 1998分类系统的计算机领域本体，假定通过本体标注技术，预先建立了本体与数据库数据之间的联系,表2给出了数据库中数据和本体中概念之间标注的数量。

表2概念与标注元组的数量

概念 标注元组数

H 7

H.2 20

Table.2 The concept and the quantity of labelling tuple H.3 H.2.2 H.2.4 H.2.8 H.2.2.1 H.2.2.3 15 9 35 7 2 18

H.2.4.6 37

H.2.4.7 40

对用户提交的任意一个查询关键词Kq，采用基于本体的关系数据库关键词查询的语义查询扩展方法。假设Kq为“Database Management”。

当m=0时，不对用户输入的关键词进行概念子树的构造。

当m=1时，构造概念子树，利用公式(2)语义相似度计算公式，可得到概念子树中圆心概念与其它概念之间的语义相似度值，见表3。计算概念子树上圆心概念与其它概念的语义相似度,依据top-k策略筛选扩展结果，并将扩展结果和用户提交的查询关键词ki合并成新的查询关键词(语义关键词)，尽可能的使生成语义关键词符合用户的真实意愿。

表3语义相似度

概念对 语义相似度

(H.2, H) 0.78 Table 3 Semantic similarity

(H.2, H.2.2)

0.92 (H.2, H.2.4)

1.01 (H.2, H.2.8)

0.9 分析可知，当m等于1的时候对关键词进行语义扩展，利用公式(2)语义相似度计算公式可得到新的排序结果，根据用户提供的k值，选择生成语义关键词的个数，返回语义关键词。同理，可得到构

造的其它概念子树返回的语义关键词。

4 结论

本文提出的基于本体的关系数据库关键词查询的语义查询扩展方法为完善关系数据库关键词查询技术的研究工作开辟了一条新路，也为关系数据库关键词语义查询的研究奠定了基础。

参考文献

[1] G.Bhalotia, A.Hulgeri, C.Nakhe, etc. Keyword searching and browsing in databases using banks[C]. Proc of International

Conference on Data Engineering, 2002:431-440.

[2] F.Liu, C.T.Yu, W.Meng, etc. Effective keyword search in relational databases[C]. Proc of the ACM SIGMOD International

Conference on Management of Data, 2006:574-563.

[3] H.He, H.Wang, J.Yang, etc. Blinks:ranked keyword searches on graphs[C]. Proc of the ACM SIGMOD International

Conference on Management of Data, 2007:305-316.

[4] G.Li, B.C.J.Feng, J.Wang, etc. Ease:Efficient and adaptive keyword search on unstructured, semi-structured and structured

data[C]. Proc of the ACM SIGMOD International Conference on Management of Data. 2008:903-914 [5] 田萱,杜小勇,李海华.语义查询扩展中词义-概念相关度的计算[J]. 软件学报, 2008:2043-2053.

[6] Y.G.Qiu, H.P.Frei. Concept based query expansion[C]. Proc of the 16th annual international ACM SIGIR conferenceon

research and development in information retrieval, 1987.30(11) :9-971 [7] 张俊,关系数据库关键词检索性能优化技术研究[D]. 中国人民大学,2007:110-134. [8] 杜小勇, 李曼, 王珊. 本体学习研究综述[J] 软件学报, 2006.17(9):1837-1847

[9] J.Kohler, S.Philippi, M.Lange.SEMEDA:ontology based semantic integration of biological databases[J].

Bioninformatics,2003.19(18):2420-2427.

[10] P.Ganesan, H.Garcia-Molina, J.Widom. Exploiting Hierarchical Domain Structure to Compute Similarity[J]. ACM

Transactions on Information Systems, 2003.21(1):-93.

[11] E.Agrire, A Proposal for Word Sense Disambiguation Using Conceptual Distance[C]. Proc of the 1st International

Conference on Recent Advances in NLP, 1995. [12] 时念云,杨晨. 基于领域本体的语义标注方法研究[J]. 计算机工程与设计, 2007.28(24).

A semantic expansion method of keywords query based

on ontology over relational database

XI Jun-fu, LIU Guo-hua, TANG Jun-jun, QI Rui-li, ZHU He

(College of Information Science and Engineering, Yanshan University, Qinhuangdao , Hebei 066004, China)

Abstract: At present, in the keywords query of relational database, matching is performed mainly according to the syntax of the keywords, instead of the semantic relation between data, which lead to an undesirable query results. In order to improve the query effect, combining with the concept of Ontology, a semantic expansion method is put forward based on Ontology for keywords query over relational database, which extends the query keywords provided by users to the semantic keywords based on Ontology. Sample analysis shows that the query results of this method are much closer to the users’ request. Key words: keyword; Ontology; concept tree; Semantic similarity

作者简介：郗君甫（1982-），男，河北邢台人，硕士研究生，主要研究方向为数据库理论，信息检索；