模型敏感搜索计划与自适应图模式匹配

理论计算机科学电子笔记152（2006）191-205www.elsevier.com/locate/entcs使用模型敏感搜索计划进行模型转换的自适应图模式匹配1GergelyVaro'2KatalinFriedl4布达佩斯技术经济大学H-1 5 21Budapest，Magyartudosokko？ru？tja2.，洪加里D'anielVaro'3布达佩斯技术经济大学H-1 5 21Budapest，Magyartudosokko？ru？tja2.，洪加里摘要本文对模型转换工具的图模式匹配问题作了两方面的贡献。 首先，模型敏感的搜索计划生成模式遍历（作为传统的多样性和现有工具的类型考虑的扩展），通过估计的预期性能的搜索计划的典型实例模型，可在transformation- tion设计时。然后，提出了一种自适应的图模式匹配方法，其中最优的搜索计划可以选择从先前生成的搜索计划在运行时的基础上收集的统计数据，从当前实例模型的转换。关键词：图变换，自适应图模式匹配，搜索计划。1第一部分是由P′eterBiz′akiPukyScholarshi p发现的，第二部分是由Ja′nosBolyiScholarship发现的。2Email：ger v arr o @cs. b me。胡3Email：varr o @mit. b me。胡4Email：friedl@cs. bme。胡1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.10.025192G. Varro等人理论计算机科学电子笔记152（2006）1911引言虽然现在模型驱动的系统开发得到了广泛的概念上不同的模型转换工具的支持，但几乎所有这些工具都必须解决一个共同的问题：复杂的基于图的模型结构的基于图变换（GT）的视觉、规则和基于模式的形式化范式的工具[13，5]已经整合了几十年的研究成果。非正式地，图转换规则通过在模型中找到由其左侧（LHS）图规定的模式的匹配并根据右侧（RHS）图改变它来对图模型执行局部操作。最近的一项调查[18]评估了图转换工具在各种基准测试示例上采用不同方法的性能，结果显示，将转换规则编译为本地可执行代码（Java，C，C++）的方法（如Fujaba [7]，PROGRES [14]或GReAT [1]）对于模型转换目的非常强大可执行代码的性能在编译时通过评估和优化不同的搜索计划[21]来优化，以遍历LHS模式，这通常利用了问题域的元模型所施加的多重性和类型限制。虽然在许多情况下，类型和多重性提供了一个非常强大的算法来修剪搜索空间，但在实际的模型转换问题中，人们对该领域的实例模型的潜在结构有进一步的领域特定知识，这通常不会在这些方法中使用此外，在模型演化过程中发生剧烈变化的情况下，模型的特征结构也可能发生变化，因此在编译时先验生成的搜索计划可能不够灵活和强大。本文对模型转换工具的图模式匹配问题做了两个首先，模型敏感的搜索计划生成被提出用于模式遍历（作为对现有工具的传统的多重性和类型考虑的扩展），通过估计在转换设计时可用的典型实例模型上的搜索计划的预期性能3）。然后，提出了一种自适应的图模式匹配方法，该方法可以在运行时根据统计数据从先前生成的搜索计划中选择最优搜索计划从转换中的当前实例模型中收集（Sec.4）.值得强调的是，第一种技术的概念直接适用于进一步微调上述基于编译器的GT方法的性能，而我们相信第二种技术是迈向高效增量模型转换引擎的一步，G. Varro等人理论计算机科学电子笔记152（2006）191193在操纵不同模型的同时，需要保持几个模型的一致性。方法概述使用这些技术的拟议工作流程总结在图中。1.一、Fig. 1. 方法概述Optim首先，收集领域的典型模型（来自转换设计者、最终用户等）优化器根据该搜索计划为每个典型模型生成具有最佳平均性能的一个搜索计划。仍然在转换设计时，生成可执行（面向对象）代码作为每个搜索计划的实现自适应在执行时，统计数据是从转换中的当前模型中实时收集的基于该数据，模式匹配策略（即，搜索计划的实现）被选择，其产生最佳的预期性能成本。确保模型统计信息引起的内存开销很小是很重要的，并且每个预编译搜索计划的成本也可以快速估计最后，使用选定的模式匹配策略将转换规则应用于实例模型本文重点介绍步骤Optim和Adapt，而步骤Cdgen（参见[2]）的详细讨论超出了本文的范围。2通过图形转换进行我们首先简要介绍元模型和模型的主要概念，然后展示如何使用图变换来操纵这些模型194G. Varro等人理论计算机科学电子笔记152（2006）1912.1元模型为了展示模型、元模型和转换的概念，本文将使用一个标准的对象关系映射（参见[16]）作为一个运行示例，它从UML类图生成一个关系数据库图二、对象关系映射的扩展元模型元模型描述了建模语言的抽象语法，可以用类型图形式化地表示UML类图和关系数据库模式的元模型（遵循CWM标准[12]）如图2所示。类型图的节点（例如模式，表）称为类。一个类可以有属性来定义特定类的某种属性。(E.g.一个表的名字可以是一个属性，但是在图中没有描述2.）的情况。继承可以在类之间定义，这意味着被继承的类具有其父类所具有的所有属性，但它可能还包含一些额外的属性。注意，CWM标准派生出数据库概念，如表、列等。从UML概念继承（见图1）。2）的情况。像EO，CF，KRF和UF这样的协会定义了类之间的联系。一个关联的两端都可以有一个多重性约束，它声明了在运行时可以参与一个关联的对象的数量。我们考虑最典型的多重性约束，这是（i）最多一个（由箭头或菱形表示），和（ii）任意（由没有箭头和菱形的线端此外，我们使用一对一的参考边（在实例模型中由双向虚线表示）连接源和目标模型节点。最后，我们在不失一般性的情况下假设关联的两端都是可导航的。G. Varro等人理论计算机科学电子笔记152（2006）1911952.2带有统计信息的实例模型实例模型（或者，正式地说，实例图）描述了用建模语言定义的具体节点和边分别称为对象和链接。对象和链接分别是元模型级别的类和关联的实例元模型中的属性显示为实例模型中的槽。实例模型中的继承强制子类的实例示例2.1这个域的一个格式良好的实例模型（如图2所4（a））有4个类Class的实例。推广节点g1和g2分别表示c1是c2的超类，c2是c3的超类。类c2已经通过对象关系映射算法进行了转换，这意味着表t2通过Ref类型的边附加到类c2。 表t2具有单个列cl2和引用列cl2的主键约束p2。我们假设在每个模型的演化过程中，某种类型的节点总数（用#type表示）保持不变。此外，我们建立了一个类似的计数器，用于在相应类型的节点之间引导的某种类型的边（由#t edge（t src，t trg）表示）。例如，在图4（a）中，#Class = 5（注意，根据CWM元模型，表也是类），#CE（泛化，类）=2。该模型统计将大量用于搜索计划优化和搜索计划适应步骤。请注意，维护这些数据所带来的开销相对较小：一种选择是使用类级别（静态）的属性和方法。事实上，在许多情况下，这些细节已经由执行环境提供（例如，如果模型持久化在数据库中，则是关系DBMS）。2.3图形变换图转换[13，5]提供了基于图模型的模式和规则操作每个规则应用程序通过用另一个图替换一个图的一部分来转换图图变换规则r=（LHS，RHS，NAC）包含LHS和NAC图一起称为前提条件PRE。在本文中，我们使用最初在[7]这里给出了这些图的并集要删除的内容有196G. Varro等人理论计算机科学电子笔记152（2006）191由del关键字标记，要创建的元素由new标记，而NAC图中的元素由neg关键字表示。将r应用于主机（实例）模型M，用RHS的图像替换M中LHS的匹配。这通过以下方式执行：（i）在M中找到LHS的匹配（通过图形模式匹配），（ii）检查否定应用条件NAC（其禁止某些对象和链接），（iii）移除模型M的可以映射到LHS但不能映射到RHS的部分，从而产生上下文模型，以及（iv）通过添加新对象和链接（其可以映射到RHS但不能映射到LHS）将上下文模型与RHS的图像粘合，获得导出的模型MJ。图变换是从初始模型MI开始的规则应用序列。例2.2选择一个图转换规则（图3（a）中的GeneralizationR）作为论文的例子，它处理类的继承。该规则表示，如果已经有一个数据库表（ 主键列），则该规则变得适用，并且生成新的外键约束以表示子类（的实例）的标识符也应该在父类的表中找到。整个对象关系映射形式化为图转换规则可以在[19]中找到3搜索计划生成众所周知，图变换性能的最关键步骤由于模式匹配仅由图变换规则的前提条件决定，因此我们目前的研究仅限于GT规则的这一部分为此，搜索计划的生成是一种经常使用和有效的策略。非正式地说，搜索计划定义了实例模型节点的遍历顺序（搜索序列），以检查模式是否可以匹配。根据特定搜索计划遍历的搜索空间表示为搜索空间树（SST），其中包含在模式匹配期间在某个点可以做出的所有决策SST的根节点表示通过固定规则的输入参数节点提供的部分匹配。从根节点开始的SST的每个路径通过匹配模式中的新（不匹配）节点来扩展该部分在本节中，我们以以下方式介绍了一种特定于模型的搜索计划(i) 首先，我们引入了搜索图的概念，以获得一个容易的，G. Varro等人理论计算机科学电子笔记152（2006）191197管理第节中GT规则先决条件的表示3.1.(ii) 基于典型模型的统计数据，通过在搜索图的边缘上添加数值权重来准备特定于模型的搜索图（第二节）。3.2）。(iii) 搜索计划的概念与成本函数一起定义，该成本函数有助于估计搜索计划的性能，并制定搜索计划何时是最佳的。三点三(iv) 最后，提出了两种算法，它们实现了为特定于模型的搜索图生成低成本搜索计划（第二节）。3.4）。3.1搜索图表在搜索计划生成过程的第一阶段，为每个模式创建搜索图。搜索图是具有以下结构的有向图模式的每个节点被映射到搜索图中的节点我们还向图中添加了一个起始节点(i) 有向边将起始节点连接到每个其他搜索图节点。当在搜索图中针对某个搜索计划选择了这样的边时，则执行该搜索计划的图模式匹配引擎(ii) 模式的每条边被映射到搜索图中的一对边，这对边在表示双向导航性的两个方向上连接对应的端节点只有当源模式节点已经匹配时，模式匹配引擎才可以选择这样的在这种情况下，这样的搜索图边缘的选择意味着沿着对应的图案边缘朝向不匹配（目标）图案节点的导航。可以类似地处理用于负应用条件的搜索图。在这种情况下，所有匹配的节点（即与LHS图共享的节点）都必须被视为起始节点。消极应用条件通常在已经为LHS找到完全匹配之后检查节点，但是只要在LHS的遍历期间处理了共享节点，就可以立即执行简单的检查（例如，像测试离开NAC中的共享节点的边是否具有零基数）。Ex. 2.2及其相应的搜索5在可导航性限制的情况下，仅生成可导航方向198G. Varro等人理论计算机科学电子笔记152（2006）191C1C2P1 P2图3（a）和图3（b）分别描绘了两个曲线图。注意，具有add（或del）注释的模式的节点和边在搜索图中没有对应的元素，因为它们表示要在更新阶段添加（或移除）的节点和边。GT1T2(a) 泛化规则Col1Col2(b) Generaliza- tionRule的搜索图图3.第三章。一个示例图转换规则及其对应的搜索图3.2特定于模型的搜索图搜索计划生成的初始步骤从问题域中获取典型模型，例如，在我们的案例中，典型的UML类图和相应的数据库模式。这些典型模型的节点和边统计也是可用的，因此可以基于从模型收集的统计数据加权搜索图是在其边缘上具有数字权重的搜索图（权重在图1和图2中被描绘为边缘的标签4（c）和4（d）。通常，当模式匹配引擎选择给定的模式边缘进行导航时，边缘的权重可以被认为是该水平上可能的SST的平均分支对边权重的这种选择提供了易于计算的成本函数，该成本函数估计搜索空间的大小。两个模型及其相应的加权搜索图如图所示四、权重计算规则在图的边缘展示4（c）（由虚线表示），其对应于图案边缘的遍历在类到表方向上的Ref类型的r2。 根据我们的统计，模型1包含5个类（因为表是CWM中的类）和1个类与表之间的引用边。因此，如果模式匹配引擎在执行期间的某个时间将Class匹配到模式节点C2，则通过沿着模式节点C2导航来找到模式节点T2的有效Table的概率为G. Varro等人理论计算机科学电子笔记152（2006）1911991（a）模型1（b）模型20.4C1511G610.425C2七点二0.25C121132G410.258C2五点五40.2510.5811T111T 2T1644T211 11814 4181311111个P-1P2121911111117名P-1P2191111114 4Col1Col2(a) 根据Model1的统计信息和可能的搜索计划为 GeneralizationRuleCol1Col2(b) 根据Model2的统计信息和可能的搜索计划为 GeneralizationRule图四、示例实例模型和相应的搜索计划参考（Ref）边是由公式#Ref（Class，Table）/#Class导出的0.2。在反向导航的情况下，公式可以表示为#Ref（Class，Table）/#Table，因此对应的权重为1。3.3搜索树木和平面图此时，加权搜索图可用于领域工程师选择的在本节中，首先，我们将介绍基于加权搜索图的搜索树和搜索计划然后定义搜索计划的成本函数来预测其性能。搜索树是加权搜索图的生成树。由于起始节点没有传入的边，因此所有其他节点都应该在从起始节点开始的有向路径上可达6搜索树的边缘在图1和图2中用粗线4（c）和4（d）。6搜索树的概念可以推广到处理部分匹配模式的完成广义概念允许多个起始节点。在这种情况下，搜索树是一个以起始节点为根的森林，它们应该确保树边缘上所有其他节点的可达性200G. Varro等人理论计算机科学电子笔记152（2006）191j=1i=1搜索计划是搜索树的一种可能的遍历遍历定义了一个遍历边的序列在这个序列中，给定边缘的位置由写在图1和图2中的粗边缘上的递增整数标记4（c）和4（d）。两个示例搜索计划（及其相应的搜索树）如图所示4（c）和4（d）。搜索计划的成本（由w（P）表示）是对应的搜索空间树（SST）中遍历的节点的估计数量SST第i层的节点数是分支因子的乘积在search平面中达到水平i的边的数量，其中h是iwj，其中wj是根据搜索计划定义的顺序，第j条节点的总数可以通过将SST在逐级基础上，得到公式w（P）=nij=1 wj.通过将该成本函数用于图1的搜索计划4（c）关于对于图4（a）的搜索计划和图4（b）的模型上的图4（d）的搜索计划，我们分别得到成本值5.04和8.5由于权重表示分支因子，因此使用这种成本函数的搜索计划的最小化导致预期在大小上是最优的SST。此外，这样的搜索计划满足第一次失败原则标准，因为它代表了在接近其根的水平上狭窄的SST3.4寻找最佳搜索计划两个传统的贪婪算法被用来解决问题的(i)用于给定加权搜索图的低成本搜索树，以及（ii）用于给定搜索树的低注意，传统算法使用不同的成本函数（即，权重之和）来确定生成树的成本，这意味着它们的解决方案在我们的情况下不一定是最优的为了在加权搜索图中找到最小搜索树，使用Chu-Liu/Edmonds算法[3，4]该算法根据定义为权重之和的成本函数在有向图中搜索具有最小成本的生成树该算法可以在Alg. 1.一、在给定搜索树中找到低成本搜索计划的情况下，使用简单的贪婪算法，该算法在Alg中概述二、我们目前并没有说明这些简单的算法也为我们的成本模型提供了最佳解决方案，但最佳工程实践表明，如果选择具有给出最小和的权重的边，则当采用我们的特殊成本函数时，由相同边组成的搜索树和搜索计划也具有低成本简单性和速度是支持成功应用这种算法的进一步G. Varro等人理论计算机科学电子笔记152（2006）191201−算法1给定一个带起始节点的加权搜索图。步骤1：丢弃进入起始节点的边。步骤2：对于每个其他节点，选择具有最小权重的传入边设选取的n 1条边为集合S.步骤3：如果S的边不构成圈，则所选边构成图的最小生成树，算法终止。否则算法继续。步骤4：对于形成的每个圈，将圈内节点收缩为一个伪节点k，根据下式修改从圈外某个节点i进入圈内节点j的c（i，k）=c（i，j）−（c（x（j），j）−minl{c（x（l），l）}）其中c（x（j），j）是进入j的循环中的边的权重。步骤5：对于每个伪节点，选择具有最小修改权重的输入边。用新选定的边替换进入S中相同实节点的边第6步：使用收缩图转到第3算法2给定一个带有起始节点的搜索树。步骤0：将计数器设置为1，并让S是由起始节点组成的集合步骤1：选择从S出去的最小树边e步骤2：将e的标签设置为计数器的值。步骤3：将计数器递增1，并将e的目标节点添加到S。第4步：如果搜索树仍然有一个不在S中的节点，则返回步骤1。4自适应模式匹配第二节根据不同的典型模型，阐述了几种搜索方案。3 .第三章。然后，对于每个搜索计划，通过标准编译阶段生成单独的Java类，从而生成可执行的Java代码。这个代码生成步骤的详细描述可以在[2]中找到我们现在介绍如何使这个（或相关的）编译图转换方法自适应。我们的代码生成解决方案使用了Strategy设计模式[8]（见下图），这意味着从搜索计划生成的每个Java类都扩展了一个抽象的Strategy类，它有两个基本功能。(i) 一种方法实现了实际的模式匹配算法，它基本上由一组相互嵌入的循环组成，如[2]中所定义的202G. Varro等人理论计算机科学电子笔记152（2006）191(ii) 另一个相关的功能是根据运行时可用值得强调的是，成本计算的复杂性与图模式的大小成线性关系后一种功能表明了如何实现自适应行为创建了一个Graph-Transformation类，它维护对给定规则可用的策略和实例模型的引用。当要应用规则时，这个中心类也通过传递实际模型来依次调用规则的每个策略的成本计算方法然后比较这些策略的成本，执行具有最小成本的策略。由于单个搜索计划的成本可能会因当前实例模型而异，因此不同策略的成本之间的关系可能会随着转换的进行而改变例4.1为了说明自适应性，让我们考虑图1的模型1作为一些其他规则应用的结果，图4（a）的模型2演变成最初，当模型1处于活动状态时，搜索计划的成本分别为5.04和5.2，因此，选择执行第一个计划由于GeneralizationRule不适用于Model1，因此两种模式匹配策略都明显检测到模式匹配失败另一方面，请注意，第一个策略更早地认识到模式无法匹配。当模型通过应用一些其他规则进化为模型2时，出现了一种新的情况，因为搜索计划成本现在分别为19.5和结果，模式匹配引擎执行该模型的第二策略。值得指出的是，我们的自适应技术的目标平台不是具有显式控制结构的传统批处理模型转换在转换过程中应用规则作为定义明确的步骤（流程）。我们的目的是利用这种技术的增量模型转换提供一致的对多个域之间的模型的维护在此，应该在模型演化的任何阶段独立地应用大量规则，其中规则的最佳模式匹配策略通过遵循第一次失败原则，我们的方法有助于早期检测模式匹配失败，这在增量模型转换中非常重要，因为必须快速确定几个规则的适用性另一方面，这种技术没有提供增量查询评估的解决方案。G. Varro等人理论计算机科学电子笔记152（2006）1912035相关工作所有基于图转换的工具都使用一些聪明的模式匹配策略。几十年来，人们对图变换进行了深入的研究，已经开发出了几种有效的方法虽然许多图转换方法（例如AGG [6]，VIATRA [17]中的[11]）使用基于约束满足的算法，但在这里，我们将重点放在三种最先进的编译方法上，这些方法使用搜索计划进行局部搜索。Fujaba [10]从系统设计者选择的节点开始执行本地搜索，并通过相邻节点和边缘逐步扩展匹配。Fujaba在编译时固定了一个单一的广度优先遍历策略（即当生成模式匹配代码时）。Fujaba使用简单的经验法则来生成搜索计划。一个示例规则是，沿着具有至多一个多重性约束的边的导航先于沿着具有任意多重性的边的导航。PROGRES [21]使用一个非常复杂的成本模型来定义基本操作的成本（如枚举类型的节点和沿边的导航这些成本不是特定于领域的，因为它们是基于对工具预期使用的典型问题领域的假设PROGRES的操作图与本文中的搜索图类似，另外还支持路径表达式和属性条件的处理。PROGRES的编译版本在编译时通过贪婪算法生成搜索计划，该算法基于基本操作的先验代价。GReAT [20]的模式匹配引擎使用从最初匹配的一组节点开始的广度优先这种初始绑定在GReAT术语中被称为旋转模式匹配这个工具使用策略设计模式是为了将来的扩展，而不是像我们的方法那样支持不同的模式匹配策略面向对象的数据库管理系统也使用高效算法[15]用于查询优化，但它们的策略与查询显著不同，查询被公式化为对象代数表达式，稍后在查询优化过程中将其转换为特殊对象管理器操作的树6结论在本文中，我们首先提出了一种模型敏感的方法，用于生成编译图转换方法的搜索计划。本质204G. Varro等人理论计算机科学电子笔记152（2006）191的技术是使用从典型的设计师模型获得的先验知识。加权搜索图是从这些模型中获取的统计数据导出的。 低成本搜索计划通过为遍历的成本函数定制众所周知的贪婪算法来定义。然后，我们提出了一种自适应技术，通过利用运行时的模型统计数据，使用策略设计模式，在不同的模式匹配策略之间切换我们希望使用这种方法进行增量转换，始终保持从不同领域的模型在未来，我们计划对我们的方法进行彻底的实验评估。最初的实验表明，模型敏感的搜索计划的性能至少与现有的方法一样好，但现在就性能问题做出明确的声明还为时过早。引用[1] Agrawal，A.，G. Karsai，Z. Kalmar，S. Neema，F. Shi和A. Vizhanyo，The design of a simplelanguage for graph transformations，Journal in Software and System Modeling（2005）。[2] Balogh ， A. ， G.Varro' ， D.V 和 A 。 Pataricza ， Generationofplatform-specificmodeltransformation plugins，submitted to ECMDA 2005.[3]Chu，Y. J.和T. H.刘，关于有向图的最短树形图，科学，14（1965），pp. 公元1396-1400年。[4] Edmonds，J.，Optimum branchings，Journal Research of the National Bureau of Standards（1967），pp. 233-240。[5] Ehrig，H.，G.恩格斯，H. J. Kreowski和G. Rozenberg，editors，[6] Ermel，C.，M. Rudolf和G. Taentzer，551-603[7] Fis cher，T.， J. 涅尔湖 Torunski和A. Zuendorf，Storydiagrams：Anewgraphrewritelanguage based onthe Unified Modeling Language，in：G.R. G. Engels，editor，Proc. of the 6th InternationalWorkshop on Theory and Application of Graph Transformation （ TAGT ） ， LNCS1764（1998），pp. 296-309[8] 伽马，E.，R.赫尔姆河Johnson和J. Vlissides，[9] Habel，A.，R. Heckel和G. Taentzer，Graph grammars with negative application conditions，Fundamenta Informaticae26（1996），pp. 287-313[10] Klein，T.， 联合 Ni ck el，J. Niere和A. 刘文，从UML到Java的，北京大学出版社，2000年。[11] Larrosa，J.和G. Valiente，用于图模式匹配的约束满足算法，计算机科学中的数学结构12（2002），pp.403-422[12] Poole，J.，D. 张氏D.Tolbert和D.Mellor，2002年。[13] 罗森伯格，G.，编辑，G. Varro等人理论计算机科学电子笔记152（2006）191205[14] S chürr，A.， A. Winter和A. Zündorf，“In [ 5 ]，chapter PR OGRES：Languageand Environment，”World Scienti fic，1999.[15] Strau b e，D. D. 和M. T. 吴文，面向对象数据管理系统中的查询优化与执行计划生成，知识与数据工程7（1995），页。210-227.[16] Ullman，J.D.，Widom和H. Garcia-Molina，[17] Vo，D.，G. V和A。Pataricza，设计可视化语言的自动转换，计算机程序设计科学44（2002），pp.205-227[18] 你好，G。、杨A. Schürr和D. V'o，2005年，《语法分析基准》，2005年被VL/HCC接受[19] 你好 GA.Schürr 和 D.Var'o， Benchmarkingforgrapht r ansformatio n ， Te chnical ReportTUB-TR-05-EE17，Budapest University of Technology and Economics（2005），http：//www. cs.bme.hu/ www.example.com[20] Vizhanyo，A.，A. Agrawal和F.Shi，Towards generation of efficient transformations，in：G. Karsai和E. Visser，editors，Proc. of 3rd Int. Conf. on Generative Programming andComponent Engineering（GPCE 2004），LNCS3286（2004），pp. 298-316[21] Zündorf，A.，P R OGRE S中的G raphpattern-matching，in：P roc. 第五届国际 G raph文法及其在计算机科学中的应用研讨会，LNCS 1073（1996），pp. 454-468