刘禹锋，朱 云，曾晓勤

（河海大学 计算机与信息学院，江苏 南京211100）

0 引 言

EGG 在ER 图上的应用的研究目标是为ER 图的结构的合法性验证提供形式化的方法，该方法可以有效地检测出几种常见的结构不规范的ER 图，为数据库设计人员提供了方便。

图文法是一种定义和分析图语言的形式化工具，是从一维字符文法自然发展而来，可以用来实现二维图的生成和分析。经过多年的发展，图文法被大量应用于过程流图描述、UML图行为语义描述、设计模式演化及软件系统结构描述等领域［1－5］。图文法主要分为上下文无关图文法和上下文相关图文法。上下文无关图文法是指产生式的左端有且只有一个非终结点的图文法。上下文无关图文法由于产生式左端是唯一的非终结点，因此在对图进行推导操作时，图柄始终是唯一的非终结点［6］，这种约束导致了上下文无关图文法的表达能力不如上下文相关图文法。由于上下文相关图文法的表达能力更强，因此近年来上下文相关图文法成为研究的热点。EGG （edge－based graph grammar）［7］作为一种上下文相关图文法，与其它上下文相关图文法相比较为简洁［8］，在用结构简单的图在主图中寻找句柄时，可以有效地降低图匹配过程的复杂性［6］。

1 图文法EGG

EGG 是一种基于边的上下文相关的图文法形式化框架，它解决了图文法中的主要问题——嵌入问题［5］。所谓嵌入问题，是指在用产生式的左端或者右端替换图柄时，需要保证不产生悬边而要解决的问题。由于本文讨论的是EGG 在ER 图上的应用，而ER 图主要为无向图，所以本文所介绍的规则均为关于无向图的EGG 规则。关于无向图的EGG 的形式化定义如下：

定义1 G＝（V，E，l，u）是一个标号集L 上的无向图，其中，V 是无向图中结点的集合，由非终结点VN和终结点VT构成；E 是边的结合；l是一个函数V→L，表示了结点和标号的对应关系；u：E→Ω是边的端点函数，表示了边和该边的端点之间的关系，Ω为边的端点对的集合。

定义1中的图可以看作是定义2 所定义的图的特例，即定义2中悬边集E为空的情况下的图。

定义3 产生式是指在标号集L 以及悬边标号集M 上的一组形如QL：＝QR的悬边图，其中QL表示产生式的左图，QR表示产生式的右图。需要注意的是当产生式的左边是初始图时，产生式的右图必须是没有悬边的图。

图1中（1.1）为一个产生式的例子，产生式左端和右端的悬边必须一一对应，EGG 中用标号表示这种对应，以避免替换时边的连接问题。另外，EGG 的产生式中允许某个结点连接的悬边的数目是不确定的，这样的悬边用加＊的边表示，称为一个悬边组，同样标号的悬边组所包含的悬边必须是一致的［9］。图1中（1.2）是一个拥有悬边组的产生式的例子。

图1 EGG 的产生式示例

定义4 对于两个图G＝（V，E，L，u）和G′＝（V′，E′，L′，u′），如果存在两个双射hV：VV′和hE：EE′满足下面两个条件，则称G 和G′同构，记作G≈G′

v∈V：l′（hV（v））＝l（v）

e∈E：hV（u（e））＝u′（hE（e））

定义5 对于一个悬边图Q，将Q 的悬边去掉的图称为其核图，记作K（Q）。

定义6 X 是G 的一个子图，Q 是一个悬边图，如果X和K（Q）同构，并且任意一组对应结点在G 和Q 中的度相同，则将X 称作Q 在G 中的图柄，记为redex（G，Q）。

定义7 如果图G 的子图X 是一个产生式p 的右端QR的图柄，那么可用此产生式的左端QL代替X 在G 中的位置而产生一个新图G′，这个操作定义为归约操作，步骤如下：

（1）在G 中删除子图X 以及端点落在X 上的所有结点的边；

（2）将QL连接到当前图中：对QL中的每条悬边，找到QR阿中与具有相同标记的悬边，根据图柄决定的映射关系g 下对应的边，将连接到落在G－X 中的端点上。

上面描述的是图文法EGG 对主图的归约操作，归约可以判定一个图是否属于某个文法产生的语言；反之，用产生式的右端替换主图中和产生式左端同构的子图的过程是EGG 对主图的推导操作，由初始图推导产生的图的集合称为图文法的语言，推导可以定义一个图语言以及实施图转换。有关EGG 图文法语法分析算法更详细的描述，可参考文献 ［10］。

2 ER 图

2.1 ER 图介绍

