基于Vague 关系数据模型的连接操作

赵法信

(岭南师范学院信息科学与技术学院，广东 湛江 524048)

1 概述

现实世界中存在着大量不精确、不确定的信息和数据。为了在信息系统中可以处理这些具有模糊性的信息和数据，许多研究已经将模糊集理论［1］用于扩展关系数据库模型，此类包含不精确属性值的数据库即被称为模糊数据库［2］。连接操作是关系数据库中同时处理多个关系的重要运算，它的模糊扩展和实现也一直是模糊关系数据库研究的重点之一，已引起了研究者们的兴趣［3-4］。

Vague 集［5］作为模糊集的进一步推广，解决了模糊集理论中单值隶属度不能同时表示支持和反对的证据的问题，具有更强的表达数据模糊性的能力［6-7］，但相对于模糊集理论来说，针对Vague 集的研究还处于起步阶段，特别是有关Vague 关系数据模型方面的研究则更少［8-9］。

在模糊数据库环境下，无论采用什么样模糊关系数据模型，对于模糊数据表T 和查询q，都可使用以下步骤获得正确操作结果:首先将含有模糊属性的数据表T 分解为其所对应的所有可能性状态{W1，W2，…，Wn}的集合，用rep(T)表示;然后对rep(T)的每一种可能性状态(皆为精确数据)发出查询q;最后所得到的集合{q(W1)，q(W2)，…，q(Wn)}即为q(T)的查询结果。虽然采用这种方法所获得的查询结果非常准确，但其查询效率和查询结果的表达方式都很难让人接受。因而，研究能够直接作用于模糊数据表T，且操作结果q(T)也类似于初始不精确数据表的查询方法是模糊数据库研究的一个重要内容。当然，新的方法必须以rep(q (T))=q (rep(T))为前提。

本文在研究基于扩展的Vague 关系数据模型的代数查询语言［10］和Vague 除操作［11］的工作基础上，对基于该模型的外键连接操作进行了进一步讨论，并给出了可直接作用于整个Vague 关系数据库的外键连接操作公式。同时，证明了由该公式得到的查询结果与q(rep(T))的等价性。进而对由外键连接操作和选择操作所组成的复合操作的有效性进行了讨论。

2 Vague 关系数据模型

定义1(Vague 集) 给定论域U 和其中的任意一个元素u。U 中的一个Vague 集V 可用一个真隶属函数tV和一个假隶属函数fV表示:tV:U →［0，1］fV:U→［0，1］，tV(u)+fV(u)≤1。其中，tV(u)是从支持u 的证据所导出的u 的隶属度下界，fV(u)则是从反对u 的证据所导出的u 的否定隶属度下界。假设U={u1，u2，…，un}，那么Vague 集V 可以表示为:

其中，tV(u)≤μV(u)≤1 -fV(u)且1≤i≤n。

这里u 的隶属度为区间值［tV(u)，1 -fV(u)］。当tV(u)等于1 -fV(u)时，Vague 集还原至模糊集，当tV(u)和1 -fV(u)同时为0 或1 时，Vague 集还原至经典集合。

定义2(Vague 关系数据模型) 设定义在论域Ui(1≤i≤m)上的属性为Ai。那么定义在关系模式R (A1，A2，…，Am)上的Vague 关系，r 可视为这些属性域笛卡尔积的Vague 子集，即:

其中，V (Ui)表示论域Ui上所有Vague 子集的集合。

经典数据库对应于现实世界的一种状态，但对于Vague 数据库而言，由于其所含信息的模糊性，它可能对应于现实世界的多种状态。如表1 所示的Vague 关系r 共对应2 种可能性状态(关系)，即关系r1和关系r2，分别如表2、表3 所示，其所对应的可能度分别为［0.7，0.8］∧［0.5，0.6］=［0.5，0.6］和［0.7，0.8］∧［0.7，0.9］=［0.7，0.8］。

表1 Vague 关系r

表2 关系r1

