張林

摘要：現(xiàn)有的基于關(guān)系數(shù)據(jù)模型的商業(yè)數(shù)據(jù)庫采用空值對缺失信息進(jìn)行建模與處理，然而，單一的空值解釋無法體現(xiàn)空值本身的豐富語義。事實上，在相關(guān)研究中空值通常被解釋為‘值未知，‘值不可用以及‘值不存在等。文中主要研究不可用空值的查詢與處理。通過仔細(xì)地觀察和深刻地理解，分別在傳統(tǒng)關(guān)系數(shù)據(jù)庫查詢和模糊數(shù)據(jù)庫查詢中討論不同語義背景和查詢條件下不可用空值的處理和分類。此外，還針對涉及不可用空值的傳統(tǒng)關(guān)系數(shù)據(jù)庫查詢提出選擇運算和差運算算法，這些算法使文中的研究更具實用性。

關(guān)鍵詞：空值；模糊數(shù)據(jù)庫；關(guān)系數(shù)據(jù)庫；查詢；不可用信息

中圖分類號：TP311文獻(xiàn)標(biāo)識：A

Abstract：Null values are used to model missing information in databases，however，the rich semantics of null values cannot be reflected by a single symbol ‘NULL.Actually，null values have been interpreted as ‘Unknown，or ‘Inapplicable，or ‘Not exist，etc.，in related researches.This paper mainly deals with the querying with such null values，especially null values representing for inapplicable information.Through carefully observation and deeply understanding，different types of inapplicable values under different contexts and querying criterions are discussed and classified in traditional database querying and fuzzy database querying respectively.Furthermore，the selection operation and the difference operation algorithms are proposed under traditional databases environment.These algorithms make the research more practical.

Key words：null values；fuzzy database；relational database；querying；inapplicable information.

1引言

現(xiàn)實世界充滿不完全信息，如：模糊信息、不精確信息、不確定性信息和缺失信息等[16]。數(shù)據(jù)庫是對現(xiàn)實世界的模擬，因此必須考慮對不完全信息的處理。傳統(tǒng)的處理方法分為三個層次：數(shù)據(jù)建模、數(shù)據(jù)庫查詢或二者兼有[2]。隨著模糊集理論[1]及相關(guān)可能性理論[3][4] 的提出，一些學(xué)者提出了‘模糊方法，并產(chǎn)生了模糊數(shù)據(jù)庫[5][11][17]和模糊查詢[6][7][18]的概念。

不完全信息在傳統(tǒng)關(guān)系數(shù)據(jù)模型中的行為已在相關(guān)研究中被廣泛強調(diào)和持續(xù)探索。本文主要處理缺失信息的語義探索及相關(guān)查詢處理。采用一個獨一無二的符號‘NULL（稱之為空值）表示數(shù)據(jù)庫中的缺失值是最常用的處理缺失信息方法[2]。盡管引入空值極大的提升了數(shù)據(jù)庫的查詢和維護(hù)性能，數(shù)據(jù)庫設(shè)計人員必須考慮空值給數(shù)據(jù)庫操縱和查詢中帶來的影響。

為了捕獲和形式化地描述空值在關(guān)系數(shù)據(jù)庫中的語義與行為，Codd基于三值邏輯拓展了關(guān)系演算[2][8]。文獻(xiàn)[10]提出了一個四值邏輯（4VL）模型，包含了兩種類型的空值：“值缺失但可用”和“值缺失且不可用”。文獻(xiàn)[12]提出了一種基于標(biāo)記空值的方法，通過使用變量表示空值，不同的變量可以對空值加以區(qū)分。

本文后續(xù)章節(jié)安排如下：第2節(jié)，介紹和討論當(dāng)前常規(guī)數(shù)據(jù)庫和模糊數(shù)據(jù)庫的空值處理方法；第3節(jié)提出新方法處理傳統(tǒng)數(shù)據(jù)庫查詢和模糊數(shù)據(jù)庫查詢中的不可用信息，并在前面工作的基礎(chǔ)上提出選擇運算和差運算的算法以實現(xiàn)傳統(tǒng)關(guān)系數(shù)據(jù)庫不可用信息的查詢處理。最后，本文的總結(jié)、相關(guān)工作的介紹和對作者未來研究的展望。

