差分故障

2024-10-25

差分故障（精选6篇）

差分故障篇1

0引言

伴随着计算机的普及和网络技术的飞速发展, 计算机安全也越来越成为不能忽视的问题。如何实现安全存储、安全处理、安全传输成为保障信息安全的重要课题, 对于现代社会具有重要意义。为了提高信息安全性, 产生了很多实用的方法, 其中利用现代密码对信息进行加密就是一种重要的方法。如何利用密码设计技术设计一种实用、高效的密码方案, 成为信息安全工作的重要环节。与密码设计技术的发展相对应, 密码分析技术也在近几年取得巨大进步, 产生了大量密码分析方法。这些分析方法能够发现现有密码体制存在的安全漏洞, 通过对密码算法的攻击, 提醒密码设计者去弥补这些漏洞, 并提出对密码方案新的要求, 从而推动密码设计技术的发展。差分故障攻击就是其中比较成功的一种分析方法。本文主要介绍差分故障攻击的一般方法和流程, 以及模拟方法和结论。

1 差分故障攻击介绍

差分故障攻击的方法首先是在公钥密码研究中提出来的, 但却是伴随着分组密码的应用而迅速发展的。分组密码以其结构简单, 安全性高, 理论成熟, 无论从硬件实现还是技术基础方面都具有优势, 在目前的网络技术中依然得到广泛的应用, 并且成为密码学研究的热点课题。差分故障分析在对分组密码分析中有着天然的优势, 因而也获得了巨大发展。

差分故障攻击的思想来源于1996年Bell通信实验室的三位学者对基于CRT实现RSA签名算法的故障攻击。在CRYPTO1997上, Biham和Shamir发现了它的潜力和价值, 将故障攻击的思想引入了分组密码, 并成功的攻击了经典分组密码算法DES。为差分故障攻击的发展打开了大门。差分故障攻击源于差分密码分析, 本质上是将密码方案看作一个数学函数, 通过人工导入的故障差分, 得到输出密文与加密密钥之间的联系, 重复进行故障导入, 最终得到密钥信息, 实现对密码的破译。

差分故障攻击实现的过程, 是通过外界手段, 诱导计算机内部发生瞬时故障, 这个故障如果参与了加密过程中, 就是我们所需的输入差分。故障诱导的方法通常有电磁干扰、电压跳变、温度突变等方法, 故障类型通常有比特故障、字节故障和多字节故障的等。随着现代技术的发展, 故障精确导入已成为现实, 故障位置和故障类型都可以控制, 我们只关注故障的应用, 故障导入这一点不作为本文主要内容。

2 差分故障攻击基本方法

下面以分组密码为例, 解释差分故障攻击的方法。

按照现代密码的要求, 密码方案的算法细节是应当被公开的, 密码的安全性完全取决于密钥的保护, 因此, 只要分析出加密主密钥, 就可以攻破密码方案。经典的分组密码通常包括两个重要的组件:S盒和P层。具体分析这两个组件的特性可以发现, S盒是一个非线性组件, 它的输入差分和输出差分之间存在一对多或多对一的非线性关系, 这给我们分析带来可能;而P层为故障差分提供的高效率扩散, 可以分析多个字节信息, 提高了分析的效率。

故障攻击首先要进行合理的假设:

(1) 攻击者拥有权限选择任意一个明文P并采用具体的密码方案进行加密, 得到正确密文C;

(2) 攻击者还能够选择同一组明文P, 在加密过程中某一个位置导入合适类型的随机故障, 当然, 故障的数值是未知的, 得到相应的错误密文C*;

得到了正误密文之后, 就可以得到输出差分.差分故障分析的理论基础, 是利用了下面的公式:

其中, a是S盒中原来的字节, f1为输入差分, f2为输出差分。这样通过已知的输出差分f2和经过对密码函数性质研究得到的输入差分f1 , 利用S盒的非线性性质, 即可推出a的候选值或候选区间。所以分析的关键步骤在于分析具体的密码函数特性, 得到f1的获取方法。不同密码方案, 分析的方法也有细微的不同。根本人之前研究的内容来看, 针对SPN结构密码, 通常通过构造S盒区分器, 例如攻击KLEIN密码;针对Feistel结构密码, 则通过对比不同位置输出差分值, 例如攻击LBLOCK密码。

当我们得到了a的值之后, 通常先对最后一轮加密进行分析, 由于大多数密码最后一轮是子密钥加的过程, 通过以下公式, 可以实现分析:

其中, NAri代表第r轮加密中a的第i个字节数据, NAri代表第r轮加密中子密钥Kr的第i个字节数据, NAri代表第r轮加密后输出Yr的第i个字节数据。式中, NAri是唯一的未知信息, 因而可以被唯一确定。

通过在不同位置多次诱导故障, 可以恢复子密钥的全部信息。经过一轮解密, 同样的方法可以再恢复上一轮的子密钥。这样可以得到多轮子密钥, 再续结合密码的密钥扩展算法, 最终可以逆推出主密钥, 实现对密码算法的攻击。

3 模拟及结果分析

密码方案通常把各组件分开设计, 最终, 再以密码函数将各部分组件整合, 这样, 通过C语言编程可以方便的实现密码方案的模拟, 先分别对各部分组件进行编译, 而后编写主函数。故障导入的过程是通过系统产生随机数的方法, 加入到加密过程中具体的位置。这样通过模拟出密码加密过程, 进一步可以实现密钥恢复, 通过多次循环, 最终得到密钥全部信息。统计恢复一个子密钥信息所需故障个数和恢复全部主密钥信息所需的故障个数, 并结合模拟结果对攻击效率进行评估。

差分故障攻击为攻击者提供了大量的新方法, 并有很大的创新空间。导入故障类型的不同和选取攻击方法的不同, 甚至是采用模拟软件不同, 攻击的结果都不尽相同。比较结果的好坏可以显示出攻击方法的优劣。

以上文中本人已经完成的两个密码方案为例, 实验模拟的结果分别如下:

在KLEIN密码分析过程中, 在各个字节处导入1bit的随机故障, 以高概率平均经过少量几次导入之后, 可以恢复出主密钥。

在BLOCK密码分析过程中, 采用的故障模型是单字节故障, 并攻击一轮扩散, 两次故障以内以高概率恢复成功。

4 结语

通过这两种密码方案的攻击过程, 可以得出, 这两种密码方案对差分故障攻击是不免疫的。除此之外, 很多密码方案都可以用差分故障攻击进行分析, 这证明了差分故障分析的方法在密码分析中是具有现实意义的方法, 同时也给密码设计提出了新要求, 设计抗差分故障攻击的密码方案变得非常有必要。

参考文献

[1]XinJie Zhao, Tao Wang, ShiZe Guo.Fault-propagation Pattern Based DFA on SPN Structure Block Ciphers using Bitwise Permutation, with Application to PRESENT and PRINTcipher.

[2]Gong Z, Nikova S, Law Y-W.A new family of lightweight block ciphers//Proceedings of the RFIDSec 2011.Amherst, Massachusetts, USA, 2012:1-18.

[3]Ruilin Li, Chao Li and Chunye Gong.Differential Fault Analysis on SHACAL-1.

[4]魏悦川, 李琳, 李瑞林, 等.SHACAL-2算法的差分故障攻击[J].电子与信息学报, 2010, 32 (2) :323-328.

[5]李卷孺, 谷大武, 张媛媛.一种针对特定结构SPN密码算法的差分故障攻击doi:10.3969/j.issn.1671-1122.2009.04.017.

[6]刘祥忠分组密码AES-128的差分故障攻击.计算机技术与发展Vol.22 No.9, Sep.2012.

[7]刘上力, 赵劲强, 聂勤务, AES差分故障攻击的建模与分析, 计算机工程, 2010年1月, 第36卷第1期, Vol.36, No.1.

差分故障篇2

带式输送机状态监测与故障诊断的难点在于带式输送机运转时噪声大、载荷重、转速低, 反映其运行状态的信号相对微弱, 不易提取。差分振子方法是微弱信号特征提取方法之一, 是一种可视化的检测方法, 相图变化易于识别, 理论水平要求低, 易于被广大现场技术人员及工人掌握。目前, 该方法已应用在电动机的匝间短路检测、连轧机在线监测与故障诊断等领域中。带式输送机的振动信号信噪比较低, 即使在解调后依然不能清晰地表征出设备故障特征。本文将差分振子方法与Hilbert解调方法有机结合, 利用Hilbert解调对信号做预处理, 然后应用差分振子对信号进行检测, 通过差分振子相图状态的变化实现故障特征的提取。通过对带式输送机减速机的故障分析, 验证了该方法的有效性。

1 差分振子基本原理

差分振子检测是一种可视化、图形化的检测方法, 以差分方程为基础, 输出相图的变化来反映设备的运行状态。差分振子检测系统的数学模型以二维离散系统来构造, 其检测器的构造[1]如下:

式中:a, b, c, d为差分振子的系统参数;p为放大倍数;fe为系统激励频率;fd为待检测频率;fs为输入信号的采样频率;T (k) 为输入信号序列, k=1, 2, …, N, N为输入信号长度。

系统的固有频率为[2]

ω0=arccos[-4βα (1+β) ] (3)

且满足

式中:α=- (a+d) ;β=ad-bc, β>0。

差分振子检测利用图形的变化来对信号进行特征提取。将待检测信号输入差分振子中, 观察差分振子相图的变化, 如果差分振子相图收敛于极环状态, 则表明待检测信号中含有故障特征频率。若差分振子相图收敛于极点状态, 则表明待检测信号中不含有故障特征频率, 说明设备运行状态正常[3]。利用差分振子检测现场采集到的一个信号, 在信号中含有50 Hz的频率成分及噪声, 其时域波形如图1所示。

利用差分振子对采集到的信号进行检测。若检测频率为50Hz, 则差分振子相图收敛于极环状态, 如图2 (a) 所示;若检测频率不是50Hz (如检测频率为55Hz) , 则差分振子相图收敛于极点状态, 如图2 (b) 所示。

从图2可看出, 利用差分振子输出相图的变化可有效检测出信号中所含的故障特征频率。

2 Hilbert解调基本原理

带式输送机在运行时, 引起其振动的激励是多方面的, 如胶带对滚筒产生的拍打现象, 滚筒支撑轴承的缺陷所引起的振动, 不对中所引起的振动等。这些激励相互影响, 形成复杂的调制现象。因此, 当带式输送机出现故障时, 其故障特征是被调制的。Hilbert解调是提取调制信号故障特征的有效工具, 可有效识别出信号中的冲击特征, 从而找到冲击振动的振源, 进而确定设备的故障部位[4]。Hilbert解调的基本原理[5,6]如下所述。

首先, 令一个实信号x (t) 产生一个90°的相移, 从而与原信号构成一个解析信号。x (t) 的Hilbert解调定义为

则解析信号g (t) 的表达式为

解析信号g (t) 的幅值A (t) 与相位Φ (t) 分别为

对A (t) 进行傅里叶变换就可以得到信号解调后的频谱。

3 差分振子在带式输送机故障诊断中的应用

2012年6月, 某矿带式输送机在线监测与故障诊断系统监测到主井带式输送机的一次二号减速机的多个测点的历史趋势出现了不同程度的跃变, 振动值超标报警, 但是该系统并没有给出设备故障部位和故障类型等相关信息。因此, 笔者对该减速机进行了全面的健康状态分析。该减速机共布置5个振动传感器, 如图3所示。

因测点1、测点2、测点3、测点5出现不同程度的振动值超标报警现象, 对以上测点所采集到的数据进行分析, 其时域波形如图4所示。

通过时域特征指标进一步检测该减速机健康状态。测点1、测点2、测点3、测点5的时域特征指标见表1。

从图4可看出, 测点1、测点2、测点3的振动幅值较测点5偏大;从表1可看出, 测点3的峭度、歪度及峰度指标均超出了正常值的范围 (设备正常运行, 峭度值一般小于3.5, 歪度值的绝对值一般小于0.1) , 说明测点3处出现了明显的轴承或齿轮故障征兆, 具体的故障部位及故障类型通过频域特征分析可以确定。而测点1和测点2时域指标均在正常值范围内, 说明测点1和测点2在时域中无故障特征表现。

限于篇幅, 仅对测点3的数据进行分析。主斜井带式输送机的胶带速度为3.5 m/s;齿轮传动比为25.48, Ⅲ轴的支撑轴承内圈故障特征频率为22Hz, 外圈故障频率为14 Hz, 滚动体故障特征频率为6 Hz;Ⅱ轴、Ⅲ轴的齿轮啮合频率为170 Hz, Ⅲ轴的转频为2.47 Hz。应用Hilbert解调与差分振子相结合的方法对测点3的数据进行分析, 其差分振子相图如图5所示。

差分振子的检测频率为22 Hz时, 差分振子输出相图呈现极环状态, 与Ⅲ轴的支撑轴承内圈故障频率相符, 说明该轴承内圈出现缺陷, 并引起了减速机振动值的增大。2012年7月6日更换了该减速机, 事后确认为Ⅲ轴的支撑轴承内圈故障, 验证了差分振子检测方法的有效性。

