（地球探测与信息技术专业论文）基于r树的空间数据库查询技术研究.pdf

摘要 空间数据库技术是当前数据库领域的一个研究热点。在国内外也 开始应用于许多不同领域。 但空间数据具有数据量巨大，结构复杂，属性数据与空间数据密 切相关，并随其反映的地理特性不同而具有不同的数据类型等特点。 由于空间数据量的庞大，以及空间对象、空间查询的高度复杂性，空 间数据库的查询效率是衡量空间数据库性能的重要指标。实际应用也 对空间数据库的查询性能提出了迫切要求。 本文从研究空间数据库查询技术的基础入手，重点进行了基于空 间聚类的r 一树索引技术、基于r 一树的空问连接索引和基于不均匀空 间对象的空间连接精处理的研究，并在此基础上设计并实现了基于 g i s 的空间数据查询试验系统。 在基于空间聚类的r 一树索引技术的研究中，总结了现有r 一树的 算法特点，提出了面向r 一树的混合空间聚类算法，并分别在动态环 境和静态环境中实现了基于该混合空间聚类算法的动态r 一树与静态 r 一树，同时分别将其与现有动态r 一树和静态r 一树进行了性能对比测 试研究，论证了本文所提出的基于混合空间聚类的耻树在查询性能 方面具有明显的优势。 在基于r 一树的空间拓扑方向连接索引的研究中，首先介绍了空 间对象间的连接关系及其判断准则，随后给出了空间连接索引的概念 及基于r 一树的空间连接方法，提出了基于r 一树的空间拓扑方向连接 索引的概念及其建立过程。空问连接索引的建立过程实际上是对参与 空间连接查询的数据集进行的过滤处理的过程。空间拓扑方向连接索 引是在建立连接索引的过程中加入了拓扑约束与方向约束，文中重点 讨论了拓扑约束与方向约束的一些规则，以及这些规则如何应用于基 于r 一树的拓扑方向空间连接索引的建立过程，并在最后研究了基于 r 一树的距离约束规则，使得本文的空间连接索引可建立在拓扑、方向 与距离关系及其任意组合的基础上，增强了基于r - 树空间连接索引 的完整性与灵活性。 基于不均匀空间对象的空间连接精处理主要是对空间连接查询 处理的精炼阶段研究的研究。在对参与连接的数据集已经建立了空间 连接索引的前提下，针对实际存储空间对象的各页面大小不均匀的特 点，提出了基于不均匀空间对象的实现空间连接精处理的聚类分区 分区排序一页面排序三步策略。页面的聚类分区问题实际上是图的分 区问题，而对各聚类分区的排序问题则实际上是图论中的货郎担问 题。本文采用遗传算法分别实现了页面聚类分区及分区排序，并提出 了一些确定最终页面访问顺序的规则，最后通过实验与现有的空间连 接处理算法进行了对比测试，论证了该算法的可行性和先进性。 g i s 空间数据查询试验系统主要是在分析当前空间数据查询处理 软件并应用本文研究成果的基础上设计并基本实现的。系统的主要功 能包括基本图文互查、点查询、区域查询、最近邻查询和空间连接查 询，其中空间连接查询主要包括空间拓扑连接查询、空间方向连接查 询、空间距离连接查询及其相互问的任意组合。 关键词：空间数据库，空间查询，r 一树，空间拓扑方向连接，过滤 精炼策略，空间连接精处理，连接索引 a b s t r a c t s p a t i a ld a t a b a s et e c h n i q u ei s ah o t s p o ti nt h ea r e ao fd a t a b a s e c u r r e n t l y , a n dt h er e s e a r c h f r u i t sh a v eb e g u nt ob ea p p l i e dt o m a n y v a r i o u sf i e l d s s p a t i a ld a t ah a v et h ec h a r a c t e r i s t i c so fh u g eq u a n t i t y , t h eh i g h c o r r e l a t i o nb e t w e e na t t r i b u t ed a t aa n ds p a t i a ld a t a ，a n dt h ed i f f e r e n td a t a t y p e sw i t ht h ed i f f e r e n tr e f l e c t i v eg e o g r a p h i c a le n t i t i e s a st h eh u g e q u a n t i t yo fs p a t i a ld a t aa n dh i g hc o m p l e x i t yo fs p a t i a lo b j e c t sa n ds p a t i a l q u e r y , t h ee f f i c i e n c yo fs p a t i a lq u e r yi so n eo ft h ei m p o r t a n tf a c t o r s e v a l u a t i n gt h ep e r f o r m a n c eo fs p a t i a l d a t a b a s e a tt h es a m et i m e ， p r a c t i c a la p p l i c a t i o n sh a v ep u tf o r w a r di m p e n d i n gr e q u i r e m e n t sf o rt h e q u e r ye f f i c i e n c yo f s p a t i a ld a t a b a s e i nt h i sp a p e r , t h eb a s i ct e c h n i q u e so fs p a t i a ld a t a b a s eq u e r ya r e f i r s t l yd e s c r i b e d ，a n dt h e n h er e s e a r c h e sf r o mr - t r e es p a t i a li n d e x t e c h n i q u eo ns p a t i a lc l u s t e r i n g ，s p a t i a lt o p l o g y - d i r e c t i o nj o i n - i n d e x b a s e do nr - t r e e ，t ot h es p a t i a lj o i nr e f i n e m e n tf o ru n e v e n l yd i s t r i b u t e d s p a t i a lo b j e c t sa r ee m p h a s i z e d ，a tl a s t ，o nt h eb a s i so f a b o v er e s e a r c h e s ， s p a t i a l d a t a q u e r ye x p e r i m e n t i n gs y s t e m o ng i si s d e s i g n e da n d i m p l e m e n t e d i nt h er e s e a r c hw o r ko fr - t r e ei n d e xt e c h n o l o g y , t h ec u r r e n t a l g o r i t h m so fr - t r e ea v ef i r s t l ys u m m a r i z e d ，a n dt h e nb a s e do nt h e s e a l g o r i t h m s ，t h eh y b r i ds p a t i a lc l u s t e r i n ga l g o r i t h mi sp u tf o r w a r da n dt h e c o r r e s p o n d i n gr - t r e e s a r ei m p l e m e n t e di nb o t hd y n a m i ca n ds t a t i c e n v i r o n m e n t a tl a s t ，s o m ep e r f o r m a n c ec o m p a r i s i o nt e s t sa r ec a r r i e do u t a n dt h ep e r f o r m a n c eo fh c r - t r e ei sp r o v e d i nt h er e s e a r c hw o r ko fs p a t i a lt o p o l o g y - d i r e c t i o nj o i n i n d e xb a s e d o nr - t r e e ，t h ej o i nr e l a t i o n so fs p a t i a lo b j e c t sa n dt h e i re s t i m a t i n gr u l e s a r ei n t r o d u c e df i r s t l y , a n dt h e nt h ec o n c e p to fs p a t i a lj o i n i n d e xa n di t s i m p l e m e n t a t i o nm e t h o d so nr - t r e ea r ed e s c r i b e d ，o nt h e s eb a s i s ，t h e c o n c e p ta n d t h ec o n s t r u c t i n gm e t h o do f t o p o l o g y - d i r e c t i o nj o i n - i n d e xa r e p u tf o r w o r d t h eb u i l d i n gp r o c e s so fs p a t i a lj o i n i n d e xi sa c t u r a l l yt h e f i l t e r s t e p o f s p a t i a lj o i nq u e r yp r o c e s s i n g t h eb u i l d i n g o f t o p o l o g y - d i r e c t i o nj o i n - i n d e x o i lr - t r e ei sa l m o s tt h es a m ew i 廿1t h e p r o c e s so fc o m m o ns p a t i a lj o i n i n d e x ，i ta d d s s o m et o p o l o g i c a la n d d i r e c t i o n a lc o n s t r a i n t si nt h ep r o c e s sw h i c ha r ee m p h a s i z e di nt h i sp a p e r i nt h ee n d ，t oi m p r o v et h ef l e x i b i l i t ya n dc o m p l e x i t yo fs p a t i a lj o i n i n d e x ， t h ed i s t a n c ec o n s t r a i n t sa r ed i s c u s s e d t h es p a t i a lj o i np r o c e s s i n go na s y m m e t r i c a ls p a t i a lo b j e c t si sm a i n l y r e l a t i v et ot h er e f i n e m e n ts t e po fs p a t i a lj o i nq u e r yp r o c e s s i n g i nt h e p r e c o n d i t i o no fb o t hd a t a s e t sh a v i n gb u i l ts p a t i a lj o i n i n d e x ，a c c o r d i n gt o t h ea s y m m e t r yc h a r a c t e r i s t i co fp r a c t i c a lp a g e s ，t h et h r e e s t e pp r o c e s s i n g s t r a t e g yo na s y m m e t r i c a ls p a t i a lo b j e c t s ，w h i c ha r ec l u s t e r sp a r t i t i o n i n g ， p a r t i t i o n ss c h e d u l i n ga n dp a g e ss c h e d u l i n g ，i sp r o p o s e d t h e c l u s t e r p a r t i t i o n i n g i s a c t u r a l l yt h ep a r t i t i o n i n gq u e s t i o n o fg r a p ha n dt h e p a r t i t i o ns c h e d u l i n gi st h et s pq u e s t i o no fg r a p hi nn a t u r e i nt h i sp a p e r , g e n e t i ca l g o r i t h mi si n t r o d u c e dt os o l v et h e s ep r o b l e m ss u c ha sc l u s t e r p a r t i t i o n i n ga n dp a r t i t i o ns c h e d u l i n g o nt h eb a s i sa n dr e s u l t so fa b o v e ， s o m ed e c i s i v er u l e so fp a g ea c c e s s e sa r ep r o v i d e d a tl a s t ，s o m e e x p e r i m e n t sa n dc o m p a r i s o n sa r ec a r r i e do u ta n dt h ef e a s i b i l i t y a n d a d v a n c e m e n to f t h i sa l g o r i t h ma r ep r o v e d i nt h ee n d ，t ov a l i d a t ea n dt e s tt h ea b o v ea l g o r i t h m s ，an e ws p a t i a l d a t aq u e r ye x p e r i m e n t i n gs y s t e mo ng i si sd e s i g n e da n dd e v e l o p e d t h e s y s t e mi sm a i n l yo nt h eb a s i so fa n a l y s i so fc u r r e n ts p a t i a ld a t aq u e r y s o f t w a r e sa n dt h ea p p l i c a t i o no fr e s e a r c hr e s u l t so ft h i sp a p e r t h em a i n f u n c t i o n so ft h i ss y s t e mi n c l u d eb a s i cq u e r y , p o i n tq u e r y , r e g i o nq u e r y , n e i g h b o r - n e a r e s tq u e r ya n dj o i nq u e r ya m o n gw h i c hj o i nq u e r yi n c l u d e s s p a t i a lt o p o l o g yq u e r y , d i r e c t i o nq u e r y , d i s t a n c eq u e r y a n da n y c o m b i n a t i o no f t h e s eq u e r i e s k e yw o r d s ：s p a t i a l d a t a b a s e ，s p a t i a lq u e r y , r t r e e ，s p a t i a l t o p o l o g y d i r e c t i o nj o i n ，f i l t e r - a n d r e f i n e m e n ts t r a t e g y , s p a t i a lj o i n r e f i n e m e n t ，j o i n i n d e x 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使 用过的材料。与我共同工作的同志对本研究所作的贡献均己在论文中作了明确的说 明。 作者签名：日期：年月日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复 印、缩印或其它手段保存学位论文；学校可根据国家或湖南省有关部门规定送交学位 论文。 作者签名 导师签名多3 匀孑硬期： 年月 日 中南大学博士研究生学位论文 第一章绪论 第一章绪论 近年来，与空间信息相关的数据受到了计算机应用领域的高度重视，这些领域通 过扩充数据库管理系统的功能来支持与空间相关的数据。空间数据库的研究成果( 如 空间多维索引) 也已开始应用于许多不同领域。这些应用包括地理信息系统( g i s ， g e o g r a p h i c a li n f o r m a t i o ns y s t e m ) 和计算机辅助设计( c a d ，c o m p u t e r - a i d e dd e s i g n ) ，以 及诸如多媒体信息系统( m m i s ，m u l t i - m e d i ai n f o r m a t i o ns y s t e m ) 、数据仓库( d a t a w a r e h o u s e ) 、地球观测系统等潜在的应用。正是已有应用的需求推动了空间数据库管理 系统的研究。也使得空间数据库技术成为当前数据库领域的一个研究热点。空间数据 库管理系统的研究也成为找到有效处理空间数据的模型和算法的重要步骤。 1 1 课题研究背景 空问数据库的查询效率是衡量空问数据库性能的重要指标。由于空间数据量的庞大 以及空间对象、空间查询的高度复杂性，实际应用如地理信息系统( g i s ) ，c a d c a m 等对空间数据库的查询性能提出了迫切要求。 空间查询是空间数据库的重要操作。商业数据库的主要厂商已推出专门处理空间 数据的产品，其中包括e s r i 开发的空间数据引擎( s p a t i a ld a t ae n g i n e ，s d e ) ，以及 i n t e r g r a p h 、a u t o d e s k 、o r a c l e 、i b m 和i n f o r m i x 等公司在对象一关系数据库服务器上 开发的空间数据插件，研究的原型系统有p o s t g r e s 、g e 0 2 和p a r a d i s e 。这些系统都提供 一组空间数据类型( 如点、线和多边形) 和一组空间操作功能( 求相交( i n t e r s e c t i o n ) 、 闭合( e n c l o s u r e ) 和距离( d i s t a n c e ) ) 。开放地理信息系统( o p e ng e o g r a p h i ci n f o r m a t i o n s y s t e m ，o g i s ) 协会制定出一套空间数据类型和空间操作的现行标准，使得空间类型 和操作可以象s q l 3 那样成为对象一关系查询语言中的一部分。为了增强性能，这些 系统还为空间存取方法、空间范围查询以及空间连接查询等提供了多维空间索引和算 法。 但由于空间数据库的前沿性和高度复杂性，目前的空间查询技术还不是很成熟。 在实际应用过程中，用户往往希望空间数据库能提供一些能更直接计算空间对象关系 ( 如拓扑关系、顺序关系、度量关系等) 的功能，例如用户希望查询满足下列条件的 矿点： 1 ) 在某条铁路的东部； 2 ) 距离该铁路不超过3 0 k i n ； 3 ) 矿点类型为锑矿； 4 1 远离居民点。 中南大学博+ 研究生学位论文第一章绪论 整个查询计算涉及了空间顺序( 铁路东部) 、空间距离关系( 距离该铁路不超过 3 0 k m ) 、空间拓扑关系( 与居民点相离) 、属性查询( 矿点类型为锑矿) 。就目前成熟的 g i s 系统( 如m a p l n f o 、a r c g i s 等) 和空间数据库( 如m a p l n f os p a t i a l w a r e 、a r c s d e 、 o r a c l es p a t i a l 等) 而言，要比较系统地完成上述查询还较为困难，到目前仍处于理论 发展和技术探索阶段。本文主要对空间数据库的查询技术进行了一些研究和探索，以 便对空间查询技术的完善作出贡献。 g i s 是空间数据库发展的主体，查询、检索是g i s 中使用最频繁的功能之一。g i s 用 户提出的大部分问题都可以表达为查询的形式。查询功能是g i s 面向用户的窗口，是用 户感觉g i s 能力的最直接的具体表现。近些年来，随着g i s 的迅猛发展，广大用户对空 间查询提出了更高更复杂的要求，简单的图文互查己远远不能满足g i s 用户的需求。虽 然已有许多专家学者致力于空间查询方面的研究，并取得了一些可喜的研究成果，但 距用户的复杂查询要求还有一定的差距，还有待进一步深入和加强。对空间查询技术 的研究已成为当前g i s 研究领域需要进一步深入解决的重大前沿课题之一。 本论文的研究主要体现在g i s 应用上。g i s 的应用范围极广，在全球范围内，g i s 技 术可用于全球变化与监测的研究，在一个国家的范围内，g i s 技术可用来进行全国范围 内的自然资源调查、环境研究、土地利用状况、森林管理、农作物生产、各种灾害预 测和防治、国民经济调查和宏观策略分析等。随着廉价且功能强大的g i s 的出现，其应 用正逐渐扩大。在一个城市范围内，g i s 技术可用作土地管理、房地产经营、污染治理、 环境保护、交通规划、上下管线管理、市政工程服务和城市规划等。 但g i s 对地下信息管理、分析、查询和显示的能力还较弱“1 ，目前g i s 在地学领域 的大部分应用是作为基本的地学数据管理系统。在地学研究与应用领域，数代地质学 家通过艰苦的努力积累了大量而宝贵的地学资料，这些地学资料是多来源、多学科的， 不仅包括地质各部门的区域地质调查数据和矿产普查数据，矿产勘查部门的勘查工程 数据和矿山开发中获取的矿体数据，地球物理勘查数据，地球化学普查数据，地质遥 感数据以及基础地理数据，还包括与地质矿产有关的各项研究成果数据等，对这些资 料的存储、加工、查询及分析处理、再利用，一直是地质学家渴望解决的重大课题。 电子技术、计算机技术、航天航空技术及通信测量技术的发展，尤其是g i s 技术的发 展，使得数据库、数据分析与处理、3 s 技术成为资料处理的重要手段，地质资料不再 是令人生畏而孤立的数字与文字的堆积与表述，而成为相互关联的、可视的、对地质 现象进行三维或多维显示及模拟的图形，g i s 已逐渐成为地质学家探索地下奥秘的利 器。利用g i s 进行多源地学数据的综合与融合，进行复杂的地学查询、分析、评价与 预测，是g i s 在地学领域的一大应用特色，也是g i s 研究领域有待进一步深入研究的 课题之一。 a r c l n f o 系统就是一个很好的地学分析应用软件系统。作为商业化产品，g i s 一改 中南人学博士研究生学位论文 第一章绪论 人们传统的商业战线中制图和用图的模式，用现代计算机技术来管理和分析空间数掘， 并将结果可视化。只要恰当运用，现代g i s 将是勘查地质学家强有力的新工具，地形 分析、流域分析、土地利用研究、经济地理研究、空间决策支持、空间统计分析、矿 产资源评价、制图等都可以借助g i s = ：具完成，g i s 己成为许多矿业公司日常工作内 容的一部分。 1 2 空间数据库及其查询研究的基本问题 空间数据查询是空间数据库的基本而重要的操作，空间数据查询的研究内容与空 问数据库密切相关，其基本问题主要体现在空间数据库相关内容的组织上。 空间数据库系统是一个存储空间和非空间数据的数据库系统，支持多种空间数据 模型、相应的空间抽象数据类型( a d t ) 及一种能够调用这些a d t 的查询语言，支持 空间索引、高效的空间操作算法及用于查询优化的特定领域规则。空间数据库主要用 以处理空间数据及与空间位置相关的属性数据，其研究内容主要包括： 1 2 1 空间数据及属性数据分析 空间数据是指用来表示空间实体的位置、形状、大小及其分布特征诸多方面信息 的数据，它可以用来描述来自现实世界的目标，它具有定位、定性、时间和空间关系 等特性。定位是指在己知的坐标系里空间目标都具有唯一的空间位置；定性是指有关 空问目标的自然属性，它伴随着目标的地理位置；时间是指空间目标是随时间的变化 而变化；空间关系通常一般用拓扑关系表示。 空间数据按不同来源和方式( 遥感与非遥感手段等) 分为矢量数据和栅格数据， 包括地图、影像、统计数据等。它是一种用点、线、面以及实体等基本空间数据结构 来表示人们赖以生存的自然世界的数据。 空问数据是数字地球的基础信息，数字地球功能的绝大部分将以空间数据为基础。 现在空间数据已广泛应用于社会各行业、各部门，如城市规划、交通、银行、航空航 天等。随着科学和社会的发展，人们已经越来越认识到空间数据对于社会经济的发展、 人们生活水平提高的重要性，这也加快了人们获取和应用空间数据的步伐。 属性数据与空间数据密切相关，有时又称作非空间数据，是属于一定地物或现象、 描述其特征的定性或定量指标，随着其反映的地理特性不同，有不同的数据类型。 中南大学博+ 研究生学位论文 第一章绪论 1 2 2 空间模型分析 数据模型是用来抽象、表示和处理现实世界中的数据和信息，是对现实世界的模 拟。空间数据模型就是寻求一种描述地理实体的有效的数据表示方法，根据应用要求 建立实体的数据结构和实体之间的关系，把它们合理地组织起来，便于应用。空间数 据模型常分为两类：即场模型和对象模型【2 】。基于场的模型将信息空间视为在空间结构 上一定空间分布的集合体，每一个空间分布可以被规则化成一个从空间结构框架到空 间属性的数学函数。如空间高程分布、降雨量分布和气温分布等。基于对象的模型将 信息空间视为离散的、可标识的和与空间相关的对象的集合体。 1 2 3 空间数据库设计 空间数据库的设计中首先分析需要存贮的数据，包括数据范围、数据分辨率、坐 标系等。数据范围包括水平和垂直范围、数据分层、空间数据和属性数据是否采用一 体化的数据存贮形式，空间数据是采用无缝数据组织还是按图幅进行组织等。其次是 要确定可以在空间数据库上进行的数据操作，包括数据更新和数据查询。数据更新包 括插入、删除和修改，数据查询包括点查询、区域查询、连接查询和近邻查询等。还 要设计空间数据库的输入与输出，设计空间数据查询语言和用户查询接口。 1 2 4 空间数据操作 空间数据库基本空间操作可分为四组 3 】： 1 ) 更新操作：标准数据库操作，如修改、创建等。 2 ) 选择操作：可分为点查询和区域查询两种。 夺点查询( p o i n tq u e r y , p q ) ：给定一个查询点p ，找出所有包含它的空间对象0 ： 使得： p q ) = ( o fp8 0 g m ( 1 - 1 ) 其中o g 为对象0 的几何信息。 夺范围或区域查询( r a n g eo rr e g i o n a lq u e r y , r q ：给定一个查询多边形p ，找出 所有与之相交的空间对象0 。当查询多边形为矩形时，称为窗口查询。这类查询有 时也称作范围查询。 r q ( p ) = to i o g n e g 由)( 1 2 ) 3 ) 空间连接：当两个表r 和s 基于一个空间谓词0 进行连接时，则该连接称为空 间连接。 4 中南大学博十研究生学位论文 第章绪论 1 2 2 空间模型分析 数据模型是用束抽象、表示和处理现实世界中的数据和信息，是对现实世界的模 拟。空间数据模型就是寻求一种描述地理实体的有效的数据表示方法，根据应用要求 建妒实体的数据结构和实体之f 日j 的关系，把它们合理地组织起来，便于应用。空f 耳j 数 据模型常分为两类：即场模型和对象模型口j 。基于场的模型将信息空问视为在空间结构 上一定空间分布的集合体，每一个空间分布可以被规则化成一个从空问结构框架到空 间属性的数学函数。如空间高程分布、降雨量分布和气温分布等。基于对象的模型将 信息空间视为离散的、可标识的和与守问相关的对象的集合体。 1 2 3 空间数据库设计 空间数据库的设计中首先分析需要存贮的数据，包括数据范围，数据分辨率，坐 标系等。数据范围包括水平和垂直范围、数据分层、空间数据和属性数据是否采用一 体化的数据存贮形式，空间数据是采用无缝数据组织还是按幽幅进行组织等。其次是 要确定可以在空间数据库l 进行的数据操作，包括数据更新和数据查询。数据更新包 括插入、删除和修改，数据查询包括点查询、区域查询、连接查询和近邻查询等。还 要设计空问数据库的输入与输出，设计空间数据查询语言和用户查询接口。 12 4 空间数据操作 空间数据库基本空间操作可分为四组p l ； 1 ) 更新操作：标准数据库操作，如修改、创建等。 2 ) 选择操作：可分为点查询和区域查询两种。 夺点查询( p o i n tq u e r y ，p q ) ：给定一个查询点p ，找出所有包含它的卒间对象o ： 使得： p q ( p ) = o p8 0 ( + ( 1 1 ) 其中o g 为对象o 的几何信息。 夺范围或区域查询( r a n g e 0 rr e g i o n a lq u e r y , r q ) ：给定个杏询多边形p ，找山 所有与之相交的空问对象o 。当查询多边形为矩形时，称为窗口查询。这类查询有 时也称作范围查询。 r q ( p ) = o i o g n e g 十， 3 1 空间连接：当两个表r 和s 基于一个空间谓词0 进行连接时 3 ) 空间连接：当两个表r 和s 基于一个空间谓词0 进行连接时 间连接。 ( 1 2 ) 则该连接称为空 则该连接称为空 中南大学博士研究生学位论文第章绪论 r 4 0s 2 ( ( o ，o ) f o8 r ，0 7 s ，0 ( o g ，o r g ) ) ( 1 - 3 ) 其中谓词0 包括相交、包含、被包围、距离、西北、邻接、接触、交叠等。 4 ) 空间聚集 空间聚集通常都是最近邻搜索( n n q ) 问题的变体，即给定一个对象o ，找出所 有距o 最近的对象o 。 n n q ( o ) = ( olvo ”：d i s t ( o g ，o g ) d i s t ( o r g ，o ff g ) ) ( 1 4 ) 其中选择操作、连接操作以及空间聚集都可归结为空间查询操作。空间数据查询 是空间数据库中重要的一类几何操作【4 】，指对空间对象的属性、空间位置、范围和关系 按一定的条件进行检索，形成一个新的数据子集，以便于空间分析1 4 1 。由于空间数据的 复杂性和用户需求的不确定性，事先完全预计用户可能提出的空间查询是不可能的。 空间查询大体上可分为点查询、区域查询、连接查询和最近邻查询。 1 2 ，5 空间数据访问方法 空间数据访问方法是空间查询的技术基础，它由空间索引和在空间索引上的操作 组成。空间数据索引及空间数据访问方法是空间数据库技术的一个研究热点。 空间索引就是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一 定的顺序排列的一种数据结构。其中包含空间对象的概要信息，如对象的标识、外接 矩形及指向空间对象实体的指针。空间索引的性能的优劣直接影响空间数据库和g i s 的整体性能，它是空间数据库和g i s 的一项关键技术。作为一种辅助性的空间数据结 构，空间索引介于空间操作算法和空问对象之间，它通过筛选作用，大量与特定空间 操作无关的空间对象被排除，从而提高空间操作的速度和效率。 1 2 6 其它技术问题 空间数据库技术中的其它技术问题包括缓冲区管理，空间几何算法的设计与实现， 空间数据库的并发控制和数据恢复，对传统关系型数据库进行扩展使之能高效处理空 间数据，数据库新技术如面向对象技术、对象一关系技术等在空间数据库中的应用等。 本文对空间数据库查询技术的研究主要集中在空问数据访问方法以及空间连接查 询的算法研究上。 l _ 3 空间数据库查询技术的国内外研究现状 近年来，空间查询已逐渐成为空间数据技术领域的研究热点之一。在国外，有众 中南大学博士研究生学位论文第一章绪论 多的研究机构、大学和公司进行空间数据库技术的研究。美国f 着手建立全球空间数 据库；当前市场中已有如m a p i n f o 、a r c g i s 等实用g i s 系统；有一大批如g e o + + 、q l g 等实验系统，很多新的技术都已应用于这些实验系统；当前一些主流关系型数据库系 统如o r a c l e 、i n f o r m i x 、s y b a s e 等都开始提供空间数据的处理功能；数据库领域的国际 著名学术会议如a c ms i g m o d 、a c mp o d s 、v l d b 、i c d e 和c i k m 等都将空间数 据库技术作为一个重要主题，同时国际上还有专业的空间数据库技术学术会议s s d 和 a c m g i s 等。 在国内，目前开展空问数据库研究的单位还不多，主要集中在几所大学和中科院 部分研究所。北京大学将空间数据库做为一个研究重点；上海复旦大学、武汉测绘科 技大学以及国防科学技术大学都在进行g i s 中空间数据库技术的研究；华中理工大学 丌发的达梦数据库也在空间数据方面进行了扩展。 空间数据查询技术的研究现状主要体现在以下几方面。 1 ，3 1 空间数据模型和表达 空间数据模型和表达方面近年来有大量的文献：c d t o m l i n 5 【6 分析了基于区域的 空间数据模型，m j e g e n h o f e r 7 】和r h g u e t i n g 等 8 】分析了基于对象的空间数据模型； t b r i n k h o f f 等9 1 分析了空间对象的表达方法。 1 3 2 空间数据访问方法 空间数据访问方法是空间查询的技术基础，对空间数据库的查询需要研究多维查 询方法，它是空间数据库中一个十分重要的问题【l0 【l ”，常用于进行空间限制( 如范围 限制、交、重叠等) 和有效地计算空间连接【1 3 】【1 4 1 。传统数据库有许多有效、可行的 存取方法，如b 一树，扩展的h a s h i n g 等，但都是一维存取方法。为处理多维空问数据 查洵，一种方法是连续对每一维都应用一维存取方法。然而，这种方法效率不高，因 为每个索引在遍历时和其它索引相互独立，在某一维搜索可能效率高，但不一定对其 它的索引有效。通常，需要扩展一维存取方法以处理多维数据。 按是否需要访问磁盘，可将多维空间数据访问方法分为主存访问方法和辅存访问 方法两种。早期的多维存取方法并不考虑分页的第二存储区，主要为主存储区而设计， 所有的数据可直接从主存获得而不需要访问磁盘。这类访问方法如k d 树、b d 树、四 叉树( 包括点四叉树和区域四叉树) 【1 5 】。辅存访问方法如基于m o r t o n 码的b + 树i l ”、 k d b 树 1 7 】、b d 树、r _ 树、m o f 树1 8 1 、变形粗网格索引【1 9 1 等。本文主要研究辅存访 问方法。 6 中南大学博士研究生学位论文 第一章绪论 辅存访问方法又可分为点访问方法( p a m s ，p o i n ta c c e s sm e t h o d s ) 和空间访问方 法( s a m s ，s p a t i a l a c c e s sm e t h o d s ) 。p a m s 分为三种：基于h a s h i n g 的访问方法、层次 访问方法和空间填充曲线访问方法。通常运用的方法是结合几种访问方法的优点而提 出的混合方法。s a m s 通常采用如下四种技术： 基于空间变换的方法【2 0 l ：基本思想是把空间中复杂对象变换为另一空间的简单对 象，或把高维空间的空间数据转化为低维空间的空间数据。它又可分为参数空间索引 方法和把高维空间变换到一维空间的方法。 基于区域交叠的方法：众所周知，如果不考虑重叠的情况，点对象可包含在单个 的子空间内，而非点对象或许需要几个子空间才能完全被包含。为了消除这种情形带 来的不便，允许子空间交叠以便空间对象只包含于一个单一的子空间内。并利用分层 划分，在这些子空间之间建立一种分层索引，从而相应地在空间对象之间也建立起了 相应的索引顺序。该方法包括r - 树 2 1 j 、r + 树、p 树、s k d 树、g b d 树、p l o p 一树等。 基于区域分割的方法：其思路是把所涉及的空间域划分成不相连接的子空间，对 子空间进行索引。该技术又可分为对象复制和对象剪切。 对象复制是指空间对象的标示被复制和存储在与它相交的子空间内。也就是说， 对象的标示可能被存储在多个页面中。而对象剪切是把一个对象分解成几个不相连接 的几个更小的对象，以便每个更小对象完全地包含在子空问内。实际上，对象复制和 对象剪切所采用的数据结构是基本的点索引结构的直接扩充，点和非零大小的空间对 象能够被存放在同一个文件中而无须修改结构。它的缺点是对象复制需要额外的存储 开销，而使得插入和删除操作过程更为复杂。该方法包括扩展的k - d 树、k 十树、r 十 树、c e l l 树口2 1 等。 多层方法：采用多层网格文件技术，包括r 一树、g 树【2 3 】等。其基本思想是将研究 区域纵横分成若干个均等的小块，每个小块都作为一个桶，将落在该小块内的地物对 象放入该小块对应的桶中【2 4 】。从精度考虑，小块还可细分，直至不可再分为止。当用 户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询 所选空间实体，这样就大大加速了空间索引的查询速度。但由于网络文件技术本质上 会使目录非常松散，因而浪费主存缓冲区和二级存储数据空间。 值得指出的是，一个索引结构往往不只使用一种索引技术，因为单个索引技术虽 然有它的优点，但也有它自己的缺陷，两个或更多方法的综合运用也许能够达到相互 取长补短的目的。 近二十多年来，基于r _ 的多维访问方法的研究成为空间数据访问方法的一个研究 热点，t s e l l i s ，n r o u s s o p o u l o s 和c f a l o u t s o s l 2 5 1 在v l d b 的十周年纪念发言t r e e sh a v e g r o w ne v e r y w h e r e ”中指出了r - 树是目前空间( 多维) 数据访问方法的基础，已有许多 学者致力于r - 树的研究，比较典型的r - 树研究有r 一树2 1 1 、r + 树、r 一树”1 、压缩 7 中南大学博七研究生学位论文第一章绪论 r 一树口引、h i l b e r tr - 树【捌、s t rr - 树口8 1 等，s t l e t e n e g g e r 等以概率论的方法分析 了使用l r u 缓冲管理算法对r 树性能的影响，m k o m a c k e r 川讨论了以r 树为基础的 通用搜索树中并发控制问题，s o t i r i sb r a k a t s o u l a s 等p 2 l 提出了一种c r 树，采用聚类 方法动态实现r 树的节点分裂。 所有这些r 树的研究方法都是在g u t t m a nr 树基础上对r - 树某一方面或某几方 面性能进行改善，都不同程度存在这样或那样的缺陷和不足，对r - 树的研究特别是对 查询效率要求较高的r ，树的研究还有待进一步深入。 1 3 3 空间连接查询 空间连接是空间数据库中最重要的一种空间查询，按照数据集上是否存在空间索 引结构，空间连接处理方法可分为以下三种：a 、即两个数据集上都不存在空间索引结 构；b 、只有一个数据集上存在空间索引结构；c 、两个数据集上都存在空间索引结构。 目前，针对第一种情况提出的方法有，基于划分的空间h a s h 连接口”、空间合并连接 p b s m l 3 4 l 及其改进方法【3 5 】、基于g 树的空间连接f 2 3 1 、基于排序的大小分离空间连接 s 3 j 3 6 】、基于分布扫描的可伸缩空间连接s s s j ”1 等；针对第二种情况提出的方法有：基 于种子树0 8 1 索引方