关系数据库理论(数据库)

时间：2022-12-25 10:30:01 | 来源：信息时代

时间：2022-12-25 10:30:01 来源：信息时代

    关系数据库理论 : 20世纪70年代初由Codd开创的、目前研究得最深入、应用得最广泛的一种数据库理论。这种数据库理论中已经普及的内容是关系代数、关系演算、函数依赖、键、范式、模式分解、规范化、多值依赖、连接依赖、广义依赖、泛关系、无回路数据库等20世纪70年代及80年代初研究的内容。
数据库的一个主要任务是查询。关系代数及关系演算(包括元组关系演算及域关系演算)是关系数据库查询的理论基础。其中,关系代数及元组关系演算是由Codd在1970年首先提出的。1972年,Codd证明了每个关系代数表达式都可以转化为一个(安全的)元组关系演算(“安全的”请见关系演算),但当时还不能证明每个元组关系演算表达式也都可以转化为一个关系代数。1978年,Pirotte总结了当时已有的关系数据库的各种处置运算,又提出了一种域关系演算,并证明了每个(安全的)元组关系演算的表达式都可转化为域关系演算,而每一个(安全的)域关系演算的表达式又都可以转化为一个关系代数,这样,再加上Codd已证明的每个关系代数表达式都可以转化为(安全的)元组关系演算,就证明了关系代数⇒(安全的)元组关系演算⇒(安全的)域关系演算⇒关系代数, 于是三者完全等价, 这就奠定了关系数据库的查询理论的基础。
除了等价性外,人们对这些运算的语义必要性也从理论上作了研究。1978年,Beck证明了并、差、串接、投影、选择是五个必要运算,其中任何一个都不能用另外四个来表示,而其他运算都能用他们来表示。进一步的研究也发现了这三种关系运算的一些不足之处,例如,不能表示传递闭包,而且还揭示了其他缺欠。这些不足之处在90年代后逐步得到了克服,请详见文献[1]。
数据库的另一个重要理论问题是数据库的存储结构。1970年Codd就提出了关于好的数据库结构的第1范式、第2范式及第3范式的理论,1972年又补充提出Boyce-Codd范式的理论,并且给出了研究范式所需的函数依赖、键、主属性、非主属性、部分依赖、传递依赖等理论概念。证明了按满足这些范式的数据库结构来存储数据将不会有冗余弊、插入弊、修改弊及删除弊。为了将不好的数据库结构转化为好的数据库结构,1976年,Bernstein研究出了将任意一个关系数据库转化为第3范式的无损依赖的分解方法。1979年,Biskup等给出了把任意一个关系数据库分解为第3范式的无损连接、无损依赖的分解方法。同年,Beeri等还解决了关系分解等价性问题。这样就完全地解决了函数依赖情况下好的数据库结构设计的理论问题。
由于函数依赖在解决关系数据库结构优劣方面起着重要的作用,所以对它还做了进一步深入的理论研究。发现有时两个函数依赖集合虽然表面不同,但实际起的作用是一样的,即它们是等价的。为了严格地在理论上定义等价,首先定义了蕴涵。显然,判定蕴涵与等价是非常重要的任务,1974年,Armstrong提出了一种用公理推导蕴涵的方法,给出了一个现在用他的名字命名的Armstrong公理系统。他证明了这个系统是有效的(推导出的都是被蕴涵的)、完备的(被蕴涵的都能被推导出),特别是其完备性证明是非常巧妙的、完美的。这项理论成果使关系数据库理论上了一个新台阶。
20世纪70年代后期,人们发现除了函数依赖外,还有其他一些依赖存在。它们也会对数据库存储的结构的优劣有影响。1976～1978年,Zaniolo、Fagin及Delobel分别独立地提出了多值依赖及第4范式,指出了多值依赖是函数依赖的推广,而对于存在着多值依赖的数据库只有属于第4范式的数据库结构才没有弊病。对多值依赖的研究发现,它也存在着蕴涵及等价等问题。受函数依赖的启发,在多值依赖理论研究的一开始,Beeri就给出了有效完备的公理系统。而且同时,Beeri(1977年)还发现多值依赖存在着一种依赖基。依赖基的理论研究加深了人们对多值依赖的认识。在实际问题中,有很多场合中多值依赖并不是对整个关系模式的,而只是对它的一个子集的。而且在一定意义上说,后者比前者出现得更多,后者被称为是嵌入的多值依赖。Fagin(1977年)、Delobel(1978年)、Tanaka(1978年)等研究了嵌入的多值依赖的相关理论问题,取得了很多理论成果。但是,在研究嵌入多值依赖的推导公理系统时却发现,无论如何也给不出完备的公理系统。1982年,Sagiv及Walecka提出了一种子集依赖,借助子集依赖他们证明了嵌入的多值依赖不存在完备的公理系统。
多值依赖只能反映两个关系的无损连接情况,而实际问题中有很多场合是要考虑三个以上关系的无损连接情况。于是在1979年,Rissanen提出了连接依赖。同年,Fagin提出了第5范式,证明了一个存在着连接依赖的数据库只有属于第5范式才能在使用时没有弊病。对连接依赖的公理系统的研究比较困难。1978年,Fagin等证明了完全连接依赖的公理系统尚不完备,即有些蕴涵的连接依赖还不能从公理推出。他们定义了一种增广完全连接依赖,证明了有一些被连接依赖集合蕴涵的连接依赖必须先从依赖集合推出某些增广连接依赖,然后由这些增广连接依赖再推出这个连接依赖。而公理系统只能对增广连接依赖才是完备的(参见连接依赖)。
为了对函数依赖、多值依赖、嵌入的多值依赖、子集依赖、完全连接依赖、嵌入的连接依赖等这么多种类型的依赖能有一种统一的方法进行研究与处理,1980～1981年,Beeri、Vardi、Paredaens、Ullman等人分别独立地提出了广义依赖的概念。广义依赖分为等值产生依赖及元组产生依赖。它们包括了以上所有类型的依赖并且使很多处理任务(例如追赶算法、蕴涵判定等)有了统一、一致的形式。广义依赖是现在通用的名称,1980年,Fagin及Yannakakis等还提出过蕴涵依赖及代数依赖等,也都是为了解决各种依赖的统一及推广问题。以上这些研究的成功扩大了关系数据库理论的覆盖面。
各种依赖模式的规范化都是将不符合范式要求的关系模式或各种依赖模式进行分解,使分解后的关系模式或各种依赖模式能满足范式的要求。然而,这样的分解将使关系模式或各种依赖模式的个数增加,这样用户使用时感到不便。为了解决这个问题,人们提出了存储时按分解后的模式存储,使用时(指查询、插入、修改、删除)仍让用户想像成是对一个整体关系的思想,这种想像中的关系被称为“泛关系”。“泛关系”的理论解决了数据库结构没有弊病与用户使用方便性之间的矛盾。早在1976年,Bernstein就已经意识到了这样做的好处。他提出了从泛属性集的观点出发进行数据库模式的设计问题。国际上公认他的这个思想意识就是泛关系研究的开始。不过早期的研究工作进展并不大,因为人们受到泛关系上的元组也不允许有空值这样一个默认的假设的束缚。如果把所有属性看成一个关系模式不进行分解,一般它将是不属于第3范式(或BC范式)的。因此,它有插入弊。这样一些元组完全可能在某些属性上还没有值。所以去掉泛关系上的元组也不允许有空值的限制是势在必行了。1980年,Honeyman、Lander及Yannakakis研究了含空值的泛关系的理论,提出了全投影、泛例、有效模式、元组的淹没、关系的淹没、代表泛例等全新概念。为了对泛关系进行查询,人们还提出了窗口函数的思想。1983年,Sagiv定义了键依赖、扩展连接及唯一性模式的新概念,并用唯一性模式作为泛关系查询的一种窗口。1986年,Maeir等推广了这个结果,允许不是键依赖的函数依赖集形成窗口。1982年,Fagin、Mendelzon及Ullman还提出了一种语义结构窗口,这种窗口更适合于泛关系查询语义的表达。关系数据库理论的发展也不是一帆风顺的,泛关系的有关理论从它出现那时起就有反对意见。1981～1982年初,W.Kent、Atzeni及Parker都发表文章认为泛关系作为一种数据模型是不合适的。1982年10月,Ullman则著文给予反驳。1983年,Kent又两次提出对泛关系的反对意见。同年,Ullman又给予反驳。连关系数据库理论的创始人Codd也反对泛关系的思想,1988年,他发表文章支持早期对泛关系的那些反对意见。现在,大多数人还都认为泛关系理论是适宜的。
泛关系理论解决了用户使用的方便性与规范化必须对模式进行分解之间的矛盾。但随着研究的深入,人们发现有时不论用哪种窗口进行对查询的解释,都可能出现有二义性。而这种二义性是由于分解后的数据库结构对应的超图有回路引起的。1982年,Fagin、Mendelzon、Ullman等提出了无回路数据库的概念。1983年,明确地把无回路超图分为α无回路、β无回路及γ无回路,证明了数据库有许多性质与它们等价。1986年,Datri及Moscarini研究了α、β、γ各种无回路数据库的识别方法及设计方法。
20世纪90年代以后,关系数据库理论更是蓬勃发展,它逐渐冲出了原有的框架,把以前偶尔研究的类型,局部获取的思想都发展成了系统的理论,把以前认为特殊的、特异的关系数据库变成了正常研究的对象。这使关系数据库理论涉及的范围进一步扩大,包括的体系更加丰富。现在的内容已是早期内容的十几倍,甚至是几十倍。例如,偏序关系数据库、时态关系数据库、空值关系数据库、概率关系数据库、对象关系数据库、Fuzzy关系数据库、粗糙关系数据库、动态关系数据库等都已形成了系统的理论,这些现在被称为非经典关系数据库理论,其成果见参考文献[1]。
进入21世纪后,在关系数据库理论的指导下,关系数据库的应用范围有了更加迅猛的增长。而实践范围的扩大必将又进一步促进理论的发展。关系数据库理论定将发展成一门具有独立体系、具有宝贵价值、具有众多璀璨成果、指导千百万人实践需求的重要学科。