圖文法EGG 在ER 圖設計中的應用

劉禹鋒，朱 云，曾曉勤

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

0 引 言

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

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

1 圖文法EGG

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

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

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

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

圖1中（1.1）為一個產(chǎn)生式的例子，產(chǎn)生式左端和右端的懸邊必須一一對應，EGG 中用標號表示這種對應，以避免替換時邊的連接問題。另外，EGG 的產(chǎn)生式中允許某個結點連接的懸邊的數(shù)目是不確定的，這樣的懸邊用加＊的邊表示，稱為一個懸邊組，同樣標號的懸邊組所包含的懸邊必須是一致的［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≈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 是一個產(chǎn)生式p 的右端QR的圖柄，那么可用此產(chǎn)生式的左端QL代替X 在G 中的位置而產(chǎn)生一個新圖G′，這個操作定義為歸約操作，步驟如下：

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

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

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

2 ER 圖

2.1 ER 圖介紹

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

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

圖2 ER 圖的基本結構

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

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

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

圖3 實體之間的錯誤結構

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

圖4 不同實體的屬性之間的錯誤結構

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

圖5 不同聯(lián)系之間的錯誤結構

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

圖6 不同屬性之間的錯誤結構

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

圖7 實體和聯(lián)系之間的錯誤結構

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

3 用EGG 圖文法判定ER 圖結構合法性

3.1 ER 圖預處理

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

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

圖8 預處理中初始ER 圖的變換

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

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

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

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

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

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

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

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

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

3.4 ER 圖的合法性驗證實例

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

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

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

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

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

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

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

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

4 結束語

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

作為一種直觀的二維圖，ER 圖在關系數(shù)據(jù)庫設計中被廣泛使用，然而設計人員在設計復雜的ER 圖時難免會出現(xiàn)差錯，這就對檢查任意給出ER 圖的合法性提出了需求。圖文法是一種能有效分析二維圖的形式化工具，通過設計合適的文法產(chǎn)生式，用基于歸約操作的分析算法，可判定給定圖的結構合法性。本文給出了用圖文法EGG 有效地判定ER 圖結構合法性的方法，避免了數(shù)據(jù)庫概念設計階段的錯誤導致后續(xù)的邏輯設計階段錯誤，為接下來從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）.［馬曉星，曹春，余萍，等.基于圖文法的動態(tài)軟件體系結構支撐環(huán)境［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.］