（计算机系统结构专业论文）rough关系数据库模型的研究与实现.pdf

r o u g h 关系数据库模型的研究与实现 计算机系统结构 硕士生：叶昌伟 指导教师：叶小平副教授 摘要 r o u 曲集作为处理不确定性信息的有力工具，在相关应用场合发挥了巨大作 用。以r o u 曲集为理论基础的r o u 曲关系数据库模型( r r d m ) 的出现更将为这些 应用提供强大的支持，以弥补传统关系数据库模型在这方面的不足。 目前r r d m 多为理论上的研究，而实现方面的研究则很少。本文侧重从实 现方面对r r d m 进行探讨，首先介绍了r o u 曲集，r r d m ，x m l ，编译原理等 相关方面的基础知识；然后讨论了存储结构和r o u 曲查询语言( r q l ) 的设计，并 以e b n f 文法的形式给出了典型r q l 语句的描述；最后借住编译原理的基本方 法在n e t 平台上实现了一个r o u 曲关系数据库( r r o b ) 中间件雏形 r r d b e n g i n e ，并利用r r d b e n g i n e 实现了一个具有初步功能的r r d b 查询分析 器，本文后半部分将对r r d b e n g i n e 的设计与实现做详细的介绍。 r r d b e n g i n e 严格按照面向对象的方法设计实现，具有很好的扩展性。实现 上巧妙的利用x m l 对r o u l 曲数据进行建模，利用连接池，存储过程，自定义函 数等技术手段提高了中间件的性能。r r d b e n g i n e 为不确定性数据的处理提供了 一个有了的工具，相信会对其它与r r d b 相关的工作起到一定的借鉴作用。 关键词：r o u 曲集，r o u 曲关系数据库，r o u 曲关系数据库模型，r q l ，x m l ， 中间件。 t h es t u d ya n dr e a l i z a t i o no f t h er o u g h r e l a t i o n a ld a t a b a s em o d e l c o m p u t e rs y s t e ma r c h i t e c t u r e n a m e ：y ec h a n g w e i s u p e r v i s o r ：a s s o c i a t ep r o f e s s o ry ex i a o p i n g a b s t r a c t r o u g hs e t h a sb e e ni n c o r p o r a t e di n t ov a r i o u sm o d e l sa n da p p l i c a t i o n sa sa m e c h a n i s mf o rt h em a n a g e m e n to fu n c e r t a i n t y t h e s ei n c l u d es y s t e m si n v o l v i n g a m b i g u o u s ，i m p r e c i s e ，o ru n c e r t a i nd a t a ，w h i c hc a nb e n e f i tm o r ef r o mt h er o u g h r e l a t i o n a ld a t a b a s em o d e l ( r c r d m ) b a s e do nr o u g hs e tt h a nf r o mt h es t a n d a r d r e l a t i o n a lm o d e l u p t on o w , m o s to fw o r kr e l a t e dt or r d mi st h e o r e t i c a lr e s e a r c h ，w h e r e a so n l ya f e ww o r k sd e a lw i t hr e a l i z a t i o n i nt h i sp a p e r , i te m p h a s i z e st h es t u d yo f r e a l i z a t i o no f r r d m f i r s t l y , t h ep a p e ri n t r o d u c e ss o m er e l a t e dt h e o r i e ss u c ha st h er o u g hs e t ， r r d m ，x m l ，a n dc o m p i l e rp r i n c i p l e s t h e ni ts t u d i e st h es t o r a g es t r u c t u r e a f t e r t h a tw ed e s i g nb a s i cr o u g hq u e r yl a n g u a g e ( r q l ) a n dd e s c r i b ei ti nt h ef o r mo fe b n e f i n a l l y , t h ep a p e r d e s c r i b e st h er o u g hr e l a t i o n a ld a t a b a s e ( r r d b ) m i d d l e w a r e r r d b e n g i n e ，w h i c hi m p l e m e n t st h ep a r s e ，t r a n s l a t i o na n de x e c u t i o no fr q l b a s e d o nt h em e t h o do f c o m p i l e rp r i n c i p l e s t h er r d b e n g i n eg a i n sg o o de x p a n s i b i l i t yb e c a u s eo fs t r i c t l yf o l l o w i n gt h e t h o u g h t o fo b j e c t o r i e n t e dd e s i g na n dd e s i g np a t t e r n s i ta l s o g a i n sg o o d p e r f o r m a n c et h r o u g hm a k i n gg o o du s eo f x m l ，c o n n e c t i o np o o l ，s t o r e dp r o c e d u r e ，a n d u s e rd e f i n e df u n c t i o n t h er r d b e n g i n ei sap o w e r f u lt o o lf o rd e a l i n gw i t h a m b i g u o u s ，i m p r e c i s e ，o ru n c e r t a i nd a t a ，a n di s a l s oag o o de x a m p l ef o rt h ew o r k r e la t e df or r d b k e yw o r d s ：r o u g hs e t ，r r d b ，r r d m ，r q l ，x m l ，m i d d l e w a r e i i 第一章绪论 1 1 研究背景及现状 数据库技术不断发展的动力是要使数据更安全有效的存储，并且方便快捷的 被人们利用。为了达到这个目标先后在各个时期出现了不同的数据库模型 1 ， 从最初的层次模型，网状模型，到现在最流行的关系模型，还有正在发展壮大的 对象模型。其中最值得关注的是1 9 7 0 年美国i b m 公司s a nj o s e 研究室的研究员 e f c o d d 提出的关系模型，经过几十年的发展，以它为基础的关系数据库系统得 到了广泛的流行和认可。它有着层次模型和网状模型无可比拟的优点，如灵活性、 逻辑和物理独立性、数据完整性等。然而，它也有自身的不足，比如对于不确定 性信息的处理能力较差。随着应用面的扩大和数据量的急剧膨胀，各种不确定信 息、不完全信息、模糊信息纷纷涌现，例如人们对一个事务的表达往往存在多种 不同的描述，如美国就存在u s a 、u s 和u n i t e d s t a t e s 等多种表达；又比 如要查询红色，可红色有粉红色、血红色和暗红色等：再比如要查询成年男子的 身高，年龄多大才算成年，3 0 还是4 0 7 关系数据库主要是针对确定性信息的处 理，显然不能很好的对上述不确定性信息进行处理，因此十分有必要对关系数据 库模型进行扩展。 r o u g h 集理论近来有广泛的应用，是处理不确定性信息的一个强有力的工 具，并且是建立在深厚的数学基础上的。在r o u 曲集的上下近似等理论的指导 下b e a u b o u e f , t 和p e t r y ，f e 等人于1 9 9 3 年首次提出了r o u g hr e l a t i o n a l d a t a b a s em o d e i ( r r d m ) 2 来弥补传统关系数据库在处理不确定性信息方面的不 足。 b e a u b o e u f , t 等人的工作为r o u g h 关系数据库( r r d b ) 的研究奠定了理论基 础。1 9 9 4 年b e a u b o u e f , t 等在 3 】中又引入f t t z z y 集理论，对r r d m 中上近似集 中的边界域进行r o u 【g h 度的刻画，进一步完善了r r d m 。2 0 0 0 年b e a u b o u e f , t 。 在4 中更加完善地阐述了r r d m ，并且非形式化地讨论了典型的r o u g h 查询语 句。v i e i r a ，j m 等在 6 中借助r r d m 的基本理论讨论了如何在r r d b 中有效 的提取知识，展示了r r d b 在处理不确定信息方面的优势。 国内在在这方面的研究则起步比较晚，曹付元等在7 1 中以查询函数的形式对 标准s q l 语言进行扩展以使其支持粗糙查询，但操作起来比较复杂。安秋生等 人在 8 中提出了组合查询，分解算子等的定义，在【9 中用粒计算的方法对r r d m 进行了研究，提出了用位向量表示上下近似的方法，在r o u g h 查询方面效果比 较好，但对于其它数据操作则显得十分笨拙。 r r d m 的研究起步较晚，但其对不确信息定信息的处理方面确实是传统关系 数据库模型望尘莫及的。相信不久的将来，这方面的研究会受到更加广泛的重视， 将有更多的研究成果出现。 1 2 论文主要工作及其意义 目前国内外对r r d m 的研究多为理论方面的研究，实现方面的研究则相比 之下很少，本文则是针对实现方面的相关问题展丌研究。由于数据库系统是一个 比较大型的系统软件，其开发是需要巨大的财力，人力，考虑到r r d m 是对关 系数据库模型的一种扩展，完全可以采取中问件的形式，充分利用关系数据库的 能力，在关系数据库的基础上实现r r d m ，这样一来，就可在较短时间开发出 具有基本功能的r r d b 。本文j 卜是以中间件的方式开发了r r d b e n g i n e ，它能处理 典型的r q l 语句，并将结果返回给用户。本文的所有：l 二作都是围绕r r d b e n g i n e 巾问件的丌发展丌的，这其中主要涉及到的问题有数据的存储结构，r q l 的形 式化描述，如何基于设计的存储结构实现各种r o u g h 数据操作以及r r d b e n g i n e 体系结构的设计。 针对上述问题，本文首次采用x m l 作为r o u g h 数据的存储手段，并基于此 存储结构提出了基于不分明组的新的查询方法，形式化描述了典型的r q l 语句。 最终在n e t 平台上构建了个具有基本功能的r o u g h 关系数据库中问件 r r d b e n g i n e 。 关于实现方面的研究，值得一提的是安秋生提出的基于粒计算的实现方式 9 】，它对于每个属性值都事先计算好它的上下近似的位向量。然而这种实现方 式存在很大的局限性，主要缺点有两点：1 ，位向量的长度随着记录数的增多而增 大，如果有1 0 万条记录，那么每个位向量的长度就是1 0 万，且每个属性值有两 个位向量，可想而知存储代价是相当惊人的。2 对数据库的任何一点改动，都必 须对所有属性值的位向量进行改动，就连新增加一条记录都将涉及到所有属性值 位向量的改动，其他更新操作将耗费更大的代价。利用本文提出的存储结构，及 建立在其之上的基于不分明组的新的实现方法，可以很大程度上改善更新方面的 代价，同时查询效率也较高。本文5 1 节中对其进行了详细的讨论。 就个人目前掌握的资料还没有r o u l g h 关系数据库中间件这方面的实现，所 以这里不能和类似系统做一个对比，希望r r d b e n g i n e 的出现能对以后这方面的 工作起到很好的借鉴作用。 1 3 论文组织结构 本论文研究的重点在于如何构造r r d b 中间件r r d b e n g i n e ，全文始终围绕 r r d b e n g i n e 实现方面遇到的问题展开讨论。 第一章介绍了相关的研究工作以及本文的工作及其意义。 第二章介绍了r r d m 的理论基础r o u g h 集，然后详细讨论了r r d m 的各 种概念、定义以及r o u 暑l l 关系代数，并给出了一个实际的例子对相关概念进行 了解释。 第三章介绍了在r r d b e n g i n e 存储结构设计中起到关键作用的x m l 技术 和r r d b e n g i n e 依托的低层关系数据库s q l s e r v e r 2 0 0 5 。 第四章介绍了r r d b e n g i n e 设计中用到的编译原理相关方法。 第五章介绍了r r d b e n g i n e 存储结构和r q l 的设计。 第六章介绍了r r d b e n g i n e 体系结构及整体的实现过程。 第七章以各种r q l 语句为主线介绍了r r d b e n g i n e 的实现细节。 第八章先介绍r r d b e n g i n e 的服务架构，然后介绍r r d b e n g i n e 提供的编 程接口，最后介绍一个基于r r d b e n g i n e 实现的查询分析器。 第九章总结了本文的工作。 第二章r o u g h 集与r o u g h 关系数据库模型 2 1r o u g h 集基本知识 二十世纪八十年代初，波兰科学院院士p a w l a k 教授提出了r o u g h 集理论 1 3 。r o u g h 集理提供了一个表示与处理不确定，不完备信息系统的框架，已经 在机器学习，知识发现等领域取得了广泛的应用。 r o u g h 集中最重要的概念是上下近似，后文中的许多讨论都和上下近似相 关。 定义2 1 1 3 设a = ( u ，r ) 是一个近似空间，其中u 是一个非空有限集合称为论 域，r 是u 上的一个划分或等价关系。 x r 为x 在r 关系卜+ 的等价类。设x c _ u ，定 义x 在u 上的一卜近似和匕近似分别如下： r + ( x ) = x | x r x ，x u ) r + ( x ) = x | x r n x o ，x e u ) 集合b n r ( x ) = r + ( x ) 一r - ( x ) 称为x 的r 边界域；p o s r ( x ) 一r 。( x ) 称为x 的r 正域； n e g r ( x ) = u r ( x ) 称为x 的r 负域。显然r + ( x ) 一p o s r ( x ) u b n r ( x ) 。 r ( x ) 或p o s r ( x ) 是由那些根据r 判断肯定属于x 的u 中元素组成的集合。 r ( x ) 是那些根据r 判断可能属于x 的u 巾元素组成的集合。 b n r ( x ) 是那些根据r 既1 i 能判断肯定属于x 又不能判断肯定不属于x 的元 素组成的集合。 n e g r ( x ) 是那些根据r 判断肯定不属于x 的元素组成的集合。 定义2 2 1 4 设a - ( u ，r ) 是一个近似空间，其中u 是一个非空有限集合称为 论域，r 是u 上的一个划分或等价关系。如果r + ( x ) = r ( x ) 则称x 为r 精确集， 否则x 为r 粗糙集。r 精确集用上近似或者下近似表示，r 粗糙集则用上下近 似同时才能表示。 2 2r o u g h 关系数据库模型简介 2 2 1r o u g h 关系数据库模型 r r d m 晟初由b e a u b o e u l ：【2 提出，r r d m 对传统关系数据库模型进行扩展， 使其能够表示和检索不确定信息。r o u g h 关系数据库模型和经典关系数据库模型 有许多相似之处，都是用关系( 即数据库中的表) 的集合表示数据，而又把关系 看作是元祖的集合，而且都是无序的。下面给出一些r o t - 曲关系数据库模型的 定义，其中一部分是改写 2 ， 4 ， 5 中的定义 r o u g h 关系数据库模型和经典关系数据库模型有许多相似之处，都是用关系 ( 即数据库中的表) 的集合表示数据，而又把关系看作是元祖的集合。一个关系 既然是一个集合，就具有一般集合所有的性质，集合中的元素( 即元祖) 是无序 的而且是不重复的。 如果有关系模式r = a l ，a n ，每个属性a 的域d o m ( a ，) 记为d 。，则r 上经 典关系的元祖t i 具有形式 ，其中d i j d j ，j = l ，n 。对于r o t i g h 关系数据库 模型中的元祖我们也把它定义成 的形式，不过每个吐i d ，且d j a 下面我们给出r o u l g h 关系的定义。 定义2 3 设r = a 1 ，a 2 ，a n 是一个关系模式，其中属性a ，的域为d i ， i = l ，n ，则r 上的r o u g h 关系r 是p ( d 1 ) p ( d 。) 的子集。一个r o u g h 元组t i 为t i = p f d l ) x p ( d 。) ，v d o p ( d i ) ，j = l ，n 其中p ( d i ) 表示d ，的冥 集减去o 可以看出r o u g h 关系的属性( 字段) 可以是一个集合，是n 1 n f 的，这与传统关 系数据库中属性必须是原子值不同，因此r o u g h 关系数据库中元组不像传统关 系数据中的元组那样，每个元组只有一个解释，即元组本身。正因为如此，传统 关系数据库中没有解释的概念，而在r o u g h 关系数据库中，这是个非常重要的 概念。 定义2 4 关系模式r = a 1 ，a 2 ，) 上的r o u g h 关系r 的元组t i = 的解释是a ： ，a j 称为d i j 的子解释，其中a j d i i ，j = l ，n 传统关系数据库中，不允许冗余的出现，同样r o u i g h 关系数据库中，也不 允许冗余的出现，下面给出冗余的定义： 定义2 5 设关系模式r = a 1 ，a 2 ，a n 上的r o u g h 关系r 中的两个元组元组 t i = ，t j = ，r ，是每个属性上的不分明关系，如果对于任意k = l n ， 都有 d 。k r k = d j k r k ，则称t i ，之间存在冗余，这里记号 d x y r j 表示u a r j ia e d x y ) 。 r o u g h 关系数掘库同传统关系数据库最大的不同在于，r o u g h 关系数据库能 够处理不确定信息，这个能力是通过定义在每个属性上的不分明关系获得的，每 个属性上的不分明关系是r o u g h 关系数据库固有的特性。 2 中提到这个关系是 一个等价关系，根据这个等价关我们可以把每个属性上的属性值划分为不同的等 价类，所有等价类的并即构成该属性的域。在实际应用中这个等价关系可以多种 多样，比如可以定义一个区分暖色和冷色的关系，根据这个关系红色，黄色被属 于一个等价类，蓝色和黑色属于一个等价类，为了反映r o u 曲关系数据库的性 质，以后都将这个等价关系称为不分明关，等价类称为不分明类。 不分明关系可以既是r o u g h 关系数据库的根本之所在，很多操作都要用到 它，在实际应用中，我们可以给每一个不分明类分配。个唯一的标识符( 不分明 i d ) ，哪个元素属于哪个不分明类，就让它具有哪个类的不分明i d ，凡是具有相 同不分明i d 的就认为是属于同一个不分明类。表2 - 2 通过为每个元素分配一个 不分明i d 从而记录了表2 1 中所有不分明关系，在实际实现中，将不可能把一个 表中的所有不分明关系都记录到同一张表中，在下文实现部分将有详细的讨论， 这里暂时这样简化表示。 下面给出一个粗糙关系的实例，本文的很多例子都是以这个实例为背景的。 例2 1 一个地理信息系统。设地球被分为大小相同的一些区域，其中每个区 域都称为地球子区域。每个予区域只关心两个问题，一是这个i i ；：域属于哪个( 那 些) 国家，二足这个区域有那些地理特征。地理特征是根据实际需求给出的某种 层次的描述，例如有的区域的地理实测是湖泊，但实际问题不需要区分是咸水湖 还是淡水湖，那么只指出该区域的特征是湖泊就可以了。这样确定之后，我们可 以认为在这个地理信息系统中，咸水与淡水湖是不分明的，所以给它们分配同一 个不分明i d ，其它属性值也基于实际应用中的考虑给它们分配不分明d ，使它 们划分到不同的不分明类中。 由表2 - 2 可以看出，属性f e a t u r e 域中的等价类是 s w a m p , b o g m a r s h ， w e t l a n d ) ， b e a c h ，c o a st ，s a n d j ， r o a d ，a r p o r t , p a r k i n gl o t ； 6 b u i l d i n g ；u r b a n ) ， w a t e r ，r i v e r ，l a k e ，s e a ，o c e a n ， g r a s s ， p a s t u r e ，m e a d o w ， c r o p l a n d ，f a r m l a n d ， f o r e st ，w o o d s ， j u n g l e ，w o o d l a n d 。 属性c o u n t r y 域中的等价类是： i u s ，u s a ，u n i t e d s t a t e s ， b e l i z e ， b r i t i s hh o n d u r a s ) ， c u b a ) ， m e x i c o ， i n t , i n t e r n a t i o n a l 。 设关系模式r = i d ，c o u n t r y , f e a t u r e ，其上的一个r o t i g h 关系 s u b r e g i o n s 如表2 1 所示。关系中一个元组已载一个地球子区域的国家及特 征，每个元组在属性i d 上的取值是该子区域的唯一标识。 由于在r o u g h 关系中，一个元组在各个属性上的取值允许是集合，所以 r o u g h 关系都不属于1 n f ，这个地理信息系统的r o u g h 关系也清楚的体现了这一 点。例如，子区域u 1 5 7 跨越了美国和墨西哥两个国家，所以它的c o u n t r y 属 于的取值就是集合 u s ，m e x i c o ；再如子区域u 1 2 5 ，在这个区域中，既有沼泽， 又有牧场，还有河流，所以它在f e a t u r e 属性上的取值就是 m a r s h ，p a s t u r e ，r i v e r ，而不能是只是一个值。 表2 1一个记载地理信息系统的r o u g h 关系s u b r e g i o n s i dc o u n t r yf e a t u r e u 1 2 3 u s ) m a r s h ，l a k e u 1 2 4 ( u s ) m a r s h ) u 1 2 5 u s a m a r s h ，p a s t u r e ，r i v e r ) u 1 2 6 u s ) s a n d , r o a d ，u r b a n ) u 1 4 7 u s ) s a n d ，r o a d ) u 1 5 7 u s ，m e x i c o s a n d ，r o a d ) m 0 0 7 m e x i c o ) s a n d ，r o a d ) m 0 0 8 ( m e x i c o ) b e a c h ) m 0 0 9 m e x i c o )( s a n d ) c 0 3 9 b e l i z e j u n g l e c 0 4 0 b e l i z e ，i n t j u n g l e ，c o a s s e a 表2 - 2 地理信息系统s u b r e g i o n s 的不分明关系 属性值 i n d f e a t u r es w a m p1 f e a t u r eb o g1 f e a t u r em a r s hl f e a ：r u r ew e t l a n dl f e a t u r eb e a c h2 f e a t u r ec o a s t2 f e a t u r es a n d2 f e a t u r er o a d3 f e a t u r ea i r p o r t3 f e a t u r e p a r k i n gl o t 3 f e a t u r e b u i l d i n g 4 f e a t u r eu r b a n4 f e a t u r ew a r t e r5 f e a t u r e r i v e r 5 f e a t u r el a k e5 f e a t u r eo c e a n5 f e a t u r es e a5 f e a t i j r eg r a s s6 f e a t u r ep a s t u r e6 f e a r r u r em e a d o w6 f e a t u i t eg r o p l a n d7 f e a t u r ef a r m l a n d7 f e a t u r e f o r e s t 8 f e 。町u r ew o o d s8 f e a t u r ej l n g l e8 f e a t u r ew o o d l a n d8 c o u n t r yu s9 c o u n t r yu s a9 c o u n t r yu n i t e d s t a t e s9 c o u n t r yc u b a 1 0 c o u n t r yb e l i z e 1 1 c o u n t r yb r i t i s hh o n d u r a s l l c o u n t r ym e x i c o1 2 c o u n t r y i n t e r n a t l 0 n a l1 3 c o u n t r y t 1 3 2 2 2r o u g h 关系运算 同传统关系数据库一样，r o u g h 关系数据库的功能也是由r o u g h 关系运算决 定的，为了更深刻的理解r o u g h 关系数据库中的操作，下面将介绍r o u g h 关系 运算，大部分的定义都是直接引自 2 1 1 4 。 粗糙关系运算中主要讨沧粗糙关系代数，包括粗糙差、粗糙并、粗糙交、料 糙选择、粗糙投影、粗糙连接，而且仍采用经典关系数据库中相应的运算符：， u ，n ，口，兀，p q 。 2 2 2 1r o u g h 差 差运算、并运算、交运算都是两个“兼容”r o u g h 关系间的运算。所谓“兼 容”r o u g h 关系其定义如下： 定义2 6 设r t = a 1 ，a 2 ，a 。i ) ，r 2 = b i ，b 2 ，b 。2 ) 是两个关系模式，满足 n l = n 2 ，即属性个数一样多；对应的a ，b i 都有相同的数据域，则称r i r 2 是兼 容的关系模式。兼容模式一k i ￥j r o u g h 关系称为兼容r o u g h 关系。 下面我们定义r o u g h 差运算。 定义2 7 设r 1 ，r 2 是两个兼容的关系模式，r i ，r 2 分别是r 1 ，r 2 上的r o u g h 关系， 则。l ，r 2 的差，记作r l i - 2 ，是一个与r b r 2 兼容的关系模式上的r d u 曲关系。r 满足： r ( r ) 2 t i t r 1 ( r 1 ) a n d t 茌r 2 ( r 2 ) ) r ( r ) = t l t r i ( r 1 ) a n d t 芒r 2 ( r 2 ) ) 即r 的下近似是r l 与r 2 的下近似的差，r 的上近似是r 1 与r 2 的上近似的差。 2 2 2 2r o u g h 并 定义2 8 设r l ，r 2 是两个兼容的关系模式，r l ，r 2 分别是r l r 2 上的r o u 曲关系 l j r l ，r 2 的差，记作r 1u r 2 ，是一个与r l ，r 2 兼容的关系模式上的r o u 曲关系。r 满足 r ( r ) 。 t it r 1 m ) o r t r 2 ( r 2 ) r + ( r ) = t l t r i ( 。1 ) o i t r 2 * ( r 2 ) 即r 的下近似是r 1 与r 2 的下近似的并，r 的上近似是r l 与r 2 的上近似的并。 2 2 2 3r o u g h 交 定义2 9 设r 1 ，r 2 是两个兼容的关系模式，r 1 ，r 2 分别是r 1 ，r 2 上的r o u 曲关系， 则r 1 ，r 2 的差，记作r 1n r 2 ，是一个与r i ，r 2 兼容的关系模式上的r o u 曲关系。r 满足 r ( r ) 2 t i t r i ( 。1 ) a n d t r 2 ( r 2 ) ) r ( r ) = t l t r 1 + ( r 1 ) a n d t r 2 * ( r 9 j r j r 的下近似是r 1 与r 2 的下近似的交，r 的上近似是r l 与r 2 的上近似的交。 2 2 2 4r o u g h 选择 r o u g h 关系数据库的选择运算是一个一元运算，运算符为口。盯的自变量是 一个r o u g h 关系。j 的返回值是根据一些特定的属性值选出的r 的一个子集。例 如，o - 一= a ( f ) ，将返回r 中在属性a 卜- 取值等价于a 的那些元组，即取值属于 a r a 的那些元组。下而给出r o u g h 选择的形式化定义。 定义2 1 0 设r 是一个关系模式，r 是r 上的r o u 曲关系，a r ，a c d o m ( a ) ，则 对r 的r o u g h 选择o - a = a ( r ) ，是r 上的r o u 曲关系s ，s 满足： r ( r ) 2 t r lu i a i r a 2u j b j r a ，a i a ，b j t ( a ) ) r ( r ) = t r iu i a i r a u j b j 】r a ，a i a ，b t ( a ) ) g j r 的下近似是a 上取值的等价类的并集等于a 的等价类的并集的那些元组，r 的 上近似足a 上取值的等价类的并集是a 的等价类的并集的超集的那些元组。 2 2 2 5r o u g h 投影 r o u g h 投影是一个一元运算，运算符为兀。n 的自变量是一个r o u 曲关系r 。 如果x e r ，则兀。( r ) 2 9 l nr 在x 的那些属性上的值，但要删除去冗余元组。为此， 我们有如下形式化定义。 定义2 1 1没r 是一个关系模式，r 是r a 21 的r o u g h 关系，x _ c r ，n r 在x 上的 投影，记作兀。( r ) ，是x 上的一个r o u g h 关系s ，s 满足： r + ( r ) - = l e d t ( x ) it r ( r ) 良( r ) = r e d t ( x ) li r + ( r ) ) 即s 的下近似是r 的下近似在x 上的取值的集合删除掉冗余后的结果，s 的上近似是 r 的上近似在x 上的取值的集合删除掉冗余后的结果。 2 2 2 6r o u g h 连接 r o u g h 连接是一个二冗运算。它把两个关系中的相关元组组合成结果关系中 的一个元组，从而用共同的属性把两个笑系合成为一个通常会更广的关系。 定义2 1 2 设r t - a h ，a 。) ，r 2 = b k 。b 。) 是两个关系模式，r 1 ，r 2 分别是r l 皿2 上的r o u g h 关系，形如a i 也的表达式称为连接条件，简称条件，1 i s n ，1 剑s m 。 r h l 2 在某条件下的连接，记作r ld q ( m ) r 2 ，是关系模式r 3 = a l i ，a 。，b 1 ) ，b 。) 上的 r o u g h 关系r 3 。若条件是a f = b i ，则r 3 满足 r ( r 3 ) = ti j t l r ( r 1 ) ，j t 2 r ( r 2 ) ，t r 1 - - h ，t r 2 - = t 2 ， t l a i r l a i = t 2 b j r 2b j ) r ( r 3 ) = t 1 3 t l r + ( r 1 ) ，3 t 1 r + ( r 1 ) ，t 【r 1 _ t l ，t r 2 】= t 2 ， t t a i r l a i t 2 b j r 2 b jo r t l a i 】r l a i 三 t 2 b j 】r 2 b j ) 即r 3 的下近似是r 3 上这样一些元组的集合，它们中每一个在r 一中属性的取值都与 某个n 中的元组一样，在r z 中属性的取值都与某个r 2 中的元组一样，而且在a j 上 的等价类与在b j 上酐j 等价类相等。r 3 的上近似是r 3 上这样一些元组的集合，它们 中每一个在r ，中属性的取值都与某个r 。中的元组一样，在r 2 中属性的取值都与某 个r 2 中的元组一样，而且或者在a i 上的等价类是在b j 上等价类的子集，或者在b 上的等价类是在a i 上等价类的子集。 值得注意的是在上述定义中r 3 _ a l i ，a n ，b 1 ，b 。) ，可见与经典关系连 接运算不同，相同属性连接后的并不合并为一个属性，这是因为连接关系是以等 价类判断的，而等价类相等，具体的属性值并不一定相等。 2 2 3r o u g h 查询示例 介绍完了r o u g h 关系数据库模型及其关系代数，下面我们给出一个具体的 例子，对上面的理论作一个形象的说明。 例2 2 我们想查询s u b r e g i o n s 中f e a t u r e 为s a n d 和r o a d 的这样 一个r o u g h 关系中的i d ，c o u n t r y , f e a t u r e 这3 个感兴趣的属性值。 查询可以用类似s q l 的形式表示如下 s e l e c ti d ，c o u n t r y , f e a t u r ef r o ms u b r e g i o n sa ssw h e r e s f e a t u r e = f s a n d ，r o a d 1 虽然r o u g h 关系查询表面上看上去和传统的关系数据库查询一样，但是其处理 过程是不一样的。原因有三点： 1 r o u g h 关系中属性值是集值。 2 属于同一个不分明类中的属性值被认为是不可区分的，也就是在比较时认为 它们是一样的。 3 查询的结果是一个r o u g h 集，也就是用一个上近似集和一个下近似集表示的 元组的集合。 查询过程如下： 根据定义2 1 0 查询所得的关系r 应满足 r + ( r ) = t ru ( s a n d rf e a t u r e ， r o a d rf e a t u r e ) = u j h rf e a t u r e ，b t ( f e a t u r e ) r + ( r ) = t ru s a n d rf e a t u r e ， r o a d rf e a t u r e ) u j h rf e a l 、u r e ， b j t ( f e a t u r e ) ) 上述条件是以不分明组的形式( 等价类) 给出，但表2 - 1 是以属性值的形式 给出的，为了直观的况明查洵的过程，这里先对表2 - 1 进行改造，即根据表2 - 2 用各属性值的不分明组的并集表示。改造后的表如表2 3 所示 根据表2 - 2查询条件中的u ( s a n d r f e a t u r e ， r o a d r fe a il j r e ) = u b e a c h ，c o a s t , s a n d ， r o a d ，a i r p o r t , p a r k i n gl o t ) ) = b e a c h ， c o a st s a n d ，r o a d ，a i r p o r t , p a r k i n gl o t 根据表2 3 得出上下近似分别为： 下近似 i dc o u n t r yf e a t u r e u 1 4 7 u s )( s a n d ，r o a d ) u 1 5 7 u s ，m e x i c o ) s a n d ，r o a d ) m 0 0 7 m e x i c o ) s a n d ，r o a d ) 上近似 i dc o u n t r yf e a t u r e u 1 2 6 u s s a n d ，r o a d ，u r b a n u 1 4 7 u s ) s a n d ，r o a d ) u 1 5 7 f u s ，m e x i c o s a n d ，r o a d m 0 0 7 m e x i c o ) s a n d ，r o a d 表2 - 3 以不分明组表示的地理信息系统的r o u g h 关系s u b r e g i o n s i dc o u n t r yf e a t u r e u 1 2 3 f u s ，u s a ， s w a m p , 1 3 0 g m a r s h ，w e t l a n d ，w a t e r ， u n i t e d s t a t e s )r i v e r ，l a k e ，s e a ，o c e a n u 1 2 4 u s ，u s a ， s w a m p , 1 3 0 g m a r s h ，w e t l a n d u n i t e d s t a t e s j u 1 2 5 u s ，u s a ， s w a m p , b o gm a r s h ，w e t l a n d ，g r a s s ， u n i t e d - s t a t e s )p a s t u r e ，m e a d o w , w a t e r ，r i v e r ， l a k e ，s e a ，o c e a n u 1 2 6 u s ，u s a ， b e a c h ，c o a s ts a n d ，r o a d ，u r b a q ， u n i t e d s t a t e s )a i r p o r t , p a r k i n gl o t , b u i l d i n g ) u 1 4 7 u s ，u s a ， b e a c h ，c o a st ，s a n d ，r o a d ，a i r p o r t , u n i t e d s t a t e s ) p a r k i n gl o t ) u 1 5 7 u s ，u s a ，m e x i c o b e a c h ，c o a st ，s a n d ，r o a d ，a i r p o r t