4 结语

带式输送机的振动是由多种激励源相互作用而产生的调制信号。基于差分振子的带式输送机故障诊断方法采用Hilbert对信号进行解调预处理, 揭示隐含在信号中的设备故障特征, 然后利用差分振子相图的变化实现对设备故障特征的提取。通过对带式输送机减速机的故障分析, 成功地诊断出该减速机Ⅲ轴的支撑轴承内圈故障, 验证了该方法的有效性。

摘要：针对带式输送机运行状态信号微弱而不易提取故障特征的问题, 提出了一种基于差分振子的带式输送机故障诊断方法。该方法采用Hilbert对信号进行解调, 揭示隐含在信号中的设备故障特征, 然后利用差分振子相图的变化实现对故障特征的提取。若信号中含有故障特征, 则差分振子相图收敛于极环状态, 反之则收敛于极点状态。应用结果验证了该方法的有效性。

关键词：带式输送机,故障诊断,差分振子,Hilbert解调

参考文献

[1]胥永刚, 马海龙, 付胜, 等.机电设备早期故障微弱信号的非线性检测方法及工程应用[J].振动工程学报, 2011, 24 (5) :529-538.

[2]马海龙.复杂机电设备微弱特征提取与早期故障诊断方法研究[D].北京:北京工业大学, 2011.

[3]胥永刚, 马海龙, 冯明时, 等.基于差分振子的轴承早期故障可视化检测[J].北京工业大学学报:2012, 38 (7) :980-987.

[4]王聪.基于Hilbert解调及倒谱的齿轮箱点蚀故障诊断研究[J].电力科学与工程, 2011, 27 (3) :36-40.

[5]马波, 魏强, 徐春林, 等.基于Hilbert变换的包络分析及其在滚动轴承故障诊断中的应用[J].北京化工大学学报, 2004, 31 (6) :95-97.

差分故障篇3

滚动轴承是旋转机械设备的重要组成零部件之一，其运行状态的好坏直接关系到旋转设备的运行状态，因此对滚动轴承工作状况进行实时监测和故障诊断的研究越来越受到人们的重视[1]。故障特征提取是故障诊断过程的一个重要环节，同时也是目前制约故障诊断技术发展的主要瓶颈，直接关系到故障诊断的准确率和故障早期预报的可靠性。传统的故障特征提取方法通常是从时域或频域中反映信号的特性，无法同时兼顾信号在时域和频域的局部化特征和全貌。经验模式分解（empirical mode decomposition,EMD）方法[2]可将复杂的多分量信号自适应分解为一系列位于不同频带的本征模态函数（intrinsic mode function,IMF）之和，每一个IMF分量都是具有单一频率成分的波形信号，但EMD算法的频率分辨率有限，对于频率相近的信号，EMD算法很难分离出，会产生模态混叠现象。针对这一问题，文献[3]提出了一种基于微分的经验模式分解（differential-based empirical mode decomposition,DEMD）方法，该方法是对EMD分解算法的改进，在信号进行EMD分解前，对原信号进行微分运算，使信号的能量尽可能地按频率从高到低递减，进而能够有效分辨出不同频率成分，有效抑制模态混叠现象。当轴承发生故障时，故障信号通常以调制的形式出现，因此解调方法就成为了机械故障诊断中一种最为常用的方法[4]，常用的Hilbert变换的包络解调方法存在着误差较大等问题[5]，而Teager提出的能量算子法[6,7,8]具有更高的解调精度，但是，能量算子只适用于单分量的调幅调频信号，而大多数机械故障振动都是多分量的信号，所以一般都是先把信号分解成若干个单分量调幅调频信号，然后进行能量算子解调[9,10,11]。

本文将DEMD和对称差分能量算子解调算法相结合用于振动信号特征的提取，即首先对信号进行DEMD分解，得到若干个本征模态函数分量，然后对每一个分量进行三点对称差分能量算子解调，计算信号的瞬时幅值和瞬时频率，最后利用谱分析得出特征提取结果。

1 微分经验模态分解

DEMD算法在进行EMD处理前先对原始信号进行微分运算，然后再对各阶IMF分量进行积分还原信号。通过对原始信号进行微分，改变了信号中不同频率成分所占比重，增强EMD的频率分解能力，有利于将信号中相近的频率或微弱的高频成分提取出来，进一步改善EMD的模态混叠现象[12]。DEMD算法的步骤如下。

