差分相关

差分相关（精选7篇）

差分相关 篇1

0 引言

AIS (船舶自动识别系统) 是一种海上无线通信系统, 它能够自动地连续发射本船静态、动态等相关信息, 同时也自动地接收周围船舶发射的类似信息, 并与海岸AIS基站进行信息交互, 从而实现船舶之间、船岸之间的通信。传统AIS监测受到了距离的限制, 星载AIS接收系统应用而生, 它通过卫星接收AIS终端的消息, 同时将信息反馈给岸上的监测中心, 以达到在更大范围内监测船舶的目的。然而星载AIS系统中, 发射机与接收机之间存在大范围时间延迟、卫星的相对运动引起的大范围的多普勒频移等问题, 会导致接收到的AIS信号判决错误, 因此, 必须进行帧同步。

AIS信号是通过GMSK调制的, 从船台到卫星的无线信道可近似为AWGN信道。针对GMSK信号的帧同步问题, Barker[1]最早提出相关识别器, 在接收信号中寻找已知的同步序列信息, Choi Z Y和Lee Y H针对其鲁棒性不强、适用范围太窄提出了双相关算法[2], 但是仍没有解决抗频偏范围小的问题, 无法满足星载AIS信号的要求。1999年, Huang Yung Liang提出快速FFT转换器[3], 即将连续相位频移键控信号CPFSK (GMSK是其中一种形式) 经过基带频率鉴别器, 对鉴别器输出的信号做FFT运算, 根据频谱峰值点判断同步序列的有无, 但它存在的缺点是判断不够准确, 只能作为一种粗略的判定。2005年, James E.Hicks, 针对GMSK/AIS信号检测在FPGA硬件中的实现, 提出了差分卷积法[4]来定位帧头的位置, 该方法有较好的抗频偏特性, 但是在低信噪比下性能不佳。

为了提高低信噪比下帧同步性能, 本文在以连续序列作帧同步码的帧同步方法[5,6]如传统相关法[1]、基于最大似然法则[7,8,9,10]、似然比检验[11,12]的基础上, 提出了以间隔式序列作帧同步码, 通过差分相关来定位帧头位置的方法, 并给出了仿真实验结果。

1 AIS消息帧结构与同步码

AIS信号主要使用自组织时分多址 (SO-TDMA) 协议工作。该协议根据GB/T7496-1978分组结构定义中所规定的HDLC高级数据链路控制规程, 采用信息分组结构, 每帧信息256 bit, AIS消息帧结构如图1所示[13]。

训练序列长度为24比特, 是由0、1交替的数码组成的序列。开始标志和结束标志长度均为8比特, 其位模式相同且为01111110, 有6个连续的1, 但不需要进行插0位填充, 分别表示传输数据信息的开始和结束。AIS信号的传输速率为9 600 bps。

对于传统的AIS接收机, 信号质量比较好, 训练序列作同步码估计出的准确度已经能够满足要求, 当接收机检测到训练序列到来时, 很快就能建立帧同步。

对于星载AIS接收机来说, 由于信号的时延范围大, 多普勒频移较严重, 多用户信号冲突等, 需要信号分离、频移估计、信道估计等, 而且这些参数之间又有相互依赖, 本文的方案是先进行帧同步, 再进行后面的处理。由于问题的复杂性, 用传统的训练序列估计精度不能满足要求, 为此将AIS帧结构中训练序列、开始标志和结束标志联合起来定义为特征序列, 以此作为同步码。其中训练序列和开始标志相连, 与结束标志是不连续的, 它们以分散 (间隔) 的形式插入在AIS帧中, 中间隔了一定数量的信息码元 (一般是184个码元) 。将特征序列也称为间隔式[6]同步码。

星载AIS接收系统[14]主要用于接收AIS信号, 高效地完成对船舶的检测, 并将接收到的船舶信息下发到地面相关接收系统。其对信号的检测可设计如图2所示。

2 差分相关同步算法

由AIS帧结构组成的二进制消息序列, 通过NRZI编码后按GMSK调制, 对应的复包络信号可以表示为:

其中:

其中, g (t) 为高斯滤波器的矩形脉冲响应, 其取值区间为: (0, LT) , q (t) 为相位脉冲响应。L为高斯滤波器持续码元个数, a={an}为信息序列, 取值为{1, -1}, 调制指数h=0.5。

星载AIS接收机收到的信号 (暂时不考虑多用户信号冲突) 可以表示为:

其中, Eb是码元能量, Tb为码元周期, Δf为频偏, θ为相移, τ为时延, w (t) 为复值白高斯噪声。

设由同步码产生的本地调制信号为s (t) , 不连续的同步码之间的信号值补零。s (t) 与r (t) 的码元周期Tb相同。为方便公式推导, r (t) 忽略噪声。差分相关算法具体流程如图3所示。

在AIS基带信号的处理中, 处理的信号都要经过接收机采样, 处理的都是数字信号, 因此, s (t) 、r (t) 以Ts为间隔采样得到s (n) 、r (n) , 且Tb=QTs, Q为过采样因子。

s (n) , r (n) 经过1比特差分处理后的结果分别表示为:

假设Δs (n) 包含的码元数为N, 其中训练序列和开始标志含码元数为N1, 结束标志含码元数为N2, 数据和帧校验序列含码元数为N0, Δr (n) 包含的码元数为M。

定义1互相关表示如下:

其中, m为可能的帧起始时刻采样序号, 变化范围最大为0到 (M-N+1) Q-1, 实际取值范围可由卫星的高度来决定, 通过最大时延来确定其具体范围。

由于s (t) 中不连续的同步码之间信号值补零, 则:

所以式 (9) 化简为:

其中:

其中, 即为估计的相应采样率下的帧起始时刻。此时, 还可以通过下式得频偏的粗略估计:

算法中部分程序设计如下:

GMSK基带调制部分程序:

差分相关算法抗噪性能的部分程序:

3 仿真结果

按照ITU-R M.1371.1998AIS国际标准, AIS帧结构和码元长度固定, 时隙为26.67 ms, 星载AIS信号时延范围为0~71Tb, 频偏的范围是-3.8~+3.8 KHz, 噪声可近似为高斯白噪声, 发射端信号调制时各参数值一般情况下是特定的。仿真实验中, 接收到的星载AIS信号, 各参数值须与发射端一致, 即GMSK调制中, 归一化3 d B带宽BT=0.4, 码元速率Rb=9 600 bps, 高斯滤波器持续码元个数L=3。Matlab编程模拟的加频偏和噪声的接收信号r (t) 是由含时延的AIS帧构成的, 码元长度为M取327。其中, AIS帧包含256个码元, 时延τ在0~71Tb范围内取值, 余下部分由随机码元填充。由图1中AIS帧结构可知, 由训练序列、开始标志和结束标志组成的同步码是间隔的, 码元长度N为40, 仅有训练序列和开始标志组成的同步码是连续的, 码长为32。仿真结果如图4-图7, 各图中纵轴为时延估计均方误差, 计算方法为, 其中K为实验中重复估计的次数。

