ѧ
JOURNAL OF SOFTWARE
1999 6 10 Vol.10 No.6 1999



*
      μ 
ժҪǶάݿԶάΪĺĻ.һֶ֧άݿͶάĹĴӶΪݲֿ⼰ṩۻ.ͬʱ»һЩӦã֤ùеǿ.
ؼʡ,,άݿ,.
ͼšTP311

An Algebra for Online Analytical Processing Data Cube 
PEI Jian CHAI Wei ZHAO Chang TANG Shi-wei YANG Dong-qing
(National Laboratory on Machine Perception Beijing University Beijing 100871)
(Department of Computer Science and Technology Beijing University Beijing 100871)
Abstract Data cube is the central mechanism in multi-dimension database and online analytical processing (OLAP) based on multi-dimensional analysis. In this paper, an algebra for OLAP data cube is proposed, which supports multi-dimensional database and analysis. It can be the theoretical foundation of semantic specification of data warehousing and OLAP manipulations. Some applications of the new mathematical tool are presented as well to show the power of the contribution.
Key wordsData cube, algebra, multi-dimensional database, online analytical processing.
ݲֿ⼰ǽݿ⼼һоصȵ.ݲֿġɵġʷݵġȶ֧־ƶ̵ݼϣ1.߼Ͻݲֿһάݿ.(online analytical processing,OLAP)ԶάΪ̻ڹ;߹жݽж桢ǶȵķҪ2.(data cube)34ݲֿĺĸ֮һ.
ȻĿǰΪֹݲֿȱֵۻάģȱӦʽ.ݲֿĹܺͲͨԷʽķģͬĳ̺Աͬ費ͬĺ壬ݲֿ⼰Ӧ.
һֹĴ֧ݲֿеĶάݸģʽڴ֮ϵΪݲֿ⼰ṩۻ.ģ;ŵ㣺
. ΨһĻʵ;
. ܹĲ걸;
. ôıϵͬ.
ĸĸйҪʺ㣬йصӦ.ڵ1Уʽ˶άģ͡һЩʣصĹ.2ڸĻ֤ΪάģʽһģͣһЩҪ.3ڸĲ.4Ӧ.
1 ⱳйع
ݲֿĶάģʽУҪ߼ϲöάķʽ֯ʹ.ݷҪȷάģʽеһЩΪݶʵĹ۲ǶȣΪά(dimension)άݶ.ͬʱӳݶԵԳΪָ(measure).Ľṹ(data cube).ʵϣûʲôһоάָ꣬лֶǸݷĵǰҪеģԵĺʱ.άвνṹ磬ڿ԰-·--֯άҲʹûԵĹ(AOI)5ݵȷγɲνṹ.
öάģͣԽжۺ(roll-up)¿(drill-down)ת(pivoting)ֲ(slicing-dicing).ˣĹ̾ǸݷҪ󣬴ԭʼй壬ִйصĲٰѽظûĹ.
ʵУڶЧʵĿǣҪԤȼһЩάϵľۼʹڻشйزѯʱֱܹʹþۼݣҪԭʼݿʼ.ڻڴģݼԣԤȼؼۼܸƾҪ.ȻھnάԭʼϿܵľۼ2n.һľۼԴһľۼٶеһάоۼõ.һۼҲΪһڵ(cuboid).
ĿǰڶάģͺǷʽģͨʾеģˣ.ϵͳƺʵֹУҪһּġʽǱĵо.
Ϊֶ֧άģͺʽӦþ
. 򵥣ʹ;
. ܹĸֲ;
. ֧άĲεȸ;
. ֵ֧Ҳֹ֧Բ;
. ʵ޹.
ף3ݷʽĸΪSQLgroup byӾһ㻯˹ؼALLʾۼ.ף6ݸ˶άݿһʽģͣάĽṹĸӲȴûн.ֵָǣף6УΪûаĽڵĸϸ֣Դ˴ϵĸԣйӵȲҲŲ.ף4ʹ˺ף3һµĸоѡЩڵʵ廯(materialization)⣬һ̰㷨.
ȻĿǰ׾ûʽо弰й.ˣؼ⣬Чʽ.
2 Ҫ
2.1 Ԥ֪ʶ
Ϊ˷壬Ҫ漰䣬ԪأͺALL.СͶӦڿֵALLֱӦף3ĹؼALL.
2.1(). DD+=D{,ALL}ң<DƫϵǡD+,<СԪALLǡD+,<Ԫ.dD+<d iff d١ͣd<ALL iff dALL.
2.2(ۼ). aggr:2D1...DnD1...DmΪD1...Dn(D1...Dm)ľۼ,ҽһaggrassist:(D1...Dm)(D1...Dm)D1...Dm(Ϊۼ)ʹT2D1...DnT1Taggr(T)=aggrassist(aggr(T1),aggr(T-T1)).
2.2 
2.3(). һԪ,cube=(Dom,D,Mdom,M,f,aggr)У
(1) Dom=dom1...domnn>0Ϊάdomi(1in)
(2) D={d1,...,dn}Ϊάʶdi(1in)domi(1in)ıʶ
(3) Mdom=mdom1...mdommm>0Ϊָmdomi(1im)
(4) M={m1,...,mm}Ϊָʶmi(1in)mdomi(1im) ıʶ
(5) f:DomMdomDomMdomϵĲӳ䣬ΪĻ(cube base)
(6) aggrMdomϵľۼ.
(Dom,Mdom,aggr)Ϊcube(signature).
άֵָȷʱʹάıʶάƺάʹָıʶָƺָʱԼΪԪcube=(D,M,f,aggr).
ĶУ漰˱ʶĶӦ.ˣŻĴ򽻻.ӱϿͽĴӰĴ.֤ͽĴȫ弯ϵһȼ۹ϵ.УǽȫڻͽĴһȼ۹ϵγɵĵȼʺ.
2.4(ͬ弯). f:DomMdomDomMdomϵĲӳ䣬CUBEf={(Dom,D,Mdom,M,f,aggr)|(Dom,D,Mdom,M,f,aggr)}ΪΪfͬ弯.
Ȼ¶.
2.1. ͬڻͽĴȼΨһ.
ɶ2.1CUBEfɼΪDom,Mdom,f,*.
2.3 άģʽ
άģʽǶάݿݲֿ߼ģͣǽ֤Ϊάģʽʵֳڶάģʽϵݷ.ʽؿ̻˶άģʽԼϵĶάžҪ.
ڶάģʽʽ壬жֻȼ۵ķף79ݷֱ.ЩȻ죬䱾Ƶ.ˣǲף8,9ݵĶ.
2.5(άģʽ). һnάģʽһԪMDS(A,K,D,F)A={a1,...,am} (mn)ΪԼ;ÿһ(domain)KAΪ뼯;D={d1,...,dn}Ϊάʶ;F:D2AΪά㣺
(1) 1ijnijF(di)F(dj)=
(2) 
(3) 1inF(di)K٣
(4) 
F(d)(dD)ΪһάǣΪʵAΪMDSӦĹϵģʽ.
廻ͽƣڶάģʽҲάʶĻ.ͬأάʶӰάģʽĴ.ˣάʶһȼ۹ϵγɵĵȼй.
¶һάģʽΨһӦһļϣüеͬĻ.֮άģʽһݽṹӦ弯ϿΪ
ݽṹڸݽṹϿܽеĶάĴʵ.
2.2. CUBEf/͡MDS={MDS(A,K,D,F)}/ֱΪȫͬ弯ȫάģʽڻͽĵȼ۹ϵγɵ̼MDS(A,K,D,F)ʡMDS/妷(MDS(A,K,D,F)):Dom,Mdom,f,*CUBEf/,
(1) Dom=domain(F(d1))...domain(F(dn))domain(F(di))F(di)F(di)ԵĿϻ
(2) MDSУfact-K={t1,...,tl}Mdom=domain(t1)...domain(tl)domain(ti)ti
(3) f:DomMdomr=keyd1,...,keydn,t1,...,tlMDSʵеļ¼keydiF(di)룬dom1,...,domndomidomain(F(di))1indomi|KF(di)=keydif(dom1,...,domn)=t1,...,tl.
ǡMDSϵһӳ.
2.4 Ҫʡʵ廯
νʵ廯ָԤִĳЩ㣬洢ʹݷʱֱӿʹüõĽҪԭʼݵм.ڱУ۵ʵ廯ָάľۼ.
2.6(άۼ). cube=(Dom,Mdom,f,aggr)Dom=dom1...domnaggr:2MdomAGGAGGǾۼaggrֵfdomi(1in)ľۼӳ:
f:dom1...domi-1{ALL}domi+1...domnAGG,
(d1,...,di-1,di+1,...,dn)dom1...domi-1domi+1...domn
f((d1,...,di-1,ALL,di+1,...,dn))=aggr({m|didomi,f((d1,...,di-1,di,di+1,...,dn))=m}).
2.7(ʵ廯Ԫ). cube=(Dom,Mdom,f,aggr)¶cubeʵ廯ԪM(cube)
(1) fM(cube)
(2) gM(cube)dgһάgdľۼgM(cube).
M(cube)СϣеԪسΪʵ廯Ԫ(cuboid).
2.3. cubeʵ廯ԪȷΨһ.
2.4. cube=(Dom,Mdom,f,aggr)|Dom|=n|M(cube)|2n.
2.8. M(cube)϶¹ϵ:1f1gҽgfһάϵľۼ.Ϊ1ĴݱհΪM(cube)ϵľۼϵ.
2.5. M(cube)ϵľۼϵM(cube),һ.
2.5 Ҫʡ̬ͬ
Ϊоϵ㣬̬ͬĸ.̬ͬڿ̻ӦоҪ.
2.9(̬ͬ). cube1=(Dom1,Mdom1,f1,aggr1)cube2=(Dom2,Mdom2,f2,aggr2)aggr1:2Mdom1AGG1aggr2:2Mdom2AGG2ӳ:(Dom1Dom2)(Mdom1Mdom2)(AGG1AGG2)ʹ
(1) dDom1(f1(d))=f2((d))
(2) TDom1(aggr1({f1(t)|tT}))=aggr2({f2((t))|tT}),
cube1=(Dom1,Mdom1,f1,aggr1)ڦ̬ͬcube2=(Dom2,Mdom2,f2,aggr2)һ̬ͬ(ӳ)cube1cube2Ϊcube1cube2.ǵ䣬Ϊ̬ͬ;䣬Ϊ̬ͬ;˫䣬Ϊͬcube1cube2Ϊcube1cube2.
3 Ĳ
ڸܹ֧Ĵ.
3.1 ָάת
3.1. aggrD1...DnϵľۼĳDi1in(d1,...,di-1,di+1,...,dn)D1...Di-1Di+1...Dnd,dDiaggr((d1,...,di-1,d,di+1,...,dn))=aggr((d1,...,di-1,d,di+1,...,dn))aggrDi޹.
3.2(ָ-άת). cube=(D1...Dn,M1...Mm,f,aggr)aggrָMi(1im)޹أMiָ-άת:MD(cube,Mi)=(D1...DnMi,M1...Mi-1Mi+1...Mm,f,aggr)У(d,m)D1...DnMif(d)=(m1,...,mi-1,m,mi+1,...,mm)
(1) f((d,m))=(m1,...,mi-1,mi+1,...,mm)
(2) aggr({(m1,...,mi-1,mi+1,...,mm)})=aggr({(m1,...,mi-1,m,mi+1,...,mm)}).
3.3(ά-ָת). cube=(D1...Dn,M1...Mm,f,aggr)άDi(1in)ά-ָת:
DM(cube,Di)=(D1...Dn,M1...MmDi,f,aggr)

