无回路数据库(数据库)

时间：2022-11-29 14:30:01 | 来源：信息时代

时间：2022-11-29 14:30:01 来源：信息时代

    无回路数据库 : 一大类具有很多良好性质的数据库的总称,由于这一大类数据库的数据库模式用超图表示时,超图没有回路,因此特称为无回路数据库。
这一大类数据库又分为α无回路、β无回路及γ无回路3个子类。最初是为了研究泛关系查询没有二义性而被提出的,但研究发现它们还有许多其他良好性质。即人们研究了α无回路超图、闭无回路超图、有弦共形特性、Graham算法、两两一致与整体一致、完全约简、连接树、运行相交特性、单调连接表达式、单调顺序连接表达式、β无回路超图、弱β回路超图、既约边集、无关节集、Graham回路超图、γ无回路超图、弱γ回路超图、不可比较的相交边集、纯回路超图等理论,并证明了直到γ无回路时泛关系查询才能没有二义性。
1982年Fagin,Mendelzon,Ullman等首先提出了无回路数据库的概念。1983年他们又明确地把无回路的数据库超图分为了α无回路、β无回路及γ无回路。γ无回路时泛关系查询才能没有二义性的证明也是他们给出的。在研究过程中人们发现这类数据库还有许多良好的性质。1986年,A.D’Atri及Moscarini还研究了α,β,γ各种无回路数据库的识别方法及设计算法,使无回路数据库的理论研究更臻完整。
设Ω={R,…,R_n}是一个数据库模式,U是所有属性的集合,则称以U中的属性为点,以Ω中的关系模式R_i(i=1,…,n)为超边的超图H=(U,∑)为数据库的超图。
α无回路超图是这样一种超图它的所有块都是平凡的。这里平凡的是指一个集合只包含一个元素,而块是指连通的无关节集的部分边集。
部分边集及关节集的定义如下:
设(N,E)是一个超图,MN,在集合{e∩E|e∈E}中删去是其他元素子集的那些元素后得到的结果记为F,则F就是“由M产生的部分边集”,简称“部分边集”,若存在e₁,e₂∈F,f=e₁∩e₂,而{e-f|e∈F}的连通分量比F的连通分量多,则称f为F的关节集。
α无回路与以下11个性质等价:
(1) H是闭α无回路超图。
(2) H是有弦共形图。
(3) H应用Graham算法成功。
(4)连接依赖⋈Ω等价于一个多值依赖集合。
(5)连接依赖⋈Ω等价于一个无冲突的多值依赖集合。
(6)Ω上的两两一致数据库一定是整体一致数据库。
(7)Ω上的每个数据库都有一个完全约简。
(8)Ω有连接树。
(9)Ω有运行相交特性。
(10)Ω有单调连接表达式。
(11)Ω有单调顺序连接表达式。
在一个超图中若它的每个子超图都是α无回路的,则称它为β无回路的,若有一个子图不是α无回路的,则称它为β回路的。超图中的一个超边序列R₁,…,R_m,R_m+1,其中R₁＝R_m+1,若记X=R₁,…,R_m,R′_i＝R_i-X(i=1,…,m+1),而R₁′,…,R′_m,R′_m+1是一个纯回路,则称这个超边序列是一个β回路。这里纯回路是指R′₁,…,R′_m互不相同,R′_m＝R′_m+1,且对所有1≤i≤m都有R′_i＝R′_i+1≠。
β回路超图的以下5个性质等价:
(1) H是β回路的,当它有一个β回路。
(2) H是β回路的,当它有一个子图不是α无回路的。
(3) H是β回路的,当它有某个非平凡连通的既约边集没有关节集。
(4) H是β回路的,当它有一个弱β回路。
(5) H是β回路的,当它有一个Graham回路。
γ回路是超图H中的一个交替序列S₁,x₁,S₂,x₂,…,S_m,x_m,S_m+1,其中x₁,…,x_m是H中互不相同的点,S₁,…,S_m是H中互不相同的边,S₁＝S_m+1,x_i∈S_i∩S_i+1(i=1,…,m)而且x_i不属于S_i及S_i+1以外的S_j(i=1,…,m-1)。
γ回路的以下四个性质等价:
(1) H是γ回路的,当H有一条γ回路。
(2) H是γ回路的,当H有一条弱γ回路。
(3) H是γ回路的,当H有一条长度为3的γ回路或有一条纯回路。
(4) H是γ回路的,当H有一对相交但不可比较的边E及F,并可推知若H=(U,∑)不是γ回路的(即γ无回路的),则Ω上的连通的顺序连接表达式都是单调顺序连接表达式。
以上这些性质的严格定义及它们彼此等价的完整证明,γ无回路时泛关系查询一定没有二义性的证明。均请见文献[1] 。
对于一个给定的超图H=(N,E),可用一种递归方法来识别它是否是θ无回路的(这里θ∈{α,β,γ})。该方法详见参考文献[1]。
由于各种无回路超图与众多的性质等价,致使它的应用已经超出了解决泛关系查询没有二义性的范畴,所以经常需要设计出指定类型的无回路超图。θ无回路超图的合理的、完全的和独立的设计方法:(这里θ∈{α,β,γ})及合理性、完全性和独立性的严格定义详见参考文献[1]。