基于语言变量的关系数据库模糊查询

基于语言变量的关系数据库模糊查询 2009 年 5 月 计 算 机 工 程第 35 卷 第 9 期 May 2009 Computer Engineering Vol.35 No.9 文章编号:1000—3428(2009)09—0028—03 文献标识码:A 中图分类号:TP311 ?软件技术与数据库? 基于语言变量的关系数据库模糊查询 陈逸菲，叶小岭，张颖超 (南京信息工程大学信息与控制学院，南京 210044) 摘 要:在模糊理论的基础上，将权重概念引入关系数据库模糊查询中，以体现用户对查询中各个属性的相对重视程度。记录按匹配度的降序输出，方便用户选择。权重和匹配度都是语言变量，取值为语言值，更加贴近自然。采用模糊集合的 alpha 截集去模糊的思想，将带 语言值权重的模糊查询条件转化为精确的 SQL 语句，利用 RDBMS 的机制进行记录的筛选，避免对整个数据库表的扫描，在一定程度上 保证查询的效率。 关键词:模糊查询;语言变量;权重 Fuzzy Queries Based on Linguistic Variables in Relational Databases CHEN Yi-fei, YE Xiao-ling, ZHANG Ying-chao (College of Information and Control, Nanjing University of Information Sciences & Technology, Nanjing 210044) 【Abstract】The concept of weight is introduced in fuzzy queries based on theory of fuzzy set, which shows the relative importance that users pay to different attributes in query clauses. The records that satisfy queries are output according to the decrease of matching degrees, so users can select what they want more conveniently. Weights and matching degrees are linguistic variables, whose values are linguistic terms, and the queries become more flexible. The alpha-cut of fuzzy set is used to translate the linguistic fuzzy querying conditions into crisp SQL clauses. It is possible to make use of the mechanism of RDBMS to filter the records, which avoids scanning the whole table and assures the efficiency. 【Key words】fuzzy queries; linguistic variables; weight 1 概述 2 语言变量及权重、匹配 度 自 Zadeh 提出模糊集合理论以来，出现了许多基于该理语言变量是以自然语言或人工语言中的字或句，而不是 以数作为值的变量。语言变量的值被称为语言值，用于描述 论的数据库模糊查询方法。 文献[1]基于模糊数的交、[7]那些不太精确的现象。文献[9]给出了语言变量的定义。 并、补的 ， 截集运算，对 SQL 定义 1 语言变量由一个5 元组(H, T(H), U, G, M)表示。 语言进行扩展，提出了将模糊的查询条件转换为精SQ确L 语 其中，H 是变量的名称;T(H)是 H 的术语集合，即H 的语言 句的方法。文献[2] 给出了 SQL 语言较完整的模糊化版 本 值的集合;H 的每一个值是由X 表示的模糊变量，并且X 定 SQLf。由于用户在查询时对于每个子条件的倾向、重视程度 义在论域 U 上，与基本变量 u 相关;G 是用来产生H 的值的 不同，有必要为各个子查询条件指定权重。文献[3-4]提出将 语法规则;M 是语义规则，与每个X 的意义 M(X)相关，M(X) 权重表示为[0,1]之间的数值，权重值越大，表示对应的条件 是 U 上的模糊子集: 在整个查询中起的作用越大。由于权重和模糊集合的隶属度 T=X1+X2+„+Xi+„ 可以将“权重”和“匹配度”作都是[0,1]之间的值，因此在模糊查询中引入权重是很方便的。 为语言变量，给出如下 文献[5]在 SQLf 的基础上将模糊查询扩展为带权重的情况。 定义: 但是对于非专业用户而言[，0,1]之间的数值权重确定起来并T(Importance)/T(Matching Degree)=absolutelhighy + 不方便。文献[6]指出模糊集合隶属度具有很强的健壮性，没 extremely high+very high+high+fairhighly + 有必要对隶属度给出精确的估计，表现在模糊隶属度本来就 somewhat high+medium+somewhalot w+ 是用于描述不精确的信息，因此，没有必要精确为数值;在 fairly low+low+very low+extremely lo w+绝大多数模糊查询的文献，如文献[1-2,5]中都是使用m in/max absolutelyl ow (1) 将隶属函数进行结合，此时没有必要知道隶属度的具体 要将上述语言变量形式的权重、匹配度用于模糊查询，值。 就必需在语言变量的各语言值之间建立全序关系，即定义有 基于这2 点可知，只要建立隶属度的全序关系即可。类似，序语言值。 权重也没有必要为[0,1]之间的数值，只要能反映出用户对条 件的相对重视程度即可。因此，建立语言值表示形式的隶属 基金项目:江苏省“六大人才高峰”基金资助项目(06-A-07);南京 信息工程大学科研基金资助项目(y644) 作者简介:陈逸菲(1981,)，度、权重是可行的。文献[7]考虑了在文献检索系统中引入语 女，讲师、博士研究生，主研方向:模 糊信息处理，时空数据库;言值权重，但是这些方法对关系数据库的查询而言并不适用 。叶小岭，副教授;张颖超，教授 本文在文献[8]的基础上，提出了一种新的利用模糊集合 截集来计算语言值表示的模糊查询的方法，该方法避免了原 收稿日期:2008-11-28 E-mail:ch_yi_f@126.com 方法需扫描整个数据库表的缺点，提高了查询的效率。 [7] 定义 2有序语言值:定义一个有限的基数为奇数的语例 1 对表 2 中的关系 Person 执行下列查询 SELECT name 言值标记集合 S , s, i 0,1,…,T (s? s 如果 i ? j )。集合 ,, ,,i i j Person FROM 中的第 T /2 ， 1 个术语表示“近似为0. 5”，其他的术语关于它 WHERE age is young AND heighits tall 对称。每个语言值由定义在[0,1]上的模糊数表示。本文采用WEIGHT age is medium; heighti s very high 梯形隶属函数 (a, b, c, d) ，其中 a, d分别为最左、最右的端 i i i i i i WITH medium 点， b, c区间范围内的隶属度为1.0 。 i i 其中，young, tall 的隶属函数为此外定义以下运算: 1, x ? 25 , Neg (s) , s; j , T i(2 ) i i 1 , (8) ,( x) , ,young 2 max(s, s ) , s如果 i ? j (3) x 25 i j i ,x , 25 1 ， , 5 min(s, s ) , s如果 i ? j ; i j i (4) 1, [10]? 190 x 本文使用 13 个语言值标记构成的集合来运算，见 1表。, 1 , (9) ,( x) , 表 1 语言值权重/匹配度和其对应的梯形模糊 数 ,tall 2 x 190 , 1 x , 190 ， 语言值符号 语言值权重/匹 配度 梯形模糊数 ,10 Absolutely high (1.0,1.0,1.0,1.0) s12 Extremely high s(0.901 7,0.949 3,1.0,1. 0) ;11 表 2 Person Very high (0.806 5,0.8541 , 0.901 7,0.949 3) s10 编号 姓名 年龄 身高/cm (0.711 3,0.758 high 9, 0.806 5,0.854 1) s9 (0.616 1,0.663 7,0.711 3,0.758 9) Fairly high s8 R1 20 173 王刚(0.520 9,0.568 5,0.616 1,0.663 7) sSomewhat hig h7 (0.425 7,0.473 3,0.520 9,0.568 5) Medium 吴平 s6 R2 31 165 (0.330 5,0.378 1, 0.425 7,0.473 3) Somewhat low s5 夏明 R3 33 181 Fairly low (0.235 3,0.282 9, 0.330 5,0.378 1) s4 张昊 Low (0.140 1,0.187 7, 0.235 3,0.282 9) s3 R4 40 175 (0.047 6,0.093 5,0.140 1,0.187 7) Very low s2 毛建 Extremely low (0.0,0.0, 0.047 6,0.093 5) R5 25 183 s 1苏宁 sAbsolutely low (0.0,0.0,0.0,0.0 ) 0 R6 28 177 范冰 [7] 定义 3NTL(Numeric To Linguistic label)是一个将[0,1]R7 39 170 丁俊 R8 22 185 贾涛 区间的数映射到有序模糊语言标记集S 合上的函数: 陈强 R9 26 172 NTL: [0,1] S; R10 31 183 NTL( x) , Sup {s S : , , Sup {, ( x)} (5) n ss l l l n 例如某人的年龄为3 0 岁，其关于年轻的数值隶属度 以 R1 为例说明计算方法: ,(R1) , 1, ,(R1) , 0.257 ,(30) , 0.5 ，根据式 (5) 得其对应的 语言值隶属 度为 young tall young NTL(0.5)=s 。此时不再用[0,1]之间的点，而是用[0,1]区间上 6 根据式(5)得到对应的语言值隶属度为s , s，代入式(6): 123的一个(梯形)模糊数s 来表示隶属度。前者称为?型模糊数， 6 MD(R1) , min(max( Neg (s), s), max( Neg (s), s)) , s 6 12 12 3 3后者称为?型模糊数，即?型模糊数的隶属度是一个?型模 [9] 4 基于 ， 截集的改进算法糊数。 显然直接根据式(6)、式(7)计算匹配度进行查询，要计算3 语言值权重和匹配度的计算 数据库表中每条记录相关属性的隶属度，效率很低。这里给 令 A , A为关系数据库中关系T 的属性。假设用户的查 i 出利用 ， 截集，将带有语言值权重的模糊查询条件转化为精 询如下:确 SQL 语句的新方法。 4.1 DLWC(Derivatioonf LWC)算法SELECT A 对式(6)进行分析，当M D(R) , min{max(Neg(w ), m ( A )),…, T FROM AC1 1 1 WHERE is CAND Ais C„ANDA is CA1 1 2 2k kmax( Neg (w ), m ( A ))} ? ， 时，也就是说 i, Neg (w ) ? ， 或 ACk A k k iWEIGHT Ais w ; Ais w ;„; Ais w 1 2 k A A A 12km ( A ) ? ， ，R 才会出现在结果中。若Ne g (w ) ? ， ，则不管 Ci A i iWITH ， m( A) 为何值， max( Neg (w), m( A)) 都必定大等于 ， 。 w C i A C i A其中，C是模糊概念，如“年轻”，用?型模糊数表示w;是 i i i i i A i 由用户在查询时给出，对于每条记录而言都相同，因此，A的语言值权重; ， 是语言值匹配度的阈值。 i Neg (w) 是已知的;而 m( A) 则由每条记录的属性值决定， 构成了有序语言值形式的条件集合:A Ci i i {(w, m( A)), (w, m( A)),…, (w, m( A))} 往往不相同。所以，先判断Ne g (w ) 可以进行初步筛选，减 A C 1 A C 2 A C k A 1 1 2 2 k k i其中， m( A) 表示属性 A关于“Ais C”的语言值隶属度。 少不必要的计算。只有当Ne g (w ) , ， 时才需要对每条记录计k k kCk k A i 记录 R 关于上文的语言值匹配度计算如下:算 m ( A ) 。 Ci i MD(R) , LWC[(w, m( A)), (w, m( A)),…, (w, m( A))] , A C 1 A C 2 A C k 1 1 2 2 k k 计算 m ( A ) 时也不必 扫描所有的 记录 。 因 为 只 有Ci i (6) min {max( Neg (w ), m ( A ))} i ACi i i m ( A ) ? ， 的记录才可能出现在结果中，其余的记录是无关C i i 类似若将上文中的“AND”换成“OR”，则有 的。但是 m( A) 和 ， 都是语言值，不能直接去模糊。假 设C i i )), (w, m( A)),…, (w , m( A))] ,MD(R) , LWD[(w, m( A AC2 ACk A C 1 2 2 k k 1 1 ， , s , p {1, 2,…,T } ，可知 语言 值 标 记 s 和 s 的交点 为 p p 1 p (7) max {min((w , m ( A ))} i ACi i i ，(见图 1，其中横坐标 μ 为?型模糊数隶属度，纵坐m标(μ ) p 其中，LWC 为 Linguistic Weighted Conjunction ;LWD 为 是 μ 关于语言标记对应的梯形模糊数的隶属数)。只有当记录 Linguistic WeightedD isjunction。 的属性 A关于模糊概念 C的隶属度不小于 ，时，其语言值只有当 w ? ， 时，才需要计算 m ( A ) 。与 4.1 节类似，采用 AC i i p i ii隶属度才可能为s 。对于那些关于 C的数值隶属度大等于 p i 去模糊化思想可以得到DL WD 算法: ，的记录，其由式(5) 计算得到的语言值隶属度必定大等 p (1)设 ， , s , p {1, 2,…,T } ，求出 s 与 s 的交点 ，。 p p p 1 p 于 s 。 p (2)判断查询中的子条件“A is C”的权重 w 是否满 A i i i 足 w ? ， ;不满足则转(3)，满足则转(4)。 A i (3)求 C的 ，截集 [,, ,] 。 i p i i (4)若 i , k , i+1，转(2)，否则转(5)。 (5)将(2),(4)中得到的 [,, ,] 组合成精确的SQ L 语 i i 图 1 语言值标记s 和 s的交点 p-1 p 句。 (6)利用 SQL 语句筛选出记录集合set (R)，对此集合中的 因此，可以利用 ，对 C的隶属函数去模糊，得到 ，其截 p i p 每一条记录利用式(7)计算语言值匹配度。集 [,, ,] ，只有在此范围内的记录才可能出现在结果 (7)将匹配度大于阈值 ， 的记录输出。 i i 中。根 注意当 p , 0 时，DLWD 算法退化成文献[8]中的算法。据上述讨论得到D LWC 算法: 5 结束语 (1)设 ， , s , p {1, 2,…,T } ，求出 s 与 s 的交点 ，。 p p p 1 p 本文在语言变量的基础上，将查询中的权重、记录的匹(2)判断查询中的子条件“A is C”的权重 w 是否满 i i A i配度都用语言值表示，使得查询更加方便直观、贴近自然语 足 Neg (w ) ? ， ;不满足则转(3)，满足则转(4)。 言。并且利用模糊集合 ， 截集去模糊的思想，将带有语言值 A i 权重的模糊查询语句转化为 RDBMS 能理解的精确SQ L 语 (3)求 C的 ，截集 [,, ,] 。 i p i i 句，从而利用RDBM S 本身的机制进行记录的筛选，在一定 (4)若 i , k , i+1，转(2)，否则转(5)。 程度上提高了查询的效率。今后将考虑对较复杂的模糊查询 语句进行语言值表示的扩展。 (5)将(2),(4)中得到的 [,, ,] 组合成精确的SQ L 语 i i 句。 (6)利用 SQL 语句筛选出记录集合set (R)，对此集合中的 每一条记录利用式(6)计算语言值匹配度。 参考文献 (7)将匹配度大于阈值 ， 的记录按降序输出。[1] Chen Shyiming, Jong W. Fuzzy Query Translation for Relational 注意当 p , 0 时，DLWC 算法退化成文献[8]中的算法， Database[J]. IEEE Transactions on Systems, 1997, 27(4): 714-721. 即只能扫描整个表来计算匹配度，得到查询结果。 [2] Bosc P, Pivert O. SQLf: A Relational Database Language for Fuzzy 例 2 用 DLWC 算法重新计算例1 Querying[J]. IEEE Transactions on Fuzzy Systems, 1995, 3(1): ， , s，根据表1 可以计算出 s和 s的交点 ，, 0.449 5 。 6 5 6 6 1-17. 年龄的权重为s ，而 Neg (s) , s= s? s，所以不必计算 6 6 12 6 6 6 [3] Kantor P B. The Logic of Weighted Queries[J]. IEEE Transactions 各记录关于“age is young”的隶属度;height 的权重为 s， 12 on Systems, 1981, 11(12): 816-821. 而 Neg (s) , s, s，只有当 m(height ) ? s时，记录才可能 12 2 6 tall 6 [4] Sanchez E. Importance in Knowledge Systems[J]. Information 满足条件。根据式(9)求出“height is tall”的隶属函数的 ，截 6 Systems, 1989, 14(6): 455-464. 集 [178.93, 250] (设正常人的身高上限为25 0 cm)，得到精确的 SQL 语句: [5] Zhang Yingchao, Chen Yifei, Ye Xiaoling, et al. Weighted Fuzzy Queries in Relational Database[C]//Proc. of the 2nd International Conference on Fuzzy Systems and Knowledge Discovery. Changsha, SELECT name China: [s. n.], 2005: 430-440. Person FROM [6] 欧阳继红. 时空推理中一些问题的研究[D]. 吉林: 吉林大学, WHERE height>=178.93 2005. 表 2 中在此范围内的记录为R3 , R5, R8, R10。根据式(6) [7] Viedma E H. An Information Retrieval Model with Ordinal 对这 4 条记录计算匹配度，并按降序排列，结果见3。表 Linguistic Weighted Queries Based on Two Weighting Elements[J]. 表 3 例 2 的查询结果 International Journal of Uncertainty, Fuzziness and Knowledge- height 的语言值隶属度 age 的语言值隶属度 记录号语言值匹配度 based System, 2001, 9(9): 77-87. R8 sss12 9 9 ssR5 s8 8 12 [8] 陈逸菲, 张颖超, 叶小岭. 带语言值权重的模糊查询[J]. 计算机 R3 sss 476 应用研究, 2005, 22(6): 73-75. R 10 sss 5 8 6 [9] Zadeh L A. The Concept of a Linguistic Variable and Its Application 4.2 DLWD(Derivatioonf LWD)算法 to Approximate Reasoning[J]. Information Science, 1975, 8(3): 对式(7)进一步分析，当 MD(R) , max{min(w , m ( A )),…, AC1 1 1 199-249 min(w , m ( A ))} ? ， 时，等 价于 i 使得 min(w , m ( A )), ACk ACi k k i i [10] Chen Shyiming, Lin Yunshyang. A New Method for Fuzzy Query i {1, 2,…,T } ，R 才会出现在结果中。即 i 使得 w ? ， 且 A Processing in Relational Database System[J]. Cybernetics and i m ( A ) ? ， 。因为 w 是已知的，若w , ， ，则无论 m ( A ) 为 Systems, 2002, 33(1): 447-482. Ci AACi i iii 何值， min(w , m ( A )) 都小于 ， ，此时不必再计算 m ( A ) ; 编辑 任吉慧ACi Ci i i i