基于元數據邏輯無關片斷的結構完整性檢測方法

趙曉非 史忠植 劉建偉

1(天津工業大學計算機科學與技術學院 天津 300387) 2(江蘇省計算機信息處理技術重點實驗室(蘇州大學) 江蘇蘇州 215006) 3(中國科學院計算技術研究所智能信息處理重點實驗室 北京 100190)zhaoxiaofei1978@hotmail.com)

作為對象管理組織(object management group, OMG)提出的主要標準之一，元對象設施(meta object facility, MOF)[1]已經成為國際主流的元數據存儲庫標準.MOF存儲庫系統中元數據的組織方式，即元數據的結構呈現出一種分層的、多級的并且動態變化的復雜結構，因此保持該種系統的一致性是一項重要任務.MOF存儲庫系統中的一致性包括：1)操作一致性.涉及存儲庫應用間的交互，與存儲庫事務的概念密切相關，它又分為協作原子性和并發多用戶訪問.2)元數據完整性.包括結構完整性和良格式.良格式確保單一層次中元素的語法正確性，而結構完整性確保1個層次中的元素符合與該層相鄰的、更高的元層次中的類型定義[1].

結構完整性是MOF存儲庫系統一致性的重要組成部分.如果結構完整性得不到保證，存儲庫應用就可能修改或建立Mn層中的元數據元素而與Mn+1層中它們的元類相沖突.例如，1個操作可能會讀取某個元素的屬性，而該元素的元類并不存在，則該操作是無效的.1個數據庫系統包含M0層到M2層.而為了提供可自定義、可擴展的系統框架，MOF標準引入了允許用戶對M2層進行定義的M3層，在運行時刻M0，M1，M2層均可以被動態修改，因而就可能導致相鄰層次之間的沖突問題，即結構完整性問題.其他系統并不面臨這類問題，因為它們假定系統框架在運行時刻是靜止的.

為了自動地執行結構完整性檢測，不同的方法被相繼提出，其中影響比較大的有3種:1)Muzaffar等人[2-3]為MOF存儲庫系統的形式化、查詢和結構完整性檢測提出了一種統一的框架OMLM.該框架采用F邏輯作為形式化機制.在文獻[2]中他們利用F邏輯的開源實現Flora-2對各層次元數據進行描述并利用推理機MULLER執行結構完整性檢測.他們在文獻[3]進一步提出了Realization維度的概念并據此建立了MOF框架與Flora-2之間的映射，隨后采用模型轉換技術(MTT)開發了到Flora-2的轉換工具，從而實現了形式化描述的自動生成.利用F邏輯形式化MOF框架并進行推理檢測的還有Bernd等人[4]的工作.2)Liliana等人[5]采用了基于代數的形式化機制，他們首先針對MOF的層次結構提出了一種基于代數演算的形式化元建模語言NEREUS并為之開發了推理接口.NEREUS利用Instantiation-算子來建模相鄰層次之間的類型-實例關系.NEREUS不僅可以實現結構完整性檢測，也可以實現良格式約束的檢測.3)Esther等人[6-7]提出了一種對MOF框架的相鄰層次進行壓扁(flattening)處理以檢測結構完整性的方法并實現了原型工具metaDepth.他們提取出元層次中與結構完整性約束有關的特性(如元素之間的引用關系、屬性的類型以及多重性等)，然后與相鄰的下層元數據進行合并從而得到單層的元數據知識庫，而后采用良設計的算法實現檢測.

1 存儲庫元數據的形式化

1.1 Mn+1層的形式化

1) 元類及元屬性

2) 元-關聯類

元層次中的元-關聯類如圖1所示.每個元-關聯類都包含2個存在多重性約束的關聯端.與元屬性不同的是，在MOF框架中元-關聯類的名字是唯一的.

Fig. 1 Meta-association class in level Mn+1圖1 Mn+1層中的元-關聯類

由于每個關聯端表示相應端的元類與元-關聯類之間的2元關系(即該元類以何種身份參與元-關聯類)，我們將元類C和C′之間的元-關聯類A(關聯端分別為r1和r2)形式化為1個概念A和2個角色r1和r2，其中r1和r2分別對應于關聯端r1和r2，r1以C和A作為第1和第2個要素，而r2以C′和A作為第1和第2個要素，因此r1端和r2端的取值限定被形式化為

C?r1.A；
C′?r2.A；
A

C(≥i1r1.A)(≤j1r1.A)；
C′(≥i2r2.A)(≤j2r2.A).

3) 元關聯

Fig. 2 Meta-association in level Mn+1圖2 Mn+1層中的元關聯

元關聯如圖2所示，用于表明2個元類的實例之間的2元關系.例如元關聯R描述了元類StructuralFeature和UniqueKey之間2元關系.R的多重性描述了每個UniqueKey的實例至少和1個StructuralFeature的實例相關聯.

由于元關聯本質上是一種2元關系，因此我們將元類C和C′之間的元關聯R形式化為1個角色R并用下述斷言描述R的取值限定：

C?R.C′；
C′?R-.C.

C的多重性i1..j1和C′的多重性i2..j2則分別被形式化為

C(≥i1R.C′)(≤j1R.C′)；
C′(≥i2R.C)(≤j2R.C).

4) 泛化

MOF框架中的泛化關系表明子類的每個實例也是父類的實例.因此子類的實例繼承了父類的屬性，此外它們還可以定義自己的屬性.

1.2 Mn層的形式化

