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

1、基于本体的关系数据库关键词语义查询扩展方法*国家自然科学基金（60773100），国家“十一五”科技支撑计划（2006BAK05BO2），河北省自然科学基金（F2009000475）。郗君甫，刘国华，唐军军，祁瑞丽，朱鹤（燕山大学 信息科学与工程学院，河北 秦皇岛 066004）6 / 6文档可自由编辑打印摘 要：目前关系数据库关键词查询技术主要利用关键词的语法匹配，而没有利用数据之间的语义关系进行匹配，导致查询效果往往都不太令人满意。为了改善查询效果，结合本体概念，提出了基于本体的关系数据库关键词查询的语义查询扩展方法，把用户提交的查询关键词扩展为基于本体的语义关键词。实例分析表明，扩展后的

2、语义关键词尽可能符合用户的真实意愿。关键词：关键词；本体；概念树； 语义相似度中图分类号：0 引言关系数据库上的关键词查询1- 4已成为数据库和信息检索领域的研究热点之一。关系数据库关键词查询(Keyword Query Over Relational Databases,KQORD)使得用户通过提交查询关键词来访问关系数据库，而无需了解数据库模式，也不用懂得书写SQL查询，也不需要学习和使用关系数据库的定制的查询界面。一般是基于关系数据库管理系统(RDBMS)提供的全文检索技术来实现的。这种访问方式仅仅采用语法匹配，而没有利用数据之间的语义关系(如同义词、上下位、转喻等)进行语义匹配，导致它

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

4、高查询结果的查全率，并改善查准率7。为了改善KQORD的查询效果，把信息检索领域的查询扩展技术应用到KQORD技术中，提出了基于本体的关系数据库关键词查询的语义查询扩展方法，把用户提交的查询关键词进行语义查询扩展，将其扩展为基于本体的语义关键词。实例分析表明，扩展后的语义关键词尽可能符合用户的真实意愿。将该方法应用到目前的关系数据库查询技术中，可使得KQORD转换成基于本体的关系数据库语义查询，为KQORD提高查询效果提供了一条新的方法和途径。1 基本定义所谓本体，通俗地讲，是用来描述某个领域甚至更广范围内的概念以及概念之间的关系，是概念和概念之间的集合8。目前，本体已经被广泛应用于语义网、知

5、识工程、信息检索以及信息集成等方面。本体可表示为O(Cg,Rg,Hg),其中Cg是概念全集，即本体中的所有概念的集合，记为CgC1,C2,Cm， Rg是概念和概念之间的关系集合， Hg是层次集合。一个领域本体可能会有很多层次结构(如父子关系、部分关系、相关关系等)，而父子关系是本体的最重要的层次结构，也是基于本体的查询处理最主要的层次结构9。父子关系是一个偏序的关系，具有传递性、自反性、反对称性等特点。如图1所示， ACM Classification System 1998分类系统作为计算机领域本体来描述DBLP数据库中的Papers表的Title属性，是一个父子关系的层次结构。把本体看作概

6、念树Ct(O)，如图1所示的概念树的根为最抽象的概念C(Root)。相关定义如下（定义8和定义12引自10)：定义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的一个顶

7、点，当且仅当关系模式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且(titj)Î(rirj)，那么，(ti ,tj)是T的一条边，其中tiÎri, tj

8、6;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:叶子概念

9、 概念树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

10、3;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)为在概念树中

11、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)。 图1 ACM CCS98的计算机领域本体片段(概念树)Fig 1 ACM CCS98s Ontology fragment in Computer domain(Concept tree)2基于本体的语义查询扩展方法把用户提交的查询关键词扩展为基于本体

12、的语义关键词的过程。(1)查询关键词转换为概念集 把用户提交的一个查询关键词Kq中的关键词ki(1£i£m)通过Ontology模块转换成本体中的概念集。(2)构造概念子树 对概念集中的各个概念进行语义扩展，生成概念子树，即概念子树由一组概念构成。(3)生成语义关键词 提出了一种新的语义相似度计算方法，对概念子树中的概念进行语义相似度计算，并对语义相似度计算值进行排序，依据top-k策略筛选扩展结果，并将扩展结果和用户提交的查询关键词ki合并成语义关键词。2.1 查询关键词转换为概念集将用户提交的查询关键词Kq中的关键词ki(1£i£m)转换成概念树相对

