о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999ꡡ3610ڡVol.36No.101999



ԼݿеĶ̬ṹ
ͮʩ
ժҪŶԼݿʵûо.Meta_ĻDM_Ӧ㷨˴洢ΪO(n)ѯI/OʱΪO(logn+t/B)ܣڶ̬ͨơ޸ͺȲԣʹɾʱΪO(logn)ﵽB_ˮƽԼݿݵĴ洢ͷ.
ؼʡԼݿ⣬ṹMeta_
ͼšTP311.13
DYNAMIC INTERVAL INDEX IN CONSTRAINT DATABASE
WANG Wei, WANG Yu-Jun, WANG Yi-Tong, and SHI Bo-Le
(Department of Computer Science, Fudan University Shanghai 200433)
AbstractThe technique of dynamic interval index is very important in the practice of constraint database. Based on the structure of Meta_tree, DM_tree is given. Its storage is O(n) and query I/O time is O(logn+t/B). To reduce the complex of insert and delete operation, methods of unfixed_constraint and late_update are applied. The complex of the insert and delete I/O time are all O(logn). This result is equal to that of B_tree. It can be used in the storage and query in constraint database.
Key wordsconstraint databaseinterval index structureMetatree
1
ԼݿоǴ90ʼģ1ݣѯԡϵͳʵֵоǽݿⷽоȵ.Լݿѧʽ߼ʽ͹еݣݣԲȷݡʱݺͿռҲкǿӶڿռݿ⡢ʱݿ⼰ݿӦйӦǰ.
ԼݿĻ˼ǽϵݿеkԵԪΪkάԪ飬kάԪΪʵkάԼĺȡ罫Ԫ(26)תΪ
name=age=26.
ԼݿϵͳƺʵУݵĲѯ͹ҪãҪԭ
(1) ԼĲȷݡʱݺͿռӦ.ĳصĽӦΪ(30mm, 50mm)ƺߵǰӵʱӦһʱ.еݱ仯ģĳһе仯ͼ1.ͼabcεıʽֱΪy=x-1;y=5;2x=-3y+31,ǶӦ3䣺(0,4),(4,6),(6,12).
(2) ΪԼѯЧʣԼڴ洢ʱҲ¼˸ʽӦ䣬ף2ݡ3Ĺ淶ʾνṹԼA<51<BB<7C=6A<BĹ淶ʾΪ11uÿϽ½.󣬿ѰķΧ.


ͼ1ĳһı仯
о80ʼһЩķһάṹInterval_4ݣͿڶάGridļQuad_KD_BInterval_Z_OrderR*_47ݵȣǶɹӦõռݿУǵƽѯЧʽϺãѯI/OʱΪO(n).ΪԼݿʵԣҪһάѯI/OʱͶ̬ʱܴﵽB_.ܵI/OĴΪλģ1.
1νṹԼA<51<BB<7C=6A<BĹ淶

tABC
1-16
u576
=>?
<=?
??=

ȽDM_ݽṹȻDM_Ĳѯ㷨Ͷ̬㷨DM_ļ㸴ԺıȽ. 
2DM_ݽṹ
ΪԼѯЧʣף8ݶSegment5,6ݽ䣬洢ΪO(nlogBn)ѯI/OʱΪO(logBn+t/B).ף9ݡ10Priority Search611ݵĻϷչMeta_,ڲ洢Ͳѯƽ˸ĽĴ洢ΪO(n)ѯI/OʱΪO(logBn+t/B)(tΪѯĸ,BΪĴС).ЩоԶ̬ûиЧ㷨.DM_DM_Ļ˼Meta_Ϊڱ֤Meta_洢(O(n))ͲѯI/Oʱ(O(logBn+t/B))ǰ½B_ķ䶯̬ĸӣʹ֮ﵽB_(ɾI/OʱΪO(logBn)).
Meta_(ͼ2)Ƕάռϵṹ˼ǽάռеĵ㰴λôһУǽB2(B Ϊÿĸ)㣬ʣĵXֵԴС˳ƽֳBݣÿݰͬķγɸ㣬Ϊӽ㣬ȻݹضԸ÷ĵвֱγһ.ӵĻַʽϿԿÿʵʶӦάϵһΣкӦľڸõӦε·.һάݽһά(a,b)תΪάռϵĵ(a,b)ȻMeta_Զάռеĵ㽨ף1ݶԴϸĽ.Meta_̬Ҫѵǽֽʱ޷ͬʱÿεϵ(εĺ·)ÿеĸ(B2)ԼÿӦӦάռеһΣʵMeta_иӦĶάռĵӽĸȷ(ֱΪB2B)ԿԽMeta_ûпǶ̬.


