
COMPUTER ENGINEERING
1999 25 10 Vol.25 No.10 1999



ݿеʵּ
ʤǱ
ժҪȽҪ3Ƕϵʵּ㷨ͱȽǵȱ㣬Ȼ󹤳ݿϵͳOSCARеʵּ
ؼʣ󹤳ݿϵͳѯŻӶ
Index Implementation Techniques in the Object-oriented Databases
Cheng Sheng Chen Qian Dong Jinxiang
1.CAD/CAM Center of China Aerospace Corporation, Beijing 100037;2.Artificial Intelligence Institute of Zhejiang University,Hangzhou 310027)
AbstractThis paper firstly introduces the implemetation technique and operation algorithms of three main indexsanalysing and comparing them form the dimensions of feasibility and performance.Then the index implementation techniques in OSCAR,which is an object-oriented engineering database mangement system,were presented
Key wordsObject-oriented engineering database mangement system;Query optimization;Complex object
ۼϵ¿ɷΪ3ࣺǶ (Nested Index) · (Path Index) (Multi-index)ϸ3ʵַͲ㷨3ʵַͲϽ˷ͱȽϡġĹݿϵͳOSCARе·ʵּ 
1  ۼϵ3
1.1   
 1 H һۼ C1 .C2  CnHϵһ·Ϊ P=C1.A1.A2An(n>1)
 CiHеһ࣬AiCiһԣ
 CiCi-1һAi-1ֵ(1<in)
 2· P=C1.A1.A2An,PϵһʵΪn+1O1.O2On+1
 O1PC1һʵ ,
 OiOi-1Եһֵ(1<in)
 3·P=C1.A1.A2AnPһʵΪO1.O2Ojj<n+1
 O1PϵһCkһʵ(k=n-j+2)
 OiǶOi-1Ai-1һֵ(1<ij)
Ϊ˵⼸µͼ1еĶݿģʽƬκͼ2еһЩʵΪ˵3

ͼ1  һݿģʽ

ͼ2  һЩʵ
1.2  Ƕ 
1.2.1  
·P=C1.A1.A2AnPϵǶΪ(O,S)ļϣ
 S={O' ʹôPʵO1.O2On+1O'=O1O=On+1},
.(O,S)еOؼ֡
ǽ·P= .ӵ..ƱֵϵǶ
.(200{A})
.(500{A})
.(3000{ABB})
Ϊµн·ʵеһһֱΪʼͽβ
1.2.2 ǶĲ㷨
һ·P=C1.A1.A2AnԼһڸ·ϵǶ
(1) 㷨C1ǶAnϵνʵļҪǶĲһĲͬģͨؼֱҵӦʼıʶ(OID)
(2) 㷨Oi(1in)·CiһʵOiAiֵOi+1AiֵҪO'i+1Ƕµ㷨
1)Oi+1ҳAnֵ뼯S.oldһOi+1ʼAn̡ͨS.oldֻһԪأ·ĳAiǶֵģ
2)O'i+1ҳAnֵ뼯S.newS.new=S.old˵ظ¡ת3)
3)ҳֱӻOi+1CiʵһOi+1ʼķ̣ i=1R={Oi}.
4)²£
S.newS.old,=S.old-S.newڡеÿؼkk¼ɾȥRеĵOIDS.oldS.new=S.new-S.oldڡеÿؼkеOID뵽k¼ȥ۷.1=S.old-S.newҡ.2=S.new-S.oldڡ.1 еÿؼk¼ɾȥRеOIDڡ.2еÿؼkRеOID뵽¼ȥ
1.2.3  ʵַ
Ƕṩ·ʼͽβֱӹǶB+ṹϣ㷨ʵ֡B+ʵ֣ҪB+ֱʵؼֶӦ·ϵĶʶ¼еЩʶΪؼ֣ÿʶһиöֱ
ע⵽άǶʱҪ·зҪķõĴڣʵʵĶݿģʽ˫ùϵࡣûݿģʽвڷãһݿϵͳеĵùϵΪ˫ĶùϵϵͳӵùϵûǲɼģýʹϵͳܹЧڶռַʹϵͳֹϵάܶĿϵͳܵ½пǵòʧǶʵֽṹѾܸӣάҲȽѣݿģʽв㹻˫ùϵһ㲻˽Ƕ
1.3  
1.3.1 
·P=C1.A1.A2AnΪ
1in{I1,I2,,Ii}
Ii(1in)Ƕ·ϵĵ
Ci.Ai ϵĵָ(O,S)ԵļϣOAiֵһֵS={O'|O'Ai=O}
ע⣬ڵУؼֿǻ(ַͣ)ҲǶʶ
·P=.ӵ..ƱֵϵĶ£
(1)·.ӵĵУ(γA{B})(γB{A})(γC{A})(γD{B})(γE{A})
(2)·ӵ.̵ĵУ(˾A{γC})(˾B{γAγDγE})(˾C{γBγF})
3)·.ƱֵĵУ
(200{˾A})(3000{˾B})(500{˾C})
1.3.2Ҫ㷨
·P=C1.A1.A2AnCi(1in)ǶAnνʼҪ(n-i+1)ҪInȻIn-1ֱIiһ·ķḶ̵́ķҪõĴڣΪͿҵ·еǰһ󡣿ԿöֱӸݹؼҵӦĶ󣬶Ҫ·ϵÿԶļһ㲻Ƕ(·ȴ2ʱ)
ԶάǶÿάԵά㷨ǱȽϼ򵥵ġ
1.3.3ʵַ 
öB+ֱʵָȻĽṹӣάҲȽϼ򵥣ܲ(·ȴ2ʱ)ѯе·ʽĳһ㶼 2ʱʵֶǺܻ㡣
1.4·
1.4.1
·P=C1.A1.A2An·Ϊ(O,S)Եļϣ
 OAnֵһֵ
 S={n+1-j(Pi)|Pi=Oi.Oi+1.On+1һ·ȫʵOn+1=O}
