基于描述逻辑的EER模型检测

陈 振 庆

(贺州学院机械与电子工程学院　广西 贺州 542899)



基于描述逻辑的EER模型检测

陈 振 庆

(贺州学院机械与电子工程学院广西 贺州 542899)

首先分析基于描述逻辑的ER模型的研究现状，提出基于描述逻辑SHOIN(D)的EER模型，给出描述逻辑SHOIN(D)的语法和语义。然后研究EER模型的SHOIN(D)描述形式，以及如何将EER模型向SHOIN(D)知识库转化。最后给出EER模型可满足性、冗余性判定定理，证明了这些推理问题的正确性，并利用pellet推理机实现了EER模型可满足性和冗余性推理。

描述逻辑SHOIN(D)知识库ER模型EER模型

0　引　言

描述逻辑是一种具备很强表达能力和可判定性的知识表示工具，具有高效的判定算法和推理机制支撑，适合于相关推理问题的研究。实体联系ER模型是一种数据库设计工具，是现实世界的抽象描述，在概念模型设计中得到广泛应用。随着应用环境的复杂化，为了准确地模拟客观世界，研究人员又扩展了基本ER模型的概念，提出了增强实体联系模型EER。Alex Borgida和Diego Calvanese等人分别提出了描述逻辑DLR和ALNUI，对ER模型的可满足性、冗余性等相关问题进行自动推理[1,2]。Artale 等人研究了在术语层和断言层上建立了描述逻辑与面向对象数据库描述之间的映射关系[3]。李鑫等人利用Answer set编程表示ER模型，利用ER模型实现异构数据库之间的语义协作[4]，就ER模型与关系数据库的融合进行了理论研究。蒋运承等人针对带属性依赖时序ER模型的需求和特点,提出了时序描述逻辑A LCQI(D)US，并研究了基本时序描述逻辑ALCQI(D)US带属性依赖时序ER模型的自动推理问题[5]。上述研究都没有扩展到EER模型，也没有进行更具体的推理实现。Horrocks I等人研究了具有很强的表达能力的面向本体的描述逻辑语言SHOIN(D)[6]，并指出其是目前应用最广泛的WEB本体表示语言OWL DL的逻辑基础。针对上述研究的不足，本文以描述逻辑SHOIN(D)为基础，研究如何把EER模型正确转化为SHOIN(D)知识库，进而转化为OWL DL本体，再利用pellet推理机对OWL DL本体知识库进行推理，实现对EER模型的可满足性、冗余性等问题进行检测。

1　SHOIN(D)语法和语义

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

(2) 任何个体名O∈NO是SHOIN(D)概念。

定义2令一个解释I=(ΔI，·I)，ΔI为解释域，·I为解释函数，·I函数把概念或个体映射成ΔI的子集，对于给定的解释I，SHOIN(D)概念必须满足以下语义：

定义3令一个解释I=(ΔI，·I)，ΔI为解释域，·I为解释函数，·I函数把角色映射成Δ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的函数，如果X与Y满足：对于任意的Xi∈X有T(Xi)=Yi且Yi∈Y，则称T为Y上 X标记的元组，记作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为关系函数，REL(R)=[U1:E1,U2:E2，…，Ui:Ei], 对于任意的R∈RS，函数值为ES上US标记的元组。

宴姝的家乡江苏省南通市建有中国最早的博物馆——南通博物馆，幼时那便是宴姝走进历史、看向世界的窗口。后来，每去一处旅游，宴姝的父亲都不惜花上半天的时间排队，带她去当地的博物馆看一看。

2.2EER模型的SHOIN(D)描述

定义7给定EER模型MS向SHOIN(D) 知识库KB转化是通过一个转化函数φ(MS)来完成。

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

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

2.3EER模型的描述逻辑推理

EER模型MS向SHOIN(D) 知识库转化都要考虑知识库的可满足性和冗余性，可满足性要求知识库逻辑上不能出现空集，否则是无意义的。冗余性则指两个实体或关系之间的逻辑描述不存在蕴含或等价关系。

定义8给定一个SHOIN(D)知识库K，KF为术语公理，当且仅当K的每一个解释I满足KF，称K蕴含KF，记作KKF。

定理1可满足性判定定理

给定一个EER模型MS，φ(MS)是EER模型MS转化得到的SHOIN(D)知识库，MS是可满足的，当且仅当φ(MS)满足以下条件：φ(MS)φ(A)∅；φ(MS)φ(P)∅；φ(MS)φ(E)∅；φ(MS)φ(R)∅。

下面仅对φ(MS)φ(A)∅进行证明，其他条件证明同理。

