（计算机软件与理论专业论文）空间数据库拓扑和方位关系查询的研究与实现.pdf

华中科技大学硕士学位论文 擅要 空间数据库管理系统是用来存储和管理空间数据和常规数据的数据库管理系 统。目前，用户已不再满足从空间数据库中获得原始的数据，更需要获得关于这些 数据的抽象信息，从而使空间分析和空间推理成为空间数据库管理系统中的研究和 ， 应用重点。f 作为空间分析和空f u q 推理的基础，拓扑关系查询和方位关系查询也已经 l ? 成为空间数据库管理系统必需提供的基本功能。扣 在安全空间数据库管理系统d ms d b 的系统设计中，为了达到查询处理的高 效率并和国际标准兼容，该系统以o p e n g i s 标准中的九交矩阵模型作为空间拓扑关 系的定义模型，并以“面模型”作为空间方位关系的定义模型，采用了阶段式查 询方法，实现了拓扑关系查询和方位关系查询。 2 d + 串是一种有实用价值的描述空间对象方位关系和拓扑关系的方法，能有效 为一阶段式查询提供空间对象方位关系及拓扑信息。改进后的2 d “串结构细化了 s a m e 位置，用于描述空间对象间的关系能更符合人们的语意，加上它预先已计算了 空间对象之间的拓扑关系，因此，当进行拓扑查询时避免了复杂且代价较高的拓扑 计算，使得d ms d b 能够更好的支持高级空间分析。恫时，系统还实现了o p e n g i s i 的标准函数，提供了丰富的数据接口和工具以支持空间查询和空间分析，使得 、 d ms d b 能够更好地支持g i s 、c a d 等应用软件。一 关键词：数据库管理系统：空间数据库：拓扑关系：方位关系：拓扑关系查询；方 位关系查询 华中科技大学硕士学位论文 a b s t r a c t s p a t i a ld b m s i sa t y p eo f d b m sw h i c h m a n a g e s b o t hs p a t i a ld a t aa n dn o r m a ld a t a a n d n o w 。s p a t i a ld a t a b a s eh a v e t ob e c o m em o r ea n dm o r ei n t e l l i g e n tt os u p p o r tm o r ea n d m o r ea p p l i c a t i o n sw h i c hf o c u so nt h es p a t i a la n a l y s i sa n ds p a t i a lr e a s o n i n g s ot h e t o p o l o g yq u e r i e sa n dd i r e c t i o nq u e r i e sw h i c hs u p p o r tt h ea d v a n c e ds p a t i a la n a l y s i sa n d c a nm a i n t a i nt h ei n t e g r i t yo ft h es p a t i a ld a t ab e c o m eah o ts p o to fs p a t i a ld a t a b a s e r e s e a r c h s a f e t ys p a t i a ld b m s ，d m s d b a i m e dt od e v e l o pas p a t i a ld b m s c o p y r i g h t e db y c h i n a d m s d be x p a n dd m d b m st os u p p o r ts p a t i a ld a t a ，a n dp r o v i d ec l i e n tt o o l st o d e f i n e ，s t o r e ，r e t r i e v ea n da n a l y z es p a t i a l d a t a t ob ec o m p a t i b l ew i t hi n t e r n a t i o n a l s t a n d a r d ，d m s d bu s en i n ei n t e r s e c t i o nm a t r i xm o d e la st o p o l o g ym o d e l ，a n d “p l a n e ” m o d e la sd i r e c t i o nm o d e l b yd e v e l o p i n g2 d “s t r i n gw h i c hd e s c r i b e st h et o p o l o g ya n dd i r e c t i o nr e l a t i o n o f s p a t i a lo b j e c t s w ei m p l e m e n tt h et o p o l o g i c a lq u e r ya n dd i r e c t i o n a lq u e r yo fd m s d b d ms d bc a np r e s e n tm o r ep r e c i s ed i r e c t i o nr e l a t i o nt h a no t h e rs y s t e m b e c a u s e2 d ” s t r i n gd e t a i l st h es a m ep o s i t i o n w ec a r la c h i e v eh i g h e rq u e r yp e r f o r m a n c e b e c a u s e2 d ” s t r i n gp r o c e s s e st h et o p o l o g i c a la n d d i r e c t i o n a lq u e r i e si no n ep h a s e w ea l s oi m p l e m e n t t h es t a n d a r df u n c t i o n sw h i c hc a nf u l f i l lt h er e q u i r e m e n tb ya p p l i c a t i o n ss u c ha sg i s ， c a d e t c k e yw o r d s ：d b m s ；s p a t i a ld a t a b a s e ；t o p o l o g yr e l a t i o n ；d i r e c t i o nr e l a t i o n ；t o p o l o g y q u e r y ；d i r e c t i o nq u e r y i i 华中科技大学硕士学位论文 = e暑j 高；昌= ；j 昌葛岩崔葛皇皇蕾- 置_ _ 覃鼻皇皇- l _ _ 冒_ _ - - i l 昌昌皇崔昌墨 1 1 项目来源及研究背景 1 绪论 近年来，随着地理信息系统( g e o g r a p h i ci n f o r m m i o ns y s t e m ，g s ) 、计算机辅 助设计( c o m p u t e r a i d e d d e s i g n ，c a d ) 技术应用和发展，作为支撑它们应用的基本 软件平台，统一管理具有一定地理要素特征的相关空间数据集合的数据库管理系统 空间数据库管理系统已渐渐成为数据库管理系统研究领域的研究热点。 由于传统关系数据库不支持空间数据类型，因此，大多数g i s 、c a d 软件采用 分离的方式管理空间数据，即常规数据为关系模式，而空间数据以文件形式存放。 这种分离的体系结构无法获得数据库系统的有效支持，因此造成空间数据管理效果 低下，数据操作困难，数据共享性差，并且应用在网络方面无法得到有效拓展。 随着数据库技术不断发展，大型关系型、对象关系型、纯对象型数据库在完整 性、安全性、标准化、开放性、可扩充性等方面日益完善，目前不少数据库厂商已 推出空间数据库管理系统商品或插件。这些商品可将空间数据和常规数据有机地集 成起来，实现有效的存储和管理，查询和各种分析操作。比较有名的商用软件有 o r a c l e 8 i 的空间数据库插件、a p i n f o 公司的s p a t i a l w a r e 空间数据库服务器、e s r i 的a r c s d e 8 空间数据库引擎等。国内目前并没有类似商用产品出现。本课题来源于 科技部中小企业技术创新基金无偿资助项目“安全空间数据库管理系统d m s d b ”， 该项目的目标就是实现一个具有自主版权的商用空间数据库管理系统。 随着数据库应用的广泛和深入发展，许多用户需已不再满足仅仅从数据库中获 得原始的数据，还需要得到关于这些数据的抽象信息。对于空间数据库管理系统而 言，高级空间分析和空间推理已日渐成为其研究和应用的重点。而作为支持空间分 析的基础功能，拓扑关系查询和方位关系查询已经成为空间数据库管理系统必需提 供的功能。本课题的目标就是实现d m s d b 的拓扑关系查询和方位关系查询，使 d m j d b 能够更好的支持高级空间分析，并且提供丰富的数据接口和工具，满足 d ms d b 用户的需求。 华冲科技大学硕士学位论文 = - | ：i = 目目目j l 目目目目= 目自目_ _ _ j _ l i g ；_ _ 目t _ e l _ - l _ 目_ _ i = = 自 1 2 国内外研究概况 进行空间数据库管理系统研究的目的是为了解决如何对空间数据进行有效的 表示、存储和处理等问题，而且它是g i s 、c a d 等系统的核心支撑软件，因此研究 它有十分重要的意义。本节将首先介绍空间数据库管理系统的研究概况，随后将分 别介绍拓扑关系和方位关系的研究概况。 1 2 1 空间数据库蕾理系统研究概况 空间数据库管理系统应该具有如下特征：1 是一个数据库管理系统；2 具有 处理空间数据的空间数据类型( s d t ) 和查询语言；3 支持空间索引和有效的空间连 接”1 。实际上，它就是一个能有效地处理空间数据和常规数据的数据库管理系统。 根据空间数据的存储位置和管理方式的不同，空间数据库管理系统可以分成集 成结构和混合结构两种。混合结构将常规数据存储在关系数据库中，空间数据存储 在文件系统中，而集成结构则将空间数据和常规数据都存储在数据库中。 采用混合型空间数据库的例子有m a p l n f op r o f e s s i o n a l 。由于混合型空间数据库 管理系统将空间数据和常规数据分开存储和管理，使得空间数据管理麻烦、操作效 率低下、一致性维护困难、网络应用无法拓展，同时它也不利于c s 结构模式下程 序的实现。 相反，由于集成结构的空间数据库管理系统在数据类型、查询处理及索引结构 等方面都进行扩展，使d b m s 能够对空间数据和常规数据进行一致高效地管理。因 而，很多数据库厂商和科研机构都实现了集成结构的空间数据库管理系统。集成型 空间数据库管理系统的商业产品包括：i n f o r m i x 的s p a t i a ld a t a b l a d e s 、o r a c l e 通用服 务器( u n i v e r s a ls e r v e r ) 的s p a t i a ld a t ac a r t r i d g e 和e s r i 的空问数据库引擎( s p a t i a l d a t ae n g i n e ，s d e ) 。其研究原型包括p o s t g r e s 的s p a t i a ld a t a b l a d e s t 甜、p r e d a t o r 、 p a r a d i s e 3 】。这些系统均提供空间数据( 如点、线、多边形) 的管理和操作( 如求交， 求距离) 的功能。并对s q l 语言进行扩充，实现了s q l 层次的空间查询1 4 5 】。这些 系统提供的性能增强包括空间索引、空间存取方法、空间范围查询和多种空间连接 算法。 华中科技大学硕士学位论文 = ；_ _ l ；_ e _ _ _ e _ j 目_ 目i i _ _ _ i _ _ _ _ _ l _ _ _ 目_ _ _ _ 目_ = j j j = = 1 2 2 拓扑关系童询研究概况 拓扑关系的相关研究在空间数据库管理系统和地理信息系统中进行。其目的是 捕获拓扑关系的语义，映射自然语言谓词到几何地理结构，并进行推理和评估。本 节将首先介绍拓扑关系的定义模型，然后介绍拓扑关系查询的具体实现方法。 1 2 2 1拓扑定义模型 当前，关于拓扑定义模型的研究主要分为两大类，一类为基于九交模型【6 - 8 1 ，另 一类为基于r c c 模型【9 i 。 1 九交模型 九交模型的根本思想是运用点集和点集之间的关系来描述两个空间对象之间 的拓扑关系，并用一个称为九交矩阵( n i n e i n t e r s e c t i o nm a t r i x ，9 1 m ) 的矩阵来记录 空间对象的内部( i m e r i o r ) 、边界( b o u n d a r y ) 和外部( e x t e r i o r ) 之间交集的维数， 从而表示相应的拓扑信息。此模型描述简单，容易实现。由于o p e n g i s 标准确认此 模型为标准模型。因此，d m s d b 将应用此模型作为拓扑关系数学定义模型。 2 r c c 模型 r c c 模型是一套推理模型。在此模型中，c u i 等人构造了一棵推理树，利用l i s p 语言实现了由上自下的推理过程，最终给出推理结果两个空间对象之间的拓扑 关系。此模型描述的拓扑关系提供给空间分析的信息比较多，但实现的难度比较大， 运算的代价也高。 1 2 2 2拓扑关系查询的实现 基于上面的拓扑描述模型，研究者大多数是采用下面两种方法来实现拓扑查 询。 1 两阶段式查询 此类方法采用过滤一求精的两段式方法来进行查询，实现拓扑查询。由于空间 拓扑计算的代价巨大，为了优化查询代价，此类方法核i i , 是在过滤的阶段尽量过滤 掉无关的数据。以减少最后用于求精的数据集的容量，从而减小拓扑关系查询的计 华中科技大学硕士学位论文 算代价。 文献f l o 】提出的方法是此类方法的代表。d i m i t r i sp a p a d i a s 等人在文章中采用r 树来加速过滤阶段的查询速度。由于r 树检索的是空间对象的最小边界矩形 ( m i n i m u mb o u n d i n gr e c t a n g l e ，m b r ) ，作者在文章中总结了1 6 9 种m b r 的拓扑 关系，并且找出实际空间对象之间的拓扑关系和代表它们的m b r 的拓扑关系之间 的关系。从而此方法将一次拓扑关系查询分解成过滤阶段( 查询代表空间对象的 m b r 的拓扑关系) 和求精阶段( 查询实际空间对象的拓扑关系) 的两段式的查询。 2 一阶段式查询 有一些研究者试图采用一段式方法解决拓扑查询的问题。其核心思想是在录入 所有的空间数据以后计算所有空间的拓扑关系，用种特殊的数据结构来储存这些 关系，当迸彳亍拓扑查询时，直接对这种数据结构操作，从中获取拓扑信息。 文献【l l 】中给出方法比较有实用价值。b o w o nk i l n 等在文中给出的2 d + 串应该 算是一种2 d 叫1 2 - 1 卸的变种结构，但和2 d 串和它的其它一些变种不同的是，2 d + 串在计算并存储空间对象之间方位信息以后，还将计算并存储那些m b r 相交的空 间对象拓扑关系。因此2 d + 串除了可以提供空间对象方位关系以外还可以提供拓扑 信息。而在查询拓扑关系或者方位关系时，通过一个阶段式查询就可以完成，查询 效率较高。因此，2 d + 串具有较高的实用价值。 一阶段式拓扑关系查询方法由于预先存储了拓扑信息，因此在进行查询阶段， 它代价上要小于两阶段式拓扑关系查询方法。不过很明显的是，一阶段式拓扑关系 查询方法比较适用于静态空间数据集，无法很好的支持对动态空间数据集。而两阶 段式拓扑关系查询方法却同时支持动态和静态数据集。 1 2 3 方位关系查询研究概况 方位关系的相关研究在空间数据库管理系统和地理信息系统中进行，学者们对 二维空间方位关系的模型已进行了许多研究，并且取得了一些结果。这些研究目的 是捕获方向关系的语义，映射自然语言谓词到几何地理结构，并进行推理和评估。 本节将首先介绍国内外关于方位关系的定义模型的研究概况，然后介绍一下方位关 4 华中科技大学硕士学位论文 jl ；_ ：目目_ 目_ _ _ _ l 目_ _ 目_ 目_ _ l 目_ _ _ _ 目l _ _ _ ；_ l _ l _ i j j 。一 系查询的具体实现方法。 1 2 3 1方位关系定义模型 国际上对方位关系的相关研究集中在点模型和最小边界矩形模型上。 1 点模型 基于点有两种模型：锥形法、投影法。这两个模型都是细分参考点的周围空间 为四个不相交的相等的区域。投影法的区域水平分割如图1 1 所示，锥形法的区域 旋转了4 5 度如图1 2 所示。对每一个区域，赋予东北、东南、西北、西南( 如图 1 1 投影法所示) 和东、南、西和北( 如图1 - 2 锥形法所示) 。对子区域进行多次细 分( 如b 区域， c 区域等) 可以得到更精确的方向表示。 n wn e s w s e 图1 1 投影法图i 2 锥形法 将参考点换成参考面的话，投影法的点模型就可以转化为相应的“面”模型， 它将细分参考面的周围空间为九个不相交的区域。命名为e a s t 、w e s t 、s o u t h 、n o r t h 、 n o r t h e a s t 、n o r t h w e s t 、s o u t h e a s t 、s o u t h w e s t 和s a m e 。 2 最小边界矩形( m b r ) 模型 图1 3 m b r 模型 e 莎j 华中科技大学硕士学位论文 最小边界矩形( m b r ) 是方向关系模型的基本方法，如图1 3 所示。这种方向 关系是按照a l l e n 的二维区间关系描述的。该模型可以区分1 6 9 种两个最小边界矩 形间所有可能的方向关系，g o y a l 等经过研究给出了所有可能的组合【l “。最小边界 矩形完全包含了一个对象，当最小边界矩形相交时。可能导致处理时的不精确。同 样，最小边界矩形表示在推理方面有弱的计算推理能力，如方向关系的组合：“东的 北面”概念应用到分离( d i s j o i n t ) 和相交( o v e r l a p ) 的时候。 同时因为方位关系还有一定的不确定性，因此近来有些学者把模糊( f u z z y ) 的 概念引入到方位关系的描述上来。比如在文献【1 7 】中，m a r i ac o b b 等人提出，应该 把空间对象的面积( 体积) 和它们之间的距离作为方位关系的一个考虑因素。这样 一来，方位关系将更加符合人类的语意。 1 2 3 2方位关系童询的实现 基于以上的方位关系描述，在空间数据库中获取空间对象之间方位关系的方法 类似于拓扑关系也大致分为两类，两阶段式查询和阶段式查询。 1 两阶段式查询 这类方法同样采用过滤一求精两段查询来获取空间对象之间的方位关系。类似 于拓扑查询，为了减少查询过程中的计算代价，此类方法的核心思想也是要在过滤 阶段尽量减少求精阶段时候的备选对象的数目。 文献【1 8 j 提出方法是此类方法的代表。d i m i t r i sp a p a d i a s 等人在文章中提出用r 树加速过滤的过程，用最小边界矩形之间的关系代表真实空间对象之间的方位关系。 应用最小边界矩形模型，对备选数据集进行过滤。从而得到一个求精的数据集。然 后再利用上述的方位关系模型对数据进行最后的求精，得到方位关系查询的最终结 果。 2 一阶段式查询 由于求精的代价比较高，两段式的查询效率受到一定的限制。因此，许多研究 者也考虑用一段式查询来解决方位关系查询问题。 2 d 串以及它的各种变种就是这类方法的代表。s k c h a n g 提出的2 d 串描述图 片中空间对象之间的方位关系。2 d 串由u 串和v 串组成，它们分别描述x 轴和y 6 华中科技大学硕士学位论文 轴上空间数据库中空间对象之间的一维拓扑关系，即按照a l l e n 描述的一维区间关 系1 1 9 1 。从而，u 串和v 串一同表达了空间数据库中空间对象之间的在二维面上的方 位关系。 除了可以在空间数据库中处理方位关系查询以外，2 d 串以及它的变种还在图像 识别方面有应用价值。 类似的，一阶段式方位关系查询方法比较适用静态空间数据集，对动态空间数 据集支持不佳。两阶段式方位关系查询方法虽然能够同时支持动静态数据集，但是 查询效率比起一阶段式查询方法较低。 1 2 4 时空数据库管理系统研究 时空数据库管理系统是包括时间和空间要素在内的数据库管理系统，时空数据 库是在空间数据库的基础上增加时间要素而构成的三维( 无高度维) 或四维数据库。 时间维的加入大大丰富了数据库的内容。它一方面增加了数据库管理的复杂性。另 一方面，海量的数据为空间和时间分析提供了极其广阔的舞台。时空数据库管理系 统和时间地理信息系统对所有与地理信息有关的领域有广泛的应用前景。特别是对 经常性变化的空间信息的管理具有重要的意义。可以说，时空数据库管理系统是空 间数据库管理系统未来的发展方向，具有光明的前景。 时空数据库管理系统在8 0 年代末期开始为人们所重视。自l a n g r a n 和c h r i s m a n 于1 9 8 8 年提出时间地理信息系统( t e m p o r a lg i s ，t g i s ) 的概念以来，时空数据库 管理系统得到了广泛的研究。w o r b o y s 和p e u q u e t 等人提出并讨论了时间数据库模 型 2 0 - 2 1 l 。f r a n k 等人和a 1 t a h a 等人在时间和空间推理方面展开了研究 2 2 2 4 1 。r a p e r 等人设计了时空数据库查询语言口”。 当前，时空数据库管理系统的相关研究重点主要在五个方面。 1 时空数据库模型：如何设计并建立一个有效的数据库结构来存储时空数据。 2 时空分析和推理：即如何根据数据库中的大量的时间序列数据和空间数据进 行包括时间推理和空间推理在内的数据分析。 3 时空数据库管理系统：目前主要研究的是时空数据库查询语言，真正数据库 管理系统层次的研究仍很少见。 华中科技大学项士学位论文 4 时空数据的可视化研究：着重探讨不同时间数据的显示、制图和符号化等问 题。在上述几个方向中，有关时空数据库模型的研究比较深入。 5 时空数据检索：探讨如何加速时空数据的检索过程。 1 3 本裸墨主要研究工作 作为空间分析的基础，拓扑关系查询和方位关系查询已经成为空间数据库必需 提供的基本功能。本课题作为d ms d b 的一个子系统，目的就是研究拓扑关系查 询和方位关系查询，并且在自主版权的国产数据库管理系统达梦t m 的基础上扩展并 实现这些功能。为此，本课题需要开展以下这些研究工作。 1 首先对d ms d b 的拓扑关系查询和方位关系查询进行需求分析，明确本课 题的目标。 2 对拓扑关系和方位关系定义模型进行分析研究，参考o p e n g i s 标准选用适 合d ms d b 的拓扑关系和方位关系定义模型。 3 。在分析拓扑关系定义模型的基础上实现d ms d b 的拓扑运算算法。 4 因为一阶段式查询具有较高的搜索性能，因此将研究并实现一个统一的结构 来实现保存空间拓扑关系和方位关系的信息实现d ms d b 一阶段式的拓扑关系 查询和方位关系查询。 5 为了支持高级空间分析和高级空间推理，还将对d ms d b 的空间拓扑关系 推理和空闯方位关系推理进行研究并实现。 华中科技大学硕士学位论文 2 系统设计 拓扑关系查询和方位关系查询是安全空间数据库管理系统d m s d b 的一个子 系统，它和d ms d b 及其子系统有着精密的联系。本章首先在对d m 3 进行分析的 一 基础上，对d m s d b 进行了系统分析。随后介绍了拓扑关系查询和方位关系查询 在d m s d b 中的地位，然后进行了拓扑关系查询和方位关系查询的需求分析，最 后在此基础上给出了完整d m s d b 的拓扑关系查询和方位关系查询的设计方案。 2 1 达梦3 系统分析 达梦3 ( d m 3 ) 是一个层次一关系型的数据库管理系统产品，它充分吸收了层次 一关系模型的优点。系统提供的模式定义语言是关系型的，与s q l 语言保持一致， 而存储模型是层次一关系型的。在g i s 应用领域，上层关系存储每幅地图的公共常 规信息及地图之间的层次和邻接关系，下层关系每类地物的常规信息及图像信息( 地 理坐标) 。这种模型具有如下三种特点。 1 可以方便的对地图数据建立数据模型，以简单的方式表达地理信息中的复杂 对象的层次关系。 2 常规数据、空间数据在事务处理、并发控制、完整性、安全性及恢复机制等 方面提供一体化的支持。 3 含并扩充的标准s q l ，以支持常规数据和空间数据的一体化存储。 针对地理信息方面的应用，d m 3 对标准的关系型数据库管理系统进行了扩充， 已经具有一些空间数据库的特性，能够管理和处理空间数据。然而d m 3 在很多方 面还存在不足，因此d m _ s d b 将对d m 3 按空间数据库的要求和体系结构进行全方 位的扩充。 2 1 1 达梦3 的空间数据类型 d m 3 的查询语言对标准s q l 进行了扩充，增加了一些新的数据类型来描述空 间数据，支持空间数据的新类型如下。 9 华中科技大学硕士学位论文 1 p i c t u r e 类型 p i c t u r e 为下层表指针类型，它指定了空间数据库中在下层表存放的首块号。 下层表未建立时为n u l l ，非空值由系统置入。 2 v a r d o t 类型 变长点集类型，描述线状地物、面状地物的点集坐标的有序集合。 3 s o r 丁类型 用来在下层关系中定义相应地物的编码，它决定了一种地物的类型和形状。 4 z o n e 类型 地物编码类型。 5 a d j o i n 类型 邻接图类型，描述了多幅地图的邻接位置关系，即多幅地图在东、南、西、北、 东南、东北、西南、西北八个方向的邻接图的图号集合。 6 s u bm a p 类型 下属图表类型，描述了两种不同比例尺地图的对应位置关系。 7 n a m e x y 类型 地名坐标类型，描述地图中地地名及其在地图中应标明地位置。 2 1 2 达梦3 的空问信息检索 为了支持对空间数据地检索，d m 3 在客户端提供了空间索引机制和空间检索函 数接口。在服务器端含有空间信息地下层关系，如“公路”关系，公路地图形信息 存于“图形”属性( v a r d o t ) ，此关系中v a r d o t 类型地属性实际上只存放了 个指针，指向一个专门存放空间线状、面状地物地矢量信息的内部存贮区，此区域 对用户透明。在客户端，提供动态链接库s p a p i d l l ，应用程序调用它访问“公路” 关系地图形属性。并对其建立网格索引，再进行基于网格索引地检索。空间检索支 持以一给定点、线、面为条件，查找与之有交集的( o v e r l a p ) 地物。 2 1 3 达梦3 管理空闫数据的不足 d m 3 虽然具备了空问数据库管理系统s d b m s 的一些特征，但在空间数据的存 0 华中科技大学硕士学位论文 储、表示和查询处理等方面的性能还存在一些不足之处，主要表现如下a 1 现有空间查询语言的功能不够完整 d m 3 在查询界面的人性化、个性化及支持空间关系方面支持不够，不能直观表 达用户的空间查询和空间表达的语义，即可视化查询的问题。 2 对拓扑检索、查询支持较弱 d m 3 在分层查询、分层要素查询，以及按拓扑关系的检索、查询等方面都支持 不够。 2 2 安全空间数据库蕾理系统d m s d l 3 分析 拓扑关系查询和方位关系查询是安全空间数据库管理系统d m s d b 的一个子 系统，它和d m s d b 及其子系统有着精密的联系。本节将在分析d m s d b 的基础 上，说明d m s d b 及其子系统对拓扑关系查询和方位关系查询的设计要求。 2 2 1d m _ s d b 设计目标 从已有的s d b 实现技术来看，结合d ms d b 的项目要求，d ms d b 在实现方 面应当满足以下三点要求。 1 有一组空间数据类型，用来表示具体的空间数据类型、复杂空间数据类型 和对这些数据的操作。 2 空间类型和操作应当是标准查询语言的一部分，对于关系数据库应当扩充 s q l 以支持空间查询和操作，其中包括拓扑关系查询和方位关系查询。 3 增强功能，如空间查询所需的空间索引、非空间查询、时空检索等。 此外，为支持空间应用，系统还必须解决的问题有：空间分类、数据模型、查 询语言、查询处理、空间数据组织以及空间索引。 2 2 2 空间数据特征对拓扑关系童询和方位关系查询的要求 为了实现d m _ s d b 的拓扑关系查询和方位关系查询，有必要对空间数据的特 征进行分析以便于进行系统分析和设计。空间数据具有以下特点。 华中科技大学硕士学位论文 = = = = e = j = 4 _ _ _ l ；# _ ；j e = _ 口；_ e = = _ _ | 目l = _ l e 目目_ 目_ - b i _ _ _ p i = _ 1 度量特点：距离、长度、面积、周长、体积、维。 2 几何特性：点、直线、曲线、面和体。所有这些特征占有一定的空间范围， 他们在组成方面具有一定的关系，这些简单的几何特征可以组成复杂的空间特征： 从空间角度看，几何特征通过其边界将空间划分为特征的内部、边界和外部。 3 拓扑特性：邻接、关联、包含等。 4 方位特性：东、南、西、北等。 5 分布特性；空间范围内的分布不规则。 6 时间特性：空间数据和时间相关。 7 数据量：空间数据具有海量性。 由此可见，拓扑关系查询和方位关系查询的目的是分析比较空间数据特性，在 d i hs d b 的实现过程中具有重要地位。 2 2 3 d m _ s d b 技术方案对拓扑关系查询和方位关系查询的要求 综合前面所有的分析情况，d m s d b 在总体上依托d m 3 成熟的技术方案和体 系结构，通过对d m 3 进行功能扩展来实现d m s d b 。以下从五个方面论述实现 d m _ s d b 必须扩展的内容的技术途径，以及其对拓扑关系查询和方位关系查询的要 求。 2 2 3 1 d m _ s d b 的扩晨方式 实现空间数据库所必须扩展数据库的内容，其扩充方式与具体的实现方式无 关。以下论证基于d m 3 体系结构的组件化扩展方式。对于d ms d b 的实现在体系 结构方面我们采用集成方式。该方案通过与后台数据库管理系统d m 3 紧密集成的 方式实现对空间数据的支持功能。具体来说，就是对d m 3 现有的部分模块进行扩 展，使其支持空间数据的定义、存储、查询、检索、修改等。同时为了便于用户的 开发，系统应当提供各种空间数据的定义、存取、分析等相关的组件接口，对于客 户端应当提供客户组件接口。集成方案结构如图2 1 所示。 该方案具有以下三个特点。 1 系统采用与d m 3 方案紧密集成的方式进行功能扩展。对于常规查询，客户 华中科技大学硕士学位论文 端可以通过o d b c 、j d b c 访问数据库，而对于涉及到空间查询的情况，可以通过 组件接口访问数据库。 2 与三层结构方式不一样，系统直接在底层扩充s q l 解释器，既可以直接处 理标准s q l 语句又能够处理为空间数据类型扩充的s q l 语句。 3 通过对消息处理模块的扩充，使得系统能够直接对空间数据进行操纵，并 且可以将空间索引建立于服务器端。 图2 i d m _ s d b 集成结构 由d ms d b 的体系结构可以看出，拓扑关系查询和方位关系查询需要在服务 器端实现，通过通信接口和s q l 语句同客户端交互。当客户端有拓扑关系查询和方 位关系套询时，服务器端的查询处理部分需要调用拓扑关系查询和方位关系查询的 功能，找到结果返回客户端。 2 2 3 2 d m _ s d b 的数据扩晨 作为一个空间数据库管理系统，d ms d b 在数据模型方面应当提供两种类型的 数据模型：抽象的空间数据类型( a d t ) 和数据库的实现模型，如图2 2 所示。 空间数据类型的扩充可以从数据库的核心层或从应用表示层两个层面进行实 现。不论从哪一个角度去实现空间数据，在逻辑上系统应当支持的基本空间数据类 型有：p o i n t 、l i n e s t r i n g 、p o l y g o n 。由于各个数据类型之间存在的共性，因此又抽 象了两种基本数据类型g e o m e t r y 和g e o m e t r yc o l l e c t i o n 。此外，系统还应当支持用 户自定义的数据类型的扩展。对于所有扩展的数据类型，数据库管理系统必须解决 华中科技大学项士学位论文 相应类型的数据结构和存取机制。 图2 2 空间数据类型关系 作为空间对象都具有的特性，拓扑关系和方位关系是抽象于g e o m e t r y 对象之上 的，也就是说，拓扑关系和方位关系是两个或多个g e o m e t r y 之间的关系，拓扑关系 查询和方位关系查询也是对g e o m e t r y 的查询。 2 2 33 d m s d b 查询扩晨 空间查询是在空间数据类型扩充的基础上，为了便于用户实现对空间数据的定 义操纵而进行的扩展。因为传统s q l 缺乏对空间数据存取的有效支持，不能处理象 空间数据这样复杂的数据类型，因而，在查询语言扩充方面，系统要提供扩展的s q l ， 这种扩展可基于o g c 的o p e n g i s 对s q l 扩展或s q l 3 。其中包括对拓扑关系查询 和方位关系查询的s q l 扩展。 2 2 3 4 d m _ s d b 查询处理 空间查询处理的目的是保证空间查询有效性，对于空间查询处理的要求是扩展 相关的空间查询谓词，其中拓扑关系查询和方位关系查询需要扩展的谓词如下。 1 拓扑 w i t h i n ；e q u a l ；d i s j o i n t ；i n t e r s e c t s ；t o u c h e s ；o v e r l a p ；c r o s s ；c o n t a i n s ； r e l a t e 。 华中科技大学硕士学位论文 2 方位 e a s t ：w e s t ：n o r t h ：s o u t h ：n o r t h e a s t ；n o r t h w e s t ：s o u t h e a s t ：s o u t h w e s t ：s a m e 。 2 2 3 5d ms d b 素引机翻 、 1 空间索引 空间索引是进行高效空间查询的基础，d m s d b 在空间索引机制方面必须同时 支持标量关系的索引以及空间索引。 标量关系索引可基于d m 3 现有的舻树索引技术思想。 对于空间索引结构，可利用改进后的r 树结构。可以参考的r 树类结构有r + 树、r 树和h i l b c r tr 树。在这三种结构中，其中h i l b e r tr 综合性能最好。我们决 定实现h i l b e r t r 树。该结构支持查询谓词应包括相等、包含、重叠和最近邻等，支 持的数据类型应包括点和多边形数据。利用通用索引结构g i s t 可以实现多种树结 构，其中就包括r 树结构。故d m _ s d b 可以首先实现g i s t ，进而在此基础上再实 现h i l b e r t r 树结构。 而在g i s t 构造过程和查询过程中都需要比较空间对象之间的拓扑关系。因此， 我们需要对空间索引模块提供拓扑关系运算的接口。 2 时态索引 d ms d b 在设计目标里面明确提出了支持时态的特性，因此必须提供时态检索 机制来加速时空数据的检索。经过研究，我们提出时态检索结构t r + 树伫6 1 ，来 加速对时空数据的检索。t r + 树认为时空对象是分布在图所示的时间平面上的，这 样傲可以避免文献以及s r 树出现的索引节点重叠的问题。而最终影响检索性能主 要原因就是重叠问题，因此t r + 树可以实现高效的检索。 图2 5 所示的就是一个具体的t r + 树的例子。该例中有如下几个时态对象 e l ( 0 ，3 ) 、e 2 ( 1 ，2 ) 、e 3 ( 1 ，3 ) 、e 4 ( 3 ，6 ) 、e 5 ( 4 ，7 ) 、e 6 ( 5 ，9 ) 、e 7 ( 6 ，9 ) 和e 8 ( 7 ，1 0 ) 。其中图2 3 表示般意义上的一维时间对象圈，图2 4 表示的是二维时态对象图。在图2 4 中， 每个对象表示为图中的一个点，其横坐标是对象事件的开始时间，纵坐标是对象事 件的结束时间。坐标轴的最远端都表示当前的系统时间。在此例中，l o 就是当前系 统的时间，也就是时态对象的最大时间。 华中科技大学硕士学位论文 图2 3 一维对象图图2 4 二维对象图 图2 5 t r 一讨 图2 5 表示的是一个根据图2 4 的时态对象构建的t r 树。为了方便显示，图 2 4 中的索引块被扩大了。但是，具体实践中，这些索引块可以最小化。比如a 应 该表示为r e c t ( o ，2 ，i ，3 ) 的索引区间。 同样的，在t r + 树的搜索和维护算法中，也需要拓扑运算。因此，需要对其提 供接口。 2 3 攘扑关系和方位关系童询系统分析 由上面对d m _ s d b 的分析，我们可以得出以下结论，拓扑关系查询和方位关 系查询都对抽象对象g e o m e t r y 进行操作，参照o p e n g i s 标准，结合d l v i _ s d b 查询 处理的要求，两种查询的需求大致如下。 6 华中科技大学硕士学位论文 e _ ；_ 目_ i ；l 目_ _ _ _ l _ _ _ 目目i _ 目_ _ i 。2 。4 2 3 1 拓扑关系需求分析 拓扑关系描述的是空间对象之间的关系，参照o p e n g i s 标准，在d m s d b 中 需要实现的拓扑关系如下。 w i t h i n ：e q u a l ；d i s j o i m ：i n t e r s e c t s ：t o u c h e s o v e r l a p ：c r o s s ；c o n t a i n s 。 其具体定义将在第三章详细描述。 拓扑关系查询是空间分析的基础，它必需向d m s d b 的其它部分提供功能， 其需要的以供测试两个空间对象拓扑关系的函数如下。 b o o l e a l le q u a l ( g e o m e t r yt h i s g e o m e t r y g e o m e t r ya i l o t h e r g e o m e t r y ) 测试此空 间对象和另一个空间对象是不是“空间上相同”； b o o l e a nd i s j o i n t ( g e o m e t r yt h i s g e o m e t r y , g e o m e t r ya n o t h e r g e o m e t r y ) 测试此 空间对象是不是和另一个空间对象“空间上相离”； b o o l e a ni n t e r s e c t ( g e o m e t r yt h i s g e o m e t r y , g e o m e t r y a n o t h e r g e o m e t r y ) 测试 此空间对象是不是和另一个空间对象“空间上相交”； b o o l e a nt o u c h e s ( g e o m e t r yt h i s g e o m e u y , o e o m e t r ya n o t h e r g e o m e t r y ) 测试此 空间对象是不是和另一个空间对象“空间上切”： b o o l e a nc r o s s ( g e o m e t r yt h i s g e o m e t r y , g e o m e t r ya n o t h e r o e o m c t r y ) 测试此空 间对象是不是“空间上横穿”另一个空间对象： b o o l e a nw i t h i n ( g e o m e t r yt h i s g e o m e t r y , g e o m e t r ya n o t h e r g e o m e t r y ) 测试此 空间对象是不是“空间上包含于”另一个空间对象里： b o o l e a nc o n t a i n s ( g e o m e t r yt h i s g e o m e t r y , g e o m e t r y a n o t h e r g e o m e t r y ) 测试 此空间对象是不是“空间上包含”另一个空问对象： b o o l e a no v e r l a p ( g e o m e t r yt h i s g e o m e t r y , g e o m e t r ya n o t h e r g e o m e t r y ) 测试此 空间对象是不是和另一个空间对象“空间上交迭”。 还有一组函数直接由查询处理器调用，完成在整个空间数据库中数据集搜索， 找到符合特定拓扑关系的数据的功能。如下所示。 g e o m e t r y s e tt o p o q u e r y ( o e o m e t