基于Vague 關(guān)系數(shù)據(jù)模型的連接操作

趙法信

(嶺南師范學(xué)院信息科學(xué)與技術(shù)學(xué)院，廣東 湛江 524048)

1 概述

現(xiàn)實(shí)世界中存在著大量不精確、不確定的信息和數(shù)據(jù)。為了在信息系統(tǒng)中可以處理這些具有模糊性的信息和數(shù)據(jù)，許多研究已經(jīng)將模糊集理論［1］用于擴(kuò)展關(guān)系數(shù)據(jù)庫模型，此類包含不精確屬性值的數(shù)據(jù)庫即被稱為模糊數(shù)據(jù)庫［2］。連接操作是關(guān)系數(shù)據(jù)庫中同時處理多個關(guān)系的重要運(yùn)算，它的模糊擴(kuò)展和實(shí)現(xiàn)也一直是模糊關(guān)系數(shù)據(jù)庫研究的重點(diǎn)之一，已引起了研究者們的興趣［3-4］。

Vague 集［5］作為模糊集的進(jìn)一步推廣，解決了模糊集理論中單值隸屬度不能同時表示支持和反對的證據(jù)的問題，具有更強(qiáng)的表達(dá)數(shù)據(jù)模糊性的能力［6-7］，但相對于模糊集理論來說，針對Vague 集的研究還處于起步階段，特別是有關(guān)Vague 關(guān)系數(shù)據(jù)模型方面的研究則更少［8-9］。

在模糊數(shù)據(jù)庫環(huán)境下，無論采用什么樣模糊關(guān)系數(shù)據(jù)模型，對于模糊數(shù)據(jù)表T 和查詢q，都可使用以下步驟獲得正確操作結(jié)果:首先將含有模糊屬性的數(shù)據(jù)表T 分解為其所對應(yīng)的所有可能性狀態(tài){W1，W2，…，Wn}的集合，用rep(T)表示;然后對rep(T)的每一種可能性狀態(tài)(皆為精確數(shù)據(jù))發(fā)出查詢q;最后所得到的集合{q(W1)，q(W2)，…，q(Wn)}即為q(T)的查詢結(jié)果。雖然采用這種方法所獲得的查詢結(jié)果非常準(zhǔn)確，但其查詢效率和查詢結(jié)果的表達(dá)方式都很難讓人接受。因而，研究能夠直接作用于模糊數(shù)據(jù)表T，且操作結(jié)果q(T)也類似于初始不精確數(shù)據(jù)表的查詢方法是模糊數(shù)據(jù)庫研究的一個重要內(nèi)容。當(dāng)然，新的方法必須以rep(q (T))=q (rep(T))為前提。

本文在研究基于擴(kuò)展的Vague 關(guān)系數(shù)據(jù)模型的代數(shù)查詢語言［10］和Vague 除操作［11］的工作基礎(chǔ)上，對基于該模型的外鍵連接操作進(jìn)行了進(jìn)一步討論，并給出了可直接作用于整個Vague 關(guān)系數(shù)據(jù)庫的外鍵連接操作公式。同時，證明了由該公式得到的查詢結(jié)果與q(rep(T))的等價性。進(jìn)而對由外鍵連接操作和選擇操作所組成的復(fù)合操作的有效性進(jìn)行了討論。

2 Vague 關(guān)系數(shù)據(jù)模型

定義1(Vague 集) 給定論域U 和其中的任意一個元素u。U 中的一個Vague 集V 可用一個真隸屬函數(shù)tV和一個假隸屬函數(shù)fV表示:tV:U →［0，1］fV:U→［0，1］，tV(u)+fV(u)≤1。其中，tV(u)是從支持u 的證據(jù)所導(dǎo)出的u 的隸屬度下界，fV(u)則是從反對u 的證據(jù)所導(dǎo)出的u 的否定隸屬度下界。假設(shè)U={u1，u2，…，un}，那么Vague 集V 可以表示為:

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

這里u 的隸屬度為區(qū)間值［tV(u)，1 -fV(u)］。當(dāng)tV(u)等于1 -fV(u)時，Vague 集還原至模糊集，當(dāng)tV(u)和1 -fV(u)同時為0 或1 時，Vague 集還原至經(jīng)典集合。

定義2(Vague 關(guān)系數(shù)據(jù)模型) 設(shè)定義在論域Ui(1≤i≤m)上的屬性為Ai。那么定義在關(guān)系模式R (A1，A2，…，Am)上的Vague 關(guān)系，r 可視為這些屬性域笛卡爾積的Vague 子集，即:

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

