时间：2022-11-03 10:30:02 | 来源：信息时代
时间：2022-11-03 10:30:02 来源：信息时代
模式分解 : 将一个关系模式或函数依赖模式分为几个更小的关系模式或函数依赖模式,并且原模式上的关系也通过投影分为几个更小的关系的理论与方法。
模式分解主要研究怎样的分解能够使分解后的关系连接后仍是原关系(这种分解称为无损连接的分解)以及怎样的分解能够使分解后的关系仍保持原关系的全部函数依赖(这种分解称为无损依赖的分解)。
对无损连接的分解的研究始于1978年,由Aho、Beeri、Ulman等人提出了最初的追赶算法,用这种算法可测试一个分解是否是无损连接的。1979年,Maier、Mendelzon及Sagiv推广了这个算法。1981年,Googman、Shmueli给出了广义依赖形式的追赶算法。无损依赖分解的测试实际是函数依赖集合间的等价的测试。
模式分解的形式化定义是:
设R是一个关系模式,若R1∪…∪Rn＝U,且i≠j时Ri≠Rj(1≤i,j≤n),则称p={R1,…,Rn}是关系模式R的一个分解。
设(R,∑)是一个函数依赖模式,若p={R1,…,Rn}是R的一个分解, 而∑i＝{X→Y|∑⊧X→Y, 且X∪YR j}(i=1,…,n),则μ={(R1,∑1),…,(Rn,∑n)}是函数依赖模式(R,∑)的一个分解。
若R上的每个关系r, 都有r=r[R1]⋈r[R2]⋈…⋈r[Rn],则称ρ是(R,∑)的无损连接的分解,若∑*＝(R1∪…∪Rn),则称μ是(R,∑)的无损依赖的分解(∑*请参看函数依赖条目)。
(R,∑)及R的一个分解ρ={R1,…,Rn}是否无损连接的分解可用以下方法判定:
首先根据ρ建立一个称为原始造型表的R上的一个关系T0:
T0有n个元组,即T0＝{u1,…,un}。对于R={A1,…,Am},我们令
在线咨询