(1）对原信号x0(t）进行一次微分后再进行EMD分解，得到m个IMF分量，利用Hilbert变换解调方法判断分解后的IMF分量是否存在模态混叠现象。

(2）如果存在模态混叠现象，则对一次微分后的信号继续微分，然后进行EMD处理，直到微分n次后得到的xn(t）再进行EMD分解后，得到的m个IMF分量cni(t)(i=1,2，…，m）没有模态混叠现象为止，rn0(t）为分解过程中残余分量。

(3）对各阶IMF分量进行一次积分得

再对各b(n-1)i(t）进行一次EMD分解得

(4)c(n-1)i(t）为原信号x0(t）微分n-1次后的IMF分量，残余分量为

(5）重复步骤（3）～步骤（4），直到n次积分后获得原始信号的各阶IMF分量和残余分量：

信号经过微分处理能够使高频成分在信号中的振幅比重增加，进而使高频成分能量增加。故障信号往往存在高频部分，尤其是故障初期，故障信号的比重很小，很可能淹没于其他信号当中，不利于故障诊断。DEMD分解可以诊断出相对于主信号占比重很小的故障信号的存在，比传统的经验模态分解具有更好的故障识别能力。

2 对称差分能量算子解调方法研究

调频调幅信号

对应的离散信号为

对于信号x(t），能量算子ψ定义为

式（5）中的能量算子针对连续时间信号定义，对于离散时间信号x(n），应用差分代替微分，则能量算子变为

一般来说，调制信号比载波信号变化要慢得多，即。对离散信号x(n）进行非线性算子运算，得

对x(n）的向后差分信号y(n)=x(n)-x(n-1）进行能量算子计算求得ψ（y(n））后，得到信号的幅值a(n）和频率ω（n）的估计值：

传统能量算子解调方法在信号波形光滑度和频率值准确度方面还不尽如人意[13?15]，与Hilbert调制方法一样，瞬时幅值和瞬时频率在端点及突变点产生较大的波动，为此提出了对称差分能量算子解调方法。

对能量算子解调方法改进如下：

首先定义x(n）的差分序列为

为了提高解调结果的准确度，该差分序列就是在原离散信号基础之上进行了平滑处理。则y(n）的差分序列为

将式（10）和式（11）代入式（5）进行能量算子运算，得到改进的算子：

使用传递函数H(z)=z(1+2z1+z2）求解新的能量算子，得到信号x(n）新的幅值和频率估计值：

称该改进方法为对称差分能量算子解调法。

3 仿真分析

无论是能量算子解调还是对称差分能量算子解调，都只适用于单分量的调幅调频信号，而大多数的旋转机械故障振动信号都是多分量的调幅和调频信号，基于此，先采用DEMD方法把一个复杂的信号分解成若干个IMF分量之和，每一个IMF分量都可以是幅度或频率调制的单分量信号，再对每一个IMF分量进行对称差分能量算子解调，得到原始复杂信号的幅值和频率信息。

仿真信号为

仿真信号的波形图见图1，对仿真信号进行DEMD分解，得到图2所示分解结果，对IMF1、IMF2分量分别采用能量算子解调方法提取幅值和频率信息，得到的瞬时幅值和瞬时频率如图3所示。图4所示为采用对称差分能量算子解调法得到的各分量瞬时幅值和瞬时频率。

对比图3、图4可以看出，采用能量算子解调方法得到的瞬时幅值和瞬时频率曲线在两端仍出现波动，而且曲线并不十分光滑，说明在解调过程中产生了误差；经过对称差分能量算子解调得到的瞬时幅值和瞬时频率曲线波动减小，而且曲线波形更加平滑。对得到的信号进行频谱分析，得到包络谱如图5、图6所示，由图5可以看出，在7.816Hz、0.9771Hz和13.68Hz处出现了峰值，这和设定的调幅频率7.5Hz、调幅频率0.5Hz的二倍频和基频15Hz值接近，但是没有提取出调幅调频分量的基频成分（90Hz），由图6a可以看出，采用对称差分能量算子解调后不仅出现了7.816Hz的频率峰值，还出现了89.89Hz的频率峰值，这与调幅频率7.5Hz和基频90Hz接近，误差分别为4.21%和0.12%，图6b中，采用对称差分能量算子解调得到IMF2分量的包络谱在0.9771Hz和14.66Hz出现了峰值，分别与调幅分量的调幅频率0.5Hz的二倍频和基频15Hz值接近，误差为2.29%和2.26%，误差小于能量算子解调得到频率误差。可见，基于DEMD和对称差分能量算子解调算法能够更加准确地提取出振动信号的特征频率。

4 试验研究

本文对美国凯斯西储大学的滚动轴承振动数据进行试验研究及分析，以进一步验证提出的基于DEMD和对称差分能量算子解调方法的有效性。在试验装置中，1.5kW的三相感应电机通过自校准联轴器与1个功率计和1个扭矩传感器相连，最后驱动风机进行运转，电机的负载由风机来调节。将电机轴的轴承作为待测轴承，待测的滚动轴承型号为SKF6205，使用电火花加工技术在轴承上布置了直径为0.1778mm的单点故障。试验中电机的转速n为1750r/min，则转轴基频为29.16Hz，将振动加速度传感器垂直固定在感应电机输出轴支撑轴承上方的机壳上进行数据采集，采样频率为12kHz，经过计算，滚动球轴承的内圈故障特征频率为157.94Hz。采集轴承内圈故障状态下的振动信号，信号时域波形如图7所示，其包络谱如图8所示，图中只在54.69Hz处存在明显谱线，这和计算得到的转轴基频的二倍频（58.32Hz）接近，内圈故障频率和其二倍频均被淹没在其他频率信号中，不能被清晰地提取出来，故需对故障信号进行近一步处理。对原信号进行小波软阈值去噪处理，分解层数取5，阈值规则选择rigrsure规则。对消噪后的信号进行DEMD分解，图9中列出了分解后的前5个IMF分量。

从图9可以看出，由于随着DEMD分解的逐阶进行，各IMF分量的幅值越来越小，作为研究数据的价值越来越小，所以取幅值相对较大的IMF1和IMF2分量作为研究对象，采用能量算子解调法提取前两个IMF分量的瞬时幅值和瞬时频率，进一步进行频谱分析，其包络谱如图10所示。

从图10包络谱中可以看出，在29.3 Hz、58.59Hz、158.2Hz和319.3Hz处出现了峰值，这和计算得到的转轴基频（29.16Hz）、转轴基频的二倍频（58.32 Hz）、内圈故障的频率（157.94Hz）及其二倍频（315.88Hz）的值接近，都在误差允许范围内，但同时也可以看出，图10中存在着虚假干扰频率，并且这些频率的幅值比较大。对分解后前两个IMF分量进行对称差分能量算子解调，进而得到图11所示的包络谱，与图10相比，不仅在计算所得到的转轴基频的二倍频（58.32Hz）、内圈故障的频率（157.94Hz）及其二倍频（315.88Hz）附近出现了峰值，而且峰值频率得到突出，几乎没有虚假干扰频率，其中只有几个幅值相当小的干扰频率，完全不影响故障诊断结果，故障特征更加明显直观。结合图8原始故障信号的包络谱可以看出，采用能量算子解调和对称差分能量算子解调提取出来的特征频率更加接近真实的故障频率，且采用对称差分能量算子解调得到包络幅值在特征频率29.3 Hz、58.59Hz、158.2Hz和319.3Hz处比能量算子解调大，幅值比重增大，更有利于机械故障特征的提取，从而可以明确地判断轴承内圈产生了故障。

可见，将DEMD与对称差分能量算子解调相结合可以较好地完成对于轴承振动信号的处理和故障特征提取，效果优于基于DEMD的能量算子解调方法。

5 结论

(1）针对滚动轴承振动信号的非平稳特性和其周期性冲击特点，提出了基于DEMD和对称差分能量算子解调的滚动轴承故障诊断方法。

(2）该方法采用DEMD方法对故障轴承振动信号进行分解，从而将复杂的多分量信号分解成多个IMF分量，再对包含主要故障信息的IMF分量进行对称差分能量算子解调来提取信号的瞬时幅值和瞬时频率，进一步进行频谱分析，提取出特征频率，并与基于DEMD能量算子解调方法进行比较。对称差分能量算子解调具有解调精度高等特点，其性能要优于常用的Hilbert变换解调和能量算子解调方法。

(3）数值仿真和试验诊断实例的结果表明，基于DEMD和对称差分能量算子解调方法，能够更加准确地提取出振动信号的特征频率，实现轴承故障有效诊断。

摘要：针对机械故障振动信号多为调制信号的特点,为了更好地提取多分量调幅调频信号的幅值和频率信息,提出了基于微分的经验模式分解(DEMD)与对称差分能量算子相结合的解调方法。利用DEMD算法将原始振动信号进行分解,得到若干个单分量信号;对每一个单分量信号进行三点对称差分能量算子解调,得到各单分量信号的瞬时幅值和瞬时频率,并计算出包络谱。将该方法应用于仿真信号和滚动轴承故障信号的诊断,实验结果表明,该方法能有效地提取机械故障信号的故障特征,实现旋转机械故障诊断。

差分故障篇4

旋转机械是机械设备中主要的驱动装置,其中滚动轴承是最重要的机械零件之一。由于工作环境中存在着强烈的噪声,使得滚动轴承故障诊断的难度增大,如何从复杂含噪的原始信号中及时准确地提取出滚动轴承故障特征,找出故障部位,成为当今滚动轴承故障诊断需要解决的关键问题。

随着滚动轴承应用范围越来越广泛,相继出现了多种信号处理的方法。如孙延奎等[1]提出的小波去噪法,得到了很好的消噪效果。黄等[2]提出的Hilbert-Huang变换法,先将信号进行经验模式分解(EMD),再进行Hilbert谱分析(HSA),这种方法对于非线性非平稳信号具有很好的效果。杨国建等[3,4]的小波分析单子带信号重构改进算法可以利用小波基将整个信号按照频率从高到低准确分解成多层,从而达到在整体上滤波的效果,但无法在局部上进行精确滤波,而赵学智等[6]提出的奇异值差分谱理论却可以实现在局域上精确滤波。

因此本文将小波分析单子带信号重构改进算法和奇异值差分谱理论相结合,提出一种滚动轴承故障诊断新方法。首先从整体上滤波,利用小波分析单子带信号重构改进算法实现不同频段的信号分离。然后对故障特征频率可能存在的某一子带信号使用奇异值差分谱理论进行局部滤波,最终得到降噪后的信号。该方法可以从强烈噪声背景中剥离出故障信号,从而准确地找到滚动轴承的故障特征频率,判断出故障部位,实现诊断功能。

1 问题描述

在实际运行过程中,机械设备的故障一般大多出现在滚动轴承上,而滚动轴承是机械设备中重要的支撑部件,其性能与工况的好坏将直接影响到整个机械设备的工作状态,因此对于滚动轴承的故障研究具有重要的意义。

滚动轴承由内环、外环和滚动体等元件组成,其结构如图1所示。

滚动轴承由于落入异物、润滑不良、内外环倾斜及电蚀等种种原因,会发生磨损、压痕、点蚀、裂纹、表面剥落、破损、胶合、锈蚀以及变色等多种异常现象。当滚动轴承的某一元件存在单一缺损时,由于此缺陷的存在,滚动体旋转时,每遇到此缺陷都将会产生一次冲击,因此对于不同的故障元件将对应着不同的故障特征频率,具体如下:

滚动体缺陷的故障特征频率:

内环缺陷的故障特征频率:

外环缺陷的故障特征频率:

其中D为滚动轴承节圆直径,d为滚动体直径,为接触角,Z为滚动体个数,fo为轴承转速。

因此若能够从滚动轴承振动信号中测得故障频率,再与理论的故障特频率相对应,将能够诊断出发生故障的部位。但在实际工作环境中,干扰源无处不在,用于诊断的故障信号总会携带大量的噪声,造成故障特征分量被湮没,使误诊率增大。我们将小波分析单子带信号重构改进算法和奇异值差分谱理论相结合,给出一种滚动轴承故障诊断新方法。

2 小波分析单子带信号重构改进算法

传统的小波分析单子带信号重构算法是将信号按Mallat分解算法进行分解,得到各尺度上的小波系数,再分别重构至与原始信号相同的尺度[3]。其基本由3步完成:与小波滤波器卷积、隔点采样、隔点插零。隔点采样与隔点插零是两个相反的过程,频率混淆的现象主要是由实际滤波器的非理想截止特性所产生的。于是在改进算法[3]中,将通过小波滤波器后的信号进行了处理。

设信号的采样频率为fs,分解层数为j,具体做法是:对于与低通分解滤波器卷积后的信号进行傅里叶变换,将频率f>fs/2j+1部分谱值置零,再进行快速傅里叶逆变换;对于与高通分解滤波器卷积后的信号进行傅里叶变换,将频率f≤fs/2j+1部分谱值置零,再进行快速傅里叶逆变换。这样就可以将信号的频带依靠小波滤波器连续降半划分到指定尺度,克服频率混淆的缺点。达到整体滤波的目的。设信号的采样频率为2fs,则经小波分析单子带信号重构改进算法处理后的信号各子带的频带范围如表1所示。

在滚动轴承故障诊断中,我们可以利用此改进算法处理输入的滚动轴承信号,将不同频率范围的信号分量划分到不同尺度上,再根据理论故障特征频率,找到故障特征频率可能存在的某一子带,并舍去其他子带信号,达到从整体上滤波的效果。

3 奇异值差分谱理论

引理1[5]:奇异值分解(Singular value decomposition,SVD)是一种正交化方法,对于一个实矩阵A∈Rm×n,不管其行列是否相关,必定存在正交矩阵U(28)(u1,u2,(43),um)∈Rm×m和正交矩阵V(28)(v1,v2,⋅⋅⋅,vn)∈Rn×n,使得:

A=UDVT

式中D(28)(diag(σ1,σ2,⋅⋅⋅,σn),)0或者其转置,这取决于mn,DÎRm×n,0代表零矩阵,q=min(m,n),且有:σ1≥σ2≥⋅⋅⋅≥σq﹥0,它们称为矩阵A的奇异值。

由文献[6]知,利用含噪信号构建的Hankel矩阵,其分解得到的奇异值中,前k个奇异值几乎代表了无噪理想信号,之后的奇异值代表噪声信号,且第k+1个奇异值明显小于第k个奇异值,所以可以利用奇异值差分谱最大峰值对应点的位置找到奇异值的突变点k,实现对有用分量个数的确定。

矩阵A也可以表示成多个矩阵分量之和的形式,如式(1)所示:

由于每个Hankel矩阵均对应着一个信号,则含噪信号也可以表示成多个信号分量之和的形式。因此,利用代表无噪理想信号的前k个奇异值,分别求出相应的k个矩阵,再求出相应的k个信号,将这k个信号进行简单线性叠加,就可以实现由前k个奇异值重构成降噪后的信号,从而达到去噪的目的。

我们可以将滚动轴承故障信号构造Hankel矩阵,利用奇异值差分谱理论除去滚动轴承故障信号中含有的强烈背景噪声,剥离出故障信号。然后求其频谱得到故障特征频率,判断出故障部位,从而实现诊断功能。

4 基于小波分析及奇异值差分谱理论的滚动轴承故障诊断

小波分析单子带信号重构改进算法可以将滚动轴承故障信号的频带连续降半划分到指定尺度,形成一系列子带,实现不同频段的信号分离,再从中挑选出存在有用分量的某一子带信号,这样就可以去除其他频带上的大量干扰信号,实现整体滤波效果,但此算法却无法对某一子带上的信号进行消噪;而SVD差分谱理论却恰恰可以实现对信号的去噪处理,将信号从大量干扰中提取出来。因此,两者的结合可以有效地剔除滚动轴承故障信号中强烈的背景噪声,实现故障特征的提取,达到诊断的目的。该方法的流程图如图2所示。

具体步骤如下:

步骤一:从整体上滤波。选用db10小波滤波器,利用小波分析单子带信号重构改进算法将输入的滚动轴承信号的频带准确地二进划分成一系列子带,实现不同频段的信号分离,然后根据理论滚动轴承故障特征频率,找到故障特征频率可能存在的某一子带。这一步将输入信号中不同的分量信息分解到不同的尺度上,并剔除不需要的分量信息(如不平衡、未校准、松动等引起的振动和部分噪声)所在的尺度,保留有用分量信息(由轴承元件单一缺损引起的故障特征分量)所在的尺度。

步骤二:从局部滤波。利用此子带信号构造Hankel矩阵,对矩阵进行奇异值分解并求出奇异值差分谱,根据奇异值差分谱最大峰值所对应的横坐标,确定有用分量的个数k,用前k个奇异值重构信号,得到降噪后的信号。

步骤三:求得降噪后的信号的频谱,对照理论滚动轴承故障特征频率,确定滚动轴承是否发生故障及具体的故障部位。

5 仿真实验与分析

某设备中的6308轴承出现故障,轴承转速为80r/min,轴承外径D=90mm,内径d=40mm,滚动体个数Z=8,接触角(28)0。根据故障特征频率计算公式,得到表2所示的故障特征频率。

用周期性脉冲信号模拟外环单故障点的振动故障;用频率为100Hz的正弦信号模拟滚动轴承固有频率;用频率为90Hz,140Hz的正弦信号模拟不平衡、未校准、松动等引起的干扰;用高斯白噪声模拟强烈的背景噪声。以采样频率fs=1280对信号进行采样,取N=4096个点,仿真出的滚动轴承故障信号及其频谱如图3所示。

利用小波分析单子带信号重构改进算法将滚动轴承故障信号进行3层分解,二进分成一系列子带,各子带信号及对应的频谱如图4所示。

根据表2中所列出的滚动轴承故障信号的各种故障特征频率,找出故障特征频率有可能存在的子带信号,这里选择a3子带信号作为原信号从整体上滤波后的结果。

利用a3子带信号构建Hankel矩阵并进行奇异值分解,从而求出奇异值差分谱。奇异值曲线及奇异值差分谱曲线如图5(a)所示。为了更利于观察,放大后的图像如图5(b)所示。

从图中可知,奇异值差分谱的最大峰值出现在第3个坐标处,则有用分量个数为3,选择前3个奇异值来重构信号,结果如图6(a)所示。降噪后的信号频谱如图6(b)所示。

从频谱中可以很清楚地看到去噪后信号为45.6250Hz,很接近滚动轴承外环故障频率46.096Hz,因此可以诊断为滚动轴承外环发生了故障,验证了基于小波分析单子带信号重构改进算法和奇异值差分谱理论的滚动轴承故障诊断方法的可行性。

6 结论

小波分析单子带信号重构改进算法可以将原始含噪滚动轴承信号的频带准确地二进划分成一系列子带,实现不同频段的信号分离,再保留故障特征频率可能存在的某一子带,用此算法可以去除其他频带上的大量干扰信号,实现整体滤波。对此子带信号构建hankel矩阵,利用奇异值差分谱理论去噪,可实现从局部上精确滤波且具有很好的降噪效果。结合小波分析单子带信号重构改进算法和奇异值差分谱理论处理原始滚动轴承信号,可以从强烈的背景噪声中剥离出故障信号,能够得到故障特征频率,判断出故障部位。

摘要：针对强烈背景噪声下的滚动轴承故障信号,故障特征频率难以提取的问题,提出了基于小波分析及奇异值差分谱理论的滚动轴承故障诊断。该方法首先从整体上滤波,利用小波分析单子带信号重构改进算法将原始滚动轴承信号的频带准确地二进划分成一系列子带,实现不同频段的信号分离,找到故障特征频率可能存在的某一子带;然后进行局部滤波,主要是利用此子带信号构造Hankel矩阵,根据奇异值差分谱理论进行去噪;最后求其频谱得到滚动轴承的故障特征频率,从而判断出故障部位。仿真实验结果表明,该方法是一种有效的故障诊断方法。

关键词：滚动轴承,小波分析,奇异值差分谱,故障诊断

参考文献

[1]孙延奎.小波分析及其应用[M].北京:机械工业出版社,2005.

[2]于德介,程军圣,杨宇.Hilbert-Huang变换在滚动轴承故障诊断中的应用[J].中国机械工程,2003,14(24):2-3.

[3]杨建国.小波分析及其工程应用[M].北京:机械工业出版社,2005.

[4]何正嘉,訾艳阳,张西宁.现代信号处理及工程应用[M].西安:西安交通大学出版社,2007.

[5]戈卢布·G·H,范洛恩·C·F.袁亚湘,译.矩阵计算[M].北京:科学出版社,2001.

[6]赵学智,叶邦彦,陈统坚.奇异值差分谱理论及其在车床主轴箱故障诊断中的应用[J].机械工程学报,2010,46(1):2-5.

[7]张超,陈建军,徐亚兰.基于EMD分解和奇异值差分谱理论的轴承故障诊断方法[J].振动工程学报,2011,24(5).

[8]Farag K.Omar,A.M.Gaouda.Dynamic wavelet-based toolfor gearbox diagnosis[J].Mechanical Systems and SignalProcessing,2012,26:190-204.

差分故障篇5

在现有的图像运动目标检测[1]方法中,帧差法[2,3]基于图像序列中两帧(或多帧)图像间的差分来实现检测,具有简单、直接、易于现、可连续处理等优点,可较好地适应环境的较大变化;但因其难以有效地检测出对应于运动目标但帧间变化不够明显的像素点,一般难以获得运动目标的完整轮廓[4]。光流法[5]通过估计图像的运动场并合并相似的运动矢量来实现检测,对于摄像机可动的情况其性能较好。但其算法复杂,运算量较大,很难实现对视频流的实时处理;背景差法[6]通过将图像序列和参考背景模型相减来实现检测,可以检测出和运动目标相关的所有像素点(完整地分割出运动对象),因而近年来广受重视和研究。但现有的该类算法普遍对于外界环境的变化(如光照、外来事件等)较为敏感[4]。

将帧差法与背景差法相融合可获得较好的检测性能[6]。本文提出一种基于梯度图像,融合帧间差分和背景差分的运动目标检测新方法。针对真实视频序列的实验结果表明,该方法既简单有效,又具有较强的抗干扰能力,较宽的适应范围,较小的运算量和较好的实时性。

1 基于梯度图像帧间差分和背景差分的运动目标检测新方法

1.1 基本思路与流程

如图1所示,本文方法的特点是基于梯度图像,将帧间差分与背景差分相融合。预先选取一帧作为背景帧,建立各像素点的(混合)高斯模型;再对相邻两帧图像的梯度图像进行差分处理,区分出背景点和变化区域;然后将变化区域与背景帧的对应区域进行模型拟合(差分),区分出显露区(此前被遮挡而今显露的区域)和运动物体;最后对运动物体进行连通性分析和检验,进一步降低噪声以获得无阴影的运动物体。背景模型更新也在此过程中完成:对帧间差分所判定的背景点按一定的规则进行更新;对背景差分所判定的显露区,则以较大的更新率收入到背景帧中;对运动物体对应的区域不进行更新。以下具体加以说明。

1.2 梯度图像生成

帧间差分法的关键是选择适当的分割阈值以区分目标和噪声。固定阈值无法适应情况(信/噪比)和环境的变化,自适应阈值则往往算法复杂。另一方面,图像的梯度不易受亮度变化、量化噪声等的影响,针对梯度图像进行帧间差分可以较小的计算成本较好地提取运动目标。因此,本文利用边缘检测性能较好、计算复杂度较低的Sobel算子[7]提取梯度图像:

$\begin{array}{l} f_{G} (x, y, t) = | f (x, y, t) * Η_{X} | + | f (x, y, t) * Η_{Y} | (1) \\ Η_{X} = \frac{1}{4} [\begin{matrix} 1 & 0 & - 1 \\ 2 & 0 & - 2 \\ 1 & 0 & - 1 \end{matrix}] \\ Η_{Y} = \frac{1}{4} [\begin{matrix} - 1 & - 2 & - 1 \\ 0 & 0 & 0 \\ 1 & 2 & 1 \end{matrix}] (2) \end{array}$

其中,f(x, y, t)为原始灰度图像在(x, y)处的像素点;fG(x, y, t)是在t时刻的近似梯度幅值;Hx、Hy分别是水平、垂直方向上的Sobel算子。

1.3 帧间差分

研究表明序列图像中背景点的帧间差分值服从零均值,方差为σ2的高斯分布N(0, σ2)[7]:

$p (d_{k} | Η_{0}) = \exp [- d_{k}^{2} / (2 σ^{2})] / [\sqrt{2 π} σ] (3)$

其中H0代表(x,y)处像素点是背景的假设,dK代表该像素点的灰度差分值。因此,根据概率统计学中的假设检验“3σ”法则,利用适当设置的阀值T即可滤除背景,检出变化区域:

$F D (x, y, t) = {\begin{matrix} 255 & f_{G} (x, y, t) \geq Τ \\ 0 & f_{G} (x, y, t) < Τ \end{matrix} (4)$

上述思想和方法同样适用于梯度图像的帧间差分[3,7]。为提高自适应性,本文按照式(5)、式(6)实时估计当前帧的背景区域的均方差值σ,按照式(7)选定T值:

$\begin{array}{l} \bar{D} (t) = \frac{1}{A} \sum_{x = 1}^{l} \sum_{y = 1}^{b} D (x, y, t) * δ (F D (x, y, t - 1)) (5) \\ σ = \sqrt{\frac{\sum_{x = 1}^{l} \sum_{y = 1}^{b} (D (x, y, t) - \bar{D} (t))^{2} * δ (F D (x, y, t - 1))}{A}} (6) \\ Τ = α \cdot σ (7) \end{array}$

其中,l、b分别是图像序列的长度、宽度,A是背景区域的面积;一般可令α=3;对于较复杂的场景(如有摆动的树枝,波动的水面等),α可取值4到8。

1.4 自适应混合高斯背景模型[8]

为了适应较为复杂的背景,本文利用混合高斯模型{η1(Xt),…,ηk(Xt),…,ηN(Xt)},为背景中的每个像素点Xt分别建模。其中N为分布模型的总个数,N=3～5(本文N=3);ηk(Xt)={μk(Xt),Dk(Xt)}为第k个高斯分布,μk(Xt)、Dk(Xt)分别对应于Xt的均值、方差。相应地,像素点Xt的概率模型是:

$Ρ (X_{t}) = \sum_{k = 1}^{l} ω_{k} (t) η_{k} (X_{t}) (8)$

其中,ωk(t)是t时刻第k个分布的优先权系数,反映它在最近时段内在模型里出现的频度。

为快速、鲁棒地反映背景的变化,本文采用下列背景更新策略:逐一将每个像素点Xt与混合模型包含的N个分布进行比较,直到找到一个与Xt最匹配的分布,匹配的定义是:

$Μ_{k} (t) = {\begin{matrix} 1 & | X_{t} - μ_{k} (t) | < λ \sqrt{D_{k} (t)} \\ 0 & 其他 \end{matrix} (9)$

其中,λ一般取3～7。然后根据ωk/Dk对这N个分布进行降序排序,并区分背景/前景状态:若前B个状态的累计概率大于TP且 B最小,则认为它们是背景状态;其余状态认作前景:

$B = \underset{b}{a r g m i n} (\sum_{k = 1}^{b} ω_{k} > Τ_{Ρ}) (10)$

若这N个分布与Xt都不匹配,说明Xt是一个新的前景点,则使用一个新的分布η(μ,D)来代替混合模型里优先权系数ωk(t)最小的那个分布,该新分布的均值μ=Xt,方差D取DMAX,优先权系数ω取一个较小的值。对各优先权系数按下式更新:

$ω_{k} (t) = (1 - α) ω_{k} (t) + Μ_{k} (t) k = 1, 2, \dots, Ν (11)$

其中α是学习速率。t时刻各分布的均值、方差分别按式(12)、式(13)进行更新:

$\begin{array}{l} μ_{k} (t) = {\begin{matrix} (1 - ρ) μ_{k} (t - 1) + ρ X_{t} & X_{t} 与第 k 个分布匹配 \\ μ_{k} (t - 1) & 否则 \end{matrix} (12) \\ D_{k} (t) = {\begin{matrix} \begin{array}{l} (1 - ρ) D_{k} (t - 1) + ρ (X_{t} - \\ μ_{k} (t))^{Τ} (X_{t} - μ_{k} (t)) \end{array} & \begin{array}{l} X_{t} 与 \\ 第 k 个分布匹配 \end{array} \\ D_{k} (t - 1) & 否则 \end{matrix} (13) \end{array}$

其中,ρ的定义和估算公式分别如式(14)、式(15)所示:

$\begin{array}{l} ρ = α η (X_{t} | μ_{k} (t), D_{k} (t)) (14) \\ ρ_{k} (t) \approx {\begin{matrix} α / ω_{k} (t) & X_{t} 与第 k 个分布匹配 \\ 0 & 否则 \end{matrix} ］ (15) \end{array}$

2 实验与讨论

利用上述方法,针对实际视频序列进行了多组实验。部分结果如图2、图3所示,反映本文方法可获得较为理想的背景图像和较好的检测效果。更多的实验结果[9]进一步表明,该方法既简单有效,又具有较强的抗干扰能力,较宽的适应范围和较小的运算量。

3 结束语

考虑到帧间差分和背景差分各有其优缺点且可互补,而图像梯度具有突出的抗噪声特性,本文提出了一种基于梯度图像,融合帧间差分和背景差分的运动目标检测新方法,并进行了实验验证。今后将继续研究其DSP实现,以实现视频运动目标的高效、实时检测。

参考文献

[1]Bors A G,Pitas I.Prediction and tracking of moving objectsin image sequences[J].IEEE Trans.on Image Processing,2000,9(8):1441-1445.

[2]Lipton A,Fujiyoshi H,Patil R.Moving target classi-ficationand tracking from real-time video[C].In:Proc.IEEE Work-shop on Applications of Computer Vision,Princeton,NJ,1998:8-14.

[3]Zhao S G,Zhao J,Wang Y,et al.Moving object eetecting us-ing gradient information[C].Three-frame-differencing andConnectivity Testing,AI 2006,LNAI 4304:510-518.

[4]Valera M,Velastin S A.Inteillgent distributed surveillancesystems:a review[J].IEE Proc.Vision Image Signal Pro-cess,2005,152(2):192-204.

[5]Barron J,Fleet D,Beauchemin S.Performance of optical flowtechniques[J].International Journal of Computer Vision,1994,12(1):42-77.

[6]朱明旱,罗大庸,曹倩霞.帧间差分与背景差分相融合的运动目标检测算法[J].计算机测量与控制,2005,13(3):215-217.

[7]William K Pratt.数字图像处理[M].北京:机械工业出版社,2005.

[8]Stauffer C,Grimson W.Adaptive background mixture modelsfor real-time tracking[C].In:Proc IEEE Conference on Com-puter Vision and Pattern Recognition,Colorado,1999:246-252.

SQL差分篇6

结构查询语言SQL, 是关系数据库标准语言, 描述对关系数据库的操作, 或是定义在关系数据库上的运算。差分, 是表达函数变化的数学工具。当前函数值减上一时刻函数值所得的差是向后差分, 下一时刻的函数值减当前函数值所得为向前差分。SQL差分研究变化中的数据库及在数据库上定义的查询。一个查询就是一个函数, 其中用到的表是该函数的自变量, 查询所得结果集是函数值。SQL差分研究数据库变化对查询结果的影响, 以及若把查询视作函数时它的差分的构成法则。

数据仓库的数据收集系统中广泛使用一种称为物化视图 (materialized view) 的机制。物化视图是一种有视图功能的实表, 根据源表的数据计算得到, 但要随着源表数据的变化而变化。有两种方式可实现跟踪:完全重算和增量修改。因完全重算工作量大、耗时多, 故一般都愿意选择后者。增量修改方法即是在视图的当前值基础上, 加上或删除从源表的变化量计算出的视图的变化量。但由于缺少算法, 目前只能处理简单的视图定义, 略为复杂一点的视图定义, 如联接、子查询等, 现有的DBMS中增量修改方法还不能实现。本文的研究就是针对这一需求展开的。

用T表示物化视图的源表 (下划线是矢量符号, T表示由一个或多个表组成的表矢量:T=T1, T2, …, Tn;n>0) , 物化视图S的定义是在T上的一个查询S=Q (T) , 描述从T计算出S的过程, 在SQL中是查询语句。若对T的修改记在一组与T相对应的表dT中, 称为T的差分, 在源表中是T的向后差分, 其中记录有已对T的行所作的增加、删除和修改, 反映了T的当前值的形成过程。对S应作的修改相应地记为dS, 是S (尚未变化) 的向前差分, 藉以把S变成与T的当前值对应的S的当前值。dS理论上应可从dT和T计算出:dS=G (dT, T) , G应可从Q导出。

因此跟踪过程由三步组成:

(1) 在数据源, 当对T作插入、删除和修改时, 用一定的方法生成dT;

(2) 由dT和T计算出dS并送到物化视图所在的系统;

(3) 在物化视图所在的系统用dS修改S。

本文第一节是第一步的一般概念。而第二步, 由dT和T计算dS, 即从Q推导出G, 开创了一个称为SQL差分的广阔的研究领域。对各种不同的Q推导出G的算法, 是后面各节研究的内容。第三步是一个理论上的简单过程, 本文不再研究。

文中所有SQL语句都使用Oracle语法, 均可在Oracle的9i或更高版本上运行。

本文读者只要学过数理逻辑和SQL语言即可。文末所列参考资料清单仅供参考, 其中文献[1]是关于Oracle的SQL语言的, 文献[2]是关于SQL的1992标准的。学习SQL的其他材料还可在网上找到。数理逻辑知识只要有大学离散数学中所学的就可以了, 也可参考文献[3]。阅读本文不需要学过数学中的差分概念, 对此有兴趣的读者只要阅读数学词典 (如文献[4]) 或百科全书中的相关条目就够了。

1 差分

1.1 SQL查询表达式

为便于对SQL查询语句的分析, 引入一种符号表示法。

定义1 设SQL查询语句一般形式是:

select Z from V where F group by G having H

(不考虑order by子句) 此语句用符号表示成Ve{F}/G{H} (A) , 描述一个SQL查询, 称为SQL查询表达式。约定:

(1) 下划线表示用逗号分隔的多项, 如A=A1, A2, …, An。

(2) Ve是对应于V的联接表达式。如表V、W的普通联接表示成V*W或简单地表示成VW。其它联接及表示法后面逐个引进。

(3) F、H中的and用&代替, or用|或∨代替, not用!代替。y is null表示为“y空”, 而y is not null为“y非空”。exists与not exists表示为∃与∃, in和not in表示为∈和∉, left join用<表示, right join用>表示。

(4) V或A中的换名 (Oracle中是空格, SQL Server等中用字as) 用冒号表示。如a1+a2:b表示列的表达式a1+a2在输出时换名为b。

(5) 如果A中有distinct, (A) 改为[A]。

(6) A是*时 (*) 可省去。

例1 SQL查询表达式表T (x) , 其中x= (p, y, z) 。

(1) T{p<100} (y, z) =Select y, z from T where p<100

(2) T{p<100}[y, z]=Select distinct y, z from T where p<100

(3) T{p<100}/p{count (*) <2} (p) =select p from T where p<100 group by p having count (*) <2

(4) T/ (p, y) (p, sum (rep) :rep) =Select p, sum (rep) rep from T group by p, y

(5) T:a{y=T{p=a.p} (max (y) ) }=Select*from T a where y= (select max (y) from T where p=a.p)

(6) T:a*T:b{a.p=b.p&a.y<b.y}=select*from T a, T b where a.p=b.p and a.y<b.y

(7) (T:a>T{a.y=T.y}) {T.y空}=select*from T a left join T on a.y=T.y where T.y is null

1.2 SQL表

定义2 SQL表 x是关系数据库意义上的属性集, rep是非零整数。

(1) 形如V (x, rep) 的一个表或视图或一个以 (x, rep) 为输出的SQL查询称为SQL表, 下文也简称表。V是表名, x中各属性称为表的列, x也记作V.cols, 是V中除rep外的所有列组成的列集。rep称为V的重数列。rep恒为1的表rep列可省去。

(2) 对表中任一行t (x0 r0) ∈V。r0是x0在t的重数, 记为t.rep (x0) 。V中所有t.x=x0的t的重数之和称为x0在V的重数, 记为:

V.rep (x $0) = \sum_{t \in V & x = x 0}$ (1)

若x0∉V, 则定义V.rep (x0) =0。

(3) 若有限制rep>0, 称V为正表。

(4) 若V每行的rep值恒为1。这时rep可省去成为V (x) , 称为V的无重数形式。

V.rep (x) 函数依赖于x, 作为x的函数, 定义域是无限集。当且仅当x出现在V中时有非零值。

注意:如定义中所示, 形如 (x, rep) 的结构表示表的列名, 逗号是列名分隔符;而形如 (x0 r0) 的结构表示表中的数据行, 空格是数据分隔符。后面均按此协定。

定义3 表的可加和相等两个表V (x, rep) 、W (y, rep) , 若x、y列数相同且对应列的数据类型也相同, 称V、W是可并的或可加的。若x (或y) 的任意值 $\underline{t} 0$ 在V、W的重数相等:V.rep $(\underline{t} 0) = W . r e p (\underline{t} 0)$ , 则两表相等。

例2 x是整数, 下面的表V1 (x, rep) 、V2 (x, rep) 、V3 (x) 是相等的:

V1 (x, rep) V2 (x, rep) V3 (x)

7 1 7 1 7

8 2 8 3 8

8 1 8

同一表在相等的意义上有多种表示形式。其中两个表示形式有特殊意义:如例中V3, 这是无重数形式, 是通常出现在数据库中的表的形式;若x值在表中不重复, 是规范形式。对应的rep表示在表中的重数。如例中V2。

如V1所示是不规范的SQL表, 是最一般的表示形式。

实际数据库中的表大多是有主键的正表, 是无重数形式的规范表。当对这些表作了投影或并时才产生重数大于1的表, 而且可能是不规范的。

对表V (x, rep) 作规范化的SQL语句:

V/x{sum (rep) <>0} (x, sum (rep) :rep) =select x, sum (rep) rep from V group by x having sum (rep) <>0

无重数形式表V (x) 的规范化语句为:

V/x (x, count (*) :rep) =select x, count (*) rep from V group by x

无重数形式和规范形式对于每一正表都存在且唯一。

1.3 表的加法和减法

定义4 表的和与差可加的两个表V (x, rep) 、W (y, rep) 之和记为V+W, 是一规范表, x的任一值x0在V+W的重数是x0在V的重数与在W的重数之和:

(V+W) .rep (x0) =V.rep (x0) +W.rep (x0) (2)

V、W之差记为V-W, 是V与 (-W) 之和, -W是W的全部重数加负号。

W+V与V+W可能列名不同及表中行的顺序不同, 但这不影响定义3意义的相等。所以表的加法可交换。

例3 V、W、V+W、V-W的数值例。

V (x, rep) W (y, rep) V+W V-W

7 1 8 1 7 1 7 1

8 2 9 2 8 3 8 1

9 2 9 -2

计算表V、W的和可先作保留重复并union all (符号∪A) 把两表合成一表, 然后规范化。语句是:

(V∪AW) /x{sum (rep) <>0} (x, sum (rep) :rep) =

select x , sum (rep) rep from (

select x, rep from V union all select y, rep from W

) group by x having sum (rep) <>0

表的加运算满足交换律和结合律。

W是空表, 则V+W=V。W是-V, 则V+W=空。与某表V可加的所有SQL表{V}与加运算构成交换群。

1.4 SQL表的差分

定义5 差分设SQL表V的当前值是从V经过一系列的insert、delete和update得到。Q (V) 是V上的一个SQL查询。d (Q (V) ) =Q (V) -Q (V0) 称为Q (V) 的差分, V0称为V的初值。

由定义5得到以下三个结论:

(1) 设Q (V) =V。则:

dV=V-V0。或d (V1, V2, …, Vn) = (dV1, dV2, …, dVn) = (V1-V10, V2-V20, …, Vn-Vn0)

dV的数据可建insert、delete、update三个trigger产生。若系统有备份V0, 则可直接计算V-V0得到。

(2) 设Q (V) 是物化视图。当V从V0变到当前值时, Q=Q (V) 的值还保持在Q0=Q (V0) 。为得到Q只要做Q0+dQ。定义5是从Q产生dQ的一种方法, 即完全重算。本文研究增量方法。

(3) d (Q (V) ) 作为函数, 它的自变量是V和V0或dV和V (因dV=V-V0) , 把此函数记为dQ (dV, V) 。如果是复合函数如Q (S (V) ) , 则 (注意与数学分析中的复合函数导数不同) :

d (Q (S (V) ) ) =dQ (d (S (V) ) ,

S (V) ) =dQ (dS (dV, V) , S (V) )

定理1 V0是正表, 则对同一x值V.rep (x) ≥dV.rep (x) 。

证明由定义5与式 (2) , dV.rep (x) =V.rep (x) -V0.rep (x) 。

V0是正表, V0.rep (x) ≥0。由此得:

V.rep (x) ≥V.rep (x) -V0.rep (x) =dV.rep (x)

定理2 和的差分两表和的差分等于差分的和:d (V+W) =dV+dW。

证明设V、W的初值为V0、W0, 则由定义5及加法的交换律和结合律,

d (V+W) =V+W- (V0+W0) = (V-V0) + (W-W0) =dV+dW

2 投影与选择

2.1 保留重复投影

定义6 保留重复投影 z是属性集, z⊆V.cols。SQL表V在z的保留重复投影, 记为V (z) , 是由形如t (z rep) 的行组成的规范SQL表, t.rep表示t.z在V中的重数。

由定义, V (z) 中每行t的重数是V中含有t.z的行的重数之和。设x=V.cols, V (z) 中z0的重数:

V (z) .rep (z $0) = \sum_{x \supseteq \underline{z} 0} V . r e p$ (x) (3)

可用如下语句计算保留重复投影:

V是无重数形式:

V (z) =V/z (z, count (*) :rep) =

select z, count (*) rep from V group by $\underline{z}$

V有rep列:

V (z) =V/z (z, sum (rep) :rep) =

select z, sum (rep) rep from V group by $\underline{z}$ having sum (rep) <>0

计算中作了规范化操作, 结果是规范的SQL表。

在符号的使用上有一点混淆:若z=x=V.cols, 则V (x, rep) 在x的保留重复投影按定义记为V (x) , 与V (x, rep) 相同。故V (x) 可能是一个无重数列的表, 也可能是另一表的保留重复投影。必要时将在上下文中明确说明。

定理3 投影可加性设V1 (x, rep) 、V2 (x, rep) 是两个可加的SQL表, z⊆x。则保留重复投影对加可分配:

(V1+V2) (z) =V1 (z) +V2 (z)

证明由SQL表相等定义3, 只要证明等号两边对任意值 $\underline{z} 0$ 的重数相等。由式 (3) 得:

(V1+V2) (z) .rep (z $0) = \sum_{x \supseteq \underline{z} 0} (V 1 + V 2) . r e p (x)$

由表相加定义4及式 (3) ,

上式 $= \sum_{x \supseteq \underline{z} 0} V 1 . r e p$ (x) $+ \sum_{x \supseteq \underline{z} 0} V 2 . r e p$ (x) $= V 1 (\underline{z}) . r e p$ (z $0) + V 2 (\underline{z}) . r e p (\underline{z} 0)$

推论保留重复投影差分对表V (x) 或V (x, rep) , 设z⊆x, 则:

d (V (z) ) =dV (z) (4)

证明 d (V (z) ) =V (z) -V0 (z) = (V-V0) (z) =dV (z) 。

定义7 一元线性运算对可加SQL表V1、V2的一元运算G若成立:

G (V1) +G (V2) =G (V1+V2)

称G对加可分配, 也称为一元线性运算。

由定理3, 保留重复投影是一元线性运算。

定理4 保留重复投影合并设y⊆z⊆x, SQL表V (x, rep) 连续在z和y的保留重复投影等于在y的保留重复投影:

V (z) (yy) =V (y)

证明证明两边在任意值y0的重数相等。由式 (3) 得:

$V (\underline{z})$ (y) .rep (y $0) = \sum_{\underline{z} 0 \supseteq y 0} V (\underline{z}) . r e p$ (z $0) = \sum_{\underline{z} 0 \supseteq y 0} \sum_{x 0 \supseteq \underline{z} 0} V . r e p$ (x)

$= \sum_{x 0 \supseteq y 0} V . r e p$ (x) =V (y) .rep (y0)

其中确认了z0⊇y0, x⊇z0与x⊇y0等价。必要性是明显的。充分性只要为满足x⊇y0的任意值x0找出满足z0⊇y0, x0⊇z0的z0即可。而此z0即是x0中包含的z上的值。

2.2 消除重复投影

从一个SQL表V中取互不相同的z, z⊆V.cols, 这一操作称为对z的消除重复投影, 可用带distinct的查询计算:

select distinct z from V

但这样定义不适用于负重数。本文使用下面的定义。

定义8 保留符号消除重复投影 SQL表V, z⊆V.cols, V在z的消除重复投影, 是对保留重复投影V (z) 的重数只取符号得到的SQL表。记为V[z]。

由定义, V[z]在任意值z0的重数是:

V[z].rep (z $0) = s i g n (\sum_{x \subseteq z 0} V . r e p (x))$ (5)

计算V[z]的SQL语句是:

V[z]=select z, sign (sum (rep) ) rep from V group by z having sum (rep) <>0

定理5 消除重复投影合并 y⊆z⊆x, 正SQL表V (x, rep) 对z、y上的投影成立

V[z][y]=V[y]

证明这是关系代数中的命题。因等号两边的y都取自同一表V而重数都是1。

有负重数时定理不成立。如下例。

例4 SQL表V (p, z, y, rep) , 值如下面第一表, 有负重数。V[p, z][z]≠V[z]。

2.3 whole函数与消除重复投影的差分

表V对V.cols作消除重复投影V[V.cols], 记作[V]。因此

V[z]=[V (z) ] (6)

定理6 V (x, rep) 、W (y, rep) 是可加正表。则[V][z] $= V [\underline{z}] ‚ [V + [W]] = [V + W]$ 。

证明先验证一个辅助等式:

当 x, y≥0, sign (sign (x) +y) =sign (x+y) (7)

若y>0, 则两边都是1, 等式成立;而若y=0, 因sign (sign (x) ) =sign (x) 等式也成立。

然后计算待证等式两边重数。第一式:

[V][z].rep (z $0) = s i g n \sum_{\underline{x} \supseteq \underline{z} 0} [V] = s i g n$ $\sum_{x \supseteq \underline{z} 0} s i g n (V . r e p$ (z) )

用辅助等式 (7) 把求和符号内的sign逐个删去, 所得等式即是V[z]在z0的重数。

第二式:

[V+[W]].rep (x0) =sign (V.rep (x0) +sign (W.rep (y0) ) )

用辅助等式把括号内的sign删去, 所得等式即是[V+W]在x0的重数。

[V]的差分是d[V], 记录因dV的变化而引起的[V]的变化。因为只有当在V中出现的x的一个值x0全部是新加入的, 或者V0中的x0在V已全部被删去, 才会对[V]产生影响, 使[V]增加或删去该x0。

用whole (dV, V) 或简单地whole (dV) 记dV中这些能使[V]发生变化的行, 称为dV的全加全删子集, 其中的行使[V]有增1行或减1行的变化。所以d[V]是whole (dV) 的保留重复投影:sign (wholw (dV) ) , 简单地写作signwhole (dV) , 即得:

d[V]=signwhole (dV) (8)

式 (8) 的V代以V (z) 。因式 (4) , d (V (z) ) =dV (z) , 得消除重复投影的差分

d (V[z]) =signwhole (dV (z) , V (z) )

为推导出whole (dV) 的表达式, 把dV的行分成三类:

(1) 全删类这类行重数均为负, 其中的x不再在V中;

(2) 全加类这类行也在V中存在, 且在V的重数与在dV的重数相同;

(3) 其他这类行中的x也在V中, 但重数不同。由定理1, 必dV.rep<V.rep。

故只要从dV中删除第 (3) 类行即得whole (dV) 。对t (x r) ∈dV构造查询V{t.r<rep} (x) , 只要t.x属于其中t即是三类行。由此得:

whole (dV) =dV{x∉V{dV.rep<rep} (x) } (V规范) , 或whole (dV) =dV{x∉V/x{dV.rep<count (*) } (x) } (V无重数) (9)

SQL形式:

select*from dV where (x) not in (select x from V where dV.rep<rep) , 或select*from dV where (x) not in (select x from V group by x having dV.rep<count (*) )

2.4 选择

SQL查询的where子句与having子句是逻辑表达式, where子句称为行条件, 选择对象是行;having子句用在分组子句group by后, 对组作选择, 称组条件。

在查询表达式中, 逻辑连接词and用&、or用|或∨、not用下划线或!表示。下面的等式来自命题演算, F代表一个逻辑表达式:

又对一般的表都成立:V{F}+V{F}=V。

定义9 选择的特征函数设F.cols是F中用到的所有列。函数f (F.cols) 当F=true取值1, 当F=false取值0。称f是F的特征函数, 用λF表示。

特征函数用以计算有选择的查询的重数。V{F}在 (x0) 的重数是:

V{F}.rep (x0) =V.rep (x0) *λF (10)

易验证下面的等式:

λ (F1&F2) =λ (F1) *λ (F2) λ (F1|F2) =sign (λ (F1) +λ (F2) ) λF=1-λF

定义10 环境无关查询V{F}的条件F称为是环境无关的, 设b是与V的类型匹配的行, F在b上的值F (b) 只与b有关而与V的内容无关。

定义的意思是, 不论b是否在V中及V中有些什么行, F (b) 不受影响。例如, 若F有组函数则不是环境无关的, 因F (b) 与和b同一组的其他行有关, 因此满足环境无关的条件必须是行条件。若F中含有重数, 因重数实际上是组函数count (*) , 也不是环境无关的。

即使行条件, 也有不是环境无关的:

例5 查询

V{∃V:a{V.p>p}}=select*from V where exists (select*from V a where V.p>p) 的行条件F={∃V:a{V.p>p}}不是环境无关的。设V有两组值:V1={2}、V2={1, 2}。则V1{F}=空, V2{F}={2}。F (2) 在V1中是false, 在V2中是true。

事实上, 决定F (b) 的除了b外还有组成F的子查询。设F.tabs是用在F的子查询中的所有表。则有下面的充分条件判断F的环境无关性。

定理7 环境无关判别法查询V{F}中若V与F.tabs无相同表, 则F是环境无关的。

证明 F (b) 实际上是F (b, F.tabs) , V与F.tabs没有相同的表, V替换成别的表不影响F.tabs, 因而也不影响F (b, F.tabs) 的值。符合定义10。

注意证明中用的是“替换”而不是“修改”。这是因为修改时V的表可能有trigger会影响F.tabs的内容。如果V的trigger不影响F.tabs, 则对V修改也未尚不可。

定理8 选择对投影和加的分配选择条件F环境无关。

① 对表V (p, z, rep) , 选择条件F只与z有关, 则:

V (z) {F}=V{F} (z) , V[z]{F}=V{F}[z]

② 表V1 (x, rep) 、V2 (y, rep) 可加, 则:

(V1+V2) {F}=V1{F}+V2{F}

证明 ① 第一式。等号两边计算得的F相同。由式 (10) 和式 (3) , 左边在z0的重数:

V (z) {F}.rep (z0) =V (z) .rep (z $0) * λ F = (\sum_{\underline{z} = \underline{z} 0} V . r e p (p, z)) * λ F$

F只与z有关, 对于求和符号中的 (p, z) 因z=常数z0, λF是常数, 由此有:

上式 $= \sum_{\underline{z} = \underline{z} 0} (V . r e p$ (p, z) $* λ F) = \sum_{\underline{z} = \underline{z} 0} V {F} . r e p$ (p, z)

=V{F} (z) .rep (z0)

根据定义3等式成立。

第二式。第一式两边作消除重复投影:

[V (z) {F}]=[V{F} (z) ]=V{F}[z]

F只与z有关因而与重数无关。由式 (6) 等号左边又可以是:

[V (z) {F}]=[V (z) ]{F}=V[z]{F}

由此第二式成立。

② F环境无关, 式中3个F对同一行得相同值。由式 (10) , 左边在x0的重数:

(V1+V2) {F}.rep (x0) = (V1+V2) .rep (x0) *λF

再由和的重数:

上式= (V1.rep (x0) +V2.rep (x0) ) *λF=V1.rep (x0) *λF+V2.rep (x0) *λF

再次由 (10) :

上式=V1{F}.rep (x0) +V2{F}.rep (x0) = (V1{F}+V2{F}) .rep (x0)

根据定义3等式成立。

推论表V的选择条件F环境无关, 选择的差分等于差分的选择:

d (V{F}) =dV{F}。

证明设V0是V的初值:

d (V{F}) =V{F}-V0{F}

F环境无关, 由定理8的②:

V{F}-V0{F}= (V-V0) {F}=dV{F}

3 联接

3.1 笛卡尔积

在SQL中两个表V、W的笛卡尔积为:

VW=select*from V, W

有重数列的SQL表的笛卡尔积一般定义为:

定义11 笛卡尔积 ①由SQL表V (x, rep) , W (y, rep) 产生的一维笛卡尔积是:

V*W=VW={ (vx wy vrep*wrep:rep) | (vx vrep) ∈V, (wy wrep) ∈W}

若V、W是规范的, 2维笛卡尔积是:

V^W={ (vx vrep wy wrep) | (vx vrep) ∈V, (wy wrep) ∈W}

V^W称为2维SQL表, 而V、W、VW等一致地是一维SQL表。vx、wy是x、y的别名。特别是当x、y中有相同列名时vx、wy中必需规定不同的别名。当x、y中无相同列名时vx、wy可直接使用x、y。

②unify函数可把2维SQL表转化成一维:

unify (V^W) =VW

③若V是n维SQL表, W是m维SQL表, V^W是n+m维SQL表。

多维笛卡尔积仅对规范表定义。

一维和多维笛卡尔积满足结合律 (证略) 。因此SQL表与笛卡尔积构成半群。

交换V、W的顺序, 定义11产生的结果列的排列不同。一般理论忽略这种差别而认同笛卡尔积是可交换的。但因为VW与WV明显是不可加的, 所以从SQL的观点两者不相等, 因而本文认定笛卡尔积不可交换。

一维和二维笛卡尔积VW、V^W在 (x0y0) 的重数是:

VW.rep (x0y0) =V.rep (x0) *W.rep (y0)

V^W.rep (x0y0) =V.rep (x0) ^W.rep (y0) = (V.rep (x0) , W.rep (y0) )

3.2 二维表的投影

多维表的任意一个重数列也可作全表的重数列。由此, 对多维表的操作可以归结到一维表, 只要指定其中一个重数列为整个表的重数列即可, 语法是“表名”。如对规范表V (x, rep) 、W (y, rep) , t⊆y, V^W在V和t保留重复投影是:

W＼t (V^W) =V^W (V^t)

$\begin{array}{l} = {(x v r e p t \sum_{y \supseteq t} w r e p (y) : t r e p) | (x v r e p) \in V ‚ (y w r e p) \in W} \\ V^W 在 V 和 t 消除重复投影 \end{array}$

W＼t[V^W]=V^W[V^t]

$= {(x v r e p t s i g n \sum_{y \supseteq t} w r e p (y) : t r e p) | (x v r e p) \in V ‚ (y w r e p) \in W}$

这里两种投影各有两种表示方法。第一种表示方法可明确地表示出计算过程, 而第二种方法与一维表的方法一致, 着重于最后结果的表达。例如, 若z⊆x, t⊆y, 先对V^W作V^t投影再对它作z^t投影为V＼z (W＼t (V^W) ) ;而先投影z再投影t则是W＼t (V＼z (V^W) ) 。用第二种方法表示两者都是V^W (z^t) 。而如投影V＼z (W＼t[V^W]) , 先对t作消除重复投影, 再对z作保留重复投影, 就不能用第二种方法表示。

由上所述, 两种投影在 (x0t0) 的重数是:

$W \underline{t} (V^W) . r e p$ (x $0 \underline{t} 0) = v r e p$ (x $0)^\sum_{y \supseteq \underline{t} 0} w r e p$ (y)

$W \underline{t} [V^W] . r e p (\underline{x} 0 \underline{t} 0) = v r e p$ $(\underline{x} 0)^s i g n$ $\sum_{y \supseteq \underline{t} 0} w r e p$ (y)

定理9 笛卡尔积的投影表V (x, rep) 、W (y, rep) 的笛卡尔积与投影可交换顺序, 即下列各等式成立:

(1) z⊆x, t⊆y:VW (zt) =v (z) W (t) ;VW[zt]=v[z]W[t]

(2) t⊆y:W＼t (V^W) = (V^W) (V^t)

=V^W (t) ;z⊆x:V＼z (V^W) = (V^W) (z^W) =V (z) ^W

(3) t⊆y:W＼t[V^W]= (V^W) [V^t]

=V^W[t];z⊆x:V＼z[V^W]= (V^W) [z^W]=V[z]^W

证明 (1) 第一式。只要证明两边在 $(\underline{z} 0 \underline{t} 0)$ 的重数相等。由式 (3) 及笛卡尔积定义得:

VW (zt) .rep (z0t $0) = \sum_{x y \supseteq \underline{z} 0 \underline{t} 0} (V W . r e p$ (xy) )

$= \sum_{x y \supseteq \underline{z} 0 \underline{t} 0} (V . r e p$ (x) *W.rep (y) )

$= \sum_{x \supseteq z 0} V . r e p$ (x) $* \sum_{y \supseteq \underline{t} 0} W . r e p$ (y)

=V (z) .rep (x0) *W (t) .rep (t0)

= (V (z) W (t) ) .rep (x0t0)

第二式。由式 (6) 及笛卡尔积定义得:

VW[zt]=[VW (zt) ]=[V (z) W (t) ]=[V (z) ][W (t) ]=V[z]W[t]

第三个等号是由于乘积的符号等于符号的乘积。

(2) 第一式。计算在 (x0t0) 的重数。由式 (3) 及二维笛卡尔积定义得:

(V^W) (V^t) .rep (x0t $0) = \sum_{V y \supseteq V \underline{t} 0} (V^W) . r e p$ (x0y0)

$= \sum_{V y \supseteq V \underline{t} 0} (V . r e p$ (x0) ^W.rep (y) )

V.rep (x0) 是常数:

上式=V.rep $(x 0)^\sum_{y \supseteq \underline{t} 0} w r e p$ (y)

又由式 (3)

$\sum_{y \supseteq \underline{t} 0} w r e p$ (y) =W (t) .rep (t0)

V.rep $(x 0)^\sum_{y \supseteq \underline{t} 0} w r e p$ (y) =V.rep (x0) ^W (t) .rep (t0)

=V^W (t) .rep (x0t0)

(3) 第一式。W＼t[V^W]=[W＼t (V^W) ]=[V^W (t) ]

=V^W[t]。

式 (3) :第二式的证明类似第一式。

对于在二维上都有的投影, 从定理9可得与第一式相似的等式:

V＼z (W＼t (V^W) ) =V＼z (V^W (t) ) =V (z) ^W (t)

V＼z[W＼t[V^W]]=V＼z[V^W[t]]=V[z]^W[t] (11)

3.3 笛卡尔积的加法

同样的思路处理多维笛卡尔积的加法, 指定任一维为操作维作一维表加法, 如下例。

例5 SQL表Vi (x, rep) ={ (7 1) }, i=1, 2。W1 (y, rep) ={ (8 1) }, W2 (y, rep) ={ (8 2) }。则Vi^Wi (x, vrep, y, wrep) }等的值为:

V1^W1 V2^W2 V1^W1+V＼V2^W2 V1^W1+W＼V2^W2

7 1 8 1 7 1 8 2 7 1 8 1 7 1 8 3

7 1 8 2

在V1^W1+V＼V2^W2指定V为加维, (x, y, wrep) 相等的两行的vrep相加, 不存在这样的行, “+V＼”成为并。而在V1^W1+W＼V2^W2中指定W为加维, (x, vrep, y) 相等的两行wrep相加, 得 (7 1 8 3) 。

定理10 笛卡尔积对加的分配律 SQL表V1 (x, rep) 、V2 (x, rep) 、W (y, rep) , 其中V1、V2可加, 则:

(V1+V2) *W=V1*W+V2*W

W* (V1+V2) =W*V1+W*V2

(V1+V2) ^W=V1^W+V＼V2^W

W^ (V1+V2) =W^V1+V＼W^V2

证明第一式, 证明在 (xy) 的重数等号两边相等。

第二式由第一式用交换律得出。

第三式。推导过程同第一式, 只是*替换成^号。第四式由第三式用交换律得到。

3.4 笛卡尔积的差分

当V和W替换成V=V0+dV, W=W0+dW, 利用定理9可导出笛卡尔积的差分。因:

由此得:

d (VW) =VW-V0W0=dVW0+VdW

d (V^W) =V^W-V0^W0=+V＼dV^W0+W＼V^dW

“+V＼”指定对V维相加。若进一步用W-dW代替W0, 得不用初值的笛卡尔积差分公式:

d (VW) =dVW0+VdW=dVW+VdW-dVdW

d (V^W) =V^W-V0^W0=+

V＼ (dV^W-W＼dV^dW) +W＼V^dW (12)

注意到这些公式的得到只是用了定理9中的分配律, 故结论可以推广到更一般的情形。

定义12 二元线性运算二元关系运算Θ若满足对加运算的左分配律, 即对第一分量满足分配律, 称左线性的;若满足右分配律, 称右线性的, 若满足左右分配律, 称为线性 (二元) 的。

定理11 二元运算全差分展开设V、W是SQL表。对于一个二元关系运算VΘW, 全差分可如下计算:

d (VΘW) =V＼d (VΘW0) +W＼d (VΘW)

或V＼d (VΘW) +W＼d (V0ΘW) (13)

其中V＼d、W＼d表示只对前缀中分量的差分, 另一分量无变化。

证明证明第一式。由V＼d (VΘW0) =VΘW0-V0ΘW0、W＼d (VΘW) =VΘW-VΘW0代入再运用分配律即得。

这一规则还能进一步推广到多元关系运算G (V1, V2, …, Vn) :

定理12 多元展开公式 n个变元的SQL查询表达式G (V1, …, Vn) 的d全差分可表示为对每一变元的差分之和:

其中i=1, …, n;第i项的参数中从第i+1项起到n项都取初值。

证明用数学归纳法。略。

如果G对Vi是线性的, 则:

Vi＼dG (V1, …, Vi, …, Vn0) =G (V1, …, dVi, …, Vn0) 。

3.5 联接

在笛卡尔积中加选择条件即为联接。V和W的一维和二维联接用V*W{F} (或VW{F}) 和V^W{F}表示, 这时F也称联接条件。如:

VW{V.x=W.y}=select V.x, W.y, V.rep*W.rep rep from V, W where V.x=W.y

一维和二维联接VW{F}、V^W{F}在 (x0y0) 的重数是:

VW{F}.rep (x0y0) =V.rep (x0) *W.rep (y0) *λF

V^W{F}.rep (x0y0) =V.rep (x0) ^W.rep (y0) *λF

作为联接条件的F一般总与两个表的列有关。但SQL的语法上也允许条件F只与一个表有关, 这时的F称为限定条件, 没有联接作用。

定理13 笛卡尔积与限定条件规范表V (x.rep) 、W (y, rep) 的二维笛卡尔积与V表的限定条件F可交换执行顺序:

V^W{F}=V{F}^W

若F与重数无关则对一维笛卡尔积也成立:

VW{F}=V{F}W (14)

证明证明一维笛卡尔积等式 (14) 。左边在 (x0y0) 的重数为:

VW{F}.rep (x0y0) =V.rep (x0) *W.rep (y0) *λF

F是V的限定条件只与V有关, λF与V.rep (x0) 组成V{F}.rep (x0) :

V.rep (x0) *W.rep (y0) *λF=V{F}.rep (x0) *W.rep (y0) =V{F}W.rep (x0y0)

根据定义3等式 (14) 得证。二维的等式证明方法相同。

由此定理可得一推论:

推论规范表V (x, rep) 、W (y, rep) 的联接与V、W表的重数无关的限定条件可合并:

(V{F1}^W{F2}) {F3}=V^W{F1&F2&F3}

(V{F1}W{F2}) {F3}=VW{F1&F2&F3}

(当F1、F2重数无关) (15)

证明由定理13, 把F1、F2从括号中移出:

(V{F1}W{F2}) {F3}=VW{F1}{F2}{F3}=VW{F1&F2&F3}

关系代数的运算优化规则中有一规则是把投影和选择移到联接前。在SQL表中也可证明这一规则可行:

定理14 联接与投影规范SQL表V, W的联接VW{F}中, 设z⊆V.cols, t⊆W.cols, F环境无关且只与z、t有关。则:

证明第一式。设x=V.cols、y=W.cols。VW{F} (zt) 在 (z0t0) 的重数为:

VW{F} (zt) .rep (z0t $0) = \sum_{x y \supseteq z 0 t 0} V W {F} . r e p$ (xy)

$= \sum_{x y \supseteq z 0 t 0} (V . r e p$ (x) W.rep (yλF)

因F只与zt有关, zt= (z0t0) 时求和号内的λF是常数, 移出求和号外, 余下部分分开成V、W两部分得:

上式 $= \sum_{x \supseteq \underline{z} 0} V . r e p$ (x) $\sum_{\underline{y} \supseteq \underline{t} 0} W . r e p$ (y) λF

=V (z) .rep (z0) *W (t) .rep (t0) λF

=V (z) W (t) {F}.rep (z0t0)

因 (z0t0) 是任意值, 由定义3所证等式成立。

第二式。在第一式两边取符号, 左边即为VW{F}[zt], 右边为V[z]W[t]{F}。等式成立。第三与第四式的证明类似, 略。

3.6 联接的差分

定理15 联接差分联接条件F环境无关时:

证明联接条件环境无关时联接满足分配律。只要在笛卡尔积差分公式 (12) 等号两边加联接条件即得定理结论。

4 量词

量词子查询是指where或having子句中含有exists或not exists。前者当子查询结果非空为真, 称为存在量词;后者是当子查询结果空时为真, 称不存在量词。

因为其他子查询都可以等价地表示为量词, 本文只研究量词子查询。

4.1 存在量词

含有存在量词的查询一般形式如:

select*from V where F0 and exists (select*from W where F) ;

该查询的表达式是V{F0&∃W{F}}。查询结果是V中满足F0且能与W通过F联接的行, 但与能联接的W的行数目无关。如果没有F0, 即可简单地记为V∃W{F}, 其中V称为存在量词的主方, W为次方。注意到F0与W无关, 所以该查询等价于V{F0}∃W{F}。

借用谓词演算的符号∃表示exists是合理的, 因为V∃W{F}就是谓词演算中存在量词∃yP (y) 的具体化, 只要令P是“y∈W&F (x, y) ”即可, 用SQL的述语是“W{F}非空”。

∃W{F}或∃Q作为选择条件是对子查询Q的非空性测试。易验证:

∃Q1&∃Q2=∃ (Q1*Q2) , 当Q2≠-Q1:∃Q1∨∃Q2

=∃ (Q1∪Q2) =∃ (Q1+Q2) (17)

第一式是:Q1、Q2都非空当且仅当Q1*Q2非空, 第二式是当Q2≠-Q1, Q1、Q2之一非空当且仅当Q1∪Q2非空。但当Q2=-Q1时, 虽Q1∪Q2非空而Q1+Q2空。第6节将为有负重数的表定义并运算∪:Q1∪Q2是Q1+Q2的消除重复投影。这样第二式成立必须有附加条件Q2≠-Q1。

存在量词∃W{F}的特征函数为:

$λ (\exists W {F}) = s i g n \sum_{t r u e} (W . r e p$ (y) *λF) 2

$= s i g n \sum_{F} W . r e p$ (y) 2 (18)

求和条件为true表示无条件。平方的作用是变负重数为正。若W是正表则平方可不要。

定理16 存在量词基本定理表V (x, rep) 规范, W (x) 正表。存在量词查询V∃W{F}是二维联接V^W{F}对V的消除重复投影的一元化:

V∃W{F}=unifyV^W{F}[V] (19)

该定理权作为本文对存在量词的定义。下面证明这样定义的合理性。

证明计算两边在x的重数并证明相等。由式 (18) , 因W是正表求和号内不用平方:

V∃W{F}.rep (x0) =V.rep (x $0) * s i g n \sum_{t r u e} (W . r e p$ (y) *λF)

另一方面:

由此后者取unify后两者相等, 定理得证。

如果V不是规范的, 不保证V∃W{F}无重复行。而V^W{F}[V]必无重复行, 故不能保证两者相等。

4.2 不存在量词

不存在量词查询是在where中有not exists的查询, 用存在量词加下划线∃表示不存在量词。∃W{F}与∃W{F}作为两个查询条件是互补的, 对V中任何一行两者不同时成立但必成立其中之一。所以设Q=W{F}:

λ (∃Q) =1-λ (∃Q) V∃Q=V-V∃Q (20)

不存在量词也有类似式 (17) 的等式:

Q2≠Q1:∃Q1&∃Q2=∃ (Q1∪Q2)

∃Q1∨∃Q2=∃ (Q1*Q2) (21)

不存在量词也满足左分配律。

4.3 量词与保留重复投影

定理17 量词次方的保留重复投影规范表V (x, rep) 、W (y, rep) , t⊆y, F只与x、t与重数有关。存在量词和不存在量词次方的保留重复投影可以合并在条件F中计算:

证明 W (t) .rep (t) $= \sum_{y \supseteq t} W . r e p (y)$ 代替等号左边的W (t) .rep。代入后F不再使用W (t) .rep而使用W.rep, 次方W (t) 应换成W。

例如:

dV (z) :a∃V (z) :b{a.z=b.z&a.rep=b.rep}

=dV (z) :a∃V{a.z=V.z $& a . r e p = \sum_{x \supseteq z} V . r e p (x)}$

18 量词主方的投影 SQL表V (x, rep) 规范, ∃W{F}环境无关。z⊆x, 若量词条件F只与z有关, 则存在量词和不存在量词主方的两种投影可延迟到量词运算后进行:

证明由定理8的等式V (z) {F}=V{F} (z) 和V[z]{F}=V{F}[z]。∃W{F}环境无关必∃W{F}也环境无关。F用∃W{F}替换即得第一、三式、用∃W{F}替换即得第二、四式。

4.4 量词的差分

定理19 量词差分规范SQL表V (x) 或V (x, rep) , W (y) 或W (y, rep) 正表, ∃W{F}环境无关。W0是W的初值。则 (式中未写出{F}) :

d (V∃W) =dV∃W0+unifysignwhole (V^dW (V) , V^W (V) )

d (V∃W) =dV∃W0-unifysignwhole (V^dW (V) , V^W (V) )

证明因∃W{F}环境无关, V＼d (V∃W) =dV∃W。再由二元展开公式可推得:

d (V∃W) =dV∃W0+W＼d (V∃W)

计算W＼d (V∃W) 。用定理16把V∃W表示成unifyV^W[V], 再由式 (10) 及W＼d (V^W (V) ) = V^dW (V) :

W＼d (V^W[V]) =signwhole (V^dW (V) , V^W (V) )

其次证明W＼d (V∃W) =unifyW＼d (V^W[V]) 。由W＼d定义:

unifyW＼d (V^W[V]) =unify (V^W[V]-W＼V^W0[V])

括号中两项对W重数作减运算, 而该重数如果有的话只能是1。又如果两项都是1的话相减后抵消。两项中只有一项是1时unify后各为V∃W或V∃W0。由此:

unifyW＼d (V^W[V]) =V∃W-V∃W0=W＼d (V∃W)

W＼d (V∃W) =unifysignwhole (V^dW (V) , V^W (V) )

第一式得证。

由V∃W+V∃W=V得W＼d (V∃W) =-W＼d (V∃W) , 据此又可得不存在量词的差分式

unifysignwhole (V^dW (V) , V^W (V) ) 的表达式根据V、W的表示形式不同而有所不同。若两者都是无重数形式时:

5 外联接

SQL外联接有左、右、全三种, 本文分别用>、<、<>表示。普通联接有一维和多维的, 外联接也有一维和多维。如V>W是一维左外联接。

V>W由两部分组成:一是组成VW{F}的部分, 该部分的重数是V.rep*W.rep, 表示每一V行被重复W.rep次;另一是与W不可联接的部分, 该部分的重数是V.rep, 这里的V行只出现一次。故V (x, rep) 和W (y, rep) 的一维左外联接V>W{F}的重数是:

V>W{F}.rep (xy) =V.rep (x) * (W.rep (x) *λF+1-λF) (23)

V和W的一维和二维左外联接可定义为:

V>W{F}=V*W{F}+V∃W{F}*Φ[W]

V>^W{F}=V^W{F}+V∃W{F}^Φ[W] (24)

Φ[W]表示只有一个空行的与W同类型的表, V∃W{F}*Φ[W]与V∃W{F}^Φ[W]表示将V∃W{F}用空值加长到与第一项等长。SQL中有专用的语法计算外联接。计算该两左外联接的语句:

V>W{F}=select x, y, V.rep*nvl (W.rep, 1) rep from V left join W on F;

V>^W{F}=select*from V left join W on F;

把保留字left改成right或full即为右或全外联接。一维和二维全外联接定义为:

V<>W{F}=V*W{F}+V∃W{F}*Φ[W]+Φ[V]*W∃V{F}

V<>^W{F}=V^W{F}+V∃W{F}^Φ[W]+Φ[V]^W∃V{F}

与左右外联接的关系:

V<>W=V>W+V<W-VW

V<>^W=V>^W+V＼V<^W-V＼V^W

后面只研究一维左外联接。并且所有关于外联接的计算式中非必要时都略去了用空值加长的表达式Φ[W], 直到要改写成SQL查询语句时再加上。

5.1 whole函数用外联接表示

根据第二节中全删子集和全加子集的描述, 外联接dV>V{dV.x=V.x}中用V.rep is null作选择是dV的全删子集, 用dV.rep=V.rep作选择是全加子集。由此得whole的外联接计算法:

whole (dV, V) =dV>V{dV.x=V.x& (V.rep空|dV.rep=V.rep) }

对比式 (9) 用in的表示方法, 外联接法可使用索引因而可以计算得较快。

5.2 外联接与投影

定理20 外联接与投影若外联接的联接条件只与投影列有关且环境无关, 则与投影 (保留或消除重复) 可交换操作顺序:

其中z⊆V.cols, t⊆W.cols, 联接条件F只与z, t有关。

证明第1式。由定义:

(V>W) (zt) = (V*W+V∃W) (zt)

=V*W (zt) +V∃W*Φ[W] (zt) 。

因联接条件环境无关, 由定理14:

上式=V (z) *W (t) +V (z) ∃W*Φ[t]=V (z) >W (t) 。

第2式。同第一式, 只是将*改为^。

第3式。F真时, V>W=V*W, (V>W) [zt]=V*W[zt]=V[z]*W[t]=V[z]>W[t];

F假时V>W=V∃W*Φ[W], (V>W) [zt]=[ (V>W) (zt) ]=[ (V∃W*Φ[W]) (zt) ]=[V (z) ∃W*Φ[t]]=V[z]∃W*Φ[t]=V[z]>W[t]。

第4式。同第3式证明, >改为>^, *改为^。

5.3 外联接的结合律

三个表V、W、P的左外联接有两种:

(1) W<V>P式, W和P都对V联接, V是两个外联接合用的左分量, 为并行外联接。

(2) V>W>P式, W在对V的外联接中是右分量而在另一外联接中是左分量, 称串行外联接。

并行和串行的左外联接在SQL中的语法为:

V left join W on F1 left join P on F2

和

V left join W left join P on F2 on F1

定理21 串行组合外联接的结合律若F1是V、W间的环境无关条件, F2是W、P间的环境无关条件且是非容空的 (空值上计算必是false) , 则:

(V>W{F1}) >P{F2}=V> (W>P{F2}) {F1}

证明把等号两边各自用外联接定义展开:

(V>W) >P= (VW+V∃W) >P

=VWP+ (V∃W) P+VW∃P+ (V∃W) ∃P

(F2环境无关)

V> (W>P) =V (W>P) +V∃ (W>P)

=V (WP+W∃P) +V∃W (F1环境无关, V∃ (W>P) =V∃W)

两者区别在于V∃W部分。V∃W分成 (V∃W) ∃P和 (V∃W) ∃P两部分, 第一式是第二式中的 (V∃W) ∃P被替换成了 (V∃W) P。

由于F2是W、P间的条件, V∃W (应是V∃W*Φ[W]) 中与P计算F2的是Φ[W]的空行, F2是非容空条件, (V∃W) P与 (V∃W) ∃P都为空, (V∃W) ∃P=V∃W。定理得证。

三个表V、W、P的内外混合联接也有两种。① (VW) >P。②V (W>P) 。

定理22 与普通联接的结合律若联接条件环境无关, (VW) >P=V (W>P) 。

证明由定义, (VW) >P=VWP+ (VW) ∃P。由联接条件环境无关, 则:

VWP+ (VW) ∃P=V (WP+W∃P) =V (W>P)

5.4 外联接差分

由于加号两边的表达式都是左线性的, 所以外联接也是左线性的。因此有:

d (V>W) =dV>W0+W＼d (V>W)

W0是W的初值。把V>W用式 (24) 代入 (第二个等号要求W是正表) :

例6W、P是正表, 推导 (V>W) >P的差分:

d ( (V>W) >P) =d (V>W) >P0+ (V>W) dP-

unifysignwhole ( (V>W) ^dP (V) , (V>W) ^P (V) )

展开d (V>W) ,

d ( (V>W) >P) = (dV>W0+VdW-unifysignwhole (V^dW (V) , V^W (V) ) ) >P0+ (V>W) dP-

unifysignwhole ( (V>W) ^dP (V) , (V>W) ^P (V) )

6 二元集合运算

本文研究的二元集合运算有union (并) 、except (oracle中用minus, 差) 、intersect (交) 三种, 而union又分为union all和union两种, 故共有四种集合运算。

6.1 保留重复集合并

union all是保留重复并, 本文中用作未规范化的加运算。设V和W可加, 保留重复并的结果记作V∪AW把V和W的行不论相同与否都合并在一起。但仅作集合运算不做规范化操作, 得到的是非规范的SQL表。由SQL表的加运算定义4知, V∪AW规范化后即为V+W, 因此两者相等:V∪AW=V+W, V∪AW的差分同和的差分:

d (V∪AW) =dV+dW (27)

6.2 消除重复集合并

没有all的union是无重复并。V和W无重复并是对V∪AW再作消除重复操作, 即[V∪AW], 表示为V∪W。其实SQL只要用下面的语句即可:

select x from V union select y from W

两个select都不用distinct, 它的作用已被union包括。

下面的定义把并推广到负重数。

定义13 保留符号消除重复并 SQL表的无重复集合并是和的保留符号消除重复投影:

V∪W=[V+W]

例如,

{ (6 2) , (7 2) }∪{ (7 -2) }={ (6 1) },

{ (6 2) , (7 -2) }∪{ (7 -3) }={ (6 1) , (7 -1) }。

定理23 并的结合律正表V1、V2、V3可加, 则它们的无重复并满足结合律, 即:

(V1∪V2) ∪V3=V1∪ (V2∪V3) =V1∪V2∪V3

证明由交换律, (V1∪V2) ∪V3=V3∪ (V1∪V2) , 所以只要证明 (V1∪V2) ∪V3=V1∪V2∪V3, 即[[V1+V2]+V3]=[V1+V2+V3]。若用在x=V1.cols的重数表示则为:

sign (sign (V1.rep (x) +V2.rep (x) ) +V3.rep (x) )

=sign (V1.rep (x) +V2.rep (x) +V3.rep (x) )

由第2节辅助等式 (7) , 取x=V1.rep (x) +V2.rep (x) , y=V3.rep (x) 即得待证的等式。

有负重数时结合律不成立。如设V1、V2={ (7-1) }, V3={{ (7 1) }。则 (V1xV2) xV3=空, 而V1x (V2xV3) ={ (7-1) }。

定理24 消除重复集合并的差分 V和W都是正SQL表, 消除重复集合并V∪W的差分是:

d (V∪W) =signwhole (dV+dW) (28)

证明由V∪W=[V+W], d (V∪W) =d[V+W]=signwhole (dV+dW) 。

6.3 集合交与差

这里只讨论消除重复的集合交intersect (∩) 和集合差except (¬) 。根据集合论, 若V、W无重复, 成立等式 (V∩W) + (V¬W) =V。

藉助于量词, 定义一般表 (重数可大于1或负) V和W的交和差如下:

定义14 交与差 SQL表V和W可加, 分别称:

V∩W=[V]∃W{V.cols=W.cols&sign (V.rep) =sign (W.rep) }

V¬W=[V]∃W{V.cols=W.cols&sign (V.rep) =sign (W.rep) }

为V, W的交V∩W和差V¬W。

当V和W正时, 不论是否有重复, 该定义与SQL的intersect和except计算结果一致。

设V、W规范, x=V.cols, y=W.cols。由此可计算集合交与差在 (x0) 的重数:

V∩W.rep (x0) =[V].rep (x $0) * s i g n \sum_{F} W . r e p$ (y) 2

V¬W.rep (x0) =[V].rep (x $0) * (1 - s i g n \sum_{F} W . r e p$ (y) 2)

因V、W规范, 故F={V.cols=W.cols&sign (V.rep) =sign (W.rep) }是一对一的。但求和号不可取消, 因为可能有不存在y的情况, 这时求和结果为0。

交的交换律是明显的。下面的定理证明交满足结合律。

定理25 交的结合律表V、W、P规范可加, 则 (V∩W) ∩P=V∩ (W∩P) 。

证明设x=V.cols, y=W.cols, z=P.cols。则:

其中F1={x=y&sign (V.rep) =sign (W.rep) }, F2={x=z&sign (V.rep) =sign (P.rep) }。另一方面:

由第2节的辅助公式 (7) , 求和号内的sign可去:

上式=[V].rep (x $0) * s i g n \sum_{F 1 & F 3} (W . r e p$ (y) 2P.rep (z) 2)

其中F3={y=z&sign (V.rep) =sign (W.rep) 。显然F1&F2=F1&F3。由此:

V∩ (W∩P) .rep (x0) = (V∩W) ∩P.rep (x0)

由此结合律得证。

交的结合律没有正表限制。

6.4 交与差的差分

当V无重复时, 由定义14交和差对V的差分是线性的。故:

V＼d (V∩W) =dV∩W, V＼d (V¬W) =dV¬W

消除重复集合交满足交换律:V∩W=W∩V。由多元展开公式得:

d (V∩W) = (dV∩W0) + (V∩dW) (29)

集合差不满足交换律。但V¬W=V-V∩W, 由此

W＼d (V¬W) =-W＼d (V∩W) =- (V∩dW)

于是得:

d (V¬W) = (dV¬W0) - (V∩dW) (30)

总结上面的推导得下述定理。

定理26 交与差的差分 V和W都是无重复可加SQL表, 集合交V∩W与集合差V¬W的差分分别可用式 (29) 、 (30) 计算。

V和W可重复时式 (29) 、 (30) 的dV和dW要替换成d[V]和d[W]。

7 应用例:关系除法

作为本文所述理论的一个应用, 本节讨论关系代数中定义的关系除法, 目标是导出计算关系商及其差分的SQL查询语句。计算关系商的SQL查询语句虽然在数据库的教科书中可以找到, 但导出过程却罕有记载。

二元关系A (x, y) 除以一元关系B (y) 的商, 是一个新一元关系, 记作A/B, 是A中与B全部y对应的x。如下面的数字例所示:

例7 关系除法的数字例。

关系A (x, y) 和B (y) 的商也可定义为是使S (x) B (y) ⊆A (x, y) 的最大S。由此有A=SB+R, R是该除法的余关系。上面例中的余关系是{ (2 1) }。

关系B可限定为非空。因为若B空则SB也空, S不定。

余关系R为空时关系除法是笛卡尔积的逆运算:

(A/B) B=A (SB) /B=S

等式A=SB+R的等号两边对x作消除重复投影。由于S的最大性, R中每一x不对应B中的全部y, R与SB不相交, 消除重复投影对加可分配。由此得:

A[x]= (SB+R) [x]=S+R[x]

S=A[x]-R[x] (31)

故要计算S可以先计算R[x]。故 (31) 等号两边与B作笛卡尔积, 然后用A-R代替SB, 整理后得

A[x]B-A=R[x]B-R (32)

A[x]B与R[x]B是笛卡尔积。式 (32) 等号两边各是把A与R补充到一个笛卡尔积的关系, 称为A与R的补。该等式说明A与R的补相同, 记作R'。例7中A与R的补是{ (2 2) }。由定义, R[x]中的每一x均不对应B的全部y, 故R'与R有相同的x (但每一x对应的y不同) , 即R'[x]=R[x]。于是:

R[x]=R'[x]= (R[x]B-R) [x]= (A[x]B-A) [x]

S=A[x]- (A[x]B-A) [x]

该式两个减运算的减项都是被减项的子集, 减运算可替换为集合差, 得关系商的一种计算方法:

S=A[x]¬ (A[x]B¬A) [x] (33)

进一步用不存在量词替换集合差:

S=A[x]∃ (A:a1[x]B∃A:a2{x=a1.x&y=B.y}) {a.x=a1.x}

最后注意到A、a1和a2是同一表, 且有条件{a.x=a1.x}相联系。因量词次方可以使用主方的列, 故a1可省略而把条件中的a1.x改成A.x, 得到了较为高效的计算A/B的表达式:

S=A[x]∃ (B∃A:a1{x=A.x&y=B.y}) (34)

(a1为原a2) 对应SQL语句:

select distinct x from A where not exists

(select * from B where not exists

(select * from A a1 where x=A.x and y=B.y) )