模糊查询（共7篇）
模糊查询 篇1
在数据库管理系统中,查询是一个很重要的内容。然而,在多数情况下人们不能准确知道作为查询条件的字段内容,如:某字段内容为“浙江省嘉兴市职业技术学院”,查询者可能只知道其简称“嘉兴学院”或“嘉职学院”。这时,为保证能查到满足条件的数据记录,只能进行模糊查询。下面从编程的角度谈谈在FoxPro 7.0中,实现模糊查询的方法。
1 简单的模糊查询
(1)利用比较操作符“=”进行模糊查询。先把SET EX-ACT的设置为OFF,这时“=”用于两个字符表达式之间作比较,其规则是“=”右边的字符逐个与“=”左边相同位置的字符进行比较,只要遇到其中一个字符不相等,或者“=”右边的字符表达式结束,比较操作就结束。所以,"abc"="abc","abc"="ab","ab_"="ab","ab"=""的比较结果均为逻辑真(.T.)。可见,这种方法的模糊性是不能令人满意的。
(2)利用“$”进行包含比较,其模糊查询的效果就比用“=”时好得多。这种方法是在“$”右边的字符表达式中查找“$”左边的字符表达式,若找到返回逻辑真(.T.),否则返回逻辑假(.F.)。用这种方法只要“$”左边字符表达式的每一个字符在“$”右边字符表达式中存在且位置不间断,查找就能成功。然而对于诸如前面提到的“嘉兴学院”或“嘉职学院”之类的简称,其查找结果为逻辑假(.F.)。
由此可见,直接利用“=”和“$”进行比较操作是不能太“模糊”的。
2 查询条件为缩略语或简称的模糊查询
缩略语或简称在地名、单位名称中使用非常广泛。通常,缩略语或简称是由全称中的某些排列位置不连续的字符组成的。因此,通过设置不同长度字符串进行比较的规则,或者利用包含比较符“$”,是不能对缩略语或简称进行模糊查询的。这时可以编写一个通用的自定义函数,将用户输入的查询条件(<字符串2>)与字符型字段变量(<字符串1>)进行逐字比较,如果<字符串2>是<字符串1>的缩略语或简称,则返回逻辑真(.T.);否则返回逻辑假(.F.),从而实现模糊查询。
2.1 设计思想
此函数必须是一个通用函数。为此,执行时可先接受两个参数──<字符串1>和<字符串2>。从<字符串2>的左边开始取其第一、二个字符X1,用AT()函数测试X1在<字符串1>中的位置S1,如果S1不为0,就将<字符串1>中包含X1以及左边部分的字符截掉,并取<字符串2>中的第三、四个字符X2,用AT()函数测试X2在<字符串1>的剩余部分中的位置S2,若S2不为0,就将<字符串1>的剩余部分中包含X2以及左边部分的字符截掉,直到将<字符串2>中的字符取完并在<字符串1>中测试完为止,最后本函数返回逻辑真(.T.)。在这个过程中只要有一次测试不成功(即Sn=0),则退出本函数并返回逻辑假(.F.)。因为一个汉字占两个ASCII字符,所以每次取二个相邻字符进行测试(让ZFBJ.PRG中的K=2)。这样做一是可以减少测试比较的次数,提高程序运行速度;二是当<字符串2>中含有数字、字母等半角字符时,可以减少满足条件的记录数目,提高查询的命中率。然而,若查询条件中含有英文缩写,则每次只能取一个ASCII字符进行测试(让ZFBJ.PRG中的K=1)。
2.2 使用举例
设内存变量m.field,其值为用户输入的用户名称的简称,如“嘉兴学院”,现在要在KTJBK.DBF中查询用户名称(字段名)为“浙江省嘉兴职业技术学院”,或为“嘉兴学院”,或为“嘉职学院”的全部记录,可以先将满足条件的记录拷贝到一临时数据库TEMP.DBF中,然后浏览,浏览完毕后删除临时数据库TEMP.DBF。其程序如下:
通过上面介绍的自定义函数实现了真正的模糊查询,然而令人遗憾的是它的速度表现总使人感到美中不足,幸好在FoxPro中引入了结构化查询语言SELECT-SQL。
3 利用FoxPro中SELECT-SQL语句的模糊查询
结构化查询语言SQL是FoxPro中值得骄傲的特色之一。利用SQL的SELECT语句可以非常方便、极其快速地进行十分复杂的查询操作。特别值得推荐的是SELECT-SQL语句中的WHERE参数支持通配符“%”和“_”。因此,对于查询条件为缩略语或简称的情况,可以非常简单地实现真正的模糊查询。这里,百分符号“%”代表0个或0个以上的任意字符,下划线符号“_”代表1个任意字符,它们只能与运算符LIKE搭配使用。
设内存变量m.field,其值为用户输入的用户名称的简称,如“嘉职学院”,现在要在KTJBK.DBF中查询用户名称(字段名)为“浙江省嘉兴职业技术学院”,或为“嘉兴学院”,或为“嘉职学院”的全部记录,可以用下面的一段程序实现:
4 结语
本程序运行时,先将m.field="嘉职学院"中插入五个通配符“%”,得到mc_cxtj="%嘉%职%学%院%"。然后利用SQL的SELECT语句,从数据库KTJBK.DBF中选出字段变量“用户名称”符合"%嘉%职%学%院%"格式的所有记录,输出到一个虚拟临时数据库TEMP.DBF中。
摘要：主要讲解在数据库管理系统中实现模糊查询的方法与技巧,提供了能实现真正模糊查询的两个通用函数的源程序,分析了结构化查询语言SQL中的通配符的使用方法。
关键词：VFP,模糊查询,SELECT-SQL
参考文献
[1]郑刚.VFP实效编程百例.(第二版),北京:人民邮电出版社,2004.
[2]尹立宏.VFP7.0数据库开发典型实例.北京:电子工业出版社,2002.
模糊查询 篇2
在使用Power Builder (以下简称PB) 开发的MIS系统中, 一般都会使用数据窗口控件来提高开发效率。而模糊查询是现在MIS系统不可缺少的查询方式。
2 设计思路及原理
在PB中数据窗口显示的数据可通过修改其SQLSELECT语句来选择, 本文的查询方法即通过修改数据窗口的SELECT语句来实现。
实现原理如下:首先获取数据窗口的所有列名;然后在一个新窗口中设置查询的条件;最后修改数据窗口的SQLSELECT语句实现查询。
3 实现
条件:数据库及数据源已建立好 (本文采用ODBC数据源, 数据源名称为“test”, 数据库用SQLserver2000建立。数据库中建立三个表:test, 存放我们需查询的信息;columnname, 存放从数据窗口中获取的列名, 仅有一列, 列名为“列名”;selecttable, 形成设置查询条件的数据窗口, 有四列, 列名分别为“列名”, “操作符”, “值”, “逻辑运算符”, 本表不存放任何信息。
1) 新建一Application, 取名为:te s t。
2) 新建数据窗口d_te s t, 显示风格为Grid, 采用Quick Se le ct数据源, 选择表test的所有列建立数据窗口。
3) 新建数据窗口d_colnam e, 显示风格为Grid, 采用Quick Se le ct数据源, 选择表colum nnam e的所有列建立数据窗口。
4) 新建数据窗口d_s qls e le ct, 显示风格为Grid, 采用Quick Se le ct数据源, 选择表s e le cttable的所有列建立数据窗口。设置列的Edit Style Type如下:列“列名”为“DropDow nDW”, DataWindow为“d_colnam e”, Dis play Colum n和Data Colum n) 均为“列名”;列“操作符”为“DropDownListBox”, Code Table如图1所示;列“值”为“Edit”;列“逻辑运算符”为“DropDownListBox”, Code Table如图2所示
5) 新建一窗口, 取名为:w_m ain。
6) 在窗口w_m ain中创建一dataw indow control, 取名为:dw_te s t, DataObje ct属性设置为d_te s t;创建命令按钮控件cb_find和cb_e xit, 属性cb_find.te xt为“查找”, cb_e xit.te xt为“退出”。
7) 新建一窗口, 取名为:w_cxtj, 在窗口w_cxtj中创建一dataw indow control, 取名为:dw_s e le ct, DataObje ct属性设置为d_s qls e le ct;创建命令按钮控件cb_ok和cb_cance l, 属性cb_ok.te xt为“确定”, cb_cance l.te xt为“取消”。
8) 为窗口w_m ain的ope n事件编写代码如下:
dw_te s t.Se tTrans Obje ct (SQLCA)
dw_te s t.Re trie ve ()
9) 为cb_find的clicke d事件编写代码如下:
11) 为数据窗口控件dw_s e le ct的ite m change d事件编写代码如下:
12) 为cb_ok的clicke d事件编写代码如下:
4 结束语
本文的程序在PB8.0下调试通过, 在实现过程中表selectable可以不建, 而采用外部数据源建立数据窗口d_sqlselect。数据窗口d_te s t各列的Tab Orde r不能设置为“0”, 否则不能获取各列的列名。
参考文献
数据库模糊查询技术应用 篇3
1 模糊集合理论
1.1 模糊集合
所谓在论域U上的一个模糊子集A是指:∀u∈U,都有μA(u)∈[0,1]与之相对应,并且称为u属于模糊子集A的隶属度。即由映射:
确定论域U的一个模糊子集A。
μA(u)=1,表示u完全属于A;μA(u)=0,表示u完全不属于A;0<μA(u)<1,表示u隶属于A的程度。
设A为论域U上的模糊集合,∀α∈[0,1],Aα={u∈U|fA(u)≥α}⊆U,称模糊集合A的α截集,称α为置信度,即对于普通集合Aα有∀u∈U当A(u)≥α时,说明在α水平下u属于模糊集合A,记为u∈Aα,反之u∉Aα。
1.2 隶属函数
隶属函数是对模糊概念的定量描述,正确地确定隶属函数,是运用模糊集合理论解决实际问题的基础。隶属函数的确定过程允许存在一定的主观意识,可以根据实际统计数据特征从几种典型模糊分布曲线中选择最为贴近的一种作为隶属函数,经过实践效果的检验进行了调整,即通过“学习”进行修改和完善,以得到更为确实的隶属函数形式。典型的模糊分布有阶梯型、指数型、正态型、线型、幂函数型、正弦型等。
1.3 语言变量
1971年Zadeh提出模糊语义定量理论并定义了“语言变量”的概念,其算子的一般数学描述为:
L=(U,T,E,N)
其中:U是论域,即语言主体的全体;T是语言值的模糊集合;E是构成语言的所有字母和符号序列的集合;N是E对U的模糊关系。对于T中值x的语义是U上的模糊子集M(x),则U中的元素y对M(x)的隶属度可表示为:μM(x)(y)=μN(x,y)。例如:设论域U=[1,100]是学生成绩集合,T为成绩的模糊集合,E={优秀,良好,中等,一般,较差}。
1.4 语气算子
在模糊理论中将自然语言中的如“比较”、“非常”、“稍微”等词看作是一种算子,称为语气算子Hλ,从程度上来限制模糊语义,在不同等级上改变模糊语义的隶属度,如模糊语义“高”可表示为“非常高”、“比较高”,“有点高”等。语气算子是一个变换,即:HλA(x)=A(x)λ,当λ>1时称Hλ为集中化算子,λ<1时称Hλ为散漫化算子,一般将H4代表“极”,H2代表“很”,H1.25表示“相当”,H0.75代表“比较”,H0.5代表“有点”,H0.25代表“稍微有点”。
1.5 模糊化算子
自然语言中常将“大约”、“近乎”、“差不多”等具有模糊意义的词放在一个精确词或语言变量之前,表示一个模糊的范围,如“某学生计算机成绩大约80分左右”,称为F化算子。可实现对精确语义的模糊化和模糊语义的模糊化。其中对于模糊语义的模糊化算子的一般形式可表示为:
对∀x∈U,
其中A是模糊集合,μA(y)是y对A的隶属度,E是U上的相似模糊关系,相似函数μE(x,y)表示为:
式中δ>0为参数。
2 模糊SQL
SQL(Structured Query Language)作为现在大多数系统都支持的语言,已经成为标准的数据库语言。而关系数据库也是使用最为广泛数据库形式,那么针对关系数据库使用SQL并对其进行模糊扩展也就具有重要意义。对数据库查询进行模糊扩展,模糊SQL一般形式可以表示为:
其中T是一个精确或模糊关系;Ci表示T上的属性;fc是一个模糊条件,可以包含模糊关系运算符(如“约等于≈”、“远远大于>>”等)、模糊谓词(is)及连接词(AND、OR);α∈[0,1]称为阈值,由于查询条件是模糊的,因此查询结果也是一个模糊集合,集合中每个结果对于查询条件fc的满足程度即匹配度不同,设置阈值α的作用是使查询结果中匹配度大于α的记录作为结果输出。
2.1 简单模糊查询
例1:存在一个学生关系(student)如表1。
在表1中查找“计算机成绩较好的学生”,模糊SQL可表示为:
SELECT姓名,计算机
FROM student
WHERE计算机is good
WITH 0.5
对于关系上的元组,计算属性“计算机”关于“”的匹配度,隶属函数可表示为:
计算关系student中每个元组的“计算机”属性值关于模糊条件对应隶属函数的匹配度见表2。
最后根据阈值α得到结果集合中匹配度大于等于0.5的有第2、3、7、8四个元组。
2.2 复合条件模糊查询
查询条件中可以使用AND、OR等连接词交多个查询条件组合形成复合查询条件,如在学生关系中“查找英语成绩较差但总分较高的学生”,模糊SQL表示为:
SELECT姓名,英语,总分
FROM student
WHERE英语is fail and总分is good
复合查询条件中涉及关系中的多个属性,这时就需要分别计算每个元组的相应属性值针对模糊条件的匹配度,进而计算综合匹配度,当连接词分别为AND和OR时综合匹配度的计算方法为:
其中mi表示元组R的第i个属性值对于模糊项隶属函数的匹配度。
2.3 模糊查询转换为精确查询
上述简单模糊查询和复合模糊查询在对关系数据库进行操作时需要对表中所有记录进行计算,表中记录多时会影响查询效率,为减少计算量可以在查询前将模糊条件转换为精确条件,将大大提高查询效率。将模糊条件转换为精确条件可以使用隶属函数及α截集求得模糊条件中属性值的区间,那么精确查询条件也就得到。如例1“计算机成绩较好的学生”中的“较好”可根据隶属函数和α求得其对应值区间为,则模糊查询可转化为:
SELECT姓名,计算机
FROM student
WHERE计算机BETWEEN 75 AND 95
在关系student中查询结果为2、3、7、8四个元组,同例1结果相同,接下来对四个元组计算匹配度,得到最终结果,结果仍与例1相同,但效率却比例1要高。
3 结束语
在数据库模糊查询中,将自然语言中模糊概念与数据库中的精确概念建立了联系,从而使查询语言得到了扩展,本文针对这一理论介绍了简单模糊查询及复合模糊查询的处理方法并做了验证,同时介绍了模糊查询转换为精确查询的方法。以上查询方法还可以扩展到多表查询、子查询等,而关系中的属性值的隶属函数和模糊中的阈值也可根据实际需要进行调整。
摘要：该文介绍了模糊集合理论相关知识及其在关系数据库查询中的应用,针对SQL语言的SELECT语句进行了模糊扩展。分析了简单模糊查询、复合模糊查询、将模糊查询转换为精确查询的方法并通过实例进行了验证。
关键词：关系数据库,模糊查询,隶属函数,阈值,匹配度
参考文献
[1]陈逸菲.基于模糊理论的关系数据库查询技术研究[D].南京:南京信息工程大学,2005.
[2]杨纶标,高英仪.模糊数学原理及应用[M].广州:华南理工大学出版社,2004.
[3]申玉静,周爱华.基于模糊数据库的数据查询设计[J].北京:计算机教育,2007(12):126-128.
基于位置隐私保护的模糊查询方法 篇4
近年来, 基于位置的服务 (location-based services, 简称LBS[1]) 不断发展, 用以实现物联网中的实时、快速、可扩展的物体位置搜索。但是, 由于用户在使用LBS服务时, 需要向LBS服务器提供自身的位置信息, 而LBS服务器又不是绝对可靠的, 有可能将收集的用户位置信息泄露给攻击者, 所以在使用LBS服务的同时, 服务泄露或非法使用用户位置信息的情况也接踵而来, 基于位置的服务给用户的位置隐私带来了极大的威胁。
在LBS服务中, 主要有三大目标:你在哪里 (空间信息) 、你和谁在一起 (社会信息) 、谁附近有什么资源 (信息查询) 。本文主要解决“谁附近有什么资源”的问题, 首先要明确两个参数:“谁”和“什么”, “谁”代表实体位置, “什么”代表服务请求。
在“谁附近有什么”的信息查询服务过程中, 如何在保护“谁”的基础上提供相对可靠的服务, 将是本文的研究重点。针对这一问题, 本文提出一种基于位置隐私保护的模糊查询方法, 在模糊位置信息的基础上提供相对可靠的服务, 并于一定程度上实现了位置隐私保护和位置服务质量之间的平衡。
1位置隐私保护服务结构
由于LBS服务器是不可信任的, 因此需要在用户和LBS服务器之间添加一个可信任的模糊服务器, 该模糊服务器在用户和LBS服务器之间可起到防火墙的作用。由用户、模糊服务器和LBS服务器所组成的位置隐私保护服务结构[2]如图1所示。
该结构中模糊服务器工作如下:
(1) 收集用户发送来的位置服务请求信息, 将这些信息存储在服务器中;
(2) 对用户发送过来的位置服务请求信息中的真实位置信息进行模糊, 用空间模糊集进行代替, 从而保护实体位置信息, 最后将模糊过后的位置服务请求发送给第三方的LBS提供商的位置服务器;
(3) 对第三方LBS提供商的位置服务器发回的基于模糊集的服务应答结果集进行接收, 并根据用户需求对应答结果集进行过滤, 找到相对合理的应答结果, 再将此结果发送给用户。
2基于k-匿名的模糊集构造
根据位置隐私保护服务结构的要求, 首先需要对用户真实位置信息进行模糊。本文采用已有的k-匿名技术[3]来构造实体模糊集, 以达到模糊效果。
k-匿名通过概括和隐匿技术[4], 发布精度较低的数据, 使得每条记录至少与数据表中其他k-1条记录具有完全相同的标识属性值, 从而减少链接攻击所导致的隐私泄露。k-匿名技术可以保证每一个体的敏感属性隐藏在规模为k的群体中, 这样, 个体能够得到确认的几率将不会超过1/k。目前的k-匿名技术主要是利用两种方法来实现匿名:泛化[5]和隐匿技术。本文采用Datafly泛化算法[6], 根据k-匿名的要求, 计算得到每个属性出现的概率, 然后对不满足要求的属性做泛化处理, 直到该属性满足k-匿名的要求为止, 从而得到规模为k的模糊集。
3基于位置隐私保护的模糊查询方法
利用K-匿名算法构造完实体位置模糊集之后, LBS服务器需要针对整个模糊集来提供“附近有什么”的查询服务, 而如何在模糊集基础上提供尽可能良好的服务即成为问题关键。针对这一问题, 本文提出一种基于位置隐私保护的模糊查询方法—FCM方法, 该方法可以嵌入到LBS服务器当中, 通过计算模糊集到附近服务请求点的最短路径长度来提供相对可靠的查询服务, 使得在保护实体真实位置的同时, 又提供了较为良好的服务。
FCM计算方法是针对模糊集进行计算的, 传统Dijkstra算法[7]是针对点进行计算, 与其有相似之处, 所以本文FCM计算方法借鉴了传统的Dijkstra算法, 但是由于Dijkstra算法以起点为中心向外层层扩展, 需要遍历计算所有节点, 过于繁琐。在实际应用当中, 面对大量节点, 使用Dijkstra算法查找最短路径时需耗费大量的时间进行数据的比较, 搜索速度较慢, 效率较低, FCM计算方法对此进行了改进, 以降低搜索复杂程度。
由于FCM需要计算模糊集合到服务请求点的最短路径距离, 而对于模糊集合O中的不同点, 到附近服务点 (如附近餐厅) 的最短路径长度也是不一样的, 如何在众多的附近服务点中选择合适的服务点返回给用户就成为求解的关键, 考虑到服务质量问题, 需要首先对模糊集进行划分。
3.1模糊集划分
对模糊集O进行划分, 需要构建对于请求点集合Q在关系δ上的划分△。
关系δ定义如下:δ∈O*O, 对任意o1, o2∈O, o1δo2当且仅当min (o1) =min (o2) 。o1δo2可以理解为对于某个请求来说, o1和o2的最短路径距离是相等的。其中函数min描述如下:min:O→Q, min (o) →q1表示对任意o∈O, 满足d (o, q1)
根据关系δ, 可以得到划分△:
(1) 计算实体位置模糊集O中各点到请求集合Q的最短路径距离, 得到
(2) 遍历所有的序对, 将终点相同的起点归为一类;
(3) 得到划分结果△, 其中o∈[o], 对任意o∈O。3.2 FCM计算方法
在划分的基础上, FCM可以在众多附近服务点中选择最适合的点返回给用户, 由此使得服务的可靠性有所提升。
为了便于研究, 如图2所示, 设置一个虚拟点s, 将s和请求集合Q中的点以权重为0.0的边连接起来。
在实际计算中, 可以先计算点s到模糊集O中各点的最短路径距离, 然后将最短路径逆序, 转化为从集合O中各点到虚拟点s的最短路径距离, 则逆序后的最短路径中倒数第二个点必然是集合Q中的点。
FCM计算方法描述如下:
FCM方法中3-10步骤计算虚拟点s到模糊集O中各点的最短路径距离, 11-12步骤将模糊集O按照关系δ进行划分, 13-19步骤在请求集合Q中选择合适的点返回, 如果划分O/δ只有一个, 那么必然是O (line 13) , 说明任意o1, o2∈O, o1δo2, O中任何一个点均可代替实体位置, 选择q=min (o) (line 14) 成立的点返回。当存在多个划分结果时, 如果用户同意标识自己所在的分类[l]属于O/δ (line 16) , 那么实体所在类中的任意一点可以代替用户位置, 选择t=min (o) 成立的点返回 (line 17) 。如果实体不同意标识自己的位置, 则返回面积最大类中的任意一点来代替实体位置, 即q=min (o) (line 19) 。在19步中, Ci=Area ([oi]) /Area ([O]) 表示q为合适请求点的可能性, 由于对于模糊集来说, Area ([O]) 是恒定的, 只需要计算Area ([oi]) 来决定Ci的大小, Area ([oi]) 表示划分[oi]中对应q点的点的数量。
4仿真实验与结果分析
基于位置隐私保护的模糊查询方法中需要用到FCM算法, 该方法在不确定条件下为用户提供尽可能可靠的服务, 并利用最短路径长度来作为衡量的标准。通过与传统算法作对比, 来验证FCM的运算效率和实用性。
4.1 FCM计算方法的实现
设图G= (V, E) 中有68个点, 580条边, 设置模糊测试集如下:Q1={14, 21, 22, 23, 24, 27, 29, 30, 32, 35}, Q2={50, 52, 54, 56, 57, 58, 59, 63}, Q3={8, 10, 11, 15, 18, 19, 24, 30, 32, 33, 34, 36, 37, 43, 47, 53, 55, 62, 65, 68}设置请求集合为:Q1={67, 38, 24, 65, 35, 62, 31, 27, 14, 11, 5, 59}。其中, Q1和Q2为相对聚集的点, Q3为随机产生的点, 较为分散。在图中加入虚拟点s, 由于Q中存在12个点, 那么整个图形变为69个点, 592条边。根据设定的边权值矩阵来计算s到O1, O2, O3中各点的最短路径。结果如表1, 表2, 表3所示。
从结果中可以看出, 集合O1中有80%的点对应请求集合中27号点, 服务器返回27号请求点给用户;集合O2中有37.5%的点对应着请求集合中的59号点, 有50%的点对应着请求集合中的65号点, 所以服务器可以返回59号和65号请求点。
由于O1和O2相对较为集中, 点数量较少, 为了能够更全面地展示算法的性能, 先对O3集合进行测试 (O3中点数量较多且为离散随机点) 。
结果表明, 即便在点数量较多和随机情况下, 14和27号请求点依然可以作为结果返回给用户, 表明在点数量更大, 随机比例更高的情况下FCM算法依然可以保持一定有效性。
综合以上测试结果, 表明算法可以在不确定条件下有效返回相关结果, 由此达到预期目标。
4.2 FCM算法与传统算法的比较
建立5张图G= (V, E) , 分别用Dijkstra算法、遗传算法[8]和FCM方法计算最短路径, 统计各自的搜索速度, 如图3所示。
由图3可以看出, 当节点数为16时, Dijkstra算法、遗传算法和FCM方法计算最短路径所花费的时间几乎相同, 当节点个数为32时, 三种方法的响应时间开始有略微差别, 当节点数为48时, 三种方法开始有明显差别, 并且随着节点数的增多, 三种方法的响应时间都有大幅提升, 但是同等条件下, Dijkstra算法和遗传算法的响应时间的上升幅度明显大于FCM方法, 而且这种差距将随节点数的增多而变得更加明显。由此可以得出如下结论:当节点数较少时, 三种方法计算最短路径的响应时间差别不大;当节点数目较多时, FCM方法的响应时间更少, 具有更好的性能。
5结束语
本文基于位置隐私保护服务结构, 实现了在不确定条件下为用户提供相对可靠的位置隐私保护服务请求。在模糊集基础上, 利用最短路径长度来作为衡量的标准, 解决了在不确定条件下“谁附近有什么”的查询问题, 其中“谁”代表实体位置模糊集, 然后, 本文提出一种基于位置隐私保护的模糊查询方法—FCM, 使得在保护了用户位置信息之后, 仍旧可以提供较为可靠的服务, 实现了位置隐私保护和服务质量的有效平衡。最后, 经过实验验证, FCM方法在一定程度节省了存储空间, 提高了运行效率, 具有一定实用价值。
参考文献
[1]ASHTON K.That‘Internet of Things’Thing[C]//RFID Journal, 2009.
[2]XIAO Z, MENG X, XU J.Quality-aware privacy protection for location-based services[C]//Proceedings of the International Conference on Database Systems for Advanced Applications.Bangkok.Thailand, 2007:113-120.
[3]SAMARATI P, SWEENEY L.Protecting privacy when disclosing information:k-anonymity and its enforcement through generalization and suppression[J].International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 2002, 10 (5) :557-570.
[4]MACHANAVAJJHALA A, GEHRKE J, KIFER D.l-diversity:Privacy beyond K-Anonymity[C]//Proceedings of the 22ndInternational Conference on Data Engineering Atlanta.GA.USA:ACM Press, 2006:3-8.
[5]ANCO H, LEON W.U-argus and t-argus:software for statistical disclosure control[C]//Proceedings of the Third International Seminar.Statistical Confidentiality, 1996:156-163.
[6]SWEENEY L.Computational disclosure control:a primer on data privacy protection[D].PhD dissertation, :Computer Science Dept.Massachusetts Institute of Technology, 2001.
[7]ZHANG Yonglong.Dijkstra shortest path algorithm optimization[J].Journal of nanchang institute, 2005, 1 (2) :23-25.
模糊查询 篇5
1 问题定义
定义1、假设D是一个数据库, 包含x个文本型及数值型属性A={A1, A2, !, Am}, n条元组T={T1, T2, !, Tn}, 设Q为D上的一个模糊查询, 如果数据库D中存有海量数据信息, 那么查询后将得到很多足该查询要求的元组, 这种情况即为模糊查询下多查询结果问题。
2 隶属度排序
(1) 属性权重系数。
一个关系中所有属性都是不一样的, 根据对于用户的重要程度, 有的划为重要属性, 有的划为次要属性。本文描述的问题则是由属性权重系数来衡量属性的重要程度的。如果在历史查询记录里, 用户在某些属性上查询的次数越多, 则证明该属性在关系中比较重要, 那么就应该分配比较高的权重系数。反之, 则只能分配较低的权重系数。因此, 根据历史记录里某属性上查询次数来确定权重系数。设F (Ai) 是历史查询记录里在属性Ai上查询的次数, N是查询总数, 那么, Ai的权重系数确定方法如下:
(2) 隶属度排序。
元组对模糊查询的隶属度越高, 那么排序的分值越大。例如:模糊查询“City=Kirkland and View=Oceanv iew and Price close to 3500”, 查询后得到结果, 元组中Price上的属性值都在3400~3600范围内, 计算出每个元组的隶属度, 进而对模糊查询的结果进行自动排序。但是, 经过隶属度排序之后, 查询得到的结果会被划分为许多具有高低不同隶属度的元组集合。这些集合里还会存在具有相同隶属度的元组, 因此还有进一步区分每个集合中隶属度相同的元组。
3 实验分析
(1) 实验环境。
实验数据采用某房地产销售数据库, 选择seattle城市, 经模糊查询后, 元组中约有6万条查询结果, 历史记录中包含200多条指定里几个属性的查询, 在原始数据群里提取5个测试数据集, 把每个测试集大小定为50条元组, 利用5个查询测试条件。每个测试条件Qi对应数据集Hi, 其中包含与Qi相关和无关的元组集合。
(2) 测试排序质量。
由于没有具体的排序质量评估标准, 因此只能以用户对查询结果排序的满意程度来大体的评估排序质量。在上述实验环境下, 对于测试条件Qi, 从Hi中选取与查询条件最为贴合的10个元组进行排序, 在此基础上应用DPR, PR和QFIDF三种排序方法, 比较排序质量。
模糊查询最后是根据阈值和隶属函数将模糊条件变为精确数值区间的, 因此变化厚度查询条件再作为PR和QFIDF方法的查询条件, 从而不论是准确查询还是模糊查询都能得到同样的结果, 最后评估其模糊查询后的排序质量, 对比结果如图1所示。
从图示对比结果来看, DPR排序方法的排序质量较高, PR、QFIDF两种方法排序质量较低。
假定不考虑模糊查询的情况下, 也不考虑隶属度排序对于三种方法排序质量的影响, 只在精确查询的情况下, 对比这三种排序算法的排序质量, 其对比结果如图2所示。
从图示对比结果来看, 在不考虑模糊查询的情况下, 也不考虑隶属度排序对于三种方法排序质量的影响, DPR方法与其两种排序方法相比, 在排序质量上分别提高了约2%~10%, 很明显, 要优于QFIDF排序方法。因此, 可以得出结论, 无论是在模糊查询结果排序方面, 还是在精确查询结果排序方面, DPR排序算法相比较PR和QFIDF两种排序方法, 有着较为明显的优越性。
4 结语
本文根据多年的计算机数据库技术经验, 及参阅了大量的资料和有效数据之后, 对于数据库模糊查询下多结果的自动排序方法基于模糊集理论, 提出了隶属度排序方法。基于PIR改进模型及历史查询记录等来多元化的分析元组中被查询的指定属性值和未指定的属性值他们之间的关联程度, 提出了改了模型排序方法。两种方法综合使用成为了DPR排序方法。经过实验, 数据表明, 对于数据库模糊查询结果的自动排序, DPR排序方法有着较高的排序质量。
参考文献
[1]孟祥福, 马宗民, 严丽.数据库模糊查询结果自动排序方法[J].东北大学学报 (自然科学版) , 2008 (7) .
模糊查询 篇6
关键词：数据库,SQL Server,模糊查询,通配符,递进法,枚举法
0、引言
数据库信息查询是任何通用数据库管理系统的必备的主要功能之一, 也是开发成功与否的重要组成部分。在开发数据库应用时, 应该容许用户按照多种方式对数据库的任意字段进行组合来查询信息。如何设计灵活、方便、高效实用的查询系统一直是众多开发者所关注的问题。本文在SQL Server的实践应用中总结出一种行之有效的方法, 即多条件模糊匹配查询, 可将该方法应用于B/S、C/S模式的系统中的搜索引擎的构建。
1、单条件模糊匹配查询
在进行数据库查询时, 有完整查询和模糊查询之分。一般模糊查询语句如下:
SELECT字段FROM表WHERE某字段Like条件
其中关于条件, SQL提供了四种匹配模式:
%:表示任意0个或多个字符。可匹配任意类型和长度的字符。
_:表示任意单个字符。匹配单个任意字符, 它常用来限制表达式的字符长度语句:
[]:表示括号内所列字符中的一个 (类似正则表达式) 。指定一个字符、字符串或范围, 要求所匹配对象为它们中的任一个。
[^]:表示不在括号所列之内的单个字符。其取值和[]相同, 但它要求所匹配对象为指定字符以外的任一个字符。
在此处要实现搜索如"姓名"、"地址"之类的字段的模糊查询, 应该正确巧妙地使用"%"。比如要根据输入的部分姓名来查找学生的基本信息, 如查找"张小明", 可以输入"张"、"小"、"明"、"张明"、"小明"等等。这里输入的部分姓名可以多种多样, 一一分析不同的情况, 如输入"张"、"小"、"明"这样的单字的搜索条件的, 我们很容易就可以写出其SQL语句:如SELECT*FROM users WHERE username LIKE'%明%';但是如果用户输入"张明"、"小明", 以上的语句就不再符合条件了, 正确应该是SELECT*FROM users WHERE username LIKE'%张%明%'和SELECT*FROM users WHERE username LIKE'%小%明%'。
综合以上的分析, 我们需要将用户输入的查询关键词逐个字符进行遍历, 同时为了满足模糊查询, 在每个字符之后加入通配符"%", 其流程如下图所示:
SQL源程序如下:
--@Partial Name存放输入的部分姓名
DECLARE@Search Condition varchar (200) , @Partial Name varchar (200)
如输入"张明" (即@Partial Name值为张明) , 即可搜索出同时包含"张"和"明"两个字的记录, 如表1所示:
2、多条件搜索
一般来讲, 有两种方法进行多条件搜索:枚举法和递进法。
2.1 枚举法
枚举法思路较简单一一判断条件是否为空, 再按非空条件搜索, 同时可以利用真值表技术来对付条件极多的情况。
采用枚举法的SQL源程序如下:
理解上述程序时, 着重琢磨核心部分, 4组语句一一对应了2个搜索框中的4种状态, 如表2所示:
如果增加两个搜索条件 (增加性别, 电子邮件) , 搜索的状态组合为24种, 需要16组语句。
从分析中我们可以看出, 搜索条件不太多时 (n<=3) , 适合使用枚举法, 因为枚举法的思路非常简单。而当条件增多时, 如有4个条件时就要写16组语句。很明显, 当条件增多以后, 枚举法的实现语句呈指数增长, 实现难度加大, 效率较低。
2.2 递进法
与枚举法相比它们只有核心部分不同, 递进法的搜索核心, 依次判断条件为空否, 非空则将其加入搜索条件。
如前文所述, 当有4个条件时, 采用递进法的SQL源程序如下:
--递进法的搜索核心, 依次判断条件为空否, 非空则将其加入搜索条件
递进法是一个明智的算法, 单从语句的长短就可以看出来了。这个算法的难点和精髓就在字符串连接符"+"以及设计"1=1"的条件。首先得先设计"1=1"的条件, 防止所有的搜索条件均为空的情况。其次你应该清楚"+"在SQL中就是一个字符串连接符, 把该符号左右的字符拼接在一起。当num不为空, se@Search Condition=@Search Condition+'and num like'''+@snum+'''';接下来name不为空时, set@Search Condition=@Search Condition+'and name like'''+@sname+'''';以此类推就可以推广到n个条件的搜索。当然当搜索条件皆为空时, 因为设计了"1=1"这个衡成立的条件, 将选择表中的所有记录。
由上分析可看出, 当查询条件增加时, 递进法的实现语句增线性递增;无论从程序的效率还是可实现性方面, 递进法明显优于枚举法。故本文使用递进法的多条件搜索结合单条件查询实现多条件模糊匹配查询。
3、多条件模糊查询的实现
综合单条件模糊查询、多条件搜索的方法, 即可实现多条件模糊查询。但是这里应该注意根据现实生活的情况, 性别字段就不需要使用like关键字。
4、在Web应用中的改进
上述方法可用于C/S系统和B/S系统中实现搜索引擎, 但是在B/S系统应用中还存在缺陷, 问题主要在于通配符%。一方面是因为人们平时习惯把*作为通配符, 另一方面%若出现在超链接中, 通过request获取时%将被"吃"掉, 如下:
在IE中浏览test.htm时点击超链接, 显示为:Testthenum。可见%直接被超链接忽略掉了。怎么才能解决这个问题呢?很简单, 我们做点小小的手脚--偷梁换柱。
将以下代码加在搜索核心之前:
将以下代码加在搜索核心之后:
在我们来分析一下这些语句。replace () 是字符串替换函数, replace (name, "*", "%") 就是将name中所有的*换成%。也就是说, 我们把3个条件中凡是出现的*都替换为%, 这样一来前3句就将通配符改成*了。而后3句就可以防止%被"吃"掉。所有问题就迎刃而解了吧。
5、结论
本文讨论的是基于SQL Server的多条件模糊匹配查询, 在查询方法的设计当中, 当要搜索如"姓名"、"地址"之类的字段时, 利用like并巧妙使用"%"来产生模糊查询。经过算法比较, 采用递进法来构建查询使用的SQL语句。此外, 还在WEB应用中改进由于通配符造成的缺陷。通过这些方法为数据库管理信息系统提供灵活、方便、有效的数据查询方法, 从而构建高效使用的搜索引擎。
参考文献
[1]周泓, 徐小良, 汪乐宇.基于模糊算法的数据库查询工具的设计[J].计算机应用研究, 2001, (5) :15～17
[2]朱蓉.基于模糊理论的查询技术研究[J].计算机应用研究, 2003, (5) :8～10, 29
[3]王佳宜, 杨路明, 谢东, 等.关系数据库上关键词的数字属性模糊查询研究[C].全国第18届计算机技术与应用 (CACIS) 学术会议论文集 (上册) , 2007:650～655
[4]张森, 韦明.数据库的模糊查询技术[J].电子与自动化, 2000, (5) :23～24
[5]张新华, 朱跃龙, 梁正和, 基于数据字典的通用动态查询系统设计与实现[J].计算机与现代化, 2006 (4)
[6]何珍文, 吴冲龙, 等.数据库应用程序中通用动态查询实现方法研究[J].计算机工程, 2002, 28 (11)
模糊查询 篇7
近年来关于图书馆书目查询的研究主要有:针对图书馆馆藏急剧增长的现状,苏菊等人提出一种基于读者借阅信息的科技图书检索结果客观排序算法[1];李石生等人提出了一个基于Deep Web的网上图书检索系统的设计方案[2];文献[3]提出了一种基于信息网格层的异构跨库信息服务体系结构和基于元数据的资源整合技术;文献[4]探讨了智能搜索引擎在数字图书馆个性化服务中的应用;文献[5]论述了在网络环境下图书馆开展个性化信息服务的方法。
通过以上文献分析可知,虽然研究者在图书检索中引入了一些比较新的概念与方法,也取得了一定的成果,但并不能真正解决用户实际的需求。针对以上分析,提出一种基于模糊聚类的目录查询新方法,该方法基于模糊C均值聚类算法,并结合了编辑距离算法,将聚类分析应用到书目信息查询当中,返回更符合用户需求的书目信息。
2 FCM聚类算法的改进
研究将聚类算法引入到目录查询当中,由于传统的FCM聚类算法自身存在着一些问题,若直接将其引入到目录查询当中,会造成查询结果的不稳定,查询结果不精确等问题。主要存在的问题如下:
(1)聚类结果的不稳定性问题。传统FCM算法对初始聚类中心和隶属度函数依赖性较强,选取不同的初始中心,将得到不同的聚类结果。
(2)边界值隶属度赋值问题。若单独将传统FCM聚类算法应用到书目查询当中,在算法执行的最初阶段,要为每一个字段赋予隶属度值。由于位置不同的两个样本点,可能存在到两个不同聚类中心的距离分别相等的情况。
通过以上分析,进行FCM聚类算法的改进,以便将改进后的算法应用到目录查询中。算法改进的主要思想:针对聚类结果的不稳定性问题,在算法的初始阶段,使用一种方法找到聚类中心点的位置,而不是进行随机选取初始聚类中心。针对边界值隶属度赋值问题,借助编辑距离方法,对处于边界值上的样本点进行两两比较,从而确定该样本点归属于哪一个类当中。
编辑距离表示为从一个字符串变换到另一个字符串的最少插入、删除、替换操作的数目。它是一种常用的字符串距离衡量方法,在确定两个字符串的相似性时,有广泛的应用。
字符串编辑距离可以形式化地定义为一个三元组:
亦,每个三元组
dc:A*、B*→R+
字符串xt∈At和字符串y V∈BV之间的距离dc(xt,y V)可以递归的表示为:
其中dc(ε,ε)=0。
由此公式(1)得到dc(xt,yv)的值就是字符串xt和y V之间的编辑距离。
为了从样本数据集中搜索权重较大的点形成高权样本集合,引入以下3个指标:权重、领域半径和高权样本点集,具体定义如下:
权重:
其中,X为样本数据集合,||xi-x||表示对象xi和x的欧氏距离,R代表领域半径。
领域半径:
其中,average(X)表示所有样本对象间距离的平均值,n是样本数目,d(xi,xj)表示对象xi和xj的距离。
高权样本点集:
其中,μweight表示所有样本的平均权重,β是平均权重系数,它针对不同的数据,取值会有所不同。通常情况下,β取值可以由用户根据经验进行设置。
改进后算法的具体步骤如下:
(1)根据(5)式计算高权样本点集H。
(2)初始化中心点集C为空,选择权重最大的点m1为第一个初始中心,并且加到中心点集C中。
(3)从H中选择离m1最远的点作为第2个初始中心m2。
(4)在H中搜索权重较大的点mi,并加入初始化中心点集C,其中mi选择满足:
(5)重复步骤(4),直到初始中心点集合C中包含c个初始中心。聚类个数c由人工进行设定。
(6)使用传统FCM聚类算法的聚类公式进行聚类计算[6]。
(7)根据公式(1)计算dc(xt,yv)的值。判断两个样本点是否是处于同一个聚类中。
3 查询框架
将改进后的FCM聚类算法应用到书目查询的过程中,提出的图书馆馆藏目录检索框架,如图1所示。
主要流程如下:
(1)用户输入查询关键字。该框架实现书目查询的第一步,是由用户输入书名的关键字信息,关键字可以是书名、作者名、主题词、出版社等。
(2)对关键字的分词及查询处理。用户输入的关键字不一定能够满足精确匹配的要求,因为用户可能记不清关于该书目的完整信息,或者用户将书面相关信息记错,因此需要对用户输入的关键字进行分词处理。在该框架中,使用特征库对关键字进行分词。分词特征库内存放了图书的目录特征信息,可以通过该特征库,将关键字分解为最适合用户需要的更小的关键字进行查询。这个时候,会返回多个查询结果。
(3)聚类分析。对上一步返回的书目信息进行改进后算法的聚类分析。首先初始化聚类中心,使用本文提出的高权样本点集计算方法进行初始聚类中心的确定;然后,对书目信息进行聚类;之后,对聚类结果进行编辑距离的计算,优化聚类结果。
(4)书目信息排序。对聚类分析后的结果信息进行按相关度大小程度进行排序。离聚类中心最近的书名,即用户最有可能想查询的书目信息,将排在最前面。
(5)查询结果显示。将排序后的查询结果显示给用户。
在图1中,虚线部分所描述的处理流程是该框架的核心部分,其中包括聚类中心的初始化、聚类分析、编辑距离的计算和数据等价判断等。下一节使用一个现实中的书目样本集,对在此提出的方法进行实验。
4 实验及结果分析
为了验证改进算法在目录查询中的有效性,进行以下两个方面的实验:(1)验证改进算法的有效性,即通过与未改进的FCM算法进行对比分析;(2)使用本文提出的基于模糊聚类的目录查询框架进行书目信息查询。两个实验的开发环境相同,开发工具为Visual Studio 2008,开发语言为C#,数据库使用SQL Server 2008,操作系统为Windows 2003,整个实现过程采用面向对象的思想。
4.1 实验一
首先对改进后的算法进行聚类分析,通过聚类的结果判断改进后算法的有效性。该实验的数据源采用UCI机器学习数据库中的Wine数据集,使用传统FCM聚类算法与改进后的聚类算法分别对Wine数据集进行40次的聚类分析。
从图2可以看出,改进的FCM算法由于采用基于权重的初始化中心算法,选取有代表性的样本作为初始聚类中心,所以改进算法的聚类结果是稳定的。再者,改进后算法的平均准确率为93.3%,而传统FCM聚类算法的平均准确率87.23%。实验结果显示,改进后算法的平均准确率比传统FCM聚类算法的平均准确率有了一定的提高。
4.2 实验二
4.2.1 书目信息初始化及查询
在用户输入查询关键字之后,首先对书目信息进行实例化。为了测试查询结果的准确性,对不同书目的关键字分别进行了多次实验。通过输入关键字,可以从特征库中查询到相关的书目信息。这样,可以得到通过关键字匹配查询的数量相对较多的结果。
4.2.2 聚类中心初始化
在此阶段,主要是对聚类中心的初始值进行计算,并从高权样本点集中选出高权样本点集,定义了如下函数进行高权样本点集的计算。
getHighestWeights(Vector
设置中心点集C:
…
通过getHighestWeights(Vector
4.2.3 聚类及一次聚类后的优化
在找到初始聚类中心后,聚类过程的执行主要包含以下步骤:
编辑距离计算,采用式(1),使用函数:
Edit_Distance(Book book1,Book book2)
通过判断样本点是否是边界值后,对是边界值的样本点进行编辑距离计算,然后进行聚类优化。
4.2.4 书目信息排序
在一次聚类及进行编辑距离计算后,可以得到一组优化后的聚类结果。对聚类分析后的结果信息进行按相关度大小程度进行排序。离聚类中心最近的书名,即用户最有可能想查询的书目信息,将排在最前面。而离聚类中心距离较远的书名,则排在后面。
分别执行了数据量为1000、2000及4000的书目信息检索实验。使用查全率和查准率来衡量文中提出的目录查询框架的有效性,如表1所示。
从表1中可以看出,改进算法下书目查询的平均准确率为88.62%,而使用传统FCM书目查询的平均准确率为8019%,能够满足书目查询的要求。随着数据规模的增大,准确率维持在一个较为稳定的水平,没有出现明显的下降。图3显示了两种不同聚类算法在执行过程中所需要的时间。斜率越小,表示该算法所需执行时间越大。从图3可以看出,改进后算法的执行速度虽然比使用传统FCM进行书目查询稍微慢一些,但该时间的损耗换来了准确率的提高。
5 结语
提出了一种基于模糊聚类的目录查询新方法,该方法基于改进的FCM聚类算法。首先分析了图书馆书目查询的研究近况,包括其存在的问题。然后提出了一种基于模糊聚类的解决方法,由于传统FCM聚类算法存在着一些问题,在将模糊聚类算法引入书目查询前,对传统FCM聚类算法进行了改进。新算法引入了高权样本点集的概念及计算方法,并结合了编辑距离,使聚类结果更加合理。给出了基于模糊聚类的目录查询框架,并进行了关键步骤的分析。
摘要：在此提出一种基于模糊聚类的目录查询新方法,该方法基于模糊C均值聚类算法,并结合了编辑距离算法。针对传统的模糊C均值聚类算法的聚类结果不稳定性问题,引入了高权样本点集;并且在处理聚类过程中的边界值归属不足问题,引入编辑距离算法。
关键词：图书目录,模糊聚类,检索,模糊C均值
参考文献
[1]苏菊,王栋.一种基于读者借阅信息的图书检索结果客观排序算法研究[J].现代图书情报技术,2008,(07).
[2]李石生,刘海博,赵耀.基于DeepWeb的图书检索系统设计[J].河北大学成人教育学院学报,2008,(01).
[3]付凯芳.网格计算在图书文献信息检索中的应用[J].微计算机信息,2009,(24).
[4]贾宏.基于搜索引擎的数字图书馆智能信息检索[J].图书馆学研究,2006,(03).
[5]董敏红,李文渊.网络环境下图书馆个性化信息服务探讨[J].大学图书情报学刊,2006,(01).