劉禹鋒，朱 云，曾曉勤

（河海大學(xué) 計算機與信息學(xué)院，江蘇 南京211100）

0 引 言

EGG 在ER 圖上的應(yīng)用的研究目標(biāo)是為ER 圖的結(jié)構(gòu)的合法性驗證提供形式化的方法，該方法可以有效地檢測出幾種常見的結(jié)構(gòu)不規(guī)范的ER 圖，為數(shù)據(jù)庫設(shè)計人員提供了方便。

圖文法是一種定義和分析圖語言的形式化工具，是從一維字符文法自然發(fā)展而來，可以用來實現(xiàn)二維圖的生成和分析。經(jīng)過多年的發(fā)展，圖文法被大量應(yīng)用于過程流圖描述、UML圖行為語義描述、設(shè)計模式演化及軟件系統(tǒng)結(jié)構(gòu)描述等領(lǐng)域［1－5］。圖文法主要分為上下文無關(guān)圖文法和上下文相關(guān)圖文法。上下文無關(guān)圖文法是指產(chǎn)生式的左端有且只有一個非終結(jié)點的圖文法。上下文無關(guān)圖文法由于產(chǎn)生式左端是唯一的非終結(jié)點，因此在對圖進行推導(dǎo)操作時，圖柄始終是唯一的非終結(jié)點［6］，這種約束導(dǎo)致了上下文無關(guān)圖文法的表達(dá)能力不如上下文相關(guān)圖文法。由于上下文相關(guān)圖文法的表達(dá)能力更強，因此近年來上下文相關(guān)圖文法成為研究的熱點。EGG （edge－based graph grammar）［7］作為一種上下文相關(guān)圖文法，與其它上下文相關(guān)圖文法相比較為簡潔［8］，在用結(jié)構(gòu)簡單的圖在主圖中尋找句柄時，可以有效地降低圖匹配過程的復(fù)雜性［6］。

1 圖文法EGG

EGG 是一種基于邊的上下文相關(guān)的圖文法形式化框架，它解決了圖文法中的主要問題——嵌入問題［5］。所謂嵌入問題，是指在用產(chǎn)生式的左端或者右端替換圖柄時，需要保證不產(chǎn)生懸邊而要解決的問題。由于本文討論的是EGG 在ER 圖上的應(yīng)用，而ER 圖主要為無向圖，所以本文所介紹的規(guī)則均為關(guān)于無向圖的EGG 規(guī)則。關(guān)于無向圖的EGG 的形式化定義如下：

定義1 G＝（V，E，l，u）是一個標(biāo)號集L 上的無向圖，其中，V 是無向圖中結(jié)點的集合，由非終結(jié)點VN和終結(jié)點VT構(gòu)成；E 是邊的結(jié)合；l是一個函數(shù)V→L，表示了結(jié)點和標(biāo)號的對應(yīng)關(guān)系；u：E→Ω是邊的端點函數(shù)，表示了邊和該邊的端點之間的關(guān)系，Ω為邊的端點對的集合。

定義1中的圖可以看作是定義2 所定義的圖的特例，即定義2中懸邊集E為空的情況下的圖。

定義3 產(chǎn)生式是指在標(biāo)號集L 以及懸邊標(biāo)號集M 上的一組形如QL：＝QR的懸邊圖，其中QL表示產(chǎn)生式的左圖，QR表示產(chǎn)生式的右圖。需要注意的是當(dāng)產(chǎn)生式的左邊是初始圖時，產(chǎn)生式的右圖必須是沒有懸邊的圖。

圖1中（1.1）為一個產(chǎn)生式的例子，產(chǎn)生式左端和右端的懸邊必須一一對應(yīng)，EGG 中用標(biāo)號表示這種對應(yīng)，以避免替換時邊的連接問題。另外，EGG 的產(chǎn)生式中允許某個結(jié)點連接的懸邊的數(shù)目是不確定的，這樣的懸邊用加＊的邊表示，稱為一個懸邊組，同樣標(biāo)號的懸邊組所包含的懸邊必須是一致的［9］。圖1中（1.2）是一個擁有懸邊組的產(chǎn)生式的例子。