ͼ2Meta_(B=3)
DM_ҲǶԶάռĵ㽨ṹ DM_еĽһΪ㼯ָÿӦĶάռеĵ㣬乹췽Meta_ƣȡĵİ㼯УʣĵΪ0BݣȻÿһݵݹͬĲ.Ϊ˲ɾķ㣬ÿĵĸÿӽĸMeta_ͬҲMeta_ҪȫþνÿӦĵ㻮ֿ(ͼ3ӽSmİ㼯ĳa丸Sİ㼯ĳb).ǽϸDM_ϵ.һάʱҲMeta_һά(a,b)תɶά(a,b)ȻDM_йһάʱǽ㼯ĳΪ伯.ǽҪDM_洢͹һάķ.


ͼ3
ǸһЩ.
1. һһά(a,b)ǼbΪβ.
2. DM_нİ伯ĸΪ.
3. DM_нİ伯ĳӽAϲļϳΪӽAϲ伯.ͼ4 еӰ־ǽAӽAϲ伯.Aϲ伯ĸΪAϲ.ĳϲСB/2ӽΪϲ.
4. ԽAӽϲΪa1,a2,,an,ֵΪBCӽϲֱΪb1,b2,,bmc1,c2,,clӽΪa1,a2,,anb1,b2,,bmһӴСĵB+1Ϊaba1,a2,,anc1,c2,,clһӴСĵB+1ΪacabacСΪAٽ.
DM_Ĺľƣ
(1) .ĳ㹲Aӽ㣬mӽΪϲ㣬ǵϲΪr1,r2,, rm,ӽٽСA/2Ϊs1,s2,, sA/2,ÿ㼯ԭһάΪ(A-m-1)B+r1+r2++rm(A/2-1)B+s1+s2++sA/2СǸ.ͨƺϲԾķֲпƣֹڶ̬ϻ½ʱƽ.
(2) .DM_нÿ伯(AB)/2һά䣬AΪýӽĸ.
(3) .ÿ0Bӽ㣬ڽӽʹB.DM_ĸвBӽ.ɼMeta_DM_.
DM_ӽӦڸİ伯֮(ͼ4).ڰ伯ֲĲԣ̬йƳƻ(Ҫÿ伯AB/2һάһ)Ϊ߶̬ܣDM_в3ֲԣ


ͼ4Meta_(B=4)
(1) .԰伯ƿԱʱΥ
(2) ͺ.伯ƱΥ󣬲еĵʹָ֮Ƶ״̬
(3) ¼ƽϵ.DM_ÿжһṹΪƽϵ¼˸ýǷعƣص.㷨ƽϵDM_ԭķת(ṹľ嶨4).
DM_ÿİ伯Ĵŷɲοף9еĺṹṹ.Ϊ߲ѯЧʣƽϵĽİ伯ɴһ.
3ѯ㷨
йĲѯ3֣
(1) ѯ.ѯĳһ伯ϣѯӦͼ5Q1ϲ(Q1۵y=x)


