基于描述邏輯的EER模型檢測

陳 振 慶

(賀州學(xué)院機(jī)械與電子工程學(xué)院　廣西 賀州 542899)

?

基于描述邏輯的EER模型檢測

陳 振 慶

(賀州學(xué)院機(jī)械與電子工程學(xué)院廣西 賀州 542899)

首先分析基于描述邏輯的ER模型的研究現(xiàn)狀，提出基于描述邏輯SHOIN(D)的EER模型，給出描述邏輯SHOIN(D)的語法和語義。然后研究EER模型的SHOIN(D)描述形式，以及如何將EER模型向SHOIN(D)知識庫轉(zhuǎn)化。最后給出EER模型可滿足性、冗余性判定定理，證明了這些推理問題的正確性，并利用pellet推理機(jī)實(shí)現(xiàn)了EER模型可滿足性和冗余性推理。

描述邏輯SHOIN(D)知識庫ER模型EER模型

0　引　言

描述邏輯是一種具備很強(qiáng)表達(dá)能力和可判定性的知識表示工具，具有高效的判定算法和推理機(jī)制支撐，適合于相關(guān)推理問題的研究。實(shí)體聯(lián)系ER模型是一種數(shù)據(jù)庫設(shè)計工具，是現(xiàn)實(shí)世界的抽象描述，在概念模型設(shè)計中得到廣泛應(yīng)用。隨著應(yīng)用環(huán)境的復(fù)雜化，為了準(zhǔn)確地模擬客觀世界，研究人員又?jǐn)U展了基本ER模型的概念，提出了增強(qiáng)實(shí)體聯(lián)系模型EER。Alex Borgida和Diego Calvanese等人分別提出了描述邏輯DLR和ALNUI，對ER模型的可滿足性、冗余性等相關(guān)問題進(jìn)行自動推理[1,2]。Artale 等人研究了在術(shù)語層和斷言層上建立了描述邏輯與面向?qū)ο髷?shù)據(jù)庫描述之間的映射關(guān)系[3]。李鑫等人利用Answer set編程表示ER模型，利用ER模型實(shí)現(xiàn)異構(gòu)數(shù)據(jù)庫之間的語義協(xié)作[4]，就ER模型與關(guān)系數(shù)據(jù)庫的融合進(jìn)行了理論研究。蔣運(yùn)承等人針對帶屬性依賴時序ER模型的需求和特點(diǎn),提出了時序描述邏輯A LCQI(D)US，并研究了基本時序描述邏輯ALCQI(D)US帶屬性依賴時序ER模型的自動推理問題[5]。上述研究都沒有擴(kuò)展到EER模型，也沒有進(jìn)行更具體的推理實(shí)現(xiàn)。Horrocks I等人研究了具有很強(qiáng)的表達(dá)能力的面向本體的描述邏輯語言SHOIN(D)[6]，并指出其是目前應(yīng)用最廣泛的WEB本體表示語言O(shè)WL DL的邏輯基礎(chǔ)。針對上述研究的不足，本文以描述邏輯SHOIN(D)為基礎(chǔ)，研究如何把EER模型正確轉(zhuǎn)化為SHOIN(D)知識庫，進(jìn)而轉(zhuǎn)化為OWL DL本體，再利用pellet推理機(jī)對OWL DL本體知識庫進(jìn)行推理，實(shí)現(xiàn)對EER模型的可滿足性、冗余性等問題進(jìn)行檢測。

1　SHOIN(D)語法和語義

(1) 任何概念C∈NC是SHOIN(D)概念。

(2) 任何個體名O∈NO是SHOIN(D)概念。

定義2令一個解釋I=(ΔI，·I)，ΔI為解釋域，·I為解釋函數(shù)，·I函數(shù)把概念或個體映射成ΔI的子集，對于給定的解釋I，SHOIN(D)概念必須滿足以下語義：