表3 关系r2

在上面定义的Vague 关系数据模型中，当Vague 关系数据库中的元组或属性值中的某些候选值被查询操作(如选择)筛选掉后，在查询结果所对应的可能性状态中将无法再找到这些被筛选掉的信息。因此，为保证直接作用于Vague 关系数据库的查询操作结果满足rep(q(T))=q(rep(T))，必须在数据库中记录相应的信息。为了解决此问题，对数据模型进行了进一步扩展，在数据模型中增加了一个的属性N，用于表示确信任意元组t 出现在给定关系r 中的程度，称之为必要度。必要度N 的初始值为1，当元组t 中的候选值未发生变化时，N 值不变，否则N 等于1 减去被筛选掉的所有候选值所对应可能度的最大值。当元组t 中属性N 的值不等于1 时，则有不包含t 的给定可能性状态的可能度为(1-N)。具体请参阅文献［10］。

3 基于Vague 关系模型的连接操作

定义3(经典等值连接) 设经典关系r 的关系模式为R(X，Y)，经典关系s 的关系模式为S(Y，Z)，其中X，Y，Z 为属性组，那么R 和S 关于Y 的等值连接可定义为:

其结果是关系r 和s 的笛卡尔积中满足r.Y=s.Y 的所有元组。

但当关系r 和s 为含有不确定信息的Vague 数据库时，直接使用定义3 中经典数据库连接操作的处理方法会产生一定的问题。

给定Vague 关系r 和Vague 关系s，如表4 和表5所示，其关系模式分别为R(U，Y)和S(V，Z)。对这2 个关系作等值连接join(r，s，(U=V))，其正确结果是〈［0.6，0.8］/ u1，a，b〉或〈［0.5，0.7］/ u2，a，c〉或为空。但是，由于同一个Vague 集中的不同候选值之间的相互独立性，由相同Vague 集中的不同候选值所组成元组之间是相互排斥的。这种元组的不独立性使得上述等值连接的结果不能表示为一个关系。根据文献［12］可知，如果要在模糊数据库环境下处理连接操作，其相关的数据模型就要有足够的能力表达相互分离的元组。

表4 Vague 关系r

表5 Vague 关系s

3.1 Vague 外键连接操作

为了解决在Vague 关系环境下执行经典连接操作所存在的问题，下面讨论一种特殊的连接操作，该操作能使连接操作结果关系中的元组保持独立性。

给定Vague 关系r(X，Y)，其中，X，Y 可以取不精确值。给定经典关系s(Y，Z)，且有函数依赖Y →Z 成立。属性Y 为关系s 的码，关系r 的外码。在这种情况下进行连接操作时，Vague 关系r 中的任意一个元组在结果关系中最多产生一条元组，从而确保结果关系中的元组能够保持独立性。将这种能够处理模糊数据的外键连接记为vf-join。需要说明的是，对这种外键连接的研究不仅具有一定的理论意义，实际上，在设计Vague 数据库的过程中，为减少冗余，常会使用与函数依赖相关的关系分解。而当需要将这些分解后的关系进行连接以产生结果关系时，即会用到上述的外键连接操作。

定义4(Vague 外键连接) 给定Vague 关系r，其模式为R(X，Y)，经典关系关系s，其模式为S(Y，Z)，其相应的外键连接操作vf-join(r，s，(r.Y=s.Y))的定义如下:

其主要思想为:对关系r 的每一个元组N/t(t=〈x，y〉)，检查Vague 属性Y 的任意解释∀yn∈Y 是否存在于s.Y 中。若存在，就将元组t 中由x ∈X 及所有满足r.Y=s.Y 的r.Y 的解释{y1+y2+…+ym}所组成的子元组t'=〈x，{y1+y2+…+ym}〉插入到结果关系中由t 产生的结果元组t”中，与t'相关的可能度是所有候选值{y1+y2+… +ym}相关可能度的最小值。与t'相关的必要度N 等于1 减去不存在于s.Y 中的所有t.Y 的解释的可能度的最大值。