經(jīng)典數(shù)據(jù)庫對應(yīng)于現(xiàn)實(shí)世界的一種狀態(tài)，但對于Vague 數(shù)據(jù)庫而言，由于其所含信息的模糊性，它可能對應(yīng)于現(xiàn)實(shí)世界的多種狀態(tài)。如表1 所示的Vague 關(guān)系r 共對應(yīng)2 種可能性狀態(tài)(關(guān)系)，即關(guān)系r1和關(guān)系r2，分別如表2、表3 所示，其所對應(yīng)的可能度分別為［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 關(guān)系r

表2 關(guān)系r1

表3 關(guān)系r2

在上面定義的Vague 關(guān)系數(shù)據(jù)模型中，當(dāng)Vague 關(guān)系數(shù)據(jù)庫中的元組或?qū)傩灾抵械哪承┖蜻x值被查詢操作(如選擇)篩選掉后，在查詢結(jié)果所對應(yīng)的可能性狀態(tài)中將無法再找到這些被篩選掉的信息。因此，為保證直接作用于Vague 關(guān)系數(shù)據(jù)庫的查詢操作結(jié)果滿足rep(q(T))=q(rep(T))，必須在數(shù)據(jù)庫中記錄相應(yīng)的信息。為了解決此問題，對數(shù)據(jù)模型進(jìn)行了進(jìn)一步擴(kuò)展，在數(shù)據(jù)模型中增加了一個的屬性N，用于表示確信任意元組t 出現(xiàn)在給定關(guān)系r 中的程度，稱之為必要度。必要度N 的初始值為1，當(dāng)元組t 中的候選值未發(fā)生變化時，N 值不變，否則N 等于1 減去被篩選掉的所有候選值所對應(yīng)可能度的最大值。當(dāng)元組t 中屬性N 的值不等于1 時，則有不包含t 的給定可能性狀態(tài)的可能度為(1-N)。具體請參閱文獻(xiàn)［10］。

3 基于Vague 關(guān)系模型的連接操作

定義3(經(jīng)典等值連接) 設(shè)經(jīng)典關(guān)系r 的關(guān)系模式為R(X，Y)，經(jīng)典關(guān)系s 的關(guān)系模式為S(Y，Z)，其中X，Y，Z 為屬性組，那么R 和S 關(guān)于Y 的等值連接可定義為:

其結(jié)果是關(guān)系r 和s 的笛卡爾積中滿足r.Y=s.Y 的所有元組。

但當(dāng)關(guān)系r 和s 為含有不確定信息的Vague 數(shù)據(jù)庫時，直接使用定義3 中經(jīng)典數(shù)據(jù)庫連接操作的處理方法會產(chǎn)生一定的問題。

給定Vague 關(guān)系r 和Vague 關(guān)系s，如表4 和表5所示，其關(guān)系模式分別為R(U，Y)和S(V，Z)。對這2 個關(guān)系作等值連接join(r，s，(U=V))，其正確結(jié)果是〈［0.6，0.8］/ u1，a，b〉或〈［0.5，0.7］/ u2，a，c〉或?yàn)榭铡５牵捎谕粋€Vague 集中的不同候選值之間的相互獨(dú)立性，由相同Vague 集中的不同候選值所組成元組之間是相互排斥的。這種元組的不獨(dú)立性使得上述等值連接的結(jié)果不能表示為一個關(guān)系。根據(jù)文獻(xiàn)［12］可知，如果要在模糊數(shù)據(jù)庫環(huán)境下處理連接操作，其相關(guān)的數(shù)據(jù)模型就要有足夠的能力表達(dá)相互分離的元組。

表4 Vague 關(guān)系r

表5 Vague 關(guān)系s

3.1 Vague 外鍵連接操作

為了解決在Vague 關(guān)系環(huán)境下執(zhí)行經(jīng)典連接操作所存在的問題，下面討論一種特殊的連接操作，該操作能使連接操作結(jié)果關(guān)系中的元組保持獨(dú)立性。