2相關(guān)背景和研究

要討論空值的語義，了解缺失信息出現(xiàn)的原因至關(guān)重要。Codd在文獻(xiàn)[2]中介紹了信息缺失的兩種主要途徑：

數(shù)據(jù)對于用戶是未知的，但是數(shù)據(jù)是可用的，在未來的任一時刻可能被已知值代替；

數(shù)據(jù)所代表的屬性對于特定的實體是無效的，從而導(dǎo)致數(shù)據(jù)缺失。

表1是對上述兩種情形的例證。表1是一個鳥類信息表，每種鳥類擁有一個屬性—飛行速度。注意到，表1中的鷹隼和企鵝的飛行速度都以空值填充。然而，造成它們飛行速度屬性數(shù)據(jù)缺失的原因并不相同。情形一：由于鷹隼的飛行速度待觀察或由于相關(guān)工作人員還沒有錄入鷹隼的飛行速度，導(dǎo)致鷹隼的飛行速度暫時被空值代替；情形二：與鷹隼不同，企鵝雖然屬于鳥類，但它并不會飛行，因此企鵝的飛行速度用空值代替恰恰說明飛行速度屬性對企鵝不適用。

21傳統(tǒng)方法

為了對不同缺失信息進(jìn)行區(qū)分，Codd在文獻(xiàn)[10]中提出將缺失信息分為兩種，一種表示“值存在但未知”（Unknown）；另一種表示“值未定義”或“值不存在”（Value not defined）。在一些形式化數(shù)據(jù)庫模型定義中，用一個基礎(chǔ)符號‘⊥表示空值[13][14]，但這并不足夠?？罩低ǔ１徽J(rèn)為是域獨立的，例如，一個缺失的字符型數(shù)據(jù)與一個缺失的整型數(shù)據(jù)，盡管它們都以空值填充，但在將來缺失的字符型數(shù)據(jù)只能被字符型數(shù)據(jù)所替代，缺失的整型數(shù)據(jù)只能被整型數(shù)據(jù)填充。因此，至少在域和屬性定義中，空值所替代的缺失數(shù)據(jù)的數(shù)據(jù)類型是無法忽視的。endprint

多值邏輯被用來定義空值在數(shù)據(jù)庫查詢和操縱中的影響[15]。根據(jù)考慮的空值語義劃分，多值邏輯可以分為三值邏輯[2]和四值邏輯[10]。在四值邏輯中，真值包括T （真），F(xiàn) （假），⊥U （未知）和⊥I （不可用）。與四值邏輯相比，三值邏輯將后兩種真值結(jié)合起來，及⊥U/I，表示值未知或不可用。

使用多值邏輯雖然給數(shù)據(jù)庫設(shè)計與維護(hù)帶來便利，但對于某些查詢，它不能夠產(chǎn)生正確結(jié)果[16]，例如，一些涉及到重言式的查詢[17]。使用多值邏輯會導(dǎo)致不矛盾律和排中律失效[16]，例如，在使用真值T、F和⊥U/I的Kleene三值邏輯系統(tǒng)中[16]，⊥U/I

∨（⊥U/I）=⊥U/I≠T， ⊥U/I∧（⊥U/I）=⊥U/I

≠F。多值邏輯的使用還可能導(dǎo)致真值的函數(shù)性問題：無法通過計算子命題的真值得到命題的真值。事實上，‘Unknown的空值解釋代表了命題真值的不確定性—命題可能為真也可能為假，這種不確定性與多值邏輯想體現(xiàn)的多值性是不同的概念[20]。這些觀察解釋了Date關(guān)于空值使用的一些批判[19]。盡管理解了空值給數(shù)據(jù)庫設(shè)計與維護(hù)帶來的問題，空值的存在依然必要，要避免這些問題，需要一個合適的方法處理不可用空值。