ͼ5Meta_(B=3)
(2) ѯ.ѯĳһ伯ϣѯӦͼ5Q2ϲ(Q2۵ڶάط)
(3) ཻѯ.ѯĳһཻ伯.ѯӦͼ5Q3ϲ.
ѯ㷨һ㷨һѡԴ洢ҪѯĽ.
㷨1. (ѯQϲֵе)
 ѡУ
 Ӻѡȡһp
 pQĴֱཻpṹԴҵ˳ȡpˮƽཻpĺṹԴµ˳ȡpа伯еȫ߷ΧڻཻӽѡУ
 ѡвתڣ.
4̬㷨
DM_Ķ̬㷨B_Ķ̬㷨ΪDM_һЩĽ.ڽ̬ܶ㷨֮ǰȽһ㷨õйؽṹͱ־.
(1) ƽϵṹ.DM_һƽϵṹq,n qΪƽ㣬nΪƽУn=0ʾýƽϵn<0ʾýİ伯еСƣٵĽڽqİ伯УٵĸΪnn>0ʾýİ伯еƣĽڽqİ伯УĸΪn.
(2) ɲ־.Ӹ·ĳİ伯.ɲ־Ϊ棬ʾûĵת޵.
(3) ɾ־.Ӹɾ·ĳ·иýûнϲΪգɽɾ־Ϊ棬ʾûɾĵת޵.
4.1㷨
DM_ĲɣһҵڵĽ㣻ڶִоĲķֽ.㷨.
㷨2. DM_в(a,b)
(1) DM_ĸʼҵ(a,b)ĽpжϸýǷɲ(伯С)򽫿ɲ־Ϊ.
(2) pСƣpƽṹq,n´
 n0(a,b)pİ伯Уqòƽ㷨pqƽϵ(ǵƽ10ƽϵ).תܣ
 n0(a,b)pİ伯Уqƣqִɾƽ㷨.pqƽϵ(ǵƽ10ƽϵ).תܣ
 n=0(a,b)pİ伯У
 pĸsƽ0sƽִвƽ㷨sƣsִɾƽ㷨ǵƽϵ㷨.
(3) ɲ־Ϊpڻ.(a,b)pİ伯.
 pβֵ丸㣬㸳ppڻƣת٣
 pƽС0pƽɾƽ㷨ǵƽϵ.pƽ0pƽòƽ㷨ǵƽϵ.pĸƽ0pĸƽòƽ㷨ǵƽϵ.㷨.
(4) ɲ־Ϊpڻ.(a,b)pİ伯.pĸƽ0pĸƽòƽ㷨ǵƽϵ.pɾƽ㷨.㷨.
4.2ɾ㷨
DM_ɾɣһҵɾڵĽ㣻ڶִоɾĺϲ.㷨.
㷨3. DM_ɾ(a,b).
(1) DM_ĸrootİ伯а(a,b)ת(3)rootƣ򽫿ɾ־Ϊ棬xϵͶӰaӽ㸳ppϲΪ0򽫿ɾ־Ϊ٣
(2) pİ伯а(a,b)ת(3)pƣ򽫿ɾ־Ϊ棬xϵͶӰaӽ㸳ppϲΪ0򽫿ɾ־Ϊ.ת(2)
(3) pƣpƽṹq,nݣ
 n0(a,b)pİ伯ɾ.pвƽ㷨.pĸtƣtɾƽ㷨tƽвƽ㷨ǵƽϵ.ת(6)
 n0(a,b)pİ伯ɾqвƽ㷨pqƽ.pĸtƣtɾƽ㷨tƽвƽ㷨ǵƽϵ.ת(6).
 pƽ0(a,b)pİ伯ɾת(6)
