泛关系(数据库)

时间：2022-12-20 22:30:01 | 来源：信息时代

时间：2022-12-20 22:30:01 来源：信息时代

    泛关系 : 用户观念上的数据库中的一种特殊关系。在数据库设计时,为了使函数依赖模式不存在弊病,需要对不属于范式的函数依赖模式进行分解,然而分解就会使函数依赖模式的数目增加,函数依赖模式越多,用户使用就越不方便。在存储时按分解后的函数依赖模式存储,在使用时让用户仍把数据库中所有属性的集合想象成是一个整体的关系模式,所有函数依赖都认为是这个关系模式上的函数依赖,所有数据都理解成是这个关系模式上的单一关系中的数据。用户的所有操作也都理解成是对这个单一关系的,这个想象中的单一关系就称为“泛关系”。
“泛关系”的研究是在1976年Bernstein提出泛属性集的观点后开始的。早期的研究工作因为受了泛关系上的元组也不允许有空值这样一个默认的假设的束缚,所以进展并不大。1980年,Honeyman、Lander及Yannakakis开始研究了含空值的泛关系的理论,提出了全投影、泛例、有效模式、元组的淹没、关系的淹没、代表泛例等全新概念,使“泛关系”的研究有了新起色,出现了许多新成果。后来,为了对泛关系进行查询,人们还提出了窗口函数的思想。1982年,Fagin、Mendelzon及Ullman等提出了一种语义结构窗口,这种窗口很适合于查询语义的表达。1983年,Sagiv定义了键依赖,扩展连接及唯一性模式的新概念,并用唯一性模式作为查询的一种窗口。1986年,Maeir等推广了这个结果,允许不是键依赖的函数依赖集形成窗口。
由于泛关系是一种用户观念上想像的数据库,所以它的可用性在历史上曾受到置疑。Kent(1981年)、Atzeni(1982年初)及Parker(1982年初)都发表文章认为泛关系作为一种数据模型是不合适的。1982年10月,Ullman则著文给以反驳。1983年,Kent又两次提出对泛关系的反对意见。同年Ullman又给予反驳。有趣的是关系数据库理论的创始人Codd竟然也反对泛关系的思想,1988年他发表文章支持早期对泛关系的那些反对意见。特别还举例说明泛关系领域中无法处理的以下查询: 关系模式R={雇员,城市,仓库},基本语义单位S₁＝{雇员,城市}表示雇员所居住的城市,基本语义单位S₂＝{城市,仓库}表示仓库所在的城市(基本语义单位请见本条目后面的说明)。查:其居住地有一个仓库或多个仓库的雇员。但在同年,Vardi等就给予了反驳,他们给出了基于唯一性模式窗口及语义结构窗口的对这个查询的查询解释。总体来看,现在大多数人还都是认为泛关系理论是适宜的。
泛关系的谓词定义如下:设U是数据库中全部属性的集合,Ω={R,…,R_n}是U上的一个数据库模式(数据库模式请参看关系数据库条目)。S_i＝{A_i1,…,A_it}U, 〈x_i1, …,x_it〉是S_i上的变量元组,P_i是以x_i1,…,x_it为变量的谓词,简称S_i上的谓词,记号P_i(S_i)表示相应的谓词公式。u是对x_i1,…,x_it的一个赋值。若u(x_i1),…,u(x_it)能使
P_i为真,则称u使P_i(S_i)为真。如果这里的每个P_i都不能再分成两个谓词的合取,而且每个S_i都是某个R_j的子集,而〈x_i1,…,x_it〉是整个U上的变量元组,且u使P₁(S₁)∧…∧P_k(S_k)为真,则称〈u(x₁),…,u(x_n)〉为U上的由谓词公式集合P₁(S₁),…,P_k(S_k)决定的一个元组,并称集合{〈u(x₁₎,…,u(x_n)〉|u使P₁(S₁)∧…∧P_k(S_k)为真}为U上由谓词公式集合P₁(S₁),…,P_k(S_k)决定的泛关系。每个S_i都称为基本语义单位,并称Γ={S₁,…,S_k}为U上的语义结构。
若r是U上的一个泛关系,r中允许有空值。XU, 则r在X上的全投影, 记作r[[X]], 是集合{u[X]|u∈r,u在X上没有空值}。例如U={A,B,C,D},U上的泛关系r如表1所示。则r[[AB]]={〈a,b〉}, r[[AC]]={〈a, c〉,〈e,f〉}, r[[BD]]=∅。

表1 一个含空值的泛关系(其中丄表示空值)

A	B	C	D
a	b	c	⊥1
e	⊥2	f	⊥3

如果Ω={R,…,R_n}是u上的一个数据库模式,ω={r₁,…,r_n}是Ω上的一个数据库,而r是U上的一个泛关系,且对每个i都有r[[R_i]]r_i(i=1, …,n),则称r是ω上的一个泛例。若∑是U上的函数依赖集合,ω中的关系都适合∑,而ω的泛例r也适合∑,则称r是ω上适合∑的泛例。如果Ω的每个适合∑的数据库都有适合∑的泛例存在,则称(Ω,∑)为一个有效模式。h是泛关系r中所有值(包括空值)上的映射,满足对所有非空值是恒等映射,若u₁,u₂∈r且h(u₁₎＝u₂,则称u₂淹没u₁。记{h(u)|u∈r}为h(r), 若h(r₁₎h(r₂₎, 则称r₂淹没r₁。 如果r₀是ω的一个适合∑的泛例,而且对任一个ω的适合∑的泛例r都有r淹没r₀,则称r₀是ω的适合∑的代表泛例。显然,若(Ω,∑)不是有效模式,则必有Ω的某个数据库ω没有适合∑的代表泛例,而且同一个ω的所有代表泛例互相淹没。构造代表泛例的方法如下:
设全部属性的集合为U,其上的数据库模式为Ω={R₁,…,R_n},依赖集合为∑,Ω上的适合∑的数据库为ω={r₁,…,r_n}。
对每个r_i中的元组u,我们都用以下方法构造一个U上的元组v。
(1)若A_j∈R_i,则令v[A_j]=u[A_j]。
(2)若A_j∉R_i, 则令v[A_j]=丄_k。
这里,丄_k是一个尚未用到过的空值,所有r_i(i=1,…,n)中的所有元组u都做了以上的处理后,这些构造出来的元组v的集合将是U上的一个含空值的关系,记作r⁽⁰⁾。当然我们也可以把这个r⁽⁰⁾看作是U上的一个造型表,再用∑中的依赖对这个r⁽⁰⁾进行追赶,应用的方法是:若依赖是元组产生依赖,则添加一个新元组; 若依赖是等值产生依赖,则将某两个值(包括空值的情况)代换为同一个值。不过我们要求,当需要代换的两个值中有一个是非空值时,则将另一个空值代换成非空值; 当两个都是空值时,则代换成其中任何一个都可以。而且这种代换是将所有出现该值的地方全代换。每次应用了一个依赖以后都检查一下有没有元组被其他元组淹没,如果有,则删掉被淹没的元组。
追赶的结果可能有两个:
(1)可能需要将两个不同的非空值代换成同一个值,这时代表泛例不存在。
(2)可能一直遇不到(1)中的情况,但再应用∑中的依赖已不能使造型表有改变了。这时,这个最后的造型表就是我们所需要的代表泛例。
将对泛关系的查询转换为对具体真实关系的查询的任务称为泛关系的查询解释。查询解释请见参考文献[1]。