智能系统：一种基于领域知识的XML数据模糊查询

第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 些信息包括模糊查询谓词涉及的叶节点，以及根据 本文引言部分的模糊查询谓词转换需要如下4 个XML文档. 文档NodeRelax.ml提供XML数据树的叶节 点信息.llimit和rlimit分别代表查询谓词所涉及的 叶节点上进行扩展的数值区间左极限和右极限； nimp中的语义词代表该叶节点在XML文档中的重 要程度，这也是查询条件中相应的查询谓词的重要 ]> 程度 文档Fuz四yTem.xml存储描述叶节点取值范围的 2.1.1 NodeRelax.xml DTD 模糊词，每个模糊词都对应一个预先定义的模糊集，模 para2,para3,para4)> ]> 文档Nodelmportance.xml存储表达叶节点重要程 度的语义词（如high、medium、low等），mdegree代表 nimp中不同语义词所对应的隶属度， 2.1.2 Nodelmprotance.xml DTD ] ]> 150 0001 000 000-800</rlimit

·528· 智能系统学报 第7卷 medium -1981 -medium = left,right --high Price 0.8 recent SqFt 0.5 005 medium 10 0.5 80130 200 250Price right -0.2nondecr 本文提出的XML模糊查询转换实现方法首先 decr 隶属函数，同时根据模糊查询谓词的重要程度（在 SqFtbetween -</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表示该模糊查询谓词.为了确