下面给出定义4 满足性质rep(vf-join(r，s，(r.Y=s.Y)))=vf-join(rep(r)，s，(r.Y=s.Y))的有效性证明。

设W 是rep(vf-join(r，s，(r.Y=s.Y)))的一个可能性状态，即W ⊂rep(vf-join(r，s，(r.Y=s.Y)))，其相应应的可能度为π。显然，可以通过在Vague 关系vf-join(r，s，(r.Y=s.Y))中的所有Vague 集中分别选取相应的候选值来获得W，其可能度π为所取候选值相关可能度的最小值。很明显，Vague 关系r 中的Vague 集t.Y 是Vague 关系vf-join(r，s，(r.Y=s.Y))中相应Vague 集的超集，因此，同样可以通过在Vague 关系r 中的所有Vague 集中选取相应的候选值来获得r 的一个可能性状态W'后，再将W'与关系s 进行连接运算来获得W，并得到相同的可能度π，即W ⊂vf-join (rep(r)，s，(r.Y=s.Y))。

同理，也可以由W ⊂vf-join(rep(r)，s，(r.Y=s.Y))⇒W ⊂rep(vf-join(r，s，(r.Y=s.Y)))。

综上可得定义4 满足性质:

实例 给定Vague 关系Person(如表6 所示)，其关系模式为Person(姓名，性别，出生地)。经典关系City(如表7 所示)，其关系模式为City(城市，所属省份)，对Person 中的“出生地”和City 中的“城市”做外链连接操作，根据定义4，结果关系如表8所示。

表6 Vague 关系Person

表7 Vague 关系City

表8 vf-join 结果关系

从实例可以看出，定义4 中的Vague 外键连接操作公式是直接对Vague 数据库进行操作的，而无需分别对Vague 数据库所对应的所有可能性状态进行逐一扫描，其操作结果也是正确、有效的，而且其产生的结果关系也是以“紧凑”的形式存在的。显然，相对于分别对所有可能性状态进行操作(即:vfjoin(rep(r)，s，(r.Y=s.Y)))，直接对Vague 数据库进行操作(即:vf-join(r，s，(r.Y=s.Y)))可以在很大程度上降低Vague 外键连接计算过程的复杂性。

3.2 外键连接操作和选择操作的复合运算

在经典关系数据库中，如果关系r 和s 分别定义在模式R(X，Y)和S(Y，Z)上，Cr和Cs分别是作用于关系r 和关系s 上的选择条件。那么有下列等式成立:

下面以实例的Vague 关系Person 和经典关系City 为例，对上述等式在Vague 关系数据库环境下的有效性进行讨论。

(1)选择条件Cs为空，Cr只与属性X 相关

给定查询“查找所有男性的基本信息”，该查询可以用以下2 种形式表示:

Q1-1:select(vf-join(person，city，(出生地=城市))，性别=“男”)

Q1-2:vf-join(select(person，性别=“男”)，city，(出生地=城市))

查询Q1-1 和Q1-2 的查询结果相同，如表9 所示。也就是说，在这种情况下，有以下等式成立:

究其原因，主要在于此时选择条件仅作用于Vague 关系r(Cs是无效的)并且与连接属性没有任何联系。

表9 Q1-1 与Q1-2 查询结果

(2)选择条件Cr为空，Cs只与属性Z 相关。

给定查询“查找出生于广东的所有人的基本信息”，该查询可以表示为以下2 种形式:

Q2-1:vf-join(person，select(city，所属省份=“广东”)，(出生地=城市))

Q2-2:select(vf-join(person，city，(出生地=城市))，所属省份=“广东”)

