ѧ
JOURNAL OF SOFTWARE
1999 1 No.1 1999



Լϵӷֽ*
־¡ʩ
ժҪԼݿеӷֽо.ԼݿһЩ,Լϵжͷĸ,֤˱ͶǽģʽӷֽĳҪ.̽˱Ա任±Էֽ.
ؼʡԼݿ,ӷֽ,,,.
ͼšTP311
Lossless Join Decomposition in Dense Linear Order Constraint Databases
FAN Zhi-xin SHI Bo-le
AbstractIn this paper, the data dependencies and lossless join decomposition in dense linear order constraint databases are studied. Several concepts of the dense linear order constraint databases are introduced. The concept of the multi-region existence dependencies is defined and studied. It is proved that the lossless join decomposition of constraint relational scheme preserves if and only if they satisfies variable independence and multi-region existence dependencies. Another dependencypartitioned multi-region existence dependencies is given. The issue of variable set under linear transformation is also proposed.
Key wordsDense linear order constraint database, lossless join decomposition, multi-region existence dependencies, variable independence, partitioned multi-region existence dependencies.
ԼݿKanellakis,KuperRevesz1990.1ۺ˹ϵݿ⡢Լ߼ơռݿ⡢ϵͳȶоɹ.˼ǽԼʽΪ,ΪģʽԼݲѯϵһ±ṩһЧ.,ѹϵݿеÿԪ鿴һȴԼȡʽ,,ϵR(A,B)еԪ(a,b)((A=a)(B=b));ڿռݿ,ƽڲΪ((a1xa2)(b1yb2)).Լݿģֶ֧Կռ䡢ʱıͲ,Ҳֶ֧ԲȫϢĴ.24
Ŀǰ,ԼݿеԼо϶27,Լ෽ҪڲѯĿɱԣ6,8,ģʽƵо.ף5ԼӷֽĳҪ淶ʾĸֿܹӷֽ,ֻһ,ûиԼģʽӷֽӦ߱;ף9ݸԼеĺ,ͱΪӵһ,ڸн,ӷֽ˵ǱҪ.
˶ĸ,Chomickiı2,õԼ±ӷֽĳҪ,Ա任Լת,˷ȸ.1ڽԼݿһЩ;2˶ȸ,óģʽӷֽĳҪ;3̽Ա任ԼһЩ.
1 ԼݿĻ
Kanellakis˵Ĺ۵1,3,4,Լϵʵһ߼ʽʾ.,ȸԼһЩ.
1.1. ԼCLOָԼ,xiΪʵ,aicΪʵ,ȡ{,,=,,,}.
Լһ߼ʽһȡʽ,ÿȡԼɵĺȡʽ.cx=,cxcȼ((cxc)(cx=c)),cxcȼ
((cxc)(cxc),cxcȼ((cx=c)(cxc)),((cxc1)(cxc2))ȼc1cxc2,ʹÿȡʽֻc1cxc2cx=cʽcxc1cxc2,ֻ֮һĺȡʽ,c1=-޺c2=+ޣ.Ǽٶõķʽвȡͺȡ.
1.2. X={x1,...,xn}ϵnԪԼԪһԼȡʽף,Լ.
1.3. X={x1,...,xn}ϵnԪԼϵRXԼԪļ,Ӧ߼ʽΪR=.DΪʵ,unr(R)={(x1,...,xn)(x1,...,xn)DnʹæR(x1,...,xn)Ϊ}.unr(R)ȡף1еġunrestricted relation of R.
1.4. RSǱXnԪԼϵ,unr(R)=unr(S),RSȼ.
1.5. RǶڱXϵԼϵ,R(X)RԼϵģʽ,RR(X)һʵ.
1.6. Լϵݿ޸Լϵɵļ.
һnԪԼԪʾnάռϵһ͹.10г޵,͹Euclidռон.ԶڴԼѯ.5,7ҪõĲ.
1.7. RǱXϵnԪԼϵ,YX,Y=m.,RYϵͶӰproj(R,Y)YϵһmԪԼϵ,unr(proj(R,Y))={sYݣsunr(R)}.
1.8. RǱXϵnԪԼϵ,SǱYϵmԪԼϵ,DΪʵ,XY=U,XY=p.,RSȻnj(R,S)Uϵ(n+m-p)ԪԼϵ,unr(nj(R,S))={uuDn+m-p,uXݡunr(R)uYݡunr(S)}.
2 ӷֽ
ԼݿҲ,ǵĴڵಢɲ쳣,õģʽԲֵرЩ쳣.
2.1. R(X)Լϵģʽ,R(X)ϵDEPһӳ,䶨R(X)ʵļ,ֵΪ.
2.2. X,Y,ZǱ,R(X),R1(Y),R2(Z)Լϵģʽ.Y,ZXYZ=X,ơR1(Y),R2(Z)R(X)һֽ.ǵֽ,ͨY-Z٦,Z-Y٦.
2.3. R(X)Լϵģʽ,DEPR(X)ϵ,R1(Y),R2(Z)R(X)һֽ,RR(X)һʵ,R1=proj(R,Y)R2=proj(R,Z).unr(nj(R1,R2))=unr(R),R(X)ķֽ⡴R1(Y),R2(Z)ӵ.
2.1. R(X)Լϵģʽ,R1(Y),R2(Z)R(X)һֽ,RR(X)һʵ,unr(R)unr(nj(proj(R,Y),proj(R,Z))).ر,RһԼԪt,Ҳunr(t)unr(nj(proj(t,Y),proj(t,Z))).
2.1:R{w,x,y,z}ϵԼϵ,
t1:0w6-1x41y-3z2,
t2:w=82x60y-3z5,
t3:w=87x80y-3z5
ɷֽ
R1(w,x): R2(w,y,z):
t11:0w6-1x4, t21: 0w61y-3z2,
t12:w=82x6, t22: w=80y-3z5.
t13:w=87x8,
2.4. RXϵԼϵ,Y,ZX,tRеԼԪ.
unr(proj(t,YZ))=unr(nj(proj(t,Y),proj(t,Z))), 
YZtУ壩.,YZt.
2.5. RԼϵ.Rȼ۵һԼϵR,YZRÿԼԪжǱ,YZRб.,YZR.
2.6. R(X)Լϵģʽ,Y,ZX.YZR(X)һʵRжǱ,YZR(X)б.
ԼϵRеÿԪ鿴ֻһԪĹϵʱ,Ա֤ЩӦĹϵģʽֽⶼ,һR˵,ܱ֤һܹӷֽ.
2.2:RX={w,x,y}ϵԼϵ,
t1:0w20x12y3,
t2:0w20x13y5,
t3:0w22x32y3.
Ȼ,{w,x}{w,y}Rб,R{w,x,y}ϵķֽ⡴{w,x},{w,y}.R{x,y}ϵͶӰһڲ.ٶԪ
t4:0w22x33y5,
R(X)ķֽ⡴{w,x},{w,y}.
Ϊ,ĸ.
2.7. R(X)Լϵģʽ,Y,ZX,YZ=X,YZ=W.R(X)һʵR,
㡡unr(nj(proj(t,Y),proj(t,Z)))=unr(nj(proj(R,Y),proj(R,Z))),
R(X)MRED(multi-region existence dependencies):WYZW(Y-W)(Z-W).Z=W,ƸMREDƽ.
ע,ϵݿĶֵ:ֵABCָͬAֵ˵,BͶӰCͶӰȻBCͶӰĵ;ABCָAͬ,BͶӰCͶӰȻBCͶӰĵ.в:ڶֵ,BCͶӰȻӿȫָBC;ڶ,BCͶӰȻӲһָܻBC.
2.3:R{w,u,v}ϵԼϵ,
t1:2w30u12v31v-u2,
t2:2w35.5u+v6.54.5v-u5.5,
t3:2w32u32v3-1v-u0,
t4:2w32u35v6.
Ȼ,Rwuv,unr(nj(proj(t,wu),proj(t,wv)))еĵ㲢ǶR,(2.7,0.4,2.5)ͲR.
2.1. R(X)Լϵģʽ,Y,ZX,YZ=X,YZ=W,RR(X)һʵ,ʽ:
unr(nj(proj(t,Y),proj(t,Z)))unr(nj(proj(R,Y),proj(R,Z))).
2.2. R(X)Լϵģʽ,RR(X)һʵ,н۳:
unr(R)=unr()=unr(t).
֤:unrĶ֪,unr(R)=unr().,һaunr(R),a,ӶaRĳtunr(t),,unr(R)unr(t).unr(R)Ķ֪,һtbunr(t),bunr(R),,unr(t)unr(R).,unr(R)=unr(t).۳.
2.2. R(X)Լϵģʽ,Y,ZX,YZ=X,YZ=W,YW,ZW.R(X)һֽ⡴R1(Y),R2(Z),ҽYZR(X)бWYZ.
֤:RR(X)һʵ.
֤.YZR(X)б2.2,֪:
unr(R)=unr(proj(t,X))=unr(nj(proj(t,Y),proj(t,Z))), 
YZR(X)WYZ,֪:
unr(nj(proj(t,Y),proj(t,Z)))=unr(nj(proj(R,Y),proj(R,Z))), 
,unr(R)=unr(nj(proj(R,Y),proj(R,Z))).Ӷ,ֽ⡴R1(Y),R2(Z).
֤Ҫ.ݶ2.1,unr(t)unr(nj(proj(t,Y),proj(R,Z))),ǵunr(R)=unr(t)unr(nj(proj(t,Y),proj(t,Z))).2.1,unr(nj(proj(R,Y),proj(t,Z)))unr(nj(proj(R,Y),proj(R,Z))),Ϊunr(nj(proj(t,Y),proj(t,Z)))=unr(nj(proj(t,Y),proj(t,Z))),unr(R)unr(nj(proj(t,Y),proj(t,Z)))unr(nj(proj(R,Y),proj(R,Z))).ɼR(X)ķֽ⡴R1(Y),R2(Z),unr(R)=unr(nj(proj(R,Y),proj(R,Z))).,
unr(R)=unr(nj(proj(t,Y),proj(t,Z))),(1)

unr(nj(proj(t,Y),proj(t,Z)))=unr(nj(proj(R,Y),proj(R,Z)))(2) 
.ʽ(2),R(X)WYZ.RеÿԼԪtΪnj(proj(t,Y),proj(t,Z)),ʽ(1)֪,unr(nj(proj(t,Y),proj(t,Z)))unr(R),Ӷ仯ԼϵRRȼ,ÿһԼԪunr(proj(t,YZ))=unr(nj(proj(t,Y),proj(t,Z))).,YZRб.R֪,YZR(X)б.
,۳.
ͶԼϵе,Ǳ֤ģʽӷֽ.ǻԶ,һҪ.
2.8. R(X)Լϵģʽ,Y,ZX,YZ=X,YZ=W.R(X)һʵR,һȼԼϵR,ʹRϴһ{G1,...,Gp},1i,jp,ij,:
(1) unr(nj(proj(t,Y),proj(t,Z)))=unr(nj(proj(Gi,Y),proj(Gi,Z)));
(2) unr(proj(Gi,Y))unr(proj(Gj,Y))=;
(3) unr(proj(Gi,Z))unr(proj(Gj,Z))=,
R(X)PMRED(partitioned multi-region existence dependencies):WYZW(Y-W)(Z-W).
2.3. ԼϵģʽR(X)ϵĶǷ.
ɼ,Ƿһʽ.
3 ԼԱ任
һ.
3.1:R{x,y,z}ϵԼϵ,
t1:1x33y+z51y-z3. 
Ȼ,{x,y}{x,z}Ǳ.y=y+z,z=y-z,{x,y}{x,z}ȴǱ.
3.1. X={x1,...,xn},X={x1,...,xn},XеÿXб,xi=aikΪʵ,1in.þʾ.
 
Y=AnnY.Ann0,x1,...,xn޹ص;, x1,...,xnص.
3.1. X={x1,...,xn},X={x1,...,xn},ԼϵģʽR(X),Y,Y,Annͬ3.1.ڣAnn0,ʹY=AnnY,RXXһһӦ.
֤:ɣAnn0֪A-1nn,ӶY=A-1nnY.֪,RXϵÿһXһӦ,RXϵÿһҲXһӦ.,RXXһһӦ.
3.2:3.1,ȡ
 
Ӷõϵ{x,y,z}µR,
t1:1x䣼33y䣼51z䣼3. 
{x,y,z}Ͷxyz,ʴֽ⡴{x,y},{x,z}.Rϵ{x,y}ϵͶӰһƽı.
,ԸıX,ϣܹҵһAnnAnn0,ͨ任ʹRڻõ±XXһһӦ,ҾĳЩõ.,12иĶͶXȻ.RڱXϲͶ,XһԱ任,ʹRڱ任ıXͶ,ôҲԽӵķֽ.
4 
оԼݿйϵģʽӷֽ.ͨ,֤ԼϵģʽӷֽĳҪǱͶ.Ǹ˷ĶԼĹϵ,̽˱Ա任±ֵȼ۵,ΪĳЩ͵Լϵṩڱ任±½Էֽ;.оԼϵеδĹ.
л лʿƽʿṩ,лʿͳʿ۲˱.
оõȻѧ.
߽ܣ־,1969,ʿ,ҪоΪݿ,֪ʶ.
ʩ,1935,,ʿʦ,ҪоΪݿ,֪ʶ.
ͨѶϵ:־£Ϻ 200433,ѧѧϵ
ߵλ־¡ʩ֡ѧѧϵ Ϻ 200433
E-mail: zxfan@ms.fudan.sh.cn
ο
1Kanellakis P C,Kuper G, Revesz P. Constraint query languages. In: Proceedings of 9th ACM Symposium on Principles of Database Systems. 1990. 299313
2Chomicki J, Goldin D Q, Kuper G M. Variable independence and aggregation closure. In: Proceedings of 15th ACM Symposium on Principles of Database Systems. 1996. 4048
3Grumbach S, Su Jian-wen. Finitely representable databases. In: Proceedings of 13th ACM Symposium on Principles of Database Systems. 1994. 289300
4Kanellakis P C. Constraint programming and database languages: a tutorial. In: Proceedings of ACM 14th Symposium on Principles of Database Systems. 1995. 4653
5Kanellakis P C, Goldin D Q. Constraint programming and database query languages. Lecture Notes on Computer Science, Springer-Verlag, 1994,789:96120
6Grumbach S, Su Jian-wen. Dense-order constraint databases. In: Proceedings of 14th ACM Symposium on Principles of Database Systems. 1995. 6677
7Goldin D Q, Kanellakis P C. Constraint query algebras. Constraints Journal, 1996,1(1):2432
8Paredaens J, den Bussche J V, Gucht D V. First-order queries on finite structures over the reals. In: Proceedings of 10th IEEE Symposium on Logic in Computer Science. 1995. 7987
9Wang Yu-jun, Shi Bo-le, Qu Yun-yao. Decomposition and lossless Join in constraint database. Lecture Notes on Computer Science, Springer-Verlag, 1997,1191:8091
10Preparata F P, Shamos M I. Computational Geometryan Introduction. David Gries ed. New York: Springer-Verlag, 1985
1997-11-11յԭ,1998-02-25յ޸ĸ 
