（计算机软件与理论专业论文）基于刻面分类的软件构件检索的研究.pdf

哈尔滨工程大学硕士学位论文 摘要 基于构件的软件开发是解决软件危机的有效途径。在基于构件复用的软 件开发过程中，构件库管理系统扮演了重要角色。在构件库管理系统中，构 件的分类方式及其检索是最基本也是最核心的功能之一。有效的检索机制能 大大降低复用成本。本文从构件的刻面分类模式出发，针对构件检索的特点， 结合树匹配模型思想，在构件树路径匹配算法的基础上提出一种改进算法。 实验证明改进的路径匹配算法具有良好的检索效率。 本文主要分三大部分，第一部分首先综合分析构件库管理系统的组成、 功能、关键技术、以及发展现状。通过对关键技术的分析，引入构件的分类 模式，并着重分析了刻面分类模式，目的是为后面内容作知识准备。 第二部分在刻面分类模式的基础上，结合树匹配模型思想，按照树匹配 条件的张驰程度依次介绍了6 种匹配模型。然后对基于包涵匹配模型的路径 匹配算法进行了者重分析。 第三部分提出一种双向匹配的改进路径匹配算法。与原算法相比，改进 算法增加了从构件方到查询树方的路径包容匹配，同时，利用路径匹配的性 质，提出一种旨在降低改进算法时间复杂度的匹配预判断机制“选择性 路径匹配机制”。在此基础上对改进算法从理论上进行了深入的分析。最后通 过实验对算法改进前后的查全率，时间复杂度进行测试。通过数据对比，分 析改进算法的优越性和不足之处。 关键词：构件库管理系统；刻面分类。；构件检索：路径包含匹配；选择性路 径匹配 堕玺鎏三堡盔兰鎏圭耋垡鲨銮 a b s t r a c t t h es o f t w a r ed e v e l o p m e n tm e t h o dt h a tb a s e do nc o m p o n e n tr e u s ei so n eo f t h ea v a i l a b l ew a y st or e s o l v et h ec r i s i so fs o f t w a r e ，a n dt h ec o m p o n e n tb a s e m a n a g e m e n ts y s t e mp l a y sa ni m p o r t a n tr o l ei nt h i sd e v e l o p m e n t i nt h i ss y s t e m ， c o m p o n e n tr e t r i e v a l i st h em o s tb a s i ca n di m p o r t a n tf u n c t i o n e f f e c t i v e m e c h a n i s mo fc o m p o n e n tr e t r i e v a lc a nr e d u c et h ec o s tf o rs o f t w a r er e u s e e v i d e n t l y t h i sp a p e rg i v ea ni m p r o v e da l g o r i t h mw h i c hb a s e d o np a t h c o n t a i n m e n tm a t c h i n ga l g o r i t h ma n dc o m b i n e dw i t ht h ef e a t u r e so ff a c e t e d c l a s s i f i c a t i o ns c h e m ea n dt h et h e o r yo ft r e em a t c h i n g t h er e s u l t so fe x p e r i m e n t s h o wt h ei m p r o v e da l g o r i t h mh a sh i g hs e a r c he f f i c i e n c yi nc o m p o n e n tr e t r i e v a l t h i st h e s i sh a st h r e ep a r t s t h ef i r s tp a r ti n t r o d u c e st h ec o m p o s i t i o n ，f u n c t i o n ， a n da p p l i c a t i o no ft h ec o m p o n e n tb a s em a n a g e m e n ts y s t e m t h e n , p r o v i d es o m e i n t r o d u c t i o nt o c o m p o n e n t c l a s s i f i c a t i o n s c h e m e ，e s p e c i a l l y t of a c e t e d c l a s s i f i c a t i o ns c h e m e t h ep u r p o s ei st op r e p a r ef o rt h ef o l l o w i n gc o n t e n t i nt h es e c o n dp a r t , o nt h eb a s i so ff a c e t e dc l a s s i f i c a t i o ns c h e m ea n dt r e e m a t c h i n gm o d e l ，a c c o r d i n gt or e l a x a t i o nd e g r e eo fm a t c h i n gc o n d i t i o n ，t h et h e s i s m a i n l yd i s c u s s6m a t c h i n gm o d e l ，a n dt h e np a ym o r ea t t e n t i o nt ot h ea n a l y s i so f p a t hm a t c h i n ga l g o d t h r aw h i c hb u i l to nt r e ec o n t a i nm a t c h i n gm o d e l i nt h et h i r dp a r t ，t h ep a p e rp u tf o r w a r dab i d i r e c t i o n a li m p r o v e dp a t h m a t c h i n ga l g o r i t h m c o m p a r e dw i t h t h ef o r m e ra l g o r i t h m ，t h i si m p r o v e d a l g o r i t h mp r o v i d e sa n e wk i n do fm a t c h i n gm u t ew h i c hf r o mc o m p o n e n tt r e et o q u e r yt r e e m e a n w h i l e ，i no r d e rt or e d u c et h et i m ec o m p l e x i t yo ft h ei m p r o v e d a l g o r i t h m ，ab e f o r e h a n dj u d g i n gm e c h a n i s mi sq u o t e dw h a tc a l l e d “s e l e c t i v ep a t h m a t c h i n gm e c h a n i s m o nt h e b a s i so fa b o v er e s e a r c h ，t h ep a p e rm a k e sa f u l l - s c a l ea n a l y s i si nt h e o r y t h e n , t oc o m p a r e 、i t ht h ef o r m e ra l g o r i t h m a p r a c t i c a lp r o g r a m m e dt e s th a sb e e nc a r r i e do u t f r o mt h et e s t i n gr e s u l t s ，w ec a n k n o wm o r ea b o u tt h ea d v a n m g ea n dt h ed e f i c i e n c yo f t h ei m p r o v e da i g o r i t h m 哈尔滨工程大学硕士学位论文 k e y w o r d s ：c o m p o n e n t b a s e m a n a g e m e n ts y s t e m ，f a c e t e dc l a s s i f i c a t i o n ， c o m p o n e n tr e t r i e v a l ，p a t hc o n t a i n m e n tm a t c h i n g ，s e l e c t i v ep a t h m a t c h i n g 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：扯 日期：别年；月j 日 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 软件复用与构件技术 软件工程的发展己近三十年。其间，众多的科研人员和工程技术人员付 出了艰辛的努力，取得了丰硕成果。软件工程思想和技术的普及，使软件生 产率稳步上升，软件质量得到很大改善。但是，这还不能满足软件产业发展 的需求，离彻底解决“软件危机”还有相当大的距离。近几年来，人们开始 认识到，要彻底解决“软件危机”，就要真正实现软件的工业化生产方式，这 样，才能保证软件生产的高效率和高质量，软件复用是一条现实可行的途径。 对软件复用技术的研究己成为软件工程界的主攻方向之一。 软件复用是指应用已有的、为重用目的而开发的软件构件构造新的软件 系统【l 】。软件构件技术被视为支持软件复用的核心技术之一。围绕软件复用 出现了许多软件开发技术，比如软件构件技术、软件构架技术、构件组装技 术等，这些方面是软件复用研究的重点。 软件行业的工业化趋势导致了软件构件的产生。所谓软件构件是指应用 系统中可以被明确辨识的构成成分，而可复用构件是指具有相对独立的功能 和可复用价值的构件。随着对构件理解的深入，构件的概念己经不再局限于 源代码构件，而是延伸到系统和构件的需求规约、构架、文档、测试计划、 钡r 试案例和数据以及其它对开发活动有利的信息。 当前，软件构件技术己成为研究的热点，其研究内容包括构件的标准与 模型、构件的生产与获取、构件的规约与描述、构件的分类与组织、构件的 检索与组装、软件体系结构、软件复用支持工具与管理手段、基于复用的软 件开发过程等方面。研究工作有很大进展和众多成果，而且还出现了一些产 业构件标准，如c o m ，d c o m ，c o m + ，s u n 的e j b 租o m g 的c c m 。这标志 着软件复用己进入蓬勃发展的时期 2 l 。 晗尔滨工糨大学硕士学位论文 l ，2 构昝疼管理系统麓余 掏l 牛瘁管理系统( c o m p o n e n tb a s em a n a g e m e n ts y s t e m 麓称c b m s ) 是冀 构件库的建立、使用和维护而配置的应用软件。通过构件库存储构件，提供 可鬟耀的软件资源。它建立在操作系统的基础土，对构件瘁避行统一的管璐 和控制，并提供相j 澎的工具支持开发者在软件开发避程中方便地从构件库中 检索、理姆和选取构件，提赢软件搿发的效率和质爨。另外构件库餐理系统 还负责构件库的维护工作，保证构件库的安全性和完整性。构件庠l 圭j 支持丰句 件运行和管理的构件库框架和构件字典组成。构件艨管理系统类似数据库管 理系统，它通过构彳牛库管理语言来宓现对构件蓐的一般管理鞫特殊管理。 构件库管理系统的基本臻求应包括以下几个方顽： ( 1 )构俘痒定义。毽旗对构件库结构的搐述、构馋瘁完整毪定义、安 全傺密定义( 如用户臼令、级别、存取权限) 、存取路径定义簿。这魑定义存 储程数据字典串，怒稳箨瘁餐建系统运季亍瀚基本依据。 ( 2 )构件存取。提供用户对构件的基本操纵功能，实现对构件库构件 熬稔索、臻入、修竣秘黧除。一个葑鹣c b m s 疲该提供功戆强显荔攀荔露鹣 构件操纵语宙、方便的操作方式和较高的数据存取率。 ( 3 穆释瘁运行警理。这是e 嚣m s 熬核心部分，包攒梭转提取、褥穆 识别、构件执行、构件库内部的维护( 如索蹲l 、构件字典的翻动维护) 等。所 鸯秘 孛疼熬搽彳萋罄簧在这些控涮程黪熬统一管理下筵 孬，滋僚证系统懿正确 运行和构件库的正确有效。 ( 枣簿 孛缀缀、存穗秘罄理。c b m s 耍爨级敷管理各炎擒停，要磺宠 以何种结构、何种存储方式缌织这些构件，如何实现构件之间的联系。构件 组织强存谑瓣基本强檬是携蹇存镶燮阗利雳率，选择合适鲍存取方法提离存 取效率。 ( 5 )稳传痒懿建立程维护。与建立与维护数摆疼类 娃，包括梅馋库的 初始建立、构件库的转储和恢复、构件库的霆组织与重构造以及性能监测分 析等功能。 ( 6 )支持构件组合。构件由对象发展而来，具有高度的封装性和继承 哈尔滨工程大学硕士学位论文 性，因而具有强大的组合功能。构件的组合是构件研究的新内容。 1 3 构件库管理系统的研究现状 目前，构件技术成为国内外研究的热点，逐渐引起软件工程研究人员的 重视。构件技术在理论和实际应用中已被人们普遍关注。在国内，北京大学、 中科院软件所、复旦大学、南京大学、华中科技大学、中山大学、吉林大学 等高校和研究所，陆续发表了许多非常有价值的学术论文，为构件技术在中 国的发展指明了方向。实际应用中，北京大学和中科院软件所的青鸟工程在 构件技术方面进行诸多尝试。此外，构件技术在一些软件公司也得到应用， 这些软件公司如中软公司、特宝科公司、天中公司等，构件技术给这些公司 带来极大的效益，获得普遍的好评。在这些公司应用构件技术的成功为以后 软件构件技术的发展积累了丰富经验。 国外对构件库管理系统的研究主要成果有a l o a f ( a s s e tl i b r a r yo p e n a r c h i t e c t u r ef r a m e w o r k , a l o a f ) 模型，r i g ( r e u s el i b r a r yi n t e r o p e r a b i l i t y g r o u p ，砒g ) ，n a t o ( n o r t h a t l a n t i et r e a t yo r g a n i z a t i o n , n a t o ) 等组织制订的 软件复用标准，r e b o o t ( r e u s eb a s e do no b j e c t - o r i e n t e d t e c h n o l o g y , r e b o o t ) 复用环境，北大青鸟工程的j b c l m s ( j a d eb i r d c o m p o n e n tl i b r a r ym a n a g e m e n ts y s t e m j b c l m s ) 系统。现在简要描述如下 【3 】 1 a l o a f 模型 它是s t a r s ( s o f t w a r et e c h n o l o g yf o ra d a p t a b l e ，r e l i a b l es y s t e m s ) 项目 为解决在构件库之间共享资源和无缝互操作问题而于1 9 9 2 年提交一个开放 体系结构的构件框架报告。该报告充分体现s t a r s 项目对可复用构件系统 的认识，给出了一个构件库框架的参考模型和该参考模型的一个实例 a l o a f 模型，由此表明了以公共元模型为基础，在构件库之间交换信息和 创建易于移植的复用工具是可能的和必要的h 。 2 i l l g 组织 该组织为了实现在软件复用库间共享软件构件、解决构件库之间的可互 操作性问题，在a l o a f 的基础上开发了一个数据模型u d m ( u n i f o r md a t a 哈尔滨工程大学硕士学位论文 m o d e l ，u d m ) 5 i ，u d m 定义了支持可互操作性的构件库之间交换构件所需的 信息，以此来达到构件库之间的无缝互操作。作为u d m 的一个步骤，r i g 开发了“b i d m ( b a s i ci n t c r o p c r a b i l i t yd a t am o d e l ，b i d m ) ”，它是u d m 的一 个子集，是实现互操作和构件库交换构件所需信息的最小集【6 ，2 7 】。 3 n a t o 组织 它制订了一组关于软件复用的标准可复用软件构件开发指南、 可复用软件构件管理指南和软件复用过程指南，其中可复用构件库 管理指南讨论了有关构件库建立和管理的问题【”。 4 r e b o o t 项目 它是国际上比较著名的构件库管理系统，包括一个存储可复用构件的构 件库和一组产生、认证、插入、提取、评价和适配可复用构件的环境i 目。 5 青鸟构件库管理系统 它是“基于构件构架模式的软件复用支持系统”【2 】的核心子系统， 用于对可复用构件进行描述、管理、存储、分类和检索，以满足基于“构件 一构架”复用方式的软件开发过程的需要【9 】。 1 4 构件技术的规范 构件技术规范是关于开发可复用构件及构件之间相互通信的一组标准的 描述。遵循构件技术规范所开发的软件构件，具有标准的接口和良好的移植 性。软件复用人员可以像搭积木一样复用这些构件，快速构造应用程序。这 样不仅可以减少软件开发的成本、节省大量时间，还能够使开发出来的新软 件系统具有较高的质量，更加符合规范。 目前已为软件行业所广泛接受的三种构件技术规范是：m i c r o s o f t 的 c ( ) m d c o m c o m + ，s u n 的e j b 和o m g 的c c m 。这三种构件技术规范分 别建立在各自的分布式计算技术平台。m i c r o s o f t 的c o m 】) c o m c o m + 是建 立在m i c r o s o f td n a2 0 0 0 ( m i c r o s o f td i s t r i b u t e di n t e r n e ta p p l i c a t i o n2 0 0 0 d n a 2 0 0 0 ) 分布计算技术平台上，e j b 是s u n 推出的基于j a v a 的服务器端构 件规范j 2 e e ( j a v a2p l a t f o r me n t e r p r i s ee d i t i o n ，j 2 e e ) 的一部分，而o m g 的c c m 是继承和吸收e 强当前规范的基础上，基于c o r b a 规范制定的服 哈尔滨工程大学礤士学位论文 务器构l 牛殿用开发模型。以下介缨了这三葶孛构件技术规范及其楣墩的分毒计 算平台。 。4 。 m i c r o s o f t 的c 0 知麟0 氧彰c o m + c o m ，d c o m 和c o m + 是微软公司在不同时期的软件构件模型和标准。 蛰c 0 辩楚c o m 逶瘦子i n t e r n e t 分布式疲蘑豹扩震。蔼c o m + 是农c o m 蘩稻 上结合微软事务服务器( m i e r o s o f lt r a n s a c t i o ns e r v e r , m t s ) 朝微软消息队列服 务嚣( m i c m s o rm e s s a g eq u e u es e r v e r , m s m q ) 瑟澎残熬。c o m 是m i c r o s o f t 提出的构件标准，它是一种以构件为发布单元的对象模型，这种模型使各软 臀褐终可滋题一耱绞一熬方式进行交互。c o m 不仅定义了拣箨糕痔之藤避 彳亍交互的标准，也提供了构件程序运行所福的环境。c o m 标准包括规范和 实现嚣部分，援藏郏努定义了梅秘秘势之阗逶臻懿枫裁，这些糕范不傣羧 予任何特定的语言和操作系统，只骚按照该规范，任何语言都可使用。c o m 椽壤熬实现部分是c o m 艨，c o m 疼受c o m 趣藏躲具体实瑗提供7 些核 心服务。c o m 库钒含以下内容： ( 1 )提供了少量a p i 函数实瑷客户鞠服务器蠛c o m 应用敕创建； ( 2 )c o m 通过注册表查找本地服务器即e x e 程序，以及程序名与 c l s i df c l a s si d e n t i f i e r ) 的转换等； ( 3 )提供了一种标准的内存控制方法，使成用程序w 以控制进程中内 存的分配。c o m 艨不在应髑程序屡实现，瓤在操作系统层次上实现，因此一 个操作系统只有一个c o m 库实现。此外，c o m 瘁的实现必须依赖予具体平 台，尤其怒系统底层的一贱标准。 d c o m 是c o m 的扩餍，它可以支持不同计算机上构件对象与客户程序 之间或者构件对象之间的棚互通信，这些计算机可以在局域网内，也可以在 广域网上，甚至邋进i n t e m e t 逶行连接。对于客户程序而嵩，构件程序鹃位 置是透明的，不必编写任何处理远程调用的代码，因此，d c o m 怒c o m 的 无缝扩震。d c o m 作为c o m 的扩展，它不仅继承了c o m 豹语富无关经、 可霪用性、软件可配置性好等优点，针对分布式环境，它也提供了一些新的 特性，如位嚣透明经、阚络安全毪、跨平窘调雳等。 c o m + 并不是c o m 的新版本，可以认为是c o m 的新发展或熨高层次上 哈尔滨工程人学硕士学位论文 的应用。c o m + 是c o m d c o m 和m t s 的集成，它不仅继承了c o m ，m t s 和d c o m 的许多特性，同时也增加了一些服务，如负载平衡、内存数据库、 事件模型、队列服务等。c o m + 新增的服务提供了很强的功能，建立在c o m + 基础上的应用程序可以直接利用这些服务而获得良好的企业应用特性。 c o m + 有以下特点： ( 1 )真正的异步通信：c o m + 底层提供了队列构件服务，允许客户和 构件进行异步通信； ( 2 )事件服务：新的事件机制利用系统服务简化了事件模型，避免了 c o m 可连接对象机制的琐碎细节，使事件源和事件接收方实现事件功能更 加灵活； ( 3 )灵活性：动态负载平衡以及驻留内存数据库、对象池等系统服务 为c o m + 的灵活性提供了技术基础； ( 4 )可管理和可部署性：c o m + 的申述式编程模型和构件管理环境支 持应用系统在开发完成后的管理和部署； ( 5 )易于开发，c o m + 开发模型比以前的c o m 构件开发更为简化。 1 4 2o m g 的c c m c o r b a 是o m g 组织基于众多系统平台厂商提交的分布对象互操作内容 的基础上制定的公共对象请求代理体系规范。它的底层和核心部分是对象请 求代理。从某种意义上说，c o r b a 是“软件总线”。c o r b a 的实质是 r p c ( r e m o t e p m c e d l l r e c a l l ，r p c ) 与面向对象技术的有机综合。在c o r b a 中， 每一个构件都是一个对象，含有一个基于匿向对象的接口，内部代码实现可 以是o o ( o to r i e n t e d 0 0 ) 或非o o 的语言，总线上的对象能够被任何其他 对象所使用。c o r b a 规范是由o m g 提出的一种开放的、分布式对象计算 结构，它为异构计算环境的互操作提供了标准。使用c o r b a ，能够实现应 用程序之间的相互通信，而不论它们的位置、编程语言以及操作系统环境是 否相同。c o r b a 具有如下突出特点l l o 】： ( 1 )分布计算技术和面向对象编程技术( o b j e c to f f e r e dp m 野a r 姗i n g ， o o p ) 相融合。通过o o p 的继承性，实现软件源代码的复用。 ( 2 )引入了“代理”的概念。代理的基本作用：完成对客户方提出的抽 哈尔滨工程大学硕士学位论文 象服务请求的映射，自动发现和寻找服务器，自动设定路由，实现到服务器 方的执行。通过代理，用户在编制客户程序时不需了解实现的细节，只需完 整地定义和说明所需完成的任务和目标即可。 ( 3 )客户端程序与服务器端程序的完全分离。通过代理机制，客户端 不再同服务器发生直接联系，而仅和代理进行交互。因此在保持调用方式不 变的情况下，服务器方和客户端程序都可以自由地修改和升级而无须通知对 方，从根本上改变了传统的面向过程调用机制的客户n 务器模式。 ( 4 )提供了“软件总线”的功能。软件总线是c o r b a 定义的一组独立 于语言和环境的接口规范，按照该接口规范开发出来的软件，便可集成到该 系统中，而且这个规范独立于任何实现语言。 ( 5 )设计原则和设计方式的层次化。c o r b a 规范仅定义了o r b 中用 到的最基本对象、属性和方法，而面向应用的对象可以在o m a 的应用对象、 领域对象或开发环境中逐层进行定义和实现，c o r b a 规范是针对o r b 通信 中间件制订的工业标准，而面向应用的对象定义则可在对象管理体系结构的 应用对象或应用开发环境中逐步分层定义和实现。 1 4 3s u n 的e t b e j b 规范是s u n 公司于1 9 9 7 年1 2 月发布的j a v a b e a n 构件模型。一个 e j b 是特定的在服务器上运行的j a v a b e a n ，并且e j b 能在可视化的工具下装 配成新的应用。e j b 应用程序只能用j a v a 语言编写，良好的e j b 应用程序可 以在j 2 e e 认证的应用服务器之间移植和互操作而不需要修改任何源代码。 e j b 规范是位于服务器方的j a v a b e a n 和一种新的构件协调者o t m ( o b j e c tt r a n s a c t i o nm o n i t o r , e j b 称之为包容器) 之间的挤定。o t m 提供运行 服务器方构件的框架，它负责激活构件或撤消构件，协调分布式事务，捕获 构件事件以及自动管理构件的状态。e j b 定义了服务器方构件模型和一个构 件协调者的框架，解决了c o r b a 出于缺乏完整的服务器方构件模型和构件 协调者的框架所引起的服务器方构件无法互相交换的问题，实现了与 c o r b a 的兼容，使得e j b 具备了基于j a v a b e a n 的客户端和服务器方的构件 模型。 e j b 简化了用j a v a 语言编写的企业应用系统的开发和配置。它定义了一 哈尔滨工程大学硕士学位论文 组可复用构件，利用这些构件，开发人员可以像搭积木一样构建所需要的应 用程序。e j b 基础结构是由e j b 构件、e j b 容器以及o t m 组成的。e j b 构 件是运行在服务器上由o t m 管理的b e a n 。o t m 充当构件协调者的角色， 使用标准的j a r 从其他o t m 或工具中导入e j b 。一旦e j b 处于o t m 内， 就可以加入事件处理、状态管理、自动激活或撤消等功能。e j b 容器提供了 系统级的服务，控制了e j b 的生命周期。所有的e j b 实例都运行在e j b 容 器中。 e j b 是一种基于构件的开发模型，它是j a v a 服务器端的服务框架规范。 e j b 详细地定义了一个可以方便地部署j a v a 构件的服务框架模型，用于创建 可伸缩、多层次、跨平台、分布式的应用，并可创建具有动态扩展性的服务 器端应用。e j b 具有以下特点【l ”。 ( 1 ) e j b 以构件的形式组织服务器，e j b 构件是宜接用j a v a 语言编写 的服务器方构件，j a v a 语言编写的跨平台特性使得e j b 构件可以方便地移植 到各种操作系统平台和e j b 服务器上： ( 2 )e j b 构件实现仅需考虑应用需求，其系统级服务诸如事务管理、 安全性、构件生命周期和线程等，都是通过e j b 服务器自动进行管理的： ( 3 )e j b 的体系结构具有面向对象、分布式、跨平台、可扩充性、安 全性以及便于开发等优点，同时它还是以协议为中心的，任何协议都可以使 用。 1 5 本文的研究内容 构件库管理系统作为实现构件技术的支撑系统，主要实现构件的存储、 检索、管理、安全和维护等功能。其中，构件的检索功能是构件库管理系统 的基本功能，它的效率和功能直接关系到整个管理系统的性能。有效的检索 机制能大大降低复用成本( 单个构件的复用成本= 检索成本+ 理解成本十修改 成本) ，所以构件的检索效率是衡量构件库管理系统的一个重要的指标，因 此构件的检索一直是构件库管理系统研究的一个重点、难点和热点。而构件 的检索方式是建立在对构件的分类方式的基础上的。目前应用最多的构件分 类方式就是刻丽分类方式，本文的研究内容主要是探讨基于刻面分类的构件 哈尔滨工程大学硕士学位论文 库管理系统中的构件检索。在前人的基础上对目前某些应用较多的刻面分类 构件检索方式进行研究，对已有的一些效率不高的检索算法进行改进。 1 6 论文的组织形式 第一章讲述软件复用与构件技术的产生背景，引入构件库管理系统与构 件技术的规范，列举了构件库技术在国内、外发展的现状，讲述了作者的研 究内容和论文的组织框架。 第二章通过介绍构件库管理系统的关键技术和主要功能，引入构件分类 与构件检索的概念，并着重介绍基于刻面分类的构件分类方式，为下一章介 绍基于刻面分类的构件检索打下基础。 第三章在刻面分类方式下，结合树匹配模型思想，按树匹配模型中匹配 条件的张驰程度依次介绍了6 种树匹配模型，并给出匹配代价的泛型算法。 第四章介绍基于树包涵匹配的路径匹配算法。通过对原路径匹配算法的 分析提出改进的路径匹配算法，从理论上证明改进后的算法在查全率方面的 提高。并在改进路径匹配算法基本思想上，利用包涵匹配的性质，提出了旨 在降低改进算法时间开销的“选择性路径匹配机制”。 第五章对改进算法的具体实现提出方案，通过实验数据对路径匹配算法 改进前后进行比较分析。作出结论，并以此作为全文总结的基础。 哈尔滨工程人学硕士学位论文 第2 章构件库管理系统的关键技术 2 1 构件库管理系统层次结构 和数据库管理系统一样，我们将构件库管理系统划分成若干层次清晰合 理的功能模块。这不仅可以帮助我们更清楚地认识构件库管理系统，更重要 的是有助予我们对构件库管理系统中的关键技术进行分析。 如图2 1 所示，按照功能将一个具有普遍性构件库管理系统的分为三个 层次，分别是构件库的入库系统、构件库的维护系统、构件库的组装系统。 m 巴霉哥 侄圈 i 和裔法性检验 ! l ”“l 三三 图2 1 构件库管理系统的层次结构 一柑件蝌浆 哈尔滨工程大学硕士学位论文 ( 1 ) 构件库的入库系统。构件制作完成后通过对构件的分类和描述，以及 合法性的检验，将构件存入构件库中。其中，构件的存储功能解决构件在构 件库管理系统中的具体的存储方法和数据结构，是实现构件库管理系统的前 提。构件的描述分类方式则决定了构件在构件库中的组织形式和检索方式、 构件间的逻辑关系、构件的合法性规则。 ( 2 ) 构件库的维护系统。完成对构件库中的构件进行检索、修改、插入、 删除、统计等功能，是构件库管理系统运行的支撑系统。构件库的维护系统 类似于数据库管理系统d b m s 对数据库管理功能。其中构件的检索功能是构 件库维护系统的基本功能，由于检索功能直接与用户进行交互，因此检索的 效率和功能就直接关系到是否能查全、查准用户所需要的构件，是否能够讲 检索的过程控制在用户所能容忍的时间空间开销内。可以说，检索功能是整 个构件库管理系统的核心功能。 ( 3 ) 构件库的组装系统。将检索到的构件经过修改，插入等过程后，得到 用户预期目标的或者是接近于用户预期目标的构件，并将这些构件按照用户 所规定的序列进行构件组装，最后生成应用系统的过程。 综上所述，我们可以看出，在一个具有普遍性的构件库管理系统中，构 件的存储功能、构件的分类方式、构件的查询功能是其关键技术所在。对此 我们将逐一进行详细分析。 2 。2 构件的存储方式 构件库的构件存储系统可以采用多种方式：面向对象数据库o o d b s m s 、 关系数据库r d b m s 和文件系统f i l e s i ”】。 o o d b s m s 具有存储数据量大、易于维护、易于扩充、易于格式动态变 动等优点，但它目前尚无成熟产品，尤其在标准化和性能上令人不满意，并 且有些构件又不支持面向对象技术，因而o o d b s m s 不能满足构件库对构件 的存储要求。 相比之下，关系数据库r d b m s 具有储存和管理大量数据的高效性、理 论的严密性和技术的成熟性，它不仅可以支持存储不同的数据类型和复杂的 数据结构，而且能够表示结构化的数据，可以方便地表达出数据之间的关系， 哈尔滨工程人学硕士学位论文 并且还可以提供多种线索进行查询，具有很高的查询效率，所以是构件存储 系统的首选：但是，在实际应用中，构件的结构极其复杂，存在形式多种多 样，且构件的体积可能很大，这与关系数据库对所保存的数据项一般都有尺 寸限制，不宜过大的要求不相符合。所以，仅用r d b m s 来存储构件显然是 可能的，但又是不够的。 另一种可用来存储的系统是文件系统f i l e s 。f i l e s 系统的存储特点是存储 容量大，对存储的数据体积无限制，且可以存储多种不同形式的构件。这点 刚好符合对构件存储的要求。目前，已也有许多软件产品都采用了文件系统 来存储构件，如b o r l a n d 公司的d e l p h i 和p o w e r s o f t 公司的p o w e r b u i l d e r 的 对象仓库等，它们就是使用的f i l e s 文件系统。但f i l e s 不利于大量数据的存 储，因为它的查询效率低，缺少有效快捷的检索途径，查找构件不方便。同 时，由于文件系统操作的基本单位是文件，文件与文件之间不能建立复杂关 系。显然，这与对构件检索高效率的要求不符，同样也与对在构件之间建立 各种关系的要求不符。因此，文件系统f i l e s 也不完全符合对构件存储的需要。 从上述的分析可以知道，数据库主要适合存放具有复杂结构和相互关系 并且对检索效率有较高要求的数据，而文件系统适合存放对检索效率没有很 高要求，但尺寸较大的数据。由此可见，任何一种单一的存储方式都不能高 效、灵活地储存和管理构件，因此在实际应用中往往是结合多种方式来实现 构件的存储。 2 3 构件的分类方式 好的分类方式是有效检索与理解的基础。w f r a k e s 和h m i l i 分别研究 了现有的构件分类和检索方法。w f r a k e s 从构件表示出发，将现有方法分 为人工智能方法、超文本方法和信息科学方法3 类【1 3 】；h m i l i 贝j j 按照复杂度 和检索效果的递增，将其分为基于文本的、基于词法描述予的、基于规约的 编码和检索3 类【l 】。w f r a k e s 重点讨论了信息科学方法，因为这是实际复用 项目中，应用较为成功的途径。图2 2 为信息科学的编目方法分类其中以枚 举、刻面、属性值、关键词和正文检索几种方法最为常用，又以关键词分类 ( k e y w o r d ) 和刻面分类( f a c e t e d ) 两种应用最多。 l2 哈尔滨工程大学硕士学位论文 亟堕l l 蜜萼： r 广_ 1 广1 广1 l 甏盛次泣| 关继训法|l 水讯币取 ；l 之ll 术t t i 献止y 小批墩| ，兰= = = = j = = 三l 型，一三二= = _ 一l = 二二j = = = = 一 困圈奎圈圆匝回 图2 2 信息科学的编目方法分类图 枚举分类。( 以杜威图书分类法为例) 通常将一个被关注的领域严格划分 为不相交的子领域，依次构成层次结构。该方法对领域进行清晰和高度结构 化的划分。例如，我们要找一本关于三阶偏微分方程的书，那么在一个枚举 分类的系统中一般的路线是先查找数学类的书，在这个范围内再查找微分方 程类的书，再在这个范围内查找偏微分方程类的书。其优点是容易为大多数 人所理解，便于使用。但是枚举分类方法有以下一些缺点：1 ) 索引必须手工 建立，丌销大，易产生错误；2 ) 一个部分的概念模糊可能让该部分适用于配 置中的多个位置，难以定位；3 ) 结构不容易平衡，相同类型的部分较多丽另 一些很少的局面很难灵活使用。 属性值分类。在属性值分类中，构件被描述成其属性和属性值的集合， 例如，如果属性为“作者”，那么其取值可能是“约翰”。这种分类方式比 较容易理解使用且可以部分自动化，但是需要比较复杂的检索机制，也同样 具有枚举分类中模糊性带来的缺点。 正文检索。从文档中自动提取分类信息，可以实现自动编码分类。其优 点是无需编码，无需学习构件查询条件，因此具有成本优势。缺点是必须与 成熟的语言处理系统结合，才能解决从复杂的正文中，准确地抽取语法和语 义信息。 关键词分类。简单而且为人熟悉，每个构件以一组与之相关的关键词编 目，查询者给出关键词来描述所需的构件，并由此获得构件。一般认为关键 词的取值是不受限制的，用来描述构件关键词，可以取任何有意义的字符串 ( 不受控的词汇表) 。由于关键词缺少上下文语境而不够精确，导致该方法所 哈尔滨工程大学硕士学位论文 支持的查询效率不高。 刻面分类。是将关键词( 术语) 置于一定的环境中，并从特定反映构件 本质特性视角( 刻面) 进行精确分类。每个刻面具有一组术语( 关键词) ，术语 之间具有一般特殊关系而形成结构化的术语空间，允许术语之间有同义词关 系。术语仅限在给定的刻面之中取值( 受控制的词汇表) 。在术语空间中，游 历可以帮助复用者理解相关领域，术语空间可以演变。 刻面选择和术语空间的建立，依赖不同构件库的角色和复用组织的需求。 例如有关文献提出刻面有：功能、对象、介质、系统类型、功能领域和应用 领域。有的在构件库中定义的4 个刻面为；抽象、操作、操作对象和依赖。有 的定义成5 个刻面分别为：使用环境、应用领域、功能、层次和表示方法。 基于词法描述子的绽码和检索所谓基于词法描述子的编码，相当于基 于受控词汇表的表示方法，该方法类有若干个变种和细化，如上述的多刻面 分类方法。其中近似匹配算法，将基于偏序关系的检索扩展为基于距离的检 索，可以利用带权语义网、模糊逻辑触发器或带权的术语空间等技术计算构 件之间的语义距离，实现近似查询。 基于规约的表示和检索。基于规约的构件表示与检索方法一般需要一 种规约语言，构件的表示用该规约语占描述。构件检索时，用户首先写出需 求规约，然后提交。构件检索的实际过程一般由检索模块根据构件规约与需 求规约间的某一偏序关系进行检索，构件库中的构件一般按照构件规约间的 偏序关系来组织。这样，在构件检索时检索历程可以大大减少需求规约与构 件规约比较的数目，从而提高检索效率。检索效果与所采用的规约语言的子 集有关，有的检索方法只采用基于基调( s i g n a t u r e b a s e d ) 的检索，有的采用基 调与前后件( p r c p o s t - c o n d i t i o n ) 联合检索。一般而言，若只采用基于基调的 检索方法、对于检索回叫率( r e c a l l ) 没有影响，但查准率( p r e c i s i o n ) 不高；若 采用基调与前后件联合检索，则准确率将会提高。 喧玺鎏三堡盔兰鎏圭主堡鲨苎 2 4 基于刻面的构件分类方式 本文所要探讨的是基于刻面分类的检索方式，所以我们有必要详细的介 绍一下刻面分类方式。 刻面( f a c e t ) 这个术语最早使用是在5 0 年代，分别出现在r a n g a n a t h a n 的 图书馆分类系统中和g u t t m a n 的一项社会调查中。但那时刻面概念还比较模 糊，刻面之间存在着语义上的文选等诸多不合理因素。 现代构件库管理系统的刻面分类检索法是p r i e t o d i a z 和f r e e m a n 在1 9 8 7 年提出的，这种方式通过反映构件本质特性的视角( 刻面) 对构件进行精确的 分类。一个刻面分类模式( f a c e t e ds c h e m e ) i 刍- - 组描述构件本质特征的刻面组 成，每个刻面从不同的侧面对构件库中的构件进行分类。每个刻面由一组术 语( t e r m ) 构成，称为术语空间( t e r ms p a c e ) ，描述子( d e s c r i p t o r ) g d 不同的刻面中 不同术语构成，用来描述构件库中的特定构件。通过用户构造描述子形成查 询条件，在构件库中检索符合条件的构件，这样对于用户来说可以直观的从 不同角度指明待检索的构件，有利于用户对构件的理解。 这种分类模式包括了3 个基本的元素：构件描述符、同义词词典以及概 念距离图，如图2 3 所示。构件描述符是一个有序1 1 元组，集合中的每一个 元素对应一个刻面，每个刻面从不同的角度来描述构件。同义词词典是把表 示同一概念的词放在同一个组中，用以消除同义词对检索影响的工具。概念 距离图描述了两个术语间的相似程度。在检索构件时，用户根据