·ڵÿΪҪβ·ʵ佨ϵ
ͼ1,ͼ2·P=.ӵ..Ʊֵϵ·£
 (200,{A.γC.˾A})
 (500,{γE.˾BB.γD.˾BB.γA.˾BA.γE.˾B })
 (3000,{ γ F. ˾ C  A. γ B. ˾ C})
1.4.2Ҫ㷨
²㷨УҳΪλ֯ģÿҳɸ¼ɣÿ¼ɸ·ʵɣ·ʵԳȵ·ʽȵʽ洢
һ·P=C1.A1.A2AnԼPϵ·
(1)㷨Ci1inAnϵǶνʵļ㣬ֻҪһβңֻҪҵؼص·ʵiԪؾҪҵCiʵOID·ĲһҪǶĲ漰ҳΪ·¼˱ǶӦ¼Ϣ
(2)㷨 ·CiһʵOi1inAiֵOi+1 O'i+1ȡ㷨£
ٸOi+1ҳӦAnֵ뼯S.oldһS.oldֻһԪأ·ϵĳЩǶֵģ
ҳO'i+1AnĲʵ뼯 SP.newO'i+1ʼҵAnֵS.new
۶S.oldеÿؼk, ҳ¼ڼ¼еÿ·ʵP ,i ԪΪOni+1ԪΪOi+1ִ²裺
PĴӵ1i-1ĲʵʱT
PӼ¼ɾ
ɵiԪΪOii+1ԪΪO'i+1·ʵʵΪpnewpnewΪTһԪأOiO'i+1SP.newһԪصĴӡpnewΪn1*n2n1n2ֱΪT SP.newԪصĸ
ݶS.newеÿؼkҵӦʱ¼pnew뵽¼ȥ
㷨Կ·ҪǶǱģ·ǶиõĿԡ
1.4.3ʵַ
·һB+ʵ֣Ծʵ˵·Ϊ㡣[3]еĴģͷ·ȴ1ʱ·ļܲõģǶļãļά˵ţ·֮Ƕ·ȵ1ʱ3˻Ϊ
ܡάۡʵּӶȵۺȨ⣬OSCARв· B+ЧʱȽϸ(һͿҵ¼)Ŀǰ󲿷ݿϵͳʵҪB+(H)OSCARҲҪB+ʵ
2OSCAR·ʵַ 
󹤳ݿϵͳOSCAR㽭ѧ˹й칤ҵܹ˾CAD/CAM ĺƵġCAD/CAPP/CAMɻµݿ֧ƷΪϵͳĲѯOSCARв˶оΪ֧ǶνŻ·Ϊʵڲ¶ĲOSCAR㷨вĲƲԡĲһӵ⣬ĲԸ̽֡
2.1¼ṹ
ǰOSCARе·B+ʵ֡B+ĽҳΪλ֯ڷҶÿռһҳ棻Ҷռһһϵҳ棬ҳȡڲҳ¼Լÿ¼е·ʵĿ
B+ĽҳСԷҳ¼ĴСΪʵָЧI/Oҳһȡ̿СOSCARУҳΪ4kB
µУµķűʾӦĲ
RLʾ¼ȣKLʾؼֳKVʾؼֳINʾ·ʵINSTiʾ·ʵiPNEXTʾָһָ룻DIRʾ¼·ʵĵַĿ¼
Ҷе¼ҳǸݹؼֵСеģһҶļ¼ṹģ

Ҷе¼
(1)¼ȲһҳĴСʱ¼֯ģ

·ʵʽţеԪΪ·˳ŵģ·ʵеĶOIDĳȶΪ·ʽĳȣʼʱʼΪա·ʵȫ·ʵһԪΪա 
(2)¼ȳһҳĴСʱһ¼·ʵҪ洢ڶҳϣʱҪڼ¼ͷһĿ¼¼ÿ·ʵĵַ·ʵĵַǶԪ(ҳţҳƫ)¼ṹΪʽ(ADDRiʾINSTiĵַ)

3 
ĽĿǰݿнڸӶϵ3ͱȽǵʵַҪ㷨OSCAR·ʵַĿǰ⼸δϵͳʵǵıOSCARʵֵ·ʵֵļѶȲĲҲȽ⡣
ĿȻѧ
߼飺ʤ1976УоҪݿѯо
ߵλʤǱй칤ҵܹ˾CAD/CAMģ100037
飨㽭ѧ˹310027
ο
1 Bertino E,Catania B,Chiesa L. Definition and Analysis of Index Organization for Object-oriented Database Systems.Technical Report, University of Milano, 1996:162-196
2 Bertino E,Foscoli P.Index Organizations for Object-oriented Database Systems.IEEE Trans.on Knowledge and Data Engineering,1995,7(2):193-209
3 Bertino E,Kim W.Indexing Techniques for Queries on Nested Objects. IEEE Trans. on Knowledge and Data Engineering,1989,1(2):196-214
ոڣ1999-01-04