給定Vague 關(guān)系r(X，Y)，其中，X，Y 可以取不精確值。給定經(jīng)典關(guān)系s(Y，Z)，且有函數(shù)依賴Y →Z 成立。屬性Y 為關(guān)系s 的碼，關(guān)系r 的外碼。在這種情況下進(jìn)行連接操作時，Vague 關(guān)系r 中的任意一個元組在結(jié)果關(guān)系中最多產(chǎn)生一條元組，從而確保結(jié)果關(guān)系中的元組能夠保持獨(dú)立性。將這種能夠處理模糊數(shù)據(jù)的外鍵連接記為vf-join。需要說明的是，對這種外鍵連接的研究不僅具有一定的理論意義，實(shí)際上，在設(shè)計(jì)Vague 數(shù)據(jù)庫的過程中，為減少冗余，常會使用與函數(shù)依賴相關(guān)的關(guān)系分解。而當(dāng)需要將這些分解后的關(guān)系進(jìn)行連接以產(chǎn)生結(jié)果關(guān)系時，即會用到上述的外鍵連接操作。

定義4(Vague 外鍵連接) 給定Vague 關(guān)系r，其模式為R(X，Y)，經(jīng)典關(guān)系關(guān)系s，其模式為S(Y，Z)，其相應(yīng)的外鍵連接操作vf-join(r，s，(r.Y=s.Y))的定義如下:

其主要思想為:對關(guān)系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}〉插入到結(jié)果關(guān)系中由t 產(chǎn)生的結(jié)果元組t”中，與t'相關(guān)的可能度是所有候選值{y1+y2+… +ym}相關(guān)可能度的最小值。與t'相關(guān)的必要度N 等于1 減去不存在于s.Y 中的所有t.Y 的解釋的可能度的最大值。

下面給出定義4 滿足性質(zhì)rep(vf-join(r，s，(r.Y=s.Y)))=vf-join(rep(r)，s，(r.Y=s.Y))的有效性證明。

設(shè)W 是rep(vf-join(r，s，(r.Y=s.Y)))的一個可能性狀態(tài)，即W ?rep(vf-join(r，s，(r.Y=s.Y)))，其相應(yīng)應(yīng)的可能度為π。顯然，可以通過在Vague 關(guān)系vf-join(r，s，(r.Y=s.Y))中的所有Vague 集中分別選取相應(yīng)的候選值來獲得W，其可能度π為所取候選值相關(guān)可能度的最小值。很明顯，Vague 關(guān)系r 中的Vague 集t.Y 是Vague 關(guān)系vf-join(r，s，(r.Y=s.Y))中相應(yīng)Vague 集的超集，因此，同樣可以通過在Vague 關(guān)系r 中的所有Vague 集中選取相應(yīng)的候選值來獲得r 的一個可能性狀態(tài)W'后，再將W'與關(guān)系s 進(jìn)行連接運(yùn)算來獲得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 滿足性質(zhì):

實(shí)例 給定Vague 關(guān)系Person(如表6 所示)，其關(guān)系模式為Person(姓名，性別，出生地)。經(jīng)典關(guān)系City(如表7 所示)，其關(guān)系模式為City(城市，所屬省份)，對Person 中的“出生地”和City 中的“城市”做外鏈連接操作，根據(jù)定義4，結(jié)果關(guān)系如表8所示。

表6 Vague 關(guān)系Person

表7 Vague 關(guān)系City

表8 vf-join 結(jié)果關(guān)系

從實(shí)例可以看出，定義4 中的Vague 外鍵連接操作公式是直接對Vague 數(shù)據(jù)庫進(jìn)行操作的，而無需分別對Vague 數(shù)據(jù)庫所對應(yīng)的所有可能性狀態(tài)進(jìn)行逐一掃描，其操作結(jié)果也是正確、有效的，而且其產(chǎn)生的結(jié)果關(guān)系也是以“緊湊”的形式存在的。顯然，相對于分別對所有可能性狀態(tài)進(jìn)行操作(即:vfjoin(rep(r)，s，(r.Y=s.Y)))，直接對Vague 數(shù)據(jù)庫進(jìn)行操作(即:vf-join(r，s，(r.Y=s.Y)))可以在很大程度上降低Vague 外鍵連接計(jì)算過程的復(fù)雜性。

3.2 外鍵連接操作和選擇操作的復(fù)合運(yùn)算

在經(jīng)典關(guān)系數(shù)據(jù)庫中，如果關(guān)系r 和s 分別定義在模式R(X，Y)和S(Y，Z)上，Cr和Cs分別是作用于關(guān)系r 和關(guān)系s 上的選擇條件。那么有下列等式成立:

下面以實(shí)例的Vague 關(guān)系Person 和經(jīng)典關(guān)系City 為例，對上述等式在Vague 關(guān)系數(shù)據(jù)庫環(huán)境下的有效性進(jìn)行討論。