再证明⟸。因为φ(MS)φ(A)∅成立，则有φ(MS)φ(A)∅，φ(A)∅，由定义8可得φ(MS)φ(A)，由定义7得知φ(A)是由原子概念转化得到的对应SHOIN(D)知识库，所以A∅。根据定义2得知存在一个解释I=(ΔI，·I)，使得AIΔI成立，所以A是可满足的， 从而得MS是可满足的，证毕。

定理2冗余性判定定理

下面进行具体证明：先证明⟹。假设(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模型推理实现

OWL是W3C推荐的Web本体语言标准，英国牛津大学IHorrocks教授已经证明了OWLDL与描述逻辑SHOIN(D)等价。Pellet是美国马里兰大学MindSwap实验室开发的开源描述逻辑本体推理机[7]，支持OWLDL所有构造元素，基于Tableau算法实现了对OWLDL本体进行推理机。文献[8]研究了描述逻辑对应的OWL本体表示形式，从而给EER模型推理提供了技术支持。本文的EER模型推理实验硬件采用处理机Intel(R)core(TM)i5-4210uCPU@2.40GHz，内存4.0GB，Widows8.1中文版64位操作系统，软件使用Pellet2.2.2推理机，系统架构如图1所示。

图1　EER模型推理框架

图2为教学管理系统的局部EER模型图，根据定义7得知该EER模型图对应的SHOIN(D)知识库是通过一个转换函数φ转换得到，所以对应的SHOIN(D)知识库不可能为空，由定理1知该EER模型图及其对应的SHOIN(D)知识库都是可满足的。但在“教师与学生之间的授课联系”中，由“授课”和“选修”这两个联系可以导出“教师与课程之间的任教联系”，出现了冗余性，从而导致模型存在不一致性。下面介绍EER模型可满足性和冗余性的推理过程，根据图1 的EER模型推理框架，首先通过转换函数把EER模型图转换为OWL DL本体，然后利用Pellet推理机进行推理[9]，可满足性推理结果如图3所示，冗余性推理结果如图4所示。

图2　教学管理系统局部EER模型

图3　EER模型可满足性推理结果

图4　EER模型一致性推理结果

从图3、图4可以看出，Pellet推理机成功实现了对EER模型本体知识库的可满足性和冗余性进行推理，其中可满足性推理主函数运行用时640 ms，本体装载用时406 ms，一致性检测用时16 ms，可满足性推理用时15 ms，最终没有发现不可满足的概念。冗余性推理主函数运行用时672 ms，本体装载用时438 ms，一致性检测用时16 ms，结果显示学生与课程之间产生了冗余，本体知识库是不一致的。

4　相关工作

Alex Borgida等人提出了基于描述逻辑DLR的ER模型，研究了ER模型的DLR表示形式，并把ER模型转化为DLR知识库，借助描述逻辑的推理机制实现对知识库进行推理[1]。Diego Calvanese等人提出描述逻辑ALNUI，研究了ALNUI知识库可满足性、冗余性自动推理问题[2]。他们主要是从理论层面进行了相关研究，若要推广到EER模型并进行更具体的推理实现，必须寻找一种具有强大表达能力，且有成熟软件支持的描述逻辑。描述逻辑SHOIN(D)作为OWL DL的逻辑基础，具有更强的语义表达能力，能够满足EER模型形式化的需要。Horrocks I等人也证明了SHOIN(D)和OWL DL是等价的[6]，可知SHOIN(D)与 OWL DL存在逻辑上的对应性，为SHOIN(D)知识库能够正确向OWL DL本体知识库转化提供了理论依据。而成熟的Pellet描述逻辑本体推理机支持OWL DL的所有元素，为基于描述逻辑的EER模型检测提供了全面的技术支持，强有力地支持了本文的研究。

5　结　语

本文给出了描述逻辑SHOIN(D)语法和语义，研究了基于描述逻辑SHOIN(D)的EER模型及其推理问题，并利用Pellet推理机对EER模型进行了可满足性、冗余性推理。实验结果表明，基于描述逻辑的EER模型检测方案切实可行。

[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].电子科技大学学报，2010，39(3):435-439.

[5] 蒋运承，汤庸，王驹，等.基于描述逻辑的带属性依赖时序 ER模型[J].计算机研究与发展，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].计算机应用与软件，2014，31(10):161-166.

[8] 陈振庆，罗兰花.基于OWL本体的UML类图推理[J].计算机应用与软件，2011，28(8):190-192,243.

[9] 柯昌博，黄志球.云计算环境下隐私需求的描述与检测方法[J].计算机研究与发展，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。广西自然科学基金项目(2014GXNSF BA118278)。陈振庆，副教授，主研领域：语义网，描述逻辑，软件工程。

TP182

A

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