圖1 EGG 的產(chǎn)生式示例

定義4 對于兩個圖G＝（V，E，L，u）和G′＝（V′，E′，L′，u′），如果存在兩個雙射hV：VV′和hE：EE′滿足下面兩個條件，則稱G 和G′同構(gòu)，記作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òu)，并且任意一組對應(yīng)結(jié)點在G 和Q 中的度相同，則將X 稱作Q 在G 中的圖柄，記為redex（G，Q）。

定義7 如果圖G 的子圖X 是一個產(chǎn)生式p 的右端QR的圖柄，那么可用此產(chǎn)生式的左端QL代替X 在G 中的位置而產(chǎn)生一個新圖G′，這個操作定義為歸約操作，步驟如下：

（1）在G 中刪除子圖X 以及端點落在X 上的所有結(jié)點的邊；

（2）將QL連接到當(dāng)前圖中：對QL中的每條懸邊，找到QR阿中與具有相同標(biāo)記的懸邊，根據(jù)圖柄決定的映射關(guān)系g 下對應(yīng)的邊，將連接到落在G－X 中的端點上。

上面描述的是圖文法EGG 對主圖的歸約操作，歸約可以判定一個圖是否屬于某個文法產(chǎn)生的語言；反之，用產(chǎn)生式的右端替換主圖中和產(chǎn)生式左端同構(gòu)的子圖的過程是EGG 對主圖的推導(dǎo)操作，由初始圖推導(dǎo)產(chǎn)生的圖的集合稱為圖文法的語言，推導(dǎo)可以定義一個圖語言以及實施圖轉(zhuǎn)換。有關(guān)EGG 圖文法語法分析算法更詳細(xì)的描述，可參考文獻 ［10］。

2 ER 圖

2.1 ER 圖介紹

ER圖即實體聯(lián)系圖，是一種可視化的圖形方法，最初是由華裔科學(xué)家陳品山發(fā)明，用于概念數(shù)據(jù)模型的高層描述。ER 圖一般用在信息系統(tǒng)設(shè)計的第一階段，例如在需求分析階段描述數(shù)據(jù)的特征。

ER 圖的基本元素有3個，分別是實體、聯(lián)系和屬性。實體是現(xiàn)實生活中區(qū)別于其它對象的有形物體或無形事件，在ER 圖中用矩形框表示；聯(lián)系是多個實體之間的互相關(guān)聯(lián)，在ER 圖中用菱形框表示；屬性是實體或聯(lián)系中具有描述性的特性值，在ER 圖中用橢圓框表示。圖2是一個簡單的ER 圖的結(jié)構(gòu)。通過無向邊表達(dá)基本元素之間的關(guān)系，圖2是一個簡單的ER 圖的結(jié)構(gòu)。目前由于ER 圖廣泛應(yīng)用，誕生了多種衍生出的結(jié)構(gòu)，例如一元聯(lián)系、復(fù)合屬性、強弱實體集等，本文只考慮最基本的ER 圖的結(jié)構(gòu)，涉及更多額外衍生出的結(jié)構(gòu)可以通過定義與其結(jié)構(gòu)相關(guān)的產(chǎn)生式來分析。

圖2 ER 圖的基本結(jié)構(gòu)

2.2 ER 圖的格式規(guī)范

ER圖可以直觀地表達(dá)現(xiàn)實世界的對象的特征和對象之間的聯(lián)系，基本的ER 圖結(jié)構(gòu)比較簡單，但是在設(shè)計一些較復(fù)雜的數(shù)據(jù)庫時，ER 圖的結(jié)構(gòu)也會變得非常龐大。設(shè)計人員在繪制ER 圖時難免出錯，根據(jù)ER 圖的定義，ER 圖有幾種常見的錯誤：

（1）實體之間不通過聯(lián)系直接連接，如圖3所示。

圖3 實體之間的錯誤結(jié)構(gòu)

（2）不同的實體或聯(lián)系關(guān)聯(lián)同一個屬性，如圖4所示。

圖4 不同實體的屬性之間的錯誤結(jié)構(gòu)

（3）不同的聯(lián)系之間直接相連，如圖5所示。

圖5 不同聯(lián)系之間的錯誤結(jié)構(gòu)