以间隔式序列作同步码, 分别用本文提出的差分相关和差分卷积法[4]在不同信噪比下的时延估计如图4所示, 从中可以看出当信噪比小于7 d B时, 本文的差分相关法抗噪性能明显好于差分卷积法[4];图5是同步算法的抗频偏性能, 差分相关法和差分卷积法[4]的抗频偏性能接近, 均比较好;由图6可以看出, 差分相关法采用间隔式同步码估计误差明显小于连续式同步码;不同采样率的情况下, 差分相关法的估计性能如图7所示, 采样率越高, 实验估计的误差越小。

综上实验结果可得, 在低信噪比下, 本文提出的差分相关法抗噪性优于差分卷积法[4], 且有较好的抗频偏性。随着采样率提高及同步码长度增加, 本文所提方法抗噪性能进一步提高。但是, 此方法的稳定性稍差一些, 这也是今后研究需要进一步提高的地方。

4 结语

本文首先对AIS消息帧结构和星载AIS信号检测结构进行了简单的阐述, 指出帧同步是AIS信号检测端所有工作的开始, 直接影响后面的检测性能。针对帧同步过程中, 遇到的AIS信号信噪比较低, 频偏范围比较大等问题, 提出了差分相关的帧同步方法, 该方法应用于星载AIS相干接收机中的AIS信号检测时, 能很好地消除频偏对帧同步的影响, 且在低信噪比下, 误差更小, 帧同步性能优于差分卷积法。

摘要：在星载AIS接收机中, 船舶信号在传输过程中产生的大范围时延和多普勒频移, 给正确解码带来了困难。针对这一问题, 基于AIS帧结构特点, 提出一种差分相关帧同步算法。算法中将AIS帧结构中训练序列、开始标志和结束标志设计为间隔式特征序列作为同步码, 通过差分相关函数来实现帧同步。仿真实验结果表明, 该算法有较好的抗频偏特性, 且在低信噪比下, 性能要优于差分卷积法。

关键词：AIS信号,同步码,帧同步,差分相关

差分相关 篇2

GPS差分技术的越来越成熟, 使得GPS定位精度得以大大提高, 相对于惯性测量、电磁波测距等这些经典测量技术来说, GPS具有观测站间无需通视、定位精度高、观测时间短的特点, 以及它能够实施全球性全天候全天时的连续不断的三维导航定位测量的特性, 为广大用户提供了高精度多用途的导航定位服务。这也就难怪美国将GPS技术视为20世纪最重大的科技成就之一了[1]。

GPS差分技术包括静态差分, 准动态差分, 实时动态差分三种, 而实时动态差分的快速发展, 加快了GPS定位技术的应用, 实时动态差分经历了从常规实时动态测量和到实时动态相位测量的伟大突破。

常规实时动态差分也叫RTD (Real Time Differential) , 是基于测距码的一种实时差分技术, 该定位技术通过在基准站上利用已知坐标求出测站至卫星的距离, 并将其与含有误差的测量距离比较, 然后利用一个滤波器将此差值滤波并求出其偏差, 并将所有卫星的测距误差传输给用户, 用户利用此测距误差来改正测量的伪距。最后, 用户利用改正后的伪距求出自身的坐标;而实时动态相位差分也叫RTK (Real Time Kinematic) , 是基于载波的一种实时差分技术, 其基本思想, 是在基准站上安置一台GPS接收机, 对所有可见的卫星进行实时连续的观测, 并将其观测数据, 通过无线电传输设备, 实时的发送给用户观测站。在用户站上, GPS接收机在接受卫星信号的同时, 通过无线电接收设备, 接收基准站传输的观测数据, 然后根据相对定位原理, 实时的计算并显示用户站的三维坐标及其精度[2]。

目前RTD和RTK是应用比较广泛的两种差分定位方式。在实际的工程应用中, 这两种定位方式的定位精度如何, 本文将通过实验, 论证RTD与RTK之间的定位精度。

1 实验方法与数据分析

1.1 实验过程

实验过程中使用中海达双频RTK, 中海达信标机, 对A、B、C、D四个E级GPS控制点进行多次独立测量, 计算出各点中误差和漂移量进行比较。

1.2 数据分析

四个观测点的数据如下图所示, 图中“x”表示使用RTK测量的点坐标, “+”表示是使用信机测量的点坐标, 三角点标示的位置是已知点。

从以上图中可以看出, 不管是RTK还是RTD其测量坐标都在已知点坐标周围漂移, 由实测数据可得, 采用RTD技术测量的数据漂移量比RTK的明显高出许多。使用RTK测量时, 其点位漂移量基本集中在0~0.05m之间, 而RTD测量的点位漂移量较大, 像正弦曲线的变化, 最大的点位漂移达到0.9m, 主要集中在0~0.3之间。漂移量越大, 说明点的离散度也越大, 这对定位精度也会产生一定的影响, 其离散度我们用相对已知点中误差来表示, 如下表2.2-3所示, 使用RTK进行测量时, 点位中误差在0~0.1之间, 主要集中在0.05以下, 而使用信标机所测量的点位中误差最大可以达到0.6m多, 最小也有0.4m, 可以看出, 实际测量中RTK的定位精度比信标机的定位精度要高, 这也反映出了载波相位差分定位精度比伪距差分定位的精度要高。

对其原因, 我们分析如下:

1) RTK采用的是载波相位差分测量原理, 通过测量卫星与接收机之间有多少个波长来测量距离的。在传播过程中, 虽然波的强度虽然会变弱, 但是波形没有改变, 而且大气环境对其的影响就会比较小;而信标机是采用伪距差分测量, 通过测量卫星到接收机的时间来确定其距离的, 由于信号在对流层, 电离层的传播过程中会发生时间延迟, 对测量精度产生较大的影响;

2) RTK是双频载波, 而信标机是单频。双频载波可以通过自身的两个载波求差, 得出的观测方程大大削弱电离层和对流层的影响, 提高定位精度;而伪距差分定位是通过基准站向移动站发送坐标差信息进行定位的, 而且随着距离的越来越远, 其定位精度也会越来越低。

3 结语

本文通过研究GPS伪距差分技术和载波相位差分技术的基本原理, 结合实例, 通过点位中误差, 证实载波相位差分定位精度高于伪距差分定位, 主要观点如下:

