第7卷第6期 智能系统学报 Vol.7 No.6 2012年12月 CAAI Transactions on Intelligent Systems Dec.2012 D0I:10.3969/i.issn.16734785.201111032 网络出版t地址：htp://www.cnki.net/kcma/detail/23.1538.TP.20121116.1702.012.html 一种基于领域知识的XML数据模糊查询 孟祥福'，张霄雁，马宗民2，彭晏飞 (1.过宁工程技术大学电子与信息工程学院，辽宁葫芦岛125105；2.东北大学信息科学与工程学院，辽宁沈阳 110819) 摘要：为了解决普通用户对XML数据的模糊查询问题，提出了一种基于领域知识的XML数据模糊查询方法.以模 糊集理论为基础，首先介绍了XL数据模糊查询的构成形式：然后提出了将领城知识和模糊集的隶属函数相结合的 方法实现XML数据的模糊查询条件转换，转换过程考虑了查询谓词的重要程度和用户偏好；最后按结果元素对模糊 查询的满足程度对模糊查询结果进行排序.该方法无需改变传统的XML查询语言和XDBMS就能够实现模糊查询， 从而提高了用户与系统之间的交互能力.实验结果表明，提出的模糊查询方法具有较高的查全率和准确率. 关键词：XML;模糊查询：领域知识：用户偏好；排序 中图分类号：TP311.13文献标志码：A文章编号：16734785(2012)060525-11 An XML fuzzy query answering approach based on domain knowledge MENG Xiangfu',ZHANG Xiaoyan',MA Zongmin2,PENG Yanfei' (1.College of Electronic and Information Engineering,Liaoning Technical University,Huludao 125105,China;2.College of Information Science and Engineering,Northeastern University,Shenyang 110819,China) Abstract:To deal with the problem of XML fuzzy query for common users,this paper proposes a domain knowledge- based XML data fuzzy query approach.Based on fuzzy sets theory,this paper firstly introduces the form of XML fuzzy query.And then,an approach which leverages the domain knowledge and membership function of fuzzy set to realize the fuzzy query translation of XML data,is presented.The importance of querying predicates and user preferences are taken into consideration when the fuzzy query is translated.Finally,for the fuzzy query results,the elements of them are ranked according to their satisfaction degree to the original fuzzy query.This approach can realize the fuzzy query without modifying XML query language and the XDBMS,and thus it can help users to improve their interaction with the system. Results of experiments demonstrate that the fuzzy query approach proposed in this paper has high recall ratio and preci- sion. Keywords:XML;fuzzy query;domain knowledge;user preference;ranking 随着WWW的迅速膨张和Internet的普遍应 能够支持其模糊查询要求的表达，通过直接含有模 用，访问Wb已成为人们获取信息的重要手段. 糊词或模糊关系的模糊语言查询XML数据， XML规范是当今Wb上信息表示与交换的标准，大 来看一个例子，在一个存储房产信息的XML文 量的异构数据因而也就集成在XML文档中.然而 档(HouseDB.xml)中，假设用户想查找“价格至多 在现实中，普通Wb用户的查询意图本身就可能是 $300000,建筑时间比较近，面积在130~200m2” 模糊或不精确的，他们所提交的查询大多数情况下 的房产，可能会输入如下XPath查询语句： 也只是其查询意图的模糊描述.因此，用户希望系统 :-/HouseDB/House[Price at most 300 000] Buildyear ='Recent']SgFt between 130 and 收稿日期：2011-11-30.网络出版日期：2012-11-16. 200]. 基金项目：国家青年科学基金资助项目(61003162). 通信作者：孟样福.E-mail:mai@126.com. 其中，基于内容的查询约束在XPath中用谓词的形
·526 智能系统学报 第7卷 式表示.很明显，该查询包含了3个查询谓词，分别 在模糊集理论基础上，提出了一种直接支持用户模 是“Price at most300O00”、“Buildyear-'Recent'"和 糊查询要求的查询处理方法，该方法能够处理模糊 “SqFt between130and200”,其中前2个查询谓词 关系和模糊词以及对精确数值区间进行模糊扩展， 分别包含了模糊关系“at most”和模糊词“Recent'”. 并且查询处理过程考虑了用户偏好.该方法能够在 这里，将包含模糊关系或模糊词的查询谓词称为模 不改变传统XML查询语言和XML数据库引擎的前 糊查询谓词.如果一个以XPat山h形式表示的XML查 提下实现模糊查询，从而提高用户与系统之间的交 询中包含了一个或多个模糊查询谓词，则称之为 互能力 XML模糊查询.然而，目前的XML数据查询处理模 1 XML模糊查询谓词的构成形式 式仅支持精确查询匹配，还不能直接处理这样的模 糊查询.因此，系统首先需要将模糊查询条件转换为 传统的XPath查询形式由路径(path)和基于内 精确查询条件，然后再提交给XML数据管理系统执 容的查询谓词(value-based predicate)2部分构成.基 行，进而获取满足模糊查询要求的结果 于内容的查询谓词形式为A0Y,其中A代表XML数 在关系数据库领域，Tahani2]最先基于Zadeh 据树的叶节点，日代表操作运算中的规则关系（例 提出的模糊集3]来处理关系数据库中含有不精确 如=、>、<、≥、≤、≠、(not)between),Y代表操 查询条件的模糊查询；Bosc等对标准SQL进行了模 作数（用户查询要求中指定的精确查询值）.在实际 糊扩展45]，提出了SQLf语言，该语言也是对以前经 应用中，由于用户提出的模彻查询要求通常体现在 典数据库模糊查询方法（如Tahanit3)、Bosc[6、Naka 基于内容的查询谓词中，也就是说在查询谓词中使 jima)的特点和功能的集成.Chen8]和Ma提出 用模糊关系（如“close to”)或模糊词（如“young”). 了模糊查询条件转换规则，能够处理查询条件中包 因此，本文主要研究XML模糊查询谓词的构成形式 含的模糊关系或模糊词.文献[10-11]提出了基于模 及其向精确查询谓词的转换方法.模糊查询谓词是 糊集的模糊描述逻辑的推理方法.近年来，研究者开 由规则关系与模糊词的结合或模糊关系（如(not)at 始关注XML数据的柔性查询工作2].文献[12- most、(not)at least、(not)close to/around)与精确值 13]利用本体处理XML文档的柔性查询，使用查询 的结合而构成的，这类基本模糊谓词条件可由具有 重写机制获取近似查询结果，查询重写过程依赖于 隶属函数的模糊集来表示， 领域专家参与建立的本体知识库和映射规则.文献 1.1模糊词作为操作数 [14]提出了XML近似查询结构匹配TreeSketch算 模糊词作为操作数与规则关系作为操作符构成 法，通过在精确的TreeSkech上构建概要来处理 的模糊查询谓词，形式为A0Y,其中A代表XML数 XML小枝模式查询，进而快速返回结构近似匹配的 据树的叶节点，0代表规则关系，Y是模糊词.其中 查询结果.文献[15]在一个XML基本模式中，首先 模糊词包括简单模糊词、复合模糊词和混合模糊词， 鉴定用户提出的XL查询模式与其他模式的结构 相似性，然后在查询处理阶段通过自动重写当前查 它们的含义都可由模糊集合表示8] 1.2模糊关系作为操作符 询，使查询模式与其他相关XML模式兼容，从而找 精确值作为操作数与模糊关系作为操作符构成 到更多模式匹配信息.文献[16]提出了AQAX在线 XML查询系统，该系统基于XML数据概要实现快 的模糊查询谓词，形式为A0Y,其中A代表XML数 速的大规模数据集探测，AQAX使用了双层体系结 据树的叶节点，8是模糊关系，Y代表精确值，Y是 构：第1层在XML聚类(XCluster)框架上生成近似 一个模糊集.在前期工作9，]中，笔者已讨论了由 结果；第2层在XML聚类元素上构建分类树，为用 上述3种模糊关系与精确值构成的模糊集隶属函数 户提供查询可视化界面.文献[17]使用基本变异操 的构建方法 作将用户初始XML查询树改写成系列变异查询树， 1.3数值区间作为操作数 在此基础上根据基本变异操作代价和嵌入代价得到 数值区间作为操作数与规则关系作为操作符构 松弛查询树，从而实现近似查询.然而需要指出的 成的查询条件，形式为AY,其中A代表XML数据 是，现有的XML数据柔性/近似查询方法都是对精 树的叶节点，0代表规则关系“between'”,Y代表数值 确查询条件进行放松处理，进而获取相关查询结果， 区间，用[Y,Y2]表示.A0Y的形式为“A between 但这类方法不支持用户直接表达模糊查询要求，并 Y,andY2”.这里，按照隶属函数和用户给出的阈值 且也不能对模糊查询要求进行转换处理.因此，本文 对数值区间进行模糊扩展
第6期 孟祥福，等：一种基于领域知识的XML数据模糊查询 ·527· 下面，结合具体实例描述以上3种情况下模糊 范围内叶节点的值对查询谓词的满足方式.例如，当 查询谓词向精确查询谓词的转换方法。 Isatisfy取值为“non desc”时，表示叶节点“Pice”上小 于100000的值对查询谓词的满足程度等于1；当Isati-- 2领域知识库 或取值为“desc”时，表示叶节点“Pice”上小于100000 领域知识库由若干XML文档构成，存储领域知 的值对查询谓词的满足程度小于1. 识信息，这些信息用来对模糊查询谓词进行转换，这 2.1.3 Relaxation.xml DTD 些信息包括模糊查询谓词涉及的叶节点，以及根据 <DOCTYPE Relaxation[ 叶节点的语义对模糊查询谓词进行扩展的范围和程 <ELEMENT Relaxation (relax *) 度.领域知识库由领域专家维护或自学习获取知识. <ELEMENT relax (leaf_node,operator,directionr- 2.1文档的DTD el,ldegrel,rdegrel,Isatisfy,rsatisfy)> 本文引言部分的模糊查询谓词转换需要如下4 <ELEMENT leaf_node (#PCDATA)> 个XML文档. <ELEMENT operator (#PCDATA)> 文档NodeRelax.ml提供XML数据树的叶节 <ELEMENT directionrel (#PCDATA)> 点信息.llimit和rlimit分别代表查询谓词所涉及的 <ELEMENT Idegrel (#PCDATA)> 叶节点上进行扩展的数值区间左极限和右极限； <ELEMENT rdegrel (#PCDATA)> nimp中的语义词代表该叶节点在XML文档中的重 <ELEMENT Isatisfy (#PCDATA)> 要程度，这也是查询条件中相应的查询谓词的重要 <ELEMENT rsatisfy (#PCDATA)>]> 程度 文档Fuz四yTem.xml存储描述叶节点取值范围的 2.1.1 NodeRelax.xml DTD 模糊词，每个模糊词都对应一个预先定义的模糊集，模 <！DOCTYPE NodeRelax[ 糊集的隶属函数参数分别取自元素paral、para2、para3、 <ELEMENT NodeRelax (nrelax *) para4中的值. <ELEMENT nrelax (leaf node,llimit,rlimit, 2.1.4 FuzzyTerm.xml DID nimp)> <！DOCTYPE FuzzyTerm[ <ELEMENT leaf_node (#PCDATA)> <ELEMENT FuzzyTerm (fterm *) <ELEMENT llimit (#PCDATA)> <ELEMENT fterm (fuzzy_term,leaf_node,paral, <ELEMENT rlimit (#PCDATA)> para2,para3,para4)> <ELEMENT nimp (#PCDATA)>]> <ELEMENT fuzzy_term (#PCDATA)> 文档Nodelmportance.xml存储表达叶节点重要程 <ELEMENT leaf_node (#PCDATA)> 度的语义词（如high、medium、low等），mdegree代表 <ELEMENT paral (#PCDATA)> nimp中不同语义词所对应的隶属度， <ELEMENT para2 (#PCDATA)> 2.1.2 Nodelmprotance.xml DTD <ELEMENT para3 (#PCDATA)> <DOCTYPE Nodelmportance[ <ELEMENT para4 (#PCDATA)>] <ELEMENT NodeImportance (nimportance *) 2.2文档实例 <ELEMENT nimportance (nimp,leaf_node,mde- 2.2.1 NodeRelax.xml文档实例 gree)> <NodeRelax> <ELEMENT nimp (#PCDATA)> <nrelax <ELEMENT leaf_node (#PCDATA)> <leaf node Price </leaf node <ELEMENT mdegree (#PCDATA)>]> <llimit >150 000</llimit 文档Relaxation.ml指明了查询谓词在相应叶节 <rlimit >1 000 000</rlimit 点上的扩展范围、扩展程度和叶节点上的值对查询谓 <nimp high </nimp 词的满足方式.Directionrel代表查询扩展范围，例如查 </nrelax 询谓词“Price around(大约)100000”，如果Directionrel <nrelax 的值为“left、ight”,则“Pice”的扩展范围同时包括小 <leaf_node SqFt </leaf_node 于和大于100000的值.ldegrel和rdegrel分别代表查询 <llimit >-</llimit 谓词的左右扩展程度.Isatis的和r8atis5分别表示扩展 <rlimit >800</rlimit
·528· 智能系统学报 第7卷 <nimp >medium </nimp> <rdegrel >-</rdegrell </nrelax <Isatisfy decr </Isatisfy <nrelax <rsatisfy nondecr </rsatisfy <leaf node Buildyear </leaf node </relax <llimit >1981 </llimit <relax> <rlimit >-</rlimit <leaf_node Buildyear </leaf_node <nimp >medium</nimp> <operator>=</operator> </nrelax <directionrel >left,right </directionrel <ldegrel>-</Idegrel </NodeRelax <rdegrel >-</rdegrell 2.2.2 NodeImportance..xml文档实例 <lsatisfy decr </lsatisfy Nodelmportance <rsatisfy decr </rsatisfy <nimportance </relax <nimp >high </nimp> <leaf_node >Price <leaf_node </Relaxation <mdegree >0.8</mdegree 2.2.4Fuz四yTem.xml文档实例 </nimportance Fuzzy Term <nimportance <fterm> <nimp medium </nimp <fuzzy_term>recent <fuzzy_term <leaf node >SqFt <leaf node <leaf_node Buildyear <leaf_node <mdegree >0.5</mdegree> <paral >0</paral </nimportance <para2 >0</para2 <nimportance <para3 >5</para3> <nimp >medium </nimp> <para4>10</para4> <leaf_node Buildyear <leaf_node </fterm <mdegree >0.5</mdegree> <fterm> </nimportance> <fuzzy term moderate <fuzzy term … <leaf_node SqFt</leaf_node </Nodelmportance <paral >80</paral 2.2.3 Relaxation.xml文档实例 <para2 >130 </para2 Relaxation <para3 >200</para3> <relax <para4 >250</para4 <leaf node >Price </leaf node </fterm> <operator at most </operator <directionrel >right</directionrel </FuzzyTerm> <ldegrel>-</ldegrel <rdegrel >0.2</rdegrell 3XML模糊查询转换方法 <Isatisfy >nondecr </Isatisfy> 本文提出的XML模糊查询转换实现方法首先 <rsatisfy >decr </rsatisfy 将模糊查询条件中的每个模糊查询谓词用相应的模 </relax 糊集表示，然后借助领域知识库中的领域知识构建 <relax> 隶属函数，同时根据模糊查询谓词的重要程度（在 <leaf_node >SqFt</leaf_node 提出查询要求时，用户可根据个人偏好指定每个查 <operator >between </operator 询谓词的重要程度)，利用权重函数对其进行放松 <directionrel left,right </directionrel 处理，最后根据阈值和α-截集运算将其转换成精确 <ldegrel >-</ldegrel 查询谓词.本节将使用引言中的例子：
第6期 孟祥福，等：一种基于领域知识的XML数据模糊查询 ·529· :-/HouseDB/House[Price at most 300 000] 糊词“Recent”及其对应的参数值（注意，计算过程中 Buildyear='Recent'][SqFt between 130 and 200], 将建筑时间转换成距今的年数).然后，构建模糊词 结领域知识库中的领域知识，描述不同情况下的模 “Recent'”的隶属函数，即 糊查询谓词转换实现方法， 1, b≤5； 10-b 3.1含模糊关系的模糊查询谓词转换 5， 5<b<10: 对于模糊查询条件中的模糊查询谓词“Price at 0. b≥10. most300000”,使用模糊集P表示该模糊查询谓词. 根据扩张原理和模糊词“Recent'”的隶属函数， 为了确定模糊集P的隶属函数，首先从领域知识库文 则可得模糊集B的隶属函数为 档Relaxation.xml中找出对应模糊关系“at most'”和 19 叶节点“Pice”的左右扩展方向(Relaxation.xml中的 b≤5； directionrel元素)，叶节点值对模糊查询谓词的满足 B(b) 10-b),5<b<10: 5 (2) 方式Relaxation.xml中的Isatisfy和rsatisfy元素.这 0 b≥10. 里，对应叶节点“Pice”和模糊关系“at most”的扩展 然而，该隶属函数没有考虑它所代表的模糊查 方向directionrel元素取值为“ight”,叶节点值对模糊 询谓词的重要程度（假设用户指定该模糊查询谓词 查询谓词的满足方式Isatisfy和rsatisfy元素取值分别 的重要程度为“medium”).为了使隶属函数式(2) 为“nondecr”、“decr”.然后，再根据模糊集“close to 体现模糊查询谓词的重要程度，本文利用了文献 Y的隶属函数9]，可将模糊集P的隶属函数定义为： [19-20]提出的权重函数对隶属函数式(2)进行转 0 p≥d; 换，即 P(P)= 1 p≤300000： (1) g(0,B(b))=1-w(1-B(b)). (3) d-p 式中：代表模糊查询谓词的重要程度.根据知识库 d-300000' 30000<p<d. 文档NodeImportance.xml,可得式（3)中的w= 对于参数d的计算，需要用到Relaxation.xml中 mportance(medium)=0.5.于是，得到转换后的隶属函 提供的扩展程度rdegrel元素的值.在Relxation.xml 数为 中叶节点Price上对应模糊关系“at most”的向右扩 展程度rdegrel=0.2,该扩展程度与模糊查询谓词的 b≤5： 1 B(b)= 重要程度m(high)=0.8相关，于是有 2 +(10b),5<6<10:(4) 5 rdegrel=(d-300000)/300000=0.2→ 0.5, b≥10. d=360000. 权重函数的功能是根据用户指定的模糊查询谓 因此，隶属函数式(1)可转换成： 词在模糊查询条件中的权重来决定其扩展程度.对 0, p≥360000； 于同一个模糊查询谓词，其重要程度越高，则扩展程 P(p)= 1, p≤300000； 度越小，在相同阈值下的查询范围相应地越小，这样 360000-2 30000<p<360000. 才能确保转换后得到的精确查询谓词与用户查询意 600001 图和偏好最为相关 假设用户（或系统）设定的阈值为0.8，则模糊 根据隶属函数(4)，假设用户（或系统）设定的 集P的0.8截集运算结果为： 阈值为0.8，则模糊集B的0.8截集运算结果为 P(p）=360000卫=0.8=p≤31200. 60000 B()=分+(0与=08-b=82 根据文献[8-9]提出的模糊查询转换规则，模糊 这样，模糊查询谓词“Buildyear=more or less 查询谓词“Price at most300000”可转换成精确查询 recent'”可转换成精确查询谓词“Buildyear≤8.2”.需 谓词“Pice312000”. 要说明一点，若给定的阈值α低于(1-0)，则截 3.2含模糊词的模糊查询谓词的转换 集运算结果规定为该模糊查询谓词所对应隶属函数 对于模糊查询条件中的模糊查询谓词“Build 的支集， year=more or less recent(建筑时间比较近)”，使用 3.3含数值区间的模糊查询谓词的转换 模糊集B表示该模糊查询谓词.首先从知识库文档 考虑模糊查询谓词“SgFt between130and FuzzyTerm.xml中找到描述叶节点“Buildyear”的模 200”,使用模糊集S表示该模糊查询谓词.为了确