资源描述
,Klicken Sie,um die Textformatierung des Masters zu bearbeiten.,Zweite Ebene,Dritte Ebene,Vierte Ebene,Fnfte Ebene,Klicken Sie,um das Format des Titel-Masters zubearbeiten.,07/25/02 Martin Pfeifle,Hans-Peter Kriegel,Martin Pfeifle,Marco Ptke,Thomas Seidl,A Cost Model for Interval Intersection Queries on RI-Trees,Institute for Computer Science,University of Munich,Germany,Database Group,SSDBM 2002,Edinburgh,Outline of the Talk,1.Introduction,2.RI-Tree,3.Cost Model,4.Evaluation,5.Conclusions and Future Work,Extended Objects in Databases,t,1D Objects:,Temporal data,Approximate values,Interval constraints,2D Objects:,Geographic data,VLSI design,Bitemporal data,3D Objects:,CAD documents,Digital mockup,Haptic rendering,t,Interval query,Box query,Window query,Integration of Access Methods,Declarative Embedding,Object-relational DML and DDL,Extensible Indexing Framework,query processing,index_open(),index_fetch(),index_close(),maintenance,index_create(),index_drop(),index_insert(),index_delete(),index_update(),Integration of Access Methods,Extensible Indexing Framework,Declarative Embedding,Object-relational DML and DDL,Physical Implementation,Block-Manager,Caches,Locking,Logging,User-defined Index Structure,Extensible Indexing Framework,Object-relational interface for index,maintenance and querying functions.,Relational Implementation,Mapping to built-in indexes(B,+,-trees);,SQL-based query processing,Integration of Access Methods,User-defined Index Structure,Extensible Indexing Framework,Object-relational interface for index,maintenance and querying functions.,Relational Implementation,Mapping to built-in indexes(B,+,-trees);,SQL-based query processing,Physical Implementation,Block-Manager,Caches,Locking,Logging,Declarative Embedding,Object-relational DML and DDL,Extensible Optimization Framework,optimization,stats_collect(),stats_delete(),predicate_sel(),index_io_cost(),Integration of Access Methods,User-defined Index Structure,Extensible Indexing Framework,Object-relational interface for index,maintenance and querying functions.,Relational Implementation,Mapping to built-in indexes(B,+,-trees);,SQL-based query processing,Physical Implementation,Block-Manager,Caches,Locking,Logging,User-defined Cost Model,Extensible Optimization Framework,Object-relational interface for selectivity estimation and cost prediction functions.,Relational Implementation,Mapping to built-in statistics facilities;,SQL-based evaluation of cost model,Declarative Embedding,Object-relational DML and DDL,Outline of the Talk,1.Introduction,2.RI-Tree,3.Cost Model,4.Evaluation,5.Conclusions and Future Work,3,a,15,a,12,c,5,c,15,a,Relational Interval Tree(RI-Tree),1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,15,8,1,3,5,7,13,11,9,2,6,10,14,4,12,alice,bob,chris,dave,7,b,1,b,13,d,13,d,Foundation:,Interval Tree,Edelsbrunner 1980,primary structure:,binary search tree on possible endpoints,secondary structure:,sorted lists of stored endpoints,each interval is registered at exactly one node,Kriegel,Ptke,Seidl VLDB 2000,15,8,1,3,5,7,13,11,9,2,6,10,14,4,12,RI-Tree:,Virtual Primary Structure,15,1,3,5,7,13,11,9,2,6,10,14,4,12,8,root,=2,h1,1,2,h,1,no materialization of the binary tree,storage cost,O,(1):,parameter,root,fixed data space,:,root,=2,h1,covers 1.2,h,1,first,step:,virtualize the primary structure,RI-Tree:,Relational Secondary Structure,8,15,1,3,5,7,13,11,9,2,6,10,14,4,12,3,a,15,a,12,c,5,c,15,a,7,b,1,b,13,d,13,d,second step,:,manage secondary structure by two B,+,-trees,storage of,n,intervals:,O,(,n,/,b,),disk blocks of size,b,insert and delete:,O,(log,b,n,),disk block accesses in the indexes,node,lower,4,8,8,13,1,3,5,13,id,b,a,c,d,node,upper,4,8,8,13,7,12,15,13,id,b,c,a,d,lowerIndex,(node,lower,id),upperIndex,(node,upper,id),upper=25,22=lower,RI-Tree:,Interval Intersection Query,16=root,24=fork,25,28,26,20,22,t,1,2,3,4,h=5,23,upper=25,22=lower,RI-Tree:,Interval Intersection Query,16=root,20,t,1,2,3,4,h=5,select,id,from,upperIndex,i,leftNodes,left,where,i.node=left.node,and,i.upper=,t,.lower,upper=25,22=lower,RI-Tree:,Interval Intersection Query,24=fork,25,22,t,1,2,3,4,h=5,select,id,from,upperIndex,i,leftNodes,left,where,i.node=left.node,and,i.upper=,t,.lower,union all,select,id,from,upperIndex,i,where,i.node,between,t,.lower,and,t,.upper,23,upper=25,22=lower,RI-Tree:,Interval Intersection Query,28,26,t,1,2,3,4,h=5,select,id,from,upperIndex,i,leftNodes,left,where,i.node=left.node,and,i.upper=,t,.lower,union all,select,id,from,upperIndex,i,where,i.node,between,t,.lower,and,t,.upper,union all,select,id,from,lowerIndex,i,rightNodes,right,where,i.node=right.node,and,i.lower=,t,.lower,union all,select,id,from,upperIndex,i,where,i.node,between,t,.lower,and,t,.upper,union all,select,id,from,lowerIndex,i,rightNodes,right,where,i.node=right.node,and,i.lower=,t,.upper,23,Outline of the Talk,1.Introduction,2.RI-Tree,3.Cost Model,4.Evaluation,5.Conclusions and Future Work,join,I/O,(T,t,)=,Gaps,left,(,t,),Gaps,right,(,t,),t,root,t,root,I/O Cost Model for Interval Inter
展开阅读全文