定義3令一個解釋I=(ΔI，·I)，ΔI為解釋域，·I為解釋函數(shù)，·I函數(shù)把角色映射成ΔI×ΔI的子集，對于給定的解釋I，SHOIN(D)角色必須滿足以下語義：

(1) RI=ΔI×ΔI。

(2)(┐R )I=ΔI×ΔIRI。

(3) (R -)I={(b,a)∈ΔI×ΔI|(a,b)∈ΔI×ΔI}}。

(4) (R1R2)I={R1，R2∈RI|(R1IR2I)∈RI}。

(5) (R1R2)I={R1，R2∈RI|(R1IR2I)∈RI}。

2　基于SHOIN (D)的EER模型

2.1EER模型

定義4令X和Y是兩個有限域，T為X→Y的函數(shù)，如果X與Y滿足：對于任意的Xi∈X有T(Xi)=Yi且Yi∈Y，則稱T為Y上 X標(biāo)記的元組，記作T(X，Y)或T=[X1:Y1,X2:Y2，…，Xi:Yi]，1≤i≤n。

定義5EER模型S為一個九元組MS=(LS，ATT，REL，KEY，CARD，WEAK，ISA，DISJ，COVER)，滿足如下說明：

(3)REL為關(guān)系函數(shù)，REL(R)=[U1:E1,U2:E2，…，Ui:Ei], 對于任意的R∈RS，函數(shù)值為ES上US標(biāo)記的元組。

宴姝的家鄉(xiāng)江蘇省南通市建有中國最早的博物館——南通博物館，幼時那便是宴姝走進(jìn)歷史、看向世界的窗口。后來，每去一處旅游，宴姝的父親都不惜花上半天的時間排隊(duì)，帶她去當(dāng)?shù)氐牟┪镳^看一看。

2.2EER模型的SHOIN(D)描述

定義7給定EER模型MS向SHOIN(D) 知識庫KB轉(zhuǎn)化是通過一個轉(zhuǎn)化函數(shù)φ(MS)來完成。

φ(MS)的概念公理Tbox由以下元素組成：

φ(MS)的概念公理Abox由以下元素組成：

2.3EER模型的描述邏輯推理

EER模型MS向SHOIN(D) 知識庫轉(zhuǎn)化都要考慮知識庫的可滿足性和冗余性，可滿足性要求知識庫邏輯上不能出現(xiàn)空集，否則是無意義的。冗余性則指兩個實(shí)體或關(guān)系之間的邏輯描述不存在蘊(yùn)含或等價關(guān)系。

定義8給定一個SHOIN(D)知識庫K，KF為術(shù)語公理，當(dāng)且僅當(dāng)K的每一個解釋I滿足KF，稱K蘊(yùn)含KF，記作KKF。

定理1可滿足性判定定理

給定一個EER模型MS，φ(MS)是EER模型MS轉(zhuǎn)化得到的SHOIN(D)知識庫，MS是可滿足的，當(dāng)且僅當(dāng)φ(MS)滿足以下條件：φ(MS)φ(A)?；φ(MS)φ(P)?；φ(MS)φ(E)?；φ(MS)φ(R)?。

下面僅對φ(MS)φ(A)?進(jìn)行證明，其他條件證明同理。

再證明?。因?yàn)棣?MS)φ(A)?成立，則有φ(MS)φ(A)?，φ(A)?，由定義8可得φ(MS)φ(A)，由定義7得知φ(A)是由原子概念轉(zhuǎn)化得到的對應(yīng)SHOIN(D)知識庫，所以A?。根據(jù)定義2得知存在一個解釋I=(ΔI，·I)，使得AIΔI成立，所以A是可滿足的， 從而得MS是可滿足的，證畢。

定理2冗余性判定定理

下面進(jìn)行具體證明：先證明?。假設(shè)(1)φ(MS)E1E2和φ(MS)E2E1或(2)φ(MS)R1R2和φ(MS)R2R1成立，由定義8得知存在一個解釋I=(ΔI，·I)，使得E1IE2I和E2IE1I成立，或者R1IR2I和R2IR1I成立，那么就有(E1E2)?和(E2E1)?，或者(R1R2)?和(R2R1)?，所以E1E2和E2E1，或者R1R2和R2R1是可滿足的，顯然MS是存在冗余性的，證畢。