13、应的概念集是指把一个关键词查询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中提出的计算本体(即概念树)上任意两个概念的相似度的公式： (1)其中

14、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的

15、概念子树时，利用公式(1),可得到圆心与其它概念之间的语义相似度值，见表1。表1 语义相似度表 Tab.1 Table of semantic similarity概念对(H.2, H)(H.2, H.2.2)(H.2, H.2.4)(H.2, H.2.8)语义相似度0.670.800.800.802.2.2 构造概念子树的方法通过简单的例子说明概念子树的构造过程：以例2.1为例，用户提交的查询关键词Kq (“Database Management”)转换成的概念集Cs=(“H.2 Database Management”)，简写为Cs=( “H.2” )，概念C(H.2)为构造的概念子树的圆

16、心。当系统设定m=0时，概念子树的半径为零，此时概念子树只有圆心点构成，如图2(a)所示；当系统设定m=1时，概念子树的半径为1，依据构造概念子树的算法生成概念子树，如图2(b)所示的概念子树的实例。为了使基于本体的语义查询扩展后，生成的语义关键词集，尽可能的符合用户的真实意愿，通过设定m的值，来构造概念子树。(a)m=0 (b)m=1图2 概念子树的实例Fig 2 The example of concept subtree构造概念子树算法的简单描述如下：(1) 确定概念集Cs中Ci在概念树上的位置，不是概念树Ct(O)根概念的情况下，才进行构造，即先确定概念子树的圆心点Ci(1£

17、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合

18、并成新的查询关键词(语义关键词)。语义相似度计算公式在此环节中至关重要，主要是为了满足根据用户输入的k值，依据top-k策略筛选扩展结果，生成语义关键词集中拥有语义关键词的个数。基于公式(1)，考虑其它因素，提出了一种新的语义相似度计算公式，在2.3.1详细描述。2.3.1 语义相似度计算公式语义相似度公式是对概念子树中的圆心与其它概念进行语义相似度计算的标准，其应该考虑三个因素：1)概念重合度：由概念子集构造的概念子树，当两棵或多棵子树中的概念有重合时，表明此概念与概念子树的圆心点语义相似度越大，简称概念重合度，t为该概念重合的个数，用P(Cj)表示。2)概念有向边的密度：文献11提到概念层

19、次树的区域密度问题。概念层次树中整体区域密度是一个固定的值，但是不同地方区域密度是不同的，该处的概念细化也越大，对应有向边的权重也就越大。此概念与概念子树的圆心点语义相似度越大，用S(Cj)表示圆心概念Cj与d个有向边的密度。其中Ci为概念子树的圆心概念，Cj为同一概念子树上的除圆心概念之外的其它概念,degree(Ci)表示圆心概念在概念层次网络树的度，degree(Cj)分别为概念子树中除圆心概念外其它概念在概念层次网络树的度，而degree(O)表示概念树Ct(O)的度。3)概念信息量：概念子树中除圆心概念外其它概念的信息量I(Cj)。I(Cj)=概念被标注的元组数量nj/概念子树中所有

20、概念被标注的所有元组的数量N, I(Cj)越大说明被越多的元组标注12，在数据库中共现程度越大。基于以上三个因素，提出语义相似度公式： (2)其中圆心概念Ci与概念子树上的其它概念Cj计算语义相似度计算公式，P(Cj)为概念Cj重合度，S(Cj) 为概念Cj有向边的密度，I(Cj)为概念Cj的信息量，q为阈值(可调节参数)，默认为2,为调节参数，默认为1。2.3.2 利用语义相似度计算公式生成语义关键词集语义查询扩展的目的是为了找到与提交的查询关键词Kq中的关键词ki(1£i£m)语义主旨相关的概念进行扩展，对概念子树中的概念进行语义相似度计算，并对经语义相似度计算后生成的

