（计算机软件与理论专业论文）业务规则管理系统的研究与实现.pdf

摘要 随着面向对象、数据库和人工智能等技术的快速发展，为了解决传统信息系统中 业务规则的修改和配置造成的效率低下问题，业务规则管理技术成了目前研究的热点。 本文在对现有业务规则管理系统深入研究的基础上，通过对原始规则匹配算法和规则 管理工具的分析与改进，设计并实现了一个业务规则管理系统原型，为业务规则管理 技术的进一步研究与应用提供了技术支持。主要研究工作包括： 1 ) 提出一种可快速访问规则树节点的索引方法。针对原始规则匹配算法效率低下 的问题，在不增加空间复杂度的前提下，提出一种可快速访问规则树节点的索引方法， 提高了规则树的索引速度。 2 ) 提出一种用层次索引和二叉树相结合的方式组织t o k e n 节点树的方法。针对t o k e n 节点访问速度偏慢的缺点，提出一种层次索引和二叉树相结合的组织方式，并应用于 t o k e n 节点树的组织结构，提高了t o k e n 节点的访问速度。 3 ) 改进状态修改的操作过程。针对状态修改操作过程中重复匹配的问题，对状态 修改的操作过程进行改进，减少了规则的匹配操作次数。 4 ) 提出一种形式固定且执行速度较快的规则编辑模式。为使业务分析人员可以方 便地编辑和管理规则，提出了一种形式固定且执行速度较快的规则编辑模式，并设计 了一种可视化的规则管理操作工具，提高了业务分析人员的工作效率。 5 ) 设计并实现规则管理系统原型。用j a v a 语言实现了改进后的规则引擎和规则管 理工具。在此基础上，针对银行贷款领域的特定用户，设计并实现了一个规则应用程 序原型系统，为业务规则管理系统的应用提供了依据。 关键词：r e t e ，规则匹配，规则引擎，规则管理工具，业务规则管理系统 r e s e a r c ha n di m p l e m e n t a t i o no fbu s i n e s sr u l em a n a g e m e n t s y s t e m a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n to fo b j e c t o r i e n t e dt e c h n o l o g y , d a t a b a s ea n da r t i f i c i a l i n t e l l i g e n c e ，i no r d e rt os o l v et h ei n e f f i c i e n c yc a u s e db yt h ec h a n g ea n dc o n f i g u r a t i o nf o r b u s i n e s sr u l e si nt r a d i t i o n a li n f o r m a t i o n s y s t e m ，b u s i n e s sr u l em a n a g e m e n tt e c h n o l o g y b e c o m e sr e s e a r c hf o c u s m a k i n gi n - d e p t hs t u d ya b o u tb u s i n e s sr u l em a n a g e m e n ts y s t e m ，t h e t h e s i si m p l e m e n t e dab u s i n e s sr u l em a n a g e m e n ts y s t e mo nt h eb a s i so fi m p r o v i n gr u l e m a t c h i n ga l g o r i t h ma n db u s i n e s sr u l em a n a g e m e n tt o o l s i ts u p p o r t st h ef u r t h e rr e s e a r c ha n d a p p l i c a t i o na b o u tb u s i n e s sr u l em a n a g e m e n tt e c h n o l o g y m a j o rr e s e a r c hi n c l u d e s ： 1 ) p r o p o s ea 1 1i n d e xb yw h i c hs y s t e mc a n a c c e s sq u i c k l yr u l e t r e en o d e f o ri n e f f i c i e n c y o fo r i g i n a lr u l em a t c h i n ga l g o r i t h m ，t h i st h e s i se s t a b l i s h e da l li n d e xf o rr u l e - t r e eo nt h eb a s i s o fn o ti n c r e a s i n gs p a c ec o m p l e x i t y , b yw h i c h s y s t e mc a l la c c e s sq u i c k l yr u l e t r e en o d e 2 ) p r o p o s ea no r g a n i z e dw a yb yt h ec o m b i n a t i o no fh i e r a r c h i c a li n d e xa n db i n a r y , b y w h i c hs y s t e mi n c r e a s e st h ei n q u i r ya b o u tt o k e n n o d e v i s i t i n gt o k e n n o d ev e r ys l o w l y , t h i s t h e s i so r g a n i z e dt h et o k e n - t r e eb yt h ec o m b i n a t i o no fh i e r a r c h i c a li n d e xa n db i n a r y , w h i c h i n c r e a s e st h ei n q u i r ya b o u tt o k e n n o d e 3 ) i m p r o v et h eo p e r a t i o na b o u tm o d i f y i n gs t a t e f o rt h er e p e t i t i v em a t c h i n go p e r a t i o ni n m o d i f y i n gs t a t e ，t h i st h e s i si m p r o v e dt h eo p e r a t i o na b o u tm o d i f y i n gs t a t e ，b yw h i c hs y s t e m c a nr e d u c et h en u m b e ro fo p e r a t i o na b o u t m a t c h i n gr u l e 4 ) p r o p o s eaf i x e dw a y f o re d i t i n gq u i c k l yb u s i n e s sr u l e s m a k i n gb u s i n e s sa n a l y s t se d i t a n dm a n a g er u l e se a s i l y , t h et h e s i sp r o p o s e daf i x e dw a yf o re d i t i n gq u i c k l yb u s i n e s sr u l e s a n dd e s i g n e dav i s u a lr u l em a n a g e m e n tt o o l ，w h i c hi m p r o v e sw o r ko fb u s i n e s sa n a l y s t s 5 ) d e s i g na n di m p l e m e n tb u s i n e s sr u l em a n a g e m e n ts y s t e m t h et h e s i si m p l e m e n t e d a ni m p r o v e dr u l e e n g i n ea n dr u l em a n a g e m e n tt o o l sb yj a v a t h e ni t d e s i g n e da n d i m p l e m e n t e da na p p l i c a t i o np r o g r a ma b o u tt h ea r e ao fb a n kl o a n sf o rs o m eu s e r s ，w h i c h p r o v i d e sb a s i sf o rt h ea p p l i c a t i o na b o u tb u s i n e s sr u l em a n a g e m e n ts y s t e m k e yw o r d s ：r e t e ，r u l em a t c h i n g ，r u l ee n g i n e ，r u l em a n a g e m e n tt o o l s ，b u s i n e s sr u l e m a n a g e m e n ts y s t e m 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许 论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所等机构将本学位论 文收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：鹜!指导教师签名： f 翌k 皿芝 z 6 ，。年翻现日年月日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本 论文不包含其它人已经发表或撰写过的研究成果，也不包含为获得西北大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 两、仅 沙p 年月1 乙日 西北人学颤：l 学位论文 1 1 研究背景及意义 第一章绪论 在企业业务活动中，除了流程和数据外，还存在着各种各样的约定，甚至还有各种 各样没有文字描述的习俗与惯例，它们都可以作为企业规则的一部分而存在。由于这些 规则都与企业的业务活动相关，因此将它们称为业务规则。随着企业的快速发展，为了 获得更大的赢利和发展，各种商业的运行策略与企业的管理制度等各种规则不可避免地 要发生改变，因此业务规则的调整与变化也在所难免。 在以往的各种信息化系统中，人们通常把业务规则看成是一个普通的逻辑过程，并 将业务规则逻辑作为程序的一部分嵌套在程序代码中。当某些业务规则发生变化时，原 有的软件必须修改相应的代码的测试和重新配置。然而在当今的商业经济社会中，企业 为了适应当前的发展潮流，业务规则通常需要频繁地进行修改。由于业务规则的修改需 要按照传统软件修改模式进行程序代码的修改与测试，这种方法将消耗大量的人力和财 力。更为严重的是，通过修改程序代码来修改业务规则的方式需要较长的时间周期，从 而浪费了大量的时间，企业往往因此错失宝贵的商业机会。因此这种业务规则的修改方 式严重阻碍了企业的发展甚至威胁到了企业的生存。对于上面存在的问题，人们构想是 否可以通过信息提取的模式，将易变的业务规则从程序代码中提取出来，使业务人员可 以像管理一般的数据一样管理业务规则，例如对业务规则的添加、查询、修改等操作。 随着面向对象技术、数据库、人工智能、x m l ( 数据结构的表示) 等技术的快速发展和广 泛应用，一种新的技术业务规则管理技术( b u s i n e s sr u l em a n a g e m e n tt e c h n o l o g y ) 应运 而生f 1 】，这种新的技术结合了最新的计算机开发技术、专家系统技术与业务管理技术， 将逻辑程序代码与业务规则分离开来，程序员负责逻辑代码的编写，业务领域专家和商 业决策者共同来管理这些容易快速变化的业务规则。通过这种技术，人们彻底解决了“业 务规则不断变化、不停修改程序代码这种让企业和软件开发者都为之头痛不已的问题。 基于业务规则的管理系统可以简称为业务规则管理系统( b r m s ，b u s i n e s sr u l e m a n a g e m e n ts y s t e m ) 【2 j 。国外在这方面的起步较早，并已经开发出了一些比较成熟的业 务规则管理系统，如i l o g 公司的j r u l e s 、b l a z e 公司开发的a d v i s o r 等，但它们都是非 常昂贵的商业产品，代码和技术都处于严格的保密状态。国外也有一些开源项目组织从 事相关的研究工作，如j b o s s 公司开发的d r o o l s 等，但它们都不是完善的业务规则管理 l 第章绪论 系统，还有待进一步的研究与开发。 今年来，业务规则管理技术在国内也得到了越来越广泛的应用，产值增长的速度非 常迅速并已经形成了一定的规模1 3 1 。由于我国在这方面的研究和成果都还较少，国内大 都使用国外的产品，因此设计实现我国的基于业务规则的管理系统迫在眉睫。 本文通过对原始规则匹配算法和规则管理工具的分析与改进，设计并实现了一个业 务规则管理系统原型，为我国基于业务规则的管理系统的设计与实现提供了支持。 1 2 国内外现状 业务规则管理系统是用于开发、管理业务规则软件的开发工具。它通过为业务分析 人员提供对业务规则的编辑和管理等操作，在业务规则和软件设计之间为业务分析人员 架起了一座沟通的桥梁。业务规则管理系统的基本思想是将业务规则程序中的业务规则 与数据验证逻辑代码和程序的流程控制代码分离开来。其中数据验证逻辑代码和程序的 流程控制代码通常由专门的程序设计人员进行编写，业务规则通常由业务分析人员进行 编写，并且业务规则在自己的容器“规则引擎 ( r u l ee n g i n e ) 中进行规则的匹配 等操作，同时将规则的匹配结果通过程序的流程控制代码传递给业务规则应用程序的其 它部分进行处理【4 】。由于业务分析人员通常是各行各业的领域专家，他们对程序代码的 编写通常比较陌生，因此业务规则应该通过简单易懂的业务规则管理工具来进行编写。 作为业务规则系统的一个重要组成部分，这些业务规则管理工具应该非常容易被广大用 户理解和学习，即使是不懂编程语言或懂一些编程语言的业务分析人员也能够通过业务 规则管理工具创建并管理这些业务规则。 尽管我国在业务规则管理系统方面的研究和应用都比较晚，但业务规则管理系统在 国外已经经历了较长时间的研究与发展，并且得到了较为广泛的应用f 5 ，6 , 7 , 8 , 9 】。同时业 务规则管理系统的结构模式也逐步地稳定。目前国际上流行的业务规则管理系统通常可 由如下三个主要部分组成： 1 ) 规则引擎：业务规则管理系统的核心组成部分，一种嵌入在业务规则应用程序 中的组件。它的主要任务是把当前提交给规贝l j j i 擎的数据对象与加载在规则引 擎中的业务规则进行规则匹配，并给业务规则应用程序提交匹配后的结果，激 活那些符合当前数据状态下的业务规则，根据业务规则中声明的动作执行相应 的逻辑代码，触发业务规则应用程序中的相应操作。 2 ) 规则管理工具：业务分析人员可以通过规则管理工具创建各种各样的业务规 2 西北 学响i 位论z 则，井可对编写的业务规则进行修改和删除等操作。然而由于业务分析人员通 常是弄个领域的专家他们对程序的编枉通常不是报熟悉因此一个好的业务 规则管理系统应该提供一个比较完善的规则管理工具，并且这些规则管理工具 能够容易被业务分析人员理解和学习，司时可以快速地掌握并进行运用。 3 ) 集成开发环境：由l t 人员( 主要是软件开发人员) 用于创建必要的业务规则 应用程序的软件框架通过此软件框架，软件开发人员可以针对业务规则的应 用建立专门的数据验证逻辑代码和程序的流程控制代码，并且可以通过建立的 应用软件与业务分析人员编辑的业务规则进行各种联系和操作。 业务规则管理系统的组成结构圈如图i l 所示： 囝1 - 1 业务规则管理系统雌组成结构圈 在上述描述的业务规则管理系统的三个主要组成部分中，j 霓| l ! | 引擎部分是业务规则 管理系统的计算核心，其性能的直f 坏直接影响到业务规则管理系统匹配效率的高低。规 则管理工具主要足业务分析人员用来编辑和管理捌则的各种操作接口，它的设计好坏主 要影响到业务分析人员使用业务规则管理系统的难易程度。集成开发环境这一部分主要 涉及的是专业程序员的软件设计开麓工作，软件设计人员为特定的应用设计专门的规则 应用程序软件柬满足用户的使用需求。 规则引擎作为执行业务规则的软件组件足业务规则管理系统的核心，索。规则引 擎的工作和研究重点重要是规则的推理机制和规则的匹配效率。规则引挈常用的算法丰 3 第一章绪论 要有：r e t e 规则匹配算法【l o l 、l e a p s 算法和t r e a t 算法1 1 2 1 。目前国际上的规则引擎产 品使用的算法基本上都是d r c h a r l e sf o r g y 在1 9 7 9 年提出的r e t e 匹配算法及其变体。 r e t e 算法是目前效率最高的一种前向链接( f o r w a r dc h a i n i n g ) 规则匹配推理算法，它的 核心思想是将数据对象通过动态构造的规则树进行规则的匹配，通过这种推理和匹配方 式来达到降低系统计算量的目的。 国外在业务规则管理系统方面的研究和应用都比较早，并且已经研制开发出了一些 基于业务规则管理系统的开源代码，同时多家国外软件公司也为业务规则管理系统领域 开发出了比较成熟的商业性产品。业务规则管理系统近几年在国内也得到了越来越多的 关注与研究，同时也得到了越来越多的使用，应用也变得越来越，泛 1 3 , 1 4 , 1 5 , 1 6 , 1 7 , 1 9 , 1 9 1 。 目前国外较流行的规则引擎开源项目主要有： c l i p s f 2 0 l ( cl a n g u a g ei n t e g r a t e dp r o d u c t i o ns y s t e m ) ：它是由美国航空航天局约翰逊 空间中心1 9 8 4 年推出的规则匹配系统。同时它也是一个基于r e t e 算法的前向链接推理 规则引擎，是通过标准的c 语言实现的。 j b o s sr u l e s 2 1 2 2 1 ：它的前身是c o d e h a u s 的一个开源项目d r o o l s ，最近它被纳入j b o s s 门下，并改名为j b o s sr u l e s ，成为j b o s s 应用服务器的规则引擎。它的规则引擎是通过 对l e a p s 算法和r e t e 算法的结合和改进，用j a v a 编程语言实现的。 目前国外著名的商业性的业务规则管理系统有： j r u l e s 2 3 1 ：是由i l o gs a 公司丌发的一款商业性的软件产品，它是一个著名的基于 j 2 e e 的业务规则管理系统的开发平台，包括高效的规则引擎和易于用户使用的规则管 理工具，它可以很方便地部署到任何j 2 e e 项目中。目前它的应用较为广泛。 。b l a z ea d v i s o r t 2 4 ：是由分析和决策管理技术提供商f a i ri s a a c f a i ri s a a ci n c 研制开发 出的一款商业性的业务规则管理系统，它是一个比较成熟的商业产品，同时提供了j a v a 和n e t 两种开发平台。 j e s s l 2 5 1 ：1 9 9 5 年由美国s a n d i a 国家实验室分布式系统成员e m e s tj f r i e d m a n h i l l 用 j a v a 编程语言实现的一个业务规则管理系统。 h a l e ya u t h o r i t y 2 6 由著名的规则引擎提供商h a l e ys y s t e m si n c 研制的一个业务规 则管理系统的商业软件。它是一个基于w i n d o w s 平台的应用开发软件，同时也提供了 w e bs e r v i c e 开发组件。 西北人学硕：学位论文 1 3 本文主要工作 本文的技术路线如下：通过对课题研究背景和国内外现状的研究与分析，本文提出 和分析了研究与开发业务规则管理系统的需求；通过面向对象的方法对r e t e 规则匹配 算法进行描述与分析，并对r e t e 算法的多个重要部分进行了改进，在对算法改进的基 础上实现了业务规则管理系统的核心组成部分一规则引擎；在实现规则引擎后，为提 高业务分析人员使用业务规则管理系统的便捷性，对现存的规则管理工具进行描述与分 析，在此基础上提出了自己的解决方案并通过编程的方式实现了改进后的规则管理工 具；最终以银行贷款信息管理系统为例，设计并开发了一个基于规则管理的应用系统原 型系统。整个业务规则管理系统在提高规则匹配效率的同时，建立了一个易于业务分析 人员使用的规则管理工具和便于普通用户使用的应用程序。 业务规则管理系统的总体设计流程图可简单描述为下图1 2 所示： 系规则规规则规则 统匹配则管理应用 整算法引丁具程序 体的分擎的设 的实 设析与实计与现与 计 改进现实现应用 图1 2 业务规则管理系统的总体设计流程图 本文完成的主要工作分为如下几个组成部分： 1 分析和改进规则匹配算法：结合面向对象的设计思想和j a v a 编程语言的特点， 第二章对规则匹配算法( r e t e 算法) 的各个组成部分进行描述与分析，并对 r e t e 匹配算法的多个重要组成部分进行了改进。为进一步提高规则的匹配效 率，第三章对规则匹配算法的几个关键组成部分( 规则树，t o k e n 节点树及状 态修改的操作过程) 进行了详细的描述和分析，并提出改进方案。在上述针对 规则匹配算法( r e t e 算法) 改进的基础上，设计了业务规则管理系统的核心组 成部分规则引擎。 2 分析与改进规则管理工具：规则管理工具是业务分析人员用来编辑和管理业务 规则的接口。本文首先对常见的规则编辑形式进行描述与分析，并提出一种编 辑形式固定且执行较快的规则编辑模式；随后根据业务分析人员对规则的操作 设计了一个规则管理工具。 5 第一章绪论 3 以银行贷款领域为例设计了一个应用程序软件模型：为了在具体的应用中使用 前面实现的规则引擎和规则管理工具，针对信用卡申请、房屋贷款和汽车贷款 等领域设计了一个专门的应用程序软件模型。 4 在应用程序软件模型的基础上实现了业务规则管理系统：在规则匹配算法改进 的基础上，用j a v a 编程语言开发出一个具有较高匹配效率的规则引擎；然后 通过对现存业务规则管理工具的分析与改进，提出了规则管理工具的实现方案 并通过编程的方式实现；最后通过使用开发的规则引擎和规则管理工具，建立 了一个部分银行贷款领域的业务规则管理系统的应用程序模型。 1 4 本文组织结构 本文所做的研究工作分为六个部分，主要内容如下： 第一章绪论：本章首先阐述了业务规则管理系统的研究背景与意义，随后描述了 该领域的国内外发展现状并概要性地介绍了本论文所完成的各个主要工作，最后介绍了 本文的组织结构和各章的主要内容。 第二章r e t e 算法的描述与分析：根据面向对象的设计思想与j a v a 编程语言的特 点，通过加入伪代码的方式，本章详细介绍了规则匹配算法( r e t e 算法) 的各个主要组 成部分，并结合自己对r e t e 规则匹配算法的理解与本论文完成的业务规则管理系统的 实现需求，在描述r e t e 算法的过程中对r e t e 规则匹配算法的部分组成内容进行了详细 的分析并提出了一些改进意见。 第三章规则匹配算法的改进：在第二章关于r e t e 规则匹配算法的分析与改进的 基础上，本章对r e t e 规则匹配算法实现过程中需要的两个重要数据结构( 规则树与t o k e n 节点树) 和状态修改的操作过程进行了详细的分析并进行了改进，随后对状态修改操作 过程中的多种操作方式进行分析和对比，并提出了自已的改进意见。 第四章规则管理工具的分析与改进：根据规则管理工具的功能特点，首先对规则 的编辑形式进行描述和分析，提出规则编辑形式的改进意见并确定了规则的编辑形式； 随后结合业务分析人员对规则的操作，设计了一个规则管理工具；最后在对用户状态编 辑模式优缺点分析的基础上，给出了自己的解决方案。 第五章业务规则管理系统的设计与实现：首先介绍了本论文实现的业务规则管理 系统的开发环境，然后概要性地描述了本业务规则管理系统的功能模块，并通过功能模 块图、用例图与类图等来描述业务规则管理系统的设计与实现；最后通过使用本文完成 6 西北入学硕t 学位论文 的规则引擎和规则管理工具，针对信用卡申请、房屋贷款和汽车贷款等银行贷款领域实 现了一个应用程序模型并给出了系统的运行界面。 总结与展望：本章首先对本文目前所做的研究工作进行了一个简要的描述和总结， 随后指出了目前所完成的业务规则管理系统需要改进的方面，这些方面也一定程度地代 表了本领域的发展方向。 7 第二章r e t c 算法的描述与分析 第二章r e t e 算法的描述与分析 在基于业务规则的管理系统中，r e t e 算法是实现规则引擎的理论基础。r e t e 匹配算 法在很多领域有着广泛的应用，例如机器学习，自动医疗诊断等领域，并且在不同领域 的系统实现中，r e t e 算法的表现形式与实现方式也各有不同。本章将结合面向对象的设 计思想和j a v a 编程语言的特点，并借助伪代码的方式详细描述与分析r e t e 算法的各个 组成部分并改进了r e t e 算法。 2 1r e t e 算法概述 在描述r e t e 算法之前，首先介绍几个基本的概念【2 7 1 ：r e t e ( 可以发音为“r e e t 或 者 r e e - t e e ”) 算法在实现过程中首先需要一个状态存储器( w o r k i n gm e m o r y ) 和一个规 则存储器( r u l em e m o r y ) ，状态存储器存储了系统的状态集合，规则存储器中存储的是 系统中业务规则的集合【2 8 ，2 9 1 。且在系统运行过程中，状态存储器中的状态和规则存储器 中的规则都可以动态地发生变化。 状态存储器中存储的状态可以简称为t n e ( w o r k i n gm e m o r ye l e m e n t ) ，每一个w m e 都 表示系统的一个状态，l t 哪l e 的集合代表系统当前的整体状态。在面向对象实现的业务规 则管理系统中，一个状态( 啪) 可以用一个对象表示，例如一个存储了三个状态的 状态存储器如下所示： f a c t if 1 ( i n ti = l ，c h a rc = c ) f a c t 2 忽( d o u b l ed = 1 1 ，s t r i n g 萨“c h e n ”) f a c t 3t 3 ( i n tk = l o ，f a c t lf l ( h a ti = l ，c h a rc = c ” 其中f a c t l ，f a c t 2 ，f a c t 3 为面向对象中的类，f 1 ，亿，f 3 为相应的对象 规则存储器存储了系统中业务规则的集合。在基于r e t e 算法实现的业务规则管理 系统中，规则通常由两个部分组成，其中一部分由一系列的条件组成，可将它们称为规 则的左部分( 1 e f t - h a n ds i d e ) 另一部分由系列的动作组成，可将它们称为规则的右部 分( r i g h t h a n ds i d e ) 。在面向对象的系统实现中，规则的一个条件可以用一个状态对象 表示，动作部分可由一段程序代码表示( 动作部分在特定时l 日j 执行即可，本文后面就不 再介绍) 。因此规则的表示形式可描述为如下所示： ( “r e t e l ”规则的名字 f a c t lf l ( i n ti _ l ，c h a rc = c ) 8 西北大学硕士学位论文 f a c t 2f 2 ( d o u b l ed 21 1 ，s t r i n gs = c h e n ”) f a c t 3f 3 ( i r al c = - 10 ，f a c t1f f l ( i n ti = f 1 i ，c h a rc - - f 1 c ) ) 上面三个对象f 1 ，亿，f 3 表示规则“r e t e l ”的三个条件 f 3 a c t i o n ( ) ) 规则 r e t e l ”的动作部分，a c t i o n 为类f a c t 3 的函数 另一个需要描述的基本概念叫做“变量绑定。变量绑定可解释为规则的一个条 件在执行规则匹配时需要用到该规则前面条件所用的对象。例如在上面描述的规则 r e t e l ”中，第三个条件( f a c t 3f 3 ( i n tk = l o ，f a c t lm ( h a ti - - f 1 i ，c h a rc = f 1 c ) ) ) 在执行规则的 匹配时需要用到该规则的第一个条件所用的对象f l 。在实际的规则中，规则的一个条件 可以绑定多个对象，同时个对象也可以被多个条件绑定。 下面将业务规则管理系统中的规则匹配过程首先如图2 1 所示： 图2 1 规则匹配过程 如上图2 1 所示，r e t e 算法被描述为一个黑盒子( b l a c kb o x ”) ，它由两个输入部分 和一个输出部分组成，其中一个输入部分表示对规则的各种操作，包括对规则的增加、 修改与删除等操作；另一个输入部分表示对状态的增加、修改与删除等操作；输出部分 为执行满足规则匹配的规则动作。在系统运行匹配的过程中，匹配结果会通过特定的形 式进行保存，当一个规则的所有条件都得到满足时，此规则的动作就存入动作存储器中 ( a c t i o n ，m e m o r y ) 。当系统的匹配操作完成后，就可以根据规则的属性动态地执行动作 存储器中的动作1 3 0 】。 前面简要描述了利用r e t e 算法实现的规则引擎在进行规则匹配时的操作流程，下 面将通过图2 2 详细描述r e t e 算法的规则匹配流程。 9 第二帝p e t e 算法的描述与分析 状态存储器中的状态如下：( f a c t i ，f a c t 2 ，f a c t 3 为面向对象的类) f a c t lf l ( i n ti - l ，c h a rc 一c )f a e t lt 2 ( i n ti = 2 ，c h a rc 2 h ) f a c t lf 3 ( i n ti = 2 ，c h a rc = h )f a c t 2f 4 ( d o u b l ed - - 1 1s t r i n gs _ - - 。c h e n ”) f a c t 3f 5 ( c h a rc - c ，f a c tf l ( i n ti = 2 ，c h a rc = l h ” 规则存储器中存储了两个规则，如f 所示： “r u l e l ”( f a c t if l ( i n ti - - - 2 ，c h a rc - - h ) ，f a c t 2f 2 ( d o u b l ed = 1 1s t r i n gg = - t h e n ”) f a e t 3t 3 ( c h a rc = c ，f a c tf l ( i n ti - - f 1 i ，c h a rc = f 1 c ) ) r u l e 2 ”( f a c t lf l ( i n ti = l ，c h a rc = 一c ) ，f a c t lf 2 ( i n ti - - 2 ，c h a rc - - - - - h ) f a c t 2f 3 ( d o u b l ed = l 。1 ，s t r i n gs - - c h e r t ” b e t a 部分r a 1 p h a 部分 i 状态进入系统 a l p h a 、网络 图2 - 2r e t e 算法匹配流程 如图2 2 描述，r e t e 算法的规则匹配过程是一个数据流所组成的网络图f 3 1 ，3 2 3 3 1 。该 网络图主要由两部分组成，分另, j n q 做a l p h a 网络部分( 图2 2 的右边部分) 和b e t a 网络部 分( 图2 - 2 的左边部分) 。a l p h a 网络部分主要是根据进入系统的状态动态地执行规则单 1 0 西北人学硕士学位论文 个条件的匹配，并将匹配成功的结果存入a l p h am e m o r y 存储器中。a l p h am e m o r y 存储 器中存储的是系统中的状态对象，a l p h am e m o r y 存储器中储存的每个对象( 里面可以 存储对缘或别的信息，后面章节将详细介绍) 都通过了相应规则的单个条件的匹配。b e t a 网络部分执行满足变量绑定的多个条件的结合，并将结果存入b e t a 存储器中。b e t a 存 储器通过存储这些匹配了规则部分条件的状态集合来确定规则匹配的完成程度，这些已 经匹配的部分条件的集合称为t o k e n 节点。当规则的全部条件都匹配成功时，规则引擎 就不再将匹配的结果通过t o k e n 节点的形式存入b e t a 存储器，而是将该规则的动作节点 ( 或者别的信息，后面将详细讨论) 存入动作存储器，当规则的匹配操作完成后，系统 将动态地执行动作存储器中的动作节点【3 4 l 。 如上图2 2 的描述，当新的状态进入系统时，首先根据a l p h a 网络中的规则树( 规 则树由规则建立而成，2 3 节将详细介绍) 进行规则的条件匹配，并为匹配成功的条件 和状态建立w m e 节点并存入到a l p h a 存储器中，然后将新建的w m e 节点和b e t a 存 储器中的t o k e n 节点进行结合，并将新产生的t o k e n 节点存入b e t a 存储器中。因此当从 状态储存器中删除状态时，首先需删除a l p h a 存储器中相应的w m e 节点，还需删除和 此w m e 节点结合产生的b e t a 存储器中的t o k e n 节点和动作储存器中相应的动作节点。 每当状态存储器中的状态发生改变时，状态的改变首先通过a l p h a 网络部分，同时 引起a l p h a 存储器中相应存储状态的变化，a l p h a 存储器中的变化将通过上图2 2 中的 数据流引起b e t a 存储器和动作存储器的变化。在上述一系列的运动中，发生在a l p h a 存 储器中的运动叫做右运动，发生在b e t a 存储器中的运动叫做左运动。虽然两种运动通 常发生在不同的节点中，但b e t a 部分中的j o i nn o d e 节点将产牛这两种形式的运动，当 a l p h a 存储器中的w m e 节点通过a l p h a 网络部分连接j o i nn o d e 节点时将产生右运动， 从b e t a 存储器中的t o k e n 节点通过b e t a 网络部分连接i o i nn o d e 节点时将产生左运动。 本章后面的其余章节将详细描述r e t e 匹配算法的各个组成部分。为了更好地讲述 r e t e 算法，本文将结合伪代码的方式描述r e t e 算法需要的主要几个数据结构，并且随 着讨论的深入，后面章节可能会修改前面章节描述的伪代码。其中2 2 节将描述r e t e 规 则匹配算法中用到的几个主要存储节点，2 3 节讨论增加规则时，规则引擎如何动态地 建立规则树，2 4 节讨论状态进入业务规则管理系统时，规则引擎如何根据前面建立的 规则树进行规则匹配操作，2 5 节将描述删除状念时规则引擎的工作情况，2 6 节阐述了 删除规则时规则引擎进行的操作，2 7 节将讨论带否定条件的规则如何进行规则的匹配 等操作，最后2 8 节对本章描述的内容进行了小结。 1 1 第_ 二章r e t e 算法的描述与分析 2 2 存储节点 本节将描述a l p h a 存储器和b e t a 存储器用到的几个主要的存储节点。其中a l p h a 存储器存储了一系列的w m e 节点。b e t a 存储器存储例了一系列的t o k e n 节点，并且t o k e n 节点由w m e 节点的集合组成。 2 2 1a l p h a 存储节点 。通过前面章节的描述可知，每个w m e 节点存储了当前系统的一个状态，本文将用 一个对象来表示系统的一个状态，首先给出w m e 节点的数据结构可如下所示： ( s t r u c t u r ew m e o ：o b j e c t 通过对象表示系统的状态 e n d ：) 由于a l p h a 存储器中存储的是一系列的w m e 节点，可将a l p h a 存储器看作是w m e 节点的集合，所以a l p h a 存储器的数据结构首先如下所示： ( s t r u c t u r e a l p h a - m e m o r y i t e m s ：l i s to f w m ew m e 节点组成的链表 e n d ：) 新的w m e 节点进入系统将会产生前面描述的右运动，在此右运动的过程中，可以 简单地将新加入的w m e 节点插入到a l p h a - m e m o r y 数据结构中的i t e m s 引用的开头，具 体的操作过程可如下所示： ( p r o c e d u r e ：i n s e r tw m e ( n o d e ：a l p h a - m e m o r y ，w ：新的w m e ) i n s e r tw a tt h eh e a do fn o d e i t e m s e n d ：) 2 2 2b e t a 存储节点 在基于r e t e 算法实现的规则引擎中，常见的t o k e n 节点的存储方式有两种，一种是 通过数组的方式存储，一种是通过链表存储。在不同的系统实现中，两种存储方法各有 优缺点，下面在面向对象的实现中，比较两个存储方式的优缺点。 当t o k e n 节点选用数组存储时，每个t o k e n 节点都需要存储前面条件的w m e 节点 和当前条件的w m e 节点。假如一个规则由k 个条件组成，第二个条件的t o k e n 节点仅 需存储一个w m e 节点；第二个条件的t o k e n 节点需要存储前面条件的w m e 节点和当 1 2 西北人学侦 ：学位论文 前条件的w m e 节点( 如图2 2 ) ，因此第二个条件的t o k e n 节点需要存储两个w m e 节 点。依次类推第i ( i ；k ) 个条件的t o k e n 节点需要存储i 个w m e 节点。当一个规则 的所有条件都经过匹配得到满足时，至少需要k 个t o k e n 节点来存储规则的t o k e n 节点， 需要存储的w m e 节点个数可计算为1 + 2 + 3 + 十k = o ( k 2 ) 。另外当第i ( i ：k ) 个条 件又一次经过匹配得到满足时，又需为规则的第i 个条件添加一个t o k e n 节点。由此可 知，当第i 个条件的t o k e n 节点建立时，首先需要拷贝上一个t o k e n 节点的内容，然后再 添加当前条件所产生的w m e 节点。因此用数组的方式存储t o k e n 节点时，需要存储大 量重复的w m e 节点，同时也将消耗大量的空间申请时间和w m e 节点拷贝所需的时间。 而且由于t o k e n 节点可以动态地修改和删除，t o k e n 节点的修改和删除也需消耗不少的资 源。但是当选用数组的方式进行存储时，可以随机地访问数组中的元素，特别是涉及变 量绑定的条件匹配时，t o k e n 节点的查找速度可以得到提升。 当选用链表方式存储t o k e n 节点时，每个t o k e n 节点仅需存储当前条件的w m e 节 点，通过链接的存储方式，各个子t o k e n 节点可以共用父t o k e n 节点的信息，此时t o k e n 节点将变成一棵t o k e n 节点树。通过链表的方式存储t o k e n 节点，由于每个t o k e n 节点仅 需要存储一个w m e 节点，因此可以节省大量的空间和由于状态不断变化带来的空闻申 请和释放所消耗的系统资源。但是由于通过链表方式存储的t o k e n 节点不能随机访问， 当涉及变量绑定的条件匹配时，只能通过遍历链表的方式寻找前面条件的状态对象。 通过上面的描述和分析，结合以前规则引擎的研究与应用【2 7 】，本文选用链表的方式 存储t o k e n 节点，因此t o k e n 节点的数据结构首先如下所示： ( s t r u c t u r et o k e n w i n e ：w m e 当前条件的w m e 节点 c h i l d ：l i s to f t o k e n子t o k e n 节点列表 p a r e n t ：t o k e n 父t o k e