（计算机应用技术专业论文）时空数据库瞬时查询和时空范围查询研究.pdf

哈尔滨理t 大学t 学硕士学位论文 时空数据库瞬时查询和时空范围查询研究 摘要 时空数据库是在空间数据库和时态数据库的基础上发展而来的。经过二 十年的发展，在时空数据模型、时空查询优化与索引和时空本体论等方面取 得了许多成果。现实世界中的许多实体都具有空间特性和时态特性，需要数 据库管理系统提供有效的时空数据管理。 时空数据库可以处理传统关系数据库难以处理的带有空间和时间特性的 数据，它相对于传统关系数据库的一个突出特点就是数据量大，数据更新频 繁。因此必须采取有效地查询和索引来提高查询效率。目前，索引方面的研 究相对比较成熟，而对于时空查询方面的研究比较少，本文旨在研究时空查 询。 时空查询在时空数据库的研究中是至关重要的。本文对已存在的索引结 构和查询方法进行了研究总结和比较，采用b u d d y 树进行瞬时查询和时空 范围查询的研究。同时，充分考虑了现实世界的不确定性，将不确定性引入 索引和查询中，使得时空查询更具准确性。 本文首先针对时空数据库和时空不确定性进行了分析说明，为下面进一 步的研究奠定了理论基础。然后提出了一种新的基于移动对象位置信息的索 引结构，该索引结构在b u d d y 树的结构上进行改进，引入了一个辅助索引 表，大大提高了索引的更新效率。同时在该索引结构的基础上进行了瞬时查 询和时空范围查询的研究，结合查询窗口扩展策略提出查询算法，性能评价 表明与现有技术相比较该算法提高了系统的查询性能。最后，基于提出的索 引结构引入时空不确定性的概念，对基于时空不确定性的时空范围查询进行 了研究，提出了时空概率范围查询算法。通过实验验证该算法降低了查询不 确定性和查询成本。本课题的研究对于时空数据库查询技术的发展具有重要 意义。 关键词时空数据库；索引结构；瞬时查询；时空范围查询；时空不确定性 哈尔滨理工大学t 学硕士学位论文 r e s e a r c ho nt i m es l i c eq u e r ya n d s p a t i o - t e m p o r a l r a n g eq u e r y i ns p a t i o - - t e m p o r a ld a t a b a s e s a b s t r a c t t h ed e v e l o p m e n to fs p a t i o - t e m p o r a ld a t a b a s e si sb a s e do nt h es p a t i a l d a t a b a s e sa n dt e m p o r a ld a t a b a s e s t h e r ea l em a n yr e s e a r c h e so nt h es p a t i o - t e m p o r a lm o d e l 、s p a t i o - t e m p o r a lq u e r yo p t i m i z a t i o na n ds p a t i o t e m p o r a l o n t o l o g y l o t so fe n t i t i e si nt h er e a lw o r l dh a v es p a t i a lp r o p e r t i e sa n dt e m p o r a l p r o p e r t i e s t h ed a t a b a s em a n a g e m e n tc a ni m p r o v et h ec a p a b i l i t yo fm a n a g i n g t h es p a t i o - t e m p o r a ld a t a s p a t i o - t e m p o r a ld a t a b a s ec a nd e a lw i t ht h ed a t aw h i c hh a st h es p a t i a la n d t e m p o r a lp r o p e r t i e s t h ed a t ai ns p a t i o t e m p o r a ld a t a b a s e sn e e db eu p d a t e d f r e q u e n t l y s ot h eq u e r y i n gm e t h o da n di n d e xs t r u c t u r es h o u l db eu s e di no r d e r t oi m p r o v et h ee f f i c i e n c yo ft h eq u e r y a tp r e s e n t ，t h er e s e a r c ho nt h ei n d e xi s m o r et h a nq u e r y s ot h ee m p h a s i so ft h i sd i s s e r t a t i o ni ss p a t i o t e m p o r a lq u e r y t h es p a t i o t e m p o r a lq u e r yi sc r u c i a l l yi m p o r t a n ti nt h er e s e a r c hf o rt h e s p a t i o t e m p o r a ld a t a b a s e t h i sd i s s e r t a t i o nd o e ss o m er e s e a r c ha n dc o m p a r i s o n o nt h ee x i s t i n gi n d e x i n ga n dq u e r y i n gm e t h o d ，a n du s e st h eb u d d y - t r e et h a ti s s u i t a b l ef o rt h er e s e a r c ho ft i m es l i c ea n ds p a t i o t e m p o r a lr a n g eq u e r y a tt h e s a m et i m e ，t h i sd i s s e r t a t i o nt a k e st h eu n c e r t a i n t yi n t oa c c o u n ta n dt r e a t st h e u n c e r t a i n t ya sa ni m p o r t a n tf a c t o ri nt h ei n d e xa n dq u e r y t h i sm e t h o dm a k e s t h es p a t i o - t e m p o r a lq u e r ya c c u r a t e t h i sd i s s e r t a t i o nf i r s t l yd i s c u s s e st h es p a t i o - t e m p o r a ld a t a b a s ea n ds p a t i o - t e m p o r a lu n c e r t a i n t y i ti st h et h e o r e t i c a lb a s i so ff u r t h e rr e s e a r c h a n dt h e nt h i s d i s s e r t a t i o np r o p o s e san e wi n d e x i n gs t r u c t u r eb a s e do nt h em o v i n go b j e c t s t h i si n d e x i n gs t r u c t u r ei si m p r o v e df r o mb u d d y t r e e s i ti n t r o d u c e sa na u x i l i a r y i n d e xs t r u c t u r e s s oi tc a ni m p r o v et h eu p d a t i n ge f f i c i e n c y a c c o r d i n gt ot h e i n d e x i n gs t r u c t u r e ，t h et i m es l i c eq u e r ya l g o r i t h ma n ds p a t i o t e m p o r a lr a n g e q u e r ya l g o r i t h ma t ep r o p o s e d ，a n dt h ep e r f o r m a n c ee v a l u a t i o ni sg i v e n t h e e x p e r i m e n ts h o w st h a tt h ep e r f o r m a n c e o ft h es p a t i o 。t e m p o r a lq u e r yb a s e do n t h ei n d e x i n gs t r u c t u r ei si m p r o v e d f i n a l l y , t h i sd i s s e r t a t i o np r o p o s e s t h es p a t i o - t e m p o r a lp r o b a b i l i t yr a n g eq u e r ya l g o r i t h m t h ee x p e r i m e n ts h o w st h a t t h e a l g o r i t h mr e d u c e st h eq u e r yu n c e r t a i n t ya n dt h ec o s to fq u e r y t h i sr e s e a r c hi s i m p o r t a n tt ot h ed e v e l o p m e n to fs p a t i o t e m p o r a ld a t a b a s eq u e r yt e c h n o l o g y k e y w o r d ss p a t i o t e m p o r a ld a t a b a s e s ，i n d e x s t r u c t u r e ，t i m es l i c eq u e r y ， s p a t i o t e m p o r a lr a n g eq u e r y ，s p a t i o t e m p o r a lu n c e r t a i n t y n i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文时空数据库瞬时查询和时空 范围查询研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独 立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他 人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已 在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：刊孤 日期：拗哆年午月分日 哈尔滨理工大学硕士学位论文使用授权书 时空数据库瞬时查询和时空范围查询研究系本人在哈尔滨理工大学攻 读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔 滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了 解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部 门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可 以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内 容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密a 。 ( 请在以上相应方框内打4 ) 作者签名：到绢日期i 砌夕年4 - 月汐日 导师签名：删 日期： 哆年 乒月扩e t 哈尔滨理工大学工学硕士学位论文 1 1 研究背景和意义 1 。1 1 研究背景 第1 章绪论 近年来，随着无线通信技术的高速发展，时空数据库越来越多地应用到 全球变化( 如气候、陆地的变化) 、交通运输( 如交通监控、智能传输系统) 、社 会( 如人口统计) 及多媒体系统等多个方面。这些应用的共同点是：要求能够比 较真实的记录并处理实体的时态信息、空问信息、空间信息随时态的变化而 发展的信息等。这就要求面向这类应用的数据库系统除了能处理基本类型的 数据外，还必须能处理空间类型，时态类型和时空复合类型n 1 。但现有的特种 数据库或者只能处理时态对象，或者只能处理静态的数据对象，目前为止还 没有能够有效处理动态空间对象的数据库管理系统产品出现。因此，无论是 理论上还是实际应用中，人们都提出了时间和空间结合起来进行研究的要 求。 传统的空间数据库和时态数据库的研究基本上是处于独立的状态。空间 数据库的研究侧重于数据库中对象的几何模型和空间查询方面的支持晗1 ；时态 数据库的研究主要关注对于当前信息和历史信息的处理和扩展，即有效时间 和事务时间的表达。1 。正是由于两者所处理对象均具有空间和维的概念，在此 基础上，集成两个方面的研究就变得很有必要，这就是时空数据库研究的任 务和来源啪。随着“数字地球 概念的提出，对时空数据库系统的研究正成为 数据库系统研究人员和地理信息系统研究人员所共同关心的热点课题。 时空数据库作为一种现代的面向对象的高级数据库技术，它有效地组织 和管理时态地理数据、属性、空间和时间语义。其研究得益于空间数据库特 别是地理信息系统( 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 s ，g i s ) 的研究和广泛应 用。时空数据库是包括时间和空间要素在内的数据库系统，是在空间数据库 的基础上增加时间要素而构成的三维( 无高度维) 或四维数据库。与传统的数据 库相比具有动态性和全面性的特点。它包括任何历史数据，并且同样可以对 其进行更新，使数据库可以成为任何一个系统和部门的完整电子信息档案 库，其对象可以是移动的物体，但不是必须具有移动的特性。而空间数据库 哈尔滨理工大学工学硕士学位论文 一般不保存历史变化或保留若干典型时间点的全局状态快照序列，具有较弱 的时空语义建模能力，无法提供时态分析能力。时态数据库和空间数据涉及 因素比较多，实现数据模型要远比建立一个数学模型复杂。虽然已经有了一 些理论基础，也有了很多数学模型，但还没有商用的成型的直接支持时空数 据的数据库管理系统。现在多数的研究基于时空数据库某个部分的比较多， 全面研究的比较少。针对时空数据索引结构的研究比较多，有关于查询算法 研究的比较少。 近几十年来，时空数据库的研究主要几种集中在以下几个方面喳1 ：时空数 据模型、时空分析和推理、时空数据索引、时空数据查询和时空数据的可视 化研究等。本课题主要研究的是时空数据库中的查询技术，主要针对移动对 象范围查询方法进行研究。 1 1 2 研究意义 在企业级数据库的全球竞争中，由于历史原因，中国的数据库开发和应 用都同国际先进水平有很大差距。在时空数据库方面，西方国家起步较早， 但西方国家也仍旧处于起步阶段，因此时空数据库的研究潜质是很大的。在 时空数据库中对时空查询技术的研究有很高的学术起点，许多关键技术都有 待进一步的研究。研究和解决该领域的问题不仅对数据库领域有着巨大的理 论和现实意义，而且对其他相关领域也起着重要的作用。 时空数据库技术已经成为活跃的技术领域，但一直没有成型的系统原型 出现，预示着在这个领域还有很多课题亟待研究。在时空数据库的关键问题 研究中，时空数据的索引与查询占据着重要的位置。查询是数据库的基本操 作，索引结构作为辅助工具支持时空查询，所以查询的性能决定了数据库的 性能，因此研究此类查询问题具有重要的理论意义和实用价值。 1 2 时空数据库发展历程 时空数据库同时兼具时态和空间双重属性，其发展途径也可以从这两个 方向进行扩充： 第一在空间数据库中加入时态属性。这种思路是基于成熟的空间数据库 技术，如地理信息系统。在对空间数据良好支持的同时添加时态属性，从而 生成联合时空数据库。但这种思路在实施的过程中发现会事倍功半：需要添 加时态属性，就必须添加历史信息，必须支持历史的回溯。空间数据库的支 哈尔滨理工大学工学硕士学位论文 持技术就必须从数据库结构开始更改。所以时空数据库的发展应该是从非空 间数据库发展而来的。 第二在时态数据库中加入空间数据的支持。同样基于成熟的时态数据库 技术，如历史数据库。在具有时态属性的同时扩充对空间数据的支持，也可 以生成时空数据库。这种思路就避开了数据库管理系统结构的可能改变，只 需要扩充数据的类型，相对实施起来更为简单一些。 到目前为止，时空数据库理论大致经历了以下几个发展阶段： 1 将空间信息随时间变化的实体作为静态的空间对象来处理，注重空间 信息的处理，而忽略实体的空间信息和时态信息的关联。这一阶段的主要成 果是7 0 年代至8 0 年代末期的g i s 的广泛应用。 2 将实体作为动态的空间对象处理，但是对象的空间信息和时态信息在 很大程度上是相互孤立的，不是一个有机的整体。这一阶段的主要成果是 l a n g r a n 和c h r i s m a n 提出的时态地理信息系统，即将时间特性融入g i s 数据的表示和处理，在同一框架内管理时空数据，t g i s 就是时空数据库的雏 形。 3 将实体看作是随时态变化而发展变化的时空对象，把对象的时态信息 和空间信息看作是有机的整体。这一阶段的主要标志是时空数据库概念的提 出。但从9 0 年代初到现在，在时间、空间的无缝结合上还没有突破性的进 展。 迄今为止，商业软件对于时空数据的全面支持还没有出现，只是在不同 程度上支持时空数据。如i n f o r m i x 的d a t a b l a d e 模块，分别支持时间和空间数 据类型，但它没有提供任何集成化的时空数据类型；o r a c l e d b m s 提供了空间 数据选件s p a t i a lc a r t r i d g e ，它支持的空间数据类型有p o i n t ，l i n es t r i n g ， p o l y g o n ；d b 2 提供了s p a t i a le x t e n d e r 模块，它支持的空间数据类型有 p o i n t ，l i n es t r i n g ，p o l y g o n 及其多个版本类型；e s r i 提供的空间数据库引擎 s d e 也只是提供了a r c i n f o 系统本身所支持的空间数据类型，并没有从数 据库的角度提供空间数据类型的更多的支持。所有这些软件系统都没有从根 本上解决时空数据类型及相关的操作。 1 3 本课题国内外研究现状 由于时空对象的操作复杂性和数据的海量性，必须采用有效的查询算法 和索引。索引模型方面的研究相对来说已经比较成熟了，有很多学者提出了 哈尔滨理工大学工学硕士学位论文 很多的索引方法，而索引方法提出的目的就是为了提高数据检索或查询的效 率，因此时空对象的查询方法的研究是很重要的。在当前的时空查询研究 中，按照时空对象的不同应用，时空变化过程有如下几种主要情况嘲：空间位 置连续变化如公路上的汽车、属性连续变化如某城市的人口、空间位置和属 性都连续变化如移动的云层、空间离散变化如道路改线、属性离散变化如更 改地名、空间和属性都离散变化如地籍变更等。时空数据库主要处理时空移 动对象，需要注意的是，时空数据库并不一定是移动数据库，其对象可以是 移动的物体，但不是必须具有移动的特性，可以是静态的，如2 0 0 7 年某城市 的人口数量信息。因此时空数据库查询可以分为静态对象查询和移动对象查 询两种。下面分别介绍这两种查询的研究现状。 1 3 1 静态对象查询方法 传统时空数据库中静态对象的查询包括投影、选择、连接和聚集操作。 其中选择查询比较具有代表性。典型的选择查询方法有点查询口1 、范围查询、 最近邻查询等。下面分别介绍这几种查询。 1 点查询( p o i n tq u e r y ，p q ) 给定一个查询点p ，找出所有包含它的空间 对象o ，即p q ( p ) = oip e o g 9 ) ，其中o g 为对象o 的几何信息。 2 范围查询( r a n g eq u e r y ，r q ) 给定一个查询多边形p ，找出所有与之 相交的空间对象0 ，即r 0 。表 t 的关系集用一个数组集来表示，形如r ：厶l o o ，其中幻t ( 1 s 约”) 并 且兰，p r ( t r l ) - 1 ) 。r 的概率是包含在r 中的数组出现的概率，即p 仪产，仨r p r ( 0 。设 r t 为表r 的关系集，对于任意两个关系r i ，r e r t ，我们假设r l ，r 2 没有相 同的数组也就是说r l n r 2 = a 。 对于一个数组集的子集s c t 和一个关系集r ，用r a s 来表示位于r 内 和出现在s 中的数组。概率区域w 是t 的一个子集，对于每一个关系集 r 2 r t 。如果p r ( a ) = l ，那么w 包含r 内的一个数组即ir a wl = 1 。如果 p r ( a ) l ，那么w 包含0 或1 个r 内的数组即lr a wl l 。我们用形来表示 所有概率区域的集合。很明显，对于每一个不确定的表t 和关系集r t ，概率 区域的数目见式3 1 。 l 形i2 r 6 r r 譬( 足) - l1w l 胎岛碍置) o ，则w e w p i o v ) = i 。 根据移动对象的表示形式将不确定性模型分为基于移动对象位置和轨迹 两种。 对象位置点的不确定性模型：对象q 在时间t 的不确定区域表示为 w f ) ，及一个封闭的区域，表示q 的实际位置在此区域中。对象的不确定概 率密度函数由触，y ，0 来表示。 在以上的定义中，假设每一个移动对象都是一个点，不考虑他们的空间 宽度。w o l f s o n 等提出了在不确定性环境下移动对象位置更新策略嘲。我 们称为航位推测更新策略，它是基于位置更新阈值的原理。设阙值为l ，m 决定了位置的不确定度，当移动对象的实际位置和存储位置的距离超过给定 的t h 时，对象向数据库发出更新请求。航位推测策略包括三种不同的方法： 第一种是速度航位推测法。在整个过程中，m 是固定的，存储在 l u n c e r t a i n t y 中。仅对当前位置和速度进行更新；第二种是自适应航位推测 法。它采用基于代价的方法对t 1 1 进行更新，更新后的t l l 值使更新代价、偏离 代价、不确定性代价的总和最小；第三种是断路检测航位推测法。它是针对 移动对象与数据库的连接断开或者其不能产生位置更新的情况而设定的。在 上一次更新后的时间单元里，如果移动对象没有发出更新请求，则t l l 值逐渐 减小；若移动对象并未与数据库断开，则将产生新的位置、速度、阈值更新 哈尔滨理工大学工学硕士学位论文 值。 轨迹的不确定性模型：为轨迹的每节线段设置不确定性阈值吖用于平 衡移动对象和它的服务器) ，当且仅当移动对象的实际位置距期望位置的偏离 值大于或等于 移动对象通过计算机每隔2 s 接受g p s 信号，这是移动对象的 实际位置，轨迹描述出移动对象的期望位置) 。其定义为：，为一正实数，t 表示移动对象在 f l ，t 2 的运动轨迹，轨迹的不确定性模型u t r 用( t ，力表示， 其中，为不确定阈值。轨迹t 的可能运动轨迹p m c t 是任意连续函数， k ，：一r 2 ，对于任意f f l ，t 2 ，三维点( 厶懈，( 0 ，0 在时刻t 的期望位置 的不确定区域内。给定一个不确定性轨迹u 唧，厂) 和两个端点，y i ，t i ) ， l ，附l ，t + 1 ) e t ，分别以线段( 麓，弗，f i ) ，( x m ，坶l ，t i + 1 ) 上所有点为中 心，为半径的圆盘总和构成论文u r r 的不确定性体积，将其投影到x - y 平面 上，不确定性体积变成不确定性区域，可能运动轨迹变成可能运动路径。 此模型是基于空间不确定性的，若考虑时间不确定性，即由轨迹表示的 某一移动物体在y ) 位置的期望时间为t 。若该物体实际到达的时间不早于 ( 或不迟于) t - 5 ( t + 8 ) ，位置的不确定性不要求更新。 如图3 1 所示，在坐标系中表示为一系列的三维平行四边形，将时间与 空间不确定性结合起来考虑，形成了如图的时空不确定性模型。它在x ，y ， t 坐标平面上以轨迹上的点作为中心点轴长分别为，6 ，形成了一个椭圆 体。由轨迹上每个点的椭圆体所构成的立体称为不确定性体积。 轨迹 图3 1 轨迹的时空不确定性模型 f i g 3 - lu n c e r t a i n t ym o d e lo ft r a j e c t o r y 3 4 不确定性时空查询 不确定性时空查询可定义为：允许被查询对像在时态属性、空间属性以 哈尔滨理工大学工学硕士学位论文 及时态和空间属性上存在不确定性的时空查询。对于范围查询来说，还应该 允许查询范围本身在时间、空间或者时空上存在一定的不确定性。 时态查询方面，一般将查询看成时态空间中的一个矩形区域来处理陆。 这些研究主要是针对时间段之间的几何关系，根据时间段之间的包含和相交 关系将时态查询进行分类。 时空查询方面，p r a m e z 等人嘲1 将时空查询分为时态选择查询，时空聚 集查询、时空投影查询以及时空状态演化查询。w o l f s o n 等人嘲指出有3 种不同类型的时空查询方法，分别为瞬时查询，返回当前数据状态；连续查 询，查询一段时间内的数据状态；持续查询，查询将在未来一段时间内持续 有效，不断返回结果。 我们从两方面来对数据库查询进行分类。首先根据返回类型进行分类： 基于实体对象的查询返回满足查询条件的对象结果集；基于值的的查询返回 的是一个单一的值。其次根据是否是聚集类型来分类，我们采用聚集松散度 来处理对象之间因相互作用而影响查询结果的查询。根据这两类分类方式我 们将查询分为四种： 1 基于值的非聚类查询这是最简单的查询类型，它返回的是移动对象 属性值，不包含任何聚集操作。概率单值查询( p r o b a b i l i s t i cs i n g l ev a l u e q u e r y ，a s i n g l e q ) 已知移动对象磊，概率单值查询返回，“， p 防【j ， 材】) 其中，u er 并且- u ，p 是t k a 的概率密度函数( t k a 表示死的属性 值) 。 2 基于对象实体的非聚类查询此类查询返回满足条件的一组对象，并 且这些对象之间是相互独立的。一个典型的例子就是概率范围查询 ( p r o b a b i l i s t i cr a n g eq u e r y ，e r q ) ：给定一个闭区间 ，川，其中，”r 且 区“，e r q 返回( 正，酌，其中p l 是乃a e 【，“】的非零概率。 3 基于对象实体的聚类查询此类查询返回满足聚类条件的一个对象结 果集。例如：概率最大( 最小) 值查询( p r o b a b i l i s t i cm i n i m u m ( m a x i m u m ) q u e r y ，e m i n q ( e m a x q ) ) ：返回具有最大( 最小) 值的乃a 的移动对象( 正，a ) ， 其中阢是乃a 阱u 】的非零概率；概率最近邻查询( p r o b a b i l i s t i cn e a r e s t n e i g h b o rq u e r y ，e n n q ) ：已知g r ，概率最近邻查询返回数组( 乃，p f ) 的结 果集r ，其中所是使i 乃a g i 为t 中所有对象的最小值的非零概率。 4 基于值的聚类查询此类查询通过聚类计算返回一个单一值。根据聚 类计算的不同分为两类： 第一类的聚类操作使得一个对象的位置和概率密度函数与其他对象不相 哈尔滨理工大学工学硕士学位论文 关。概率平均( 总值) 查询( p r o b a b i l i s t i ca v e r a g e ( s u m ) q u 叫，v a v g q ( v s u m q ) ) ： 查询返回值z ，h ， 鼬) k 【l 川) ，其中z ，铭r 且l u ，x 是对象集r 中的 属性a 的平均值( 总和) 的随机变量，删是x 的概率密度函数，并且满足当 x u 时烈炉0 。 第二类聚类操作使得一个对象的位置和概率密度函数与其他对象相关， 包括概率最小值( 最大值) 查询( p r o b a b i l i s t i cm i n i m u m ( m a x i m u m ) v a l u eq u e r y ， v m i n q ( v m a x q ) ) 查询返回值， ，) k 【l ，“】) ，其中，u e r 且区“， x 是对象集r 中的属性a 的最小( 最大) 值的随机变量，p 是x 的概率密度函 数，并且满足当x l 时巩沪o 。 基于不确定性模型的时空查询算法研究方面，主要有w o l f s o n 等人嘲 基于位置不确定移动目标的一些考虑，w o l f s o n 等人嘲分析不确定性移动 点与确定性区域之间的不同时空关系，将查询分为点查询( p o i n tq u e r y ) 和时空 范围查询( s p a t i o t e m p o r a lr a n g eq u e r y ) 两大类，引入包含不确定性语义的操作 符如w h e n - a t ，w h e r e - a t ，s o m e t i m e s p o s s i b l y - i n ，a l w a y s - d e f i n i t e l y - i n 等。分 别从时间和空间可能性对移动对象进行查询。主要算法有r e y n o l dc h e n g 的概率范围查询和概率最近邻查询算法例，是基于对象位置的不确定性模 型；还有g o c et r a j c e v s k i 等啪1 对于轨迹不确定性模型提出的范围查询算 法。 目前，对基于不确定性模型的移动对象查询算法尚处于起步阶段，有些 研究并未独立出来，结合其他数据路里的共同特征对移动对象数据库中的不 确定数据进行综合讨论。解决移动对象查询中的不确定性，除了建模、查询 算法，还涉及到索引结构，对索引结构进行相应调整，将不确定因素融入到 索引结构中去，会提高索引数据的精确度但是存储容容量或系统计算量也会 相应增大。为了有效的进行查询，综合索引结构进行考虑是一个重要的处理 时空不确定的方法。 3 5 本章小结 本章阐述了时空不确定性。首先明确了时空不确定性的概念；然后分析 了时空不确定性模型，并给出了时空不确定模型的分类；最后在时空不确定 模型的基础上对时空不确定性查询进行了分析总结，同时指出了基于时空不 确定性查询的研究方向。 哈尔滨理工大学工学硕士学位论文 第4 章瞬时查询和时空范围查询基本研究 4 1 引言 在时空数据库中由于移动对象不断地产生大量的时空信息，要保持最新 的信息就必须及时的更新数据，其数据量是十分庞大的。所以在时空数据库 中如何有效地管理这些动态信息一直是被广泛关注的研究课题。 目前，主要存在两种构造空间索引结构的方式啼引。第一种是基于空间分 割的索引结构，它主要是将多维空间分割成细小的单元，如四叉索引。第二 种是基于实体对象的索引结构，如r - 树索引。当前研究的时空索引的方法主 要是扩展现有的空间索引结构。传统的空间索引方法主要用来快速检索静态 的对象，而在移动对象数据库等应用中，移动对象频繁地改变，这会引起索 引结构的动态变化，所以移动对象索引不但要考虑查询效率问题还要考虑更 新代价问题。 本章在对瞬时查询和时空范围查询研究的基础上，针对现存问题提出一 种新的索引结构，并给出了基于这种结构的瞬时查询和时空范围查询的算 法。 4 2 索引结构 4 2 1 传统b u d d y 一树 b u d d y - 树是建立在对空间区域循环分解原则之上的一种索引结构，可以 看作是r 一树和网格文件的一种折中的方法。网格文件在形式上较松散，但其 数据相关性较强。b u d d y - 树是基于数据空间分割，并且不分割空的数据空 间。与r 树相比较，其插入和删除等操作是严格按照一条路径进行的。 b u d d y - 树可用于索引移动对象并支持各种查询操作，如：范围查询、连接查 询、最近邻查询等。 b u d d y - 树中的每个非叶子节点又称为目录页，由( b r ，p o i n t t o c h i l d ) 单元 组成。其中b r 为包含其对应孩子节点的外包矩形，p o i n t t o c h i l d 是指向子树 的指针。叶子节点又称为数据页，c a ( o l d ，d a t a ) 单元组成。其中o l d 为移动对 哈尔滨理工大学工学硕士学位论文 象标识符，d a t a 是数据记录。 g u o 等人提出了b u d d y * 树。其主要思想是在原有b u d d y - 树的索引结构 基础上采用l b s ( l o o s eb o u n d i n gs p a c e ) 来替代非叶节点的外包矩形，以此降低 了传统m b r 较高的更新代价；在每一层上采用右链，类似于b 1 i n k 或r - l i n k 。由此，在每一层上所有的节点链成一个单链表，提高系统并行操作的性 能。图4 _ 1 是b u d d y * 树在二维空间的索引结构图，其中a ) 是空间划分图b ) 是 b u d d y * - 树结构图。 a ) 空间划分图b ) b u d d y * 树索引结构图 a ) p l a n a ro fr e p r e s e n t a t i o n b ) b u d d y * - t r e 图4 - 1b u d d y * 树索引结构示意图 f i g 4 - 1s t r u c t u r eo f b u d d y * - t r e e 4 2 2b h 索引结构 本节针对瞬时查询和时空范围查询提出了一种新的索引结构，该索引结 构通过引入h a s h 辅助索引表直接检索叶节点，大大降低了查询操作时间，从 而提高了查询性能。将这个索引结构记为b h 结构。 b h 结构由两部分组成：一个是对移动对象位置进行索引的树形结构 b u d d y * - 树；一个是用来简化更新过程的h a s h 辅助索引表。 下面给出b h 索引结构的定义。 定义4 1b u d d y * - 树结构中叶节点形式为( t ，以o l d ，d a t a ，p n 劫，其中： 1 t 表示移动对象时间戳信息。 2 矿为叶节点的速度信息。 3 o i d 为移动对象标识符。 4 如绍为数据信息。 哈尔滨理工大学工学硕士学位论文 5 砌删指向在叶子节点层与其相邻的节点。 定义4 2b u d d y * 一树结构中非叶子节点形式为嬲，v b r ，p c h t l d ，胁劫， 其中： 1 l b s 为包含其对应孩子节点的外包矩形。 2 v b r 为非叶节点速度信息。 3 p c h i u t 指向该节点孩子节点的指针。 4 砌谢指向同一层次上与其相邻的节点。 特别地，b u d d y * - 树结构中根节点的形式为伍嬲，p c h i i d ! ，p c h i k l 2 ， p c h i l , m ) 。 在b u d d y * 树中进行时空检索时，随着索引目标数量的增多，树的深度逐 渐增大，而查找依旧从根节点出发，其查找性能随着空间数据量的增加而急 剧下降。因此我们增加了建立在叶节点之上的h a s h 辅助索引表来支持对象的 更新操作。 定义4 3b h 结构中h a s h 辅助索引表中每个单元的形式为( o i d ，p t r ) ，其 中： 1 o d 表示移动对象的标识符。 2 p 护表示指向移动对象最近一次发生位置更新时所处的b u d d y * 树叶节 点的位置。 图4 2 是b h 结构中b u d d y * 树结构和h a s h 辅助索引表结构的示例。当 在b u d d y * 树中插入一个新对象时，如果相应的叶节点已满则需进行节点分裂 生成新的叶子节点，同时向h a s h 辅助索引表中插入一条记录( d d ，p t r ) 。 图牝b h 索引结构图 f i g 4 - 2s t r u c t u r eo fb h 哈尔滨理t 大学t 学硕上学位论文 在b u d d y * - 树中删除一个移动对象时，首先通过h a s h 辅助索引表找到该 对象所在的叶节点，然后将该对象对应的叶节点删除，若节点删除后其父节 点没有予节点则对其父节点采取相应的合并操作。同时将该对象在h a s h 辅助 索引表中的记录删除。 当移动对象位置发生改变时，只需要在叶子节点层通过h a s h 辅助索引表 找到该对象所在叶节点，然后将该对象删除，并将其新的位置索引信息插入 新的叶节点中，同时修改h a s h 表中该对象对应记录的指针使其指向新的叶节 点。 如果b u d d y * 树中的对象在最大间隔时间内没有更新，则将通过“删除一 重插入 方式把它放入当前最新的b u d d y * 树中，并同时修改h a s h 索引表。 通过上述分析可以看出，由于引入了h a s h 辅助索引表，移动对象的插 入、删除和移动都是发生在叶子节点层及其父节点层的自底向上的局部更 新，不用遍历整个b h 索引结构来进行更新。这种方式极大的提高了系统的 查询效率，减少了额外的磁盘i o 。 4 3 基于b h 结构的时空查询 基于上一节提出的b h 索引结构，首先介绍了b h 索引结构的索引快照模 型和查询