（计算机应用技术专业论文）axml的重写优化的研究与在计划排产中的应用.pdf

e 论文题目： 内蒙古科技大学硕士学位论文 作者： 赵菲 指导教师：壁 协助指导教师： 型垫望单位：鬯茎立型垫奎兰 单位： 单位： 论文提交日期：2 0 1 0 年0 6 月1 2 日 学位授予单位：内蒙古科技大学 e a x m 的重写优化的研究与在计划排产中的应用 i n p l a ns c h e d u l i n g 研究生姓名：赵菲 指导教师姓名：高永兵 内蒙古科技大学信息工程学院 包头0 1 4 0 1 0 ，中国 c a n s i s a t e ：z h a of c i s u p e r v i s o r ： g a oy o n g - b i n g s c h o o lo f i n f o r m a t i o ne n g i n c c r i n g i n n e rm o n g o l i au n i v c r s i 秒o fs c i e n c ea n st e c h n o l o g y b a o t o u0 1 4 0 1 0 ，p i l c h 烈a ，l一 。 卜 l i 内蒙古科技大学硕十学位论文 摘要 随着i n t e m e t 的快速发展，尤其是w e ；b 服务技术、电子商务等的广泛使用， x m l 作为一种自描述的半结构化数据模式已成为w e ；b 数据表示和交换的新标准，越 来越多的信息处理系统采用x m l 文档作为信息存储、交换和发布的载体，x m l 类 型的数据已成为当前主流的数据形式。有了x m l 和w e bs e r v i c e s ，在网络上分布信 息变得很容易。x m l 和w e bs e r v i c e s 正在成为有价值的动态的更新信息资源的标 准。这些标准的急速扩展必然导致新一代x m l 文档的产生，即a c t i v ex m l 文档。 a c t i v ex m l 定义为一种分布式信息管理语言，是对x m l 的扩展，其主要思想 是在x m l 文档中嵌入w e bs e r v i c e s 调用，实现对w e bs e r v i c e s 资源的动态访问，但 语法上仍是有效的x m l 文档。一个a c t i v ex m l 文档包含两种信息，在文档中直接 表示出来的数据称为“显式数据”，以w e bs e r v i c e s 调用表示的数据称为“隐含数 据”。由于x m l 文档中引入嵌入式w e bs e r v i c e s ，增加了文档的动态性和灵活性。 然而，也带来了诸多新问题，如文档重写、a c t i v ex m l 文档查询、文档包含及服务 调用可终止性问题等。 本文结合树形有限自动机的特点，分析和研究了目前解决x m l 的重写的方法， 根据w e bs e r v i c e s 的相关标准，提出了基于树自动机技术的解决a c t i v ex m l 重写的 处理方法。该方法通过将a c t i v ex m l 文档定义成树，并把a c t i v ex m l 文档或模式 中的函数结点或数据结点定义成树自动机中的状态结点，根据对这些带有函数标签 的状态结点，通过算法进行检测，看是否在文档或模式重写时能完全的符合目标模 式，有效地实现a c t i v ex m l 的完全重写。本文通过利用计划排产中的实例，对本算 法进行了阐述。 最后对本文涉及的方法进行了性能测试，实验结果表明树自动机技术可以有效 地解决a x m l 文档的完全重写问题，而且提出的新方法在计划排产的性能上要优于 传统方法。 关键词：a c t i v e 舭；重写； - t - b j 排产；树自动机 内蒙古科技人学硕+ 学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e t , e s p e c i a l l yt h ew i d e s p r e a du s eo fw e bs e r v i c , c s t e c h n o l o g ya n de - c o m m e r c e ，x m l a si ts e l f - d e s c r i b e da n ds e m i s t r u c t u r e dd a t am o d e lh a s b e c o m et h en e ws t a n d a r d so fw e bd a t ar e p r e s e n t a t i o na n de x c h a n g e m o r ea n dm o r e i n f o r m a t i o np r o c e s s i n gs y s t e mu s e sx m ld o c u m e n t sa st h ev e c t o ro fi n f o r m a t i o ns t o r a g e , e x c h a n g ea n dd i s s e m i n a t i o n x m lt y p e so f d a t ah a v eb e c o m et h em a i n s t r e a mo fd a t af o r m b e c a u s eo fx m l , a n dw e bs e r v i c e s d i s t r i b u t i o ni n f o r m a t i o no nt h en e t w o r kb e c o m e sv e r y e a s y x m l a n dw e bs e r v i c e sh a v eb e e nt h ei n f o r m a t i o nr e s o u r c es t a n d a r do fv a l u a b l ea n d a b l et ou p d a t ed y n a m i c a l l y t h er a p i de x p a n s i o no ft h e s es t a n d a r d si n e v i t a b l yh a sl e a dt oa n e wg e n e r a t i o no fx m ld o c u m e n tg e n e r a t i o n ，n a m e l yt h ex m ld o c u m e n ta c t i v e x m l 4 a x m l ) d o c u m e n t a x m li sd e f i n e da sad i s t r i b u t e di n f o r m a t i o nm a n a g e m e n tl a n g u a g e , a nx m l e x t e n s i o n i t sm a i ni d e ai st oe m b e dx m ld o c u m e n t si nw e bs e r v i c e sc a l l st or e a l i z et h e d y n a m i ca c c e s st ow e bs e r v i c e sr e s o u r c e s b u ti ti ss t i l lv a l i dx m l d o c u m e n tp h r a s e o l o g i c a l a na x m ld o c u m e n tc o n t a i n st w ok i n d so fi n f o r m a t i o nt h a tc a m eo u td i r e c t l yi nt h e d o c u m e n td a t ai sc a l l e d ”e x p l i c i td a t a ”a n di nw e bs e r v i c e si n v o k i n gi sr e f e r r e dt o 勰 h i d d e nd a t a ”s i n c et h ei n t r o d u c t i o no ft h ee m b e d d e dw e bs e r v i c e si nx m ld o c u m e n t t h e r ei sa l li n c r e a s ei nt h ed y n a m i ca n df l e x i b l ea s p e c t s h o w e v e r , i ta l s ob r i n g sm a n yn e w p r o b l e m s ，s u c ha sd o c u m e n t a t i o nr e w r i t e , a x m ld o c u m e n tq u e r i e s ，d o c t m a e n t si n c l u d i n g a n dt e r m i n a t i o no f s e r v i c ec a l l sa n ds oo i l t h i sp a p e rc o m b i n e st h ec h a r a c t e r i s t i c so ft r e ea u t o m a t a , a n a l y z e sa n dr e s e a r c h e st h e c u r r e n tr e w r i t i n ga p p r o a c ht os o l v ex m l a c c o r d i n gt ot h er e l e v a n ts t a n d a r do fw e b s e r v i c e s ，t h ea p p r o a c hb a s e do nt r e ea u t o m a t at e c h n i q u e si sp r o p o s e dt os o l v ea x m l r e w r i t i n g t h em e t h o dd e f i n e sa na x m ld o c u m e n t 鹤a 毗a n df u n c t i o nn o d e so rd a t a n o d e si na x m ld o c u m e n to rm o d e l 雒t h es t a t en o d e si nt r e ea u t o m a t a a e c o r d i i n gt ot h e s t a t en o d e sw i t ht h ef u n c t i o nl a b e ln o d e , b yt h ea l g o r i t h mt e s t , i ti st os e ei ft h ed o c u m e n to r m o d er e w r i t t e nc a nc o m p l e t e l ya c c o r dw i t ht h et a r g e tm o d et oe f f e c t i v e l yr e a l i z ea x m l c o m p l e t er e w r i t i n g t h i sp a p e rd e s c r i b e st h ea l g o r i t h mb yu s i n gt h ee x a m p l eo fp r o g r a m s e h e d u l i n 吕 f i n a l l y , w et e s tt h ea l g o r i t h mi n v o l v e di nt h ep a p e r e x p e r i m e n t a lr e s u l t ss h o wt h a tt h e t r e ea u t o m a t at e c h n o l o g yc a ne f f e c t i v e l ys o l v et h ep r o b l e ma x m ld o c u m e n t sr e w r i t t e n c o m p l e t e l y , a n dt h ep r o p o s e dn e wm e t h o d i ss u p e r i o rt ot r a d i t i o n a lm e t h o d si l lp e r f o l i i l a n c e k e yw o r d s - a x m l ；r e w r i t i n g ；p l a ns c h e d u l i n g ；t r e ea u t o m a t a l-il 目录 摘要i a b s t r a c t i i 1 者论1 1 1 背景知识1 1 2a x m l 的产生3 1 3a x m l 的研究现状4 1 4 研究意义6 1 5 课题的研究内容舌 1 5 1 课题要解决的问题6 1 5 2 课题的研究思路7 2a x m l 的简介8 2 1 定义a x m l 文档8 2 2a x m l 的模式9 2 3 重写的简介1 1 2 4a x m l 站点1 1 2 4 1 作为用户的a x 匝站点1 2 2 4 2a x m l 站点作为服务器。1 4 3 删l 的重写及其优化18 3 1 删l 文档的重写1 9 3 1 1a x m l 重写的技术基础2 0 3 1 2a x m l 文档重写的具体解析2 0 3 2 文档的安全重写算法2 1 3 3 对于a x m l 可能的重写优化2 4 3 3 1 树自动机理论2 5 3 3 2 文档的递归终止性检验。2 5 3 3 3a x m l 文档的可重写性检验2 8 3 3 4a x m l 模式的重写算法。3 0 4 删l 重写的应用3 3 4 1 计划排产3 3 4 2 计划排产技术3 3 4 3a x m l 重写在单件车间计划排产中的应用3 5 5 实验测试与结果评价3 9 5 1 实验环境：3 9 5 2 实验结果3 9 内蒙古科技人学硕+ 学位论文 结论。z 1 2 参考文献。4 3 在学研究成果4 6 致谢。，4 7 - 2 内蒙古科技大学硕士学位论文 1 绪论 1 1 背景知识 1 x m l 随着i n t e r n e t 的快速发展，尤其是电子商务、w e ；bs e r v i c e s 等应用的广泛使用， x m l 已成为w e b 数据表示和交换的新标准，越来越多的信息处理系统采用x m l 文档 作为信息存储、交换和发布的载体，x m l 类型的数据已成为当前主流的数据形式。 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) l l j ，即可扩展标记语言，是一套定义语义标记 的规范，这些标记将文档分成许多部件并对这些部件加以标识，其目标是能够定义计算 机和人都能方便识别的数据类型。它作为一种结构化数据模式，x m l 具有自描述性、 简单易用、可扩展性和平台无关性等特点，能以可读的格式表示数据而不受表现形式的 限制。 x m l 的出现和使用，有可能从根本上改变在互联网环境下的数据交换和信息共享 的形式。x m l 提供描述结构化数据的格式，是一种用来描述数据的语言。x m l 提供了 一种独立于应用程序的方法来共享数据，它是一种新的用来自动描述信息的标准语言。 x m l 提供了一种通用的标准来表现数据，能增加结构和语义信息，使得计算机可以及 时处理多种形式的信息。 1 ) 域名空间 x m l 是一种元标记语言，允许用户定义自己的标记，因此，很可能出现名称重复 的情况。为了解决这个问题，w 3 c 在1 9 9 9 年1 月颁布了域名空间( n a m es p a c e ) 【2 】标 准。该标准对域名空间的定义是：x m l 域名空间提供了一套简单的方法，将x m l 文 档和u r l 引用标记的名称相结合，来限定其中的元素和属性名。由此可知它通过使用 u r l ，解决了x m l 文档中标记重名的问题，从而确保任何一篇x m l 文中使用的名字 都是全球范围内独一无二的。原则上一个不使用域名空间的x m l 文档是一个实用意义 不大的文档，因为在全球范围内很可能有和它同名的标记存在。在本文中利用不同的域 名来区别工件名称和它的生产状况。 2 ) x m l 的文档模式 首先，d t d ，文档类型定义 3 1 ( d o c m n e n tt y p ed e f i n i t i o n s ，d t d ) ，就是定义一种 标记语言。主要包括一门标记语言由几部分组成，该语言都是由哪些标记构成的，这些 标记的嵌套关系如何，该语言中是否存在实体，标记中是否可用属性，属性的取值该如 何指定，简言之就是合法的x m l 文档的规则所在。 内蒙古科技人学硕十学位论文 其次，x m ls c h e m a ，虽然d t d 在校验x m l 文档的有效性方面非常有用，但它仍 然存在许多问题，例如采用了非x m l 的语法规则、不支持多种多样的数据类型、扩展 性较差等，这些缺陷使d t d 的应用受到了很大的限制。为了解决上述问题，以 m i c r o s o f t 公司为首的众多公司提出了x m ls c h 锄a 【4 1 。x m ls c h e m a 建立在x m l 之 上，它的样子和一般的x m l 文档完全相同，使得x m l 达到从内到外的完美统一。 3 ) l 的查询 首先，x p a t h t 5 期是制定x m l 技术规范标准的、w 3 c 推出的x m l 文档寻址语言， 在1 9 9 9 年11 月x p a t h l 0 就已经成为w 3 c 的推荐标准，目前已经推出了x p a t h 2 0 的工 作草案。x p a t h 的出现给x m l 文档的查询提供了规范。 ( p a t h 中的基本语法单元是和 传统计算机文件系统路径相似的位置路径表达式( l o c a t i o np a t he x p r e s s i o n ) 。通过 它，我们可以精确的查找到x m l 元素节点的位置。位置路径表达式可以有两种表示： 绝对路径和相对路径。 其次，x q i l 哪即是由w 3 c 定义的，用于从x m l 文档中寻找和提取元素和属性的 语言，它是x m l 数据的查询语言，它和x m l 的关系相当于s q l 与数据库。x q u e r y 是建立在x p a t h 表达式的基础上的。x q u e r y l 0 和x p a t h 2 0 有相同的数据模式，并支持 相同的函数和操作。 x q u e r y 中最重要的就是f l w o r 表达式，其中f l w o r 是“f o r ，l e t ，w h e r e ， o r d e rb y ，r e t u r n ”的首字母缩写。 x p a t h 路径表达式： b i b # b o o k a u t h o r = a s l e t i t l e 选择在b i b 元素下的b o o k 元素下所有a u t h o r 元素值等于a s l e 的r i f l e 元素。 f l w o r 表达式会和上面的路径表达式所选择的结果相同： f o r $ xi nd o c ( b i b x m l ) b i b b o o k w h e r es x a u t h o r = a s l e r e t u r n $ x t i t l e 由此可见，x q u e r y 是基于x p a t h 上的，单独的x p a t h 位置路径本身就是有效的 x q u e r y 。 2 w e bs e r v i c e s w e bs e r v i c e s t 8 】是建立可互操作的分布式应用程序的新平台。w e ；bs e r v i c e s 平台需要 一套协议来实现分布式应用程序的创建。任何平台都有它的数据表示方法和类型系统。 要实现互操作性，w e bs e r v i c e s 平台必须提供一套标准的类型系统，用于沟通不同平 台、编程语言和组件模式中的不同类型系统。在传统的分布式系统中，基于界面 ( i n t e r f a c e ) 的平台提供了一些方法来描述界面、方法和参数( 如c o m 和c o b a r 中 的i s l 语言) 。同样的，w c bs e r v i c e s 平台也必须提供一种标准来描述w 曲s e r v i c e s ， 内蒙古科技火学硕十学位论文 让客户可以得到足够的信息来调用这个w e bs e r v i c e s 。最后，还必须有一种方法来对这 个w e bs e r v i c e s 进行远程调用。这种方法实际是一种远程过程调用协议( r p c ) 。为了 达到互操作性，这种r p c 协议还必须与平台和编程语言无关。下面几个小节就简要介 绍了组成w e bs e r v i c e s 平台的这三个技术。 1 ) s o a p 简单对象访问协谢9 】( s o a p ) 提供了标准的r p c 方法来调用w e bs e r v i c e s 。s o a p 意味着w e bs e r v i c e s 是以对象的方式表示的，s o a p 规范定义了s o a p 消息的格式， 以及怎样通过h 兀甲协议来使用s o a p 。s o a p 也是基于x m l 和x s s 的，x m l 是 s o a p 的数据编码方式。 2 ) w s d l w s d l ( w e bs e r v i c ed e s c r i p t i o nl a n g u a g e ) 【1 0 咐西服务器描述语言是用x m l 文档 来描述w e ；b 服务的标准，是w e b 服务的接口定义语言，由a r i b a 、i n t e l 、m m 、m s 等 共同提出，通过w s d l ，可描述w e b 服务的三个基本属性：( 1 ) 服务做些什么服 务所提供的操作( 方法) ；( 2 ) 如何访问服务一和服务交互的数据格式以及必要协 议；( 3 ) 服务位于何处协议相关的地址，如u r l 。 w s d l 文档以端口集合的形式来描述w c b 服务，w s d l 服务描述包含对一组操作 和消息的一个抽象定义，绑定到这些操作和消息的一个具体协议，和这个绑定的一个网 络端点规范。 1 2a x m l 的产生 a c t i v ex m l 】是由法国自动化所s e r g ea b i t e b o u l 等人于2 0 0 2 年提出，目前s e r g e a b i t e b o u l 等人在a c t i v ex m l ( 以下简称m m 几) 方面的开展了大量的研究与应用工作：在 数据集成方面，他们提出种基于a x m l 和w 曲s e r v i c e s 的w e b 规模的x m l 数据集成基 本框架，与传统w e b 数据集成方案相比，使分布式数据的获取变得更加灵活，支持 w r a p l x x 的异步操作；在分布式工作空间管理方面，他们为嵌入调用设计了更多参数，如调 用方式( 实时还是定时) ，重写规则( 如何数据重写嵌入调用) 等；还将其用在分布式电 子病历方面，在保证病历完全和病人隐私的前提下实现了共享。现在所进行的工作m s p 2 p ( m a s s i v ed a t ai np e e r - t o - p e e r ) 系统，即个n a t i v ea x m l 数据管理系统，主要用于p 2 p 系统。国内有_ 些学者近两年也加入了a c t i v ex m l 的研究行列，如重写方面的研究和情报 管理方面的应用。 a x m l 定义为一种分布式信息管理语言，是对x m l 的扩展，其主要思想是在 x m l 文档中嵌入w e bs e r v i c e s 调用，实现对w e bs e r v i c e s 资源的动态访问，但语法上 内蒙古科技人学硕士学位论文 仍是有效的x m l 文档。一个a c t i v ex m l 文档包含两种信息，在文档中直接表示出来 的数据称为“显式数据 ，以w e ；bs e r v i c e s 调用表示的数据称为“隐含数据”。 a x m l 的本质是很简单的，它是一个有效的x m l 文档，其中某些特殊的元素( 如 例子中的标签s o ) 是作为服务调用插入的。这些元素的存在使得文档变得隐含了，因此 有某些是显式给定的数据，而某些是隐式给定的，通过调用获得数据。a x m l 文档也 可以看成是动态的。由于外部数据的改变，相同的调用可以获得不同的数据，在不同时 间的相同文档会有不同的语义，同时也可能反映世界的变化。 调用返回的新数据作为s c 元素的兄弟元素插入文档中或直接替换原有文档( 下面 会详细介绍) 。因此，调用w e bs e r v i c e s 修改( 典型为丰富) 文档，并且调用的重复激 活可以更新信息，使得文档更加丰富。 嵌入调用的思想在数据库中并不新颖：( 1 ) 关系系统支持程序的属性，即被某些 编码定义的关系中的列表；( 2 ) 在对象数据库中的对象已经附上了函数。例如： m a c r o m e d i am x 1 2 j 或a p a c h ej e l l y t l 3 】，他们也允许在文档中包含w e bs e r v i c e s 调用。 a x m l 的典型目的是集成些自主的非均匀的资源提供的信息并能查询他们。通 常要在数据集成例子中区分出两个主要的内容：数据仓库和相对的介质。前者由感兴趣 的、来自于外部资源的数据副本和部分工作在这个数据上的副本组成，然而后者依靠查 询重写机制在查询时从资源获取必要的数据。除了数据集成，其目的还在于促进基于详 细的分布式的数据的分布式应用的配置。 1 3a x m l 的研究现状 在介绍研究现状之前，先来描述一下数据集成，目的是为了与a x m l 进行区别。 数据集成系统由提供中介信息的数据源和相关数据进行整合。前者和后者的区别表现在 一个模式的水平( s c h e m al e v e l ) 上，在源数据模式和集合模式中映像 1 4 , 1 5 1 。用这些模式 把集合模式的队列翻译成源点的队列。 最近语义载体也受到了关注，集合包含实体【1 6 1 。这种关联的主要不同在于集合模式 的数据模式被解释成o w l r 7 1 ，一种面向对象数据模式，它有继承的特性。实体队列的 形式体系通常有不同种类的解密逻辑【1 8 1 ，这种关联同时也需要不同的重写技术【1 9 1 。 对比基于模式和基于实体的方法，a x m l 经常用于直接数据源信息的链接。这种 方法是动态的，应为在调用的时候发现一种源点，与传统数据在重写技术上是互补的， 目的是处理源点间的语义异构性。 在传统的数据集成系统里，队列中的源点是允许被访问的。在a x m l 里源点有更 多的限制，因为他们只显示一个特殊的被定义成标签的函数在w s d l 定义中有显示。 把这些函数能看作是在源数据参数队列里中定义的，用绑定的形式完成，因为变量一定 4 内蒙古科技人学硕士学位论文 要绑定才能够赋值给它。一个最新的程序【2 0 】采用了可变化方法，与传统的数据集合接 近，w e ；bs e r v i c e s 把队列看成单个参数，他们的标签用来限制允许的队列。 a x m l 模式是动态的自组拓扑网，主要与嵌入在a x m l 文档中的服务调用指令一 致。因为a 3 3 v i l 服务结果中表达着服务的调用指令。第三章中会介绍a x m l 系统的对 称角色，数据源和部分实现其他节点，为数据集成嵌入一个更加灵活和可扩展的网络结 构。w e bs e r v i c e s 被用作异构数据源点包装器，也提供了恢复数据的方法。模式数据的 转换和语义集合开发的工具能够作为w c ；bs e r v i c e s 来丰富a x m l 的框架。 能实现服务调用，使a x m l 文档具有隐式性是a ) 0 i ，文档的主要特征，其中一些 数据是明确给出的。隐式信息在d a - t a l 0 9 2 l 】环境下是经常被用到。显式数据库是由常量 组成，而隐式数据库由一套预先定义的节点队列组成。在隐式信息环境下有一个重要的 问题是：给定一个评估队列，假设一个算法叫m a g i cs e t s 冽和q i u e 妒s u b q i u 奶，【2 3 1 ，对它 的实现是否包含最小数量的隐式信息。 a x m l 用服务调用的输出作为另一个的输入也能够撰写服务，还能在这些组合的 基础上定义新的服务，也就是a x m l 不是服务组合的框架而是用w e bs e r v i c e s 的分布 数据管理。 文献【2 4 】中提到了在l o r e l 2 5 】和对象数据库的显式里用外部函数来处理半结构数据， 在x m l 数据里介绍外部调用。在这里服务调用也能够被嵌入到o f f i c e 文档，主要是通 过提供背景工具丰富用户要求的内容，目标是在一个分布式程序里用提供给w e ；b s e r v i c e s 调用的控制和丰富方式。也提到了其他基于嵌入式w e bs e r v i c e s 的x m l 语言 系统，例如文献【2 6 】和文献【2 7 1 。 在关联数据库里，t d g g e r s 的用法和服务调用是更有关联性的。a c t i v e 规则最近也 被用在x m l x q u e r y 环境里，并且也在研究w e ；bs e r v i c e s 调用指令困】，其目的是想在 w 曲s e r v i c e s 框架里得到数据集合。 但是和a c t i v ev i e w s 2 9 1 不同的是a x m l 提供节点到节点的关系，通过一个中央重 置来相互制约，a x m l 的基石是x p a t h 、q u e r y 、w e bs e r v i c e s 和对象数据库。 s e r g ea b i t e b o u l 等人最近研究了通过在应用间交换这种隐含x m l 文档引起的新问 题，和文档中数据是否在发送前被重写。这个工作在a x m l 系统和语言中也会被涉及 到。系统中是a x m l 文档，也就是隐含的x m l 文档，其中的调用，典型表示为查询 或更新。描述了基本的在交换常规的x m l 数据和交换隐含的x m l 数据间的不同。目 前隐含文档有一个关键的性质：由于w e bs e r v i c e s 可以在网络上的任何地方被调用，不 再需要重写全部的隐含数据。相反的，有一种更灵活的数据交换范例，其中发送者发送 一个隐含的文档并让接收者当需要的时候自由的重写数据。应用一种综合的方法，确定 某些数据在文档发送前被发送者重写，而某些被接收者重写。 内蒙古科技人学硕士学位论文 在国内，郝忠孝，马海涛，朱燕等人也研究了基于树自动机的a x m l 模式重写， 并证明了该算法的优越性。本文就是根据树自动机的a x m l 重写进行优化，并将其应 用于计划排产中，实现了工件的快速、有效的排产。 1 4 研究意义 a ，文档的最大特点是可以像普通的x m l 那样成为一种数据交换模式，也就是说 嵌入在a x m l 文档中的w e bs e r v i c e s 调用可以被用来交换，使静态x m l 集成了动态的特 点。由于w e bs e r v i c e s 已经成为分布式计算模式的事实标准，a x m l 从而也成为种具有 广阔前景的分布式框架语言。就我们看来，a x m l 的想法非常先进，有着广阔的应用前 景。这也是我f 进一步研究的主要动机。 重写是a x m l 中的核心内容，而提高重写效率是a x m l 理论研究的重中之重。深入 研究这些问题，并借鉴些其他方面的优化技术的思想，提出新的a x m l 重写优化方法， 实现该算法，应用在计划排产当中去，并能够提高计划排产算法的运行效率。 曾经，企业一直把心e r p 看成是对企业生产控制的有力工具，但随着最近几年产 品质量的提高、交货期缩短以及竞争的激烈，企业逐渐了解到了m r p l l e r p 软件的不足： 它主要是针对资源的计划，通常能处理以前发生的事情，虽然可以预计并且处理明天即将 要发生的事件，但是对今天j 下在发生的事情却常常留下不规范的缺口。因此，如何更好 的、精确的控制车间生产管理，找出影响产品质量和成本的因素，提高计划的实时性、有 效性和灵活性，同时又能改善车间生产的生产效率已经成为每个企业所关心的重要的问 题。 因此本文根据对国内外研究现状的分析，在本课题中提出了一种改进方法：结合树自 动机理论的重写模式，借鉴其他的优化思想，提出a x m l 重写优化方法，实现该算法，并 且应用在计划排产当中去，以提高计划排产算法的运行效率。 1 5 课题的硼究内容 1 5 1 课题要解决的问题 x m l 作为一种自描述的半结构化的数据模式已成为w e b 数据表示和交换的新标 准，越来越多的信息处理系统采用x m l 文档作为信息存储、交换和发布的载体，x m l 类型的数据已成为当前主流的数据形式。w e bs e r v i c e s 是由组件技术发展起来的新标 准，它的意图是允许一些活动对象为潜在的请求提供松散耦合的分布式服务。w e b s e r v i c e s 是建立在x m l 、s o a p ( 简单对象访问协议) 、w s d l ( w e bs e r v i c e s 描述语 言) 、u d d i ( 统一描述、发现和集成) 3 0 1 基础之上的分布式应用架构。在w e b 内蒙古科技大学硕士学位论文 s e r v i c e s 架构的各模块问及其模块内部，消息以x m l 格式传递，因为，以x m l 格式 表示的消息易于理解和阅读，并且x m l 文档具有跨平台性和松散耦合的结构等特点。 为适应w e b 数据管理的需求，s e r g ea b i t e b o u l 等人提出了主动的x m l ( a c t i v e x m l ，删l ) 语言，在p 2 p 的架构上，以w e bs e r v i c e s 作为数据管理的工具，定义 了一种新的数据和服务集成的框架。a x m l 文档能够在应用之间进行数据交换。 自动机理论论述计算的数学模式的定义和性质，它是算法描述和分析、计算复杂性 理论、可计算性等研究的基础，它为计算理论提供了可靠的数学模式【3 1 】。树自动机是对 传统字符自动机的扩展，两种自动机的根本区别在于状态转移规则的不同，这种特性使 得树自动机更适合于处理树形数据结构。 总结x m l 各种重写问题的基础上，基于自动机理论，定义用于抽象a x m l 模 式的树自动机，将给定的a x m l 源模式及目标模式利用树自动机，产生最优函数调 用序列，来判定符合源模式的所有a x m l 文档是否能够全部重写为目标模式的文档 实例，并将该算法应用于车间制造系统的基于标准单件车间作业计划排产中去。 1 5 2 课题的研究思路 本文完成了基于树自动机对a x m l 的重写优化，并将该算法应用于车间制造系统 的基于标准单件车间作业计划排产中以提高效率。本文完成的工作如下： 第一个算法是完成了对文档的递归终止性问题的解决，当a x m l 模式中包含较多 函数节点数目时，算法依然能够有效地完成对模式无环性进行判定。 第二个算法是完成了对文档可重写性的检验，基于树自动机理论，提出了a x m l 文 档可重写性的检验算法。实验表明，基于该算法能够有效地完成对a m ，文档的可重写 性检验。 第三个算法完成了对a x m l 模式的重写问题，实验表明该算法是可终止的、正确 的、完备的、复杂度为多项式时问。 第四是完成了a x m l 重写优化在单件车间计划排产中的应用，试验表明该方法的应 用节省了排产中的数据准备的时间，因此提高了排产的时间。 本文的组织结构如下： 第一章介绍了a x m l 语言的发展背景及特点，以及课题的研究内容。 第二章介绍了a x m l 的基本内容。 第三章介绍了a x m l 重写技术。 第四章介绍了重写在基于标准单件车间作业的计划排产中的应用。 第五章进行了实验和性能测试。 最后对全文作了总结。 内蒙古科技人学硕十学位论文 2a x m l 的简介 本章介绍a x m l 语言的基本组成部分：a x m l 文档和a x m l 服务，简单介绍 a x m l 的重写以及a x m l 站点。通过对基本案例和分布式数据管理多样性的阐述，简 单介绍下a 的特性。 2 1 定义a x m l 文档 a x m l 文档定义为由两种类型结点组成的标签树数据集结点和函数结点。后者 为服务调用。假设存在某些非连接域：结点n ，标签l ，函数结点f 和函数值d 。 定义1 ：一个隐含的文档t 是一个扩展的( t ，九) ，其中t 兰( n ，e ， ) 是一个有 序树，n 是结点有限集合，e 包含于nx n 是边， e x h i b i t s 其中t i t l e 表示总厂名称，a d d r e s s 表示总厂地址，w o r k i n g - s i t u a t i o n 表示工厂的生产 情况。o r d e r - 表示工厂的订单。s c 表示嵌入在文档中的调用。s c 的孩子元素被看作是隐式 定义的。孩子元素的变化的内容作为调用激活的结果。某些信息是显式的( 例如工厂名 称r i f l e ) ，然而某些是隐式的( 例如订单o r d e r 、生产情况w o r k i n g - s i t u a r i o n ) 。文档指 定了怎样在l i s t 上获得隐式信息。 带有在l u d 中的标签的结点称作数据结点，带有在f 中的标签的结点称为函数结 点。函数结点的孩子子树是函数的参数。当函数被调用的时候，说明子树已被通过了。 返回值代替文档中的函数结点。例如工厂的加工情况的a x m l 文档，关于订单列表和 内蒙古科技人学硕士学位论文 工件的加工情况的服务调用，对于每个要被调用的w e bs e r v i c e s 用a x m l 的s c 属性来 定义。例如g e t o r d e r s l i s t t o m 我们想要调用l i s t 提供的g e t o r d e r 。用s o a p 协议调 用服务需要的所有信息的指令代码。函数结点下面的子树是调用的参数。例如调用的参 数用了一个同期( d a t e ) 和一个参数。通常参数可以是任何的x m l 数据，但有的服务 它本身就包含服务调用。下面简单介绍一下a x m l 文档的特性。 首先，文档具有动态