SQL差分

第27卷第7期計算機應用與軟件Vol. 27 No. 72010年7月Computer Applications and SoftwareJul.2010SQL差分樓榮生(復且大學(xué)上海(國際)數據庫研究中心上海200433)摘要研究定義在變化中的數據庫上的查詢(xún)。一個(gè)查詢(xún)是一個(gè)函數,以數據庫表為自變量,也以數據庫表作函數值。SQL差分研究自變量變化對查詢(xún)結果的影響,推導出法則以精確推斷因自變量的變化而查詢(xún)結果應該發(fā)生的變化,從而產(chǎn)生了查詢(xún)差分的概念。對構成sL查詢(xún)的各種成份如投影、選擇、聯(lián)接、外聯(lián)接、二元集合運算等分別研究了各自的差分生成規則,也研究了這些成份相互復合所產(chǎn)生的查詢(xún)的差分構成方法,從而使所得出的方法幾乎復蓋了當前使用的大部分查詢(xún)語(yǔ)句。以此為目的,為SQL查詢(xún)設計了一套完善的代數符號以使對SQL查詢(xún)進(jìn)行代數推導成為可能,并據此發(fā)現了SQL系統中的許多鮮為人知的代數性質(zhì),有助于為SQL構造完整的理論基礎以取代關(guān)系代數。關(guān)鍵詞數據庫變化跟蹤物化視圖的增量修改SQL查詢(xún)表達式可重復集合SQL表的相等及加減法多維聯(lián)接和多維表SQL中的線(xiàn)性運算SL代數性質(zhì)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的視圖的變化量。但由于缺少算法,目前只能處理簡(jiǎn)單的視圖0引言定義,略為復雜一點(diǎn)的視圖定義,如聯(lián)接、子查詢(xún)等,現有的DBMS中增量修改方法還不能實(shí)現。本文的研究就是針對這結構查詢(xún)語(yǔ)言SQL,是關(guān)系數據庫標準語(yǔ)言,描述對關(guān)系數需求展開(kāi)的。據庫的操作,或是定義在關(guān)系數據庫上的運算。差分,是表達函用T表示物化視圖的源表(下劃線(xiàn)是矢量符號T表示由數變化的數學(xué)工具。當前函數值減上一時(shí)刻函數值所得的差是個(gè)或多個(gè)表組成的表矢量:T=T,T2,…,Tn;n>0),物化視向后差分,下一時(shí)刻的函數值減當前函數值所得為向前差分。圖S的定義是在T上的一個(gè)查詢(xún)S=Q(T),描述從T計算出SSQL差分研究變化中的數據庫及在數據庫上定義的查詢(xún)。一個(gè)的過(guò)程在SQL中是查詢(xún)語(yǔ)句。若對T的修改記在一組與T相查詢(xún)就是一個(gè)函數其中用到的表是該函數的自變量查詢(xún)所得對應的表中稱(chēng)為T(mén)的差分,在源表中是T的向后差分,其結果集是函數值。SQL差分研究數據庫變化對查詢(xún)結果的影中記錄有已對T的行所作的增加、刪除和修改,反映了T的當響,以及若把查詢(xún)視作函數時(shí)它的差分的構成法則。前值的形成過(guò)程。對S應作的修改相應地記為ds,是S(尚未數據倉庫的數據收集系統中廣泛使用一種稱(chēng)為物化視圖變化)的向前差分藉以把S變成與T的當前值對應的S的當( materialized view)的機制。物化視圖是一種有視圖功能的實(shí)前值。dS理論上應可從娌和T計算出:dS=C(哩,T),G應表根據源表的數據計算得到,但要隨著(zhù)源表數據的變化而變可從Q導出?；?。有兩種方式可實(shí)現跟蹤:完全重算和增量修改。因完全重因此跟蹤過(guò)程由三步組成:算工作量大耗時(shí)多故一般都愿意選擇后者。增量修改方法即是在視圖的當前值基礎上,加上或刪除從源表的變化量計算出收稿日期:2008-11-19。樓榮生,教授,主研領(lǐng)域:數據庫技術(shù)第7期樓榮生:SQL差分137(1)在數據源當對作插人、刪除和修改時(shí)用一定的方1.2SQL表法生成dT;定義2SQL表x是關(guān)系數據庫意義上的屬性集,ep是(2)由d和計算出dS并送到物化視圖所在的系統;非零整數。(3)在物化視圖所在的系統用ds修改S。1)形如v(x,rep)的一個(gè)表或視圖或一個(gè)以(x,rep)為輸本文第一節是第一步的一般概念。而第二步由扛和計出的SQu查詢(xún)稱(chēng)為SQL表下文也簡(jiǎn)稱(chēng)表。V是表名,中各屬算ds,即從Q推導出G開(kāi)創(chuàng )了一個(gè)稱(chēng)為SQL差分的廣闊的研性稱(chēng)為表的列,x也記作v.cols,是V中除rep外的所有列組成究領(lǐng)域。對各種不同的Q推導出G的算法是后面各節研究的的列集。p稱(chēng)為V的重數列。mp恒為1的表rep列可省去。內容。第三步是一個(gè)理論上的簡(jiǎn)單過(guò)程,本文不再研究。文中所有SQL語(yǔ)句都使用 Oracle語(yǔ)法,均可在 Oracle的9i(2)對表中任一行t(x00)∈V。n0是0在t的重數,記為本文讀者只要學(xué)過(guò)數理邏輯和SQL語(yǔ)言即可。文末所列數記為。V中所有Lx=的t的重數之和稱(chēng)為o在V的重或更高版本上運行。ep(x0)。Ⅴ.rp()=,p(1)參考資料清單僅供參考,其中文獻[1是關(guān)于 Oracle的SQL語(yǔ)言的,文獻[2]是關(guān)于SQL的1992標準的。學(xué)習SQL的其他材若x0gV,則定義Ⅴ.rep(x0)=0。料還可在網(wǎng)上找到。數理邏輯知識只要有大學(xué)離散數學(xué)中所學(xué)(3)若有限制rep>0稱(chēng)Ⅴ為正表的就可以了也可參考文獻[3]。閱讀本文不需要學(xué)過(guò)數學(xué)中(4)若Ⅴ每行的rep值恒為1。這時(shí)Pp可省去成為v的差分概念對此有興趣的讀者只要閱讀數學(xué)詞典(如文獻(x),稱(chēng)為V的無(wú)重數形式[4])或百科全書(shū)中的相關(guān)條目就夠了。v.rep(x)函數依賴(lài)于x,作為x的函數,定義域是無(wú)限集當且僅當x出現在V中時(shí)有非零值。1差分注意:如定義中所示,形如(x,rep)的結構表示表的列名,逗號是列名分隔符;而形如(x00)的結構表示表中的數據行,空1.1SQL查詢(xún)表達式格是數據分隔符。后面均按此協(xié)定為便于對SQL查詢(xún)語(yǔ)句的分析,引入一種符號表示法。定義3表的可加和相等兩個(gè)表V(x,rep)、W(y,rep),若xy列數相同且對應列的數據類(lèi)型也相同,稱(chēng)ⅤW是可并定義1設SQL查詢(xún)語(yǔ)句一般形式是:或可加的。若x(或y)的任意值在ⅤW的重數相等:V.repselect Z from V where F group by g having H(不考慮 order by子句)此語(yǔ)句用符號表示成veF|/GH/(p)=W.rep(0),則兩表相等(A),描述一個(gè)SQL查詢(xún)稱(chēng)為SQL查詢(xún)表達式。約定例2x是整數,下面的表vl(x,rep)、V2(x,rep)、V3(x)是(1)下劃線(xiàn)表示用逗號分隔的多項,如A=A1,A2,…,An相等的:(2)Ve是對應于Ⅴ的聯(lián)接表達式。如表VW的普通聯(lián)接VI(x, rep) V2(x, rep) V3(x)表示成Ⅴ*W或簡(jiǎn)單地表示成ⅤW。其它聯(lián)接及表示法后面逐71個(gè)引進(jìn)。(3)FH中的and用&代替,or用或Ⅴ代替,not用!代888替。 y is null表示為“y空”,而 y is not nul為“y非空"。exis與 not exists表示為彐與彐,in和 not in表示為∈和g, left join同一表在相等的意義上有多種表示形式。其中兩個(gè)表示式有特殊意義:如例中V3,這是無(wú)重數形式,是通常出現在數據(4)Y或A中的換名(Ome中是空格, SQL Server等中用庫中的表的形式;若值在表中不重復,是規范形式。對應的字a)用冒號表示。如al+a2:b表示列的表達式al+n2在輸p表示在表中的重數。如例中v2。出時(shí)換名為b。v所示是不規范的SQL表是最一般的表示形式。5)如果A中有 distinct,(A)改為[A]。實(shí)際數據庫中的表大多是有主鍵的正表,是無(wú)重數形式的(6)A是*時(shí)(*)可省去。規范表。當對這些表作了投影或并時(shí)才產(chǎn)生重數大于1的表,例1SL查詢(xún)表達式表T(x),其中x=(p,y,z)而且可能是不規范的(1)TIp<100;(y, z)=Select y, z from T where p<100對表Ⅴ(x,rep)作規范化的SQL語(yǔ)句(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無(wú)重數形式表V(x)的規范化語(yǔ)句為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無(wú)重數形式和規范形式對于每一正表都存在且1.3表的加法和減法(5)T:aly=TIp=a pl(max(y))I Select from Ta定義4表的和與差可加的兩個(gè)表(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兩表合成一表,然后規范化。語(yǔ)句是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在符號的使用上有一點(diǎn)混淆:若z=x=V.cols,則Ⅴ(x,rp)group by x having sum(rep)<>0在x的保留重復投影按定義記為Ⅴ(x),與V(x,rep)相同。故Ⅴ表的加運算滿(mǎn)足交換律和結合律。W是空表則V+W=V。W是-V則V+W=空。與某(x)可能是一個(gè)無(wú)重數列的表也可能是另一表的保留重復投影。必要時(shí)將在上下文中明確說(shuō)明表V可加的所有SQL表V|與加運算構成交換群。定理3投影可加性設Ⅵ(x,rep)、V2(x,rp)是兩個(gè)可1.4SQL表的差分加的SQL表,Sx。則保留重復投影對加可分配定義5差分設SQL表Ⅴ的當前值是從Ⅴ經(jīng)過(guò)一系列的(v1+v2)(z)=V1(z)+V2(z)Insert, delete和 update得到。Q(V)是Ⅴ上的一個(gè)SQL查詢(xún)。明由SQL表相等定義3,只要證明等號兩邊對任意值dQ(y))=Q(V)-Q(vo)稱(chēng)為Q()的差分Vo稱(chēng)為Y的初值20的重數相等。由式(3)得由定義5得到以下三個(gè)結論:(Ⅵ+V2)(2).mp(20)=E(v1+V2).rp(x)(1)設Q()=V。則:由表相加定義4及式(3)dy=y-vo?；騞(v1,V2,…,Wn)=(dvl,dv2,…,dvn)=(V1-v10,V2-V20,…,vn-Vn0上式=3.rp(x)+2m()=V1()m()+dv的數據可建ine,deyd個(gè)igr產(chǎn)生。若系2(2,rp()統有備份v0,則可直接計算-V0得到。推論保留重復投影差分對表V(x)或V(x,rep),設z(2)設Q(y)是物化視圖。當y從v變到當前值時(shí),Q=Qx,則:V)的值還保持在00=Q(v0)。為得到Q只要做Q0+dQ。定d(v(z))=dv(z)義5是從Q產(chǎn)生唄Q的一種方法,即完全重算。本文研究增量證明d(v(z)=V(2)-V0(z)=(V-V0)(z)=dv(2)。方法。定義7一元線(xiàn)性運算對可加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)),則(注意與數學(xué)分析中的復合函數導數不同)稱(chēng)G對加可分配,也稱(chēng)為一元線(xiàn)性運算。d(Q(s(v)))=dQ(d(s(v))由定理3保留重復投影是一元線(xiàn)性運算。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等價(jià)。必要性是明顯的。充W)=dⅤ+dW。分性只要為滿(mǎn)足x20的任意值x找出滿(mǎn)足02y0,x0220的明設VW的初值為vo、w0,則由定義5及加法的交0即可。而此即是x0中包含的z上的值換律和結合律,2.2消除重復投影d(+W)=Ⅴ+W-(v0+W0)=(V-V0)+(W-W0)=d+dW從一個(gè)SQL表V中取互不相同的,zsv.cols,這一操作稱(chēng)2投影與選擇為對z的消除重復投影,可用帶 distinct的查詢(xún)計算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。稱(chēng)f(x))=sign(x)等式也成立。是F的特征函數,用AF表示。然后計算待證等式兩邊重數。第一式:特征函數用以計算有選擇的查詢(xún)的重數。V|F在(x0)的[VLz3 rep(20)=sign E[V]=sign sign(V. rep(2))重數是:用輔助等式(7)把求和符號內的sig逐個(gè)刪去,所得等式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環(huán)境無(wú)關(guān)查詢(xún)Ⅴ|F|的條件F稱(chēng)為是環(huán)境無(wú)關(guān)用輔助等式把括號內的sig刪去,所得等式即是[V+W]的設b是與Ⅴ的類(lèi)型匹配的行,F在b上的值F(b)只與b有關(guān)在x0的重數。而與Ⅴ的內容無(wú)關(guān)。[V]的差分是d[V],記錄因d的變化而引起的[V]的變義的意思是,不論b是否在Ⅴ中及V中有些什么行,F(b)化。因為只有當在Ⅴ中出現的x的一個(gè)值0全部是新加入的,不受影響。例如,若F有組函數則不是環(huán)境無(wú)關(guān)的,因F(b)與或者V0中的0在V已全部被刪去,才會(huì )對[Ⅴ]產(chǎn)生影響,使和b同一組的其他行有關(guān),因此滿(mǎn)足環(huán)境無(wú)關(guān)的條件必須是行[]增加或刪去該x0。條件。若F中含有重數,因重數實(shí)際上是組函數 count(*),也用 whole(dv,V)或簡(jiǎn)單地 whole(dV)記dⅤ中這些能使不是環(huán)境無(wú)關(guān)的。[ⅴ發(fā)生變化的行稱(chēng)為d的全加全刪子集其中的行使[]即使行條件,也有不是環(huán)境無(wú)關(guān)的:有增1行或減1行的變化。所以dV]是 whole(dv)的保留重例5查詢(xún)復投影:sign( wholw(dv),簡(jiǎn)單地寫(xiě)作 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}}不是環(huán)式(8)的代以V(z)。因式(4),d(V(2))=dV(z),得消境無(wú)關(guān)的。設V有兩組值v1={2|、V2=11,2。則v1F}=除重復投影的差分空,V2|F}=12}。F(2)在Ⅴ1中是 false,在Ⅴ2中是tued(v[z])=signwhole(dv(z), v(z))事實(shí)上,決定F(b)的除了b外還有組成F的子查詢(xún)。設F為推導出 whole(dv)的表達式,把dv的行分成三類(lèi):tabs是用在F的子查詢(xún)中的所有表。則有下面的充分條件判斷(1)全刪類(lèi)這類(lèi)行重數均為負,其中的不再在V中;F的環(huán)境無(wú)關(guān)性。(2)全加類(lèi)這類(lèi)行也在Ⅴ中存在,且在V的重數與在dv定理7環(huán)境無(wú)關(guān)判別法查詢(xún)Ⅴ{F|中若Y與F. tabs無(wú)的重數相同;相同表則F是環(huán)境無(wú)關(guān)的。(3)其他這類(lèi)行中的x也在Ⅴ中,但重數不同。由定理證明F(b)實(shí)際上是F(b,F,tabs),與F.tabe沒(méi)有相同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稱(chēng)為2維SQL表,而ⅤW、VW等一致地是一維SQL時(shí)Y的表可能有 trigger會(huì )影響F.thbs的內容。如果Y的tger表。w是xy的別名。特別是當x、y中有相同列名時(shí)x、不影響Ftbs,則對Ⅴ修改也未尚不可。中必需規定不同的別名。當x、X中無(wú)相同列名時(shí)w、w可直接定理8選擇對投彩和加的分配選擇條件F環(huán)境無(wú)關(guān)使用x、y①對表v(p,,rep),選擇條件F只與z有關(guān),則: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的重數:維和多維笛卡爾積滿(mǎn)足結合律(證略)。因此SQL表與V(z){F|,Pp(0)=V(z).rp(功0)*AF=(∑V.rp(p,z)*AF笛卡爾積構成半群F只與z有關(guān),對于求和符號中的(p,2)因z=常數0,AF是交換VW的順序,定義11產(chǎn)生的結果列的排列不同。常數,由此有:般理論忽略這種差別而認同笛卡爾積是可交換的。但因為vW上式=vm(e)AP)=Fmp(P)與WV明顯是不可加的,所以從SQL的觀(guān)點(diǎn)兩者不相等,因而本文認定笛卡爾積不可交換。=Ⅴ|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只與有關(guān)因而與重數無(wú)關(guān)。由式(6)等號左邊又可32二維表的投影以是多維表的任意一個(gè)重數列也可作全表的重數列。由此,對[V(z)|F]=[V()]{F|=V2]|F多維表的操作可以歸結到一維表,只要指定其中一個(gè)重數列為由此第二式成立整個(gè)表的重數列即可,語(yǔ)法是“表名\”。如對規范表Ⅴ(x,rep)、②F環(huán)境無(wú)關(guān),式中3個(gè)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地表示出計算過(guò)程,而第二種方法與一維表的方法一致,著(zhù)重于I FI). rep(xo)最后結果的表達。例如,若zGx,tGY,先對ⅤW作v'!投影再根據定義3等式成立。對它作投彩為va(Wu(W));而先投影z再投影!則是W推論表Ⅴ的選擇條件F環(huán)境無(wú)關(guān)選擇的差分等于差分(v(vw)。用第二種方法表示兩者都是vw(x!)。而如的選擇投影v(W[VW]),先對作消除重復投影再對z作保留重d(VF)=dv{Fl。復投影,就不能用第二種方法表示。證明設Vo是V的初值由上所述兩種投影在(0t0)的重數是:d(VIFI)=VIFI-VOIFEF環(huán)境無(wú)關(guān),由定理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聯(lián)接爾積與投影可交換順序,即下列各等式成立(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中兩個(gè)表Ⅴ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(甲)產(chǎn)由式(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)第三個(gè)等號是由于乘積的符號等于符號的乘積。= 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\"指定對Ⅴ維相加。若進(jìn)一步用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二元線(xiàn)性運算二元關(guān)系運算若滿(mǎn)足對加運式(3):第二式的證明類(lèi)似第一式對于在二維上都有的投影,從定理9可得與第一式相似的算的左分配律即對第一分量滿(mǎn)足分配律稱(chēng)左線(xiàn)性的;若滿(mǎn)足等式:右分配律,稱(chēng)右線(xiàn)性的,若滿(mǎn)足左右分配律,稱(chēng)為線(xiàn)性(二元)的。Viz(W\t(vW))=Viz(vw(t)=v(z)w(t)V\z[ W\[ V-W]]=viz[vw[t]]= v[z]w[:](11)定理1l二元運算全差分展開(kāi)設ⅤW是SQL表。對于3.3笛卡爾積的加法個(gè)二元關(guān)系運算V6W,全差分可如下計算:d( vew)=Vid( vewo)+W\d( vew)同樣的思路處理多維笛卡爾積的加法指定任一維為操作或ld(veW)+Wd(Vo⊙W)(13)維作一維表加法,如下例其中V\d、W\d表示只對前綴中分量的差分,另一分量無(wú)變化例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代入再運用分配律即得。等的值為這一規則還能進(jìn)一步推廣到多元關(guān)系運算G(v1,v2VIWI V2-W2 VI-W1+v\v2*W2 VI"w1+W\V2*W271817182718171837182定理12多元展開(kāi)公式n個(gè)變元的SQL查詢(xún)表達式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)?！芕ldG(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證明用數學(xué)歸納法。略。W*(V1+V2)=W*ⅤI+W*V2如果G對Ⅴi是線(xiàn)性的,則(VI +12)W=VI"W+V\v2"Wvidc(v1,…,vi,…,Vm0)=G(,…,dVi,…,vno)。W(VI+v2)=wVI +V\WV2證明第一式證明在(x)的重數等號兩邊相等。3.5聯(lián)接((VI+ v2).W). rep(xy)=(VI + V2).rep(x).W rep在笛卡爾積中加選擇條件即為聯(lián)接。V和W的一維和二維聯(lián)接用V*W|F(或ⅤW{F|)和ⅴWF表示,這時(shí)F也稱(chēng)(Vl. rep(x)+ V2. rep(x)).W rep(y)聯(lián)接條件。如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)維和二維聯(lián)接VWF|vWF|在(0y0)的重數是第二式由第一式用交換律得出。VWIFI. rep(x0 y0)=V rep(x0)+Wrep(yO)+AF第三式。推導過(guò)程同第一式,只是*替換成號。第四式由VoWIFI rep(xo y0)=V rep(x0)W rep(y0).AF142計算機應用與軟件2010年作為聯(lián)接條件的F一般總與兩個(gè)表的列有關(guān)。但SQL的證明聯(lián)接條件環(huán)境無(wú)關(guān)時(shí)聯(lián)接滿(mǎn)足分配律。只要在笛卡語(yǔ)法上也允許條件F只與一個(gè)表有關(guān),這時(shí)的F稱(chēng)為限定條件,爾積差分公式(12)等號兩邊加聯(lián)接條件即得定理結論沒(méi)有聯(lián)接作用。定理13笛卡爾積與限定條件規范表V(xPp)W(x,4量詞rep)的二維笛卡爾積與Ⅴ表的限定條件F可交換執行順序VWIFI=ViFI"W量詞子查詢(xún)是指 where或 having子句中含有 exists或not若F與重數無(wú)關(guān)則對一維笛卡爾積也成立:exists前者當子查詢(xún)結果非空為真,稱(chēng)為存在量詞;后者是當vwF=Ⅴ|F|W(14)子查詢(xún)結果空時(shí)為真稱(chēng)不存在量詞證明證明一維笛卡爾積等式(14)。左邊在(x0y0)的重因為其他子查詢(xún)都可以等價(jià)地表示為量詞,本文只研究量數為:詞子查詢(xún)VWIFI. rep(x0 y0)=V rep(xo)*W rep(yO)+AF4.1存在量詞F是V的限定條件只與Ⅴ有關(guān),AF與V.rep(xo)組成Ⅴ含有存在量詞的查詢(xún)一般形式如: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該查詢(xún)的表達式是v}F0&彐W|F}。查詢(xún)結果是Ⅴ中滿(mǎn)(yo)=VIFI W rep(x0 yo足F0且能與W通過(guò)F聯(lián)接的行但與能聯(lián)接的W的行數目無(wú)根據定義3等式(14)得證。二維的等式證明方法相同。關(guān)。如果沒(méi)有F0,即可簡(jiǎn)單地記為v彐WF其中Ⅴ稱(chēng)為存在由此定理可得一推論量詞的主方,W為次方。注意到F0與W無(wú)關(guān),所以該查詢(xún)等價(jià)推論規范表v(x,rp)W(Y,rp)的聯(lián)接與ⅤW表的重于VF|WF。數無(wú)關(guān)的限定條件可合并借用謂詞演算的符號彐表示eait是合理的,因為Ⅴ彐W(VIFIIWI F2I) F31=V" FI&F2&F3FF|就是謂詞演算中存在量詞彐yP(y)的具體化,只要令P是“y(VIFIIWIF21)IF31= VWI F1&F2&F31∈W&F(x,y)”即可,用SQL的述語(yǔ)是“WF非空(當F1、F2重數無(wú)關(guān)(15)彐W|F}或彐Q作為選擇條件是對子查詢(xún)Q的非空性測證明由定理13,把F1、F從括號中移出試。易驗證(VIFIl W F2I) F31=VWIFll F21 I F31=vWIFI&F2&F31彐Q1&彐q=3(Q1*Q2),當Q2≠-Q1:彐QlV彐Q2關(guān)系代數的運算優(yōu)化規則中有一規則是把投彩和選擇移到=彐(Q1Uq2)=3(Q1+02)(17)第一式是:Q1、Q2都非空當且僅當Q1*Q2非空第二式是聯(lián)接前。在SQL表中也可證明這一規則可行:定理14聯(lián)接與投彩規范SQL表VW的聯(lián)接WW丿F/當≠-Q1,Q1、Q2之一非空當且僅當QUQ2非空。但當Q2=-Q1時(shí)雖Q1Uq2非空而Q1+Q2空。第6節將為有負中設zv.cols,tgW.col,F環(huán)境無(wú)關(guān)且只與z有關(guān)。則:重數的表定義并運算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表示無(wú)條件。平方的作用是變負重數為VWIFI(z).rep( 0 tO)=E VWIFI rep(yy正。若W是正表則平方可不要So(V. rep(x)Wrep(yAF)定理16存在量詞基本定理表Ⅴ(x,rep)規范,W(x)正表。存在量詞查詢(xún)v彐WF|是二維聯(lián)接WF對Ⅴ的消除因F只與n有關(guān)=(00)時(shí)求和號內的AF是常數移重復投影的一元化出求和號外,余下部分分開(kāi)成Ⅴ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}。等式成立。第三與第四式的證明類(lèi)另一方面:似,略。vwIF|[Ⅴ]rp(功o)=sign(vWF|(v).rep(c0))3.6聯(lián)接的差分=sign 2(V-W rep(xy)*AF)定理15聯(lián)接差分聯(lián)接條件F環(huán)境無(wú)關(guān)時(shí):=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無(wú)重復行。面VW第7期樓榮生:SQL差分1434.2不存在量詞1時(shí)uniy后各為Ⅴ彐W或Ⅴ彐W0。由此不存在量詞查詢(xún)是在 where中有 not exists的查詢(xún),用存在unify W\d(vw[])=Ⅴ彐W-Ⅴ彐W0=W\d(ⅴ彐W)量詞加下劃線(xiàn)彐表示不存在量詞。彐WF|與彐WF|作為兩W\d(v3 w)=unifysignwhole(v'dw(v), V"W(V))個(gè)查詢(xún)條件是互補的,對V中任何一行兩者不同時(shí)成立但必成第一式得證立其中之一。所以設Q=WF:由Ⅴ3W+Ⅴ彐W=Ⅴ得Wd(V彐W)=-Whd(V彐W),A(丑Q)=1-A(3Q)V3Q=VVQ(20)據此又可得不存在量詞的差分式不存在量詞也有類(lèi)似式(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不存在量詞也滿(mǎn)足左分配律(V))4.3量詞與保留重復投影unifysignwhole(vdW(v),vW(v))的表達式根據ⅤW的表示形式不同而有所不同。若兩者都是無(wú)重數形式時(shí):定理17量詞次方的保留重復投影規范表v(x,rep)、Wunifysignwhole(V'dw(V),V-W(v))(x,rep),YF只與x與重數有關(guān)。存在量詞和不存在量詞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)外聯(lián)接=Y丑W|F(,v即P,WrP(y)證明W(),mP(!)=W,rp(y)代替等號左邊的W(SQL外聯(lián)接有左、右、全三種,本文分別用>、<、<>表示。rp。代人后F不再使用w(t)呷而使用W唧p次方W(!)應普通聯(lián)接有一維和多維的,外聯(lián)接也有一維和多維。如V>W換成W是一維左外聯(lián)接例如V>W由兩部分組成:一是組成WF{的部分,該部分的dv(z): a3v(z): b a z=b. z&a rep=b rep重數是V.rep*W.rep,表示每一V行被重復W.rep次;另一是與W不可聯(lián)接的部分,該部分的重數是V.mep,這里的Ⅴ行只=dv(2):a=Vla.2=V.&8. rep=5V.rep(x)出現一次。故Ⅴ(x,mep)和W(y,rep)的一維左外聯(lián)接Ⅴ>W18量詞主方的投影SQL表Ⅴ(x,rp)規范,彐W\F|環(huán)F的重數是境無(wú)關(guān)。x,若量詞條件F只與z有關(guān),則存在量詞和不存在v>WF|rp(x)=V.mp(x)*(W.p(x)…AF+1-AF)v(2)3WF|=(V彐WF)(2)V和W的一維和二維左外聯(lián)接可定義為: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]表示只有一個(gè)空行的與W同類(lèi)型的表,V三WF證明由定理8的等式v(2)Fl=VF()和V[2]F=*4W與Ⅴ丑WF◆[W表示將丑WF|用空值加長(cháng)到viFI[J。彐W|F環(huán)境無(wú)關(guān)必丑W{F也環(huán)境無(wú)關(guān)。F用彐W與第一項等長(cháng)。SQL中有專(zhuān)用的語(yǔ)法計算外聯(lián)接。計算該兩左F{替換即得第一、三式、用三WF替換即得第二、四式。外聯(lián)接的語(yǔ)句: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環(huán)境無(wú)關(guān)。W0是W的初值V>WIFI =select* from V left join W on F:則(式中未寫(xiě)出F1):把保留字left改成 right或fu即為右或全外聯(lián)接。一維和d(v3w)=dv3W0+ unifysigmwhole(Vdw(V),ww(v))二維全外聯(lián)接定義為:dV三W)=dⅤWo- unifysignwhole(vdw(v),yW(v)<>WF}=V*WF|+Ⅴ彐WF*Φ[W]+φ[V]*W彐F證明因彐WF環(huán)境無(wú)關(guān),Vwd(V彐W)=dv彐W。再由V<>wiFl=WF|+v彐W|F|φ[W]+φ[V]w彐vF二元展開(kāi)公式可推得與左右外聯(lián)接的關(guān)系d(v彐W)=dⅤ彐Wo+Whd(v彐W)v<>W=vw+vW=V>W+VVV括號中兩項對W重數作減運算,而該重數如果有的話(huà)只能dV.x=V.x中用V. rep is null t作選擇是d的全刪子集,用是1又如果兩項都是1的話(huà)相減后抵消。兩項中只有一項是dv.rep=v.rep作選擇是全加子集。由此得 whole的外聯(lián)接計計算機應用與軟件2010年算法三個(gè)表VWP的內外混合聯(lián)接也有兩種。①(W)>Pwholel(dV,v)=dV>vdV.x=V.x&(V.rep空l(shuí)dv.rp=v.rep)②W(W>P)。對比式(9)用in的表示方法,外聯(lián)接法可使用索引因而可定理22與普通聯(lián)接的結合律若聯(lián)接條件環(huán)境無(wú)關(guān),以計算得較快。(W)>P=W(W>P)。5.2外聯(lián)接與投影證明由定義,(W)>P=WwP+(WW)丑P。由聯(lián)接條件定理20外聯(lián)接與投彩若外聯(lián)接的聯(lián)接條件只與投影境無(wú)關(guān),則:列有關(guān)且環(huán)境無(wú)關(guān),則與投影(保留或消除重復)可交換操作VwP+(ⅧW)彐P=W(WP+W彐P)=V(W>P)順序:5.4外聯(lián)接差分(V>W)(z)=V(z)>W(!)由于加號兩邊的表達式都是左線(xiàn)性的,所以外聯(lián)接也是左(ⅴ>W)(a)=V(2)>W(!)線(xiàn)性的。因此有:(V>W)[]=V[2]>w[!d(v>w)=dv>w0+Wld(v>w(V>W)[]=V[]>w[tW0是W的初值。把V>W用式(24)代入(第二個(gè)等號要其中≌V.cols,tsW.cols,聯(lián)接條件F只與z,t有關(guān)求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)因聯(lián)接條件環(huán)境無(wú)關(guān),由定理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真時(shí),V>W=V*W,(V>W)[n]=V*W[z]unifysignuhole((V>w)'dP(V), (V>W)P(n))V[z]W[!]=v]>w[!;展開(kāi)d(V>W)F假時(shí)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外聯(lián)接的結合律6二元集合運算三個(gè)表ⅤW、P的左外聯(lián)接有兩種:本文研究的二元集合運算有 union(并)、 except( oracle中用(1)W<>P式W和P都對Y聯(lián)接V是兩個(gè)外聯(lián)接合miu,)、mma(交)三種,雨而min又分為 unon a和anmn用的左分量,為并行外聯(lián)接。(2)V>W>P式W在對V的外聯(lián)接中是右分量而在另兩種,故共有四種集合運算。一外聯(lián)接中是左分量稱(chēng)串行外聯(lián)接6.1保留重復集合并并行和串行的左外聯(lián)接在SQL中的語(yǔ)法為: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串行組合外聯(lián)攥的結合律若F是VW間的環(huán)UAW規范化后即為v+W因此兩者相等:VU,W=V+W,V境無(wú)關(guān)條件,F2是WP間的環(huán)境無(wú)關(guān)條件且是非容空的(空值U,W的差分同和的差分上計算必是fae),則:d(vu, W)=dv+dw(V>WF11)>P|F2}=V>(W>P|F2)|F6.2消除重復集合并證明把等號兩邊各自用外聯(lián)接定義展開(kāi):沒(méi)有a的unin是無(wú)重復并。V和W無(wú)重復并是對vV>W)>P=(WW+V彐W)>P∪,W再作消除重復操作即[vUAW],表示為VUW。其實(shí)SQL=WW尸+(VW)P+WP+(VW丑P只要用下面的語(yǔ)句即可:(F2環(huán)境無(wú)關(guān))elect x from V union select y from WV>(W>P)=v(W>P)+V3(W>P)兩個(gè) select都不用 distinct,它的作用已被 union包括。=v(WP+W丑P)+V丑W(門(mén)1環(huán)境無(wú)關(guān),V下面的定義把并推廣到負重數。丑(W>P)=V三W定義13保留符號消除重復并SQL表的無(wú)重復集合并兩者區別在于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重復并滿(mǎn)足結合律,即: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]交的結合律沒(méi)有正表限制。=[Ⅵ+v2+V3]。若用在x=V.cos的重數表示則為:64交與差的差分sign(sign(VI. rep(x)+v2. rep(x))+V3. rep(x))當V無(wú)重復時(shí),由定義14交和差對Ⅴ的差分是線(xiàn)性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有負重數時(shí)結合律不成立。如設Ⅵ1V2=1(7-1)},v3=消除重復集合交滿(mǎn)足交換律:V∩W=W∩V。由多元展開(kāi)(71)|。則(vxV2)xV3=空,而Ⅵx(V2xXV3)=1(07-公式得1)d(v∩W)=(d∩Wo)+(∩dW)它理24消除重復集合并的差分V和W都是正SQL集合差不滿(mǎn)足交換律。但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都是無(wú)重復可加SQL這里只討論消除重復的集合交 intersect(n)和集合差ex表集合交V∩W與集合差V-W的差分分別可用式(29)、cep(-)。根據集合論,若VW無(wú)重復,成立等式(v∩W)+(30)計算。(V- W)=VV和W可重復時(shí)式(29)、(30)的dV和dW要替換成d[V]藉助于量詞定義一般表(重數可大于1或負)V和W的交和d啊]。和差如下定義144交與差SQL表V和W可加,分別稱(chēng)7應用例:關(guān)系除法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作為本文所述理論的一個(gè)應用,本節討論關(guān)系代數中定義為VW的交Ⅴ∩W和差=W。的關(guān)系除法,目標是導出計算關(guān)系商及其差分的SQL查詢(xún)語(yǔ)當Ⅴ和W正時(shí),不論是否有重復,該定義與SQL的句。計算關(guān)系商的SQL查詢(xún)語(yǔ)句雖然在數據庫的教科書(shū)中可sect和 except計算結果一致以找到,但導出過(guò)程卻罕有記載。設ⅤW規范,x=V.cols,y=W.cols。由此可計箅集合交與二元關(guān)系A(x,y)除以一元關(guān)系B(y)的商是一個(gè)新一元差在(x0)的重數:關(guān)系,記作MB,是A中與B全部y對應的x。如下面的數字例vnW rep(0)=[V]. rep(x0).sign/ W rep(r)所示例7關(guān)系除法的數字例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的情況,這時(shí)求和結果為0。交的交換律是明顯的。下面的定理證明交滿(mǎn)足結合律。關(guān)系A(xy)和B(y)的商也可定義為是使S(x)B(y)sA定理25交的結合律表VWP規范可加則(vnW)∩(x,y)的最大S。由此有A=SB+R,R是該除法的余關(guān)系。上=vn(W∩P)。面例中的余關(guān)系是{(21)|。證明設x=v.cols,=W.cols,=P.col則關(guān)系B可限定為非空。因為若B空則SB也空,S不定。(nW)∩P.rep(x0)余關(guān)系R為空時(shí)關(guān)系除法是笛卡爾積的逆運算:=[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上,同時(shí)也把A的列名加入相應的投R[x]=R1x]=(R[x]B-R)[x]=(A[x]B-A)[x]影中。得:S=A[x]-(ALx]B-A)[x]dl=dA彐220-該式兩個(gè)減運算的減項都是被減項的子集,減運算可替換(/*Adz2*為集合差,得關(guān)系商的一種計算方法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同名率進(jìn)一步用不存在量詞替換集合差(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聯(lián)系。因量詞次方可以使用主方的列故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語(yǔ)句:(*)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)的差分。分解成四個(gè)查詢(xún)的嵌套其中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從三維虛擬人體提取的領(lǐng)圍線(xiàn),是基于eMTM的虛擬衣片的上界如圖8所示準確的領(lǐng)圍線(xiàn)能搭建起準確的服裝結構,并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且在虛擬服裝的數據處理與三維顯示上不會(huì )出現錯誤與失真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領(lǐng)圍線(xiàn)為服裝衣片的上界group by a. x, a, y having rep count(.))/d[b] End./4結論ng sum(rep)<>0)where(x) not in本文提出的方法能夠準確自動(dòng)地從三維虛擬人體上提取領(lǐng)圖線(xiàn)。為服裝設計和制造做了必要的鋪墊,并且大大提高了select a,xx from a where not existseMTM系統的效率如表4所示。4對圖1虛擬人體的頸圍線(xiàn)提取計算結果select from b where not existsCPU時(shí)間()長(cháng)度誤差面積誤差select from a al where x=a. x and y=b yl.8%2.6%group by a x having rep