22‘模糊方法

模糊數(shù)據(jù)庫與傳統(tǒng)數(shù)據(jù)庫處理空值的方法不同。在幾乎所有的模糊數(shù)據(jù)庫模型中，只存在一種空值—不可用空值，因為‘Unknown型空值可以用可能性分布進(jìn)行建模[3]。

文獻(xiàn)[15]提出一種基于Kleene三值邏輯的方法，將真值分為：T （真），F(xiàn) （假）和⊥I （不可用）。通過對真值建立可能性分布，可以得到“拓展的可能性真值”（Extended possibilistic truth values），下面用EPTV表示。EPTV是對“可能性真值”（Possibilistic truth values）[20][21]，即PTV的拓展。設(shè)命題P，EPTVt⌒（P）的定義為：

t⌒（P）={（T，μT），（F，μF），（⊥I，μ⊥I）}

μT，μF和μU/I為各自真值的可能性分布程度，取值范圍為[0，1]。EPTV可以表示查詢滿足性[21]，還可以處理查詢條件求值過程中遇到的不可用信息[22]。然而，使用特殊符號來表示不可用空值同樣會導(dǎo)致不矛盾律和排中律失效，例如：

{（T，0），（F，0），（⊥I，1）}∧{（T，0），（F，0），（⊥I，1）}={（T，0），（F，0），（⊥I，1）}∧{（T，0），（F，0），（⊥I，1）}{（T，0），（F，0），（⊥I，1）}≠{（T，0），（F，1），（⊥I，0）}。

命題P的PTV定義為t*（P）={（T，μT），（F，μF）}，其中μT和μF為0或1。注意到上述問題依然存在，例如，當(dāng)t*（P）={（T，1），（F，1）}=UNK時（假設(shè)UNK表示‘Unknown），t*（P∧P）=UNK≠F，且t*（P∨P）=UNK≠T。與EPTV相比，PTV存在特殊情況：對于t*（P∨P），μT=1；對于t*（P∧P），μF=1。因此，本文將采用PTV來處理模糊數(shù)據(jù)庫查詢滿足性問題。使用PTV會導(dǎo)致某些不可用信息在查詢條件求值時丟失[16]，因此如何處理模糊數(shù)據(jù)庫查詢中的不可用信息并確保查詢結(jié)果的語義正確是作者必須面對和解決的問題。

3不可用信息的查詢處理

數(shù)據(jù)庫中某些屬性對于某些記錄可能不適用。如表1中，屬性FLYSPEED對于企鵝是不適用的，因為企鵝不會飛；表2中，某學(xué)生的屬性SCORE可能不適用，由于考試未發(fā)生；表3中，對于男員工，PREGNANT屬性將不適用。

注意到，不可用信息（Inapplicable information）與未知信息（Unknown information）不同，例如，表2中，張三和李四的成績都是NULL，但它們的含義不同。李四參加了考試，由于成績未登入或其它原因，導(dǎo)致暫時以NULL替代。由此可知，不可用信息與未知信息在數(shù)據(jù)表示本身就存在差異。當(dāng)處理涉及這些信息的查詢時，應(yīng)該考慮到它們的差異，并在查詢結(jié)果中體現(xiàn)?，F(xiàn)有的數(shù)據(jù)庫查詢機制中認(rèn)為，當(dāng)用戶對數(shù)據(jù)庫系統(tǒng)提出一個查詢，對于用戶的問題（“數(shù)據(jù)庫中的記錄是否滿足查詢？”）的可能結(jié)果為：‘yes，‘no和‘maybe，而不是‘inapplicable。此外，一條記錄的查詢求值結(jié)果只能是滿足（部分）或不滿足，因此滿足度本身不會是不可用的。