3　EER模型推理實(shí)現(xiàn)

OWL是W3C推薦的Web本體語言標(biāo)準(zhǔn)，英國牛津大學(xué)IHorrocks教授已經(jīng)證明了OWLDL與描述邏輯SHOIN(D)等價。Pellet是美國馬里蘭大學(xué)MindSwap實(shí)驗(yàn)室開發(fā)的開源描述邏輯本體推理機(jī)[7]，支持OWLDL所有構(gòu)造元素，基于Tableau算法實(shí)現(xiàn)了對OWLDL本體進(jìn)行推理機(jī)。文獻(xiàn)[8]研究了描述邏輯對應(yīng)的OWL本體表示形式，從而給EER模型推理提供了技術(shù)支持。本文的EER模型推理實(shí)驗(yàn)硬件采用處理機(jī)Intel(R)core(TM)i5-4210uCPU@2.40GHz，內(nèi)存4.0GB，Widows8.1中文版64位操作系統(tǒng)，軟件使用Pellet2.2.2推理機(jī)，系統(tǒng)架構(gòu)如圖1所示。

圖1　EER模型推理框架

圖2為教學(xué)管理系統(tǒng)的局部EER模型圖，根據(jù)定義7得知該EER模型圖對應(yīng)的SHOIN(D)知識庫是通過一個轉(zhuǎn)換函數(shù)φ轉(zhuǎn)換得到，所以對應(yīng)的SHOIN(D)知識庫不可能為空，由定理1知該EER模型圖及其對應(yīng)的SHOIN(D)知識庫都是可滿足的。但在“教師與學(xué)生之間的授課聯(lián)系”中，由“授課”和“選修”這兩個聯(lián)系可以導(dǎo)出“教師與課程之間的任教聯(lián)系”，出現(xiàn)了冗余性，從而導(dǎo)致模型存在不一致性。下面介紹EER模型可滿足性和冗余性的推理過程，根據(jù)圖1 的EER模型推理框架，首先通過轉(zhuǎn)換函數(shù)把EER模型圖轉(zhuǎn)換為OWL DL本體，然后利用Pellet推理機(jī)進(jìn)行推理[9]，可滿足性推理結(jié)果如圖3所示，冗余性推理結(jié)果如圖4所示。

圖2　教學(xué)管理系統(tǒng)局部EER模型

圖3　EER模型可滿足性推理結(jié)果

圖4　EER模型一致性推理結(jié)果

從圖3、圖4可以看出，Pellet推理機(jī)成功實(shí)現(xiàn)了對EER模型本體知識庫的可滿足性和冗余性進(jìn)行推理，其中可滿足性推理主函數(shù)運(yùn)行用時640 ms，本體裝載用時406 ms，一致性檢測用時16 ms，可滿足性推理用時15 ms，最終沒有發(fā)現(xiàn)不可滿足的概念。冗余性推理主函數(shù)運(yùn)行用時672 ms，本體裝載用時438 ms，一致性檢測用時16 ms，結(jié)果顯示學(xué)生與課程之間產(chǎn)生了冗余，本體知識庫是不一致的。

4　相關(guān)工作

