时间：2022-12-25 08:30:01 | 来源：信息时代
时间：2022-12-25 08:30:01 来源：信息时代
广义依赖 : 函数依赖、多值依赖、嵌入的多值依赖、连接依赖、子集依赖等多种数据依赖的共同推广,它可揭示各种依赖的很多共同性质,给出各种依赖都可使用的很多统一方法。
广义依赖的概念是由Beeri、Vardi、Paredaens、Ullman等人于1980～1981年分别独立地提出的。广义依赖又分为等值产生依赖及元组产生依赖。广义依赖的出现使数据库的很多理论(例如追赶算法、蕴涵判定等)有了统一、一致的形式。广义依赖是现在通用的名称,实际上在 1980年,Fagin及Yannakakis等还提出过蕴涵依赖及代数依赖等,也都是为了解决各种依赖的统一及推广问题。以上这些研究的成功使得关系数据库理论的覆盖面更加扩大了。
用表示所有变量的集合, 表示所有常数的集合,R={A1, …,Am}是一个关系模式, R到上的映射v,称为R上的变量元组,这个元组也可用记号〈v[A1],…,v[Am]〉来表示。设v1,…,vn是关系模式R上的n个变量元组,且对任何1≤i1,i2≤n及1≤j1,j2≤m,只要j1≠j2,就有vi1[Aj1]≠vi2[Aj2],即对每个Ai∈R,v[Ai]不与T中Ai以外属性上的变量相同,则称v1,…,vn为R上的一个造型表。若等式x=y中的x,y都是在v1,…,vn中出现的变量,则称记号:v1,…,vn/x=y是一个等值产生依赖。我们把所有变量及所有常数,即∪中的元素统称为“符号”。设V是v1,…,vn中所有变量的集合, Ψ是从V到符号集合∪的映射, 称Ψ为符号映射。如果vi＝〈x1,…,xm〉,则记Ψ(vi)=〈Ψ(x1),…,Ψ(xm)〉。
R是一个关系模式,v1,…,vn/x=y是R上的一个等值产生依赖,r是R上的一个关系(关系请参看关系数据库条目),记T=v1,…,vn,若Ψ能使Ψ(v1)∈r,…,Ψ(vn)∈r,则称Ψ是从T到r的同态映射,若用记号Ψ(T)来表示{Ψ(v1),…,Ψ(vn)},则符号映射Ψ是从T到r的同态映射的充要条件就是Ψ(T)>r。如果对每一个从T到r的同态映射Ψ都有Ψ(x)=Ψ(y)成立,则称r适合等值产生依赖T/x=y。
设T=v1,…,vn是关系模式R上一个造型表。设v是R上的一个变量元组,满足对每个A∈R,v[A]不与T中A以外属性上的变量相同,则称记号v1,…,vn/v,或T/v,为R上的元组产生依赖。称只出现在v中而不出现在T中的变量为独立变量。v中没有独立变量的元组产生依赖称为“完全元组产生依赖”,有独立变量的称为“嵌入的元组产生依赖”。R是一个关系模式,T/v是R上的一个元组产生依赖,r是R上的一个关系,v中非独立变量所对应的属性集合是V0＝{A1,…,Am},若对应每个T到r的同态映射y,都有一个u∈r存在,使得Ψ(A1)＝u[A1],…,Ψ(Am)＝u[Am],则称关系r适合元组产生依赖T/v。
设R是一个关系模式,R上的等值产生依赖及元组产生依赖统称R上的广义依赖。若∑是一个R上广义依赖的集合,则称二元组(R,∑)为一个广义依赖模式。若r是R上的一个关系,且r适合∑中的所有广义依赖,则称r是(R,∑)的一个实例。设(R,∑)是一个广义依赖模式,T/x=y(或T/v)是R上的一个广义依赖,若R上的每个适合∑的关系r,也都适合T/x=y(或T/v),则称∑蕴涵T/x=y(或T/v),记作∑⊧T/x=y(或∑⊧T/v)。 为了给出在广义依赖模式中判定蕴涵的方法(这个方法显然将是判定蕴涵的最普遍的方法),先定义“依赖应用于造型表”的概念:设R是一个关系模式,T是R上的一个造型表。T0/x=y是R上的一个等值产生依赖,将T看作是R上的一个关系(也可称为变量关系),Ψ是从T0到关系T的一个同态映射。称“将T中的Ψ(y)全换成Ψ(x)而得到一个新的造型表T”这件事为: “应用广义依赖T0/x=y到T”并称T是应用T0/x=y于T的结果。
设R是一个关系模式,T是R上的一个造型表,T0/v是R上的一个元组产生依赖,将T看作是R上的一个关系,Ψ使从T0到关系T的一个同态映射,若v中的独立变量是x1,…,xm,将Ψ扩展到这些独立变量上,且满足Ψ(x1),…,Ψ(xm)不与T中任何一个变量相同,而且它们彼此也互不相同,令T`=T∪{Ψ(v)},此过程称为“应用广义依赖T0/v到T上”,并称T`为应用T0/v到T上的结果。显然这时T`仍是R上的一个造型表。
按照这些定义,给出广义依赖集合蕴涵一个等值产生依赖的判定算法及广义依赖集合蕴涵一个元组产生依赖的判定方法如下。这些方法被统称为广义追赶算法,是判定蕴涵的最一般的方法。
判定关系模式R上一个广义依赖集合∑是否蕴涵一个等值产生依赖T/x=y的方法是:
(1)令T1＝T及i=1。
(2)对Ti进行检查,查看是否所有x,y位置上的符号都已换成了相同的符号,若是,则∑蕴涵T/x=y,并称此时为成功的追赶; 否则执行步骤3。
(3)应用∑中的各个依赖于Ti,若应用某一个不能使Ti有改变,则再应用下一个,直到有一个∑中的依赖应用于Ti后能使Ti有改变为止,并将此应用的结果记为Ti+1,令i=i+1,转步骤2。若所有∑中的依赖应用于Ti后,都不能使Ti有改变,则∑不蕴涵T/x=y。
判定关系模式R上一个广义依赖集合∑是否蕴涵一个元组产生依赖T/v的方法是:
(1)令T1＝T及i=1。
(2)对Ti进行检查,查看是否存在一行,这一行的非独立变量与v的非独立变量完全相同,若有,∑蕴涵T/v,并称此时为成功的追赶,称该行为目标行; 若没有,则执行步骤(3)。
(3)依次应用∑中的各个依赖于Ti,若应用某一个依赖不能使Ti有改变,则再应用下一个。若所有∑中的依赖应用于Ti后,都不能使Ti有改变,则∑不蕴涵T/v。若能有一个依赖应用后能使Ti有改变,则将此应用的结果记为Ti+1,并令i=i+1,转步骤2。
广义追赶算法,当∑|≠σ且≠∑中含有嵌入的依赖时,有可能无限执行下去,不会结束。不过对于这种不会结束的情况,严格地说已不能成为一种算法,只能作为∑σ的一种特殊形式的指示。 广义依赖的有向无回路图等其他内容详见参考文献[1]。
在线咨询