(4) ɾ־Ϊ棬pڻСƣ(a,b)pİ伯ɾ丸βֵСppĸ㸳pظֱִƵĽ.ʱpĸƣɾƽ㷨.ת(6)
(5) ɾ־ΪpڻСƣ(a,b)Ӱ伯ɾpִвƽ㷨
(6) 类ɾĽɾת޵Ľְ伯(伯βֵĳֵcΪϲеСβֵĳֵcӽB/2)Ըýִв㷨ɾ㷨е.
㷨4. ϲ㷨(rsϲ)
(1) rsİ伯ϲһ
(2) ӽϲһ𣬲޸ƽϵṹ.
㷨5. ƽ㷨
룺DM_һp
(1) pӽqİ伯βֵ(q)븸Уqƣ㷨qΪҶ㣬ת(2)qpת(1)
(2) pڻB2/2㷨ppֵܺpĸ齫Ϊһ͡1ӽ㣬pĸӽֵܵСBת(3)㷨.
(3) pĸrֵsӽСBrsϲ(úϲ㷨)p½ĸ㣬ת(3).㷨.
㷨6. ɾƽ㷨
룺DM_һp.
(1) pΪҶ㣬ת(2).pϲӽϲβֵСӽ㣬ӽ㸳ppڻƣת(1).㷨
(2) ppֵܺpĸСB3+B2㷨
(3) pĸһΪ䣬pĸ㸳p
(4) pĳһֵܹС2Bֵܣ㷨ӽBĽrİ伯ӽһΪrֳ㣬ͬʱİ伯һİ伯ƣƽϵָýһƽϵ(趨ƽƽ).prĸ㣬ת(4).
5ܷ
5.1㷨Է
1. DMĴ洢ռΪO(n/B)DM_ܹO(logBn).(nΪάĸ).
֤. ÿDM_ֻ洢һΣף9еĴ洢ṹɵ洢ռΪO(n/B).
DMB_ͬÿB/2ӽ㣬ÿ AB/2䣬DM_ܹO(logBn).
㷨6Ĳ(3)нһΪʱȻƽ󣬼ƻСƣĺͺƵ.ҲƽԺԺÿβɾִʱ֤ƽϵĽܺͲ䣬Ƶķת.
֤.
2. ڶһзֽʱýκνƽϵ.
֤. ƽϵֻĳִвнзֽʱŻ.
ĳڷֽ֮ǰҪΪýBӽ㣬ֽԭһΪ0Ϊ0ÿӽµ䶼ý䣬ԵٴηֽʱѴﵽˮƽӶƽϵ.ҲƽԺԺÿβɾִʱƽ0Ľ㣬㷨ǲмӵģͬʱƽ1ƽǲڸýֽ֮ǰڵǰ㼰ӽвƽٴηֽʱƽϵѽ.Զ֤.
֤.
1. DM_ÿֻһƽϵ.
֤. ɲ㷨ɵһֻڷֽʱŲйصµƽϵһڷֽʱƽϵDM_ÿֻһƽϵ.֮˷ֽ޷µĽ㣬һƽϵĽ֮ǲµĽģһƽϵĽڵ.
֤.
1Ͷ2Կơͺͼ¼ƽϵϿɱ֤ڶ̬ĹжƵΥֻǴ֮.˿ͨɾƽϵĴ״̬ͬʱڲѯ㷨ǿɨ裬ڵĽƽϵʱӰѯЧ.
3. ѯI/OʱΪlogBn+t/B.(nΪάĸtΪѯĸ).
֤. DM_ϵĲѯϿԿѯڵİ伯3ֿܣ
(1) ȫӽߵˮƽֲཻÿİ伯ĸΪAB/2(һζȡB21)ԶȡⲿĴΪO(t/B)Σ
(2) ߵĴཻ߲Ӷ1пɿDM_ܹO(logBn)㣬ṹصԿÿֻһе䲻ȫѯԶȡⲿֽĴΪO(logBn).
(3) ߵˮƽཻ߲ӽߵˮƽཻɺṹصԿÿֻһе䲻ȫѯӱĵ2ֿ֪DM_ÿAӽ㣬ÿİ伯ĸΪAB/2(ڽĺһ۵)ĳˮƽཻӽA.A+1ٶȡAB/2䣬һζȡڸòֵʴΪO(t/B).̬ɾпɲѯСڶĿB/26еĵ֤.
ԲѯI/OʱΪO(logBn+t/B).
֤.
3ף1жMeta_ĲѯԵķƵ.
4. DM_ĵ㷨вɾI/OʱO(logBn).
֤. DM_ϵĲڵ1ӸҶĲ̵ʱ临ΪO(logBn)ΪֻO(logBn)㣬ÿĲʱ临Ϊ.Ҷϵĵֻһ½еģ临ԿΪǳ.ÿƽ㷨ִеʱ临ΪO(logBn)ִֻ޴ƽ㷨ʱ临ΪO(logBn).
DM_ϵɾ1ӸҶɾ̵I/OʱΪO(logBn)ΪֻO(logBn)㣬ÿĲʱ临Ϊ.Ҷϵĵֻһ½еģ临ԿΪǳ.ÿƽ㷨ִеʱ临ΪO(logBn)ɾִֻ޴ƽ㷨6ֻ԰伯ɾĽת޵ĽʹãҲִֻһΣʱ临ΪO(logBn).
֤.
ƺٽ趨ڸӽ佻ʱְ伯ƽ.ͼ6SS1S2βֵϴӽĲ٣SmSm-1βֵϴӽĲ϶.ӰѯЧ.ɾ㷨ĵ6Ͳ㷨ĵ3һп.


