第27卷第7期計算機應用與軟件Vol. 27 No. 72010年7月Computer Applications and SoftwareJul.2010SQL差分樓榮生(復且大學上海(國際)數(shù)據(jù)庫研究中心上海200433)摘要研究定義在變化中的數(shù)據(jù)庫上的查詢。一個查詢是一個函數(shù),以數(shù)據(jù)庫表為自變量,也以數(shù)據(jù)庫表作函數(shù)值。SQL差分研究自變量變化對查詢結(jié)果的影響,推導出法則以精確推斷因自變量的變化而查詢結(jié)果應該發(fā)生的變化,從而產(chǎn)生了查詢差分的概念。對構(gòu)成sL查詢的各種成份如投影、選擇、聯(lián)接、外聯(lián)接、二元集合運算等分別研究了各自的差分生成規(guī)則,也研究了這些成份相互復合所產(chǎn)生的查詢的差分構(gòu)成方法,從而使所得出的方法幾乎復蓋了當前使用的大部分查詢語句。以此為目的,為SQL查詢設計了一套完善的代數(shù)符號以使對SQL查詢進行代數(shù)推導成為可能,并據(jù)此發(fā)現(xiàn)了SQL系統(tǒng)中的許多鮮為人知的代數(shù)性質(zhì),有助于為SQL構(gòu)造完整的理論基礎(chǔ)以取代關(guān)系代數(shù)。關(guān)鍵詞數(shù)據(jù)庫變化跟蹤物化視圖的增量修改SQL查詢表達式可重復集合SQL表的相等及加減法多維聯(lián)接和多維表SQL中的線性運算SL代數(shù)性質(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的視圖的變化量。但由于缺少算法,目前只能處理簡單的視圖0引言定義,略為復雜一點的視圖定義,如聯(lián)接、子查詢等,現(xiàn)有的DBMS中增量修改方法還不能實現(xiàn)。本文的研究就是針對這結(jié)構(gòu)查詢語言SQL,是關(guān)系數(shù)據(jù)庫標準語言,描述對關(guān)系數(shù)需求展開的。據(jù)庫的操作,或是定義在關(guān)系數(shù)據(jù)庫上的運算。差分,是表達函用T表示物化視圖的源表(下劃線是矢量符號T表示由數(shù)變化的數(shù)學工具。當前函數(shù)值減上一時刻函數(shù)值所得的差是個或多個表組成的表矢量:T=T,T2,…,Tn;n>0),物化視向后差分,下一時刻的函數(shù)值減當前函數(shù)值所得為向前差分。圖S的定義是在T上的一個查詢S=Q(T),描述從T計算出SSQL差分研究變化中的數(shù)據(jù)庫及在數(shù)據(jù)庫上定義的查詢。一個的過程在SQL中是查詢語句。若對T的修改記在一組與T相查詢就是一個函數(shù)其中用到的表是該函數(shù)的自變量查詢所得對應的表中稱為T的差分,在源表中是T的向后差分,其結(jié)果集是函數(shù)值。SQL差分研究數(shù)據(jù)庫變化對查詢結(jié)果的影中記錄有已對T的行所作的增加、刪除和修改,反映了T的當響,以及若把查詢視作函數(shù)時它的差分的構(gòu)成法則。前值的形成過程。對S應作的修改相應地記為ds,是S(尚未數(shù)據(jù)倉庫的數(shù)據(jù)收集系統(tǒng)中廣泛使用一種稱為物化視圖變化)的向前差分藉以把S變成與T的當前值對應的S的當( materialized view)的機制。物化視圖是一種有視圖功能的實前值。dS理論上應可從娌和T計算出:dS=C(哩,T),G應表根據(jù)源表的數(shù)據(jù)計算得到,但要隨著源表數(shù)據(jù)的變化而變可從Q導出。化。有兩種方式可實現(xiàn)跟蹤:完全重算和增量修改。因完全重因此跟蹤過程由三步組成:算工作量大耗時多故一般都愿意選擇后者。增量修改方法即是在視圖的當前值基礎(chǔ)上,加上或刪除從源表的變化量計算出收稿日期:2008-11-19。樓榮生,教授,主研領(lǐng)域:數(shù)據(jù)庫技術(shù)第7期樓榮生:SQL差分137(1)在數(shù)據(jù)源當對作插人、刪除和修改時用一定的方1.2SQL表法生成dT;定義2SQL表x是關(guān)系數(shù)據(jù)庫意義上的屬性集,ep是(2)由d和計算出dS并送到物化視圖所在的系統(tǒng);非零整數(shù)。(3)在物化視圖所在的系統(tǒng)用ds修改S。1)形如v(x,rep)的一個表或視圖或一個以(x,rep)為輸本文第一節(jié)是第一步的一般概念。而第二步由扛和計出的SQu查詢稱為SQL表下文也簡稱表。V是表名,中各屬算ds,即從Q推導出G開創(chuàng)了一個稱為SQL差分的廣闊的研性稱為表的列,x也記作v.cols,是V中除rep外的所有列組成究領(lǐng)域。對各種不同的Q推導出G的算法是后面各節(jié)研究的的列集。p稱為V的重數(shù)列。mp恒為1的表rep列可省去。內(nèi)容。第三步是一個理論上的簡單過程,本文不再研究。文中所有SQL語句都使用 Oracle語法,均可在 Oracle的9i(2)對表中任一行t(x00)∈V。n0是0在t的重數(shù),記為本文讀者只要學過數(shù)理邏輯和SQL語言即可。文末所列數(shù)記為。V中所有Lx=的t的重數(shù)之和稱為o在V的重或更高版本上運行。ep(x0)。Ⅴ.rp()=,p(1)參考資料清單僅供參考,其中文獻[1是關(guān)于 Oracle的SQL語言的,文獻[2]是關(guān)于SQL的1992標準的。學習SQL的其他材若x0gV,則定義Ⅴ.rep(x0)=0。料還可在網(wǎng)上找到。數(shù)理邏輯知識只要有大學離散數(shù)學中所學(3)若有限制rep>0稱Ⅴ為正表的就可以了也可參考文獻[3]。閱讀本文不需要學過數(shù)學中(4)若Ⅴ每行的rep值恒為1。這時Pp可省去成為v的差分概念對此有興趣的讀者只要閱讀數(shù)學詞典(如文獻(x),稱為V的無重數(shù)形式[4])或百科全書中的相關(guān)條目就夠了。v.rep(x)函數(shù)依賴于x,作為x的函數(shù),定義域是無限集當且僅當x出現(xiàn)在V中時有非零值。1差分注意:如定義中所示,形如(x,rep)的結(jié)構(gòu)表示表的列名,逗號是列名分隔符;而形如(x00)的結(jié)構(gòu)表示表中的數(shù)據(jù)行,空1.1SQL查詢表達式格是數(shù)據(jù)分隔符。后面均按此協(xié)定為便于對SQL查詢語句的分析,引入一種符號表示法。定義3表的可加和相等兩個表V(x,rep)、W(y,rep),若xy列數(shù)相同且對應列的數(shù)據(jù)類型也相同,稱ⅤW是可并定義1設SQL查詢語句一般形式是:或可加的。若x(或y)的任意值在ⅤW的重數(shù)相等:V.repselect Z from V where F group by g having H(不考慮 order by子句)此語句用符號表示成veF|/GH/(p)=W.rep(0),則兩表相等(A),描述一個SQL查詢稱為SQL查詢表達式。約定例2x是整數(shù),下面的表vl(x,rep)、V2(x,rep)、V3(x)是(1)下劃線表示用逗號分隔的多項,如A=A1,A2,…,An相等的:(2)Ve是對應于Ⅴ的聯(lián)接表達式。如表VW的普通聯(lián)接VI(x, rep) V2(x, rep) V3(x)表示成Ⅴ*W或簡單地表示成ⅤW。其它聯(lián)接及表示法后面逐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,這是無重數(shù)形式,是通常出現(xiàn)在數(shù)據(jù)(4)Y或A中的換名(Ome中是空格, SQL Server等中用庫中的表的形式;若值在表中不重復,是規(guī)范形式。對應的字a)用冒號表示。如al+a2:b表示列的表達式al+n2在輸p表示在表中的重數(shù)。如例中v2。出時換名為b。v所示是不規(guī)范的SQL表是最一般的表示形式。5)如果A中有 distinct,(A)改為[A]。實際數(shù)據(jù)庫中的表大多是有主鍵的正表,是無重數(shù)形式的(6)A是*時(*)可省去。規(guī)范表。當對這些表作了投影或并時才產(chǎn)生重數(shù)大于1的表,例1SL查詢表達式表T(x),其中x=(p,y,z)而且可能是不規(guī)范的(1)TIp<100;(y, z)=Select y, z from T where p<100對表Ⅴ(x,rep)作規(guī)范化的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無重數(shù)形式表V(x)的規(guī)范化語句為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無重數(shù)形式和規(guī)范形式對于每一正表都存在且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是一規(guī)范表x的任一值0在Ⅴ+W的重數(shù)是(6)T:a*T:b|a.p=b,p&a,y0兩表合成一表,然后規(guī)范化。語句是v(z)=v/z(VUA W)/xisum( rep)<>0|(x, sum( rep): rep)select x, sum( rep)rep from計算中作了規(guī)范化操作,結(jié)果是規(guī)范的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)相同。故Ⅴ表的加運算滿足交換律和結(jié)合律。W是空表則V+W=V。W是-V則V+W=空。與某(x)可能是一個無重數(shù)列的表也可能是另一表的保留重復投影。必要時將在上下文中明確說明表V可加的所有SQL表V|與加運算構(gòu)成交換群。定理3投影可加性設Ⅵ(x,rep)、V2(x,rp)是兩個可1.4SQL表的差分加的SQL表,Sx。則保留重復投影對加可分配定義5差分設SQL表Ⅴ的當前值是從Ⅴ經(jīng)過一系列的(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的重數(shù)相等。由式(3)得由定義5得到以下三個結(jié)論:(Ⅵ+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的數(shù)據(jù)可建ine,deyd個igr產(chǎn)生。若系2(2,rp()統(tǒng)有備份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產(chǎn)生唄Q的一種方法,即完全重算。本文研究增量證明d(v(z)=V(2)-V0(z)=(V-V0)(z)=dv(2)。方法。定義7一元線性運算對可加SQL表Ⅵ、V2的一元運(3)d(Q(y)作為函數(shù)它的自變量是Ⅴ和v或d和Ⅴ算G若成立:(因dⅤ=V-V0),把此函數(shù)記為dQ(dV,y)。如果是復合函數(shù)G(v1)+G(v2)=G(v+Ⅴ2)如Q(S(y)),則(注意與數(shù)學分析中的復合函數(shù)導數(shù)不同)稱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)。連續(xù)在和的保留重復投影等于在Y的保留重復投影證明由定義5與式(2),dv.rep(x)=V.rep(x)-V0.repY)=V(證明證明兩邊在任意值y0的重數(shù)相等。由式(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上的值換律和結(jié)合律,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但這樣定義不適用于負重數(shù)。本文使用下面的定義。2.1保留重復投影定義8保留符號消除重復投影SQL表V,zsV.cls,交定義6保留重復投!是屬性集,cvc。SQL表v在的消除重復投影,是對保留重復投影V的重數(shù)只取符號的保留重復投影記為v(2),是由形如t(zrp)的行組成的得到的SL表。記為v2]義,V[z]值0的重數(shù)是第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列。函數(shù)(F.cos)當F=tme取值1,當F=flse取值0。稱f(x))=sign(x)等式也成立。是F的特征函數(shù),用AF表示。然后計算待證等式兩邊重數(shù)。第一式:特征函數(shù)用以計算有選擇的查詢的重數(shù)。V|F在(x0)的[VLz3 rep(20)=sign E[V]=sign sign(V. rep(2))重數(shù)是:用輔助等式(7)把求和符號內(nèi)的sig逐個刪去,所得等式VIFI rep(x0)=V rep(x0)+ AF即是Ⅴ[z]在0的重數(shù)。易驗證下面的等式:第二式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)境無關(guān)查詢Ⅴ|F|的條件F稱為是環(huán)境無關(guān)用輔助等式把括號內(nèi)的sig刪去,所得等式即是[V+W]的設b是與Ⅴ的類型匹配的行,F在b上的值F(b)只與b有關(guān)在x0的重數(shù)。而與Ⅴ的內(nèi)容無關(guān)。[V]的差分是d[V],記錄因d的變化而引起的[V]的變義的意思是,不論b是否在Ⅴ中及V中有些什么行,F(b)化。因為只有當在Ⅴ中出現(xiàn)的x的一個值0全部是新加入的,不受影響。例如,若F有組函數(shù)則不是環(huán)境無關(guān)的,因F(b)與或者V0中的0在V已全部被刪去,才會對[Ⅴ]產(chǎn)生影響,使和b同一組的其他行有關(guān),因此滿足環(huán)境無關(guān)的條件必須是行[]增加或刪去該x0。條件。若F中含有重數(shù),因重數(shù)實際上是組函數(shù) count(*),也用 whole(dv,V)或簡單地 whole(dV)記dⅤ中這些能使不是環(huán)境無關(guān)的。[ⅴ發(fā)生變化的行稱為d的全加全刪子集其中的行使[]即使行條件,也有不是環(huán)境無關(guān)的:有增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}}不是環(huán)式(8)的代以V(z)。因式(4),d(V(2))=dV(z),得消境無關(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))事實上,決定F(b)的除了b外還有組成F的子查詢。設F為推導出 whole(dv)的表達式,把dv的行分成三類:tabs是用在F的子查詢中的所有表。則有下面的充分條件判斷(1)全刪類這類行重數(shù)均為負,其中的不再在V中;F的環(huán)境無關(guān)性。(2)全加類這類行也在Ⅴ中存在,且在V的重數(shù)與在dv定理7環(huán)境無關(guān)判別法查詢Ⅴ{F|中若Y與F. tabs無的重數(shù)相同;相同表則F是環(huán)境無關(guān)的。(3)其他這類行中的x也在Ⅴ中,但重數(shù)不同。由定理證明F(b)實際上是F(b,F,tabs),與F.tabe沒有相同140計算機應用與軟件2010年的表y替換成別的表不影響F.tabs,因而也不影響F(b,F若VW是規(guī)范的,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的內(nèi)容。如果Y的tger表。w是xy的別名。特別是當x、y中有相同列名時x、不影響Ftbs,則對Ⅴ修改也未尚不可。中必需規(guī)定不同的別名。當x、X中無相同列名時w、w可直接定理8選擇對投彩和加的分配選擇條件F環(huán)境無關(guān)使用x、y①對表v(p,,rep),選擇條件F只與z有關(guān),則:2uni函數(shù)可把2維SQL表轉(zhuǎn)化成一維: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)多維笛卡爾積僅對規(guī)范表定義。和式(3),左邊在0的重數(shù):維和多維笛卡爾積滿足結(jié)合律(證略)。因此SQL表與V(z){F|,Pp(0)=V(z).rp(功0)*AF=(∑V.rp(p,z)*AF笛卡爾積構(gòu)成半群F只與z有關(guān),對于求和符號中的(p,2)因z=常數(shù)0,AF是交換VW的順序,定義11產(chǎn)生的結(jié)果列的排列不同。常數(shù),由此有:般理論忽略這種差別而認同笛卡爾積是可交換的。但因為vW上式=vm(e)AP)=Fmp(P)與WV明顯是不可加的,所以從SQL的觀點兩者不相等,因而本文認定笛卡爾積不可交換。=Ⅴ|F|(2),rep(0)根據(jù)定義3等式成立。維和二維笛卡爾積WⅴW在(x0y0)的重數(shù)是第二式。第一式兩邊作消除重復投影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)因而與重數(shù)無關(guān)。由式(6)等號左邊又可32二維表的投影以是多維表的任意一個重數(shù)列也可作全表的重數(shù)列。由此,對[V(z)|F]=[V()]{F|=V2]|F多維表的操作可以歸結(jié)到一維表,只要指定其中一個重數(shù)列為由此第二式成立整個表的重數(shù)列即可,語法是“表名\”。如對規(guī)范表Ⅴ(x,rep)、②F環(huán)境無關(guān),式中3個F對同一行得相同值。由式W(x,mp),sY,vW在V和!保留重復投影是:(10),左邊在x0的重數(shù)W\t(VW)=V-W(Vt)(Ⅵ+V2)F|.rep(x0)=(Ⅵ+V2).rep(x0)*AF={(xvp!Ewep(r):tmp)|( x vrep)∈V,ywrp)∈W再由和的重數(shù)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)最后結(jié)果的表達。例如,若zGx,tGY,先對ⅤW作v'!投影再根據(jù)定義3等式成立。對它作投彩為va(Wu(W));而先投影z再投影!則是W推論表Ⅴ的選擇條件F環(huán)境無關(guān)選擇的差分等于差分(v(vw)。用第二種方法表示兩者都是vw(x!)。而如的選擇投影v(W[VW]),先對作消除重復投影再對z作保留重d(VF)=dv{Fl。復投影,就不能用第二種方法表示。證明設Vo是V的初值由上所述兩種投影在(0t0)的重數(shù)是:d(VIFI)=VIFI-VOIFEF環(huán)境無關(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中兩個表ⅤW的笛卡爾積為(3) Sy: Wi[VW]=(vw)[V!]VW=select from V. wv-w[t]; zCx: Viz[v-W]=(v-w)[zw]=v[z]w有重數(shù)列的SQL表的笛卡爾積一般定義為:證明(1)第一式。只要證明兩邊在(00)的重數(shù)相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)第三個等號是由于乘積的符號等于符號的乘積。= owo +dwwo)+( vOdW +dvdw)2)第一式。計算在(00)的重數(shù)。由式(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)是常數(shù):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中的分配律,故結(jié)(3)第一式。W[VW]=[W(vw)]=[vW(!)]論可以推廣到更一般的情形。v^w[!]。定義12二元線性運算二元關(guān)系運算若滿足對加運式(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笛卡爾積的加法個二元關(guān)系運算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代入再運用分配律即得。等的值為這一規(guī)則還能進一步推廣到多元關(guān)系運算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)?！芕ldG(v,…,v,0,,va0定理10笛卡爾積對加的分配律SL表Ⅵ(x,mp)、V2其中i=1,…,m;第i項的參數(shù)中從第i+1項起到n項都取(x,rep)、W(y,rep),其中v、V2可加,則初值。(VI+V2)·W=V1*W+V2*W證明用數(shù)學歸納法。略。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)的重數(shù)等號兩邊相等。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表示,這時F也稱(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)的重數(shù)是第二式由第一式用交換律得出。VWIFI. rep(x0 y0)=V rep(x0)+Wrep(yO)+AF第三式。推導過程同第一式,只是*替換成號。第四式由VoWIFI rep(xo y0)=V rep(x0)W rep(y0).AF142計算機應用與軟件2010年作為聯(lián)接條件的F一般總與兩個表的列有關(guān)。但SQL的證明聯(lián)接條件環(huán)境無關(guān)時聯(lián)接滿足分配律。只要在笛卡語法上也允許條件F只與一個表有關(guān),這時的F稱為限定條件,爾積差分公式(12)等號兩邊加聯(lián)接條件即得定理結(jié)論沒有聯(lián)接作用。定理13笛卡爾積與限定條件規(guī)范表V(xPp)W(x,4量詞rep)的二維笛卡爾積與Ⅴ表的限定條件F可交換執(zhí)行順序VWIFI=ViFI"W量詞子查詢是指 where或 having子句中含有 exists或not若F與重數(shù)無關(guān)則對一維笛卡爾積也成立:exists前者當子查詢結(jié)果非空為真,稱為存在量詞;后者是當vwF=Ⅴ|F|W(14)子查詢結(jié)果空時為真稱不存在量詞證明證明一維笛卡爾積等式(14)。左邊在(x0y0)的重因為其他子查詢都可以等價地表示為量詞,本文只研究量數(shù)為:詞子查詢VWIFI. rep(x0 y0)=V rep(xo)*W rep(yO)+AF4.1存在量詞F是V的限定條件只與Ⅴ有關(guān),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}。查詢結(jié)果是Ⅴ中滿(yo)=VIFI W rep(x0 yo足F0且能與W通過F聯(lián)接的行但與能聯(lián)接的W的行數(shù)目無根據(jù)定義3等式(14)得證。二維的等式證明方法相同。關(guān)。如果沒有F0,即可簡單地記為v彐WF其中Ⅴ稱為存在由此定理可得一推論量詞的主方,W為次方。注意到F0與W無關(guān),所以該查詢等價推論規(guī)范表v(x,rp)W(Y,rp)的聯(lián)接與ⅤW表的重于VF|WF。數(shù)無關(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的述語是“WF非空(當F1、F2重數(shù)無關(guān)(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關(guān)系代數(shù)的運算優(yōu)化規(guī)則中有一規(guī)則是把投彩和選擇移到=彐(Q1Uq2)=3(Q1+02)(17)第一式是:Q1、Q2都非空當且僅當Q1*Q2非空第二式是聯(lián)接前。在SQL表中也可證明這一規(guī)則可行:定理14聯(lián)接與投彩規(guī)范SQL表VW的聯(lián)接WW丿F/當≠-Q1,Q1、Q2之一非空當且僅當QUQ2非空。但當Q2=-Q1時雖Q1Uq2非空而Q1+Q2空。第6節(jié)將為有負中設zv.cols,tgW.col,F環(huán)境無關(guān)且只與z有關(guān)。則:重數(shù)的表定義并運算U:Q1UQ2是Q1+Q2的消除重復投影。VWIFI(z)=v(z)W(t)IFI這樣第二式成立必須有附加條件Q2≠-Q1。VWIFI[z]=v[z]wIt]IF)存在量詞彐WF的特征函數(shù)為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)的重數(shù)為:求和條件為tue表示無條件。平方的作用是變負重數(shù)為VWIFI(z).rep( 0 tO)=E VWIFI rep(yy正。若W是正表則平方可不要So(V. rep(x)Wrep(yAF)定理16存在量詞基本定理表Ⅴ(x,rep)規(guī)范,W(x)正表。存在量詞查詢v彐WF|是二維聯(lián)接WF對Ⅴ的消除因F只與n有關(guān)=(00)時求和號內(nèi)的AF是常數(shù)移重復投影的一元化出求和號外,余下部分分開成ⅤW兩部分得:v彐W|F|= unifyV-WIF[V]上式=,wm(3)WmP(x)AF該定理權(quán)作為本文對存在量詞的定義。下面證明這樣定義(z)rep(20)*W(!).rp(0)AF的合理性v(z)w()IFI rep(0 o)證明計算兩邊在x的重數(shù)并證明相等。由式(18),因W因(00)是任意值,由定義3所證等式成立。是正表求和號內(nèi)不用平方第二式。在第一式兩邊取符號,左邊即為ⅴ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聯(lián)接的差分=sign 2(V-W rep(xy)*AF)定理15聯(lián)接差分聯(lián)接條件F環(huán)境無關(guān)時:=V rep(xD)sign 2(.rep(y)+AF)d(wifi)=(dv)wolF) +Vdw i FI由此后者取uniy后兩者相等,定理得證=dvW FI-dWdVI FI +vdwiFld(V-WIFI)如果v不是規(guī)范的,不保證Ⅴ彐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)據(jù)此又可得不存在量詞的差分式不存在量詞也有類似式(17)的等式d豆W)=d丑W0+wld(VWQ≠Q(mào)1: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))的表達式根據(jù)ⅤW的表示形式不同而有所不同。若兩者都是無重數(shù)形式時:定理17量詞次方的保留重復投影規(guī)范表v(x,rep)、Wunifysignwhole(V'dw(V),V-W(v))(x,rep),YF只與x與重數(shù)有關(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重數(shù)是V.rep*W.rep,表示每一V行被重復W.rep次;另一是與W不可聯(lián)接的部分,該部分的重數(shù)是V.mep,這里的Ⅴ行只=dv(2):a=Vla.2=V.&8. rep=5V.rep(x)出現(xiàn)一次。故Ⅴ(x,mep)和W(y,rep)的一維左外聯(lián)接Ⅴ>W18量詞主方的投影SQL表Ⅴ(x,rp)規(guī)范,彐W\F|環(huán)F的重數(shù)是境無關(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]表示只有一個空行的與W同類型的表,V三WF證明由定理8的等式v(2)Fl=VF()和V[2]F=*4W與Ⅴ丑WF◆[W表示將丑WF|用空值加長到viFI[J。彐W|F環(huán)境無關(guān)必丑W{F也環(huán)境無關(guān)。F用彐W與第一項等長。SQL中有專用的語法計算外聯(lián)接。計算該兩左F{替換即得第一、三式、用三WF替換即得第二、四式。外聯(lián)接的語句:4.4量詞的差分V>WIFI = select x, y, V rep nvl( W rep, 1)rep from V定理19量詞差分規(guī)范SQL表V(x)或V(x,rp), w left join W on F;(y)或W(y,mp)正表,彐WF環(huán)境無關(guān)。W0是W的初值V>WIFI =select* from V left join W on F:則(式中未寫出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)境無關(guān),Vwd(V彐W)=dv彐W。再由V<>wiFl=WF|+v彐W|F|φ[W]+φ[V]w彐vF二元展開公式可推得與左右外聯(lián)接的關(guān)系d(v彐W)=dⅤ彐Wo+Whd(v彐W)v<>W=vw+vW=V>W+VVV括號中兩項對W重數(shù)作減運算,而該重數(shù)如果有的話只能dV.x=V.x中用V. rep is null t作選擇是d的全刪子集,用是1又如果兩項都是1的話相減后抵消。兩項中只有一項是dv.rep=v.rep作選擇是全加子集。由此得 whole的外聯(lián)接計計算機應用與軟件2010年算法三個表VWP的內(nèi)外混合聯(lián)接也有兩種。①(W)>Pwholel(dV,v)=dV>vdV.x=V.x&(V.rep空ldv.rp=v.rep)②W(W>P)。對比式(9)用in的表示方法,外聯(lián)接法可使用索引因而可定理22與普通聯(lián)接的結(jié)合律若聯(lián)接條件環(huán)境無關(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)接條件只與投影境無關(guān),則:列有關(guān)且環(huán)境無關(guān),則與投影(保留或消除重復)可交換操作VwP+(ⅧW)彐P=W(WP+W彐P)=V(W>P)順序:5.4外聯(lián)接差分(V>W)(z)=V(z)>W(!)由于加號兩邊的表達式都是左線性的,所以外聯(lián)接也是左(ⅴ>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,聯(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)境無關(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真時,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外聯(lián)接的結(jié)合律6二元集合運算三個表ⅤW、P的左外聯(lián)接有兩種:本文研究的二元集合運算有 union(并)、 except( oracle中用(1)W<>P式W和P都對Y聯(lián)接V是兩個外聯(lián)接合miu,)、mma(交)三種,雨而min又分為 unon a和anmn用的左分量,為并行外聯(lián)接。(2)V>W>P式W在對V的外聯(lián)接中是右分量而在另兩種,故共有四種集合運算。一外聯(lián)接中是左分量稱串行外聯(lián)接6.1保留重復集合并并行和串行的左外聯(lián)接在SQL中的語法為:union all是保留重復并,本文中用作未規(guī)范化的加運算V left join W on FI left join P on F2設V和W可加保留重復并的結(jié)果記作vUW把V和W的行不論相同與否都合并在一起。但僅作集合運算不做規(guī)范化操v left join W left join P on F2 on FI作,得到的是非規(guī)范的SQL表。由SQL表的加運算定義4知定理21串行組合外聯(lián)攥的結(jié)合律若F是VW間的環(huán)UAW規(guī)范化后即為v+W因此兩者相等:VU,W=V+W,V境無關(guān)條件,F2是WP間的環(huán)境無關(guān)條件且是非容空的(空值U,W的差分同和的差分上計算必是fae),則:d(vu, W)=dv+dw(V>WF11)>P|F2}=V>(W>P|F2)|F6.2消除重復集合并證明把等號兩邊各自用外聯(lián)接定義展開:沒有a的unin是無重復并。V和W無重復并是對vV>W)>P=(WW+V彐W)>P∪,W再作消除重復操作即[vUAW],表示為VUW。其實SQL=WW尸+(VW)P+WP+(VW丑P只要用下面的語句即可:(F2環(huán)境無關(guān))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環(huán)境無關(guān),V下面的定義把并推廣到負重數(shù)。丑(W>P)=V三W定義13保留符號消除重復并SQL表的無重復集合并兩者區(qū)別在于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重復并滿足結(jié)合律,即:F&F3。由此(VIUV2)UV3=VIU(V2U V3 )=VI UV2U V3vn(WnP).rep(0)=(∩W)∩P.rep(x0)證明由交換律,(vlUV2)UⅤ3=V3U(ⅥuV2),所以由此結(jié)合律得證。只要證明(v1UV)Uv3=ⅥuVU3,即[[Ⅵ+V2]+V3]交的結(jié)合律沒有正表限制。=[Ⅵ+v2+V3]。若用在x=V.cos的重數(shù)表示則為: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節(jié)輔助等式(7),取x=V.rep(x)+V2rep(x)的。故v3.rep(x)即得待證的等式。vld(ⅤnW)=dv∩W,vd(v-W)=dv-W有負重數(shù)時結(jié)合律不成立。如設Ⅵ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)總結(jié)上面的推導得下述定理63集合交與差定理26交與差的差分V和W都是無重復可加SQL這里只討論消除重復的集合交 intersect(n)和集合差ex表集合交V∩W與集合差V-W的差分分別可用式(29)、cep(-)。根據(jù)集合論,若VW無重復,成立等式(v∩W)+(30)計算。(V- W)=VV和W可重復時式(29)、(30)的dV和dW要替換成d[V]藉助于量詞定義一般表(重數(shù)可大于1或負)V和W的交和d啊]。和差如下定義144交與差SQL表V和W可加,分別稱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作為本文所述理論的一個應用,本節(jié)討論關(guān)系代數(shù)中定義為VW的交Ⅴ∩W和差=W。的關(guān)系除法,目標是導出計算關(guān)系商及其差分的SQL查詢語當Ⅴ和W正時,不論是否有重復,該定義與SQL的句。計算關(guān)系商的SQL查詢語句雖然在數(shù)據(jù)庫的教科書中可sect和 except計算結(jié)果一致以找到,但導出過程卻罕有記載。設ⅤW規(guī)范,x=V.cols,y=W.cols。由此可計箅集合交與二元關(guān)系A(chǔ)(x,y)除以一元關(guān)系B(y)的商是一個新一元差在(x0)的重數(shù):關(guān)系,記作MB,是A中與B全部y對應的x。如下面的數(shù)字例vnW rep(0)=[V]. rep(x0).sign/ W rep(r)所示例7關(guān)系除法的數(shù)字例V-W rep(x0)=[V]. rep(x0).(1-sign]Wrep(y))A(x, y) B S(x) SB因ⅤW規(guī)范故F=|.cols=W.cols&sign(v.rep)=sig1 I11(W.rep)是一對一的。但求和號不可取消因為可能有不存在122y的情況,這時求和結(jié)果為0。交的交換律是明顯的。下面的定理證明交滿足結(jié)合律。關(guān)系A(chǔ)(xy)和B(y)的商也可定義為是使S(x)B(y)sA定理25交的結(jié)合律表VWP規(guī)范可加則(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為空時關(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節(jié)的輔助公式(7),求和號內(nèi)的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內(nèi)部,即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*為集合差,得關(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同名率進一步用不存在量詞替換集合差(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語句:(*)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的相對誤差都在在允許范圍之內(nèi)。ng sum( rep)< >0方差D(S)=0.178D(S)2·A=0.351where(x,, b_y) not in從三維虛擬人體提取的領(lǐng)圍線,是基于eMTM的虛擬衣片的上界如圖8所示準確的領(lǐng)圍線能搭建起準確的服裝結(jié)構(gòu),并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且在虛擬服裝的數(shù)據(jù)處理與三維顯示上不會出現(xiàn)錯誤與失真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)圍線為服裝衣片的上界group by a. x, a, y having rep count(.))/d[b] End./4結(jié)論ng sum(rep)<>0)where(x) not in本文提出的方法能夠準確自動地從三維虛擬人體上提取領(lǐng)圖線。為服裝設計和制造做了必要的鋪墊,并且大大提高了select a,xx from a where not existseMTM系統(tǒng)的效率如表4所示。4對圖1虛擬人體的頸圍線提取計算結(jié)果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