3.1 载波相位采用的是测相伪距观测, 即通过波长进行伪距的计算, 由于信号在传播过程中, 波形发生的改变很小, 基本上维持不变, 这样可以获得较高的定位精度;而伪距差分采用的是测码伪距观测, 通过计算时间差进行定位, 由于信号在大气中传播的过程中, 会产生延迟, 大大降低了定位的精度。虽然两者同为差分GPS, 移动台都要通过接受基准站的差分信息进行高精度定位, 但是载波相位差分采用双频接收技术, 即同时接收L1载波和L2载波的信号, 然后进行单差改正, 消除环境误差的影响。

3.2 由点位中误差的表格可以看出, 使用RTK进行定位测量时, 中误差最大到0.07m, 最小到0.02m, 根据工程测量规范 (如表2所示) , 可以得出, 使用RTK至少可以进行大比例尺的测量要求, 而使用RTD进行定位时, 可以满足小比例尺的测量要求。

摘要：伪距差分和载波相位差分是差分GPS的两大定位技术, 在各领域都有广泛的应用。本文首先介绍GPS的定位原理及其误差分析, 然后介绍伪距差分原理和载波相位差分原理, 最后结合实例, 通过点位漂移量和点位中误差, 证实载波相位差分定位精度高于伪距差分定位的精度。

关键词：伪距差分,载波相位差分,精度

参考文献

[1]张勤, 李家权, 等.GPS测量原理及应用[M].北京:科学出版社, 2006:42-70.

SQL差分 篇3

