移动对象数据库.ppt

移动对象数据库,1 研究背景,近年来，随着无线通信技术的高速发展，时空数据库越来越多地应用在地理信息系统、交通管理、定位、城市规划等各个领域。在无线定位业务（Location-Based Service,LBS）应用中，LBS 通过无线通信网络获取移动对象的位置信息，在地理信息系统平台的支持下为客户提供相应的服务，其中包括儿童保护、个人导航应用、寻友服务、销售人员管理、资产跟踪服务等。获取的移动对象及其位置信息组成的数据库称为移动对象数据库（Moving Objects Databases，MOD），它基于时空数据库中时间和空间变化类型之一：实体的运动。,时空数据库作为一种现代的面向对象的高级数据库技术，它有效地组织和管理时态地理数据、属性、空间和时间语义。时空数据库是包括时间和空间要素在内的数据库系统，是在空间数据库的基础上增加时间要素而构成的三维（无高度维）或四维数据库。与传统的数据库相比具有动态性和全面性的特点。它包括任何历史数据，并且同样可以对其进行更新，使数据库可以成任何一个系统和部门的完整的电子信息档案库，同时，对历史、当前和将来进行对比、分析、监测和预测预报，从而为预测预报系统、决策支持系统和其他分析系统服务。时空数据库并不一定是移动数据库，其对象可以是移动的物体，但不是必须具有移动的特性。,移动对象数据库技术是一项新兴技术，在国外已有大量的研究，国内目前起步还比较晚。移动对象是移动计算环境下的运行主体，因而如何实施对移动对象的有效管理，便成为了这一领域的研究热点。目前，移动对象数据库的研究大致分为四个方向：位置建模、查询语言、索引结构、不确定性处理。,2 移动对象数据库,2.1 时空数据库的基本概念随着空间数据库技术的不断发展，对空间对象的时域信息的研究和应用显得日益重要。任何实体都有其时间（时态）、空间特性。在许多现实应用中实体本身及实体之间的时态、空间、时空关系往往成为人们需要对实体进行处理的主要方面。例如：天文、地理信息管理、城市规划、交通管理、天气预报、生态管理等等，这些应用的共同点是：要求能够比较真实的记录并处理实体的时态信息、空间信息、空间信息随时态的变化而发展变化的信息等。,传统空间数据库技术不能处理和反映空间对象历史信息的变化，所以只有发展新的数据库技术才能克服这一问题，才能支持对对象空域和时域信息的同时有效管理，传统空间数据库对对象的空间信息管理是有效的，但它的处理操作仅限于当前时间有效的空间对象，当一个新的对象值被插入到当前存在的数据库中时，旧的对象值就会被删除，因此对随时间变化的空间对象很难实现空间对象历史信息的有效管理。为解决这一问题，时空数据库的研究日益成为热点，时空数据库可同时为对象提供有效的历史和空间管理支持。,时态数据库和空间数据库。时态数据库是存储与管理时态数据的数据库，目前，时态数据库被应用于医疗系统，证券系统，信用管理系统等应用领域中。空间数据库系统是描述、存储和处理空间数据的数据库管理系统。空间数据库已经在地理信息系统(GIS)，计算机辅助设计和制造系统(CAD/CAM)，多媒体数据库等应用领域得到了比较广泛的应用。随着数据库技术的发展，用户也提出了越来越高的要求，如：当用户需要查询 2010 年千山中路的地理地貌时，单独的时态和空间数据库都无法满足。在这种情况下时空数据库的诞生成为必然。时空数据库是时间和空间要素相结合而构成的三维（无高度维）或四维数据库，时间维的存在大大丰富了数据库的内容。它一方面增加了数据库管理的复杂性，另一方面，海量的数据为时间和空间分析提供了极为广阔的舞台。,时空数据库的实现可以使数据库成为真正意义上的资源清单，它可以为分析提供横向的现势和纵向的历史数据，对历史、当前和将来进行对比、分析、监测和预测预报，从而为预测预报系统、决策支持系统和其它分析系统服务。时空数据库是时态地理信息系统（TGIS）的核心，同时兼具时态和空间双重属性,时态地理信息系统的关键问题是时空数据库的设计和管理，建立合适的时间与空间联合的数据模型时空数据模型，采用科学的管理方法，更有效地组织和完善时态地理对象的属性、空间和时间语义，以便重现历史状态，跟踪变化，预测未来。时空数据库和时间地理信息系统对所有与地理信息有关的领域有广泛的应用前景，特别势对经常性变化的空间信息的管理具有重要意义，目前，TGIS 在地籍、土地利用、房地产、交通、能源等方面有着良好地应用。,2.2 移动对象数据库的基本概念,时空数据库作为一种现代的面向对象的高级数据库技术，它必须而且只能建立在原来的数据库技术的基础之上。移动对象数据库是作为时空数据库的分支发展而来的，它基于时空数据库中对象的运动的特性，具有移动的特性。移动对象数据库是对移动对象的位置及其相关信息进行表示与管理的数据库。在移动对象数据库中通常管理着两类空间对象，一类是静态的空间对象，比如“查询离我最近篮球场”所提到的篮球场，这类,信息通常依赖于用户所在的位置；另一类则是移动对象，其位置是不断变化的，比如“查询位于 A 街区的出租车”中所提到的出租车。移动对象数据库是指对移动对象（如车辆、飞机、移动用户等）及其位置进行管理的数据库。移动对象管理技术在许多领域展现了广阔的应用前景。在军事上，移动对象数据库可以回答常规数据库所无法回答的查询；在民用领域，利用移动对象数据库技术可以实现智能运输系统、出租车/警员自动派遣系统、智能社会保障系统以及高智能的物流配送系统。此外，移动对象管理技术还在电子商务领域有着广泛的应用前景。目前，移动对象管理主要研究问题包括：,1.位置的表示与建模：为了对移动对象的位置进行行之有效的管理,移动对象数据库系统必须能够准确地获取移动对象的当前位置信息（位置信息的获取）,并建立有效的位置管理模型（位置信息的表示）。2.移动对象索引技术：在移动对象数据库中，通常管理着数量非常庞大的移动对象。在查询处理时，如果逐个扫描所有的移动对象显然会极大地影响系统的性能。为了减小搜索空间，就必须对移动对象进行索引。移动对象的索引技术是一个充满挑战性的研究领域。到目前为止，这方面的研究资料不是很多，尚待进一步地深入。,3.移动对象及静态空间对象的查询处理：移动对象数据库中的查询目标分为两种：一种是移动对象、（如汽车、移动用户等），另一种是静态空间对象（如旅馆、医院等），对这两类数据的查询各自需要相应的索引结构的支持。移动对象数据库中的查询具有位置相关的特性,即查询结果依赖于移动对象当前位置，同一个查询请求，其提交的时间、地点不同，返回的结果也将不同。典型的查询包括区域查询（查询某个时间段处于某个地理区域的移动对象）、KNN 查询（查询离某一点最近的 K 个移动对象）以及连接查询（查询满足条件的移动对象组合）等。,4.不确定性的表示及处理：移动对象的位置管理方式本质上就具有不确定性（或称不精确性）。不管采用何种位置管理及位置信息更新策略，移动对象数据库中保存的位置信息与移动对象的实际位置总会存在一定的偏差。比如在周期性位置更新方法中，位置信息的更新是周期性完成的，在每一个更新周期内，数据库中的位置信息是不变的，而实际上移动对象可能已经在此期间离开了原来的位置。将位置表示为时间的函数同样也存在着位置的不确定性，位置函数仅仅是近似地刻画了实际位置的变化，因此偏差总是客观存在着。此外，系统通过设定阈值的方式来减少位置信息更新代价的策略，也增加了位置的不确定性。,2.3 时空建模,时空数据库的目的是处理、管理和分析时空数据。大多数信息系统的能力在很大程度上依赖于其数据模型的设计。数据模型是一个信息系统的概念内核，它们定义了数据对象的类型、关系、操作，以及保持数据库完整性的规则。一个严格的数据模型必须能够预见在时空数据库系统中将会执行到的时空查询和分析方法。关于时态构造的信息必须在数据模型所定义的数据对象中表示出来，以便在时空数据库系统中存储、提取和分析。如果时空数据库没有一个很好的数据模型，就难以有效支持时空查询和时空分析。,目前，建立高效统一的时空数据模型还存在相当的困难，在过去的二十多年里，各相关领域为此已提出不少模型，它们来自不同的背景并能够满足各自不同的需求与限制。常见的时空模型有：序列快照模型、基态修正模型、时空复合模型、基于事件的时空模型、时空对象模型等等。时空数据库的本质是关于移动对象的数据库，移动对象是随时间变化的几何体，其变化可以是连续的，也可以是离散的，它为移动对象定义了一个抽象数据类型的框架。这个框架以一系列基本类型为开端，其中包括标准数据类型、空间数据类型、时态数据类型。由此产生了移动点和移动区域类型，移动点类型描述对象在空间中的位置，移动区域描述对象的移动，扩张和收缩。,这种建模方法定义了两个层次的模型，包括抽象模型和离散模型。抽象模型的定义以无限集为基础，因此可以将一个移动点看成是三维空间中一条连续的曲线，也就是一个从无限的时间域道同样无限的空间域的任意映射。这种抽象的观点是我们感兴趣的概念模型，例如，飞机的飞行轨迹是连续的，任意时刻总存在一个值，不论能否为这个映射找到一个有限表示。抽象模型在概念上非常简单，语义也相对容易定义，但却无法在计算机中存储和操作。因此需要离散模型来表示移动点和移动区域以及其它相关的类型，可以将离散模型看成是无限模型的有限表示，比如空间数据库中用一个多边形表示区域，用线集表示河流等等，我们可以将移动点的运动线性近似的表示为三维时空上的一个线集，将移动区域线性近似,成一个多面体的集合。离散模型的定义较抽象模型复杂，但是离散模型可以直接转化为数据结构和算法，而抽象模型无法做到这一点。随着 GPS 技术和无线通讯技术的发展，管理移动对象动态信息成为可能。这使移动对象数据模型的研究得到了广泛关注。准确地获取移动对象的当前位置信息，是进行更为复杂的位置管理的先决条件。移动对象的位置总是在改变，要保证位置数据随时有效，传统方法是周期性刷新数据。但移动对象位置的频繁变动会给服务器带来严重的更新开销，而且会增加网络负担。这就需要新的处理方法。目前移动对象数据库技术主要采用如下位置建模方法：将移动对象的位置抽象成时间的函数，即 Location=f(t)，系统可根据该函数计算出移动对象在将来任一时刻的位置，移动对象无需周期性地报告当前位置，只在实际位置与计算,位置的偏差达到或超过一定阈值时，才对数据库进行更新。这种方法极大地降低了数据库的更新开销,减轻了网络负担。在移动对象的位置模型中具有代表性的成果有移动对象时空(MOST)模型。MOST 模型是由美国 Illinois 大学芝加哥分校的 Ouri Wolfson 及其研究小组提出的。它引入了动态属性的概念。当然，MOST模型也有其局限性，另外的专家学者也提出了相关的模型。,2.4 查询语言,在空间数据库中的基本对象类型包括点、区域、线，空间关系包括拓扑空间关系、顺序空间关系和度量空间关系，其中，拓扑空间关系是空间关系理论的重点和难点。移动对象数据库中常见的查询请求有：1.基于坐标的查询，(1)点查询，如查询车辆在 t 时刻的位置。(2)基于距离的查询，如查询离当前位置 500m 之内的商店。(3)最近邻查询，如查询离我当前位置最近的旅馆，其中，另一种经典的表示形式是 k 最近邻查询（KNN）查询 k 个距离最近的对象。在此例中，k=1。2.基于轨迹的查询，(1)拓扑查询，如查询在 2005 年 6 月 14 日早上经过（cross）A 大街的人。(2)导航查询，如查询飞机飞行的速度，,其中速度、方向等动态信息并不是显式地存储在数据库中，而是由轨迹推导得出。(3)基于相似性的查询，它通过某一衡量标准（如欧几里得距离），在一组轨迹中找出与参考轨迹最相似的轨迹。此类查询较广地应用于数据挖掘中。例如，我们可以通过观察分析超市里顾客的运动轨迹，来最优配置商品。(4)轨迹最近邻查询，查询某时间间隔内离某点最近的轨迹，或离某轨迹最近的轨迹。3.复合查询，这种查询是以上列举的查询中两个及其以上的复合(也可以对其自身的复合)。例如查询在一小时后，在今天 7a.m.和 8a.m.时间间隔内离开鞍山的车辆的轨迹信息，其中，今天 7a.m.和 8a.m.时间间隔、鞍山构成了一个范围查询，一个小时之后，限定了需要检索的轨迹的时间范围。,4.位置相关的持续查询以一个具体的位置相关的持续查询 Q 为例，Q 对应于一个时间区域，在该时间区域内，Q 处于活动状态，由于移动对象位置的改变，Q 的查询结果也在不断变化，系统需要随时将查询结果的变化信息传递给查询用户，使用户能不断地实时监控最新的查询结果。这类查询在常规的数据库中是无法实现的，因为常规的数据库查询语言（如SQL 及 OQL 语言）不具备时态操作符。因此，为了表示位置相关的查询，需要在其原有语言功能的基础上扩充新的内容。目前，时空查询语言：,（1）基于 SQL 的时空数据库语言。STSQL 是基于 ADT 的时空数据库查询语言，通过时空抽象数据类型及其操作实现时空数据表示和查询。它采用兼容 SQL的方法进行时空数据库语言的设计，对 SQL 的子句不作任何扩充。（2）FTL基于未来时态逻辑的查询语言。,2.5 索引结构,在移动对象数据库中，通常管理着数量非常庞大的移动对象。在查询处理时如果扫描所有的移动对象显然会极大地影响系统性能。为了提高搜索效率，就必须对移动对象进行索引。索引结构作为辅助工具支持时空查询，迄今为止，专家学者从基本的空间索引结构和时态索引出发，提出了大量的时空索引结构，其中空间索引结构 R 树从1984 年 Guttman 最初提出，经过 20 年的发展，不断产生的 R 树变体逐渐形成了一个枝繁叶茂的时空索引 R 树家族，从其覆盖的广度和深度来看，多维空间索引R 树就像一维线性索引 B 树一样，是无处不在的。,空间索引是基于R树家族树的，对于众多 R 树家族的空间索引结构，没有哪一种在学术和商业应用上获得一致的认可和肯定，所以对于空间索引技术可以做为一个研究出发点。时空索引移动对象的索引方法通常借鉴于空间数据索引技术，是从空间索引基础上发展而来的，不同之处在于移动对象索引中要考虑时间维。从检索数据的时间段进行分类，大致分为三类：检索历史数据，检索当前数据，检索当前和未来数据。专家学者在历史、当前和未来数据的检索上提出了大量有效的索引结构，这些索引结构通常只支持其一或其二的查询，如何能在一个索引结构上同时支持过去、现在、未来的查询成为当前的研究热点。,2.6不确定性建模与分析,不确定性的建模与分析有些研究人员提出了相关的模型，目前还不能达成一致的统一。由于移动对象数据库所涉及的研究问题为上述四个，其中移动对象的索引和查询技术是时空数据库和移动对象数据库的关键性核心技术。故我们的研究重点可以放在查询和索引上面，其所用到的相关模型和算法值得我们深入研究。,