ER图即实体联系图，是一种可视化的图形方法，最初是由华裔科学家陈品山发明，用于概念数据模型的高层描述。ER 图一般用在信息系统设计的第一阶段，例如在需求分析阶段描述数据的特征。

ER 图的基本元素有3个，分别是实体、联系和属性。实体是现实生活中区别于其它对象的有形物体或无形事件，在ER 图中用矩形框表示；联系是多个实体之间的互相关联，在ER 图中用菱形框表示；属性是实体或联系中具有描述性的特性值，在ER 图中用椭圆框表示。图2是一个简单的ER 图的结构。通过无向边表达基本元素之间的关系，图2是一个简单的ER 图的结构。目前由于ER 图广泛应用，诞生了多种衍生出的结构，例如一元联系、复合属性、强弱实体集等，本文只考虑最基本的ER 图的结构，涉及更多额外衍生出的结构可以通过定义与其结构相关的产生式来分析。

图2 ER 图的基本结构

2.2 ER 图的格式规范

ER图可以直观地表达现实世界的对象的特征和对象之间的联系，基本的ER 图结构比较简单，但是在设计一些较复杂的数据库时，ER 图的结构也会变得非常庞大。设计人员在绘制ER 图时难免出错，根据ER 图的定义，ER 图有几种常见的错误：

（1）实体之间不通过联系直接连接，如图3所示。

图3 实体之间的错误结构

（2）不同的实体或联系关联同一个属性，如图4所示。

图4 不同实体的属性之间的错误结构

（3）不同的联系之间直接相连，如图5所示。

图5 不同联系之间的错误结构

（4）由于本文不考虑复合属性，在不考虑复合属性的情况下，不同的属性之间的连线也应避免，如图6所示。

图6 不同属性之间的错误结构

（5）在不考虑一元联系的ER 图中，一个联系至少和两个实体相关联，因此不可以只有一个实体和联系之间有连线，如图7所示。

图7 实体和联系之间的错误结构

以上几种错误都是工程设计人员在绘制ER 图时经常产生的，在规模较大的ER 图中，若出现错误不仅难以检测，而且容易导致在后续的逻辑设计阶段产生更严重的错误。

3 用EGG 图文法判定ER 图结构合法性

3.1 ER 图预处理

（1）将ER 图中的表示实体、联系和属性的各种形状转变成圆形结点，将原始的ER 图转变为图论里面的图的形式，以便在此基础上进行分析操作。

（2）本文使用EGG 的目的是对ER 图的结构合法性进行判定，而在分析ER 图的结构信息时，可暂不考虑其语义信息，因此在预处理中将原始ER 图的语义信息存入结点的数据结构中，并在数据结构中设置一个标志位，表明结点的性质（实体、联系或属性），这些结点的性质在可视化图中用产生式中的结点中的字母表示该结点在ER 图中的类型，E或e表示实体，R 或r表示联系，A 表示属性，字母的大小写的区分表明结点是否终结符，大写表示终结符，小写表示非终结符。如图8所示。

图8 预处理中初始ER 图的变换

3.2 EGG 产生式设计

对于ER 图结构的合法性的验证需要定义与其结构的约束相对应的产生式，在通过产生式对主图进行归约操作时，如果能归约到初始图，则说明该ER 图的结构是合法的，相应的，如果归约不到初始图，则说明该ER 图的结构不合法。根据ER 图的结构特点，定义了图9所示的产生式组。以归约操作为例，在图9描述的产生式组中，p1中的左端是一个初始图，右端是一个实体，用于归约操作的最后一步；p2可以作用于实体的删减；p3可以在两个实体间删减联系；p4 和p5 作用于实体或联系的属性删减；p6可以作用于多元联系，可以在多元联系中删减一个实体和联系之间的关联；p7和p8用于将实体和联系终结符转换成非终结符，在图9 所示的产生式组中，所有的属性都是终结符。

由于这组产生式均是依据ER 图的标准规范所定义，从而结构不合法的ER 图均不能根据这组产生式归约到初始图，因此可以通过关于这组产生式的归约操作对ER 图的结构的合法性进行判定。

3.3 EGG 归约操作对ER 图合法性判定

本文通过EGG 的归约操作分析ER 图的结构的合法性，给定一个ER 图，如果能够归约到初始图，则该ER 图的结构是合法的，如果归约不到初始图，则该ER 图的结构是不合法的。归约步骤分为三步：

（1）用产生式p7和p8的右端在主图中寻找图柄，并用产生式的左端替换主图中的图柄，即将主图中的实体和联系都转换成非终结符；

（2）用p1到p6中每一个产生式的右端在主图中寻找图柄；

图9 ER 图应用中的产生式组

