基于差分隐私保护技术的高校贫困生认定系统设计

张林

摘要：现有的基于关系数据模型的商业数据库采用空值对缺失信息进行建模与处理，然而，单一的空值解释无法体现空值本身的丰富语义。事实上，在相关研究中空值通常被解释为‘值未知，‘值不可用以及‘值不存在等。文中主要研究不可用空值的查询与处理。通过仔细地观察和深刻地理解，分别在传统关系数据库查询和模糊数据库查询中讨论不同语义背景和查询条件下不可用空值的处理和分类。此外，还针对涉及不可用空值的传统关系数据库查询提出选择运算和差运算算法，这些算法使文中的研究更具实用性。

关键词：空值；模糊数据库；关系数据库；查询；不可用信息

中图分类号：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