Alex Borgida等人提出了基于描述邏輯DLR的ER模型，研究了ER模型的DLR表示形式，并把ER模型轉(zhuǎn)化為DLR知識庫，借助描述邏輯的推理機(jī)制實(shí)現(xiàn)對知識庫進(jìn)行推理[1]。Diego Calvanese等人提出描述邏輯ALNUI，研究了ALNUI知識庫可滿足性、冗余性自動推理問題[2]。他們主要是從理論層面進(jìn)行了相關(guān)研究，若要推廣到EER模型并進(jìn)行更具體的推理實(shí)現(xiàn)，必須尋找一種具有強(qiáng)大表達(dá)能力，且有成熟軟件支持的描述邏輯。描述邏輯SHOIN(D)作為OWL DL的邏輯基礎(chǔ)，具有更強(qiáng)的語義表達(dá)能力，能夠滿足EER模型形式化的需要。Horrocks I等人也證明了SHOIN(D)和OWL DL是等價的[6]，可知SHOIN(D)與 OWL DL存在邏輯上的對應(yīng)性，為SHOIN(D)知識庫能夠正確向OWL DL本體知識庫轉(zhuǎn)化提供了理論依據(jù)。而成熟的Pellet描述邏輯本體推理機(jī)支持OWL DL的所有元素，為基于描述邏輯的EER模型檢測提供了全面的技術(shù)支持，強(qiáng)有力地支持了本文的研究。

5　結(jié)　語

本文給出了描述邏輯SHOIN(D)語法和語義，研究了基于描述邏輯SHOIN(D)的EER模型及其推理問題，并利用Pellet推理機(jī)對EER模型進(jìn)行了可滿足性、冗余性推理。實(shí)驗(yàn)結(jié)果表明，基于描述邏輯的EER模型檢測方案切實(shí)可行。

[1] Borgida A,Lenzerini M Rosati.Description logics[C]//The Description Logic Handbook,ACM，2003：472-494.

[2] Calvanese D, Giacomo G D, Nardi D, et al. Reasoning in expressive description logics[C]//Handbook of Automated Reasoning.Milan:Elsevier Science Publishers, 2001：1581-1634.

[3] Artale A, Franconi E, Mandreoli F.Description logics for modeling dynamic information[C]//Logics for Emerging Applications of Databases. Berlin:Springer-Verlag, 2003：239-275.

[4] 李鑫，李凡，劉啟和. ER模型的邏輯表示途徑[J].電子科技大學(xué)學(xué)報，2010，39(3):435-439.

[5] 蔣運(yùn)承，湯庸，王駒，等.基于描述邏輯的帶屬性依賴時序 ER模型[J].計算機(jī)研究與發(fā)展，2007，44(10):1765-1773.

[6] Horrocks I, Pate1 Schneider PF, van Harmelen F. From SHIQ and RDF to OWL: The Making of a Web Ontology Language[J].Journal of Web Semantics, 2003,1(1):7-26.

[7] 歐陽柳波，尹勝臺.層疊推理機(jī)的設(shè)計與實(shí)現(xiàn)[J].計算機(jī)應(yīng)用與軟件，2014，31(10):161-166.

[8] 陳振慶，羅蘭花.基于OWL本體的UML類圖推理[J].計算機(jī)應(yīng)用與軟件，2011，28(8):190-192,243.

[9] 柯昌博，黃志球.云計算環(huán)境下隱私需求的描述與檢測方法[J].計算機(jī)研究與發(fā)展，2015，52(4):879-888.

EER MODEL CHECKING BASED ON DESCRIPTION LOGIC

Chen Zhenqing

(DepartmentofMechanicsandElectronicsEngineering,HezhouUniversity,Hezhou542899,Guangxi,China)

We first analysed current status of description logic-based ER model researches, and presented the description logic SHOIN(D)-based EER model, as well as put forward the syntax and semantics of description logic SHOIN(D). Then we studied the describing form of SHOIN(D) in EER model, and the way of how to translate EER model into description logic SHOIN(D) knowledge bases. Finally we gave the judgement theorem of the satisfiability and redundancy of EER model, proved the correctness of these reasoning problems, and employed the pellet’s inference mechanism to achieve the reasoning of satisfiability and redundancy in EER model.

Description logic SHOIN(D)Knowledge basesER modelEER model

2015-04-27。廣西自然科學(xué)基金項(xiàng)目(2014GXNSF BA118278)。陳振慶，副教授，主研領(lǐng)域：語義網(wǎng)，描述邏輯，軟件工程。

TP182

A

10.3969/j.issn.1000-386x.2016.08.009