d=(d1,...,di-1,di,di+1,...,dn)D1...Dnf(d)=(f(d),di)

(m,d)M1...MmDi,dDiaggr({(m,d)})=aggr({m}).
ά-ָתΪDMת.
ά-ָתһάָȥͬʱɾά.ʱһάһָͬʵһָƣָ-άǲһ.ά-ָĸƷʽָάĺ.
ָ֤-άתά-ָת.
3.1. MD(cube,Mi)һ.
3.2. DM(cube,Di)һ.
3.3. cube=(D1...Dn,M1...Mm,f)op1,op2{MD,DM}d1,d2{D1,...,Dn,M1,...,Mm}d1d2op1(cube,d1)op2(cube,d2)жʱop2(op1(cube,d1),d2)=op1(op2(cube,d2),d1).
3.3漰ͬάʱָά֮ת԰ִУ.Ϊά任(pivot)ĲкͲṩ۱֤.
3.2 ָά˻
ۼָеĳ޹أڷвҪʹøʱȻֱȥԣָͨ˻ʵ.
3.4(ָ˻). cube=(D1...Dn,M1...Mm,f,aggr)aggrָMi(1im)޹أ¶Miָ˻Deg(cube,Mi)=(D1...Dn,M1...Mi-1Mi+1...Mm,f,aggr)dD1...Dnf(d)=(m1,...,mi-1,m,mi+1,...,mm)
(1) f(d)=(m1,...,mi-1,mi+1,...,mm)
(2) aggr({(m1,...,mi-1,mi+1,...,mm)})=aggr({(m1,...,mi-1,m,mi+1,...,mm)}).
3.4. Deg(cube,Mi)һ.
ά˻Ҫָ˻һЩΪ뱣ָ˻άĺ.
3.5(ھۼά˻). cube=(D1...Dn,M,f,aggr)aggr:MAGGάDi(1in)ھۼ˻£
Deg(cube,Di)=(D1...Di-1Di+1...Dn,AGG,f,aggrassist)