结构查询语言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)={\displaystyle \sum _{\text{t}\in \text{V}\&\text{x}=\text{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) 的任意值$\underset{¯}{\text{t}}0$在V、W的重数相等:V.rep$(\underset{¯}{\text{t}}0)=\text{W}.\text{r}\text{e}\text{p}(\underset{¯}{\text{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

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)={\displaystyle \sum _{\text{x}\supseteq \underset{¯}{\text{z}}0}\text{V}}.\text{r}\text{e}\text{p}$ (x) (3)

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

V是无重数形式:

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

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

V有rep列:

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

select z, sum (rep) rep from V group by$\underset{¯}{\text{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, 只要证明等号两边对任意值$\underset{¯}{\text{z}}0$的重数相等。由式 (3) 得:

(V1+V2) (z) .rep (z$0)={\displaystyle \sum _{\text{x}\supseteq \underset{¯}{\text{z}}0}(}\text{V}1+\text{V}2).\text{r}\text{e}\text{p}(\text{x})$

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

上式$={\displaystyle \sum _{\text{x}\supseteq \underset{¯}{\text{z}}0}\text{V}}1.\text{r}\text{e}\text{p}$ (x) $+{\displaystyle \sum _{\text{x}\supseteq \underset{¯}{\text{z}}0}\text{V}}2.\text{r}\text{e}\text{p}$ (x) $=\text{V}1(\underset{¯}{\text{z}}).\text{r}\text{e}\text{p}$ (z$0)+\text{V}2(\underset{¯}{\text{z}}).\text{r}\text{e}\text{p}(\underset{¯}{\text{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) 得:

$\text{V}(\underset{¯}{\text{z}})$ (y) .rep (y$0)={\displaystyle \sum _{\underset{¯}{\text{z}}0\supseteq \text{y}0}\text{V}}(\underset{¯}{\text{z}}).\text{r}\text{e}\text{p}$ (z$0)={\displaystyle \sum _{\underset{¯}{\text{z}}0\supseteq \text{y}0}}{\displaystyle \sum _{\text{x}0\supseteq \underset{¯}{\text{z}}0}\text{V}}.\text{r}\text{e}\text{p}$ (x)

$={\displaystyle \sum _{\text{x}0\supseteq \text{y}0}\text{V}}.\text{r}\text{e}\text{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)=\text{s}\text{i}\text{g}\text{n}\left({\displaystyle \sum _{\text{x}\subseteq \text{z}0}\text{V}}.\text{r}\text{e}\text{p}(\text{x})\right)$ (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]$=\text{V}[\underset{¯}{\text{z}}]‚[\text{V}+[\text{W}]]=[\text{V}+\text{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)=\text{s}\text{i}\text{g}\text{n}{\displaystyle \sum _{\underset{¯}{\text{x}}\supseteq \underset{¯}{\text{z}}0}[}\text{V}]=\text{s}\text{i}\text{g}\text{n}$${\displaystyle \sum _{\text{x}\supseteq \underset{¯}{\text{z}}0}\text{s}}\text{i}\text{g}\text{n}(\text{V}.\text{r}\text{e}\text{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)*\text{λ}\text{F}=\left({\displaystyle \sum _{\underset{¯}{\text{z}}=\underset{¯}{\text{z}}0}\text{V}}.\text{r}\text{e}\text{p}(\text{p},\text{z})\right)*\text{λ}\text{F}$

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

上式$={\displaystyle \sum _{\underset{¯}{\text{z}}=\underset{¯}{\text{z}}0}(}\text{V}.\text{r}\text{e}\text{p}$ (p, z) $*\text{λ}\text{F})={\displaystyle \sum _{\underset{¯}{\text{z}}=\underset{¯}{\text{z}}0}\text{V}}\{\text{F}\}.\text{r}\text{e}\text{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}=\left\{\left(\text{x}\text{v}\text{r}\text{e}\text{p}\text{t}{\displaystyle \sum _{\text{y}\supseteq \text{t}}\text{w}}\text{r}\text{e}\text{p}(\text{y}):\text{t}\text{r}\text{e}\text{p}\right)|(\text{x}\text{v}\text{r}\text{e}\text{p})\in \text{V}‚(\text{y}\text{w}\text{r}\text{e}\text{p})\in \text{W}\right\}\\ \text{V}^\text{W}\text{在}\text{V}\text{和}\text{t}\text{消}\text{除}\text{重}\text{复}\text{投}\text{影}\end{array}$

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

$=\left\{\left(\text{x}\text{v}\text{r}\text{e}\text{p}\text{t}\text{s}\text{i}\text{g}\text{n}{\displaystyle \sum _{\text{y}\supseteq \text{t}}\text{w}}\text{r}\text{e}\text{p}(\text{y}):\text{t}\text{r}\text{e}\text{p}\right)|(\text{x}\text{v}\text{r}\text{e}\text{p})\in \text{V}‚(\text{y}\text{w}\text{r}\text{e}\text{p})\in \text{W}\right\}$

这里两种投影各有两种表示方法。第一种表示方法可明确地表示出计算过程, 而第二种方法与一维表的方法一致, 着重于最后结果的表达。例如, 若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) 的重数是:

$\text{W}\underset{¯}{\text{t}}(\text{V}^\text{W}).\text{r}\text{e}\text{p}$ (x$0\underset{¯}{\text{t}}0)=\text{v}\text{r}\text{e}\text{p}$ (x$0)^{\displaystyle \sum _{\text{y}\supseteq \underset{¯}{\text{t}}0}\text{w}}\text{r}\text{e}\text{p}$ (y)

$\text{W}\underset{¯}{\text{t}}[\text{V}^\text{W}].\text{r}\text{e}\text{p}(\underset{¯}{\text{x}}0\underset{¯}{\text{t}}0)=\text{v}\text{r}\text{e}\text{p}$$(\underset{¯}{\text{x}}0)^\text{s}\text{i}\text{g}\text{n}$${\displaystyle \sum _{\text{y}\supseteq \underset{¯}{\text{t}}0}\text{w}}\text{r}\text{e}\text{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) 第一式。只要证明两边在$(\underset{¯}{\text{z}}0\underset{¯}{\text{t}}0)$的重数相等。由式 (3) 及笛卡尔积定义得:

VW (zt) .rep (z0t$0)={\displaystyle \sum _{\text{x}\text{y}\supseteq \underset{¯}{\text{z}}0\underset{¯}{\text{t}}0}(}\text{V}\text{W}.\text{r}\text{e}\text{p}$ (xy) )

$={\displaystyle \sum _{\text{x}\text{y}\supseteq \underset{¯}{\text{z}}0\underset{¯}{\text{t}}0}(}\text{V}.\text{r}\text{e}\text{p}$ (x) *W.rep (y) )

$={\displaystyle \sum _{\text{x}\supseteq \text{z}0}\text{V}}.\text{r}\text{e}\text{p}$ (x) $*{\displaystyle \sum _{\text{y}\supseteq \underset{¯}{\text{t}}0}\text{W}}.\text{r}\text{e}\text{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)={\displaystyle \sum _{\text{V}\text{y}\supseteq \text{V}\underset{¯}{\text{t}}0}(}\text{V}^\text{W}).\text{r}\text{e}\text{p}$ (x0y0)

$={\displaystyle \sum _{\text{V}\text{y}\supseteq \text{V}\underset{¯}{\text{t}}0}(}\text{V}.\text{r}\text{e}\text{p}$ (x0) ^W.rep (y) )

V.rep (x0) 是常数:

上式=V.rep$(\text{x}0)^{\displaystyle \sum _{\text{y}\supseteq \underset{¯}{\text{t}}0}\text{w}}\text{r}\text{e}\text{p}$ (y)

又由式 (3)

${\displaystyle \sum _{\text{y}\supseteq \underset{¯}{\text{t}}0}\text{w}}\text{r}\text{e}\text{p}$ (y) =W (t) .rep (t0)

V.rep$(\text{x}0)^{\displaystyle \sum _{\text{y}\supseteq \underset{¯}{\text{t}}0}\text{w}}\text{r}\text{e}\text{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)={\displaystyle \sum _{\text{x}\text{y}\supseteq \text{z}0\text{t}0}\text{V}}\text{W}\{\text{F}\}.\text{r}\text{e}\text{p}$ (xy)

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

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

上式$={\displaystyle \sum _{\text{x}\supseteq \underset{¯}{\text{z}}0}\text{V}}.\text{r}\text{e}\text{p}$ (x) ${\displaystyle \sum _{\underset{¯}{\text{y}}\supseteq \underset{¯}{\text{t}}0}\text{W}}.\text{r}\text{e}\text{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}的特征函数为:

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

$=\text{s}\text{i}\text{g}\text{n}{\displaystyle \sum _{\text{F}}\text{W}}.\text{r}\text{e}\text{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)*\text{s}\text{i}\text{g}\text{n}{\displaystyle \sum _{\text{t}\text{r}\text{u}\text{e}}(}\text{W}.\text{r}\text{e}\text{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) $={\displaystyle \sum _{\text{y}\supseteq \text{t}}\text{W}}.\text{r}\text{e}\text{p}(\text{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$\&\text{a}.\text{r}\text{e}\text{p}={\displaystyle \sum _{\text{x}\supseteq \text{z}}\text{V}}.\text{r}\text{e}\text{p}(\text{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)*\text{s}\text{i}\text{g}\text{n}{\displaystyle \sum _{\text{F}}\text{W}}.\text{r}\text{e}\text{p}$ (y) 2

V¬W.rep (x0) =[V].rep (x$0)*(1-\text{s}\text{i}\text{g}\text{n}{\displaystyle \sum _{\text{F}}\text{W}}.\text{r}\text{e}\text{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)*\text{s}\text{i}\text{g}\text{n}{\displaystyle \sum _{\text{F}1\&\text{F}3}(}\text{W}.\text{r}\text{e}\text{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) )

再推导式 (34) 的差分。分解成四个查询的嵌套, 其中F是“a1.x=A.x&B.y=a1.y”:

由式 (9) 和定理19, 各自的差分为:

为计算F必须把A^分配到dZ2内部, 即dB∃A0:a1{F}、B^dA:a1{F}和B^dA:a1{F}上, 同时也把A的列名加入相应的投影中。得:

下面是相应的SQL语句:

8 后 记

为验证上述理论, 本文研制了一个试验系统。对于任意一个查询Q及所用各表的结构定义, 可生成Q的差分dQ。有兴趣研究的读者可发email到rslou@163.com免费索取。因程序功能有限, 且还有一些为简化编程所加, 而在实际应用中较难满足的限制条件, 故只能作研究用。

参考文献

[1]何明.从实践中学习Oracle/SQL[M].清华大学出版社, 2004.

[2]Information Technology-Database Language SQL.1992.http://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt.

[3]施伯乐.计算机科学中的数学基础[M].科学出版社, 1989.

[4]谷超豪.数学词典[M].上海辞书出版社, 1992.

特殊的差分方程 篇4

对于常系数线性差分方程而言, 它的解法已经相当完善了.而对于非线性差分方程而言, 它的类型广, 形式多样, 所以并没有固定的解法.本文的主要思想就是通过各种变形将这类非线性差分方程转变为线性差分方程求解.

定理1 差分方程an=λan-1+ban-2的特征方程为x2-λx-b=0.若其特征根x1, x2为一对相异实根, 则差分方程的通解为an=c1x${}_1^n$+c2x${}_2^n$.

若x1=x2, an= (c1+c2n) x${}_1^n$.

若x1=δ+iω, x2=δ-iω, an=c1ρncosnθ+c2ρnsinnθ.

其中$\rho =\sqrt{\delta {}^2+\omega {}^2}‚\theta =\arctan \frac{\omega }{\delta }.$

定理2 差分方程$a{}_n=\lambda +\frac{b}{a{}_{n-1}}$的特征方程为x2-λx-b=0.若其特征根x1, x2为一对相异实根, 则差分方程的通解为$a{}_n=\frac{c{}_{1}x{}_1^{n+1}+c{}_{2}x{}_2^{n+1}}{c{}_{1}x{}_1^n+c{}_{2}x{}_2^n}.$

若$x{}_1=x{}_2‚a{}_n=\frac{[c{}_1+c{}_2(n+1)]x{}_1^{n+1}}{(c{}_1+c{}_{2}n)x{}_1^n}=\frac{c{}_1+c{}_2(n+1)}{c{}_1+c{}_{2}n}x{}_1.$

$\begin{array}{l}\text{若}x{}_1=\delta +i\omega ‚x{}_2=\delta -i\omega ‚\\ a{}_n=\frac{c{}_1\rho {}^{n+1}\cos (n+1)\theta +c{}_2\rho {}^{n+1}\sin (n+1)\theta }{c{}_1\rho {}^n\text{c}\text{o}\text{s}n\theta +c{}_2\rho {}^n\text{s}\text{i}\text{n}n\theta }.\end{array}$

其中$\rho =\sqrt{\delta {}^2+\omega {}^2}‚\theta =\arctan \frac{\omega }{\delta }.$

证明 令$a{}_n=\frac{b{}_{n+1}}{b{}_n}$, 代入原差分方程, 得bn+1=λbn+bbn-1.应用常系数线性差分方程的解法即可得结论.

为简化计算, 设差分方程$a{}_n=\frac{a{}_{n-1}}{2}+\frac{k}{a{}_{n-1}}(k>0)$中$k=\frac{1}{2}.$

令$a{}_n=\frac{b{}_n}{c{}_n}$代入上式.

$\begin{array}{l}\text{令}\{\begin{array}{l}b{}_n=b{}_{n-1}^2+c{}_{n-1}^2‚\\ c{}_n=b{}_{n-1}c{}_{n-1}‚\end{array}\\ \therefore b{}_n+c{}_n=(b{}_{n-1}+c{}_{n-1}){}^2‚\\ \therefore b{}_n+c{}_n\ge 0(n\ge 2).\end{array}$

假设b1+c1≥0, ∴bn+cn≥0 (n≥1) .

应用线性差分方程的解法bn+cn= (b1+c1) 2n-1.

$\begin{array}{l}\text{同}\text{理}b{}_n-c{}_n=(b{}_1-c{}_1){}^{2{}^{n-1}}‚\\ 2b{}_n=(b{}_1+c{}_1){}^{2{}^{n-1}}+(b{}_1-c{}_1){}^{2{}^{n-1}}‚\\ 2c{}_n=(b{}_1+c{}_1){}^{2{}^{n-1}}-(b{}_1-c{}_1){}^{2{}^{n-1}}‚\\ a{}_n=\frac{2b{}_n}{2c{}_n}=\frac{(b{}_1+c{}_1){}^{2{}^{n-1}}+(b{}_1-c{}_1){}^{2{}^{n-1}}}{(b{}_1+c{}_1){}^{2{}^{n-1}}-(b{}_1-c{}_1){}^{2{}^{n-1}}}.\end{array}$

$\begin{array}{l}\text{令}c{}_1=1‚b{}_1=a{}_1‚\\ a{}_n=\frac{(a{}_1+1){}^{2{}^{n-1}}+(a{}_1-1){}^{2{}^{n-1}}}{(a{}_1+1){}^{2{}^{n-1}}-(a{}_1-1){}^{2{}^{n-1}}}.\end{array}$

对于任意常数k, 差分方程$a{}_n=\frac{a{}_{n-1}}{2}+\frac{k}{a{}_{n-1}}(k>0).$

$\begin{array}{l}\text{令}a{}_n=\sqrt{2k}b{}_n‚a{}_{n-1}=\sqrt{2k}b{}_{n-1}‚\\ \therefore b{}_n=\frac{b{}_{n-1}}{2}+\frac{1}{2b{}_{n-1}}‚\\ b{}_n=\frac{(b{}_1+1){}^{2{}^{n-1}}+(b{}_1-1){}^{2{}^{n-1}}}{(b{}_1+1){}^{2{}^{n-1}}-(b{}_1-1){}^{2{}^{n-1}}}\\ =\frac{\left(\frac{a{}_1}{\sqrt{2k}}+1\right){}^{2{}^{n-1}}+\left(\frac{a{}_1}{\sqrt{2k}}-1\right){}^{2{}^{n-1}}}{\left(\frac{a{}_1}{\sqrt{2k}}+1\right){}^{2{}^{n-1}}-\left(\frac{a{}_1}{\sqrt{2k}}-1\right){}^{2{}^{n-1}}}‚\\ \therefore a{}_n=\sqrt{2k}b{}_n\\ =\sqrt{2k}\cdot \frac{\left(\frac{a{}_1}{\sqrt{2k}}+1\right){}^{2{}^{n-1}}+\left(\frac{a{}_1}{\sqrt{2k}}-1\right){}^{2{}^{n-1}}}{\left(\frac{a{}_1}{\sqrt{2k}}+1\right){}^{2{}^{n-1}}-\left(\frac{a{}_1}{\sqrt{2k}}-1\right){}^{2{}^{n-1}}}.\end{array}$

定理3 差分方程$a{}_n=\frac{a{}_{n-1}}{2}+\frac{k}{a{}_{n-1}}(k>0)$的通解为:

参考文献

差分跳频技术探析 篇5

要探究差分跳频技术的原理, 首先让我们来看一下这个公式Fn=G (Fn-1, Xn) , 其中Fn为当前的频率值, 上一跳为Fn-1, Xn则代表当前时刻的数据符号。而G (·) 可以看做一个G函数, 而且G函数可以实现正变换和逆变换。G函数的正变换是上一跳时刻的频率值和当前数据符号通过G转换成当前时刻频率值, 逆变换则是上一跳和当前的频率值通过G变换成当前时刻数据。这就要求首先要用接收端的数字化宽带接受信号后, 由FFT分析出上一跳和当前的频率值, 经G函数逆变换求的当前时刻数据。

因为差分跳频技术用的是软件无线电的方式, 所以就简化了系统有关硬件方面的电路结构。而解调的过程则是在接收端运用A/D采样化模拟信号为数据信号, 接着和吓一跳采集来的数据进行FFT运算, 得到当前时刻频率。根据上图, 前一次的频率点如果和当前的不相等, 则为不同步, 进而不能确定解调频率的工作。反之只有同步后才能确定真正的解调码。

这些原理决定了差分跳频技术的几大特性。首先, 有关的G函数具有产生跳频图案和调制解调的功能, 可以说G函数是这一技术的核心。G函数的变换, 不仅使跳频控制和数传过程自动产生了跳频图案, 而且使频率和数据之间“书-频”编码得以实现。但是对于G函数的探究还应继续深入, 因为数据流的难以控制的特性, 直接的影响了跳频图案的性能。其次, 作为一种异步跳频体制的差分跳频对于任意时刻的发端频率是无法预测的, 从而则是消除了频率符合其的需要。最后, 这种技术所用的体制还是一种相关的跳频体制。这是由于差分跳频所用的G函数, 使得上下频率是息息相关的, 就连解调还原都是依照这种相关性, 也可以称这种跳频为相关跳频。

二、差分跳频技术的有关分析

在差分跳频通信的过程中, 会产生跳频图案。所以我们需要对跳频图案进行分析。跳频图案又有哪些特点呢?我们接下来进行介绍。

(1) 相邻频点具有不重复性。在差分跳频图案进行转移时, 一定会从另外一个频率子集中选出一个频率, 所以不会产生相邻相同的频率, 即跳频图案相邻频点具有不重复性。 (2) 初始频率与待传数据流决定了跳频图案。差分跳频图案不但与发端数据流有关, 还和初始频率有关。所以, 在收端必须得到初始频率, 否则收端无法恢复出发端的数据。 (3) 跳频图案不存在初始密钥, 跳频密钥其实就是数据流, 数据流是一种不断改变着的流动密钥。 (4) 时间不参与跳频图案的运算。

以前的跳频图案和和差分跳频图案不同, 以前的跳频图案出了序控制意外, 初始密钥和时间参数都是跳频图案运行的一部分。而差分跳频图案的运行只需要数据流, 它就相当于密钥, 而与时间无关。

除此之外, 我们还要对差分跳频技术的抗干扰力进行一定的分析。差分跳频技术的抗干扰性是由它的高跳速所促成的。多径时延远远大于频率驻留的时间, 这样便使本跳信号无法落到本跳内, 可是如果把驻留时间变小, 就是本跳信号落入下一跳的几率提高。而本跳和下一跳的频率不相同时, 根据正确的频率拣择, 会出现检测失误, 形成干扰信号。所以差分跳频的抗干扰性仍然有待加强。据此, 很多人用增加带宽的方法来提高它的抗干扰能力, 这有异于传统和常规的跳频技术, 主要是提高阻塞的抗干扰能力也同样是提高抗多径干扰能力。

三、差分跳频技术的应用

差分跳频是一种新型的扩频技术, 不同于传统调频技术, 它有着传输速度快、防跟踪性能强等特点。所以差分跳频技术能够很好地用于其他领域。下面我就来介绍差分跳频技术是如何运用于短波窄带猝发通信的。

在发射与接收方面窄带差分跳频和宽带差分跳频基本上是相同的。而在跳速、频率集频点数等方面它们存在着差异, 这几个方面共同决定了差分跳频的属性。

与宽带差分跳频相比, 窄带差分跳频的带宽窄, 所以它们相同的跳速时, 可用的频数就会减少。这就是由带宽和最小频率共同决定的。所以说最小频率间隔的选择是最重要的也是最基础的。接下来还要对频率集频点数与最小自由距离进行选择。

所谓的最小自由距离, 就是对于两条互相一同且长度无限频率转移路径中的最小汉明距离。这一选择必然和差分跳频的核心G函数有着密不可分的联系, 也可以说G函数确定了最小自由距离, 而最小自由距离则是一种重要参数, 它影响了通讯系统误码性。

而另一种选择是频率集频点数, 它承接了最小频率间隔, 并且是由跳速和带宽的反比来决定的其中的可用频点数。必然, 这一项也是和G函数紧密联系的, 根据G函数的相关性, 就可以看出在频率序列频率依次表现出均匀性和随机性, 这就要求着DFH编码的完备。除此之外, 还要求最大的频率集里面的频率点数不大于带宽内的, 这也就是决定了, 跳速影响着最大频率集的频率点数。

高速的数据传输能力是差分跳频技术的特点, 跳速越高, 传输速率又快。当跳速确定的情况下, 每跳所带的比特数越多, 传输速率就越快。

四、结束语

差分遗传算法收敛性研究 篇6

关键词：遗传算法,差分遗传算法,差分进化

0 引言

遗传算法(Genetic Algorithm,GA)由美国教授Holland于1975年根据生物进化过程和遗传机制基本知识而提出,是建立在随机选择和遗传学基础上的并行寻优算法[1]。遗传算法虽具有很好的全局搜索能力,但同时也存在一些自身的局限性。初始种群是随机生成的,寻优方向不确定且不断发生变化,复杂度较大,存在局部收敛造成的“早熟”现象[2],致使输出的局部最优解并非全局最优,只能作为问题的近似局部最优解,给实际应用问题带来很大不足。本文引入差分思想,在传统遗传算法的基础上进行改进,通过交叉率、缩放因子和种群规模大小3个控制参数来实现,在生成初始种群后采用差分思想进行变异、交叉操作,产生试验个体,在父代个体与试验个体之间根据适应度大小进行排序,保留适应度较高的个体,实现种群的进化。差分进化算法原理简单、易于理解和实现,本文通过实验表明其运行结果可靠、鲁棒性强、收敛速度快,能更好地保持群体的多样性,同时具有更高的全局寻优能力,可在很多领域得到广泛应用。

1 基本差分进化遗传算法

1.1 差分进化算法

差分进化算法[3](Differential Evolution Algorithm,DE)是1996年由Rainer Storn等提出,正如其它演化算法,差分算法是一种基于实数编码的、随机的,基于群体差异的并行直接搜索算法,它可对非线性的不可微连续空间函数进行最小化。从整体来看,它与遗传算法有很大的相似之处,同样差分算法也存在着变异、交叉和选择操作,但是它又不同于遗传算法。

与传统进化算法相比,差分进化算法保留了基于种群的全局搜索策略和实数编码,变异操作是个体算术组合的结果,并使用一对一的替换方式,只有在子代个体优于父代个体时才进行替换,很大程度上降低了遗传操作的复杂性。

1.2 差分进化算法基本思想

差分进化算法的基本思想[4]是根据父代个体间的差分向量执行变异、交叉和选择操作,是从某一随机产生的初始种群开始,在初始种群中选取任意两个个体的差向量作为一个基本个体,选择出的其余个体为参照个体,将差向量加权后按照一定的规则与第三个个体求和产生变异个体,接着按一定的概率,变异个体与某个预先确定的目标个体之间进行交叉操作,生成一个试验个体。如果试验个体的适应度值大于与之相比较的目标个体的适应度值,则在下一代中就用该试验个体取代目标个体;否则,保存目标个体。在每一代的进化过程中,每一个体向量作为目标个体一次,通过反复地迭代进行,保留优良个体,引导搜索过程逼近全局最优解,实现种群进化[5],如图1所示。

2 差分算法基本操作

差分进化算法的主要步骤与其它进化算法基本一致,主要包括变异(Mutation)、交叉(Crossover)、选择(Selection)3种操作。与传统遗传算法不同的是操作的执行顺序,差分算法先进行变异操作,然后利用变异个体与父代进行交叉操作,最后执行选择操作,选择出适应度高的个体作为新一代个体[6]。

种群初始化:设种群规模M,在n维空间中,随机生成初始种群Xi.(0)以及初始种群的第i个个体的第j个基因Xij(0)分别表示如下:

其中,i=1,2,...,M;j=1,2,...,n;xijmax和xijmin分别是第j个样本个体的取值范围,rij是[0,1]上的一随机数。

设当前进化代数为t,Xi(t)=(xti1,xti2,...,xtin)T为种群中的第i个个体,最大迭代代数为t-max,对于每个个体依次进行编译、交叉、选择操作[7]。

2.1 变异操作(Mutation)

变异操作是差分进化的主要操作,它是基于群体的差异向量来修正各个体的值,从初始种群中随机选择两个不同的个体,然后将它们的差向量加权后按一定的准则与第3个个体向量求和产生新个体的过程。

随机选择3个样本个体Xa、Xb、Xc且i≠a≠b≠c,生成的新的变异个体用Vij来表示,则变异操作为:

其中,j=1,2,...,n;Xbj(t)-Xcj(t)为差异向量,η∈(0,2)为变异算子,a、b、c为小于M的随机整数。

2.2 交叉操作(Crossover)

为了弥补局部早熟收敛造成种群的多样性减弱问题,在初始种群中随机选择两个父代个体的差向量来执行交叉操作,交叉后生成的变异个体Vij与另一个预先确定的目标个体进行交叉操作生成试验个体。

设rij(0≤rij≤1)是一随机数,k(0≤k≤1)为执行交叉操作的交叉算子,试验个体为Tij,r(i)(1≤r(i)≤n)是随机整数,以确保Ti至少可以从变异个体Vi中获得元素,具体操作如下:

若rij≤k或j=r(i),则

若rij>k且j≠r(i),则

2.3 选择操作(Selection)

差分进化算法的选择策略是从父代个体Xi和试验个体Ti中选择一个适应度值最好的作为下一代个体Xi(t+1)。设适应度函数Fit(f(s))=f(s),为了确定Xi(t)是否成为下一代成员,对向量Ti(t+1)和目标向量Xi(t)的适应度值进行比较:

3 差分算法与传统遗传算法收敛性对比

为了对差分进化遗传算法的性能进行定性评价[8],选择典型的Benchmarks函数,对差分进化算法和传统遗传算法的收敛性进行对比。本文选择典型的Sphere函数和Rosenbrock函数,通过对差分进化遗传算法和传统遗传算法的进化代数和适应度函数值之间的对应函数关系进行分析对比[9,10]。结果表明,在同样的环境条件下,差分进化遗传算法在适应度值收敛于0时,进化代数明显要少于传统遗传算法,并且程序的运行时间也相应缩短。

图2和图3是差分进化算法与遗传算法分别在Sphere和Rosenbrock函数下的函数值与种群的迭代数进化曲线。在种群个体数M=100,每个个体编码的维度n=25的情况下,设定最大迭代数初始值t-max=3 000,交叉因子η=0.3,交叉率k=0.7,可以看出,差分进化算法的收敛速度迅速,进化初期函数值变化幅度较大,浮动逐渐缓慢,直到趋于稳定状态。相比差分进化算法,遗传算法在相同参数条件下的收敛速度较缓慢。在相同硬件设施下,从程序运行速度来看,差分进化遗传算法和传统遗传算法在Sphere函数下的程序运行时间分别为16.255 304ms和22.635 745ms;而Rosenbrock函数下,程序的运行时间分别为17.986 915ms和24.414 156ms,由此可知,使用差分进化算法时,程序的运行速度明显比遗传算法要快,降低了算法的时间复杂度。

图4和图5分别是两种算法在种群规模、个体编码维度、最大进化代数以及交叉率不变的情况下,将其交叉因子变为η=0.5。可以看出,差分进化的收敛速度较之前变得缓慢,但随着其进化的进行,函数值不再随着进化代数的增长而改变,而是逐渐趋于0,收敛到稳定状态,在一定程度上表明变异因子对收敛速度的影响,且变异率越大,收敛速度越缓慢。相比差分进化算法,遗传算法在相同参数条件下的收敛速度更显得缓慢。从程序的运行速度进行分析,Sphere函数下,差分进化算法的程序运行时间为15.350 498ms,而遗传算法的运行时间为21.824540ms;Rosenbrock函数下差分进化与传统遗传算法的运行时间分别为13.540 887ms、20.451 731ms。同样可知,相同参数条件下,差分进化的性能比传统遗传算法的性能更优。

4 结语

由Matlab实验测试结果可知,差分进化遗传算法在传统遗传算法的基础上进一步提高了算法的全局寻优能力,在交叉因子一定的情况下,变异因子越大收敛速度越缓慢,而种群规模会影响程序的运行时间。本实验仿真验证了差分进化遗传算法的有效性,从实验对比数据可以看出,该算法在求解最优解的过程中,相比传统遗传算法,差分进化算法在迭代次数较少的情况下就可以达到稳定状态,在较短时间内就能够搜索到较高精度的解,程序运行速度也明显提高。因此,本文提出的算法具有较强的全局搜索能力,同时缩短了算法的搜索时间,在一定程度上降低了算法的复杂度。

参考文献

[1]苗振华,孙旭东.基于交叉库与并行变异的自适应遗传算法[D].大连:大连理工大学,2015.

[2]王岚.基于自适应交叉和变异概率的遗传算法收敛性研究[J].云南师范大学学报,2010,30(3):32-37.

[3]杨启文,蔡亮.差分进化算法综述[J].模式识别与人工智能,2008,21(4):506-513.

[4]魏玉霞,林健良.差分进化算法的改进及其应用[D].广州:华南理工大学,2013.

[5]LIU JUNHONG,LAMPINEN J.A fuzzy adaptive differential evolution algorithm[J].Soft Computing:A Fusion of Foundations,Methodologies and Applications,2005,9(6):448-462.

[6]郭鹏,赵正.差分进化算法改进研究[D].天津:天津大学,2011.

[7]BABU B V,JEHAN M M L.Differential evolution for multi-objective optimization[J].Evolutionary Computation,2003,4(12):8-12.

[8]高岳林,刘军民.差分进化算法的参数研究[J].黑龙江大学自然科学学报,2009,21(1):81-85.

[9]汪民乐.遗传算法的收敛性研究[J].计算技术与自动化,2015,34(1):58-62.

全差分运算放大器设计 篇7

运算放大器是模数转换电路中的一个最通用、最重要的的单元。全差分运放是指输入和输出都是差分信号的运放, 与普通的单端输出运放相比有以下几个优点:输出的电压摆幅较大;较好的抑制共模噪声;更低的噪声;抑制谐波失真的偶数阶项比较好等。因此通常高性能的运放多采用全差分形式。近年来, 全差分运放更高的单位增益带宽频率及更大的输出摆幅使得它在高速和低压电路中的应用更加广泛。随着日益增加的数据转换率, 高速的模数转换器需求越来越广泛, 而高速模数转换器需要高增益和高单位增益带宽运放来满足系统精度和快速建立的需要。速度和精度是模拟电路两个最重要的性能指标, 然而, 这两者的要求是互相制约、互为矛盾的。所以同时满足这两方面的要求是困难的。折叠共源共栅技术可以较成功地解决这一难题, 这种结构的运放具有较高的开环增益及很高的单位增益带宽。全差分运放的缺点是它外部反馈环的共模环路增益很小, 输出共模电平不能精确确定, 因此, 一般情况下需加共模反馈电路 (CMFB) 。

1 运放结构的选择

运算放大器的结构重要有三种: (a) 简单两级运放, (b) 折叠共源共栅, (c) 共源共栅, 如图1的前级所示。本次设计的运算放大器的设计指标要求差分输出幅度为±4V, 即输出端的所有NMOS管的VDSAT, N之和小于0.5V, 输出端的所有PMOS管的VDSAT, P之和也必须小于0.5V。对于单级的折叠共源共栅和直接共源共栅两种结构, 都比较难达到该要求, 因此我们采用两级运算放大器结构。另外, 简单的两级运放的直流增益比较小, 因此我们采用共源共栅的输入级结构。考虑到折叠共源共栅输入级结构的功耗比较大, 故我们选择直接共源共栅的输入级, 最后选择如图1所示的运放结构。两级运算放大器设计必须保证运放的稳定性, 我们用Miller补偿或Cascode补偿技术来进行零极点补偿。

1.1 主运放结构

该运算放大器存在两级: (1) Cascode级增大直流增益 (M1-M8) ; (2) 、共源放大器 (M9-M12)

对该电路进行小信号分析, 第一级增益为A1, A1可表示为:

第一级增益为A2, A2可表示为:

整个运算放大器的增益Aoverall:

1.2 共模负反馈 (CMFB) :

对于全差分运放, 为了稳定输出共模电压, 应加入共模负反馈电路。在设计输出平衡的全差分运算放大器的时候, 必须考虑到以下几点:

共模负反馈的开环直流增益要求足够大, 最好能够于差分开环直流增益相当;

共模负反馈的单位增益带宽也要求足够大, 最好接近差分单位增益带宽;

为了确保共模负反馈的稳定, 一般情况下要求进行共模回路补偿;

共模信号监测器要求具有很好的线性特性;

共模负反馈与差模信号无关, 即使差模信号通路是关断的。

该运算放大采用连续时间方式来实现共模负反馈功能。如图2所示。

该结构共用了共模放大器和差模放大器的输入级中电流镜及输出负载。这样, 一方面降低了功耗;另一方面保证共模放大器与差模放大器在交流特性上保持一致。因为共模放大器的输出级与差模放大器的输出级可以完全共用, 电容补偿电路也一样。只要差模放大器频率特性是稳定的, 则共模负反馈也是稳定的。这种共模负反馈电路使得全差分运算放大器可以像单端输出的运算放大器一样设计, 而不用考虑共模负反馈电路对全差分放大器的影响。

1.3 电压偏置电路:宽摆幅电流源 (如图3所示)

在共源共栅输入级中需要三个电压偏置, 为了使得输入级的动态范围大一些, 图中的宽摆幅电流源来产生所需要的三个偏置电压。根据宽摆幅电流源的设计要求, 必须满足:

2 仿真结果及分析

根据手工计算的结果, 编写输入网表, 在输入端为2.5V共模电压的情况下, 进行直流工作点的分析:

2.1 AC特性图, 如图4所示:

由图4可知:直流增益:80d B;单位增益带宽:74.5MHz;相位裕度:80度;

2.2 阶跃特性

放大器摆率如图5所示。

由图5知道, 放大器的开环压摆率为236.6V/us。

3 结论

本文对全差分放大器的部分性能指标进行了分析, 经过手工计算, 再通过Hspice软件进行仿真调试。表1是整个运算放大器的部分性能指标。

摘要：研究设计了全差分、高增益的CMOS运算放大器, 本文采用折叠共源共栅结构、连续时间方式共模反馈以及宽摆幅偏置电路。基于CSMC 0.6μm CMOS工艺, 采用HSPICE软件对电路进行仿真。对各性能参数的仿真结果表明, 该电路在输入2.5V电压的情况下, 此电路的开环直流增益为80dB, 相位裕度800, 单位增益带宽74.5MHz, 具有较高的增益。

关键词：全差分,高增益,运算放大器,HSPICE

参考文献

[1]PhillipE Allen, DouglasR.Holberg.CMOS模拟集成电路设计[M].北京:电子工业出版社, 2005.

[2]朱小珍, 朱樟明, 柴常春.一种高速CMOS全差分运算放大器[J].半导体技术, 2006, 31 (4) .

[3]赵雅兴.Pspice与电子器件模型[M].北京:北京邮电出版社, 2004.

[4]Young-Ju Kim, Hee-Cheol Choi, Si-Wook Yoo, Seung-Hoon Lee, Dae-Young Chung, Ky-oung-Ho Moon, Ho-Jin Park and Jae-Whui Kim.A Re-configurable0.5V to1.2V, 10MS/s to100MS/s, Low-Power10b0.13um CMOS Pipeline ADC.IEEE2007Custom Intergrated Circuits Conference (CICC) .185-188