一种解决次协调数据库中无限关系的方法

摘要: 次协调数据库的数据模型是用来处理数据库中两类不确定信息，即不完全信息和不一致信息（矛盾信息）.次协调关系模型上的代数运算是普通关系上的代数运算的扩展，但由于次协调关系的特殊性，在其上的代数运算会产生无限关系，因此，以次协调关系为基础的DBMS必须能够表示和操纵无限关系.首先介绍了无限关系以及几种常见的解决方法，然后提出了一种新的元组扩展的方法以避免无限关系的出现，从而为次协调数据库的应用打下坚实的基础.

关键词: 次协调数据库；4值逻辑；无限关系；元组有效扩展

中图分类号:TP 311.13 文献标志码:A 文章编号:1672-8513(2011)03-0177-05

A Method for Solving the Infinite Relations in the Paraconsistent Database

YING Yi

(College of Computer Science and Technology, Sanjiang University, Nanjing 210012, China)

Abstract: The paraconsistent database is introduced to manipulate two kinds of uncertain information in the database: incomplete and inconsistent. Algebraic operators on the underlying paraconsistent relations of this model are generalizations of the usual ones on ordinary relations. Because of the particularity of paraconsistent relations, the result of algebraic operators can make infinite relations. So, a DBMS based on paraconsistent relations should be capable of handling infinite relations. Now, a new method of extension of tuple has been developed to avoid the appearance of infinite relations. These results help establish the application of the paraconsistent database.

Key words: paraconsistent database; four-valued logic; infinite relations; effective extension of tuple

在现实世界里，随处都可遇到不确定信息.例如，对于一个病人判断其是否患有乙肝，主要测试HBsAg这项指标，如果呈阳性则表明病人感染了肝炎病毒.现对这个病人分别做了2次测试，第1次呈阴性，第2次呈阳性，于是矛盾信息就出现了.再如，在测试病人是否患乙肝时，除了测试HBsAg以外，还有其他的指标配合判断，其中有一项是测试病人是否带有乙肝病毒抗体，这项指标对于患了乙肝的病人来说就不重要了，因此数据库中可能会缺失这项指标，这种情况下就产生了不完全信息［1］.[JP]

通常，人们认为数据库中不应该包含不确定信息，使得这种信息一直未被受到重视.目前使用的数据库还不能专门处理这种信息，然而生活中矛盾信息，不完全信息却是很常见的.次协调数据库的产生就是为了解决这样一类问题.

1 次协调关系

次协调逻辑［2］的逻辑性次于经典逻辑，即矛盾性在这种逻辑中不再普遍有效，但又远高于完全不协调系统，即矛盾在这一逻辑系统中不会任意扩散.将次协调逻辑引入到关系数据库系统中，就建立了次协调关系数据库［3］.次协调关系提供了一种在元组级别处理不完全甚至不一致信息的框架结构.[JP]

次协调关系模型以4值逻辑［4-5］为基础，是关系数据模型在4值逻辑上的扩张.比较运算和逻辑运算的结果有4种状态：真（t）、假（f）、未知（┴）、矛盾（┬）.

在次协调关系中，任意一关系R由一对关系R+和R-组成，即R=，其中R+是关系R上所有被认为是肯定的元组的集合，R-是关系R上所有被认为是否定的元组的集合.也可以认为：R+上的元组满足关系R，R-上的元组不满足关系R.很明显，在R+和R-中都不出现的元组是未知信息（不知该元组是否满足关系R），在R+和R-中都出现的元组是矛盾信息（该元组既满足关系R又不满足关系R）.因此，这种关系模型能够有效地表示和处理未知信息和矛盾信息.

1.1 次协调关系模型

设有关系模式Σ，它是若干属性的有限集合，即Σ={ A1，A2，…，An }.每个属性都对应一个“域”，属性A的非空值域记作dom(A)，关系模式Σ上的一个元组t是这样一个映射：Σ∪A∈Σdom(A)，即对于任意的属性A∈Σ，有t(A)∈dom(A).