d=(d1,...,di-1,di+1,...,dn)D1...Di-1Di+1...Dn
f(d)=aggr({f((d1,...,di-1,di,di+1,...,dn))|diDi}).
3.5. Deg(cube,Di)һ.
3.6. cube=(D1...Dn,M1...Mm,f)
Deg(DM(cube,Di),Di)=cube.
3.3 ѡ 
ѡʹʹ߿ԸҪĻѡһӼӼΪγһµ.
3.6(ѡ). cube=(D,M,f,aggr)pDMϵν()ѡp(cube)=(D,M,f,aggr)dD,f(d)=f(d) iff p(d,f(d)).
3.7. p(cube)һ.
3.4 ͬļ
ֱϿġģʽˣͬģʽݼ()Խвȴͳϲ.
3.7(ļ). cube1=(D,M,f1,aggr)cube2=(D,M,f2,aggr)dDf1(d)f2(d)ж壬f1(d)=f2(d)ô
(1) cube1cube2=(D,M,u,aggr)dDu(d)=f1(d), if f1(d)жf2(d), if f1(d)޶f2(d)ж壻
(2) cube1cube2=(D,M,g,aggr)dDg(d)=f1(d), if f1(d)жf2(d)ж壻
(3) cube1-cube2=(D,M,h,aggr)dDg(d)=f1(d), if f1(d)жf2(d)޶.
3.8. cube1cube2,cube1cube2cube1-cube2.
3.5 Ļ
Ļƴγһģ.
3.8(Ļ). cube1=(D1,M1,f1,aggr1)cube2=(D2,M2,f2,aggr2)壬Ļcube1cube2=(D1D2,M1M2,f,aggr)(d1,d2)D1D2f((d1,d2))=(f1(d1),f2(d2))ҽf1(d)f2(d)ж壻{(m1,m2)}2M1M2aggr({(m1,m2)})=(aggr1({m1}),aggr2({m2})).
3.9. cube1cube2.
һҪʹһҪӳһ.
3.9(νʵ). cube1=(D1D,M1M,f1,aggr1)cube2=(DD2,MM2,f2,aggr2)D1DD2M1MM2ϵνʣνʦȵǣ
(1) (d1,d,d2)D1DD2f((d1,d,d2))=(f1((d1,d)),f2((d,d2))|M2)ҽf1((d1,d))f2((d,d2))ж壬f1((d1,d))|M=f2((d,d2))|MҦ(d1,d,d2,f1((d1,d)),f2((d,d2))|M2)
(2) {(m1,m,m2)}2M1MM2aggr({(m1,m,m2)})=(aggr1({(m1,m)}),aggr2({(m,m2)}).
3.10. .
3.11. .
3.9Ļӵ.
4 Ӧ
4.1 ı
1۵С.Ȼ϶㣬ϽڶĲѾĲά任(pivot),roll-up,drill-downslice and dice.
1 

ڵͬ
ָ-άת
ά-ָת
ָ˻
ھۼά˻
ѡ񡡡


2ʽذϵ˱Ƚ.ȻһϵΪԾάָΪ{1}.ǣϵͶʹʾ. 
2 ϵȽϣ

ϵ
ͳ㲢ϻȲ
ϵѡӡͶӰָάת˻ѡ񡢻ӵ


һ棬ʹùϵΪݽṹ.֤ùϵʵ.Ҫ.
4.1. ϵıͬ.
֤:ȣһn-ԪϵΪԼΪۼԹһ.ǹϵСÿ.֤Щĸʾ.ˣıڹϵ.
Σһcube=(D,M,f,aggr)ʵΪһϵDMкf.֤ÿ㶼ʵΪϵĸ.ˣıǿڹϵ.
㣬֤. 
4.2 Ӧ
ֶ֧άһǿѧߣӦԺϵͳķơݲֿĹ淶˵ȷ.⣬ԴϸطоάھеһЩ.
ڽԵĹɷ˵ļӦ.
ԵĹ(AOI)5,10ھеһЧĸ㷨.ͨάݽзøλݷֲʵи.ԵĹ㷨ԱΪеһݹ麯AOIֻҪֵ㣬ϵݹִ.
ף11ݸ»ԵĹɷ㷨.
begin
While ݼеĿֵ do begin
 ѡĳA
 {Aִһ㻯(generalization)}
 if AĲθṹдһ(һ)ļ
 then øһֵAֵ
 鲢ͬУ
end; {while}
end.
ȻѡAʱ಻ͬķˣпܵ¹ɵĽһ.ͬʱɵĹǷһֹЩҪʽԽ.
4.1. 伯{CiCi+1|1il,lN}Ϊ{C1,...,Cl}ϵһ޸νṹҽ{CiCi+1|1il}û˫|Cl|=1.C1ΪʼClΪս.ʱȻ|Ci+1|<|Ci|.
4.2. C|C|ޣشCΪʼĸνṹ.
ȻʵӦУݼֵ޵.ˣһڻԹԽйɵ޸.֤¶.
4.3. AOI㷨ֹ.
4.2. Ҫcube0=(D,M,f,aggr)ʵʩɣΪÿάϱʾ޸εָһΨһľۼcubecubeһάϵһɶõΪcube1cobe䣬Ϊһɹϵ.CUBEСϣ
(1) cube0CUBE
(2) cubeCUBE,{cube|cube1cube}CUBE.
ΪCUBE1ĴݱհΪɹϵ.
4.4. (CUBE,)һ.
㷨AOIòͬѡȡԶֵʱͣڲͬĽ.ˣɽͬ.ǣ4.4ͬĹɽͬһеĲͬԪأˣChurch-RoserʣԺ.Ա֤˻ԵĹɷϵһ.
5  
һֶ֧άʽߡҪʡйӦ.оҪۼֵ.
ĿǰΪ۹ߣоȡһЩ׶ԵĽ.ǵҪ¼棺
. ԸģΪƺʵ֧Ķάݿԣ첻ͬĵײƶʵֵӰ죻
. Ϊۻоļۣչִ֧ģĶ༶ۺϺݼھ
. оݲֿۣ̽άģʽİԶƷ.
*оõӾϢصʵҿſ.
߼顡ὡ1969ʿҪоΪݲֿ,,ھ,Ϣϵͳɼ.
⣬Ů1972˶ʿҪоΪݿ⣬ݲֿ⣬ھ.
ԳŮ1973˶ʿҪоΪݿ⼼.
μ1939ڣʿʦҪоΪݿ뼼ռϢͼ.
࣬Ů1945ڣʿʦҪоΪݿ뼼ռϢͼ.
ͨѶϵ:ὡ100871ѧѧ뼼ϵݿо
ߵλӾϢصʵҡ100871ѧѧ뼼ϵ100871
ο
1 Inmon W H. Building the Data Warehouse. 2nd ed., New York: John Wiley and Sons, Inc., 1996
2 Codd E F, Codd S B, Salley C T. Beyond decision support. Computer World, 1993,27(30):8789
3 Gray J, Chaudhuri S, Bosworth A et al. Data cube: a relational aggregation operator generalizing group-by, cross-tab, and sub-totals. Data Mining and Knowledge Discovery, 1997,1(1):2953
4 Harinarayan V, Rajaraman A, Ullman J D. Implementing data cube efficiently. In: Jagadish H V, Mumick Inderpal Singh eds. Proceedings of ACM SIGMOD International Conference on Management of Data. New York: ACM Press, 1996. 205216
5 Han J, Fu Y. Exploration of the power of attribute-oriented induction in data mining. In: Fayyad U M et al eds. Advances in Knowledge Discover and Data Mining. Cambridge: AAAI/MIT Press, 1996. 399421
6 Agrawal R, Gupta A, Sarawagi S. Modeling multidimensional databases. In: Gray Alex, Larson Per-ke eds. Proceedings of the 13th International Conference on Data Engineering. Birmingham: IEEE Computer Society Press, 1997
7 Gjyssens M, Lakshmanam L V S. A foundation for multi-dimensional databases. In: Proceedings of the 23rd International Conference on Very Large Databases. San Fransisco: Morgan Kaufmann Publishers, Inc., 1997. 106115
8 Pei J, Tang S, Yang D et al. Encapsulate multi-dimension objects in a data warehouse environment. In: Chen J et al eds. Proceedings of the 27th International Conference on Technology of Object Oriented Languages and Systems. IEEE Computer Science Press, 1998. 362371
9 Pei J, Tang S, Yang D et al. An algorithm for star schema construction based on query example. In: Rabi et al eds. Proceedings of the International Conference on Information Technology (ICIT'98). New York: MiGrall-Hill Press, Inc., 1998
10 Han J, Cai Y, Cercone N. Data-driven discovery of quantitative rules in relational databases. IEEE Transactions on Knowledge and Data Engineering, 1993,(5):2940
11 Heinonen O, Mannila H. Attribute-oriented induction and conceptual clustering. Series of Publications C, No.C-1996-2. Department of Computer Science, University of Helsinki, 1996
1998-12-09յԭ,1999-02-08յ޸ĸ