·530 智能系统学报 第7卷 定模糊集S的隶属函数，需要在知识库文档Fuz2四 House[Price at most 300 000][Buildyear ='Recent'] Term.xml中找出一个模糊词，该模糊词满足如下2 [SqFt between130and200]”可转换成精确查询： 个条件：1)代表该模糊词的模糊集与模糊查询谓词 “Q:-/HouseDB/House[Pice≤312000][Build- 的隶属函数形状相同；2)代表该模糊词的模糊集的 year≤8.2][SqFt between110and220]”. 核与模糊查询谓词所指定的数值区间具有相同范 3.4XML模糊查询谓词转换算法 围.通过查找，发现知识库中描述叶节点“SqFt”的模 根据上述转换方法，下面给出通用的XML模糊 糊词“moderate”满足上述条件（即模糊词“moder- 查询谓词转换算法： te”的隶属函数为梯形隶属函数，并且其核为[130， 算法1XML模糊查询谓词转换算法 200]),因此模糊集S的隶属函数可由定义模糊词 输入：模糊查询Q中的模糊查询谓词集合 ‘moderate”的隶属函数表示，即 {C,',C2',…,C'},知识库KB,阈值A 0, s≤80ors≥250： 输出：转换后的精确查询谓词集合{C1,C2,…, 8-80 80<s<130; C}. S(s)= 50 (5) 130≤s≤200； 1)Q-0: 250-s200<s<250, 2)for每一个模糊查询谓词C,e0do 50 3)MFS MembershipFunctionShape relaxation 如果文档FuzzyTerm.xml中不存在满足上述条 direction,satisfaction type); 件的模糊词，需要采用如下方法解决：假设[Y,Y2] 4)w←用户指定（或系统默认）的模糊查询谓 为模糊查询谓词指定的数值区间，则代表该模糊查 词 询谓词的隶属函数取值分别为 C:的重要程度； Y （1+入Y,,(1+)月 5)f(扩展程度(relaxation degree)null)then 6)C:ComputeMembershipFunctionl relaxde- 式中：入（入∈[0,1]）是阈值，入值越小，则该模糊查 gTee,10:,0）; 询谓词的模糊集支集与核的距离越小. 7)else 假设用户没有指定模糊查询谓词“SqFt between 130and200”的重要程度，此时需访问领域知识库 8)if(3 FuzzyTerm T=C,中的模糊词)（shape 文档NodeRelax.xml来获取该模糊查询谓词对应叶 (T)=MFS)then 节点的权重（在NodeRelax..xml文档中对应叶节点 9)CComputeMembershipFunction2(T,,); Sgft的权重为“nimp=medium”),利用权重函数g 10)else (0.5,S(s))=1-0.5(1-S(s)对隶属函数(5)进 11)if(ヨFuzzyTerm T)∧(core(T)=C,的数值区 行转换，得到转换后的隶属函数为 )A(shape(T)=MFS)then 0.5, s≤80ors≥250； 12)C+ComputeMembershipFunction2(T,w;,a); s-30 13)else 80<s<130; S(s)= 100 14)C+ComputeMembershipFunction3 (finterval, 1, 130≤s≤200； 0,a): 300-s 200<s<250 100 l5)return{C1,C2,…,C. 假设用户（或系统）设定的阈值为0.8，则模糊 算法1首先识别出模糊查询Q中的每个模糊 集S的0.8截集运算结果为 查询谓词C:,并根据C:对应的模糊关系和叶节点在 S(s)=-30 100 =0.8→s=110; 领域知识库中的扩展方向及叶节点取值对模糊查询 谓词的满足方式，确定该模糊查询谓词的隶属函数 s(s)=3003=0.8→5=220. 100 形状（第2）~3)步；然后，根据C:的权重、对应叶节 这样，模糊查询谓词“SqFt between130and200”可 点在领域知识库中的扩展程度以及相应参数值来构 转换成精确谓词“SqFt between110and220”. 建隶属函数：根据用户或系统提供的阈值，对隶属函 至此，引言中的模糊查询“：-/HouseDB/ 数进行α-截集运算，从而将C,转换成精确查询谓词

第6期 孟祥福，等：一种基于领域知识的XML数据模糊查询 ·531· C(第4)~14)步)；最后，将转换后得到的精确查询 8)advance (T); 谓词{C,C2,…,C.}合并返回（第15步）.利用转 9)if nextBegin (T)<nextBegin(Tmin))re- 换后的精确查询谓词替换最初的XPath查询中相应 turn Q; 的模糊查询谓词，最终得到精确的XPath查询. 10)else return nmin. 子函数：showSolutions(SN,SP) 4查询匹配与结果排序方法 /*假设路径查询q中从根到叶的n个查询结 4.1查询匹配方法 点的栈编号为1,2，…，n,假设通过数据index[l, 对于Xpath查询匹配方法，本文利用了文献 2,…,n]存储正在生成的匹配结果在各个栈中的位 [21]提出的基于TwigStack的查询结构匹配方法. 置，即index[]表示正在生成的匹配结果n元组中 函数：TwigStack（Q,T1,T2,…,Tn). 第i个数据结点在第i个栈中的位置.这里，1代表 输入：小查询Q,n个查询结点流T,T2,…,T 栈底位置，SN,SP分别表示当前正在处理栈的编号 (其中n代表查询Q的查询结点数量). 以及栈中当前正在处理数据结点的位置.* 输出：按从叶到根有序的小枝查询Q的匹配结 1)index[SN]SP; 果 2)f(SN==1)//当前正在处理根栈； 1)while(not end(Q))/如果查询Q没有结 3)output(index[n],…,index[1]);/输出 束，执行循环； 来自栈链的已经生成的匹配结果n元组 2)qact←-getNext(Q)；/取下一个XPath查询 4)else/递归调用 条件； 5)for (i=1 to index[SN].pointer)index[SN]. 3)f(isRoot（qact)or(not empty（Sparent pointer/表示index[SN]所指向结点在双亲栈中的 (Qa)))/如果qact是根或//qact父亲不为空； 位置 4)cleanStack（Sat,nextBegin(Tt);/将 6)showSolutions(SN-1,i). qact待匹配结点流中begin值最小的流放入V/ 4.2结果排序方法 Sqact; 模糊查询结果排序的基本思想是按结果元素对 5)moveStreamToStack (T,St,pointer to 模糊查询的满足程度进行排序.结果元素t对模糊 top (Sparent(qact))); 查询￠的满足程度定义为 6)f(!isRoot(qact)/当qact不是根时； 7）cleanStack（Sparent（qact),nextBegin Satisfaction(t,)=∑to:×hs.(u:).(6) (T));/下一个待查询结点入栈； 式中：k为交中包含的模糊查询谓词个数；®(：) 8)if(isLeaf(qact))/当qact是叶节点时； 9)showSolutions (qact,1); 代表元素t中的叶节点值：对模糊查询谓词C:的 10)pop (Se); 隶属度；w:代表模糊查询谓词C:在模糊查询条件中 11)else advance (T); 的重要程度.利用式(6)计算出的满足程度越高，表 12)mergeAllPathSolutions () 示该结果元素的排序分值越大，因此其排序位置就 子函数：cleanStack（S,actBegin) 越靠前 1)while not empty (S)and topEnd (S)< actBegin) 5实验测试与结果分析 2)pop(S). 5.1实验环境和测试数据 子函数：getNext(Q) 所有实验都是在配置为Pentium(R)Dual-Core 1)if (isLeaf (Q))return Q; CPUE6500@2.93GHz,2GB内存，160GB、7200rpm 2)for (every qi in children (Q)) 硬盘和Microsoft Windows XP操作系统下进行，使用 3)ni=getNext (q); SAX2解析XML文档，用Java和eclipse集成环境开 4)if(n:！=q:）return n:; 发实验系统.测试文档由BM XML data generator[a] 5)nmin minargni nextBegin (T); 产生，生成2个XML数据集，Car DB和House DB 6)nmax maxargni nextBegin (T); 的文档结构如图1所示) 7)while(nextEnd（T,）<nextBegin(Tr)）〉

·532. 智能系统学报 第7卷 CarDB 1)CarDB.xml数据集：从htp:/autos.yahoo.com/ UsedCar 网站随机抽取了200000条二手车信息，利用BM XML data generator生成CarDB..xml数据集，该数据 Make Price Color Mileage Engine Year Fcatures 集包括200000个UsedCar元素. 2)HouseDB数据集：从http:/homes.yahoo. Model Interior Exterior Trans Brakes Wheels com/网站随机抽取了250000条房产信息记录，利 (a)CarDB 用IBM XML data generator生成HouseDB.xml数据 HouseDB 集，该数据集包括250000个House元素. 5.2测试模糊查询效果 House 该实验以用户调查方式测试XML模糊查询方 法的查全率(recall)和准确率(precision).查全率是 City Ros Price Buildyear SqF Propery Details 指查询结果中的相关元素数占文档中相关元素总数 Bxdrooms BathroomsNeighborhood Schooldistrict Build Features Utilities 的百分比.准确率是指查询结果中的相关元素数占 Deck Patio Floor Covering 查询结果中总元素数的百分比.邀请了10位测试 者，每位测试者根据自己的需求和偏好，对CarDB (b)HouseDB 和HouseDB分别提出各1条模糊查询进行效果测 图1 CarDB和HouseDB的文档结构图 试.用户提出的测试模糊查询如表1所示， Fig.1 The schema of CarDB and House DB 表1 HouseDB和CarDB上的模糊测试查询 Table 1 Fuzzy test queries over HouseDB and CarDB ID Fuzzy XML queries over HouseDB Fuzzy XML queries over CarDB //House[Price at most 300 000] //UsedCar[Price between 10 000 and 20 000] Q1 [SgFt between 80 and 130]City ='Bellevue'] Make/[Model='Camry'][Mileage at most 50 000] //House[Price between 700 000 and 800 000] Q2 //UsedCar[Make='Ford'][Price at most 10 000] View ='Waterview'][SqFt at least 300] Year 'more or less recent'] //House[City ='Redmond'][Price ='medium'] //UsedCar[Price ='moderate'][Year ='Recent'] Q3 [SqFt between 150 and 200] Mileage at most 30 000] //House[Price ='moderate'][SqFt='more or less large']//UsedCar[Make ='BMW'][Price close to 30 000] 04 [BuildYear 'more or less recent'] Color/[Exterior ='white'] //House[City ='Seattle']SqFt ='large']Price at most //UsedCar[Make ='Nissian'][Price between 5 000 and Q5 700000] 10000][Mileage='more or less little'] //House[City='Seattle'][Price='more or less low'] //UsedCar[Make ='Dodge'][Price at most 15 000] Q6 Rooms/[Bedrooms =3] Year ='moderate'] Q7 //House[SqFt moderate][Bedrooms =5] Neighborhood&School info/[Neighborhood ='shoreline'] //UsedCar[Make 'Honda'][Price ='very low'] //House[Price ='moderate'][SqFt between 200 and 250] //UsedCar[Make ='Ferrari'][Price between 25 000 and 30 Q8 Neighborhood&School info/[Schooldistrict ='Central Seat- 000][Year='more or less Recent'] tle'] //House[City='Bellevue'][Bedrooms between 4 and 6]//UsedCar Make =Ford']Price =moderate'] Q9 [SgFt ='moderate'][Buildyear 'Recent'] Mileage ='little']Year 'Recent'] Q10 //House[City Seattle Price between 300 000 and 500 //UsedCar[Make="Tucson'] 000][SqFt='more or less large'] Price ='more or less low'][Engine =3.2]

第6期 孟祥福，等：一种基于领域知识的XML数据模糊查询 ·533· 对于CarDB和HouseDB上的每个测试查询Q:, 者从他们所标注的相关元素中选出最相关的前10 从原始数据集中为其生成一个小型数据集H,H:中 个元素.然后，分别在CarDB和HouseDB上执行排 包含了60个与该查询相关的和不相关的适量元素. 序方法为每条测试查询返回前10个元素.本文采用 然后，将所有测试查询和相应数据集提供给每个测试 式(7)所示的排序准确率评价排序质量： 者，让这些测试者从H:中标出与查询Q:相关的所有 R=Y2每 (7) 元素最后将系统返回的结果与用户标注的结果进行 对比来测试本文方法的查全率和准确率， 式中：：代表排序函数返回的元素列表中第i个元 本文的测试方法是从0~100%之间选取10个 素的得分（若该元素被标记为最相关的，则ī：取值 不同的查全率水平，然后计算对应的准确率（通过 为1，否则r:取值为0).可见，在R度量方法下，如 调整阈值，可以获得不同的查全率).也就是说，对 果本文排序方法返回的相关元素在列表中所处的位 于由本文方法返回的模糊查询结果，用户逐个检查 置越靠前，则它对R值的影响就越大，对于每个测 结果元素是否为用户标注的相关元素.如果是相关 试查询，取10个测试者根据式(7)计算得到的平均 元素，则对应该元素的准确率为100%，否则为0，最 排序准确率作为该查询结果的排序准确率.图3给 终该测试查询的准确率为所有结果元素对应准确率 出了在CarDB和HouseDB上对应于每个测试查询 的平均值.图2给出了从0~100%之间选取的10 的查询结果排序准确率.实验结果表明，本文提出的 个不同查全率水平下获得的对应准确率.图中显示 排序方法在2个数据集上的平均排序准确率分别达 的评估值是分别在CarDB和HouseDB上的10个测 到0.77和0.80 试查询的准确率的平均值， )B 0.6 0 02 -e-HouseDB CarDB 0.6 234 78910 0.5 测试查询 0.10.20.30.40.50.60.70.80.91.0 查全率 图3 HouseDB和CarDB上的排序准确率 图2 HouseDB和CarDB上的查全率和准确率 Fig.3 Ranking quality over HouseDB and CarDB Fig.2 Precision and recall over HouseDB and CarDB 5.4响应时间测试 从图2中可以看出，高准确率的获得是以查全 本文方法的执行过程主要包括模糊查询转换和 率的牺牲为代价的，反之亦然.但该实验主要反映的 结果排序处理2个阶段.第1阶段完成模糊查询谓 是，当本文方法的查全率为100%时，HouseDB和 词到精确查询谓词的转换，其时间复杂度为 CarDB上的平均准确率分别为71%和69%；当查全 O(mk),其中m代表模糊查询条件中的模糊查询谓 率为90%时，HouseDB和CarDB上的平均准确率均 词个数，k代表每个模糊查询谓词所涉及知识库文 为73%；当查全率为80%时，HouseDB和CarDB上 档中包含的不同元素个数的平均数.第2阶段包括 的平均准确率分别为78%和76%.由于用户在提交 结果元素的排序分值计算和排序处理2个部分，结 查询时可以根据个人偏好为查询谓词指定重要程 果元素的排序分值计算时间复杂度为O(n),n代表 度，因此返回的查询结果也就更能贴近用户需求和 结果元素个数；排序处理的时间复杂度为 偏好.也就是说，本文提出的模糊查询方法能够同时 O(nlog n),n代表结果元素个数.因此，第2阶段的 具有较高的查全率和准确率， 总体时间复杂度为O(nlog n).图4给出了本文方法 5.3测试结果排序质量 在2个数据集上不同结果元素个数下的响应时间. 该实验目的是测试结果排序方法的排序质量， 从图中可以看出，本文的响应时间随着查询结果元 为了观察不同测试查询下排序方法的质量，让测试 素个数的增加几乎呈线性增长趋势

.534 智能系统学报 第7卷 1010 Man,and Cybernetics,Part B:Cybernetics,1997,27 (4):714-721. 8 [9]MA Z M,YAN Li.Generalization of strategies for fuzzy query translation in classical relational databases[].Information and Software Technology,2007,49(2):172-180. [10]李言辉，徐宝文，陆建江.一般术语公理下的模糊描述逻 辑FALCN推理[J].软件学报，2008,19(3)：594604. --CarDB LI Yanhui,XU Baowen,LU Jianjiang.Reasoning with --HouseDB ×10 general terminological axioms in fuzzy description logic 10 20 25 FALCN[J].Joumal of Software,2008,19(3):594-604. 查询结果元素个数 [11]康达周，徐宝文，陆建江，等。支持模糊隶属度比较的 图4不同查询结果元素个数下的响应时间 扩展模糊描述逻辑[J].软件学报，2008,19(10)： 2498-2507. Fig.4 Response time of different number of elements KAN Dazhou,XU Baowen,LU Jianjiang,et al.Extended in query results fuzzy description logics with comparisons between fuzzy 6结束语 membership degrees[J].Journal of Software,2008,19 (10):2498-2507. 本文以模糊集理论为基础，提出了一种利用隶 [12]KANZA Y,SAGIV Y.Flexible queries over semi-struc- tured data[C]//Proceedings of the 20th ACM SIGACT- 属函数、领域知识和模糊集的-截集运算相结合实 SIGMOD Symposium on Principles of Database Systems. 现XML模糊查询和结果排序的方法.该方法不需要 Scottsdale,USA,2001:40-51. 改变传统XDBMS的结构和XML查询语言就能够 [13]王真星，顾宁，施伯乐。基于本体的半结构化数据的柔性 实现XML数据的模糊查询转换和结果排序处理，从 查询[J].计算机研究与发展，2003,40(11)：1571-1578. 而在很大程度上提高了用户与系统之间的交互能力. WANG Zhenxing,GU Ning,SHI Bole.An ontology-based flex- ible query method for semistructured data[J].Joumal of Com- 实验结果表明，本文方法能够同时具有较高的查询准 puter Research and Development,2003,40 (11):1571-1578. 确率和查全率，具有较好的查询结果排序质量，能够较 [14]POLYZOTIS N,GAROFALAKIS M,IOANNIDIS Y.Ap- 好地满足用户需求和偏好.未来工作将从查询结果排 proximate XML query answers [C]//Proceedings of the 序和知识库的自学习方面作进一步的完善. 2004 ACM SIGMOD Intemational Conference on Manage- ment of Data.Paris,France,2004:263-274. 参考文献： [15]MANDREOLI F,MARTOGLIA R,TIBERIO P.Approxi- mate query answering for a heterogeneous XML document [1]BRAY T.Extensible markup language (XML)1.0 CP/OL]. base[C]//Proceedings of the International Conference on [2011-03-18].http://www.w3.org/TR/REC-xml/. Web Information Systems Engineering.Brisbane,Austral- [2]TAHANI V.A comceptual framework for fuzzy querying ia,2004:337-351. processing:a step toward very intelligent databases systems [16]SPIEGEL J,PONTIKAKIS E D,BUDALAKOTI S,et al. [J].Information Processing Management,1997,13:289- AQAX:a system for approximate XML query answers 303. [C]//Proceedings of the 32nd International Conference on [3]ZADEH L A.Fuzzy sets J].Information and Control, Very Large Data Bases.Seoul,Korea,2006:1159-1162. 1965,8(3):338-353. [17]衡星辰，罩征，邵利平，等.基于两阶段查询重写的1 [4]BOSC P,PIVERT O.SQLf:a relational database language 近似查询算法[J.电子学报，2007,35(7)：127-1278. for fuzzy querying J].IEEE Transactions on Fuzzy Sys- HENG Xingchen,QIN Zheng,SHAO Liping,et al.Two- tem8,1995,3(1):1-17. phase query rewriting based approximate XML query algo- [5]BOSC P,PIVERT O.Extending SQL retrieval features for rithm [J].Chinese Joumal of Electronics,2007,35 (7): the handing of flexible queries[C]//Proceedings of Interna- 1271-1278. tional Conference on Fuzzy Information Engineering.New- [18]MA Z M,MENG X F.A knowledge-based approach for York,USA,1997:233-251. answering fuzzy queries over relational databases [C]/ [6]BOSC P,GALIBOURG M,HAMON G.Fuzzy querying Proceedings of the 12th International Conference on Knowl- with SQL:extensions and implementation aspects[J]. edge-based and Intelligent Information and Engineering Fuzzy Sets Systems,1988,28:333-349. Systems.Zagreb,Croatia,2008:623-630. [7]NAKAJIMA H,SOGOH T,ARAO M.Fuzzy database lan- [19]LARSEN H L.An approach to flexible information access guage and library:fuzzy extension to SQL[C]//Proceedings systems using soft computing[C]//Proceedings of the of the 1993 International Conference on Fatigue Science. 32nd Annual International Conference on System Sciences. Washington DC,USA,1993:477-482. Mai,LUSA,1999:6042. [8]CHEN S M,JONG W T.Fuzzy query translation for rela- [20]YAGER RR.Information fusion and weighted median ag- tional database systems[J].IEEE Transcations Systems, gregation[C]//Proceedings of the 5th International Work-