1) 若Mn層元素c是其元層次中元類C的實例，則將其形式化為C(c)；

2) 若Mn層元素c關聯了c′，相應的元類C(或其祖先)通過元關聯R與元類C′(或其祖先)相聯系，元關聯R被形式化為Tbox中的角色R，則將c和c′之間的關系形式化為R(c，c′)；

3) 若Mn層元素c關聯了c′，相應的元類C(或其祖先)通過元-關聯類A與元類C′(或其祖先)相聯系，而元-關聯類被形式化為概念A和角色r1，r2，則將c和c′之間的關系形式化為3個斷言A(a)，r1(c，a)，r2(c′，a).

2 元數據邏輯無關片斷的抽取

2.1 基本思路

我們的目標是劃分出精確的元數據片斷，該片斷僅包含對給定簽名必不可少的斷言，從而使得產生的片斷在保持信息完備性的同時具有最小的規模.簡單地說，要使得斷言對于給定簽名S必不可少，它們必須能夠影響S中任意元數據元素的邏輯結論，為了區分這種斷言，我們給出定義4：

證畢.

通過定理1可知，由于簽名S中每個元素的邏輯無關片斷的并集即為S的邏輯無關片斷，因此我們僅需為S中單個元數據元素的邏輯無關片斷的計算提出算法即可.

由第2種斷言我們得到:

其中C1是b的類屬概念.

其中C3是將元素a作為要素的所有其他角色斷言的限定性概念的合取.

2.4 邏輯無關片斷的抽取算法

證畢.

3 基于邏輯無關片斷的結構完整性檢測

根據結構完整性約束，如果某個操作修改了元層次中某元屬性的類型，若新類型不是原有類型的超類且原有類型是元層次中已存在的元類，而下級層次中該元屬性的相應實例沒有被修改則會產生結構完整性沖突之一——屬性類型沖突.該類沖突可以通過定義函數1來檢測(假定元類Property的元屬性referencedType的類型由StructuredType變為SimpleType，而非DataType等超類型，如圖3所示)：

Fig. 3 An example for property type inconsistency圖3 屬性類型沖突示例

if (count1>count2)

print(“Property type inconsistency: some fillers do not belong to the type #.”,referencedType).)

下例是多重性沖突的檢測.根據結構完整性約束，如果某個操作修改了元層次中的關聯端的多重性，而下級層次中的元素沒有被相應修改,則可能會導致相應實例數目與修改后的多重性發生沖突.可以通過定義函數2來檢測該類沖突(假定Association和AssociationEnd間的元關聯在AssociationEnd端的多重性由1改為2)：

count1=|ans(associationEnd)←body

association,associationEnd))|;

count2=get-min-cardinality((get-conceptAssociation)(get-relationAssociation-AssociationEnd));

if (count1

print(“AssociationEnd multiplicity inconsistency:#associates#elements,at least # is needed.”,association,count1,count2).)

4 方法有效性評測

為了評測本文方法的有效性，我們進行了大量實驗，重點測試了抽取元數據片斷對結構完整性檢測效率的提升，并對本方法與前述3種主要方法(OMLM，NEREUS，metaDepth)的檢測時間性能進行對比.所有實驗是在Intel i5-8265U、8 GB內存和Windows 10操作系統的環境下執行的.實驗采用基于MOF 2.5.1框架的元數據集ReMoDD[14]作為測試集，我們隨機地選擇4個檢測任務：ColumnSet的屬性類型沖突、Dimension的屬性類型沖突、TableOwning的多重性沖突以及SchemaOwning的多重性沖突并分別使用2種推理機HermiT和FaCT++執行檢測.測試結果如表1和圖4所示.

從實驗結果來看，無論采用何種推理機，本文的方法在4種檢測任務上的表現均大幅優于NEREUS方法.值得注意的是，在采用HermiT推理機時，我們的方法執行2個多重性沖突檢測任務的平均時間508.20 s不如OMLM方法的444.67 s，這一差距在FaCT++的情況下(596.66 s)甚至更大，即便如此，由于本方法在屬性類型沖突檢測中的優勢，4種任務的平均執行時間509.45 s(HermiT)和520.88 s(FaCT++)仍略優于OMLM方法的531.16 s.這一結果在與metaDepth方法(611.60 s)的對比中同樣得以反應.綜合來看，在實驗元數據集上，我們的方法取得了顯著優于NEREUS方法但略優于OMLM和metaDepth方法的結果.

Table 1 Experimental Results for Extracting Logically Independent Fragment表1 抽取邏輯無關片斷的實驗結果

Fig. 4 Time performance comparison with related approaches圖4 與相關方法的時間性能比較

5 結 論

通過在抽取出的元數據片斷上進行查詢推理，本文提出了一種高效、自動地檢測MOF存儲庫系統的結構完整性的方法.我們研究了將層次化的元數據轉化為描述邏輯知識庫的方法；最小邏輯無關片斷的獲取方法以及基于該片斷的結構完整性檢測方法.為了證明方法的正確性，我們給出了嚴格的形式化證明.由于抽取出的元數據子集是原始集合的邏輯蘊含的閉包，因此待查詢元素的所有邏輯結論均得以保留從而使得本方法在不改變檢測結果的前提下具有較高的效率.實驗過程組合了不同的推理機和檢測任務，結果表明邏輯無關片斷的抽取可以顯著地提高檢測的效率以及本方法具有優于相關方法的時間性能.