ͼ6
5.2Ƚ
潫DM_ļһ±Ƚϣ2.
2

ƴ洢ЧʲѯI/OʱI/OʱɾI/Oʱ
Interval_O(n/B)O(logBn+t/B)
Segment_O(nlogBn/B)O(logBn+t/B)
Meta_O(n/B)O(logBn+t/B)O(log2Bn)
DM_O(n/B)O(logBn+t/B)O(logBn)O(logBn)

ϱԿDM_Ĵ洢ѯɾЧʴﵽţDM_ۺЧǽϺõ. 
6ܽ
һDM_ԼݿݵĴ洢ͷʣһάĴ洢ѯͶ̬нϺۺܣﵽB_.Ժ󻹽νһԼжάҪһо.
õȻѧ.
߼飺ͮŮ1973ʿҪоΪݿͰṹݴ.
ʩ֣У1935ѧϯڣʿʦҪоΪݿ⡢֪ʶݲֿ.
ߵλѧѧϵϺ200433
ο
1Kanellakis P et al. Constraint query language. Journal of Computer Science and System1995, 51
2Goldin D Q, Kanellakis P. Constraint query algebra. To appear in Constraints Journal 1st issue 1996
3.Լݿ⣺ģʽơѯԼ۲ʿģ. ѧ. Ϻ 1996
(Wang YujunConstraint database: Scheme design, algebra query language and indexing Ph D dissertation(in Chinese). Fudan University, Shanghai, 1996)
4Edelsbruner H. A new approach to rectangle intersections (Part I). Internet Journal of Computer, 1983
5Guting R H. Spatial database systemsVery Large Database '95
6Samet H. The Design and Analysis of Spatial Data Structure. Reading, MA: Addison-Wesley, 1989
7Samet H. Application of Spatial Data Structure. Reading, MA: Addison-Wesley, 1989
8Blankenagel G, Guting R H. External segment tree. Algorithmica, 1994, 12: 498532
9Kanellakis P et al. Indexing for data models with constraints and classes, Principle of Database '93. Washington: ACM Press, 1993. 2528
10Ramaswamy S, Subramanian S. Path caching: A technique for optimal external searching. Principle of DataBase '94. Minneapolis: ACM Press, 1994. 2426
11Mccreight E M. Priority search trees, SIAM Journal of Computer, 1985, 14(2): 257276
ԭյڣ1998-10-06
޸ĸյڣ1999-03-08.
