基于差分隱私保護技術的高校貧困生認定系統設計

張林

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

關鍵詞：空值；模糊數據庫；關系數據庫；查詢；不可用信息

中圖分類號：TP311文獻標識：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引言

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

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

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

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

2相關背景和研究

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

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

數據所代表的屬性對于特定的實體是無效的，從而導致數據缺失。

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

21傳統方法

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

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

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

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

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

22‘模糊方法

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

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

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

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

{（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。注意到上述問題依然存在，例如，當t*（P）={（T，1），（F，1）}=UNK時（假設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來處理模糊數據庫查詢滿足性問題。使用PTV會導致某些不可用信息在查詢條件求值時丟失[16]，因此如何處理模糊數據庫查詢中的不可用信息并確保查詢結果的語義正確是作者必須面對和解決的問題。

3不可用信息的查詢處理

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

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

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

31傳統數據庫查詢

在傳統數據庫中，查詢結果是滿足條件求值記錄的集合（這里不考慮多重集合）。‘Inapplicable被當作‘Unknown以‘NULL表示。含‘NULL的元組的條件求值結果為F，除非使用一些特殊關鍵字如SQL中的‘IS NULL。顯然，這并非是最好的處理方法，有時，可以用一些可用的值來滿足查詢條件求值。

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

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

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

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

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

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

SELECT BIRDKINDFROM BIRDWHERE FLYSPEED<50.0

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

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

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

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

32模糊數據庫查詢

與傳統的數據庫查詢比（滿足度為s∈[0，1]） ，PTV的未知模型求值結果t*（P）={（T，1），（F，1）}，或部分未知模型的求值結果t*（P）={（T，1），（F，0.5）}在處理查詢滿足度問題時，顯然具有優勢。因此，PTV可以輕松地處理單一 ‘Unknown型空值的數據庫查詢（采用域屬性的可能性分布）。然而，如第2節所述，模糊數據庫依然需要一個特殊符號處理不可用空值，否則將導致所有涉及不可用空值的查詢求值為假，PTV表示為t*（P）={（T，0），（F，1）}。

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

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

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

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

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

4結束語

本文提出了一種新的方法處理數據庫中的不可用信息。文中展示了基于標記的空值可以用來獲取語義正確的查詢結果，即使用戶沒有意識到不可用信息的存在。空值不同的‘標記可以用來表示不可用信息在當前語義環境下與之等價的域值。與傳統的盡可能避免對不可用信息處理的方法不同，文中基于不同語義背景和查詢條件，對不可用信息進行假設和處理，并在傳統常規數據庫背景下提出了處理不可用信息的選則運算和差運算算法。

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

參考文獻

[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]馬宗民，嚴麗.含有空值關系數據庫的查詢處理[J].計算機研究與發展，1995，32（09）：31-36.

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