（计算机软件与理论专业论文）移动对象的建模与查询.pdf

华中科技大学硕士学位论文 摘要 l ( ，移动计算环境对传统的数据库技术，提出了新的要求和挑战。查询是 数据库系统中的重要操作。移动计算环境的移动性、断接性等特点和客户 不满足于访问静态资源，希望得到具有诸如位置相关性、演绎性的结果， 这些都对查询的范围和深度提出了新的课题。面对这种新型的查询要求， 必须提出新的数据模型和查询语言来适应这种需求少矿 通过研究移动对象模型，提出了移动对象的离散表示方法，并将移动 对象抽象为移动点、移动线段、移动区域三类，采用分片法来表示移动对 象。在保留关系型数据库管理系统中的数据类型的前提下，根据移动查询 的需求，对数据类型进行了扩充并分析了该模型下的算子，给出了具体的 数据结构和算法实现，并在国产移动数据库系统m i ) m 2 上初步实现了支持 移动查询的原型系统。 移动对象的查询可能涉及到移动对象的未来状态，传统的数据库系统 不能处理这类查询。通过对常规s o l 语句进行扩展可满足该需求。将扩 展安装在代理服务器上，通过代理服务器支持带时间算子的移动查询，而 非时间相关查询的处理则由底层的数据库系统提供。从性能方面考虑，将 移动对象分为冷对象和热对象，利用b n 树对两者分别进行位置索引，并 利用新的m t 方法对查询结果的传输提出了改进。 关键词：移动数据库：移动查询；数据模型；移动对象；数据类 型；移动算子 i 华中科技大学硕士学位论文 a b s t r a c t m o b i l e c o m p u t i n g e n v i r o n m e n th a si m p a c t e dc h a l l e n g e s t ot h e t r a d i t i o n a id a t a b a s et e c h n i q u e q u e r y i sa n i m p o r t a n t o p e r a t i o n o f d a t a b a s em a n a g e rs y s t e m t h em o b i l i t y 、d i s c o n n e c t i o n o fm o b i l e c o m p u t i n ge n v i r o n m e n ta n d c l i e n ti sn o ts a t i s f i e dw i t hh a v i n ga c c e s st o s t a t i cr e s o u r c e b u th o p et o g e tp o s i t i o nd e p e n d e d a n dd e d u c t i v e c o n c l u s i o n s on e wd a t am o d e la n dq u e r yl a n g u a g em u s tb ep r o p o s e d t h i sp a p e rd i s c u s s e st h em o d e io fm o b i l eo b j e c t s ，a n dp r o p o s e sa d i s c r e t em e t h o dt od e s c r i b et h em o b i l eo b j e c t s ，a n dr e g a r d sm o b i l e o b j e c t sa sm o v i n gp o i n t 、m o v i n gl i n e 、m o v i n gr e g i o n i na b s t r a c ta n d r e p r e s e n tt h e mb y s l i c e dm e t h o d p r e s e r v i n gt h ed a t at y p eo fr d b m s ， i na c c o r d i n gt ot h en e e do fm o b i l eq u e r y , d a t at y p ei se m e n d e d ，a n dt h e c o n c r e t ed a t es t r u c t u r ea n da l g o r i t h m si s i m p l e m e n t e d ap r o t o t y p e w h i c hi sc a p a b l eo fp r o c e e d i n gt h em o b i l eq u e r yo nb a s i so fm d m 2i s p r o p o s e d q u e r yo nm o b i l eo b j e c t sm a yr e f e rs a t a t u so ff u t u r ew h i c hc a n t h a n d l e b yt r a d i t i o n a l d b m s i tc a nb ep r o c e e d e d b ye x t e n d t i o n o n s t a n d a r ds q l t h em a i ni d e a li s a s s e m b l i n gt h ee x t e n d t i o no na g e n t s e r v e r , w h i c hs u p o r tt h et e m p o r a jo p e r a t o r s ，w h i l et h en o n t e m p o r a j q u e r yc a nb ep m e s s e dt h r o u g ht h eb o s o mo fd b m s o nc o n s i d e r a t i o n o fp e r f o r m a n c e ，m o b i l eo b j e c t sa r ed i v i d et oh o to b j e c t sa n dc o l do b j e c t ， w h o s ep o s i t i o na r ei n d e x e dr e s p e c t i v ea n dt h em e t h o do ft r a n s p o s i n g q u e r y r e s u l t si si m p r o v e d k e yw o r d s ：m o b i l ed a t a b a s e ：m o b i l eq u e r y ：d a t am o d e l ：m o b i l e o b j e c t s ：d a t at y p e ：m o b i l eo p e r a t o r 华中科技大学硕士学位论文 一 1 绪论 1 1 课题背景 数据库技术是计算机科学中的重要分支，是当前发展最快、应用最广的技 术之一，是计算机信息系统与应用系统的核心技术和重要基础。近年来通信技 术快速的发展，特别是无线通讯设备、个人数字助理等硬件的普及，使得提供 给客户的服务类型向更广和更高的方向延伸成为可能。客户已不再局限于固定 的网络连接，还可以通过无线方式，随时、随地的访问所需的资源。由此可以 预见，未来的绝大部分移动计算机都将配备以无线网络为主的移动联网设备， 以满足移动用户访问网络中数据的需要。这将是一种更加灵活、复杂的分布计 算环境，人们称之为移动计算。目前，移动计算已成为包括w e b 计算、数据仓 库和数据挖掘在内的“以客户为中心”应用的三大技术手段之一“1 。 在传统的分布计算系统中，各个计算结点之间都是通过固定网络连接，并 保持网络持续连接性。而移动计算系统是由固定结点和移动结点构成的分布计 算系统，客户不再需要停留在固定的位置，可以携带着移动计算机自由移动， 并在移动的同时通过移动通信网络保持与固定结点或其他移动结点的连接。这 种移动性将创造一类全新的应用，使得人们能够更加方便地访问各种信息。与 基于固定网络的传统分布计算环境相比，移动计算环境具有以下几个特点a ”1 1 移动性 在移动计算环境中，一台移动计算机不仅可以在不同的地方联通网络，而 且在移动的同时也可以保持网络的连接。这种计算平台的移动性可能导致系统 访问布局的变化和资源的移动性。 2 频繁断接性 移动计算机在移动过程中，由于受使用方式、电源、无线通信费用、网络 条件等因素的限制，一般不采用持续联网的工作方式，而是主动或被动地间歇 性的入网、断接。 3 网络条件的多样性 移动计算机的移动性使得不同时间可用的网络条件( 如网络带宽、通信代 价、网络延迟以及服务质量等) 往往差别非常大：移动计算机可以工作在高带宽 有线l a n ，也可工作在低带宽无线l a n ，甚至根本无网可上( 处于断接状态) 4 网络通信的不对称性 华中科技大学硕士学位论文 一 这表现在固定服务器节点可以拥有强大的发送设备，而移动计算帮l 明友遮 能力有限，造成下行链路( 服务器到移动计算机) 的通信带宽和代价与上行链路 ( 移动计算机到服务器) 的相差很大。 5 移动计算机的电源能力 移动计算机的电池容量一般只够维持几个小时，电池容量有限的问题将长 期存在。 6 可靠性 无线网络与固定网络相比，可靠性差，故障率高。此外，也存在安全问 题。 7 规模 许多移动应用环境，如公共交通信息系统“1 ，都要求系统支持大量的移动用 户并发访问，这要求移动计算系统必须具有比传统的客户服务器及分布式系统 高得多的可伸缩性。 由于移动计算环境的上述特点，使得传统的分布式数据库技术不能支持或 有效支持移动计算环境。必须认识到，移动计算这种看起来仅仅提供了有限数 据访问类型和有限数据容量的计算手段正好适应了企业计算在后端不断向高性 能、大容量方向发展的趋势，为前端的易管理、易操作性提供了良好思路，将 给未来的数据库带来深远的影响。作为传统数据库应用的一种延伸，移动数据 库应用会在工业领域更快地推广起来。 查询是数据库系统中的重要操作，而移动计算环境对查询的范围和深度提 出了新的课题。这一方面是由于移动计算环境有着不同于传统固定网络连接的 特点，如移动性、断接性等。另一方面，客户的查询不满足于访问静态的资 源，更希望得到具有诸如位置相关性、演绎性的结论。面对这种新型的查询要 求，必须提出新的数据模型和查询语言来适应这种需求。 1 2 国内外研究概况 目前，移动计算的研究覆盖了许多研究领域，如移动硬件设备、移动通 信、移动联网技术、无线聊访、移动数据库技术和无线客户服务器应用 等。与数据库技术密切相关的研究是移动数据库技术，即支持移动计算的分布 式数据库技术。 移动数据库技术的研究领域相当广泛。为了实现移动数据库系统必须解决移 2 华中科技大学硕士学位论文 一 动计算环境中断接性、移动性、通讯的不对称性等因素对数据库系统的影响。 主要应包含移动事务处理、数据广播、数据复制缓存技术、移动查询等关键技 术。本文关注的是移动查询相关研究的进展情况，但即使局限于该领域，众多 大学和科研机构学术研究的起点、侧重点、范围及深度也不尽相同。z & 仇愕 提出了一种基于离散变化的时空对象，用空间属性和时态属性的笛卡尔积表示 该对象“。 在文献“1 中，作者提出了具有位置约束的查询概念。如“找一位离我最近的 医院”是关于位置的一元约束。又如“寻找x , y 和z ，他们在同一栋楼中，y 在x 和= 之间”涉及一个三元位置约束和三个一元位置约束。为了以尽可能小的通信 代价去检索必要的信息以满足查询的要求，作者建议使用启发算法来解决这个 问题。其基本做法是将位置服务器管辖的区域基于固定基点划分为若干分组， 每个分组互不相交。当移动客户从一个分组移动到另一个分组时，便向宿主位 置服务器报告。客户查询位置属性的步骤为：首先查询其宿主服务器，若查询 对象不在宿主服务器管理的分组中，则漫游到移动对象当前所在的位置服务 器，然后从该位置服务器查出移动对象的位置。作者还讨论了一组协议：将全 球定位系统g p s 集成在z 尸上，以便提供位置依赖服务。这些服务的例子是：对 特殊地理位置( 如汽车位置) 有选择性的进行多播。 文献0 1 提出了一个查询处理接口，成为基于徽标的查询( q b o 。通过蜂窝电 话，该接口与远程数据库联系并显示图解信息，这个接口能对用户的输入产生 响应，自动的生成查询请求。例如系统将数据库的多种关系提供给用户，用户 用笔在屏幕上轻击这些关系，可得到感兴趣的属性。更进一步，用户可以请求 一 显示各属性之间所有可能的路径。也就是说，只用轻击显示器，就可显示出路 径连接，进而可以显示连接表和表示该连接表的s 耍匾查询。( q e i ) 的功能如下： 1 徽标视觉语言允许用户使用类似笔的点击设备来控制徽标，以建立查 询。 2 语义数据模型获取数据库各方面的信息。 3 断接查询工具用于断接运行时的查询。当网络断接时。查询仍被响 应，访问的数据会被传送到移动客户，而不必访问服务器上的实际数据 o w o l f s o n 等人主要在移动对象建模、查询及定位等方面进行了研究m 。他 们提出了一种表示移动对象的数据模型 m o s t ( m o v i n go b j e c t ss p a t i o - t e m p o r a l ) 。并为该模型提供了查询语言 华中科技大学硕士学位论文 一 f t l ( f u t u r et e m p o r a ll o g i c ) 及相应的算法。m o s t 模蛩眄p 将移动对象抽象为 点，并捕捉当前及较近未来的移动对象位置。但是移动对象的位置并不直接存 储在数据库中，而是用运动矢量描述位置、速度大小和方向。只要基于运动矢 量的预测位置与移动对象的真实位置的偏差小于给定的上限，就可不考虑更新 数据库。此外，还就位置更新代价和位置信息的不确定性进行了权衡。但是这 些研究局限于移动的点对象，没有完整的描述移动对象的轨迹，没有对一致性 查询作出处理，也没有涉及较为复杂的几何体，如移动变化的区域等。 在移动查询优化方面，ra l o n s o 提出了设计移动数据库系统的一些准则 “”。d u n h a m 等对位置相关数据和查询研究进行了形式化描述和讨论“。文献“ 2 ”对移动对象的位置属性的索引作了研究，提出了各自的索引方案。 g u t i n g 所在的小组8 0 年代便开始了对空间数据的研究僻，近年来，他们 的工作重点逐渐向时态数据库、时空数据库和移动数据库等方向转移汹“1 。在移 动数据库方面，他们的思想是，不依赖具体的d b m s ( 如r d b m s ，o o d b m s 等) ，从代数系统的角度。2 3 “，用抽象数据类型来描述移动数据库中的数据类 型，并给出相应的算子及算法( 如移动点对象和移动区域对象的距离算法等) 。5 。 蚓。他们观察到任何时态相关的对象都可用以时间为参变量的函数表示，因此某 种类型o t 的时态版可用时间到位的映射函数表示。例如移动的点集、变化的区 域等时空对象便是时态对象的某些特例，此时口为空间数据类型。此外他们还 讨论了移动对象的抽象模型和离散模型及两者的关系。以上工作主要关注的是 在二维空间里运动的空间对象，将结论扩展到更高维空间仍需进步研究，而 且还没有完整实现在现有d b m s 基础上扩展移动数据类型和算子的工作。 目前，移动数据库系统通常采用三层结构，即在客户机和服务器之间增加 ： 了一层来实现。比如o r a c l e 的m o b i l ea g e n t ，i n f o r m i x 公司的i m o b i l e ， s y b a s es o la n y _ 【v h e r e 和s o lr e m o t e 以及国内人大金仓“小金灵”系统。 以上这些产品都是侧重于解决客户机与数据服务器之间因为无线网络的低 带宽、高延迟和易中断等特点而带来的网络连接问题，借助扩展传统的客户服 务器结构来提高无线网络的利用率，借助数据复制技术来支持断接情况下的数 据库操作。对客户机的移动性等方面考虑很少或者没有加以考虑。 1 3 课题来源、目的及意义 根据应用需求以及华中科技大学计算机学院青年基金移动对象的建模 华中科技大学顾士学位论文 一 与查询( 项目编号：2 0 0 0 0 3 ) 的资助下，我们开展了移动数据库技术研究。 在开展移动数据库技术研究之前，在分布式数据库技术方面进行了大量的 研究，最有代表性的成果是分布式多媒体数据库管理系统d m 2 d g 。该系统采用 关系一层次- o o 数据模型，符合数据库语言s o l 标准。系统从客户端到服务器 提供了多层次、多途径、多机制的完整性控制，实现了唯一性约束、引用约 束、检验约束的定义、检查与处理。系统具备故障恢复功能。系统提供站点透 明性，支持副本：各服务器之间协调工作，共同完成分布式查询、更新等任 务，能够保证多个站点上数据库状态的致性。系统提供了o d b c 接口和嵌入 式、交互式i s w l 方式操纵数据库，支持多媒体、地图信息管理功能，实现了对 。 常规数据、多媒体数据、地图数据的一体化定义、存储和操纵。系统对1 0 万条 常规和地图数据的检索速度为秒级，系统安全级达到b 1 级。本文的工作将以 d m 2 为基础，实现移动对象查询系统原型。 目前，移动数据库技术已经成为国际数据库界一个新的研究方向。移动数 据库的典型应用有： 1 公共信息发布 比如，移动用户需要经常访问的股票、天气和交通等信息。在文献“中提到 的a t i s 系统为例，它将为配置有移动计算机的各种车辆提供城市交通信息。在 交通高峰时段，一个大城市的a t i s 系统将同时为超过1 0 0 ，0 0 0 个移动客户服 务，对于这种大规模并发服务的应用，传统的客户f t 务器数据库技术显然难以 适用。 2 移动办公 -比如，用户在移动的汽车上借助移动计算机可以与公司保持联络处理相关 信息。从一家美国汽车保险公司雇员移动办公的例子油1 ，可以看到在移动数据 库环境中，工作效率大大提高。同时，也可看到移动数据库的事务通常是一种 长事务，事务处理要解决断接问题。断接问题是移动数据库要解决的基本闯题 之一。 3 数字战场 现代战争对信息的需求越来越强烈，通过移动计算机在联机或断接情况下 辅助处理战场相关情况。目前，美军正在实施一项战场获知与数据发布研究计 划。 4 。位置相关查询 s 华中科技大学硕士学位论文 一 查询与移动用户位置和或移动方向相关的数据和信息。例如，查询“最近 的餐馆在哪里? ”，其结果取决于用户所处的位置。 1 4 本文研究内容和安排 本文共分七章。 第一章为概述，介绍了课题的来源、目的、意义及国内外研究概况。 第二章介绍移动查询技术的体系结构和所涉及的一些相关概念。 第三章主要研究移动对象的数据模型。 第四章讨论移动对象的数据类型。 第五章分析移动查询的算子及算法。 第六章给出支持移动查询原型系统实现方案。 第七章是本课题的总结和展望。 6 华中科技大学硕士学位论文 一 2 移动数据库体系结构和关键技术的研究 2 1 移动数据库的体系结构 客户服务器结构从开发至今已经成为一种应用广泛的计算模式。其基本思 想是给特定的设备赋予特定的功能，完成特定的服务，即进行功能分布。支持 客户服务器结构的数据库系统的出现是应用需求驱动的。它与数据库技术相结 合产生了客户服务器结构的数据库系统。在这种数据库系统中，体系结构的不 同划分其性能是不同的。移动数据库系统作为传统分布式数据库系统的推广， 它具有传统分布式数据库系统所不具有的特点，如移动性、断接性等，使得传 统的二级客户服务器结构不能完全满足移动数据库系统的需要。比如，传统的 二级客户服务器结构中客户机和服务器要保持持久连接，不支持断接性。又比 如，移动客户机的移动可能跨越多个数据库服务器平台，显然直接在数据库服 务器这一层管理移动客户机跨平台移动及相关信息是不合理的，至少应该抽象 出一层来管理移动性。也就是说，必须扩展传统的二级客户服务器结构为多级 客户服务器结构( 本文将三级以上包括三级统称为多级) 。因此，必须研究适用 于移动数据库系统的客户服务器结构。 为了有效地管理移动数据库就应该提供相应的移动数据库管理系统，这可 以在分布式数据库管理系统的基础上进行研究。我们认为，移动数据库管理系 统的主要目标是支持客户机在移动和或断接情况下的数据库操作。其主要功能 应包括：移动事务处理，移动查询优化，移动客户机的位置信息管理，复制缓 存管理等。由于移动数据库系统中仍然存在传统的静态客户机，而且一旦移动 客户机的位置确定后，主要的查询处理过程与分布式数据库的是基本一致的。 - 考虑到移动客户机和静态客户机的同时存在以及前面的讨论，我们认为与移动 有关的信息和预处理t ：作应抽象出来作为层，这意味着移动数据库管理系统 应采用多级客户服务器结构。这必然要考虑移动数据库管理系统的功能划分问 题，下面首先讨论客户服务器结构的数据库管理系统( d b i - i s ) 不同的功能划分对 数据库系统的影响。然后讨论适用于移动数据库系统的客户服务器结构，在此 基础上阐述基于d m 2 的移动数据库管理系统体系结构。 d m 2 是我们自行研制的分布式数据库管理系统，不支持移动计算环境下的数 据管理。为了使之支持移动数据库的管理。我们将在此基础上扩展，构成三层 7 华中科技大学硕士学位论。文一 客户服务器结构，中间层是具有一定代理功能的虚拟服务器。下面将讨论虚拟 服务器的概念。 虚拟服务器 1 虚拟服务器与动态分布式数据库 在移动计算环境中客户机是移动的。运动是相对的，即客户机被假定静止 时，服务器则是动态变化的。在移动数据库环境中，客户机的移动，造成了数 据库s e r v e r 的“移动”。为此引入“虚拟服务器”( 简称v s ) 的概念。数据不仅 是分布的，而且是动态变化的。为此，我们引入动态分布式数据库的概念。所 谓动态分布式数据库是指：在物理上静态的分布式数据库，对用户而言，是随 着用户的移动，所见到的是不同的，逻辑上是动态变化的数据库。相应的我们 认为：移动数据库管理系统是一种动态分布式数据库管理系统。在此基础上， 构造的移动数据库管理系统( m d m 2 ) 的体系结构 2 虚拟服务器的功能和体系结构的特点 ( 1 )虚拟服务器的功能 虚拟服务器的主要功能有：提供通讯接口和用户接口；动态分布数据库构 造及数据库定位功能。动态分布数据库要包含与位置和时间有关的信息，而且 要能提供在原始数据上一定的归纳、提取和抽象功能以及提供物理数据库缓存 区保存缓存数据。数据库定位要确定物理数据库的位置；由管理。确定在本地 还是异地处理，此外要管理移动客户机的位置信息；翻译处理。具有网关功 能；移动事务处理：移动查询及优化处理；据缓存管理。 ( 2 )体系结构主要特点 基于该虚拟服务器的体系结构的最主要特点是：较强的通用能力和可扩展 性。 3 虚拟服务器的功能实现 根据前面所提出的体系结构，结合我们自行研制的d m 2 系统服务器核心所 构造的移动数据库管理系统m d m 2s e r v e r 核心的体系结构。移动数据库管理系 统m d m 2 要解决的关键问题主要有：移动事务管理，移动查询及优化处理和数据 缓存管理等。 在移动数据库系统环境众多特点中，最为重要的是移动性。为了支持客户 华中科技大学硕士学位论文 机的移动。必须跟踪客户机的位置状态，以便让相应的服务器为客户机提供服 务。为此在客户机和服务器端要提供一种机制完成客户机的逻辑位置( 在那个 组数据库服务器的服务范围内) 的跟踪。虚拟服务器具备一定代理功能，它是连 接客户机缓存和固定网络中央数据库的桥梁，它将提供跨多个异构数据库平台 的数据整合能力。 用户在移动过程中，查询的结果往往与位置是相关的。也就是说，对一个 查询的回答不仅依据数据库的内容，而且要依据查询发生的位置( 它是时间的函 数) 。本文我们将移动客户机，移动计算机称为移动对象( m o b i l eo b j e c t ) 。 客户端d b m sl i t e 为了有效地支持客户机的移动，必须提供相应功能的客户机端d b 淞，在设 计客户端d b m s l i t e 时，考虑到移动客户机资源相对有限，这需要进行功能 上的简化：同时又要保证客户机端具有足够的自治性。为此我们在d m 2 基础上 进行了剪裁和利应扩充：保留本地事务管理和数据操纵相关的功能，包括数据 操纵、查询处理、记录管理、并发控制和日志及恢复管理；为了支持客户机的 断接操作，我们重新设计缓存区管理，增加断接管理、收集管理、和重集成管 理三个模块。 2 2 移动查询的关键技术 移动查询领域存在诸多研究方向。其中至少涉及位置管理、支持移动查询 的s q l 语言扩展、查询结果传输等方面。文献。“还研究了移动查询结果的规范 化问题。 2 2 1 位置管理策略 移动计算的最显著的特点是移动性。移动客户希望在任意位置获取信息的 需求，对现有的网络、操作系统和数据库领域提出了一系列新型的问题，而对 象位置管理和位置相关查询处理是移动计算面临的主要挑战。如何得到移动对 象的位置信息是处理位置相关查询的前提。所谓位置相关查询指结果依赖于请 求查询客户的“j j 口位置信息。下面将描述两种主要的实现策略。种是基于 g p s 的位置管理策略，另一种是基于小区管理策略。此外，将论述位置属性固 有的不确定性。 华中科技大学硕士学位论文 一 2 2 1 1 基于( j p s 的位置管理策略 在移动计算环境下，借助全球卫星定位系统( g p s ) 可以对移动对象进行定 位。我们知道，g p s 是具有全球性、全能性( 陆地、海洋、航空与航天) 的导航 定位、定时、测速系统。它可以在全球范围内，全天候、实时地为用户连续提 供精确的位置、速度及时间信息。因此可以考虑利用g p s 来确定移动对象的位 置属性”。 在移动数据库管理的移动对象上装备g p s 卫星接收机，并捕捉、跟踪卫星、 接收、放大和记录g p s 信号，并由接收机中的运算单元解算出移动对象当前的 位置信息，还可同时获得测速、定位、定时等数据。g p s 的定位数据可通过移 动对象上的通信设备，传送到位置管理服务器。 这种策略通过全球定位系统，及时接收卫星信号，获取移动对象当前所处的 位置、速度等信息。而且g p s 定位的精度特别高。g p s 静态相对定位的精度一 般在几毫米至儿粒米范围内，动态相对定位的精度一般在几厘米至十几米范围 内。另外，装配在移动对象上的g p s 卫星接收机只负责接收讯号，而不用发射 讯号，因此g p s 卫星接收机的能耗相当低。从技术角度讲，可以时刻跟踪移动 对象的位置；从经济上考虑也是低代价和易于实现的。因此，论文采用该种策 略。 2 2 1 2 基于小区的位置和查询管理策略 基于小区方案是受移动通信中蜂窝技术的启发。该策略中对应于蜂窝系统 的收发基站( b s ) 是位置管理的虚拟服务器( l v s ) ，对应于蜂窝系统的移动交换 中心( m s c ) 的赶全局的位置虚拟服务器。至于小区( c e i l ) 、移动设备( m u ) 的概 念，两者含义基本相同。 值得指出 0 足，无论使用哪一种位置管理策略，或者采用精度更高的定位 系统，得到的移功对象位置都是内在不精确的。因为，不可能保证数据库中的位 置信息始终与移动对象的实际位置保持一致性。文献”3 就位置更新代价和位置 信息的不确定r ：进行了权衡。 2 2 2 支持移动介淘的s o l 语言扩展 在移动数据库系统中，可能存在两种客户机：移动客户机和传统静态客户 机。因此发送到服务器上的查询可能是传统的分布式查询，也可能是移动查 华中科技大学硕士学位论文 一! ! ! = ! ! ! = ! = = = ! ! = = ! ! ! ! = ! = = = ! = ! = ! ! = ! ! ! = = = ! = = ! ! ! = ! = = = = = ! ! 询。传统的分布式查询可以看作是移动查询的特例。 移动查询的处理可能与发出查询请求的移动客户机本身相关，也可能无 关。但查询的结果集通常与时间是相关的。使用s g l 进行的常规查询是一种非 时间相关查询，它隐含着与发出查询的当前时刻相关。例如，“检索当前在多 边形p 中的所有对象”。常规s q l 若能支持时间谓词就可以完成对移动对象的 时间相关查询。比如，有下面时间相关查询q ：“检索对象对( d ，n ) ，要求是。和 ”之间的距离在5 公里之内，直到它们都进入多边形p ”。用一般的s q l 表达这 样一个时间相关的查询将非常繁琐。比如，假定对于每个谓词g ，可采用 b e g i n i m e ( g ) 和e n d t i m e ( g ) 函数来表示满足g 的第一个时间区间的起始时间和 终止时间。并假定用”n o w ”来标识当前时间，则查询q 可以表示为： r e t r i e v eo , n f r o m m o v i n g _ o b j e c t s w h e r e b e g i n _ _ t i m e ( d i s t ( o , 砂s 影sn o w a n de n dt i m e ( o l s t ( o ，叫j b e g i n t i m e ( i n s i d e ( o , 功a i n s i d e ( n , 尸”： 其中，d i s t ( o ，n ) 返回。与n 的距离，而1 n s i d e ( o ，p ) 表明0 是否在p 之 内。由此可见，如果不进一步提供时间算子，描述一个时间相关查询将非常繁 琐。这类时间相关的移动查询往往涉及到数据库的未来状态。下面将所讨论的 支持时间相关的查询语言称为s q l 扩展。s q l 扩展应安装在虚拟服务器上，通 过虚拟服务器支持带时间算子的移动查询，非时间相关查询的处理则由底层的 。d b m s 提供。 。 2 2 2 1 s q l 语言扩展的语法 移动查询往往与系统的未来状态有关。为此，跑扩展要支持与未来时间 状态有关的查询，应安装到d b m s 的顶层，且不依赖于特定的底层查询语言， s q l 扩展使用两个基本的将来时态算子u n t i l 和n e x t t i m e 。其它时态算子。如 e v e n t u a l l y ，能够用u n t i l 和n e x t t i m e 表示。这种算子可以作用于不同的类型，比 如字符串型、整型等等。假设，对每一个n 0 ，有一个一元函数符号集和n 元 关系符号集。每个n 元函数符号表示一个函数，它接收n 个特定类型的参变量， 返回一个函数值。例如， “+ ”和“”是表示整型加和乘的函数符号。同样， 华中科技大学硕士学位论文 处指用底层非时态查询语言表示的查询) 。假定所有原子查询的返回值只有一 个。例如，“r e t r i e v e ( o h e i g h t ) w h e r eo i d = 1 0 0 ；”表示找出i d 等于1 0 0 对 象的身高。原子查询中可以出现变量。 比如， “r e t r i e v e ( o h e i g h t ) w h e r eo i d = 弘”中有自由变量y ：对y 的每一个给定 值，它将取出耐由y 给定对象的身高。 查询逻辑由函数和关系符号、对象类、变量、逻辑符号n 和- 、赋 值符- 、方括号【，】、时态算子u n t i l 和n e x t t i m e 组成。 一个项( t e r m ) 是一个变量或者是其它项的组合。例如，t e r m + 1 0 仍然是一个 t e r m ；如果x ，y 是变量，厂是一个二元函数，那么厂o ，y ) 是一个t e r m ；查询 “r e t r i e v e ( o h e i g h t ) w h e r eo i d = y ；”也可作为一个t e r m 。良态 ( w e l lf o r m e d ) 子句的定义为：若 ，t 2 ，f 。是某种类型的t e r m ，r 是一个n 元关 系符，那么r ( t ，2 ，t 。) 是一个良态子句。如果，与g 是良态子句，那么 f “g ，厂u n t i lg 和( 陆+ - - t l f ) 也是良态予句，这里石是一个变量，f 是与x 同 类型的t e r m ，而且可以含自由变量；这样，可表示一个查询。s o l 扩展的查询表 现形式为： r e t r i e v e f r o m w h e r e ： 2 2 2 2s o l 语言扩展的语义 下面定义靶语言扩展的语义。假定在逻辑中所用的每一种类型都有一个 值域相对应，而且该类型的所有对象从该值域中取值。对函数和关系符的解释 沿用标准解释，例如，表示小于或等于，+ 表示标准整型加。对于一 个评价，将确定满足的查询条件。评价就是一个映射，它将值与变量联系起 来。例如算式( b4 - r e t r i e v e ( o ) n e x t t i m e ) r e t r i e v e0 x ，当0 的某种属性 的值在两个连续的数据库状态中不相等时成立。子算式r e t r i e v e0 r 的成 立与否取决于在当前数据库中针对0 的原子查询结果，也取决于x 的取值。其中 评价是将数据库状态中0 的值与x 值相关联。 华中科技大学硕士学位论文 语义解释根据算式结构进行处理。如果算式不含有时态算子和赋值量词， 那么它在某历史状态下的满足条件唯一取决于数据库中变量值和评估量。对 u n t i l g 的评估的成立，当且仅当下面两种情况之一满足：或者g 在该状态是 成立的，或者存在一个未来状态，g 成立，+ 而且直到，之后继续成立。对 n e x t t i m e 厂的评估会在下一个历史状态下成立。对( 肛- ，】厂) 的评估的成立， 当且仅当算式厂在与一个新的评估在相同状态下成立，这个新评估将f 的值赋 予x 且其它变量值保持不变。一个形如f a g 的算式成立等价于厂和g 在相同状 态下都成立；一个形如厂的算式成立等价于在此状态下不成立。在算式中还 可以使用v ( 或) ，j ( 逻辑蕴含) ，它们可用，和x 来定义。 2 2 2 3s o l 语言扩展的查询处理 将每一个动态属性4 存储为三个d b m s 属性：a v a l u e 、a u p d a t e t i m e 和 a f u n c t i o n 。任何从移动客户机发出的查询在提交到d b m s 之前，首先经过虚拟 服务器，若是传统的分布式查询( 不涉及位置属性和时态算子) 则只需将该查询 提交给底层的d b m s 即可，返回的查询结果要经过虚拟服务器转发。 现在假定查询包含对动态属性的引用，但不包含时态算子。这要分两种情 况：s e l e c t 子句和w h e r e 子旬中的引用。如果查询仅在s e l e c t 语句中包含 对一个动态属性的引用，那么虚拟服务器将它转换成取出a v a l u e ， a u p d a t e t i m e ，a f u n c t i o n ，而不是彳。 若对动态属性的引用在s e l e c t 语句中，假设w h e r e 语句为f ，它是多个 原子表达式的布尔组合。首先考虑这种情况，当且仅当只有一个原子算式p 涉 及f 中的动态属性。在将最初的查询q 传递给d b m s 之前，虚拟服务器将用两 个查询g i 和q 代替9 。这种转换是基于等式：f = f f u f ” 这里f 是使p 为真的f ，f ”是p 不为真的f 。q 和q ：定义如下，d i 和 q 的目标列表包含g 的目标列表，再加上p 中的动态属性的子属性。q 和9 中 的f r o m 语句与q 中的相同。q 1 的w h e r e 语句是f ，q ，的w h e r e 语句是 f “。q 1 和q ：都被提交给底层d b m s ，结果在返回给用户前如下处理：原子表 达式，作用于g 结果中的元组，原子表达式叩作用于级结果中的元组。不满 足各自原子表达式的元组被剔除，最终结果返回给用户。如果w h e r e 语句有多 个原子表达式涉及动态属性，那么就要循环执行上述过程，每一次处理一个含 有动态属性变量的原子表达式。没有使用动态属性索引方法时，则要检测口和 华中科技大学硕士学位论文 p 中的每个结果。如果采用动态属性索引，则不必对每个9 和q 2 的兀组避仃p 和，p 计算，而是直接取出满足p 和叩的元组，然后满足q 1 的关系与满足p 的 关系进行连接操作。同样，将满足q 2 的关系与满足妒的关系进行连接操作。 对于具有时间算子查询的处理，要将它修改为d b m s 支持的查询处理。时 态算子及其使用方法如下。 s q l 扩展的两个最基本的时间算子为u n t i l 和n e x t t i m e 。比如，表达式 fu n t i lg 成立，当且仅当下列两种情况之一成立：要么g 满足这个状态，要么 存在个将来的状态g ，其后总是满足的。表达式n e x t t i m eg 成立，当且仅当 在譬的当前状态中的下一个状态成立。 其他应支持的时间区间表达式有： e v e n t u a l l y w i t h i n ( c ，g ) ：g 将在接下来的c 个时间单元内成立。 e v e n t u a l l y a ) q e r ( c ，g ) ：g 至少在c 个时间单元后是成立的。 a l w a y s f o r ( c ，g ) ：g 将在下一c 个连续时间单元内总是成立的。 通过以上s q l 扩展，就可以完成更为复杂的查询。 2 2 3 查询结果的传送 2 2 3 1 瞬时查询和持续查询 移动性是移动数据库系统中最显著的特征之一，位置数据在位置相关查询 中成为一个重要的信息。比如在包含了静态对象和移动对象及其位置信息数据 库的酒店管理信息系统中。一个典型的查询为：一显示在我当前位置5 公里以 内的旅馆房价和可用空房信息”。这样的查询可以从移动对象( 在汽车上的移动 用户) 也可从一个静态客户机上发出。因此，位置相关查询的结果将依赖于发出 查询的移动客户机的位置。位置相关查询通常可以分为瞬时查询( 简称坦) 和连 续查询( 简称c o ) 。 假设瞬时查询的结果是由于价格太高等原因没找到满意的汽车旅馆。对于 这个查询来讲，即使数据库没有改变，查询q 的结果也随着汽车的行驶而变 化。因此，旅行者就希望查询能够带有持续性，就是说需要系统把它作为一个 持续的、在每个时钟节拍都提交的瞬时查询来处理。随着汽车的行驶，它就是 一系列在时间f t 的瞬时查询( 可以设定中止时间点来中止查询) 。如果连续查 华中科技大学硕士学位论文 一 询的结果通过屏幕反馈给用户，那么既使数据库没有改变，显不也会随看时l b j 变化( 因为客户机在移动) 而变化。显然在连续查询处理中，如何传送查询结果 也是一个十分重要的问题。 用 表示查询的结果集，其含义为对象s 是从时间b e g i n 到时 间e n d 的c q 的结果总和。一旦查询结果计算得到，就要决定如何将c q 的缉果 集传送到m u 。传送c q 结果集中的元组要考虑以下两个基本的通讯开销： 1 控制报文开销。在网络通讯协议中，每条消息都有固定大小的控制报 文，对应有相应的开销： 2 元组重传开销。对一个数据对象的更新会改变引用了该对象的元组，从 而要重传某些元组，这也存在一定开销。 假定代表移动对象s 的位置属性在时间，发生了变化，相应地，引用了s 的 元组 也进行更新( 保证元组集依然满足相应的查询) 。 与b e g i n 的关系存在两种可能： ( 1 ) ，b e g i n ( 2 ) b e g i n - 在第一种情况下，只有当元组以前曾传送到m u ，才有必要将该元组重传 到相应的m u 。在第二种情况，重传是合理的，这是因为在时刻b e g i n ，元组已 经传送给柳。 要在减少控制报文和减少重传开销间进行折中，元组传送方法是十分重要 的，特别在消息传送按字节收费的应用中更是如此。比如，r a m 移动数据公司 按每条消息最少4 美分收费“，而附加费用按消息的大小收取。显然，给定c o 查询结果的个元组集，不同的元组传送方法产生的费用不同。 元组传送方法也影响m u 处于睡眠模式的时间长短。传送次数和m u 用于 侦听通信通道的全部时间应最小以减少m u 能量的消耗。因为m u 只有有限的 电源容量，正常使用只有2 到