(1)選擇條件Cs為空，Cr只與屬性X 相關(guān)

給定查詢“查找所有男性的基本信息”，該查詢可以用以下2 種形式表示:

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

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

查詢Q1-1 和Q1-2 的查詢結(jié)果相同，如表9 所示。也就是說，在這種情況下，有以下等式成立:

究其原因，主要在于此時選擇條件僅作用于Vague 關(guān)系r(Cs是無效的)并且與連接屬性沒有任何聯(lián)系。

表9 Q1-1 與Q1-2 查詢結(jié)果

(2)選擇條件Cr為空，Cs只與屬性Z 相關(guān)。

給定查詢“查找出生于廣東的所有人的基本信息”，該查詢可以表示為以下2 種形式:

Q2-1:vf-join(person，select(city，所屬省份=“廣東”)，(出生地=城市))

Q2-2:select(vf-join(person，city，(出生地=城市))，所屬省份=“廣東”)

查詢Q2-1 和Q2-2 的查詢結(jié)果分別如表10 和表11 所示，可以看出，兩者的區(qū)別在于屬性“出生地”值的不同。更進(jìn)一步可以看出，Q2-2 的結(jié)果是不正確的，因?yàn)槠浣Y(jié)果中的第二條元組中“出生地”的值存在候選值“長沙”，該值不對應(yīng)于任何有效的可能性狀態(tài)(即該值不可能被選擇)，因?yàn)樗粷M足選擇條件，而且在“所屬省份”中也沒有其所對應(yīng)的值。此時，表達(dá)式select(vf-join(r，s，(r.Y=s.Y))，Cs)與vf-join(r，select(s，Cs)，(r.Y=s.Y))是不等價的，可以證明，用后者可以獲得正確的結(jié)果。

表10 Q2-1 查詢結(jié)果

表11 Q2-2 查詢結(jié)果

(3)僅考慮作用于屬性Y 上的條件CY，下列查詢表達(dá)式通常是不等價的。

可以證明，查詢表達(dá)式Q3-2 和Q3-3 通常會產(chǎn)生正確的結(jié)果。

(4)僅考慮作用于屬性Y 和屬性Z 的復(fù)合選擇條件(CYand CZ)，下列表達(dá)式通常也是不等價的，可以證明，表達(dá)式Q4-2 和Q4-3 通常是正確的。

綜上可以看出，在Vague 數(shù)據(jù)庫環(huán)境下，當(dāng)選擇操作和外鍵連接操作進(jìn)行復(fù)合運(yùn)算時，在經(jīng)典數(shù)據(jù)庫環(huán)境下成立的等式(1)不再一直有效。為了保證查詢結(jié)果的正確性(和基于可能性狀態(tài)的查詢結(jié)果保持一致)，應(yīng)該先執(zhí)行選擇操作，再執(zhí)行外鍵連接操作。這就意味著當(dāng)處理不精確值時，必須禁止那些在精確屬性條件下為了提高執(zhí)行效率而進(jìn)行的操作轉(zhuǎn)換。因而，需要為用戶的查詢形式制定一定的規(guī)則，查詢也必須按照相應(yīng)的表達(dá)式進(jìn)行計(jì)算。

4 結(jié)束語

本文基于擴(kuò)展的Vague 關(guān)系數(shù)據(jù)模型，討論了一種Vague 外鍵連接操作的實(shí)現(xiàn)方法，并給出了相關(guān)的外鍵連接計(jì)算公式，該公式可直接對整個Vague 數(shù)據(jù)庫進(jìn)行操作，并滿足性質(zhì)rep(q(T))=q(rep(T))，與基于可能性狀態(tài)的查詢方法相比，該方法的查詢結(jié)果有效且具有較高的執(zhí)行效率。在此基礎(chǔ)上，還對外鍵連接操作與選擇操作進(jìn)行復(fù)合運(yùn)算時所存在的問題及應(yīng)遵循的原則進(jìn)行了討論。

［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 集相似度量的圖像隱寫系統(tǒng)安全性測度［J］.計(jì)算機(jī)學(xué)報，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 數(shù)據(jù)庫的代數(shù)查詢語言［J］.小型微型計(jì)算機(jī)系統(tǒng)，2008，29(10):1893-1899.

［11］趙法信.基于Vague 關(guān)系數(shù)據(jù)模型的除操作研究［J］.計(jì)算機(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.