《计算机学报》2009年8期
支持模糊数据类型表示的模糊描述逻辑F-SHOIQ(G)
王海龙1 马宗民1 严丽2 程经纬1
1 (东北大学信息科学与工程学院计算机应用技术研究所 沈阳 110004)
2 (东北大学软件学院软件工程研究所 沈阳 110004)
摘 要 分析了现有描述逻辑在模糊知识和数据类型表示方面存在的问题,提出了一种新的模糊描述逻辑F-SHOIQ(G). F-SHOIQ(G)不仅能够表示模糊知识,而且能够表示含有自定义模糊数据类型及自定义模糊数据类型谓词的模糊数据信息.首先,给出了模糊数据类型域的概念和模糊数据类型表示的一般形式,在此基础上,定义了F-SHOIQ(G)的语法、语义及相应的知识库,进而给出了基于模糊Tableaux的F-SHOIQ(G)概念的可满足性推理算法.其次,将经典描述逻辑中的推理结构(该结构将Tableaux扩展规则推理和数据类型推理相分离)用于F-SHOIQ(G)的推理问题,设计了相应的模糊数据类型推理机.最后,详细证明了F-SHOIQ(G)概念的可满足性推理问题是可判定的.在数据类型表示方面, F-SHOIQ(G)具备比FSHOIQ更强的表达能力和推理能力,为语义Web表示和推理模糊数据信息提供了理论基础.
关键词 模糊描述逻辑; F-SHOIQ(G); 模糊数据类型表示; Tableaux算法; 自定义模糊数据类型谓词
中图法分类号 TP301(
Fuzzy Description Logic F-SHOIQ(G) Supporting Representation of Fuzzy Data Types
WANG Hai-Long1 MA Zong-Min1 YAN Li2 CHENG Jing-Wei1
1 (Institute of Computer Application Technology, College of Information Science and Engineering,
Northeastern University, Shenyang 110004)
2 (Institute of Software Engineering, School of Software, Northeastern University, Shenyang 110004)
Abstract The shortcomings of existing description logics in the representation of fuzzy knowledge and data types are analyzed and a kind of new fuzzy description logic named F-SHOIQ(G) is proposed in the paper. F-SHOIQ(G) can support not only the representation of fuzzy knowledge, but also the representation of fuzzy data information with customized fuzzy data types and customized fuzzy data type predicates. Firstly, the concept of fuzzy data type group and a general formalism of the representation of fuzzy data types are introduced. Then, based on the fuzzy data type group, the syntax, semantics of F-SHOIQ(G) and the components of its corresponding knowledge base are defined. Furthermore, the satisfiability reasoning algorithm of F-SHOIQ(G)-concept based on the fuzzy Tableaux is presented. Secondly, the traditional reasoning architecture in which the reasoning of Tableaux expansion rules and data type can be divided is adopted for the reasoning of F-SHOIQ(G). The corresponding fuzzy data type reasoner is designed. Finally, the decidability of the satisfiability reasoning problem of F-SHOIQ(G)-concept is proved. The representation and reasoning capabilities of F-SHOIQ(G) go beyond the fuzzy description logic FSHOIQ in the representation of data information. F-SHOIQ(G) lays a theoretical foundation for the representation and reasoning of fuzzy data information in the Semantic Web.
Keywords fuzzy description logic; F-SHOIQ(G); representation of fuzzy data types；Tableaux algorithm; customized fuzzy data type predicate
1 引 言
为了让计算机能够理解Web资源信息并做推理,需要建立本体,并利用本体语言来表示语义Web[1]中的知识和语义.描述逻辑[2]作为本体语言的逻辑基础,使语义Web具备了可推理的性质.经典描述逻辑如ALC、ALCQI[2]等只能表示精确知识,不能对现实世界中大量存在的模糊知识进行处理.为了增强语义Web对模糊信息的处理能力,康达周提出了支持模糊隶属度比较的模糊描述逻辑ALCfc[3],Stoilos提出了模糊描述逻辑f-SHIN[4],蒋运承提出了面向语义Web表示的模糊描述逻辑FSHOIQ[5].但是,上述模糊描述逻辑只能处理模糊知识(knowledge),并不能处理现实应用中大量存在的模糊数据(data)信息[6].
在实际应用中,一个本体不仅包含许多重要的知识,而且包括大量的数据信息,因此,语义Web需要能够以一种智能的方式来表示和处理这些信息.实际上,对数据类型表示的支持作为OWL自身设计的一个重要特征,已经引起了SWBPD (W3C Semantic Web Best Practices and Deployment Working Group)的广泛讨论与关注.尽管OWL DL具有很强的表达能力,但最近的研究表明,它仍然缺乏对数据类型信息表示的支持,尤其是不支持自定义数据类型和自定义数据类型谓词,使得OWL DL难以满足用户需求 .为此,Pan引入了数据类型域(data type group,缩写为G),提出了描述逻辑SHOQ(G)和SHIQ(G)来支持精确情形下自定义数据类型和自定义数据类型谓词的表示[6],但SHOQ(G)和SHIQ(G)不能表示和推理模糊知识与模糊数据信息.作为处理模糊数据信息的一个尝试, Straccia提出了模糊描述逻辑fuzzy SHOIQ(D)[7],但没有给出推理算法,也没有给出有数量约束限制的模糊数据类型概念的定义,特别是它不能表示自定义模糊数据类型和自定义模糊数据类型谓词,而后者在实际应用中有时非常重要.例如,在电子商务中,电子商店用商品的长、宽、高之和来表示商品的大小,并据此对商品进行分类.如果应用中已经给定表示“三个整型数之和”的数据类型谓词sum和表示“小”的模糊数据类型谓词small, 那么要定义概念“小商品(small item)”,就必须通过自定义模糊数据类型谓词psmall-item.实际上,很多潜在的用户指出,如果不克服描述逻辑及OWL的上述局限性,他们将不会在应用中采用此语言.SWBPD已经制定了一项课题致力于解决描述逻辑及OWL表达能力中存在的这些问题 .
为此,本文基于模糊描述逻辑FSHOIQ[5],对描述逻辑SHOQ(G)和SHIQ(G)[6]进行模糊扩展,提出了一种新的模糊描述逻辑F-SHOIQ(G),它不仅能够表示模糊知识,而且能够表示含有自定义模糊数据类型及自定义模糊数据类型谓词的模糊数据信息.文中定义了F-SHOIQ(G)的语法、语义及模糊Tableaux的概念,进而基于模糊Tableaux给出了F-SHOIQ(G)的概念可满足性推理算法;然后,将SHOQ(G)中的推理结构[6](该结构将Tableaux扩展规则推理和数据类型推理相分离)用于F-SHOIQ(G)的推理问题,设计了关于F-SHOIQ(G)的模糊数据类型推理机.在模糊扩展后的推理结构中,用户在内部支持的基本数据类型和模糊数据类型谓词的基础上,可以定义适合应用需求的新的模糊数据类型及模糊数据类型谓词,而新的模糊数据类型和模糊数据类型谓词加入后不必更改原有的模糊Tableaux扩展规则推理机.
2 模糊数据类型表示
模糊数据类型域
定义1[6]. 一个数据类型v由词汇空间L(v)、值空间V(v)和词汇空间到值空间的映射函数L2V(v)构成,其中,L(v)是非空的Unicode字符串集合,V(v)是非空的数据类型值的集合.
定义2. 基本数据类型d是XML Schema规范中支持的所有数据类型的最基本构成单元,如xsd:integer、xsd:string等.
所有的基本数据类型含有不同的值空间.例如,对任意两个基本数据类型d1和d2,V(d1)∩V(d2)= (.
定义3[6]. 数据类型谓词p用于约束和限制相应的数据类型.用a(p)表示其元数,如果p是变元的,则用amin(p)表示其最小元数.
定义4. 根据Zadeh对模糊集的语义解释方法[8],一个模糊数据类型谓词p的语义由((D, (D)给出,其中(D是模糊数据类型域,(D是模糊数据类型解释函数.(D将每个n元模糊数据类型谓词p映射为(D上的n元关系pD:(Dn→(((([0,1]),即((Dn,(((pD,这表明: (D上的数据类型变量v1,…,vn之间的关系在(程度上满足谓词p.
例如,用于表示“年轻”的young:N→[0,1]是一个模糊数据类型谓词,可以根据经验定义如下:
youngD(v) = max(0, 1 – ) (1)
并且a(young) = 1.根据(1)式,整型值18属于谓词“young”的隶属度为(1 – *182) = .
根据上述定义,一个模糊数据类型实际上是一个特殊的一元模糊数据类型谓词;并且,数据类型可以看作是模糊数据类型的特例,数据类型谓词可以看作是模糊数据类型谓词的特例.
例如,sum是一个变元的数据类型谓词,并且amin(sum)=3,sum(i0, i1, i2, …, in)表示i0 = i1+ i2 + … + in,并限定i0, i1, i2,…,in为整数.实际上,sum也可以看做是变元的模糊数据类型谓词,并有如下解释:
sumD(i0, i1, i2,…, in) = (2)
模糊数据类型域是对经典数据类型域[6]的模糊扩展.它提供了一个表示模糊数据类型和模糊数据类型谓词的统一机制.
定义5. 一个模糊数据类型域G是一个三元组((G, DG, dom),其中,(G是通过谓词统一资源定位符(predicate URI references)定义的模糊数据类型谓词的集合,它包含了当前模糊数据类型域中所支持的谓词;DG是G中的基本数据类型的集合;dom是模糊数据类型谓词p的域函数,并且dom(p)=
因为基本数据类型是一类特殊的模糊数据类型谓词,所以DG ( (G.由dom域函数可见,模糊数据类型域G中的每一个模糊数据类型谓词p都定义在一系列基本数据类型的基础上.也就是说,对G中的每一个模糊谓词p,总存在一系列基本数据类型d1,…dn ( DG, 满足dom(p) ( V(d1) (…(V(dn).
下面给出一个模糊数据类型域的实例G1.首先给定一系列模糊数据类型谓词如下:表示两个字符串相似匹配程度的模糊数据类型谓词strmatch(str1, str2);表示“小”的模糊数据类型谓词small(v);以及前面介绍的模糊数据类型谓词young,sum.则G1 = ((G1, DG1, dom1)定义如下:
(G1 = {xsd: string, xsd: integer, strmatch, small, young, sum},
DG1 = {xsd: string, xsd: integer},
dom1 = {(xsd: string, xsd: string(, (xsd: integer, xsd: integer(, (strmatch, (xsd: string, xsd: string)(, (small, xsd:integer(, (young, xsd:integer(, (sum, (xsd: integer, xsd: integer,…, xsd: integer)(}.
定义6. 给定一个模糊数据类型域G = ((G, DG, dom)和一个基本数据类型d(DG,一个关于d的模糊数据类型子域sub-group(d, G)定义如下:
sub-group(d,G)={p((G|dom(p)={d,…,d}(a(p)个)}.
上面给出的模糊数据类型域G1可被完全划分成两个模糊数据类型子域,其中:
sub-group(xsd: string, G1) = {xsd: string, strmatch},
sub-group(xsd: integer, G1) = {xsd: integer, small, young, sum}.
在一个模糊数据类型域G中,(G已经定义了其支持的模糊数据类型及谓词,未定义的模糊数据类型及谓词则可以由用户在此基础上通过模糊数据类型表达式自行定义.
定义7. 给定一个模糊数据类型域G,关于G的模糊数据类型表达式集合记为Dexp(G),其中模糊数据类型表达式E(Dexp(G)定义如下:
E := ⊺D | (D | p | p(| {l1 , ... , ls} | (E1 ( … ( Es ) | (E1 ( …( Es ) | [u1, …,us]
其中, ⊺D、(D分别表示模糊全局数据类型表达式和模糊空数据类型表达式; p是模糊数据类型谓词; p(是关于p的逆谓词; l1,…,ls是有型文字(typed literals[6]); ui是形如d, pu或pu(的一元谓词, 这里d(DG, pu是一元模糊数据类型谓词, 1( i ( s.
由((D, (D)给出对上述模糊数据类型表达式的语义解释如下:
⊺DD(v1 , …, vn) = 1
(DD(v1 , …, vn) = 0
pD(v1 , …, vn) → [0,1]
{l1 , ... , ls}D(v) = ∨si=1(liD = v)
(E1 ( … ( Es )D (v1 , …, vn) = (E1)D (v1 , …, vn) ( … ( (Es )D (v1 , …, vn)
(E1 ( …( Es )D (v1 , …, vn) = (E1)D (v1 , …, vn) (…( (Es )D (v1 , …, vn)
([u1, …,us])D(v1,…,v s) = u1D(v1)(…(usD(vs)
特别地,对模糊数据类型域中模糊逆表达式的语义解释作如下定义:
D =
在模糊数据类型域G1中,如果要表示语义“v年轻并且不小”,则可以利用定义7中的模糊合取表达式及逆表达式表示为: (young(small)(v).
此外,为了保证模糊数据类型域的可判定性,对其做如下限定:
定义8[6]. 一个模糊数据类型域G是一致的,当且仅当G满足:
对任意p((G\DG, a(p)= n (n ( 2),满足dom(p) =(d,…,d) (n次),其中d(DG,并且
对任意p((G\DG,总存在p’((G\DG 使得p’D = D,并且
关于G的每个sub-group上的有限个模糊数据类型谓词联合的可满足性问题是可判定的.
在该定义中,条件1保证了(G可以被完全划分成若干个sub-groups,即对于G中的每一个模糊谓词p,总存在唯一的基本数据类型d( DG,满足dom(p) ( V(d)a(p).条件2保证了可以等价替换掉逆谓词.条件3保证了每一个sub-group是可判定的.
模糊数据类型概念的表示
模糊数据类型概念是对描述逻辑的一个模糊扩展,它通过模糊数据类型角色将抽象个体映射为模糊数据类型域(D上的值,如integer、string等,这些具体数值再被模糊数据类型谓词约束.
定义9. 最一般的模糊数据类型概念表达形式包括数量限制、模糊数据类型角色和模糊数据类型谓词,形如格式:
mT1,…,Tn. E
其中,m是正整数,表示数量限制;Ti是复杂或简单模糊数据类型角色;E是模糊数据类型表达式,并且E (Dexp(G).
所谓的简单模糊数据类型角色,就是直接将抽象个体x映射为模糊数据类型域上的数据类型值v,即(x, v((Ti.复杂模糊数据类型角色由简单模糊数据类型角色合成,如复杂模糊数据类型角色T = f1 ° …° fn,其中fi是简单模糊数据类型角色.在以下讨论中,出于可判定性考虑[9],Ti为简单模糊数据类型角色.
看一个例子,根据(1)式中对谓词“young”的定义,模糊数据类型概念“youngperson”可以定义为:
youngperson = person⊓(age. young (3)
根据公式(1)和(3),一个18岁的少年将会以的隶属度属于一个“youngperson”.在(3)式中, (age. young是一个模糊数据类型概念,“age”是简单模糊数据类型角色.
3 F-SHOIQ(G)的语法语义及知识库表示
将一致性模糊数据类型域G引入到模糊描述逻辑FSHOIQ[5]中,得到模糊描述逻辑F-SHOIQ(G). F-SHOIQ(G)不仅包含原有描述逻辑FSHOIQ中的概念构子,而且还增加了与模糊数据类型表达式相关的概念构子,从而能够表示模糊数据信息.
定义10. 对于角色R,定义其逆角色为R(.其中,对于个体x, y, (x, y(( R, 当且仅当(y, x(( R(; 并且逆关系是对称的,为了避免出现R( (,定义取逆函数Inv,满足: Inv(RN) := R(,如果RN= R; Inv(RN) := R,如果RN = R(.
定义11. 假设C, RA, RD, I分别是F-SHOIQ(G)的不相交的概念名、抽象角色名、数据类型角色名以及个体名的集合, R = RA∪RD.抽象角色R := RN | R(, 其中RN( RA; T( RD叫做数据类型角色.假设A是C中的原子概念, T1 ,…, Tn ( RD, o(I, G是一致性模糊数据类型域, E(Dexp(G). F-SHOIQ(G)概念遵循以下抽象语法:
C := ⊺|(| A | ¬C | C ⊓ D | C ⊔ D |( |( |{o1,…, on}| ( n | ( n |(T1,…,Tn. E |(T1,…,Tn. E | ( mT1,…,Tn. E |( mT1,…,Tn. E
在上述语法表示中,含有模糊数据类型表达式E的F-SHOIQ(G)概念,如(T1,…,Tn. E、(T1,…,Tn. E、( mT1,…,Tn. E、( mT1,…,Tn. E,称之为模糊数据类型概念,其余的称之为模糊抽象概念.
描述逻辑F-SHOIQ(G)的语义由解释I = ((I, (I)给出.I包括非空域(I和解释函数(I,并且(I与(D互不相交.(I将每个抽象个体a(I映射为一个元素aI((I,将任意概念A(C映射为一个函数AI: (I →[0, 1],将抽象角色R ( RA映射为一个函数RI: (I × (I →[0, 1],将数据类型角色T ( RD映射为函数TI : (I ×(D →[0, 1].进而,对模糊抽象概念的语义解释类似于文献[5],对模糊数据类型概念的语义解释如下所示,其中x( (I ,v是数据类型变量.
((T1,…,Tn. E)I(x) =
((T1,…,Tn. E)I(x) =
(( mT1,…,)I(x) =
(( mT1,…,)I(x) = 1 - (((m+1)T1,…,)I(x)
在上述语义解释中,模糊补操作采用Lukasie- wicz算子,即¬a = 1-a;模糊交和并操作采用Gödel算子,即a(b = min(a, b), a(b = max(a, b);模糊蕴含操作采用Kleene-Dienes算子,即a→b = max(¬a, b),其中a,b([0, 1].
一个F-SHOIQ(G)知识库K由模糊TBox T,模糊RBox R和模糊ABox A组成,即K = (T, R, A(,其中:
模糊TBox是有限个形如C ⊑ D的术语包含公理的集合,其中C和D是F-SHOIQ(G)概念.形如C ( D的模糊概念公理可以拆分为C ⊑ D且D ⊑ C.
模糊RBox 是有限个模糊角色公理的集合.对于角色R,形如Trans(R)的模糊角色公理,叫做模糊传递公理;形如R ⊑ S,或T ⊑ U的模糊角色公理,叫做模糊包含公理,其中R, S是抽象角色,T, U是数据类型角色.支持F-SHOIQ(G)角色层次表示的RBox R定义为:
R = (R∪{Inv(R) ⊑ Inv(S) | R ⊑ S ( R}, ⊑*),
其中⊑*是R∪{Inv(R) ⊑ Inv(S) | R ⊑ S ( R}上关于⊑的自反传递闭包.
模糊 ABox是有限个形如((, ⋈, k(的模糊断言的集合,其中,k ( [0, 1],并且模糊断言(或者形如x: C,或者形如(x, y): R,或者形如(x, v): T (x, y ( (I,v是数据类型变量).
一个F-SHOIQ(G)概念C是可满足的当且仅当存在一个解释I对某个x( (I,满足CI(x) = k, k((0,1].此时,解释I叫做概念C的一个模型.一个解释I满足模糊TBox T中的一条公理C ⊑ D,当且仅当(x((I, CI(x) ≤DI(x). I是TBox T的一个模型当且仅当I满足T中的所有公理.一个解释I满足模糊RBox R 当且仅当对R中的每条角色传递公理Trans(R),满足(x, y, z( (I, RI(x, z) ≥ sup y∈(I (RI(x,y) ( RI(y, z));对R中的每条角色包含公理R ⊑ S, 满足((x, y(( (I((I, RI(x, y) ≤SI(x, y). 一个解释I满足(x: C, ⋈, k(当且仅当CI (x) ⋈k, 满足((x,y):R, ⋈, k(当且仅当 RI (x, y) ⋈k, 满足((x, v): T, ⋈, k(当且仅当TI (x, v) ⋈k. I 叫做ABox A 的一个模型当且仅当I 满足A中的所有断言.一个知识库K是可满足的当且仅当存在一个解释I同时满足TBox T, RBox R和ABox A.
F-SHOIQ(G)能够支持自定义模糊数据类型和自定义模糊数据类型谓词,具备更强的表达能力.例如,在电子商务中,电子商店根据商品的大小来对其进行分类,并且对其中的“小商品(small item)”有相应的优惠政策,比如,对“小商品”可以免收邮寄费用,那么支付系统就可以根据这项政策免收所有“小商品”实例的邮寄费用.现已给定模糊数据类型域G2 = ((G2, DG2, dom2),其中sum, small((G2, psmall-item ( (G2, xsd: integer(DG2.在(G2中,根据商店的统计,表示商品“小”的一元模糊数据类型谓词small定义为:
small(v) = max(0, 1 – ). (4)
数据类型谓词sum的定义如前所述.假定用商品的长、宽、高之和来表示商品的大小,那么要定义概念“small item”,就必须通过自定义模糊数据类型谓词psmall-item.这时,可以利用定义7中的模糊合取表达式自定义模糊数据类型谓词psmall-item如下:
psmall-item(i0, i1, i2, i3)=sum(i0, i1, i2, i3 )( small(i0)
并且a(psmall-item) = 4;则模糊数据类型概念“small item”可以定义如下:
small-item = item⊓(sumInCM, heightInCM, widthInCM, lengthInCM. psmall-item (5)
其中sumInCM,heightInCM,widthInCM, lengthInCM是模糊数据类型角色.假定一个商品长8cm,宽6cm,高7cm,那么根据公式(4)和(5),它隶属于“small item”的概率是,进而相应的价格优惠规则可以在此基础上进行推理和运用.
4 F-SHOIQ(G)的推理
F-SHOIQ(G)的推理算法可以在FSHOIQ[5]推理算法的基础上通过扩展对一致性模糊数据类型域G的推理而得到,所以在以下讨论中只关注对一致性模糊数据类型域G的推理.
F-SHOIQ(G)概念的可满足性推理算法
为了讨论问题的方便,假定所有的F-SHOIQ(G)概念都是NNF范式的形式,即取反构子只出现在原子概念、个体名或者模糊数据类型表达式前.每一个非NNF范式形式表示的F-SHOIQ(G)概念可以等价地转化为NNF范式[6].
此外,在下面的叙述中,用符号▷表示>和≥,用符号◁表示<和≤,用符号⋈(()表示>, ≥, <和≤,用⋈-1, ▷-1,◁-1分别表示⋈, ▷,◁的反射,其中≥和≤相互反射, >和<相互反射.如果ψ是F-SHOIQ(G)中的断言公理,则记ψiC为ψ的共轭公式.在F-SHOIQ(G)中,互为共轭的元组有以下四种形式:
{(ψ≥n(,(ψ<m(,n≥m}, {(ψ>n(,(ψ<m(,n≥m}, {(ψ≥n(,(ψ≤m(,n>m}, {(ψ>n(,(ψ≤m(,n≥m}.
F-SHOIQ(G)概念D的模糊Tableaux
概念可满足性问题是描述逻辑中最基本的推理问题,其它推理问题都可以转化为此问题.对F-SHOIQ(G)概念D的可满足性检查就是看能否构造一个关于概念D的模糊Tableaux,这个Tableaux实际上是关于概念D的一个模型.在对模糊Tableaux的定义中,用到了形如(C/R/T, ⋈, k(的成员函数三元组,元组内的元素C/R/T分别表示概念、抽象角色或数据类型角色,k表示相应的隶属度.出现在三元组中的概念C的集合是cl(D)的子集,其中cl(D)表示概念D中出现的所有子概念[5]的幂集.同时,用clG(D)表示概念D中出现的所有模糊数据类型表达式及其子表达式.
定义12. 给定一个用NNF形式表示的F-SHOIQ(G)概念D,R是关于F-SHOIQ(G)的RBox, RAD是关于D和R中出现的所有抽象角色及其逆角色的集合,RDD是所有数据类型角色的集合,G是一致性模糊数据类型域,并且E(clG(D)是模糊数据类型表达式,X = {(, (, (, (}.相对于R,的F-SHOIQ(G)概念D的一个模糊Tableaux
T = (SA, SD, L, DC, εA, εD)
定义如下:
SA是抽象个体的非空集合;
SD是数据类型变量的非空集合;
L: SA ( 2cl(D) ( X ( [0,1]将SA中的个体映射为2cl(D) ( X ( [0,1] 中的成员函数三元组;
DC: 是形如(E(v1,…,vn), ⋈, k(的模糊数据类型约束和形如((vs1,…,vsn(,(vt1,…,vtn(, ()的不等式的集合,其中E(clG(D),v1,…,vn, vs1,…,vsn, vt1,…,vtn(SD, s, t为整数, k([0, 1];
εA: RAD(( X ( [0,1]将RAD 中的抽象角色映射为( X ( [0,1]中的成员函数三元组;
εD: RDD(( X ( [0,1]将RDD 中的数据类型角色映射为( X ( [0,1]中的成员函数三元组;
存在一个x0(SA,使得(D, ⋈, k((L(x0).对所有的x(SA, v(SD, C,C1,C2( cl(D), R, S(RAD, T, T’( RDD,模糊Tableaux T满足:
(P0)存在一个数据类型解释((D, (D)和一个从SD到(D的映射(, 使得对于每一个(E(v1,…,vn), ⋈, k(( DC(x), 有ti = ((vi)(1( i ( n), 并且满足(ED(t1,…,tn(, ⋈, k(,
(P1)如果((T1,…,Tn. E, ▷, k( ( L(x), 则存在v1,…,vn ( SD, 使得: ((x, vi(, ▷, k( ( εD(Ti) (1( i ( n), 并且(E(v1,…,vn), ▷, k( ( DC(x),
(P2)如果((T1,…,Tn. E, ◁, k( ( L(x), 则存在v1,…,vn ( SD, 使得: ((x, vi(, ◁-1, 1-k( ( εD(Ti) (1( i ( n), 并且(E(v1,…,vn), ◁, k( ( DC(x),
(P3)令ψi = ((x, vi(, ▷-1,1-k( (1( i ( n), 如果((T1,…,Tn. E, ▷, k( ( L(x), 并且存在v1,…,vn ( SD, 使得: ψiC( εD(Ti) (1( i ( n),则(E(v1,…,vn), ▷, k( ( DC(x),
(P4)令ψi = ((x, vi(, ◁, k( (1( i ( n),如果((T1,…,Tn. E, ◁, k((L(x),并且存在v1,…,vn(SD,使得:ψiC( εD(Ti) (1( i ( n),则(E(v1,…,vn), ◁, k( ( DC(x),
(P5)如果(( mT1,…,Tn .E, ▷, k( ( L(x), 则存在(vi1,…,vin( ( SD (1( i ( m), 使得: ((x, vij(, ▷, k( ( εD(Tj) (1( i ( m, 1( j ( n), 并且(E(vi1,…,vin), ▷, k( ( DC(x) (1( i ( m),
(P6)如果(( mT1,…,Tn .E, ◁, k( ( L(x), 则(( (m+1)T1,…,Tn .E, ◁-1, 1-k( ( L(x),
(P7)令ψij = ((x, vij(, ▷-1,1-k( (1( j ( n), 如果(( mT1,…,Tn .E, ▷, k( ( L(x), 则至多不会存在m+1组不同的(vi1,…,vin( ( SD, 使得: ψijC( εD(Tj) (1( j ( n), 并且(E(vi1,…,vin), ▷, k( ( DC(x) ( i 为整数),
(P8)如果(( m T1,…,Tn .E, ◁, k(( L(x), 则 (((m-1) T1,…,Tn .E, ◁-1, 1-k( ( L(x).
定理1. 一个用NNF形式表示的F-SHOIQ(G)概念D关于RBox R是可满足的,当且仅当概念D存在一个关于R的模糊Tableaux.
证明. 首先证明(.假设F-SHOIQ(G)概念D存在一个相对于R的模糊Tableaux T=(SA, SD, L, DC, εA, εD),则F-SHOIQ(G)概念D的一个模型可以定义为I = ((I, (I):
(I = SA;
AI = {(x, k)|(A, ⋈, k( ( L(x)},对任意的原子概念A;
RI =
TI = {((x, ((v)(, k)| ((x, v(,⋈, k)(εD(T)};
其中,εA(R+)是εA(R)的传递闭包.
根据(P0),存在一个关于模糊数据类型域G的解释((D, (D).要证明概念D是可满足的,只需证明对任意C ( cl(D),如果(C, ⋈, k(( L(x),则(x, k) ( C I.通过对概念D的结构进行归纳,可以证明其成立.
其次证明(.假定概念D存在一个相对于R的模型I = ((I, (I),则相对于R的概念D的一个模糊Tableaux T=(SA, SD, L, DC, εA, εD)可以定义如下:
SA = (I;
L(x) = {(C, ⋈, k(| C ( cl(D), (x, k) ( CI};
εA(R) = {((x, y(, ⋈, k(| ((x, y(, k) ( RI};
将SD, DC初始化为空集,(和εD(T)初始化为空关系.对T中的每一个模糊数据类型角色(x, t(,创建一个新的变量v,然后,按如下方式构造SD, (, εD(T)和DC:
SD := SD∪{v};
( := (∪{(v, t(};
εD(T) := εD(T) ∪{(x, v(, ⋈, k };
DC := {(E(v1,…,vn), ⋈, k(|(v1,…,vn ( SD, E(clG(D), ti = ((vi)(1( i ( n),并且满足(ED(t1,…,tn (, ⋈, k(}.
可以证明,T = (SA, SD, L, DC, εA, εD)是相对于R 的F-SHOIQ(G)概念D的一个模糊Tableaux.由模糊Tableaux的定义可知,SA是抽象个体的非空集合, L是SA ( 2cl(D) ( X ( [0,1]的映射,εA是RAD(( X ( [0,1] 的映射,εD是RDD(( X ( [0,1]的映射,并且满足定义12的规则要求. (
构建F-SHOIQ(G)模糊Tableaux的算法
定理1说明了可以利用定义12设计一个基于模糊Tableaux T的推理算法,用于检查F-SHOIQ(G)概念D的可满足性.该推理算法生成的一个关于D的模糊Tableaux可以用森林F表示.F的节点分为抽象节点和数据类型节点两种.每一个抽象节点x用L(x)进行标记,L(x)是形如(C, ⋈, k(的集合;每一个数据类型节点在F中只能作为叶节点出现,并且没有任何标记.F中的抽象边(x, y(用L((x, y()进行标记,L((x, y()是形如(R, ⋈, k(的集合,其中R(RAD;同样,数据类型边(x, v(用L((x, v()进行标记,L((x, v()是形如(T, ⋈, k(的集合,其中T(RDD.
定义13. 在森林F中,如果节点x和节点v之间通过边(x, v(进行连接,则v称作x的T-后继.数据类型变量v1,…,vn叫做x的(T1,…,Tn(-后继,其中vｊ是x的Tj-后继(1(j( n).
定义14[5]. 在森林F中,一个节点x被阻塞,当且仅当x不是根节点,并且x被直接阻塞或间接阻塞.节点x被直接阻塞,当且仅当x的任何祖先没有被阻塞,并且x存在祖先x’, y, y’,满足:
y不是根节点;
x是x’的后继, y是y’的后继;
L(x) = L(y), L(x’) = L(y’);
L((x’, x() = L((y’, y();
这时也称节点y阻塞了节点x.节点x被间接阻塞,当且仅当x的祖先被阻塞,或者x是节点y的后继,并满足L((y, x() = (.
定义15[10]. 一个森林F被称为完全森林,当且仅当任何Tableaux扩展规则都对其不起作用.
在推理算法中,用DC(x)存储节点x的数据类型后继所应满足的模糊数据类型表达式,它是形如(E(v1,…,vn), ⋈, k(的模糊数据类型约束和形如((vs1,…,vsn(,(vt1,…,vtn(, ()的不等式的集合,其中E( clG(D),v1,…,vn,vs1,…,vsn,vt1,…,vtn(SD, s,t为整数.算法通过调用模糊数据类型推理机检查DC(x)的可满足性.DC(x)是可满足的当且仅当数据类型查询
(
(6)
是可满足的.可见,DC(x)是F-SHOIQ(G) Tableaux扩展规则推理与模糊数据类型推理的接口.
定义16. 给定节点x, x包含冲突,即L(x)包含FSHOIQ冲突[5],或者包含G-冲突.一个完全森林F的节点x,如果满足下列条件之一:
如果存在数据类型角色T1,…,Tn,有((mT1,…,, ▷, k( ( L(x),并且x存在m+1个(T1,…,Tn(-后继(vi1,…,vin( (1( i ( m+1), 满足: (E(vi1,…,vin(,▷, k(( DC(x) (1( i ( m+1),并且((vi1,…,vin(, (vj1,…,vjn(,()(DC(x), (1(i<j(m+1);
对于节点x, DC(x)是不可满足的.
则称节点x包含一个G-冲突.
算法1. F-SHOIQ(G)概念的可满足性推理算法.
输入：F-SHOIQ(G)概念D;
输出：布尔值;
步骤：
1. 对森林F进行初始化,其中：F包含节点x0, 并且L(x0) ＝ {(D, >, 0(}. 对应于节点x0的数据结构DC(x0)被初始化为空集,里面也不包含任何不等关系.
2. 森林F通过Tableaux扩展规则(包括FSHOIQ-规则[5]和下面的G-规则)进行扩展,直到无规则可用为止.
1) ∃p▷-规则: 如果(∃T1,…,Tn. E, ▷, k( ( L(x), x没有被阻塞, 并且x不存在一个(T1,…,Tn(-后继(v1,…,vn(, 满足:L((x, vi() = {(Ti, ▷, k(} (1( i ( n), 以及(E(v1,…,vn), ▷, k( ( DC(x),
则创建一个关于x的(T1,…,Tn(-后继(v1,…,vn(,使得:L((x, vi()={(Ti, ▷, k(}(1( i ( n),并且DC(x)=DC(x)∪{(E(v1,…,vn),▷, k(}.
2) ∀p◁-规则: 如果(∀T1,…,Tn. E, ◁, k( ( L(x), x没有被阻塞, 并且x不存在一个(T1,…,Tn(-后继(v1,…,vn(, 满足:L((x, vi() = {(Ti, ◁-1, 1-k(} (1( i ( n), 以及(E(v1,…,vn), ◁, k( ( DC(x),
则创建一个关于x的(T1,…,Tn(-后继(v1,…,vn(,使得:L((x, vi()={(Ti,◁-1,1-k(}(1(i(n),并且DC(x)=DC(x)∪{(E(v1,…,vn),◁,k(}.
3) ∀p▷-规则: 如果(∀T1,…,Tn. E, ▷, k( ( L(x), x没有被阻塞, 并且x存在一个(T1,…,Tn(-后继(v1,…,vn(, 满足: L((x, vi() = {(*, ▷, r(}(1( i ( n), 其中(*, ▷, r(与(*, ▷-1, 1-k(互为共轭, *表示形如(x, vi(的任意二元关系, 以及(E(v1,…,vn), ▷, k( ( DC(x),
则DC(x) = DC(x)∪{(E(v1,…,vn), ▷, k(}.
4) ∃p◁-规则: 如果(∃T1,…,Tn. E, ◁, k( ( L(x), x没有被阻塞, 并且x存在一个(T1,…,Tn(-后继(v1,…,vn(, 满足: L((x, vi() = {(*, ▷, r(}(1( i ( n), 其中(*, ▷, r(与(*, ◁, k(互为共轭, *表示形如(x, vi(的任意二元关系, 以及(E(v1,…,vn), ◁, k( ( DC(x),
则DC(x) = DC(x)∪{(E(v1,…,vn), ◁, k(}.
5) (p▷-规则: 如果(( mT1,…,Tn .E, ▷, k( ( L(x), x没有被阻塞, 并且x不存在m个(T1,…,Tn(-后继(vi1,…,vin( (1( i ( m), 满足: L((x, vij() = {(Tj, ▷, k(} (1( i ( m, 1( j ( n), 以及(E(vi1,…,vin), ▷, k( ( DC(x) (1( i ( m)和((vi1,…,vin(, (vj1,…,vjn(,()( DC(x) (1( i<j( m),
则创建m个关于x的(T1,…,Tn(-后继(vi1,…,vin( (1( i ( m), 使得: L((x, vij() = {(Tj, ▷, k(} (1( i ( m, 1( j ( n), 并且DC(x) = DC(x)∪(E(vi1,…,vin), ▷, k( (1( i ( m), DC(x) = DC(x)∪{((vi1,…,vin(, (vj1,…,vjn(, ()}(1( i<j( m).
6) (p◁-规则: 如果(( mT1,…,Tn .E, ◁, k( ( L(x), x没有被阻塞,
则将(p▷规则应用于(( (m+1)T1,…,Tn .E, ◁-1, 1-k(上.
7) (p▷-规则: 如果(( mT1,…,Tn .E, ▷, k( ( L(x), x没有被阻塞, 并且x存在m+1个(T1,…,Tn(-后继(vi1,…,vin( (1( i ( m+1), 满足: 1) L((x, vij() = {(*, ▷, r(}(1( i ( m+1, 1( j ( n), 其中(*, ▷, r(与(*, ▷-1, 1-k(互为共轭, *表示形如(x, vij(的任意二元关系, 2) (E(vi1,…,vin), ▷, k( ( DC(x) (1( i ( m+1), 3)在上述m+1个(T1,…,Tn(-后继中存在两个不同的(T1,…,Tn(-后继(vs1,…,vsn( 和(vt1,…,vtn( (s(t)使得{((vs1,…,vsn(, (vt1,…,vtn(,()}( DC(x),
则对x的每一对不同数据类型的Tj-后继vsj和vtj, 做: 1) L((x, vsj() = L((x, vsj()∪L((x, vtj(),并且2) 在DC(x)中,所有的vtj用vsj代替,并且删除vtj,并且3) L((x, vtj(= (.
8) (p◁-规则: 如果(( mT1,…,Tn .E, ◁, k( ( L(x), x没有被阻塞,
则将(p▷规则应用于(( (m-1)T1,…,Tn .E, ◁-1, 1-k(上.
3. 如果完全森林F的每个节点都不包含冲突,那么关于RBox R的F-SHOIQ(G)概念D是可满足的,返回结果为真;否则,D是不可满足的,返回结果为假.
4. 算法结束.
F-SHOIQ(G)的推理结构及推理机的设计
算法1讨论了如何通过Tableaux扩展规则构造一个完全森林,其中,将对模糊数据类型表达式的约束当成一个整体,并存储于数据结构DC中.根据经典描述逻辑SHOQ(G)的推理问题中将规则推理和数据类型推理相分离的思想[6],由算法1的实现过程可以归纳出模糊描述逻辑F-SHOIQ(G)推理问题的一个重要特征:关于F-SHOIQ(G)的Tableaux扩展规则推理和关于一致性模糊数据类型域G的模糊数据类型推理可以分离开进行.根据此特征,F-SHOIQ(G)推理问题的推理结构设计如下(如图1所示).
图1 F-SHOIQ(G)的推理结构
在图1所示的推理结构中,关于F-SHOIQ(G)的Tableaux扩展规则推理通过F-SHOIQ(G)推理机来完成,而模糊数据类型的推理则通过模糊数据类型推理机来完成.基于这样的推理结构,当有新的模糊数据类型或模糊数据类型谓词需要加入时,仅需要更改模糊数据类型推理机即可,而不必更改F-SHOIQ(G)推理机.此外,在此推理结构中,模糊数据类型谓词的表达能力仅受到模糊数据类型域的一致性条件的约束.
从图1可以看出,有两种不同的模糊数据类型推理机:一种是模糊数据类型管理器,用于将形如(6)式的模糊数据类型表达式的可满足性判定问题转化为基于不同基本数据类型的各种模糊数据类型谓词联合的可满足性判定问题;另一种是模糊数据类型检查器,用于判定基于一个基本数据类型的模糊数据类型谓词联合的可满足性问题.根据相应的经典数据类型推理机[6],模糊数据类型推理机具体设计如下.
模糊数据类型检查器
定义17. 给定一致性模糊数据类型域G和G中的一个基本数据类型d,关于d的一个模糊数据类型检查器记为DCd.它把一个模糊数据类型谓词联合(作为输入,并且
( = , ⋈, k (7)
其中vi(j)是数据类型变量,pj是基于基本数据类型d 的模糊数据类型谓词,并且a(pj) = nj.当(可满足时,模糊数据类型检查器返回的查询结果为真,否则返回的查询结果为假.(是不可满足的当且仅当(中包含以下情形之一:
存在互为共轭的两个谓词(p(v1,…,vn), ▷, r(和(p(v1,…,vn), ▷-, r’((r ( r’);
存在谓词(p(v1,…,vn), (, 1(;
存在谓词(p(v1,…,vn),(, 0(.
模糊数据类型管理器
模糊数据类型管理器工作在F-SHOIQ(G)推理机和若干模糊数据类型检查器之间.模糊数据类型管理器的设计支持上述定义7中提到的所有模糊数据类型表达式的形式.
直观上讲,一个模糊数据类型管理器把一个形如(6)式的模糊数据类型表达式ψ转化成一系列模糊谓词联合的并,并且把每一个模糊谓词联合转化成几个形如(7)式的子联合,其中每一个子联合是关于模糊数据类型域G中某个基本数据类型上的模糊谓词查询.如果不同的子联合之间有共同的数据类型变量,则返回“不满足”,因为不同的基本数据类型的值空间是不相交的;否则,模糊数据类型管理器把每一个子联合发送到适当的模糊数据类型检查器上,以判定它的可满足性.如果一个模糊谓词联合的所有子联合是可满足的,则它是可满足的;如果有一个模糊谓词联合是可满足的,则输入的模糊数据类型表达式ψ是可满足的.
定义18. 给定一个一致性模糊数据类型域G,关于G的模糊数据类型管理器记做的设计如算法2所示,它将形如(6)式的模糊数据类型表达式ψ作为输入,根据ψ的可满足性返回相应的结果.当ψ可满足时,DMg返回的查询结果为真,否则,返回的查询结果为假.
假设p((G, q((G, d(DG, d1,…,dn ( sub-group (d, G), a(di)=1 (1( i ( n), 并且P,Q是具有相同元数的模糊数据类型表达式.
算法2. 模糊数据类型管理器的实现算法.
输入：形如(6)式的模糊数据类型表达式ψ;
输出：布尔值;
步骤：
1. DMg通过以下公式消除ψ中的的取反构子,将ψ变为ψ1：
¬p ( ⊔ (d,…,d) ( n个d)；¬( p ⊔ (d,…,d) ( n个d)；
¬q ( ；¬ ( q；
¬(d1,…,dn) ( (d1,…,dn)；¬ (d1,…,dn) ( (d1,…,dn)；
¬(P ⊓ Q) ( ¬P ⊔ ¬Q；¬(P ⊔ Q) ( ¬P ⊓ ¬ Q
2. DMg通过以下公式重写ψ1中的(d1,…,dn)和(d1,…,dn),将ψ1转化为ψ2：
(d1,…,dn) (v1,…,vn) ( d1(v1) ⊓ ... ⊓ dn(vn);
(d1,…,dn) (v1,…,vn)(⊔ ... ⊔ 并且
=
其中, d = dom(di) (1( i ( n).
3. DMg通过以下式子消除逆谓词( p((G \ DG),将ψ2转化为ψ3：
( e (其中, e((G, dom(e) = dom())
4. DMg将ψ3转化为ψ4,通过重写不等式((vi1,…,vin(, (vj1,…,vjn(,() ( ((vi1, vj1( ⊔…⊔ ((vin ,vjn(;
5. DMg将ψ4转化为析取范式的标准形式ψ5；
6. DMg按如下步骤检查ψ5的每一个标准合取式M：
(1) 给定变量v,如果M中的模糊谓词p和同时含有变量v,并且p ( sub-group (d, G), 则M是不可满足的.
(2) 给定变量v,如果M中的模糊谓词p1和p2同时含有变量v,并且p1 ( sub-group (d1, G), p2 ( sub-group (d2, G), d1 ( d2, 则M是不可满足的.
(3) 否则,因为(G =sub-group (d, G), DMg将M划分为N, Md1 ,…, Mds的联合,其中, s是M中sub-group的数量,{d1,…,ds} ( DG,使得：
N包含所有的不等式谓词；
对Mdh (1(h( s)中的每个模糊数据类型谓词p, 满足p( sub-group (dh, G).
对于每一个( (vis, vjs(, 如果变量vis, vjs同时存在于Mdh中,则DMg将其添加到Mdh中. 然后,DMg调用相应的模糊数据类型检查器来检查Mdh的可满足性.最后,如果所有的模糊数据类型检查器返回可满足,则M是可满足的；如果ψ5中有一个标准合取式M是可满足的,则表明形如(6)式的模糊数据类型表达式ψ是可满足的, DMg返回真;否则, ψ是不可满足的, DMg返回假.
7. 算法结束.
定理2. 给定一致性模糊数据类型域G,则模糊数据类型管理器DMg根据算法2能够判定形如(6)式的模糊数据类型表达式的可满足性.
证明. 在算法2中,前5步是从形如(6)式的模糊数据类型表达式到一个模糊数据类型谓词联合的析取范式的等价转换.
在步骤1中,等价转换依据模糊数据类型表达式的语义进行:
假定p((G,并且p( sub-group (d, G), 则有
(¬p)D = ((D)n \ pD
= (((D)n \ (dom(p))D)∪((dom(p))D \ pD)
=(d,…,d)D ∪D (n个d)
所以有¬p (⊔ (d,…,d) (n个d);
同样有¬( p ⊔ (d,…,d) ( n个d).
假定q((G,是一个未定义的模糊数据类型谓词,根据模糊数据类型域中对逆谓词的语义解释,有D = ((D)n \ qD,所以 ( ¬q.
根据对域表达式的语义解释,有
¬(d1,…,dn)D =((D)n\(d1,…,dn)D=(d1,…,dn)D,
所以有¬(d1,…,dn) ( (d1,…,dn).
假定P, Q是具有相同元数的模糊数据类型表达式,根据摩根定律,以下两式显然成立.
¬(P ⊓ Q) ( ¬P ⊔ ¬Q
¬(P ⊔ Q) ( ¬P ⊓ ¬ Q
在步骤2中,d(DG, d1,…,dn ( sub-group (d, G), a(di)=1 (1( i ( n),根据定义,有
(d1,…,dn) (v1,…,vn) ( d1 (v1) ⊓ …⊓dn (vn)
同样有 (d1,…,dn) (v1,…,vn) ( ¬(d1,…,dn) (v1,…,vn)
¬d1 (v1) ⊔ …⊔ ¬dn (vn)
根据模糊数据类型域中对逆表达式的语义解释,对¬di的取值有以下两种可能的情形：
如果di=d, 那么(¬di)D =(¬d)D=D,所以有¬di=,
否则,(¬di)D =(D \diD =((D \ d D)∪ (dD \ diD)= D∪iD,所以有¬di (∪i.
由模糊数据类型域的一致性条件2,可以保证步骤3的等价转换是正确的.根据数理逻辑的知识,步骤4,5中的转化显然是等价的.最后,在步骤6中,算法检查析取范式ψ5的每一个标准合取式M,其中M是一个模糊数据类型谓词的联合.
在步骤6(1)中,假定M是可满足的,那么因为p ( sub-group (d, G), 则存在一个从SD到(D的映射(, 使得((v) ( dD; 又因为存在(v),所以((v) (D. 而dD∩D= (,产生矛盾,所以M是不可满足的.
在步骤6(2)中,假定M是可满足的,那么因为p1 ( sub-group (d, G), 则存在一个从SD到(D的映射(, 使得((v) ( d1D;又因为存在p2 (sub-group (d, G),所以((v) ( d2D.而d1D∩d2D= (,产生矛盾,所以M是不可满足的.
在步骤6(3)中,DMg将M划分为N, Md1,…, Mds的联合,然后通过调用模糊数据类型检查器来判定Mdh的可满足性.所以如果所有的模糊数据类型检查器返回的结果为真,则M返回真;最后,如果ψ5中有某一个合取式M取得真值,则DMg返回真. (
通过模糊数据类型管理器和模糊数据类型检查器,可以判断基于模糊数据类型域G的形如(6)式的模糊数据类型表达式的可满足性.也就是说,模糊数据类型推理机可以检查DC(x)的可满足性.在图1所示的推理结构中,F-SHOIQ(G)推理机正是通过调用模糊数据类型推理机来检查DC(x)的可满足性,并最终判定F-SHOIQ(G)概念D的可满足性.综上,基于F-SHOIQ(G) Tableaux扩展规则推理的算法1与模糊数据类型推理机,共同组成完整的判定F-SHOIQ(G)概念D的可满足性的推理系统.
可判定性证明
定理3. 如果G = ((G, DG, dom)是一个一致性模糊数据类型域,则关于G的形如(7)式的模糊数据类型谓词联合(的可满足性问题是可判定的.
证明. 根据每个模糊数据类型谓词所约束的基本数据类型的不同,通过交换律和结合律,(可以被等价的转化为如下形式：( = (d1( … ( (dk ( (U, 其中DG = {d1,…,dk}, (di (1( i ( k)是关于模糊数据类型子域sub-group(di, G)上的模糊数据类型谓词的联合,(U是未定义模糊数据类型谓词的联合.根据模糊数据类型域的一致性条件3和模糊数据类型检查器的设计,模糊数据类型谓词联合(S = (d1( … ( (dk 的可满足性问题是可判定的. (U是不可满足的当且仅当存在某一个模糊谓词p((G,使得三元组(p(v1,…,vn), ▷, r(和(p(v1,…,vn), ▷-, r’( (r ( r’)同时出现在(U中,显然这是可判定的.(是可满足的当且仅当(S和(U都是可满足的.所以关于(的可满足性问题是可判定的. (
定理4. 如果G = ((G, DG, dom)是一个一致性模糊数据类型域,那么关于G的形如(6)式的模糊数据类型查询ψ的可满足性问题是可判定的.
证明. 形如(6)式的模糊数据类型表达式的可满足性问题可以转化为有限个模糊数据类型谓词联合的可满足性问题来判定.
由域表达式构子所组成的模糊数据表达式可以转化为一元模糊谓词的联合:
(u1,…,un) (v1,…,vn)( u1(v1) ⊓ …⊓ un (vn)
同样有,
¬(u1,…,un)(v1,…,vn)(¬u1(v1) ⊔…⊔ ¬un (vn)
根据对逆表达式的语义解释和模糊数据类型域的一致性条件2,可以去掉(6)式中的逆谓词,从而最终可以将域表达式转化为以模糊数据类型谓词为命题变元的一般逻辑表达式.
显然,由模糊合取及模糊析取构子所组成的模糊数据类型表达式是以模糊数据类型谓词为命题变元的一般逻辑表达式.
根据((vi1,…,vin(, (vj1,…,vjn(, () ( ((vi1, vj1( ⊔…⊔ ((vin, vjn(,可以将(谓词的联合改写为一系列以形如((vik ,vjk(的谓词单元作为命题变元的一般逻辑表达式.
因为一般逻辑表达式可以在有限步内转化为相应的析取范式.析取范式是可满足的,当且仅当析取范式中有一个合取式是可满足的.根据定理3,模糊数据类型谓词联合的可满足性是可判定的,所以每个合取式的可满足性是可判定的.最终,形如(6)式的模糊数据类型查询ψ的可满足性问题是可判定的. (
定理5. 关于RBox R的用NNF形式表示的F-SHOIQ(G)概念D的可满足性问题是可判定的.
证明. 根据图1所示的推理结构,用于F-SHOIQ(G)概念D的可满足性判定的推理系统分为两部分:基于F-SHOIQ(G) Tableaux扩展规则的F-SHOIQ(G)推理机和模糊数据类型推理机.
应用F-SHOIQ(G) Tableaux扩展规则扩展初始化森林F成为完全森林的过程是可终止的.
记 h = |cl(D)|, mmax = max{m| ( mT1,…,Tn. E}.在F-SHOIQ(G) Tableaux扩展规则中,FSHOIQ-规则[5]用于在扩展森林F中添加或者删除抽象节点,或者在抽象节点x的L(x)集合中添加或删除三元组;而G-规则用于在扩展森林F中添加或者删除数据类型节点,或者在使用此规则的抽象节点x的DC(x)结构体中添加模糊数据类型约束.已知使用FSHOIQ-规则扩展森林F的过程是可终止的[5],下面证明使用G-规则扩展森林F的过程的终止性.
(i) 根据G-规则的内容,对每个模糊数据类型概念对应的形如(C, ⋈, k(的三元组,其中C ( {(T1,…,Tn. E, (T1,…,Tn. E, ( m’T1,…,Tn. E, ( mT1,…,Tn. E},G-规则只运行一次,而且不会再产生新的三元组,所以对每条数据类型知识,G-规则只使用一次.
(ii) 根据G-规则的内容,G-规则可能产生的数据类型后继节点只是在完全森林F的最后一层,即作为叶节点出现,所以G-规则在原有扩展森林的基础上只是对森林的深度增加了1.
(iii) 在G-规则中,只有(T1,…,Tn. E, (T1,…,Tn. E, ( mT1,…,Tn. E, ( mT1,…,Tn等概念相应的扩展规则可能产生数据类型后继节点,而每个抽象节点最多含有h个(T1,…,Tn. E, (T1,…,Tn. E, ( mT1,…,Tn. E, ( mT1,…,Tn. E概念,所以每一个抽象节点所含有数据类型后继节点的最大出度为hmmax.
根据定理4,通过模糊数据类型推理机,形如(6)式的模糊数据类型查询ψ的可满足性问题是可判定的.
综上,对用NNF形式表示的F-SHOIQ(G)概念D的可满足性问题是可判定的. (
5 相关工作
为了能够表示语义Web中的模糊知识,作为语义Web理论基础的模糊描述逻辑已经引起研究者的广泛关注.Straccia提出了模糊描述逻辑FALC,给出了FALC的语法、语义和Tableaux推理算法[11].但FALC仅提供了有限的模糊表示和推理能力,只包含了并、交、非、全称量词和存在量词等简单的构造算子,因而不能表示和推理复杂的模糊知识.李言辉将模糊概念和模糊关系的截集引入到描述逻辑中,提出了一种支持数量约束的扩展模糊描述逻辑EFALCN,给出了其推理算法,讨论了相应的推理复杂度[12].Hölldobler通过添加成员函数操作符作为概念构造算子,提出了模糊描述逻辑ALCFH[13].Sánchez通过添加模糊数量限定算子,提出了能够表示数量约束限制的模糊描述逻辑ALCQF+,给出了ALCQF+的推理算法及在某些情形下的算法优化方法[14].蒋运承提出了模糊描述逻辑FALNUI,给出了FALNUI的语法、语义及Tableaux推理算法[15].FALNUI包含FALC的所有构造算子,还包含数量约束和逆关系构造算子,但FALNUI不包含语义Web本体语言所必需的关系分层、传递关系和枚举个体等构造算子,因而FALNUI不能满足语义Web的需求.Stoilos在FALC的基础上添加了传递关系、逆关系,提出了表达能力更强的模糊描述逻辑fKD-SI,给出了检查ABox一致性的推理算法[4],并在fKD-SI基础上添加了关系分层和不带资格限定的数量约束等模糊构造算子,构成了表达能力更强的fKD-SHIN[4].蒋运承提出了面向语义Web表示的模糊描述逻辑FSHOIQ[5],给出了完整的推理算法.
为了能够在描述逻辑中表示数据信息,Lutz提出了有型域的概念,并进一步提出了描述逻辑ALC(D),给出了相应的推理算法,讨论了其推理复杂度[9].Horrocks提出了表达能力更强的能够表示数据信息的描述逻辑SHOQ(D)[16],给出了SHOQ(D)的推理算法.SHOQ(D)支持命名个体和数据类型,但它不支持自定义数据类型和自定义数据类型谓词.为此,Pan和Horrocks提出了能够表示自定义数据类型及谓词的数据类型域的概念,并在此基础上提出了描述逻辑SHOQ(G)和SHIQ(G)[6],给出了它们的推理算法,并讨论了算法的正确性和完备性.但是SHOQ(G)和SHIQ(G)只能表示精确的数据信息,不能处理模糊的数据信息.作为处理模糊数据信息的一个尝试,Straccia提出了模糊描述逻辑FALC(D)[17],后来又提出了表达能力更强的模糊描
表1 一些主要模糊描述逻辑的研究现状
仅支持模糊知识表示的模糊描述逻辑
支持模糊数据类型表示的模糊描述逻辑
FALC
EFALCN
f-ALCFH
f-ALCQF+
f-SI
f-SHIN
f-SHOIQ
f-ALC(D)
f-SHOIQ(D)
f-SHOIQ(G)
语法语义
[11]
[12]
[13]
[14]
[4]
[4]
[5]
[17]
[7]
推理算法
[11]
[12]
[13]
[14]
[4]
[4]
[5]
[17]
可判定性证明
[11]
[12]
[13]
[14]
[4]
[4]
[5]
述逻辑fuzzy SHOIQ(D)[7],但它只能表示简单的模糊数据类型谓词,不能表示自定义模糊数据类型及谓词.
表1给出了面向语义Web语义表示的一些主要模糊描述逻辑的研究现状.从中可以看出,本文的研究工作主要集中在表中最后一列,即讨论模糊描述逻辑F-SHOIQ(G)的语法语义,知识库表示,推理问题及其可判定性等.
6 结论
语义Web本体语言OWL及作为其推理基础的描述逻辑在数据类型表示方面存在很大的局限性,例如不能表示和推理含有自定义模糊数据类型及自定义模糊数据类型谓词的模糊数据信息.为此,提出了模糊描述逻辑F-SHOIQ(G).文中给出了F-SHOIQ(G)的语法、语义及相应的知识库表示,进而给出了F-SHOIQ(G)概念的可满足性推理算法.此外,将经典描述逻辑中的推理结构用于F-SHOIQ(G)的推理问题,提出了模糊扩展的推理结构,并设计了关于F-SHOIQ(G)的模糊数据类型推理机.在模糊扩展后的推理结构中,用户可以在内部支持的基本数据类型和模糊数据类型谓词的基础上,定义适合应用需求的新的模糊数据类型及模糊数据类型谓词.
在以后的研究工作中,将重点研究F-SHOIQ(G)推理算法的优化技术及其计算复杂度,并设计实现相应的推理机来验证推理算法的有效性.此外,还将进一步研究一般术语公理约束下模糊描述逻辑F-SHOIQ(G)的推理问题.
致谢 向对本文提出宝贵意见的评审专家表示衷心的感谢！
参 考 文 献
[1] Berners-Lee T., Hendler J. A., Lassila O.. The Semantic Web.
Scientific American, 2001, 284 (5): 34-43
[2] Nardi D., Brachman R. J.. An introduction to description logics //Baader F., McGuinness D. L., Nardi D.. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge: Cambridge University Press, 2003: 5-44
[3] Kang Da-Zhou, Xu Bao-Wen, Lu Jian-Jiang, Li Yan-Hui. Reasoning for a fuzzy description logic with comparison expressions // Proc. of the 2006 International Workshop on Description Logics, Lake District, UK. 2006: 111-118
[4] Stoilos G., Stamou G., Tzouvaras V., Pan J. Z., Horrocks I.. Reasoning with Very Expressive Fuzzy Description Logics. Journal of Artificial Intelligence Research, 2007, 30: 273-320
[5] Jiang Yun-Cheng, Shi Zhong-Zhi, Tang Yong, Wang Ju. Fuzzy description logic for semantics representation of the Semantic Web. Journal of software, 2007, 18(6): 1257-1269
(蒋运承, 史忠植, 汤庸, 王驹. 面向语义Web语义表示的模糊描述逻辑. 软件学报, 2007, 18(6): 1257-1269)
[6] Pan J. Z.. A flexible ontology reasoning architecture for the Semantic Web. IEEE Transaction on Knowledge and Data Engineering, 2007, 19(2): 246-260
[7] Straccia U.. Towards a fuzzy description logic for the Semantic Web (Preliminary Report) // Proc. of the 2nd European Semantic Web Conference, Heraklion, Crete, Greece. 2005: 167-181
[8] Zadeh L. A.. Fuzzy sets. Information and Control, 1965, 8(3): 338-353
[9] Lutz C.. NEXPTIME-complete description logics with concrete domains. ACM Transactions on Computational Logic, 2004, 5(4): 669-705
[10] Li Yan-Hui, Xu Bao-Wen, Lu Jian-Jiang, Kang Da-Zhou. Reasoning with general terminological axioms in fuzzy description logic FALCN. Journal of Software, 2008, 19(3): 594-604
(李言辉, 徐宝文, 陆建江, 康达周. 一般术语公理下模糊描
述逻辑FALCN推理. 软件学报, 2008, 19(3): 594-604)
[11] Straccia U.. Reasoning within fuzzy description logics. Journal of Artificial Intelligence Research, 2001, 14(1): 137-166
[12] Li Yan-Hui, Xu Bao-Wen, Lu Jian-Jiang, Kang Da-Zhou. On computational complexity of the extended fuzzy description logic with numerical restriction. Journal of Software, 2006, 17(5): 968−975
(李言辉, 徐宝文, 陆建江,康达周. 支持数量约束的扩展模糊描述逻辑复杂性研究. 软件学报, 2006, 17(5): 968-975)
[13] Hölldobler S., Störr H. P., Tran D. K.. The fuzzy description logic ALCFH with hedge algebras as concept modifiers. Journal of Advanced Computational Intelligence and Intelligent Informatics, 2003, 7 (3): 294-305
[14] Sánchez D., Tettamanzi G.. Reasoning and quantification in fuzzy description logics // Proc. of the 6th International Workshop on Fuzzy Logic and Applications, Crema, Italy, 2005. Berlin: Springer, 2005: 81-88
[15] Jiang Yun-Cheng, Tang Yong, Wang Ju, Shen Yu-Ming. A tableaux decision procedure for fuzzy description logic FALNUI. Journal of Computer Research and Development, 2007, 44(8): 1309-1316
(蒋运承, 汤庸, 王驹, 申宇铭. 模糊描述逻辑FALNUI的tableaux推理.计算机研究与发展, 2007, 44(8): 1309-1316)
[16] Horrocks I., Sattler U.. Ontology reasoning in the SHOQ(D) description logic // Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI 2001), Seattle, Washington, USA. 2001: 199–204
[17] Straccia U.. Fuzzy description logics with concrete domains. Pisa, Italy: ISTI-CNR, Technical Report: 2005-TR-03, 2005
MA Zong-Min, born in 1965, Ph. D., professor, Ph. D. supervisor. His research interests include intelligent data and knowledge engineering.
YAN Li, born in 1964, Ph. D., associate professor. Her research interests include XML databases.
CHENG Jing-Wei, born in 1974, Ph. D. candidate. His research interests include description logics and Semantic Web.
Background
Data type support is one of the most useful features that OWL is expected to provide, which has received extensive discussions in the Semantic Web Best Practices mailing list. Recent efforts have shown that Web ontology languages and their corresponding description logics are limited in the representation of fuzzy data information. Furthermore, they cannot deal with imprecision and uncertainty which widely exist in human knowledge and natural language. The existing researches mainly focus on the representation and reasoning of fuzzy knowledge rather than fuzzy data information. In order to provide reasoning services for the description logics integrated with fuzzy data type group, in this paper, we propose a kind of new fuzzy description logic named F-SHOIQ(G). F-SHOIQ(G) can support not only the representation and reasoning of fuzzy knowledge, but also the representation of fuzzy data information with customized fuzzy data types and predicates. The representation and reasoning capabilities of F-SHOIQ(G) go beyond the other fuzzy description logics in the representation of fuzzy data information. F-SHOIQ(G) lays a foundation for the representation and reasoning of fuzzy knowledge and data in the Semantic Web.
This work is supported by the National Science Foundation of China (60873010) and the Program for New Century Excellent Talents in University (NCET- 05-0288), and in part by the MOE Funds for Doctoral Programs (20050145024).
联系人：马宗民
地址：沈阳市东北大学信息科学与工程学院计算机应用技术研究所
邮编：110004
电话：024-83681582
传真：024-83681582
手机：13840472162
邮箱：mazongmin@
收稿日期:2008-1-24; 修改稿收到日期: 2009-5-22. 本课题得到国家自然科学基金(60873010)、教育部新世纪优秀人才支持计划(NCET-05-0288)、教育部高等学校博士学科点专项科研基金(20050145024)资助. 王海龙, 男, 1983年生, 博士研究生, 主要研究方向为描述逻辑与语义Web. 马宗民, 男, 1965年生, 博士, 教授, 博士生导师, 主要研究领域为智能数据与知识工程. E-mail: HYPERLINK "mailto:asdf036@" zongmin_ma@ . 严丽, 女, 1964年生, 博士, 副教授, 主要研究领域为XML数据库. 程经纬, 男, 1974年生, 博士研究生, 主要研究方向为描述逻辑与语义Web.
Re: [UNITS, OEP] FAQ: Constraints on data values range.
HYPERLINK " , Mailing Lists, starts from 2004.
PAGE
PAGE 3
F-SHOIQ(G) 推理机
模糊数据类型管理器
模糊数据类型检查器1
模糊数据类型检查器2
模糊数据类型推理机
模糊数据类型检查器n
… …
