SQL差分

第27卷第7期计算机应用与软件Vol. 27 No. 72010年7月Computer Applications and SoftwareJul.2010SQL差分楼荣生(复且大学上海(国际)数据库研究中心上海200433)摘要研究定义在变化中的数据库上的查询。一个查询是一个函数,以数据库表为自变量,也以数据库表作函数值。SQL差分研究自变量变化对查询结果的影响,推导出法则以精确推断因自变量的变化而查询结果应该发生的变化,从而产生了查询差分的概念。对构成sL查询的各种成份如投影、选择、联接、外联接、二元集合运算等分别研究了各自的差分生成规则,也研究了这些成份相互复合所产生的查询的差分构成方法,从而使所得出的方法几乎复盖了当前使用的大部分查询语句。以此为目的,为SQL查询设计了一套完善的代数符号以使对SQL查询进行代数推导成为可能,并据此发现了SQL系统中的许多鲜为人知的代数性质,有助于为SQL构造完整的理论基础以取代关系代数。关键词数据库变化跟踪物化视图的增量修改SQL查询表达式可重复集合SQL表的相等及加减法多维联接和多维表SQL中的线性运算SL代数性质SQL DIFFERENCEou tongshenAbstract In this paper we studied the queries which are defined on dynamic database. Each query is a function, the database tables areoth the arguments and the function values. The "SQL Difference"is to study how the variation of arguments affects query result, and to de-duce principles to precisely infer the deserved changes of a query result incurred by the changes of the argument, on this way we produced anew concept of"Query Difference". In the paper we studied the generation rules of query differeomponents of SQLrespectively, such as projection, selection, join, out- join and binary set operations, etc. as well as studied the composition of difference ofthe queries derived from the mutual compositing of those components. As a result, the solution provided in this paper almost covers a greatpart of the query syntaxes that are currently in use. To achieve above objective, in this paper a set of complete algebra symbols are designedfor SQL query, so that the algebra reasoning on SQL querying becomes possible. During the course, we discovered many rarely known alge-braic properties in SQL system. These will help us to build a complete theoretical base for SQL to supersede the relational algebraKeywords Tracking changes in DB Incremental update of materialized view SQL query expression Repeatable set Equality and ad-dition and subtraction of SQL tables Multi-dimension join and multi-dimension table Linear operations in SQL SQLs algebra properties的视图的变化量。但由于缺少算法,目前只能处理简单的视图0引言定义,略为复杂一点的视图定义,如联接、子查询等,现有的DBMS中增量修改方法还不能实现。本文的研究就是针对这结构查询语言SQL,是关系数据库标准语言,描述对关系数需求展开的。据库的操作,或是定义在关系数据库上的运算。差分,是表达函用T表示物化视图的源表(下划线是矢量符号T表示由数变化的数学工具。当前函数值减上一时刻函数值所得的差是个或多个表组成的表矢量:T=T,T2,…,Tn;n>0),物化视向后差分,下一时刻的函数值减当前函数值所得为向前差分。图S的定义是在T上的一个查询S=Q(T),描述从T计算出SSQL差分研究变化中的数据库及在数据库上定义的查询。一个的过程在SQL中是查询语句。若对T的修改记在一组与T相查询就是一个函数其中用到的表是该函数的自变量查询所得对应的表中称为T的差分,在源表中是T的向后差分,其结果集是函数值。SQL差分研究数据库变化对查询结果的影中记录有已对T的行所作的增加、删除和修改,反映了T的当响,以及若把查询视作函数时它的差分的构成法则。前值的形成过程。对S应作的修改相应地记为ds,是S(尚未数据仓库的数据收集系统中广泛使用一种称为物化视图变化)的向前差分藉以把S变成与T的当前值对应的S的当( materialized view)的机制。物化视图是一种有视图功能的实前值。dS理论上应可从娌和T计算出:dS=C(哩,T),G应表根据源表的数据计算得到,但要随着源表数据的变化而变可从Q导出。化。有两种方式可实现跟踪:完全重算和增量修改。因完全重因此跟踪过程由三步组成:算工作量大耗时多故一般都愿意选择后者。增量修改方法即是在视图的当前值基础上,加上或删除从源表的变化量计算出收稿日期:2008-11-19。楼荣生,教授,主研领域:数据库技术第7期楼荣生:SQL差分137(1)在数据源当对作插人、删除和修改时用一定的方1.2SQL表法生成dT;定义2SQL表x是关系数据库意义上的属性集,ep是(2)由d和计算出dS并送到物化视图所在的系统;非零整数。(3)在物化视图所在的系统用ds修改S。1)形如v(x,rep)的一个表或视图或一个以(x,rep)为输本文第一节是第一步的一般概念。而第二步由扛和计出的SQu查询称为SQL表下文也简称表。V是表名,中各属算ds,即从Q推导出G开创了一个称为SQL差分的广阔的研性称为表的列,x也记作v.cols,是V中除rep外的所有列组成究领域。对各种不同的Q推导出G的算法是后面各节研究的的列集。p称为V的重数列。mp恒为1的表rep列可省去。内容。第三步是一个理论上的简单过程,本文不再研究。文中所有SQL语句都使用 Oracle语法,均可在 Oracle的9i(2)对表中任一行t(x00)∈V。n0是0在t的重数,记为本文读者只要学过数理逻辑和SQL语言即可。文末所列数记为。V中所有Lx=的t的重数之和称为o在V的重或更高版本上运行。ep(x0)。Ⅴ.rp()=,p(1)参考资料清单仅供参考,其中文献[1是关于 Oracle的SQL语言的,文献[2]是关于SQL的1992标准的。学习SQL的其他材若x0gV,则定义Ⅴ.rep(x0)=0。料还可在网上找到。数理逻辑知识只要有大学离散数学中所学(3)若有限制rep>0称Ⅴ为正表的就可以了也可参考文献[3]。阅读本文不需要学过数学中(4)若Ⅴ每行的rep值恒为1。这时Pp可省去成为v的差分概念对此有兴趣的读者只要阅读数学词典(如文献(x),称为V的无重数形式[4])或百科全书中的相关条目就够了。v.rep(x)函数依赖于x,作为x的函数,定义域是无限集当且仅当x出现在V中时有非零值。1差分注意:如定义中所示,形如(x,rep)的结构表示表的列名,逗号是列名分隔符;而形如(x00)的结构表示表中的数据行,空1.1SQL查询表达式格是数据分隔符。后面均按此协定为便于对SQL查询语句的分析,引入一种符号表示法。定义3表的可加和相等两个表V(x,rep)、W(y,rep),若xy列数相同且对应列的数据类型也相同,称ⅤW是可并定义1设SQL查询语句一般形式是:或可加的。若x(或y)的任意值在ⅤW的重数相等:V.repselect Z from V where F group by g having H(不考虑 order by子句)此语句用符号表示成veF|/GH/(p)=W.rep(0),则两表相等(A),描述一个SQL查询称为SQL查询表达式。约定例2x是整数,下面的表vl(x,rep)、V2(x,rep)、V3(x)是(1)下划线表示用逗号分隔的多项,如A=A1,A2,…,An相等的:(2)Ve是对应于Ⅴ的联接表达式。如表VW的普通联接VI(x, rep) V2(x, rep) V3(x)表示成Ⅴ*W或简单地表示成ⅤW。其它联接及表示法后面逐71个引进。(3)FH中的and用&代替,or用或Ⅴ代替,not用!代888替。 y is null表示为“y空”,而 y is not nul为“y非空"。exis与 not exists表示为彐与彐,in和 not in表示为∈和g, left join同一表在相等的意义上有多种表示形式。其中两个表示式有特殊意义:如例中V3,这是无重数形式,是通常出现在数据(4)Y或A中的换名(Ome中是空格, SQL Server等中用库中的表的形式;若值在表中不重复,是规范形式。对应的字a)用冒号表示。如al+a2:b表示列的表达式al+n2在输p表示在表中的重数。如例中v2。出时换名为b。v所示是不规范的SQL表是最一般的表示形式。5)如果A中有 distinct,(A)改为[A]。实际数据库中的表大多是有主键的正表,是无重数形式的(6)A是*时(*)可省去。规范表。当对这些表作了投影或并时才产生重数大于1的表,例1SL查询表达式表T(x),其中x=(p,y,z)而且可能是不规范的(1)TIp<100;(y, z)=Select y, z from T where p<100对表Ⅴ(x,rep)作规范化的SQL语句(2)TIP< 100I [y, z]= Select distinct y, z from T where pV/xl sum(rep)<>01(x, sum(rep): rep)=select x, sum( rep)repfrom V group by x having sum( rep)<>0(3)TIp< 100 /p I count(+)<2(p)=select p from T无重数形式表V(x)的规范化语句为where p<100 group by p having count(*)<2V/x(, count(* ): rep)=select x, count(.)rep from V group by x(4)T/(p, y)(P, sum( rep): rep )= Select P, sum( rep)rep无重数形式和规范形式对于每一正表都存在且1.3表的加法和减法(5)T:aly=TIp=a pl(max(y))I Select from Ta定义4表的和与差可加的两个表(x,rp)、W(y,rp)where y =( select max(y)from T where p=a. P)之和记为Ⅴ+W是一规范表x的任一值0在Ⅴ+W的重数是(6)T:a*T:b|a.p=b,p&a,y0两表合成一表,然后规范化。语句是v(z)=v/z(VUA W)/xisum( rep)<>0|(x, sum( rep): rep)select x, sum( rep)rep from计算中作了规范化操作,结果是规范的SQL表。select x, rep from V union all select y, rep from W在符号的使用上有一点混淆:若z=x=V.cols,则Ⅴ(x,rp)group by x having sum(rep)<>0在x的保留重复投影按定义记为Ⅴ(x),与V(x,rep)相同。故Ⅴ表的加运算满足交换律和结合律。W是空表则V+W=V。W是-V则V+W=空。与某(x)可能是一个无重数列的表也可能是另一表的保留重复投影。必要时将在上下文中明确说明表V可加的所有SQL表V|与加运算构成交换群。定理3投影可加性设Ⅵ(x,rep)、V2(x,rp)是两个可1.4SQL表的差分加的SQL表,Sx。则保留重复投影对加可分配定义5差分设SQL表Ⅴ的当前值是从Ⅴ经过一系列的(v1+v2)(z)=V1(z)+V2(z)Insert, delete和 update得到。Q(V)是Ⅴ上的一个SQL查询。明由SQL表相等定义3,只要证明等号两边对任意值dQ(y))=Q(V)-Q(vo)称为Q()的差分Vo称为Y的初值20的重数相等。由式(3)得由定义5得到以下三个结论:(Ⅵ+V2)(2).mp(20)=E(v1+V2).rp(x)(1)设Q()=V。则:由表相加定义4及式(3)dy=y-vo。或d(v1,V2,…,Wn)=(dvl,dv2,…,dvn)=(V1-v10,V2-V20,…,vn-Vn0上式=3.rp(x)+2m()=V1()m()+dv的数据可建ine,deyd个igr产生。若系2(2,rp()统有备份v0,则可直接计算-V0得到。推论保留重复投影差分对表V(x)或V(x,rep),设z(2)设Q(y)是物化视图。当y从v变到当前值时,Q=Qx,则:V)的值还保持在00=Q(v0)。为得到Q只要做Q0+dQ。定d(v(z))=dv(z)义5是从Q产生呗Q的一种方法,即完全重算。本文研究增量证明d(v(z)=V(2)-V0(z)=(V-V0)(z)=dv(2)。方法。定义7一元线性运算对可加SQL表Ⅵ、V2的一元运(3)d(Q(y)作为函数它的自变量是Ⅴ和v或d和Ⅴ算G若成立:(因dⅤ=V-V0),把此函数记为dQ(dV,y)。如果是复合函数G(v1)+G(v2)=G(v+Ⅴ2)如Q(S(y)),则(注意与数学分析中的复合函数导数不同)称G对加可分配,也称为一元线性运算。d(Q(s(v)))=dQ(d(s(v))由定理3保留重复投影是一元线性运算。S(V))=dQ( ds(dV, v), S(V))定理4保留重复投影合并设yS2S,SQL表Ⅴ(x,rep定理1vo是正表,则对同值Vmp(3)≥dV.m(x)。连续在和的保留重复投影等于在Y的保留重复投影证明由定义5与式(2),dv.rep(x)=V.rep(x)-V0.repY)=V(证明证明两边在任意值y0的重数相等。由式(3)得:vo是正表,vO.rep(x)≥0。由此得v(x)(x),rp(0)=2(2),mp(80)=33w.m(V rep(x)>V rep(x)-vO rep (x)=dV. rep(x)=副vm()=V(,rm(0)定理2和的差分两表和的差分等于差分的和:d(V+其中确认了2y0,x20与x2y0等价。必要性是明显的。充W)=dⅤ+dW。分性只要为满足x20的任意值x找出满足02y0,x0220的明设VW的初值为vo、w0,则由定义5及加法的交0即可。而此即是x0中包含的z上的值换律和结合律,2.2消除重复投影d(+W)=Ⅴ+W-(v0+W0)=(V-V0)+(W-W0)=d+dW从一个SQL表V中取互不相同的,zsv.cols,这一操作称2投影与选择为对z的消除重复投影,可用带 distinct的查询计算select distinct z from V但这样定义不适用于负重数。本文使用下面的定义。2.1保留重复投影定义8保留符号消除重复投影SQL表V,zsV.cls,交定义6保留重复投!是属性集,cvc。SQL表v在的消除重复投影,是对保留重复投影V的重数只取符号的保留重复投影记为v(2),是由形如t(zrp)的行组成的得到的SL表。记为v2]义,V[z]值0的重数是第7期楼荣生:SQL差分139V[z]. rep( 0)=sign( $V rep(x))(5)1,必dV.rep0行。由此得定理5消除重复投影合并 ySiS,正SL表Ⅴ(x,rep)whole(dⅤ)= dvixe vidv.rep0,则两边都是1,等式成立;而若y=0,因sgn(n列。函数(F.cos)当F=tme取值1,当F=flse取值0。称f(x))=sign(x)等式也成立。是F的特征函数,用AF表示。然后计算待证等式两边重数。第一式:特征函数用以计算有选择的查询的重数。V|F在(x0)的[VLz3 rep(20)=sign E[V]=sign sign(V. rep(2))重数是:用辅助等式(7)把求和符号内的sig逐个删去,所得等式VIFI rep(x0)=V rep(x0)+ AF即是Ⅴ[z]在0的重数。易验证下面的等式:第二式A(Fl&F2)=入(F1)*A(F2)λ(FI|F2)=sign(λ(F1)+λ[V+[Wl]. rep(xo)= sign( V. rep(x0)+sign( W rep (F2)) AF=1-Al(y0))定义10环境无关查询Ⅴ|F|的条件F称为是环境无关用辅助等式把括号内的sig删去,所得等式即是[V+W]的设b是与Ⅴ的类型匹配的行,F在b上的值F(b)只与b有关在x0的重数。而与Ⅴ的内容无关。[V]的差分是d[V],记录因d的变化而引起的[V]的变义的意思是,不论b是否在Ⅴ中及V中有些什么行,F(b)化。因为只有当在Ⅴ中出现的x的一个值0全部是新加入的,不受影响。例如,若F有组函数则不是环境无关的,因F(b)与或者V0中的0在V已全部被删去,才会对[Ⅴ]产生影响,使和b同一组的其他行有关,因此满足环境无关的条件必须是行[]增加或删去该x0。条件。若F中含有重数,因重数实际上是组函数 count(*),也用 whole(dv,V)或简单地 whole(dV)记dⅤ中这些能使不是环境无关的。[ⅴ发生变化的行称为d的全加全删子集其中的行使[]即使行条件,也有不是环境无关的:有增1行或减1行的变化。所以dV]是 whole(dv)的保留重例5查询复投影:sign( wholw(dv),简单地写作 signwhole(d),即得VI3V: alV p>pl I =select* from V where exists( selectd[ v]=signwhole(dv)(8) from V a where V.p>p)的行条件F=|彐v:aV.p>p}}不是环式(8)的代以V(z)。因式(4),d(V(2))=dV(z),得消境无关的。设V有两组值v1={2|、V2=11,2。则v1F}=除重复投影的差分空,V2|F}=12}。F(2)在Ⅴ1中是 false,在Ⅴ2中是tued(v[z])=signwhole(dv(z), v(z))事实上,决定F(b)的除了b外还有组成F的子查询。设F为推导出 whole(dv)的表达式,把dv的行分成三类:tabs是用在F的子查询中的所有表。则有下面的充分条件判断(1)全删类这类行重数均为负,其中的不再在V中;F的环境无关性。(2)全加类这类行也在Ⅴ中存在,且在V的重数与在dv定理7环境无关判别法查询Ⅴ{F|中若Y与F. tabs无的重数相同;相同表则F是环境无关的。(3)其他这类行中的x也在Ⅴ中,但重数不同。由定理证明F(b)实际上是F(b,F,tabs),与F.tabe没有相同140计算机应用与软件2010年的表y替换成别的表不影响F.tabs,因而也不影响F(b,F若VW是规范的,2维笛卡尔积是:abs)的值。符合定义10。V W=l(vx vrep wy wrep )I(y vrep)EV, (wy wrep)EWI注意证明中用的是“替换”而不是“修改”。这是因为修改v^W称为2维SQL表,而ⅤW、VW等一致地是一维SQL时Y的表可能有 trigger会影响F.thbs的内容。如果Y的tger表。w是xy的别名。特别是当x、y中有相同列名时x、不影响Ftbs,则对Ⅴ修改也未尚不可。中必需规定不同的别名。当x、X中无相同列名时w、w可直接定理8选择对投彩和加的分配选择条件F环境无关使用x、y①对表v(p,,rep),选择条件F只与z有关,则:2uni函数可把2维SQL表转化成一维:V(2)|F|=VF|(2),v2]Fl=VF|[unif y( v-W)=vW②表Ⅴ1(x,rep)v2(y,rep)可加,则③若V是n维SQL表,W是m维SQL表,VW是n+m维vI+V2)|F|=VlF|+Ⅴ2|F证明①第一式。等号两边计算得的F相同。由式(10)多维笛卡尔积仅对规范表定义。和式(3),左边在0的重数:维和多维笛卡尔积满足结合律(证略)。因此SQL表与V(z){F|,Pp(0)=V(z).rp(功0)*AF=(∑V.rp(p,z)*AF笛卡尔积构成半群F只与z有关,对于求和符号中的(p,2)因z=常数0,AF是交换VW的顺序,定义11产生的结果列的排列不同。常数,由此有:般理论忽略这种差别而认同笛卡尔积是可交换的。但因为vW上式=vm(e)AP)=Fmp(P)与WV明显是不可加的,所以从SQL的观点两者不相等,因而本文认定笛卡尔积不可交换。=Ⅴ|F|(2),rep(0)根据定义3等式成立。维和二维笛卡尔积WⅴW在(x0y0)的重数是第二式。第一式两边作消除重复投影vW rep( x0 yo)=Vrep(xo)*W. rep(yo)[V(z)IFI]=[VIFI(z)J=VIFI[z]VW rep(xo y0)=V rep(xo)W rep(yo)=(.rep(x0), W rep(yo))F只与有关因而与重数无关。由式(6)等号左边又可32二维表的投影以是多维表的任意一个重数列也可作全表的重数列。由此,对[V(z)|F]=[V()]{F|=V2]|F多维表的操作可以归结到一维表,只要指定其中一个重数列为由此第二式成立整个表的重数列即可,语法是“表名\”。如对规范表Ⅴ(x,rep)、②F环境无关,式中3个F对同一行得相同值。由式W(x,mp),sY,vW在V和!保留重复投影是:(10),左边在x0的重数W\t(VW)=V-W(Vt)(Ⅵ+V2)F|.rep(x0)=(Ⅵ+V2).rep(x0)*AF={(xvp!Ewep(r):tmp)|( x vrep)∈V,ywrp)∈W再由和的重数VW在Ⅴ和t消除重复投影Ex=(vI rep(x0)+ V2. rep(x0). AF= VI rep(xo)WIt[vW]=vwIvt]AF+ V2. rep(x0)*AF((x ep! sign 2 wrep(y): trep)I (x mep)eV,(y wrep)eW)再次由(10):这里两种投影各有两种表示方法。第一种表示方法可明确上式=V1F,p(0)+V21F,p(80)=(ⅥF+V2地表示出计算过程,而第二种方法与一维表的方法一致,着重于I FI). rep(xo)最后结果的表达。例如,若zGx,tGY,先对ⅤW作v'!投影再根据定义3等式成立。对它作投彩为va(Wu(W));而先投影z再投影!则是W推论表Ⅴ的选择条件F环境无关选择的差分等于差分(v(vw)。用第二种方法表示两者都是vw(x!)。而如的选择投影v(W[VW]),先对作消除重复投影再对z作保留重d(VF)=dv{Fl。复投影,就不能用第二种方法表示。证明设Vo是V的初值由上所述两种投影在(0t0)的重数是:d(VIFI)=VIFI-VOIFEF环境无关,由定理8的②:Wit(V-W). rep(:oro)=vrep(:0)"Ewrep(2)VIFI-VOlFI=(V-VO)IFI =dVIFIWig[ V-W]. rep(xOro)= vrep(x0)sign 2 wrep(y)定理9笛卡尔积的投影表Ⅴ(x,rep)、W(x,rep)的笛卡3联接尔积与投影可交换顺序,即下列各等式成立(1)x,!sy:WW()=v(z)W(!);VW]=v[]W[!y3.1笛卡尔积(2)tCy: W\(V-W)=(v-w)(Vt)vw(t:zCx: VIz(vw)=(vw)(zw)=v(z)"W在SQL中两个表ⅤW的笛卡尔积为(3) Sy: Wi[VW]=(vw)[V!]VW=select from V. wv-w[t]; zCx: Viz[v-W]=(v-w)[zw]=v[z]w有重数列的SQL表的笛卡尔积一般定义为:证明(1)第一式。只要证明两边在(00)的重数相8a定义Ⅱ葡卡尔积①由L表V(m,W(甲)产由式(3)及笛卡尔积定义得:一维笛卡尔积是:I(vx wy vrep+wrep: rep)I(yx vrep)eV. (wyvw(z), rep(20 1o)-. o(VW rep(y))wrep)E WIE(V. rep(x)+Wrep(y))r 2pp第7期楼荣生:SQL差分141=3m(3)·Wmp(y)第三式用交换律得到。=v(z). rep(xO).w(t). rep(to)34笛卡尔积的差分(V(2)W(!).rep(x00)当V和W替换成Ⅴ=V0+dV,W=W0+dW,利用定理9第二式。由式(6)及笛卡尔积定义得可导出笛卡尔积的差分。因:W[]=[wW(a)]=[v(z)W(!)]=v(z)][W(t)]=Vz]w!]VW =(vO +dv)(wo+dw)第三个等号是由于乘积的符号等于符号的乘积。= owo +dwwo)+( vOdW +dvdw)2)第一式。计算在(00)的重数。由式(3)及二维笛卡W =(vO +dV)(wo+dw)尔积定义得:(vO-wo +V\dvwo)+w\(vodw+vldV'dw)vw)(Vt).rep(:0 0)=2(V-W).rep(x0 y0)由此得:Svo(V. rep(so)w rep(2))d(vw)=vw-vowo=dvw0+Vawvrp(x0)是常数:d(v-W)=v'W-VOwo=+V\dv-wo +w\VdW上式=V.rep(x0)wrep(x)+V\"指定对Ⅴ维相加。若进一步用W-W代替W0,又由式(3)得不用初值的笛卡尔积差分公式:2 wrep(y)=W(!).rep(t0)d(vW)=dⅤwo+VdW=dⅤW+ⅤdW-dvdWV rep(xo)E wrep(y)=V, rep(xo)W(!). rep(t0)d(v-w)=v(12)v\dV-W-W\dv'dw)+w\vdW=V-W(). rep(xo to)注意到这些公式的得到只是用了定理9中的分配律,故结(3)第一式。W[VW]=[W(vw)]=[vW(!)]论可以推广到更一般的情形。v^w[!]。定义12二元线性运算二元关系运算若满足对加运式(3):第二式的证明类似第一式对于在二维上都有的投影,从定理9可得与第一式相似的算的左分配律即对第一分量满足分配律称左线性的;若满足等式:右分配律,称右线性的,若满足左右分配律,称为线性(二元)的。Viz(W\t(vW))=Viz(vw(t)=v(z)w(t)V\z[ W\[ V-W]]=viz[vw[t]]= v[z]w[:](11)定理1l二元运算全差分展开设ⅤW是SQL表。对于3.3笛卡尔积的加法个二元关系运算V6W,全差分可如下计算:d( vew)=Vid( vewo)+W\d( vew)同样的思路处理多维笛卡尔积的加法指定任一维为操作或ld(veW)+Wd(Vo⊙W)(13)维作一维表加法,如下例其中V\d、W\d表示只对前缀中分量的差分,另一分量无变化例5SQL表vi(x,rep)=1(71)},i=1,2。W1(y,rep)证明证明第一式。由Vld(ⅤeW0)=ⅤeWo-V06W0=(81),W2(y,rp)={(82)}。则wiw(x,vrep,y,we)wd(veW)=V6W-Vew代入再运用分配律即得。等的值为这一规则还能进一步推广到多元关系运算G(v1,v2VIWI V2-W2 VI-W1+v\v2*W2 VI"w1+W\V2*W271817182718171837182定理12多元展开公式n个变元的SQL查询表达式G在vW+VV2W2指定V为加维,、x,y,wp)相等的两(V1,…,vn)的d全差分可表示为对每一变元的差分之和行的vep相加不存在这样的行,“+Vl”成为并。而在Ⅴ1dc(V1,V2,…,vn)=vldG(vl,V20,…,vn0)+…++W\V2W2中指定W为加维,(x,vep,y)相等的两行wrp相Ⅵildc(v1,…,vi,…,Vno)+…+ Vn\dG(V1,…,Vn-1,n)加得(7183)。∑VldG(v,…,v,0,,va0定理10笛卡尔积对加的分配律SL表Ⅵ(x,mp)、V2其中i=1,…,m;第i项的参数中从第i+1项起到n项都取(x,rep)、W(y,rep),其中v、V2可加,则初值。(VI+V2)·W=V1*W+V2*W证明用数学归纳法。略。W*(V1+V2)=W*ⅤI+W*V2如果G对Ⅴi是线性的,则(VI +12)W=VI"W+V\v2"Wvidc(v1,…,vi,…,Vm0)=G(,…,dVi,…,vno)。W(VI+v2)=wVI +V\WV2证明第一式证明在(x)的重数等号两边相等。3.5联接((VI+ v2).W). rep(xy)=(VI + V2).rep(x).W rep在笛卡尔积中加选择条件即为联接。V和W的一维和二维联接用V*W|F(或ⅤW{F|)和ⅴWF表示,这时F也称(Vl. rep(x)+ V2. rep(x)).W rep(y)联接条件。如Vl. rep(x)*W rep(y)+V2. rep(x)+W rep(y)vWIV.x=W yI select V.x. W.y. V. rep W rep rep from=VI.W rep(xy)+v2.W rep(xy)V, W where V x=Wy=(VI*W+V2.W).rep(xy)维和二维联接VWF|vWF|在(0y0)的重数是第二式由第一式用交换律得出。VWIFI. rep(x0 y0)=V rep(x0)+Wrep(yO)+AF第三式。推导过程同第一式,只是*替换成号。第四式由VoWIFI rep(xo y0)=V rep(x0)W rep(y0).AF142计算机应用与软件2010年作为联接条件的F一般总与两个表的列有关。但SQL的证明联接条件环境无关时联接满足分配律。只要在笛卡语法上也允许条件F只与一个表有关,这时的F称为限定条件,尔积差分公式(12)等号两边加联接条件即得定理结论没有联接作用。定理13笛卡尔积与限定条件规范表V(xPp)W(x,4量词rep)的二维笛卡尔积与Ⅴ表的限定条件F可交换执行顺序VWIFI=ViFI"W量词子查询是指 where或 having子句中含有 exists或not若F与重数无关则对一维笛卡尔积也成立:exists前者当子查询结果非空为真,称为存在量词;后者是当vwF=Ⅴ|F|W(14)子查询结果空时为真称不存在量词证明证明一维笛卡尔积等式(14)。左边在(x0y0)的重因为其他子查询都可以等价地表示为量词,本文只研究量数为:词子查询VWIFI. rep(x0 y0)=V rep(xo)*W rep(yO)+AF4.1存在量词F是V的限定条件只与Ⅴ有关,AF与V.rep(xo)组成Ⅴ含有存在量词的查询一般形式如:IFI rep(x0):selectfrom V where FO and exists( select. from W where F);V rep(x0)+W rep(y0)*AF=VI FI. rep(xo)*Wrep该查询的表达式是v}F0&彐W|F}。查询结果是Ⅴ中满(yo)=VIFI W rep(x0 yo足F0且能与W通过F联接的行但与能联接的W的行数目无根据定义3等式(14)得证。二维的等式证明方法相同。关。如果没有F0,即可简单地记为v彐WF其中Ⅴ称为存在由此定理可得一推论量词的主方,W为次方。注意到F0与W无关,所以该查询等价推论规范表v(x,rp)W(Y,rp)的联接与ⅤW表的重于VF|WF。数无关的限定条件可合并借用谓词演算的符号彐表示eait是合理的,因为Ⅴ彐W(VIFIIWI F2I) F31=V" FI&F2&F3FF|就是谓词演算中存在量词彐yP(y)的具体化,只要令P是“y(VIFIIWIF21)IF31= VWI F1&F2&F31∈W&F(x,y)”即可,用SQL的述语是“WF非空(当F1、F2重数无关(15)彐W|F}或彐Q作为选择条件是对子查询Q的非空性测证明由定理13,把F1、F从括号中移出试。易验证(VIFIl W F2I) F31=VWIFll F21 I F31=vWIFI&F2&F31彐Q1&彐q=3(Q1*Q2),当Q2≠-Q1:彐QlV彐Q2关系代数的运算优化规则中有一规则是把投彩和选择移到=彐(Q1Uq2)=3(Q1+02)(17)第一式是:Q1、Q2都非空当且仅当Q1*Q2非空第二式是联接前。在SQL表中也可证明这一规则可行:定理14联接与投彩规范SQL表VW的联接WW丿F/当≠-Q1,Q1、Q2之一非空当且仅当QUQ2非空。但当Q2=-Q1时虽Q1Uq2非空而Q1+Q2空。第6节将为有负中设zv.cols,tgW.col,F环境无关且只与z有关。则:重数的表定义并运算U:Q1UQ2是Q1+Q2的消除重复投影。VWIFI(z)=v(z)W(t)IFI这样第二式成立必须有附加条件Q2≠-Q1。VWIFI[z]=v[z]wIt]IF)存在量词彐WF的特征函数为VWIFI(zt=v(z)W(!IFIλ(彐wF|)=sign∑(W,rep(x)*AF)2VWIFI[z]=v[z]wIt]IFIsign2W.rep(y)证明第一式。设x=V.coly=W. cols, VWF(a)在(0t0)的重数为:求和条件为tue表示无条件。平方的作用是变负重数为VWIFI(z).rep( 0 tO)=E VWIFI rep(yy正。若W是正表则平方可不要So(V. rep(x)Wrep(yAF)定理16存在量词基本定理表Ⅴ(x,rep)规范,W(x)正表。存在量词查询v彐WF|是二维联接WF对Ⅴ的消除因F只与n有关=(00)时求和号内的AF是常数移重复投影的一元化出求和号外,余下部分分开成ⅤW两部分得:v彐W|F|= unifyV-WIF[V]上式=,wm(3)WmP(x)AF该定理权作为本文对存在量词的定义。下面证明这样定义(z)rep(20)*W(!).rp(0)AF的合理性v(z)w()IFI rep(0 o)证明计算两边在x的重数并证明相等。由式(18),因W因(00)是任意值,由定义3所证等式成立。是正表求和号内不用平方第二式。在第一式两边取符号,左边即为ⅴWF[a],右V3WFl,rp(x0)=V.四p(0)*2(Wmp(Y)*AF边为V[z]W[!]|F}。等式成立。第三与第四式的证明类另一方面:似,略。vwIF|[Ⅴ]rp(功o)=sign(vWF|(v).rep(c0))3.6联接的差分=sign 2(V-W rep(xy)*AF)定理15联接差分联接条件F环境无关时:=V rep(xD)sign 2(.rep(y)+AF)d(wifi)=(dv)wolF) +Vdw i FI由此后者取uniy后两者相等,定理得证=dvW FI-dWdVI FI +vdwiFld(V-WIFI)如果v不是规范的,不保证Ⅴ彐WF无重复行。面VW第7期楼荣生:SQL差分1434.2不存在量词1时uniy后各为Ⅴ彐W或Ⅴ彐W0。由此不存在量词查询是在 where中有 not exists的查询,用存在unify W\d(vw[])=Ⅴ彐W-Ⅴ彐W0=W\d(ⅴ彐W)量词加下划线彐表示不存在量词。彐WF|与彐WF|作为两W\d(v3 w)=unifysignwhole(v'dw(v), V"W(V))个查询条件是互补的,对V中任何一行两者不同时成立但必成第一式得证立其中之一。所以设Q=WF:由Ⅴ3W+Ⅴ彐W=Ⅴ得Wd(V彐W)=-Whd(V彐W),A(丑Q)=1-A(3Q)V3Q=VVQ(20)据此又可得不存在量词的差分式不存在量词也有类似式(17)的等式d豆W)=d丑W0+wld(VWQ≠Q1:Q1&3Q2=3(Q1UQ2)d丑Wo-Wd(v彐W)3QV彐Q2=彐(Q1*Q2)(21)dⅤ丑W0- unifysignwhole(Ⅴdw(v),^W不存在量词也满足左分配律(V))4.3量词与保留重复投影unifysignwhole(vdW(v),vW(v))的表达式根据ⅤW的表示形式不同而有所不同。若两者都是无重数形式时:定理17量词次方的保留重复投影规范表v(x,rep)、Wunifysignwhole(V'dw(V),V-W(v))(x,rep),YF只与x与重数有关。存在量词和不存在量词Vdw(V. cols, sum( rep): rep)次方的保留重复投影可以合并在条件F中计算I(V cols) V-W/V cols rep < count(+)I(V cols)Ⅴ彐W(!)|F(x,v.rep,t,W(!).rep)l(V. cols, sign( rep): rep)=V彐W|F(xV即p,,W.rep(y)}v 3W(t)IF(x, V rep, w(t).rep)外联接=Y丑W|F(,v即P,WrP(y)证明W(),mP(!)=W,rp(y)代替等号左边的W(SQL外联接有左、右、全三种,本文分别用>、<、<>表示。rp。代人后F不再使用w(t)呷而使用W唧p次方W(!)应普通联接有一维和多维的,外联接也有一维和多维。如V>W换成W是一维左外联接例如V>W由两部分组成:一是组成WF{的部分,该部分的dv(z): a3v(z): b a z=b. z&a rep=b rep重数是V.rep*W.rep,表示每一V行被重复W.rep次;另一是与W不可联接的部分,该部分的重数是V.mep,这里的Ⅴ行只=dv(2):a=Vla.2=V.&8. rep=5V.rep(x)出现一次。故Ⅴ(x,mep)和W(y,rep)的一维左外联接Ⅴ>W18量词主方的投影SQL表Ⅴ(x,rp)规范,彐W\F|环F的重数是境无关。x,若量词条件F只与z有关,则存在量词和不存在v>WF|rp(x)=V.mp(x)*(W.p(x)…AF+1-AF)v(2)3WF|=(V彐WF)(2)V和W的一维和二维左外联接可定义为:v(z)丑WF=(V三W|F)(2)V>WF}=V*WF|+V丑WF}*φ[W]v[2]彐W|F|=(v彐WF)[2]V>WIFI=VWIFI +V W](24)v[2]丑WF|=(V丑WF)[2]φ[W]表示只有一个空行的与W同类型的表,V三WF证明由定理8的等式v(2)Fl=VF()和V[2]F=*4W与Ⅴ丑WF◆[W表示将丑WF|用空值加长到viFI[J。彐W|F环境无关必丑W{F也环境无关。F用彐W与第一项等长。SQL中有专用的语法计算外联接。计算该两左F{替换即得第一、三式、用三WF替换即得第二、四式。外联接的语句:4.4量词的差分V>WIFI = select x, y, V rep nvl( W rep, 1)rep from V定理19量词差分规范SQL表V(x)或V(x,rp), w left join W on F;(y)或W(y,mp)正表,彐WF环境无关。W0是W的初值V>WIFI =select* from V left join W on F:则(式中未写出F1):把保留字left改成 right或fu即为右或全外联接。一维和d(v3w)=dv3W0+ unifysigmwhole(Vdw(V),ww(v))二维全外联接定义为:dV三W)=dⅤWo- unifysignwhole(vdw(v),yW(v)<>WF}=V*WF|+Ⅴ彐WF*Φ[W]+φ[V]*W彐F证明因彐WF环境无关,Vwd(V彐W)=dv彐W。再由V<>wiFl=WF|+v彐W|F|φ[W]+φ[V]w彐vF二元展开公式可推得与左右外联接的关系d(v彐W)=dⅤ彐Wo+Whd(v彐W)v<>W=vw+vW=V>W+VVV括号中两项对W重数作减运算,而该重数如果有的话只能dV.x=V.x中用V. rep is null t作选择是d的全删子集,用是1又如果两项都是1的话相减后抵消。两项中只有一项是dv.rep=v.rep作选择是全加子集。由此得 whole的外联接计计算机应用与软件2010年算法三个表VWP的内外混合联接也有两种。①(W)>Pwholel(dV,v)=dV>vdV.x=V.x&(V.rep空ldv.rp=v.rep)②W(W>P)。对比式(9)用in的表示方法,外联接法可使用索引因而可定理22与普通联接的结合律若联接条件环境无关,以计算得较快。(W)>P=W(W>P)。5.2外联接与投影证明由定义,(W)>P=WwP+(WW)丑P。由联接条件定理20外联接与投彩若外联接的联接条件只与投影境无关,则:列有关且环境无关,则与投影(保留或消除重复)可交换操作VwP+(ⅧW)彐P=W(WP+W彐P)=V(W>P)顺序:5.4外联接差分(V>W)(z)=V(z)>W(!)由于加号两边的表达式都是左线性的,所以外联接也是左(ⅴ>W)(a)=V(2)>W(!)线性的。因此有:(V>W)[]=V[2]>w[!d(v>w)=dv>w0+Wld(v>w(V>W)[]=V[]>w[tW0是W的初值。把V>W用式(24)代入(第二个等号要其中≌V.cols,tsW.cols,联接条件F只与z,t有关求W是正表)证明第1式。由定义:d(v>w)=dv>W0+ W\d(VW+V3 w)(v>W)(z)=(V*W+V三W)(2)=dV>W0+VW+W\d(V彐W)=V*W()+V豆W*φ[W]()。dv>w0+VdW-unifysignwhole(vdw(v), w(v)因联接条件环境无关,由定理14:上式=V(z)*W(!)+v(2)丑W*φ[!]=V(z)>W(t)。例6WP是正表,推导(V>W)>P的差分第2式。同第一式,只是将*改为。d((v>)>p)=d(v>w)>p0+(v>W)dP-第3式。F真时,V>W=V*W,(V>W)[n]=V*W[z]unifysignuhole((V>w)'dP(V), (V>W)P(n))V[z]W[!]=v]>w[!;展开d(V>W)F假时v>W=V丑W*φ[W],(V>W)[n]=[(V>W)d((v>w)>p)=(dv> w+ vdW-unifysignuhole(VdW(z)]=[(v丑W*φ[W])(a)]=V(x)丑W*φ[!]=v(,pWY)>P0+(>W)dP[z]彐W*φ[!=Vz]>W[!。unifysignwhole((V> W)dP(V), (V>W)P(v)第4式。同第3式证明,>改为>°,*改为^5.3外联接的结合律6二元集合运算三个表ⅤW、P的左外联接有两种:本文研究的二元集合运算有 union(并)、 except( oracle中用(1)W<>P式W和P都对Y联接V是两个外联接合miu,)、mma(交)三种,雨而min又分为 unon a和anmn用的左分量,为并行外联接。(2)V>W>P式W在对V的外联接中是右分量而在另两种,故共有四种集合运算。一外联接中是左分量称串行外联接6.1保留重复集合并并行和串行的左外联接在SQL中的语法为:union all是保留重复并,本文中用作未规范化的加运算V left join W on FI left join P on F2设V和W可加保留重复并的结果记作vUW把V和W的行不论相同与否都合并在一起。但仅作集合运算不做规范化操v left join W left join P on F2 on FI作,得到的是非规范的SQL表。由SQL表的加运算定义4知定理21串行组合外联攥的结合律若F是VW间的环UAW规范化后即为v+W因此两者相等:VU,W=V+W,V境无关条件,F2是WP间的环境无关条件且是非容空的(空值U,W的差分同和的差分上计算必是fae),则:d(vu, W)=dv+dw(V>WF11)>P|F2}=V>(W>P|F2)|F6.2消除重复集合并证明把等号两边各自用外联接定义展开:没有a的unin是无重复并。V和W无重复并是对vV>W)>P=(WW+V彐W)>P∪,W再作消除重复操作即[vUAW],表示为VUW。其实SQL=WW尸+(VW)P+WP+(VW丑P只要用下面的语句即可:(F2环境无关)elect x from V union select y from WV>(W>P)=v(W>P)+V3(W>P)两个 select都不用 distinct,它的作用已被 union包括。=v(WP+W丑P)+V丑W(門1环境无关,V下面的定义把并推广到负重数。丑(W>P)=V三W定义13保留符号消除重复并SQL表的无重复集合并两者区别在于V丑W部分。V三W分成(VW)彐P和(V是和的保留符号消除重复投影:W)丑P两部分第一式是第二式中的(v三W)彐P被替换成vUW=[Ⅴ了(v三W)P。例如,由于P2是WP间的条件V丑W(应是V豆W*中[W])中1(62),(72)|UH(7-2)=|(61)与P计算P2的是φ[W]的空行,F2是非容空条件,(V豆W)P1(62),(7-2)}U1(7-3)}=1(61),(7-1)。7期楼荣生:SQL差分145重复并满足结合律,即:F&F3。由此(VIUV2)UV3=VIU(V2U V3 )=VI UV2U V3vn(WnP).rep(0)=(∩W)∩P.rep(x0)证明由交换律,(vlUV2)UⅤ3=V3U(ⅥuV2),所以由此结合律得证。只要证明(v1UV)Uv3=ⅥuVU3,即[[Ⅵ+V2]+V3]交的结合律没有正表限制。=[Ⅵ+v2+V3]。若用在x=V.cos的重数表示则为:64交与差的差分sign(sign(VI. rep(x)+v2. rep(x))+V3. rep(x))当V无重复时,由定义14交和差对Ⅴ的差分是线性sign(vI rep(x)+v2. rep(x)+v3. rep(x))由第2节辅助等式(7),取x=V.rep(x)+V2rep(x)的。故v3.rep(x)即得待证的等式。vld(ⅤnW)=dv∩W,vd(v-W)=dv-W有负重数时结合律不成立。如设Ⅵ1V2=1(7-1)},v3=消除重复集合交满足交换律:V∩W=W∩V。由多元展开(71)|。则(vxV2)xV3=空,而Ⅵx(V2xXV3)=1(07-公式得1)d(v∩W)=(d∩Wo)+(∩dW)它理24消除重复集合并的差分V和W都是正SQL集合差不满足交换律。但V→W=V-V∩W,由此表消除重复集合并UW的差分是:Wd(V→W)=-Wd(vnW)=-(V∩dW)d(vuw)=signwhole(dv+dw)(28)于是得:证明由VuW=[V+W],d(VuW)=d[V+W]=sigd (v- w)=(dv wo)-(vndw)总结上面的推导得下述定理63集合交与差定理26交与差的差分V和W都是无重复可加SQL这里只讨论消除重复的集合交 intersect(n)和集合差ex表集合交V∩W与集合差V-W的差分分别可用式(29)、cep(-)。根据集合论,若VW无重复,成立等式(v∩W)+(30)计算。(V- W)=VV和W可重复时式(29)、(30)的dV和dW要替换成d[V]藉助于量词定义一般表(重数可大于1或负)V和W的交和d啊]。和差如下定义144交与差SQL表V和W可加,分别称7应用例:关系除法VOw=[V]3WIV cols= W cols&sign(V. rep)=sign( W rep)V-W=[V]3WIV cols=W cols&sign(V. rep)=sign(W rep)I作为本文所述理论的一个应用,本节讨论关系代数中定义为VW的交Ⅴ∩W和差=W。的关系除法,目标是导出计算关系商及其差分的SQL查询语当Ⅴ和W正时,不论是否有重复,该定义与SQL的句。计算关系商的SQL查询语句虽然在数据库的教科书中可sect和 except计算结果一致以找到,但导出过程却罕有记载。设ⅤW规范,x=V.cols,y=W.cols。由此可计箅集合交与二元关系A(x,y)除以一元关系B(y)的商是一个新一元差在(x0)的重数:关系,记作MB,是A中与B全部y对应的x。如下面的数字例vnW rep(0)=[V]. rep(x0).sign/ W rep(r)所示例7关系除法的数字例V-W rep(x0)=[V]. rep(x0).(1-sign]Wrep(y))A(x, y) B S(x) SB因ⅤW规范故F=|.cols=W.cols&sign(v.rep)=sig1 I11(W.rep)是一对一的。但求和号不可取消因为可能有不存在122y的情况,这时求和结果为0。交的交换律是明显的。下面的定理证明交满足结合律。关系A(xy)和B(y)的商也可定义为是使S(x)B(y)sA定理25交的结合律表VWP规范可加则(vnW)∩(x,y)的最大S。由此有A=SB+R,R是该除法的余关系。上=vn(W∩P)。面例中的余关系是{(21)|。证明设x=v.cols,=W.cols,=P.col则关系B可限定为非空。因为若B空则SB也空,S不定。(nW)∩P.rep(x0)余关系R为空时关系除法是笛卡尔积的逆运算:=[v]rp(0)* sign tW.rep()·g】Pmp(2)(A/B)B=A (SB)/B=Ssign X W,rep(y)P rep(z)等式A=SB+R的等号两边对x作消除重复投影。由于S其中F]={x=y&aign(V.rep)=sign(W.rep)},F=|x=2&sign的最大性,R中每一x不对应B中的全部y,R与SB不相交,消V.rep)=sign(P.rep)}。另一方面:除重复投影对加可分配。由此得vo(WnP). rep(xo)A[x]=(SB+R)[x]=S+R[x][VJ. rep(20).sign E(wnP).rep(r)S=Alx]-R[x(31)故要计算S可以先计算R[x]。故(31)等号两边与B作笛[V]. rep(:0).sign E(W rep(r)sing EP. rep (z))卡尔积然后用A-R代替SB,整理后得由第2节的辅助公式(7),求和号内的sign可去:ALxB-A=RIxJB-R(32)上式=[V].m(0)*2(Wmp()Pm(y)2)A[x]B与R[x]B是笛卡尔积。式(32)等号两边各是把A计算机应用与软件2010年明A与R的补相同,记作R。例7中A与R的补是(22)。(*)}(A.x,A,y)}(A.x,A.y,sign(rep):rep)由定义,R[x]中的每一x均不对应B的全部y,故R与R有相同为计算F必须把A分配到Z2内部,即dBA0:al{F{、B的x(但每一x对应的y不同),即Rx]=R[x]。于是dA:alF和BdA:alF上,同时也把A的列名加入相应的投R[x]=R1x]=(R[x]B-R)[x]=(A[x]B-A)[x]影中。得:S=A[x]-(ALx]B-A)[x]dl=dA彐220-该式两个减运算的减项都是被减项的子集,减运算可替换(/*Adz2*为集合差,得关系商的一种计算方法AdB 3 A0: al FI(Ax, A. y, B y b_y, repS=A[x]-(A[x]B→A)[x]/*by是B.y的别名以避免与A.y同名率进一步用不存在量词替换集合差(A"BdA: al FI(A.x, A y, B y b_y, sum( rep): rep)S=Alx]3(A: al[x]B 3A: 2lx=al x&y =B yl)Ia.x=al, xII (y)EAB'dA: al Fl/yi rep count(*)I(y)最后注意到Aa1和a2是同一表且有条件|ax=al.x}相(x, y, b_y, sign( rep):rep联系。因量词次方可以使用主方的列故al可省略而把条件中)/(A.x,A.y)的a1x改成A.x,得到了较为高效的计算MB的表达式:(x, y, sum( rep): rep)S=A[x]3(B 3A:alIx=A. x&y=B yl)(34)I(Ax, A y)EAB 3 A0: AI FI/(A x, A y)(al为原a)对应SQL语句:(*)I(A.x, A y)I(A.x, A y, sign( rep):rep)select distinet x from a where not exists最后,把dZ与Z1代入d0即得所求差分dzo(x, rep(select. fromm A al where x=A. x and y= B y))=dzi(x)ix Zi irep count(*)I(x)I(x, sign(rep):再推导式(34)的差分。分解成四个查询的嵌套其中F是rep)al. x=A. x&B y=al. y=(/*dZ1*20(x)=Zl[x]彐220ZI(x, y)=A 3Z222(y)=B彐23AdB 3 A0: al I FI(Ax, A y, B y b_y, rep.Z(x, y)=A: al I FI(ABdA: alI FI(A. x, A. y, B. y b_y, sum(rep): rep由式(9)和定理19,各自的差分为I (y)#ABdA: al I FI/yl rep< count (+)I(y)dzo(x, rep )=signwhole( dzI (x), ZI(x))(x, b_y, sign(rep): rep=d(x)ⅸx/x0dzi =dA 3 Z20select,sign(rep)rep from/.[b] Begin/select x, y, sum( rep)rep fromdB彐A0:lFl(乱.xx,ayy,sum(mp)(BdA: al I FI(y, count(.): rep)I(y)E BdA: al I FI/yI rep < count(.)I(y)I(y, sign (rep): rep)select from a0 al where al x=a. x and al. y =b y)group by a x, a y having sum( rep)<>0(A. x, A y, sum(rep): rep)union allA y)E A"B? A0: AI FI/(Ax,Acountfrom/.d[aa第7期楼荣生:SQL差分147相对误差2.5%2,7%select &.I x, y y, b y b_y, suwhere al x=a. x and al. y =b. y group by a x, a. y, b yL与S的相对误差都在在允许范围之内。ng sum( rep)< >0方差D(S)=0.178D(S)2·A=0.351where(x,, b_y) not in从三维虚拟人体提取的领围线,是基于eMTM的虚拟衣片的上界如图8所示准确的领围线能搭建起准确的服装结构,并xx,.yy, b. y b_y frowhere al. x=a. x and al. y=b y group by a. x, a. y, b. y hat且在虚拟服装的数据处理与三维显示上不会出现错误与失真ingp< count(·))/·d[aal]End·/group by x,y having sum( rep)<>0select a. x x, a. yy from a, b where not existsselect from a al where al. x=a. x and al. y=b. y图8领围线为服装衣片的上界group by a. x, a, y having rep count(.))/d[b] End./4结论ng sum(rep)<>0)where(x) not in本文提出的方法能够准确自动地从三维虚拟人体上提取领图线。为服装设计和制造做了必要的铺垫,并且大大提高了select a,xx from a where not existseMTM系统的效率如表4所示。4对图1虚拟人体的颈围线提取计算结果select from b where not existsCPU时间()长度误差面积误差select from a al where x=a. x and y=b yl.8%2.6%group by a x having rep