21、结果进行排序，根据用户需求，依据top-k策略筛选扩展结果，生成语义关键词。3 实例验证及分析基于本体的关系数据库关键词查询的语义查询扩展方法，为关系数据库关键词查询提高查询效果提供了一条新的方法和途径。但是，目前对于基于关键词查询语义扩展方法，如何衡量生成的语义关键词集的好坏和查询扩展效率的高低，没有一系列标准的测试数据集和基准测试查询，而在IR领域，有一系列的标准数据集和基准测试查询(TREC)。利用ACM Classification System 1998分类系统的计算机领域本体，假定通过本体标注技术，预先建立了本体与数据库数据之间的联系,表2给出了数据库中数据和本体中概念之间标注的数

22、量。表2概念与标注元组的数量Table.2 The concept and the quantity of labelling tuple概念HH.2H.3H.2.2H.2.4H.2.8H.2.2.1H.2.2.3H.2.4.6H.2.4.7标注元组数7201593572183740对用户提交的任意一个查询关键词Kq，采用基于本体的关系数据库关键词查询的语义查询扩展方法。假设Kq为“Database Management”。当m=0时，不对用户输入的关键词进行概念子树的构造。当m=1时，构造概念子树，利用公式(2)语义相似度计算公式，可得到概念子树中圆心概念与其它概念之间的语义相似度值，见表3

23、。计算概念子树上圆心概念与其它概念的语义相似度,依据top-k策略筛选扩展结果，并将扩展结果和用户提交的查询关键词ki合并成新的查询关键词(语义关键词)，尽可能的使生成语义关键词符合用户的真实意愿。表3语义相似度Table 3 Semantic similarity概念对(H.2, H)(H.2, H.2.2)(H.2, H.2.4)(H.2, H.2.8)语义相似度0.780.921.010.9分析可知，当m等于1的时候对关键词进行语义扩展，利用公式(2)语义相似度计算公式可得到新的排序结果，根据用户提供的k值，选择生成语义关键词的个数，返回语义关键词。同理，可得到构造的其它概念子树返回的语

24、义关键词。4 结论本文提出的基于本体的关系数据库关键词查询的语义查询扩展方法为完善关系数据库关键词查询技术的研究工作开辟了一条新路，也为关系数据库关键词语义查询的研究奠定了基础。参考文献1 G.Bhalotia, A.Hulgeri, C.Nakhe, etc. Keyword searching and browsing in databases using banksC. Proc of International Conference on Data Engineering, 2002:431-440.2 F.Liu, C.T.Yu, W.Meng, etc. Effective key

25、word search in relational databasesC. 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 graphsC. Proc of the ACM SIGMOD International Conference on Management of Data, 2007:305-316.4 G.Li, B.C.J.Feng, J.

26、Wang, etc. Ease:Efficient and adaptive keyword search on unstructured, semi-structured and structured dataC. Proc of the ACM SIGMOD International Conference on Management of Data. 2008:903-9145 田萱,杜小勇,李海华.语义查询扩展中词义-概念相关度的计算J. 软件学报, 2008:2043-2053.6 Y.G.Qiu, H.P.Frei. Concept based query expansionC.

27、Proc of the 16th annual international ACM SIGIR conferenceon research and development in information retrieval, 1987.30(11) :964-9717 张俊,关系数据库关键词检索性能优化技术研究D. 中国人民大学,2007:110-134.8 杜小勇, 李曼, 王珊. 本体学习研究综述J 软件学报, 2006.17(9):1837-18479 J.Kohler, S.Philippi, M.Lange.SEMEDA:ontology based semantic integrat

28、ion of biological databasesJ. Bioninformatics,2003.19(18):2420-2427.10 P.Ganesan, H.Garcia-Molina, J.Widom. Exploiting Hierarchical Domain Structure to Compute SimilarityJ. ACM Transactions on Information Systems, 2003.21(1):64-93.11 E.Agrire, A Proposal for Word Sense Disambiguation Using Conceptual DistanceC. Proc of the 1st International Conference on Recent Advances in NLP, 1995.12 时念云,杨晨. 基于领域本体的语义标注方法研究J. 计算机工程与设计, 2007.28(24).A semantic ex