（4）由于本文不考慮復(fù)合屬性，在不考慮復(fù)合屬性的情況下，不同的屬性之間的連線也應(yīng)避免，如圖6所示。

圖6 不同屬性之間的錯誤結(jié)構(gòu)

（5）在不考慮一元聯(lián)系的ER 圖中，一個聯(lián)系至少和兩個實體相關(guān)聯(lián)，因此不可以只有一個實體和聯(lián)系之間有連線，如圖7所示。

圖7 實體和聯(lián)系之間的錯誤結(jié)構(gòu)

以上幾種錯誤都是工程設(shè)計人員在繪制ER 圖時經(jīng)常產(chǎn)生的，在規(guī)模較大的ER 圖中，若出現(xiàn)錯誤不僅難以檢測，而且容易導(dǎo)致在后續(xù)的邏輯設(shè)計階段產(chǎn)生更嚴(yán)重的錯誤。

3 用EGG 圖文法判定ER 圖結(jié)構(gòu)合法性

3.1 ER 圖預(yù)處理

（1）將ER 圖中的表示實體、聯(lián)系和屬性的各種形狀轉(zhuǎn)變成圓形結(jié)點，將原始的ER 圖轉(zhuǎn)變?yōu)閳D論里面的圖的形式，以便在此基礎(chǔ)上進行分析操作。

（2）本文使用EGG 的目的是對ER 圖的結(jié)構(gòu)合法性進行判定，而在分析ER 圖的結(jié)構(gòu)信息時，可暫不考慮其語義信息，因此在預(yù)處理中將原始ER 圖的語義信息存入結(jié)點的數(shù)據(jù)結(jié)構(gòu)中，并在數(shù)據(jù)結(jié)構(gòu)中設(shè)置一個標(biāo)志位，表明結(jié)點的性質(zhì)（實體、聯(lián)系或?qū)傩裕?，這些結(jié)點的性質(zhì)在可視化圖中用產(chǎn)生式中的結(jié)點中的字母表示該結(jié)點在ER 圖中的類型，E或e表示實體，R 或r表示聯(lián)系，A 表示屬性，字母的大小寫的區(qū)分表明結(jié)點是否終結(jié)符，大寫表示終結(jié)符，小寫表示非終結(jié)符。如圖8所示。

圖8 預(yù)處理中初始ER 圖的變換

3.2 EGG 產(chǎn)生式設(shè)計

對于ER 圖結(jié)構(gòu)的合法性的驗證需要定義與其結(jié)構(gòu)的約束相對應(yīng)的產(chǎn)生式，在通過產(chǎn)生式對主圖進行歸約操作時，如果能歸約到初始圖，則說明該ER 圖的結(jié)構(gòu)是合法的，相應(yīng)的，如果歸約不到初始圖，則說明該ER 圖的結(jié)構(gòu)不合法。根據(jù)ER 圖的結(jié)構(gòu)特點，定義了圖9所示的產(chǎn)生式組。以歸約操作為例，在圖9描述的產(chǎn)生式組中，p1中的左端是一個初始圖，右端是一個實體，用于歸約操作的最后一步；p2可以作用于實體的刪減；p3可以在兩個實體間刪減聯(lián)系；p4 和p5 作用于實體或聯(lián)系的屬性刪減；p6可以作用于多元聯(lián)系，可以在多元聯(lián)系中刪減一個實體和聯(lián)系之間的關(guān)聯(lián)；p7和p8用于將實體和聯(lián)系終結(jié)符轉(zhuǎn)換成非終結(jié)符，在圖9 所示的產(chǎn)生式組中，所有的屬性都是終結(jié)符。

由于這組產(chǎn)生式均是依據(jù)ER 圖的標(biāo)準(zhǔn)規(guī)范所定義，從而結(jié)構(gòu)不合法的ER 圖均不能根據(jù)這組產(chǎn)生式歸約到初始圖，因此可以通過關(guān)于這組產(chǎn)生式的歸約操作對ER 圖的結(jié)構(gòu)的合法性進行判定。

3.3 EGG 歸約操作對ER 圖合法性判定