关系模式Σ上所有元组的集合记作Tup(Σ)，Tup(Σ)的任意一个有限子集R都称作Σ上的一个关系.Tup(Σ)是关系模式Σ上所有属性域的笛卡儿积，即Tup(Σ)=dom(A1)×dom(A2)×…×dom(An).

定义1 关系模式Σ上的次协调关系是一对关系R=，其中R+和R-是Tup(Σ)上的任意子集.

如前所述，我们认为R+是关系R上所有被认为是肯定的元组的集合，R-是关系R上所有被认为是否定的元组的集合.注意，由于矛盾信息在次协调关系中是存在的，所以我们并没有假设R+和R-是相互独立的，即R+和R-可能相交，又由于关系R中存在着未知信息，所以R+和R-也没有包含Tup(Σ)中的所有元组.

对于一个次协调关系R，如果R+和R-是不相交的，并且R+和R-又包含了Tup(Σ)中的所有元组，那么次协调关系R在本质上是一个普通关系，这个普通关系就是R+（满足关系R），由于R-（不满足关系R）没有现实意义，通常不将它表示出来.因此，每一个普通关系都有一个次协调关系与之对应，它们包含有相同的信息内容.但对于任意一个次协调关系，并不一定存在一个普通关系与之对应，因此，次协调关系是普通关系的一个扩张.普通关系中的运算，例如并、交、投影，也能够推广到次协调关系上.

为了反映这样一种扩张，并与普通关系相区别，在普通关系的运算符上打上一个点来表示相对应的次协调关系运算符，例如，普通关系上的并运算用∪表示，与此相对应，用∪•表示次协调关系上的并运算.

下面看一个例子，假设某个医院有2个病人P1，P2，他们2人分别做了3种不同的医疗测试s1，s2，s3.我们把2人的测试结果记录在次协调关系TEST中.TEST是基于关系模式{P，s}的，如图1所示.[KH*2]

从次协调关系TEST所包含的信息中，可以看出病人P1的测试s1，s2结果是阳性的，测试s3结果是阴性的；病人P2的测试s3结果是阳性的，而测试s1结果既是阳性的又是阴性的.

请注意，病人P2的测试s2结果是未知的.这种信息的缺失可能是由于很多原因造成的，比如，该医疗测试还未做，或做过了但结果还未出来，甚至是因为医生认为该测试对病人来说并不重要而将结果忽略了.

我们也注意到，病人P2的测试s1结果既是阳性的又是阴性的（矛盾的）.这种信息的不一致可能是由于在一段时间内对病人P2进行了2次s1测试所造成的.

1.2 次协调关系上的关系运算

次协调关系上的集合运算和关系运算是普通关系上的代数运算在次协调逻辑上的扩张［3］.下面我们来讨论次协调关系上的关系运算.首先给出元组扩展的含义.

定义2 设有关系模式Σ，Δ，且ΣΔ，则对于任意元组t∈Tup(Σ)，tΔ是元组t在关系模式Δ上扩展后元组的集合，即tΔ={t′∈Tup(Δ)| t′(Ai)=t(Ai)，对于所有Ai∈Σ}.

显然，如果任意一个(Δ-Σ)（在Δ上而不在Σ上）上的属性域是无限的，则tΔ也是无限的.

同理，对于任意TTup(Σ)，有TΔ=∪t∈TtΔ.

定义3 [JP+2]设在关系模式Σ上有次协调关系R，在关系模式Δ上有次协调关系S，则R和S的自然连接，记作R[XC公式.TIF;%10%10;X*6]S，它是一个在关系模式Σ∪Δ上的次协调关系，并且有：[JP]