盡管查詢結(jié)果的滿足度永遠(yuǎn)不會不可用，也不應(yīng)放棄使用空值，畢竟，與什么都不知道的情況相比，能夠了解信息是不可用的情況顯然更好。一些學(xué)者認(rèn)為，必須通過對數(shù)據(jù)庫模型進(jìn)行優(yōu)化以盡可能避免不可用信息[16][23]，但這并不合適—涉及不可用信息的查詢依然給數(shù)據(jù)庫用戶帶來問題，而用戶甚至不會意識到不可用信息的存在。

31傳統(tǒng)數(shù)據(jù)庫查詢

在傳統(tǒng)數(shù)據(jù)庫中，查詢結(jié)果是滿足條件求值記錄的集合（這里不考慮多重集合）?！甀napplicable被當(dāng)作‘Unknown以‘NULL表示。含‘NULL的元組的條件求值結(jié)果為F，除非使用一些特殊關(guān)鍵字如SQL中的‘IS NULL。顯然，這并非是最好的處理方法，有時，可以用一些可用的值來滿足查詢條件求值。

為了處理空值豐富的語義，本文采用一種標(biāo)記空值（Marked NULL Value）的方法[12]，使用⊥U表示‘Unknown空值。對于‘Inapplicable空值，我們進(jìn)一步細(xì)分，下面是不同情形：

⊥I，0可以用來表示查詢條件求值中語義等價于‘0的不可用空值，例如表1中企鵝的FLYSPEED屬性的值；

⊥I，U可以用來表示查詢條件求值中語義等價于‘Unknown（⊥U）的不可用空值，如表2中學(xué)生李四的屬性SCORE的值；endprint

⊥I，F(xiàn)可以用來表示查詢條件求值結(jié)果等價于‘F（假）的不可用空值，如表3中男性雇員的屬性PREGNANT的值。

基于此，作者提出處理不同語義不可用空值的選擇運算算法如例1所示。通過使用該算法，可以得到最接近用戶查詢目的的結(jié)果，并且可以避免查詢結(jié)果的非直覺性問題[23][24]。該算法的時間復(fù)雜度為O（n），其中n是關(guān)系R中的元組數(shù)。

通過例1的算法，對于表1的查詢：

SELECT BIRDKINDFROM BIRDWHERE FLYSPEED<50.0

可以得到結(jié)果集（企鵝，貓頭鷹）。與現(xiàn)有數(shù)據(jù)庫查詢結(jié)果（只有“貓頭鷹”）相比，結(jié)果中有“企鵝”顯然更符合實際查詢的期望。

此外，下面還提出了處理不同語義不可用空值的差運算算法，如例2所示。它的時間復(fù)雜度為O（kmn），其中k是關(guān)系R的屬性數(shù)，m、n分別是關(guān)系R和關(guān)系S的元組數(shù)。Pi和Qj分別是關(guān)系R和關(guān)系S的第i個和第j個元組。注意到，算法EqualD最先在文獻(xiàn)[25]中被提出，這里用于實現(xiàn)全元組[17]的等價差運算。符號‘表示兩個全元組是相容的，符號‘表示兩個全元組是等價的；顯然，符號‘和符號‘分別表示兩個全元組不相容和不等價。等價和相容的概念源自于文獻(xiàn)[26]，在此不做贅述。

例2處理不可用空值的差運算算法

至此，文中考慮并提出了傳統(tǒng)關(guān)系型數(shù)據(jù)庫處理不可用空值的選擇運算和差運算算法，其它的一些關(guān)系運算如：并運算、笛卡兒積和投影運算等與空值無關(guān)，它們的運算規(guī)則與傳統(tǒng)關(guān)系數(shù)據(jù)庫中相應(yīng)運算相同，在此不再贅述。

32模糊數(shù)據(jù)庫查詢

