《面向对象图转换的Meta模型及其在FUJABA中的应用》

41《理论计算机科学电子札记》44卷第4期（2001年）网址：http://www.elsevier.nl/locate/entcs/volume44.html11页如何指定图形转换方法：一个适用于Fujaba的Meta模型*ReikoHeckel1AlbertZuendorf2部数学与计算机科学学院德国帕德博恩D-33095摘要面向应用的图转换方法提供了顶点和边之外的结构特征，如分层图中的组合，面向对象图中的继承，多重性约束等。通常，这些特征具有特定的动态解释，需要复杂的嵌入机制和上下文条件。例如，删除复合节点通常意味着删除其组件。在本文中，我们提出使用Meta图语法来定义这样一个复杂的图转换方法。Meta图语法是一种类型化的图语法，其类型图提供了对图的结构、规则和方法的转换的静态描述。这个静态的Meta模型，与UML规范中的Meta模型相当，通过图形嵌入规则的规则应用操作符的规范进行扩展，即， Meta图文法的产生式。这些嵌入规则允许对规则的可容许上下文嵌入以及规则应用对上下文的副作用进行简明的视觉描述。作为一个案例研究，Meta图语法的面向对象的图形转换方法FUJABA的选定功能。关键词：图变换与图文法，Meta建模，fujaba*研究部分得到ESPRIT工作组APPLIGRAPH和TMR网络GETGRATS。1 电子邮件地址：reiko@upb.de2 电子邮件地址：zuendorf@upb.de2001年由ElsevierScienceB. 诉 在CCBY-NC-ND许可下开放访问。HECKEL和ZÜNDORF42Fig. 1.示例类图图二.对象关系图1介绍通过图、规则和变换的概念，给出了一种图变换方法。此外，一些方法提供了像图模式或控制结构这样的概念。通常，这些概念的正式定义集合论、逻辑、代数或代数）术语（参见[15]这是一个定义的集合。虽然数学定义是理论发展不可或缺的工具，但它们对于向潜在用户解释概念和结构往往不是很有用，特别是如果数学语言与要定义的方法具有非常不同的性质这个问题的一个解决方案，这是流行的可视化建模语言，如UML[13]，是Meta建模的方法[12]。在这里，建模语言是在一种自举过程中定义的，它使用要定义的语言的一个简单子集作为Meta语言（为了避免循环定义，这个子集必须给出一个独立的形式化。例如，在UML规范[13]中，使用类图和约束来指定UML的抽象语法和静态语义。动态语义只是在非正式文本中描述在本文中，我们提出Meta建模作为一种技术，用于规范面向应用程序的图转换方法的静态和动态方面基于一个类UML的Meta模型静态定义的类的图，规则，和转换的方法，元图语法用于生成，从每个规则，一类的转换。作为一个案例研究，这种技术被应用到（一个子集）面向对象的图形转换方法FUJABA，其中包括功能，如合成，多重性约束，继承。2Fujaba方法FUJABA项目[6]（参见www.fujaba.de）旨在促进图形转换在面向对象软件开发中的使用。 为了吸引面向对象的软件开发人员，F UJABA采用U ML协作di-agrams作为图形重写规则的符号。此外，FUJABA环境提供了一个代码生成器，它生成类图和图重写规则的Java实现。我们生成使用非常简单的实现概念的纯Java代码。图重写规则被应用于通常的主存对象，并采用标准JAVABEAN访问方法来查找和操纵对象结构。HECKEL和ZÜNDORF43∗∗类和对象图。 图1显示了一个类图的片段，该图对工业装配车间中的自动物料流系统的控制软件进行了建模，该系统是在I SILEIT项目[7]中开发的。在富贾巴，类图中的类被转换成通常的JAVA类。类属性成为相应JAVA类的私有数据成员使用适当的set和get方法。类图关联表示在类之间发送双向关系。因此，关联被转换为相应Java类中的指针对。类图中的关联可以用多重性约束来描述. 例如，每个机器人可以持有任意数量的货物（多重对于一个关联的一对多HashSet类型的vate数据成员，即，JAVA运行时库提供的标准容器类此外，还有一些访问方法，被创建，例如，添加和删除来自/到关联的链接，并枚举其所有链接。因此，对于图1中的关联holds的to-many端（附加到类Good），私有数据成员HashSet holds;在类Robot中，使用方法addToHolds，removeFromHolds和iteratorOfHolds生成。一对一关联最自然地由指针实现。因此，我们生成了neighbors类型的私有数据成员以及set和get方法。 在类Robot中，关联的一端保持，在类Good和方法setRobot和getRobot中创建一个私有数据成员Robot robot。通过通常的指针实现一对一的关联节省了内存空间，并将读访问减少到最小。然而，这意味着我们的实现不能在某个对象上为给定的关联存储多个指针，即使是临时的。例如，如果好的g已经属于某个机器人r1，并且如果我们分配一个新的机器人r2通过调用g.setRobot（r2）来保存g，然后我们在所有者中创建一个constrict在机器人R1和R2之间运送。 必须通过拒绝新所有者或重写旧所有者或引发运行时异常来处理此冲突。在FUJABA方法中，默认行为是用新所有者覆盖为了保证表示两个对象之间链接的指针对的一致性，相应数据成员的写 方 法 相 互 调 用 例如， 方 法 r.addToGoods （ g ） 调 用 方 法 g.setRobot（r），反之亦然。类似地，调用r.removeFromGoods（g）会导致调用g.setRobot（null），反之亦然。由于数据成员是私有的，并且只能通过它们的访问方法进行更改，因此我们能够保证每次向对象结构添加链接或从对象结构中删除链接时，都正确地建立或删除相应的指针对这种保证将通常的JAVA对象结构转换为面向对象图的适当实现。HECKEL和ZÜNDORF44--------图三.一个故事模式创造了一个一对一的关联见图4。一种处理作文的因此，关联的双向实现保证了每个对象都知道它的所有邻居。因此，我们可以生成一个方法removeYou，它可以删除一个对象和它的邻居之间的所有链接这样一个孤立的对象很容易被垃圾收集。因此，我们的方法removeYou允许实现一种行为，其中节点可以在不显式了解其上下文的情况下被删除，同时避免悬挂引用的严重问题并保证引用完整性。removeYou-方法还用于实现简单的组合概念。 在U ML类图中，用黑色菱形标记的关联表示指示所谓的重合寿命的组成关系。我们将这种重合的生存时间实现为弱存在依赖：如果一个组件对象失去了它的复合，它也会被删除我们通过递归转发removeYou调用组合关系来实现这一点因此，在图2中的对象图中，它实例化了图1中的类图，调用g1.removeYou（）将递归地隔离（并因此垃圾收集）所有Good对象。规则和转换。图3和图4显示了两种FUJABA故事模式，即，图重写规则在UML协作图符号。故事模式表示为一组连接的对象，可选地具有附加属性约束。对象和链接可以用约束new和destroyed 来标记，对象的属性舱可以包含属性赋值。 通过收集所有未标记的元素和属性约束以及所有标记为已销毁的元素，可以从这样的协作图中导出通常的图重写规则的左侧。相应的图重写规则的右侧由所有未标记的元素、属性赋值和标记为new的元素组成。左侧和右侧的公共元素映射相同。图3表示一个故事模式，它查找一个属性prodName等于“bobby car“的好g1这个对象结构这种故事模式在图1所示的对象结构中的应用2将匹配对象g1和s，并在它们之间创建一个hold-link。到目前为止，这造成了良好的g1连接到两个保持链接连接到组装单元a和穿梭机s，分别的情况这将违反关联持有的多重性约束，该约束允许最多一个机器人作为特定物品的持有者此外，我们的指针为基础的实现是不能够举行一个以上的机器人指针在一个好。如已经讨论了富贾巴这种方法通过删除现有的Holds- 链接附加到货物上，新的Holds-链接附加。因此在HECKEL和ZÜNDORF45在我们的示例中，作为在G1和S之间添加保持链接的副作用，去除了连接装配单元C和货物G1的保持链接。图4概述 了我们 的方法如何处理组合。所示的故事模式查找属性prodName等于“bobby car“的良好g1和属性这个对象结构通过破坏好g1和到好g3的parts-link，并通过创建新的好g9和到g3的新parts-link来重写。虽然这个操作看起来除了好的g1的对象id之外没有改变任何东西，但是它有戏剧性的副如图1所示，零件-关联是一种组合关系.这意味着删除父商品也会删除所有成为孤儿的子商品。因此，在Fig.2，g1的删除将导致其所有子商品的删除，并递归地删除所有后代。然而，图4的故事模式明确地移除了从g1到g3的部分链接。由此，子对象g3与其父对象g1分离，并且因此，子对象g3不被商品g1的移除所干扰。然而，g1的其他子节点没有被故事图中的某个其他对象拯救，并且它们与它们的父节点一起被移除，即，对象G2和G4被移除，并且它们的子对象G5、G6、G7和G8成为孤儿并且也被移除。乍一看，好的g3的生存可能看起来很奇怪，因为它中间变成了孤儿。然而，在我们的项目中，这种语义已经被证明是非常有用的，因为它允许解构组合层次结构，并从它们的父母卸载部分，以便单独存储它们供以后重用。在我们的例子中，未安装的座椅直接重新用于新的g9。总而言之，图转换在面向对象数据模型中的应用为图重写规则的语义定义带来了挑战特别是，关联和组合关系的多重性约束意味着创建和删除对象和链接的某些方面，需要仔细指定。 语义决策（如覆盖一对一关联的链接）是由Java和a中的实现指导的，与大多数其他图转换方法相反。在下面的两节中，我们将给出这些非标准特性的静态和动态方面的形式化。3抽象图：类型图如UML[13]，我们采用Meta建模方法[12]。为了规定面向对象图和图图式、故事模式和转换构成了FU-JABA语言的核心（静态）Meta模型（语言定义）和各个模型（语言的元素）之间的关系由类型化图的概念捕获[2]。所谓图，我们指的是有向无标号图G=<$GV，GE，srcG，tarG<$HECKEL和ZÜNDORF46→∗→ →⟩⟨⟩图五. FUJABA静态Meta模型其中顶点集GV、边集GE以及函数srcG：GE→GV和tarG：GE→GV分别将每条边与其源顶点和目标顶点相关联 图同态f：G → H是一对与源和目标相容的函数f V：G V H V，f E：G EH E，即，对于GE中的所有边e，fV（ srcG （ e ） ） =srcH （ fE （ e ） ） 和 fV （ tarG （ e ） ） =tarH （ fE（e））。给定一个图TG，称之为类型图，一个TG-型（实例）图由图G和类型同态g：G TG组成，G的每个顶点和边x对应于TG中的类型g（x）= t.在这种情况下，我们也记为x：t∈G。在TG上类型化的所有实例图的集合由GraphTG表示。在 本 文 中 ， 类 型 图TG将由图 1 中描绘的 FUJABAMeta模型五、遵循UMLMeta模型[13]，我们区分两个非常相似结构的级别：模式级别由元类型Class，Assignment，AssocEnd，Attribute，Type和Schema组成，实例级别由元类型Object，Link，LinkEnd，AttribLink，Value和Graph给出。每个实例级图形元素通过instOf-edge与模式元素相关联所有的顶点类型都有一个属性名：string，它没有在diagram中显示出来除非另有说明，边缘的多重性是（任何）。属于关联两端（而不是整个关联）的属性（如多样性和组合）被建模为顶点类型AssocEnd。超链接对从子类指向超类的类之间的继承进行建模.富贾巴我们遵循[10]的方法（也用于UMLMeta模型[13]），将属性实例视为从对象到属性值的链接相应地，在类型级别，每个属性都与它的类和类型相关联。后者提供了一个Meta属性排序，它指的是一个代数签名S =S，OP的排序，而值-顶点被赋予了一个S-代数A的元素（对应的载体）。我们假设签名A和代数A是固定的，以反映语言的内置数据类型模式元素与模式的关联以及图形元素与图形的关联由如图5的下部中建模的el-edge表示。它还将变换Trafo定义为一对两个图（不一定不相交）。各种完整性约束必须施加在这个Meta模型的实例，以表示良好形成的FUJABA模型。 其中许多是显而易见的，如面向对象图和图模式中的instOf-边与el-边的可交换性。例如，连接到LinkEnd的Object应该是连接到相应AssocEnd的Class的实例。此外，我们要求与Graph-vertex到el-edges相关联的元素确实形成了一个面向对象的图，该图是HECKEL和ZÜNDORF47∪∪图六、示例图模式和故事模式的抽象语法对应的schema。使用正式的约束语言的形式化，这种约束超出了本文的范围图3给出了根据该Meta模型的故事模式的表示。六、上半部分表示图1的图表模式1中，为了可读性，我们省略了一些明显的instOf-和el-边缘下半部分将故事模式描述为一对图，在本例中，前图是后图的子图。注意，Meta模型并不区分故事模式（即， 重写规则）和转换。事实上，在下面的部分中，故事模式被认为是一个最小的转换，所有使用该模式的转换都可以通过上下文嵌入规则生成。4操作语义：嵌入规则在本节中，Meta图语法用于为每个故事模式指定将该模式应用于合法的面向对象图所产生的转换集这种Meta图语法的结果生成了模式可以放置的上下文。每个产生式同时描述了在给定的语境中转换的匹配条件和结果生成式以嵌入规则的形式呈现，如下图所示PT<$P<$T<$< $ P<$C<$T<$→C<$T其中P称为前提，C为结论，T为规则的类型化条件，使得联合PCT是有定义的。通常，P和 C表示转换（或故事模式），而T是图模式的一个片段形式上，我们的Meta图语法是基于代数双推出（DPO）的方法，图转换[4，3]使用类型图[2]和否定的应用条件[8]。前提P和条件T共同构成了图语法产生式的左侧，如上图右侧所示右边由结论C和类型条件C给出，中间的界面图是两者的交集将这样的产生式应用于表示变换的TG型图，产生另一个TG型图，其表示具有附加对象、链接或属性实例的变换。使用给定故事模式G0的所有变换的集合由所有良构的T G-型图G可由G0通过图文法产生式导出这种嵌入规则的使用受到SOS [14]中的上下文化规则的启发，就像CCS [11]中的限制规则，说明在哪些条件下可以在限制运算符的上下文中执行动作。CHECKEL和ZÜNDORF48关于我们见图7。类似于DPO的嵌入规则：添加断开的节点，在保留的节点之间添加边，以及合并保留的节点见图8。嵌入规则的抽象语法：接口顶点（左上）、悬挂边（右）和泛化（左下）。见图9。类似于SPO的嵌入规则：删除悬挂边、合并已破坏的节点和冲突解决图10个。组合规则：隐式删除依赖对象，除非存在另一个依赖上下文嵌入规则在抽象语法层次上进行了形式化定义然而，正如从图1所示的抽象语法图中显而易见图6中的故事模式3、这个演示即使在简单的例子中也相当复杂此外，它不足以解释故事模式对语言使用者的应用（例如，软件开发人员或领域专家）。因此，我们提出了基于语言具体语法的图形演绎规则风格的上下文嵌入规则[1]图的规则7指定DPO方法的嵌入策略第一条规则指出，给定任何变换，对于每个顶点类型C，我们可以添加一个顶点o：C以获得另一个变换。顶点被添加到接口，即，它发生在前图和后图中，因为没有被破坏或新的限定（参见。第2节）。第二条规则指出，只要模式图允许，可以通过在接口中的顶点之间第三个规则指定了如果两个顶点具有相同的类型，则可以将它们粘合在界面中类似的规则也可以定义为边。因此，给定一个DPO生产（在图1中表示为Meta模型的实例），5），图中的规则7允许我们导出所有合法的DPO变换，即，它们在DPO方法中指定了生产应用的概念。对于第一条和第二条规则，基于Meta模型指定的抽象语法的形式表示分别在图8的左上方和右侧显示。图9，示出了为了规范更一般的SPO方法所需的三个附加规则这三条规则对应于DPO粘合条件[3]排除的三种情况：删除悬挂边，合并都被删除的顶点，以及删除和保留之间的冲突，这是有利于删除的解决方案请注意，DPO和SPO之间的差异（查看原始定义很难分辨）如何归结为一些额外的嵌入规则。就正常联想而言（除了“”之外没有复合或多重性是的-HECKEL和ZÜNDORF49见图11。多重性规则：将链接添加到受约束的关联，以及链接图12个。属性链接的继承和嵌入W.R.T.该组合物在图10中示出。其思想是组件对象依赖于至少一个复合对象的存在，即，当最后一个组合被移除时，它被删除。正如第一条规则所规定的，一个破坏一个对象o的变换可以通过将一个合成关系附加到另一个对象p上来扩展，这样，对象p和合成关系也都被破坏了。如果存在p的第二个合成关系，则对象在变换中保持不变，如右边的规则所指定为了完整，我们必须添加第三条规则，类似于图7中的第二条规则，它在两个都被保留的对象之间添加组合。图11详细说明了FUJABA可能最令人惊讶的特征，重数为0的链接的覆盖.. 1.正如第2节所讨论的，这一想法是将这样的链接视为指向对象的指针，一旦创建了这种类型的新链接，在处理重数为0的链接时，我们基本上区分了两种情况。1. 在它的左边，图。图11显示了一个简单的例子，如果到目前为止还不存在这样的链接，则将其引入接口这是由这个规则的前提中的否定应用条件所具体化的，该条件由被划掉的对象p：D所描绘。为了将A边引入到变换的前图或后图，需要类似的在右边，它显示了一个转换，其中一个新的A-链接被创建，可以发生在第二个A-链接的存在。作为一个侧面效应，后者被摧毁。图12左边的规则指定了继承的语义：如果D是C的子类，则故事模式中的对象o：C可以与转换中的对象o：D匹配。该规则的抽象语法在图8的左下方示出。在图12的右侧，解释了属性链接的实例化。中间的规则规定，给定一个具有属性attr：type的类C，对象o：C可以链接到同一类型的属性值val。图12右侧的规则描述了删除对象如何导致删除其属性链接。尽管链接和属性链接的具体语法不同，但这些规则与嵌入和隐式删除链接的这就结束了我们对FU-JABA故事模式的上下文嵌入规则的介绍。 我们已经考虑了结构特征，如多重性约束0。1、组成、属性和继承。 由于空间不足，其他几个特性被省略了，比如更复杂的多重性约束，有序或限定关联，以及多对象。 其中一些需要更强大的图形语法概念，例如，终结符和非终结符的区别除了，HECKEL和ZÜNDORF50基本概念，同时也是图文法理论的成果，可以为具体的图变换方法提供有益的借鉴，是今后工作的一个问题5结论在本文中，我们提供了一个Meta模型的静态和动态方面的一个子集的FUJABA语言-面向对象的图形转换方法的基础上的UML和JAVA。静态方面由元图语法的类型图来描述，元图语法的生成用于指定从故事模式生成转换，即，图重写规则。本文中提出的技术并不局限于具体的个别图变换方法。事实上，我们对图形演绎规则的使用与图形操作语义（GOS）方法[1]密切相关，其中类似的规则用于指定UML图语言的操作语义[5]。图变换规则和全UML列图之间的对应关系在这方面，可以发现非常相似的问题。例如，在规范级别和实例级别上的协作图之间的UML中的区别对应于图转换规则和转换之间的区别嵌入规则可以是指定这两个级别之间的关系的一般手段确认感谢Stefan Sauer对本文的初步版本提出了许多有用的意见引用[1] Corradini，A.，R. Heckel和U. Montanari，图形操作语义学，在：A.Corradini和R.张文龙，图转换与可视化建模技术，2000年，中国科学院学报，2001年。uni-paderborn.de/cs/ag-engels/Papers/2000/CorradiniGTVMT00.pdf。[2] Corradini，A.，联合Montanari和F. Rossi，Graph processes，FundamentaInformaticae26（1996），pp. 241-266[3] Corradini，A. 、乌桕属U. Montanari，F. Rossi，H. 埃里格河 他是我的朋友。 刘伟，图变换的代数方法，第一部分：基本概念和双推出方法，在：罗森伯格[15]页。163-245HECKEL和ZÜNDORF51[4] Ehrig ， H. ， M. Pfender 和 H. Schneider ， Graph grammars ： an algebraicapproach ， in ： 14th Annual IEEE Symposium on Switching and AutomataTheory（1973），pp.167比180[5] Engels，G.，J. 豪斯曼河Heckel和S. 动态Meta建模：UML中行为图的操作语义的图形化方法，在：A。Evans，S. Kent和B. Selic，editors，Proc. UML 2000，York，UK，LNCS 1939（2000），pp. 323-337[6] F是C，T， J. 涅尔湖 Torunski和A. Zu？ndorf，Storydiag rams：Anewgraphtransformation language based on UML and Java，in：H. Ehrig，G.恩格斯，H.J. Kreowski和G.Rozenberg，editors，Proc. 第六届国际图变换理 论 与应 用研讨会（ TAGT '98 ） ， 帕 德 博 恩 ， 1998 年 11 月 ，LNCS 1764（2000）。[7] Gausemeier，J. 、乌桕属U. Glüasser，W. S chüafer和（项目经理），柔 性 自 动 化 制 造 分 布 式 控 制 系 统 的 集 成 规 范 ，www.upb.de/cs/isileit，由德国研究基金会（DFG）资助。[8] Habel ， A. ， R. Heckel 和 G. Taentzer ， Graph grammars with negativeapplication conditions，Fundamenta Informaticae26（1996），pp. 287[9] 黑 克 尔 河 和 S.Sauer ， 通 过 状 态 转 换 加 强 UML 协 作 图 ， 在 ： H 。Hußmann ， 编 辑 ， Proc.FundamentalApproachestoSoftwareEngineering（FASE[10] L ？ we ， M. ， M.K 或 K+ 和 A.Wagner ， Analgebraaicframeworkfortransformation of attributed graphs，in：M.睡吧M Plasmeijer和M. van Eekelen，编者，术语图重写：理论与实践，John Wiley SonsLtd，1993年，第100页。185-199.[11] 米尔纳河，“Communication and Concurrency,” Prentice-Hall,[12] 对象管理组，Meta对象设施（MOF）规范（1999），http://www.omg.org。[13] 对象管理组，UML规范版本1.3（1999），http：//www.omg.org。[14] Plotkin ， G. ， A structural approach to operational semantics ， TechnicalReport DAIMI FN-19，Aarhus University，Computer Science Department（1981）.[15] 罗森伯格，G.，编辑，