(R[XC公式.TIF;%10%10;X*6]S)+= R+[XC公式2.TIF;%10%10;X*6］S+，

(R[XC公式.TIF;%10%10;X*6]S)-=(R-)Σ∪Δ(S-)Σ∪Δ.

定义4 [JP+2]设有关系模式Σ，Δ，且ΔΣ，在关系模式Σ上有次协调关系R，则R在Δ上的投影，记作π[DD(-*4/5]•[DD)]Δ(R)，它是一个在关系模式Δ上的次协调关系，并且有：[JP]

π[DD(-*4/5]•[DD)]Δ(R)+=ΠΔ(R+),

π[DD(-*4/5]•[DD)]Δ(R)-={t∈Tup(Δ)|tΣR-}.

定义5 设在关系模式Σ上有次协调关系R，令F是关于关系模式Σ上若干属性的逻辑运算（由常量、变量、算术比较符（>，≥，

σ[DD(-*4/5]•[DD)]F(R)+=σF(R+),

σ[DD(-*4/5]•[DD)]F(R)-= R-Uσ-F(Tup(Σ)).

2 次协调数据库中的无限关系

2.1 无限关系的产生

[JP+2]由1.1所述知道：Tup(Σ)=dom(A1)×dom(A2)×…×dom(An).因此，Tup(Σ)是无限的当且仅当至少存在1个属性Ai(1≤i≤n)，它的值域dom(Ai)是无限的.由于关系中的属性经常是无限的（例如实数域），Tup(Σ) 是无限的几乎不可避免.但是，普通关系是Tup(Σ)的一个子集，它作为一个有限关系能够满足绝大部分现实世界的需求，而且，在普通关系上的代数运算是封闭的，所以即使Tup(Σ)是无限的，任意的普通关系，以有限的元组为起点，进行任意的代数运算后，仍旧能够得到一个元组有限的普通关系.基于这条性质，有限的普通关系很容易设计成关系数据库并将其应用.[JP]

然而，次协调关系并不具备这一良好性质.

定义6 对于次协调关系R=，如果R+和R-都是Tup(Σ)的有限子集，那么R被称为有限的次协调关系.

我们能够证明：在次协调关系下，集合运算∪•和－ •是封闭的［6］，也就是说，从一个有限的次协调关系开始，进行∪•和－ •运算，最后得到的依旧是一个有限的次协调关系.可是，运算，σ[DD(-*4/5]•[DD)]，π[DD(-*4/5]•[DD)]都不能保持有限，当关系模式的某个属性域是无限时，，σ[DD(-*4/5]•[DD)]，π[DD(-*4/5]•[DD)]运算结果的否定部分R-可能是一个元组无限的关系.从，σ[DD(-*4/5]•[DD)]，π[DD(-*4/5]•[DD)]运算的定义，我们很容易发现这主要是由元组扩展造成的.[JP]

元组扩展的含义在1.2中论述过.

例如，令R是关系模式{X, Y}上的次协调关系，S是关系模式{Y, Z}上的次协调关系.且X,Y的值域为{a，b，c}，而Z的值域是自然数.如图2所示.

令T=R[XC公式.TIF;%10%10;X*6]S，它是在关系模式{X, Y, Z}上的次协调关系.这时，由于dom(Z)是无限的，在运算结果T-中就出现了无限关系,如图3所示.

值得注意的是，元组关系演算允许出现无限关系，但在基于2值逻辑的普通关系中，产生无限关系的表达式是无意义的，因此，普通关系的元组关系演算只考虑安全的表达式（不产生无限关系的表达式）.但是，由于次协调数据库无可避免的要解决无限关系，所以，表达式的安全性并不需要在次协调关系别考虑［7］.

2.2 有效语言

我们知道，无限关系是无法在数据库中表示的，所以，怎样在数据库中存储无限关系，是次协调数据库应用首先必须解决的问题.

我们认为，需要找到一种无限的次协调关系语言类，如果它能有效地构成次协调DBMS，就必须满足以下性质：①对于在其上的次协调关系R，R+，R-能够以有限的形式存储无限关系；②次协调关系上的代数运算在该语言类中必须封闭.如果满足这2条性质，我们就称该语言为有效语言.

基于以上性质，我们首先考虑的是递归可枚举语言.在计算复杂性理论中有2种不同的对递归可枚举语言分类的方法得到广泛的研究.一类是基于语法的Chomsky分类方法，它根据语法表达能力的不同将递归可枚举语言分为4类：REGULAR（正则语言）、CONTEXT-FREE（上下文无关语言）、CONTEXT-SENSITIVE（上下文敏感语言）、R.E.（递归可枚举集语言）.另一类是基于图灵机的分类方法，它根据时间/空间使用的确定性将递归可枚举语言分为以下几类：DTIME(ploy),NDTIME(ploy),DSPACE(ploy),DSPACE(log),NSPACE(log).[JP]

我们能够证明，正则语言是一个有效语言，通过一个简单的语法转换（在末尾添加空标志，使得所有元组的任意属性值都具有相同的长度），上下文无关语言、DSPACE语言也是一个有效语言.而其它语言都不能称为有效语言［6］.

[JP+2]可是，我们知道，许多经常使用的运算（例如比较运算和算术运算），是不能在正则语言上执行的，而这些运算对于数据库中的选择运算（σ）是必须的.另一方面，对于上下文有关语言，PSPACE语言虽然能够通过一种元组级的语法转换使其在次协调数据库中有效地工作，但是这种语法转换会使得数据库的存储空间变得很大，当数据库中的元组数量很多时，计算量也会很大.[JP]

3 元组有效扩展

如果不从语言类的角度而从属性域的角度去考虑问题，难度要小一些，而且也更加实用.例如，现在有一种解决办法是对于关系模式Σ={ A1,A2,…,An }，其中的每一个属性Ai ( 1≤i≤n )都给出一个有限的值域.

我们这里给出一种改进后的方法，思想仍旧是限定属性的值域，但不是明显地认为值域有限.我们仍然认为值域无限，只是在进行元组扩展时，只将其扩展至有效的值域范围，我们称这种方法为元组有效扩展.

下面来看元组有效扩展的含义.首先给出关系模式Σ上属性Ai有效值域的概念.

定义7 设有关系模式Σ(A1,A2,…,An)，属性Ai的非空值域记作dom(Ai)(1≤i≤n).在关系模式Σ上有次协调关系R，则与R相关的Ai的有效值域记为adom(Ai, R)，adom(Ai, R)={ d | d∈dom(Ai)，存在元组t∈R+且t(Ai)=d或者元组t∈R-且t(Ai)=d}.与R相关的关系模式Σ上的有效元组集合记作aTup(Σ, R).aTup(Σ, R)是关系模式Σ上所有属性有效值域的笛卡儿积，即aTup(Σ, R)=adom(A1, R)×adom(A2, R)×…×adom(An, R).

定理1 与次协调关系R相关的关系模式Σ上的有效元组集合aTup(Σ, R)是有限的.

证明 属性Ai的值域dom(Ai)可能是无限的,并且adom(Ai, R)dom(Ai);

由定义7，有adom(Ai,R)是所有在关系R+，R-中出现的属性Ai的值的集合，有些Ai的值虽然属于dom(Ai)，但它不在R+，R-中出现，则它不属于adom(Ai, R).

因为在R+，R-中出现的Ai的值是有限的，所以adom(Ai, R)是dom(Ai)的一个有限子集.

由定义7，有aTup(Σ, R)=adom(A1, R)×adom(A2, R)×…×adom(An, R)，所以aTup(Σ, R)也是有限的.

定义8 设有关系模式Σ,Δ，且ΣΔ，令R,S分别是关系模式Σ,Δ上的次协调关系，则对于元组t∈aTup(Σ, R)，tΔ是元组t在关系模式Δ上有效扩展后元组的集合，即tΔ={ t′ ∈aTup(Δ, S) | t′(Ai)=t(Ai)，对于所有Ai ∈Σ }.

定理2 若tΔ是元组t在关系模式Δ上有效扩展后元组的集合，则tΔ是有限的.

证明 因为tΔ是元组t在关系模式Δ上有效扩展后元组的集合，若t′∈tΔ，则t′ ∈aTup(Δ,S).所以tΔ aTup(Δ, S).

由定理1，有aTup(Δ, S)是有限的,所以tΔ是aTup(Δ, S)的一个有限子集，所以tΔ是有限的.

因此，当在次协调关系上，要进行[XC公式.TIF;%10%10;X*6]，σ[DD(-*4/5]•[DD)]，π[DD(-*4/5]•[DD)]运算时，我们用元组有效扩展的方法代替元组扩展方法，就仍旧能够得到一个有限的次协调关系.

[JP+2]再看上面提到的例子.使用元组有效扩展的方法来执行T=R[XC公式.TIF;%10%10;X*6]S运算，T-在adom(Z, R)上进行扩展.由于adom(Z, R) = { 1, 2, 3 }，所以运算结果T-仍旧是一个有限关系，如图4所示.

4 结语

本文首先介绍了次协调数据库中的无限关系，之后针对次协调关系下代数运算不封闭的特性，提出一种新的元组扩展的方法，避免无限关系的产生，这对次协调数据库的实现有着重大的意义.但由于次协调数据库的概念直到近年来才被提出，在许多理论和应用方面，例如关系演算、查询优化［8］、模糊关系和隶属度［9］、完整性约束、查询语言［10-11］等，还有待于进一步的深入研究.

参考文献:

［1］王新, 赵强. 不完全数据库中的关联规则挖掘［J］.云南民族大学学报：自然科学版, 2005,14(3): 252-254.

［2］姜跃, 周凯, 赵榆琴, 等. 基于信任半格的次协调逻辑领域本体公理表示方法的研究［J］.云南民族大学学报：自然科学版, 2009,18(3): 260-263.

［3］BAGAI R,SUNDERRAMAN R. A paraconsistent relational data model［J］. International Journal of Computer Mathematics, Gordon and Breach Science Publishers, 1995, 55(1): 39-55.

［4］BELNAP N D. A useful four-valued logic［C］// Modern Uses of Many-Valued Logic.Boston:D Reidel Publishing Company,1977:8-37.

［5］毛宇光, 徐洁磐, 朱梧. 用于不完全信息数据库的多值逻辑研究［J］.计算机科学, 2002,29(z1): 279-281.

［6］TRAN N, BAGAI R.Infinite relations in paraconsistent databases［J］. Lecture Notes in Computer Science, Springer-Verlag, 1999, 1691: 275-287.

［7］BAGAI R. Tuple relational calculus for paraconsistent databases［J］. Lecture Notes in Artificial Intelligence, Springer-Verlag, 2000, 1952: 409-416.

［8］BAGAI R. A query construct for paraconsistent databases［C］//In Proceedings of the 7th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems. Paris, France, 1998: 428-434.

［9］应毅, 毛宇光. 可信度在次协调关系数据库中的应用［J］.计算机科学, 2005,32(7,zB): 392-395.[ZK)]

［10］[ZK(#]黄慧, 毛宇光, 刘正涛. 一种支持次协调数据库的UcQL语言［J］.计算机工程与应用, 2006,42(10): 158-161.

［11］黄慧, 毛宇光. 基于多重集的次协调数据库的研究［J］.计算机应用, 2005,25(z1): 183-185.

收稿日期:2010-11-01.

基金项目:三江学院创新工程（200905）;三江学院创新计划（XJ201033）.

作者简介:应毅（1979-），男，硕士，讲师.主要研究方向：软件工程及数据库.