本文通過EGG 的歸約操作分析ER 圖的結(jié)構(gòu)的合法性，給定一個ER 圖，如果能夠歸約到初始圖，則該ER 圖的結(jié)構(gòu)是合法的，如果歸約不到初始圖，則該ER 圖的結(jié)構(gòu)是不合法的。歸約步驟分為三步：

（1）用產(chǎn)生式p7和p8的右端在主圖中尋找圖柄，并用產(chǎn)生式的左端替換主圖中的圖柄，即將主圖中的實體和聯(lián)系都轉(zhuǎn)換成非終結(jié)符；

（2）用p1到p6中每一個產(chǎn)生式的右端在主圖中尋找圖柄；

圖9 ER 圖應(yīng)用中的產(chǎn)生式組

（3）若找到圖柄，則用該產(chǎn)生式的左端對主圖的圖柄進行替換后，執(zhí)行（2）；若沒找到圖柄，并且此時的主圖是含有標(biāo)號＃的初始圖，則歸約成功；若沒找到圖柄，而此時的主圖不是初始圖，則規(guī)約失敗。

3.4 ER 圖的合法性驗證實例

圖10是一個ER 圖的結(jié)構(gòu)的合法性驗證的具體過程，原ER 圖是一個具有二元聯(lián)系和三元聯(lián)系的ER 圖，對主圖的歸約分析過程，可概括為以下幾步：

（1）對原ER 圖預(yù)處理操作將ER 圖轉(zhuǎn)換成圖論中的圖，并將結(jié)點的語義信息存入結(jié)點的數(shù)據(jù)結(jié)構(gòu)中；

（2）再用產(chǎn)生式p7，p8將代表實體和聯(lián)系的結(jié)點轉(zhuǎn)換成非終結(jié)符；

（3）用產(chǎn)生式p4，p5在主圖中去掉代表屬性的結(jié)點；

（4）用產(chǎn)生式p6 將主圖中的多元聯(lián)系轉(zhuǎn)變?yōu)槎?lián)系；

（5）用產(chǎn)生式p3去掉主圖中所有的二元聯(lián)系；

（6）用產(chǎn)生式p2將主圖轉(zhuǎn)換成只有一個結(jié)點的圖；

（7）用產(chǎn)生式p1將主圖轉(zhuǎn)換成帶有標(biāo)號＃的初始圖，歸約成功。

4 結(jié)束語

圖10 ER 圖的合法性判定的實例

作為一種直觀的二維圖，ER 圖在關(guān)系數(shù)據(jù)庫設(shè)計中被廣泛使用，然而設(shè)計人員在設(shè)計復(fù)雜的ER 圖時難免會出現(xiàn)差錯，這就對檢查任意給出ER 圖的合法性提出了需求。圖文法是一種能有效分析二維圖的形式化工具，通過設(shè)計合適的文法產(chǎn)生式，用基于歸約操作的分析算法，可判定給定圖的結(jié)構(gòu)合法性。本文給出了用圖文法EGG 有效地判定ER 圖結(jié)構(gòu)合法性的方法，避免了數(shù)據(jù)庫概念設(shè)計階段的錯誤導(dǎo)致后續(xù)的邏輯設(shè)計階段錯誤，為接下來從ER 圖自動生成所需范式的關(guān)系模式奠定研究基礎(chǔ)。

［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）.［石兵，冉平，馬曉星，等.軟件體系結(jié)構(gòu)的屬性圖文法描述及其約束驗證 ［J］.計算機應(yīng)用研究，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）.［馬曉星，曹春，余萍，等.基于圖文法的動態(tài)軟件體系結(jié)構(gòu)支撐環(huán)境［J］.軟件學(xué)報，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］.計算機科學(xué)，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）.［曾曉勤，韓秀清，鄒陽.一種基于邊的上下文相關(guān)圖文法形式化框架［J］，軟件學(xué)報，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）.［鄒陽，呂建，曹春，等.上下文相關(guān)圖文法的表達(dá)能力分析 ［J］.軟件學(xué)報，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 在設(shè)計模式中的應(yīng)用［J］.計算機工程與科學(xué)，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］.計算機科學(xué)，2012，39 （10）：272－277.］