與傳統(tǒng)的數(shù)據(jù)庫查詢比（滿足度為s∈[0，1]） ，PTV的未知模型求值結(jié)果t*（P）={（T，1），（F，1）}，或部分未知模型的求值結(jié)果t*（P）={（T，1），（F，0.5）}在處理查詢滿足度問題時，顯然具有優(yōu)勢。因此，PTV可以輕松地處理單一 ‘Unknown型空值的數(shù)據(jù)庫查詢（采用域?qū)傩缘目赡苄苑植迹Ｈ欢?，如?節(jié)所述，模糊數(shù)據(jù)庫依然需要一個特殊符號處理不可用空值，否則將導(dǎo)致所有涉及不可用空值的查詢求值為假，PTV表示為t*（P）={（T，0），（F，1）}。

因此，與3.1節(jié)類似，這里采用基于標(biāo)記的空值來表示不可用空值。下面是不同語義情境下，處理不可用空值的實例：

⊥I，0可以用來表示查詢條件求值中語義等價于‘0的不可用空值，例如若對表1中企鵝的FLYSPEED屬性作模糊查詢“FLYSPEED < ‘V” （‘V表示一個可能存在的速度范圍，如：大約20KM/H），采用PTV的求值結(jié)果為t*（P）={（T，1），（F，0）}，也就是真。若模糊查詢“FLYSPEED > ‘V”， PTV的求值結(jié)果為t*（P）={（T，0），（F，1）}，也就是假；

⊥I，U可以用來表示查詢條件求值中語義等價于‘Unknown（⊥U）的不可用空值，如若對表2作模糊查詢“SCORE = ‘HIGH”（‘HIGH表示一個可能地成績范圍，如：大約90分），對于張三的成績，若不考慮類似“IS NULL”這類求值，采用PTV的求值結(jié)果為t*（P）={（T，1），（F，1）}，也就是未知，表示不確定相關(guān)人員的成績是否滿足該查詢；

⊥I，F(xiàn)可以用來表示查詢條件求值結(jié)果等價于‘F（假）的不可用空值，如若對表3作條件為“PREGNANT= ‘F” 的查詢，對于男性雇員，采用PTV的求值結(jié)果為t*（P）={（T，1），（F，0）}，也就是真。如果查詢條件改為“PREGNANT= ‘T”，則對于男性雇員，采用PTV的求值結(jié)果為t*（P）={（T，0），（F，1）}，也就是假。

注意到，這些基于標(biāo)記的不可用空值的求值結(jié)果并不是一成不變的，它們依賴于不同的語義背景和查詢條件。

4結(jié)束語

本文提出了一種新的方法處理數(shù)據(jù)庫中的不可用信息。文中展示了基于標(biāo)記的空值可以用來獲取語義正確的查詢結(jié)果，即使用戶沒有意識到不可用信息的存在?？罩挡煌摹畼?biāo)記可以用來表示不可用信息在當(dāng)前語義環(huán)境下與之等價的域值。與傳統(tǒng)的盡可能避免對不可用信息處理的方法不同，文中基于不同語義背景和查詢條件，對不可用信息進(jìn)行假設(shè)和處理，并在傳統(tǒng)常規(guī)數(shù)據(jù)庫背景下提出了處理不可用信息的選則運算和差運算算法。

本文只考慮不可用信息在理想狀態(tài)下如何進(jìn)行分類、標(biāo)記。然而，在實際應(yīng)用中，如何自動化地識別不可用信息并對其加以區(qū)分、標(biāo)記為語義等價的域值，是一個巨大的挑戰(zhàn)，這將是作者今后研究的重點。

參考文獻(xiàn)

[1]ZADEH L A.“Fuzzy Sets，”[J].Information and Control，1978，8（3）：3-28.

[2]CODD E F.“Missing information （applicable and inapplicable） in relational databases，”[J].ACM SIGMOD Record，1986，15（4）：53-78.

[3]DUBOIS D，PRADE H，“Possibility Theory，”[M].Plenum，New York，1988.

[4]ZADEH L A，“Fuzzy sets as a basis for a theory of possibility，”[J].Fuzzy Sets and Systems，1978，1（1）：3-28.