（3）若找到图柄，则用该产生式的左端对主图的图柄进行替换后，执行（2）；若没找到图柄，并且此时的主图是含有标号＃的初始图，则归约成功；若没找到图柄，而此时的主图不是初始图，则规约失败。

3.4 ER 图的合法性验证实例

图10是一个ER 图的结构的合法性验证的具体过程，原ER 图是一个具有二元联系和三元联系的ER 图，对主图的归约分析过程，可概括为以下几步：

（1）对原ER 图预处理操作将ER 图转换成图论中的图，并将结点的语义信息存入结点的数据结构中；

（2）再用产生式p7，p8将代表实体和联系的结点转换成非终结符；

（3）用产生式p4，p5在主图中去掉代表属性的结点；

（4）用产生式p6 将主图中的多元联系转变为二元联系；

（5）用产生式p3去掉主图中所有的二元联系；

（6）用产生式p2将主图转换成只有一个结点的图；

（7）用产生式p1将主图转换成带有标号＃的初始图，归约成功。

4 结束语

图10 ER 图的合法性判定的实例

作为一种直观的二维图，ER 图在关系数据库设计中被广泛使用，然而设计人员在设计复杂的ER 图时难免会出现差错，这就对检查任意给出ER 图的合法性提出了需求。图文法是一种能有效分析二维图的形式化工具，通过设计合适的文法产生式，用基于归约操作的分析算法，可判定给定图的结构合法性。本文给出了用图文法EGG 有效地判定ER 图结构合法性的方法，避免了数据库概念设计阶段的错误导致后续的逻辑设计阶段错误，为接下来从ER 图自动生成所需范式的关系模式奠定研究基础。

［1］Zou Y，Zeng XQ，Han XQ，et al.Context－attributed graph grammar framework for specifying visual languages［J］.Journal of Southeast University（English Edition），2008，24 （4）：455－461.

［2］Kong J，Zhao CY.Visual language techniques for software development［J］.Journal of Software，2008，19 （8）：1902－1919.

［3］Zhao CY，Kong J，Dong J，et al.Pattern based design evolution using graph transformation ［J］.Journal of Visual Languages and Computing，2007，18 （4）：378－398.

［4］SHI Bing，RAN Ping，MA Xiaoxing，et al.Attributed graph grammar－based description and constraints verification of software architectures ［J］.Application Research of Computers，2007，24 （3）：163－168 （in Chinese）.［石兵，冉平，马晓星，等.软件体系结构的属性图文法描述及其约束验证 ［J］.计算机应用研究，2007，24 （3）：163－168.］

［5］MA Xiaoxing，CAO Chun，YU Ping，et al.A supporting environment based on graph grammar for dynamic software architectures［J］.Journal of Software，2008，19 （8）：1881－1892（in Chinese）.［马晓星，曹春，余萍，等.基于图文法的动态软件体系结构支撑环境［J］.软件学报，2008，19 （8）：1881－1892.］

［6］HAN Xiuqin，ZENG Xiaoqin，ZOU Yang，et al.Survey of graph grammars［J］.Computer Science，2008，35 （8）：10－16 （in Chinese）. ［韩秀清，曾晓勤，邹阳，等.图文法综述［J］.计算机科学，2008，35 （8）：10－16.］

［7］ZENG Xiaoqin，HAN Xiuqing，ZOU Yang.An edge－based context－sensitive graph grammar formalism ［J］.Journal of Software，2008，19 （8）：1893－1901 （in Chinese）.［曾晓勤，韩秀清，邹阳.一种基于边的上下文相关图文法形式化框架［J］，软件学报，2008，19 （8）：1893－1901.］

［8］ZOU Yang，LV Jian，CAO Chun，et al.On the expressiveness of context－sensitive graph grammars［J］.Journal of Software，2012，23 （7）：1635－1655 （in Chinese）.［邹阳，吕建，曹春，等.上下文相关图文法的表达能力分析 ［J］.软件学报，2012，23 （7）：1635－1655.］

［9］HAN Xiuqing，ZENG Xiaoqin，ZOU Yang.Application of graph grammar EGG in design patterns ［J］.Computer Engineering ＆ Science，2010，32 （3）：104－110 （in Chinese）.［韩秀清，曾晓勤，邹阳.图文法EGG 在设计模式中的应用［J］.计算机工程与科学，2010，32 （3）：104－110.］

［10］ZHU Yun，ZENG Xiaoqin，ZHU Ning.Research on parsing algorithm of EGG graph grammar ［J］.Computer Science，2012，39 （10）：272－277 （in Chinese）. ［朱云，曾晓勤，朱宁.EGG 图文法语法分析算法的研究 ［J］.计算机科学，2012，39 （10）：272－277.］