查询Q2-1 和Q2-2 的查询结果分别如表10 和表11 所示，可以看出，两者的区别在于属性“出生地”值的不同。更进一步可以看出，Q2-2 的结果是不正确的，因为其结果中的第二条元组中“出生地”的值存在候选值“长沙”，该值不对应于任何有效的可能性状态(即该值不可能被选择)，因为它不满足选择条件，而且在“所属省份”中也没有其所对应的值。此时，表达式select(vf-join(r，s，(r.Y=s.Y))，Cs)与vf-join(r，select(s，Cs)，(r.Y=s.Y))是不等价的，可以证明，用后者可以获得正确的结果。

表10 Q2-1 查询结果

表11 Q2-2 查询结果

(3)仅考虑作用于属性Y 上的条件CY，下列查询表达式通常是不等价的。

可以证明，查询表达式Q3-2 和Q3-3 通常会产生正确的结果。

(4)仅考虑作用于属性Y 和属性Z 的复合选择条件(CYand CZ)，下列表达式通常也是不等价的，可以证明，表达式Q4-2 和Q4-3 通常是正确的。

综上可以看出，在Vague 数据库环境下，当选择操作和外键连接操作进行复合运算时，在经典数据库环境下成立的等式(1)不再一直有效。为了保证查询结果的正确性(和基于可能性状态的查询结果保持一致)，应该先执行选择操作，再执行外键连接操作。这就意味着当处理不精确值时，必须禁止那些在精确属性条件下为了提高执行效率而进行的操作转换。因而，需要为用户的查询形式制定一定的规则，查询也必须按照相应的表达式进行计算。

4 结束语

本文基于扩展的Vague 关系数据模型，讨论了一种Vague 外键连接操作的实现方法，并给出了相关的外键连接计算公式，该公式可直接对整个Vague 数据库进行操作，并满足性质rep(q(T))=q(rep(T))，与基于可能性状态的查询方法相比，该方法的查询结果有效且具有较高的执行效率。在此基础上，还对外键连接操作与选择操作进行复合运算时所存在的问题及应遵循的原则进行了讨论。

［1］Zadeh L A.Fuzzy Sets［J］.Information and Control，1965，8(3):338-353.

［2］Ma Z M，Mili F.Handling Fuzzy Information in Extended Possibility-based Fuzzy Relational Databases［J］.International Journal of Intelligent Systems，2002，17(10):925-942.

［3］Bosc P，Duval L，Pivert O.About Selections and Joins in Possibilistic Queries Addressed to Possibilistic Databases［C］//Proc.of International Conference on Database and Expert Systems Applications.Berlin，Germany:Springer，2002:597-606.

［4］Bosc P，Pivert O.About Projection-selection-join Queries Addressed to Possibilistic Relational Databases［J］.IEEE Transactions on Fuzzy Systems，2005，13(1):124-139.

［5］Gau W L，Buehrer D J.Vague Sets ［J］.IEEE Transactions on Systems，Man，and Cybernetics，1993，23(2):610-614.

［6］Lu An，Ng W.Vague Sets or Intuitionist Fuzzy Sets for Handling Vague Data:Which One is Better［C］//Proc.of LNCS'05.［S.1.］:IEEE Press，2005:401-416.

［7］欧阳春娟，李 斌，李 霞，等.基于Vague 集相似度量的图像隐写系统安全性测度［J］.计算机学报，2012，35(7):1510-1521.

［8］Lu A，Ng W.Maintaining Consistency of Vague Databases Using Data Dependencies ［J］.Data ＆ Knowledge Engineering，2009，68(7):622-641.

［9］Zhao F X，Xue B.Inclusion Dependencies in Vague Relational Databases［C］//Proc.of FSKD'12.［S.1.］:IEEE Press，2012:85-88.

［10］赵法信，马宗民，吕艳辉.基于Vague 数据库的代数查询语言［J］.小型微型计算机系统，2008，29(10):1893-1899.

［11］赵法信.基于Vague 关系数据模型的除操作研究［J］.计算机工程，2012，38(14):29-31.

［12］Imielinski T，Lipski W.IncompleteInformation in Relational Databases［J］.Journal of the Association for Computing Machinery，1984，31(1):761-791.