[5]BORDOGNA G，PASI G.”Recent Issues on Fuzzy Databases，”[M].PhysicaVerlag，Heidelberg，1995.endprint

[6]BOSC P，PIVERT O.“SQLf：A Relational Database Language for Fuzzy Querying，”[J].IEEE Transactions on Fuzzy Systems 1995，3：1-17.

[7]BOSC P，KACPRZYK J.“Fuzziness in Database Management Systems，”[M].PhysicaVerlag，Heidelberg，1995.

[8]CODD E F.“RM/T：Extending the Relatioanl Model to capture more meaning，”[J].ACM Transastions on Database Systems，1979，4（4）.

[9]DE TR G，DE CALUWE R.VERSTRAETE，J.，et al“Conjunctive Aggregation of Extended Possibilistic Truth Values and Flexible Databases Querying，” [J].LNCS，2002，25（22）：344-355.

[10]CODD E F.“More commentary on missing information in relational databases （applicable and inapplicable information），”[J].ACM SIGMOD Record，1987，16（1）：42-50.

[11]DE CALUWE R.“Fuzzy and Uncertain Objectoriented Databases：Concepts and Models，”[J].World Scientific，Singapore，1997.

[12]IMIELISKI T，LIPSKI W.“Incomplete Information in Relational Databases，”[J].Journal of the ACM 1984，31（4）：761-791.

[13]ABITEBOUL S，HULL R.VIANU，V.，“Foundations of databases，”[M].AddisonWesley Publishing Company，1995.

[14]RIEDEL H，SCHOLL M H.“A Formalization of ODMG Queries，”[C].7th Working Conference on Database Semantics，Leysin，Switerland，1997：90-96.

[15]RESCHER N.“ManyValued Logic，”[M].Mc GrawHill，New York，1969.

[16]MATTH T，TR G D.“The Bipolar Semantics of Querying Null Values in Regular and Fuzzy Databases，” Information Processing and Management of Uncertainty in KnowledgeBased Systems[C].Applications.Springer Berlin Heidelberg 2，2010：137-146.

[17]ZANIOLO C.“Database relations with null values，”[J].Journal of Computer & System Sciences，1984，28（1）：142-166.

[18]DUBOIS D，PRADE H.“Possibility Theory，Probability Theory and MultipleValued Logics：A Clarification[J].Annals of Mathematics and Artificial Intelligence，” 2001，32（1-4）：35-66.

[19]DATE C J.“NOT is Not ‘Not！ （notes on threevalued logic and related matters），”[J].AddisonWesley Publishing Company，1990.

[20]DE TR G，DE CALUWE R.“Modelling Uncertainty in Multimedia Database Systems：An Extended Possibilistic Approach，” International Journal of Uncertainty[J].Fuzziness and KnowledgeBased Systems 2003，11（1）：5-22.

[21]DE TR G，DE CALUWE R，PRADE H.“Null Values in Fuzzy Databases，”[J].Journal of Intelligent Information Systems 2008，30（2）：93-114.

[22]PRADE H，TESTEMALE C.“Generalizing Database Relational Algebra for the Treatment of Incomplete or Uncertain Information and Vague Queries.”[J].Information Science，1984，34：115-143.

[23]RUBINSON C，“Nulls，threevalued logic，and ambiguity in SQL：critiquing dates critique，”[J].ACM SigMod Record，2007，36（4）：13-17.

[24]FRANCONI E，TESSARIS S.“On the logic of SQL nulls，”[J].Proceedings of Amw on Foundations of Data Management，2012：114-128.

[25]馬宗民，嚴(yán)麗.含有空值關(guān)系數(shù)據(jù)庫的查詢處理[J].計算機研究與發(fā)展，1995，32（09）：31-36.

[26]郝忠孝，潘玉浩.空值環(huán)境下的數(shù)據(jù)依賴保持條件[J].計算機工程，1989，10（8）：47-53.endprint