移动对象数据库第三章.ppt

《移动对象数据库第三章.ppt》由会员分享，可在线阅读，更多相关《移动对象数据库第三章.ppt（109页珍藏版）》请在金锄头文库上搜索。

1、上海海事大学信息工程学院本章我们从位置管理的视角来考虑移动对象数据库。假设我们需要在数据库中管理一些移动对象的集合（小汽车，直升机，手持移动电话的人等），而这些移动对象正在运动，我们希望检索这些移动对象的当前位置，还有它们当前如何移动的信息，未来位置的查询。3.1：讨论一些基本的假设和问题3.2：介绍MOST（移动对象时空）数据模型3.3：FTL(未来时态逻辑)的查询语言3.4：移动对象向数据库发送自己当前位置和移动速度的实际和频率问题3.5：不确定轨迹问题许多应用都需要记录移动对象位置的轨迹。例如：u在一个存储了某个城市所有出租车位置的数据库中，一个查询可能是：检索出接近Kongigsall

2、ee48(用户请求查询的位置)的3辆空闲出租车u运输公司数据库：哪些卡车距离卡车T48(可能这辆车需要帮助)在10公里之内u接下来的15分钟之内到达峡谷的友军直升机本章提出的基本思路是通过运动矢量而不是通过对象的位置来表示和存储移动对象(即对象的位置是时间的一个函数)，即使数据库没有任何显示的更新，数据库中所表示的位置也是连续变化的，虽然仍需偶尔更新运动矢量，但与存储位置的方式相比，它的更新频率要小的多。运动矢量不是显示可见的，所以引入新的概念“动态属性”。动态属性的值随时间而改变，因此得到的查询结果也会随时间而变化：相同的查询在不同时间里执行通常会产生不同的结果，即使数据库中的内容没有改变。

3、 例：假设一辆小汽车在高速公路上行驶时驾驶员发出一个查询：检索出距离我当前位置5公里之内的便宜的汽车旅馆，此时连续地重复计算这一查询是有意义的，因为当小汽车行驶时该查询结果会随之变化。然而，在传统数据库中连续查询（如触发器）必须在每一次相关更新时重新计算，但是并没有明确说明该如何执行连续查询。后面内容中，我们将描述一种执行策略，该策略仅需要对连续查询计算一次，并且只在显示更新是才需要重新计算查询。 运动矢量所表示的对象运动在通常情况下无法准确表示真实的运动。我们将数据库中的位置和真实位置之间的距离定义为偏移。假设移动对象通过一次更新将真实位置和速度发送了数据库，在这一更新时间偏移是0，之后偏移

4、会随着时间逐渐增长。对于数据库而言，不仅需要知道给定时间里对象的预计位置，而且要知道可能的偏移范围。为限制对象位置的偏移以及不确定性的范围，假设在移动对象和管理对象位置的数据库之间存在着一个“约定”：无论何时，当偏移达到某给定阈值，移动对象就给数据库发送一个更新通知报告自己的位置和速度。MOST针对当前和未来的移动的数据模型在移动对象的位置模型中具有代表性的成果有移动对象时空(MOST)模型和移动对象离散数据模型。 MOST模型是由美国Illinois大学芝加哥分校的Ouri Wolfson及其研究小组提出的。它引入了动态属性的概念，动态属性将移动对象的位置表示为时间的函数，这样在移动对象正常

5、运动时，无需对其位置信息反复更新，仅在发生异常情况，如速度突然变化或运动线路发生改变时才进行数据库更新。 然而MOST模型也存在着一定的局限。由于简单函数的表达能力有限，动态属性只能表达移动对象在未来较短时间内的移动轨迹，而对较长时间移动对象轨迹的表示就显得无能为力了。为克服这一缺陷，意大利Aquila大学的Luca Forlizzi等人提出了移动对象离散数据模型，它将复杂的空间对象及移动轨迹分割为相对简单的离散片段，为表示和处理复杂移动对象提供了一种可行的解决方案。 数据库是一个对象类的集合，每个对象类有一个属性集合。假设存在可用的空间数据类型，例如点，线和多边形以及这些数据类型上相应的操作

6、。一些对象类被指定为空间对象类，意味着他们有个表示空间值的属性，例如一个点或者一个多边形。这时对象本身被称为一个点对象或多边形对象。对空间值的操作也可以直接应用到这些对象上。例如，如果有两个点对象p1,p2以及一个多边形对象pol,可以应用空间操作如DIST(p1,p2)得到两个点p1,p2之间的距离，或者用INSIDE(p1,p0l)来判断点p1是否位于多边形pol之内。注：对于所有这些工作，要求每一个对象必须只有一个空间属性。即是：假设每一个空间对象类是点类，线类和多边形类三者之一。MOST模型对点对象尤其感兴趣。第一种点对象建模的方法是赋予他们一个特殊的属性pos，该属性依次包含两个部分

7、(成为子属性)，表示为pos.x,pos.y（假设是二维坐标系统）。子属性的数据类型可以是int或者real类型。除了对象类之外，数据库还包含一个特殊对象Time，它表示了在任一时刻的当前时间。时间是离散的(即时间域是自然数，用int类型表示)，时间对象的值每一个时钟周期加1.MOST模型中最基本的创新思想是所谓的动态属性。对象类的每个属性被分为静态属性或动态属性。静态属性与通常属性一样，动态属性则随着时间自动改变属性值。并不是所有属性类型都适合扩展为动态属性。这样的数据类型（指能够扩展为动态属性的数据类型）要求必须具有0值和一个加操作。这一要求对于数值类型如int和real是成立的，也可以扩

8、充到point这样的类型上。例：一个描述小汽车在xy平面上自由运动的对象类模式Car(license_plate:string,pos(x:dynamic real,y:dynamic real)类型T的动态属性A(表示为A:T)可以通过3个子属性来形式化地表示，A.value、A.updatetime和A.function。A.value:类型是TA.updatetime:一个时间值A.function:一个函数,即f:intT,并满足t=0时,f(t)=0.表示的语义为”A在时间t时的值”,并且定义如下Value(A,t)=A.value+A.function(t-A.updatetime

9、), ( t=A.updatetime)一个位置更新操作将A.updatetime设置为当前的时间值，并改变A.value，或两者一起改变。一个查询也可能直接涉及动态属性的子属性，此时我们需要访问动态属性的内部结构。例如，用户可能会请求满足pos.x.function=5(意指f(t)=5t)的对象，从而查找到x方向上速度为5的对象对于交通而言，更实际的假设是它们都沿着路网移动。第二种建模方法是用一个具有6个子属性的loc属性，分别是loc.route，loc.startlocation, loc.starttime, loc.direction, loc.speed, loc.uncerta

10、intyloc.route：是一个线空间对象(指针)，它描述交通网络上某一个路径的几何性质(即对象移动的路线)loc.startlocation：loc.route上的一个点，它是移动对象在loc.starttime时的位置loc.direction：是一个布尔值，表示对象移动的路线方向 loc.speed：一个函数f，它与自上次位置更新后(loc.starttime开始)所消耗的时间一起给出了对象与loc.startlocation之间的距离。假设每次位置更新都将设置loc.starttime,并将loc.startlocation设置为该时刻的位置。同样,要求 f(0)=0.多数简单情况下

11、，loc.speed存储的是一个常量v，因此，在时间loc.starttime+t时，对象与loc.sartlocation之间距离是v*tLoc.uncertainty是一个常量，或是有自上次位置更新以来所消耗时间单位数的函数，它代表对象偏移的阈值。无论何时，只要达到阈值，对象就会发送一次位置更新。uLoc属性的语义同样是平面上一个时间相关的位置(x,y),只不过它正好位于网络上。u在loc.starttime时，它的位置是loc.startdirection；在loc.starttime+t时，它在loc.route上沿着loc.direction方向与loc.startlocation相

12、距loc.speed*tu查询求解也可以考虑不确定性，即对象m在时间t时的位置查询结果可能是这样：对象在路线loc.route上的位置不确定性loc.uncertainty达到最大时位于位置(x,y)之前或之后。数据库状态是一个对象类和对象之间以及Time对象与时间值之间的映射，该映射将每个对象类和一组具有适当类型的对象相关联，同时将Time对象与某个时间值相关联。对数据库中的任意对象o,我们用o.A表示o的属性A，如果A有个子属性B可以表示为o.A.B。在数据库状态s下o.A的值表示为s(o.A),s(Time)给出了数据库状态s的时间值。每个动态属性在状态s下的值为value(A,s(Ti

13、me)。数据库历史：是由每个时钟周期的数据库状态所组成的一个无限序列，它开始于某一时间u并延伸至无限的将来即su,su+1,su+2,st-1,st,st+1 st+2,接着，从时间t开始的历史为su,su+1,su+2,st-1,st,st+1 ,st+2,所以，对于每个时钟周期，我们都会得到一个新的数据库状态，并且对于每一次更新，我们都会得到一个新的数据库历史。我们用Hu,k表示从u到u+k为止的一段历史(即直到时间u+k,才完成全部更新)。Hu,0=Hu，并且t=u+k,更新前历史是Hu,k-1，更新之后的历史是Hu,k假设当前的时间为t，用Q(H,t)表示在数据库历史H上进行求解的一个

14、查询Q。在时间t时提交的即时查询Q求解为：Q(H,t)这表明如果当前时间为t，则即时查询是在起始时间为t的数据库历史上进行求解。即时查询并不意味着它只会用到当前的数据库状态。例如：“找出我可以在10分钟内到达的所有汽车旅馆”，这一查询将涉及从当前时间到10分钟之后这段时间里的所有数据库状态。对于在时间t时提交的连续查询Q，我们以一个查询序列来求解Q(Ht ,t ),Q(Ht+1 ,t+1),Q(Ht+2,t+2),一个连续查询在每个时钟周期里都以即时查询的方式重新进行计算。对于某个时刻u，我们可以得到有效的即时查询结果Q(Hu,u)。一个连续查询的结果所显示的内容可能自动变化，并不需要用户的交

15、互。可以通过对一系列元组都增加一个时间戳标记来实现。元组的时间戳表明它属于查询结果集的时间区间。随着时间的推移，一些元组的时间区间开始满足查询条件，则被加入到查询结果集，另一些元组时间戳过期，于是从结果集中移除它们。第三种类型的查询是持久查询。这种查询的产生动机源于这样一个事实，即目前的连续查询还不能识别某些特殊类型的演变过程。例如：Q=“找出所有5分钟之内速度增加了一倍的小汽车”假设该查询以连续查询的方式在t=20(假设时间单位是分钟)时提交。设o表示一个小汽车，它的o.loc.speed=40，假设o的速度在t=22时被显式更新为60，在t=24时更新为80.当计算连续查询Q(H20,20

16、)时，由于在所有将来的状态中o的速度都是40，o不会出现在结果集中。当计算Q(H22,22)，所有将来的状态中o的速度都是60，o不会出现在结果集中。同理t=24时o也不会出现在结果集中。对于在时间t时提交的持久查询Q，以一个查询序列来进行求解：Q(Ht,0,t), Q(Ht,1,t), Q(Ht,2,t),即一个持久查询所以，持久查询就是时间t开始的数据库历史上的一个连续计算，当数据库历史由于显式更新而改变时，其查询结果也会随之而改变。如上例，在计算上面查询序列第5个查询Q(H24,20),可发现时间20到24速度已经翻倍，所以o被作为查询结果返回。注：我们并没有在每个时钟周期里都重新计算查

17、询，仅在每次更新时才计算，因为更新可能会影响查询结果，这和连续查询的处理方式是一样的。FTL-基于未来时态逻辑的查询语言例3.1 哪些卡车距离卡车T68不超过10公里RETRIEVE tFrom trucks t,trucks sWhere s.id=“T68”dist(s,t)10查询的一般形式RETRIEVE FROM WHERE FTL语言只能用来处理即时查询，FTL语言一般不支持将一个连续查询的方式进行计算，一般必须要在语言外部进行说明（例如用户接口中）例3.2 卡车T70是否会在半小时之内到达目的地？假设目的地表示为一个点对象类destinations，所有点都位于交通网络上。卡车对

18、象的dest属性指明它的目的地，这个属性是对目的地对象的引用。RETRIEVE tFrom trucksWhere t.id=T70eventually_within_30(dist(t,t.dest)=0)neventually_within_c :一个新时态操作符c是关于时间单位的数字常量，可用在谓词p中neventually_within_c(p)意思是：在接下来的c个时间单位内，谓词p将为真例3.3 检索将会在15分钟之内到达峡谷并在峡谷至少停留5分钟的友军直升机RETRIEVE tFrom helicopters hWhere eventually_within_15 (inside

19、(h,Valley)always_for_5(inside(h,Valley)nValley是一个多边形对象nInside操作比较一个点对象是否包含在一个多边形对象内定义3.1 FTL语言由如下符号组成：(1)常量。常量是原子数据类型（例如54、“T68”）或数据库中的命名对象（例如，Valley），Time也是常量。(2)对每个n0,有一个n元函数符号集。每个函数符号表示一个具有n个不同类型参数并返回某个特定类型值的函数。例如int类型上的+、操作，它输入某个对象类的一个对象和一个属性名并返回一个该属性类型的值。(3)对每个n0,有一个n元谓词符号集，每个谓词表示n个特定类型的参数之间的联系

20、。例如，表示通常的算术比较操作(4)变量。变量是类型化的，并且可以使用所有对象类或原子类型。例如，h truck是使用了truck类的变量，又如jint是一个整形变量(5)逻辑连接符和(6)赋值量词(7)时态模型操作符until和nexttime(8)括号和标点符号“(”、“)”、“”、“”、“，”MOST模型和FTL语言可以在提供非时态查询语言实现（如OQL）的DBMS上实现。FTL允许将所谓的原子查询嵌入到底层查询语言之上。如：RETRIEVE d.name FROM destinations d WHERE d.id=d12 返回一个string类型的值。这种原子查询被看作一个常量符号。

21、这种查询也可含有变量：RETRIEVE d.name FROM destinations d WHERE d.id=y这个带有一个自由变量的查询可视为一个函数符号，表示了一个给定参数返回一个string值的一元函数定义3.2 下列之一的元素称为一个项：(1)一个常量c(2)一个变量v(3)一个属性访问v.A(4)一个应用到若干具有适当类型的项上的函数f(t1 , tn)例：10、x+3、dist(x,y)和d.name和“RETRIEVE d.name FROM destinations d WHERE d.id=y”都是项定义3.3 一个合式公式的定义如下(1)如果R是一个n元谓词符号，且t

22、1 , tn是具有适当类型的项，则R(t1 , tn)是一个合式公式(2)如果f和g是合式公式，则fg和g是合式公式(3)如果f和g是合式公式，则f until g和 nexttime f 是合式公式。(4)如果f是合式公式，x是一个变量，且t是一个与x类型相同的项，则(xtf)是一个合式公式。如果公式中的变量没有出现在形如xt的赋值量词中，我们称该变量是自由的。注：FTL中没有一阶谓词逻辑中的全称和存在量词。但是赋值量词允许将一个变量绑定到数据库历史某个状态的一个查询结果上。特别地，它可能会在某个时间点及时捕获一个原子值并在稍后的时间点及时将该原子值关联到其他值上。定义3.4 公式f的一个变

23、量赋值是一个映射,它对f中每个自由变量都赋一个取自其所在域的值。我们用x/u表示一个从中得到的映射，该映射对变量赋值u，同时保持其他的变量不变。例3.4 假设在例3.1的truck对象类中，存在着对象标识符从T1到T100的若干卡车对象。对于如下公式：s.id=T68dist(s,t)10一个可能的变量赋值是=(s, T10)(t,T20)定义3.5 给定一个变量赋值，状态s下项t的计算过程表示为s,t,定义如下：(1)如果t是一个常量c，则s,c=s(c)(2)如果t是一个变量v，则s,v= (v)(3)如果t是一个属性访问v.A，则s,v.A= s(v.A)(4)如果t是一个应用到参数t1

24、 , tn 的函数，则s,f(t1 , tn )=f(s,t1,s,tn)注意：常量是在某个特定的数据库状态中计算的，而常量Time的计算尤其需要这样一个数据库状态。此外，动态属性的计算也是和数据库当前状态相关的。定义3.6 给定一个变量赋值，公式f在数据库历史H中的某个数据库状态s上是满足的(简称在(s, )处满足)：(1)R(t1 , tn ) 是可满足的:R(s,(t1 ) , s,(tn )成立。(2)如果f g是满足的:f和g都在(s, )处满足。(3)f是满足的: f在(s, )处不满足(4) f until g是满足的: g在(s, )处满足,或在历史H存在一个未来状态s并满足(

25、g在（s , )处满足对所有历史H中早于状态s的状态si,f在(si,)处满足)(5)nexttime f是满足的:f在（s , )处满足，这里s是历史H中紧接着s的状态。(6)(xtf)是满足的:f在(s, x/s,t)处满足例3.5 公式(xdist(a,b)(nexttime dist(a,b)x)的计算过程如下:这里我们假设这一公式是在状态s处计算的，并且s是s的下一状态。(xdist(a,b)(nexttime dist(a,b)x)在状态s处满足 (nexttime dist(a,b)在状态s处满足，这里 是在状态s处满足对象a和b之间的距离 (dist(a,b) )在状态s 满足

26、 ( ),这里实在状态s处对象a和b之间的距离因此，如当前状态改变到下一个状态时对象a和b之间的距离是递增则公式满足的时态操作eventually和always可以像下面这样定义：n eventually g:指g将在某个未来状态处成立，我们可以将其定义为true until gn always g:指g在所有未来状态处都满足，包括当前状态。它可定义为(eventually(g) ) 使用具有有界时间区间(不是无限时间区间)的相关操作符也是有益的。定义until操作符的有界版本:n g until_within_c h断言从现在开始至多c个时间单位内存在一个未来时间使h成立，并且在这个未来时间

27、之前g一直都是满足的ng until_after_c h断言从现在开始至少c个时间单位内存在一个未来时间使h成立，并且在这个未来时间之前g一直都是满足的neventually_within_c g断言g将会在从现在开始的c个时间单位内成立，定义为 true until_within_c gn eventually_after_c g断言g至少在c个时间单位后才成立，定义为 true until_after_c gn always_for_c g断言g将会在从现在开始的c个时间单位内一直成立，定义为 g until_after_c truenf until g是满足的 g在(s, )处满足,或在

28、历史H存在一个未来状态s并满足(g在（s , )处满足对所有历史H中早于状态s的状态si,f在(si,)处满足)nnexttime f是满足的f在（s , )处满足，s是历史H中紧接着s的状态。neventually g g将在某个未来状态处成立，我们可以将其定义为true until gn always g g在所有未来状态处都满足，包括当前状态。它可定义为(eventually(g) )ng until_within_c h 断言从现在开始至多c个时间单位内存在一个未来时间使h成立，并且在这个未来时间之前g一直都是满足的ng until_after_c h 断言从现在开始至少c个时间单位内

29、存在一个未来时间使h成立，并且在这个未来时间之前g一直都是满足的neventually_within_c g 断言g将会在从现在开始的c个时间单位内成立，定义为 true until_within_c gn eventually_after_c g 断言g至少在c个时间单位后才成立，定义为 true until_after_c gn always_for_c g 断言g将会在从现在开始的c个时间单位内一直成立，定义为 g until_after_c true合式公式是这样构造的:n没有否定n没有nexttime操作符n没有任何对Time对象的引用 去除否定是为安全，即保证查询结果的有限性，因为

30、否定可能引入无限的结果。去除带有时间变量的条件，意味着对于每一个出现在公式f中赋值量词右边的查询q(即，形如x),任何时候求解q所返回的值独立于时间。它仅返回对q中自由变量赋值后再应用函数所产生的结果，且它仅依赖于对象的当前位置。 这一条件保证了当对象在某个特定位置时，一个非时态谓词的满足性只和对象的所在位置相关，而与对象到达该位置的时间无关。但我们允许像eventually_within_c这样的有界时态操作符。因为我们不能使用Time，因此求解算法必须显示地处理两个基本操作符until_within_c和until_after_c另一个约束条件是，只允许处理即时查询和连续查询，不包括持久查

31、询。求解FTL公式的基本思路:对每个具有自由变量x1,xk的公式f构造并计算一个关系Rf(x1,xk, tstart,tend).在这个关系中,f中每个自由变量都有一个对应的属性,另外还有描述时间间隔的两个属性tstart,tend。Rf 的每个元组(o1,ok,t1,t2)表示对自由变量x1,xk的一个实例化=,并且在t1,t2这个时间间隔里该实例所对应的公式f为真。更进一步，如果两个元组对变量x1,xk的实例=相同,那么它们的时间间隔既不能相同也不能相连。具有相同实例的元组集合T和它们的时间间隔集合I表示了多个对象的一个组合，该对象集在时间I期间满足公式f。根据定义3.3(合式公式的定义)

32、可知，一个FTL公式是由若干子公式构造而成的。求解的想法就是首先确定原子公式的关系，再自底向上求解，求解时我们将连接符转换为相应的关系操作。定义3.7 (在有限制的情况下)合式公式定义如下:(1)如果R是一个n元谓词符号，且t1 , tn是具有适当类型的项，则R(t1 , tn)是一个合式公式(2)如果f和g是合式公式，则fg也是合式公式(3)如果f和g是合式公式，则f until g是合式公式。(4)如果f和g是合式公式，则f until_within_c g是合式公式。(5)如果f和g是合式公式，则f until_after_c g是合式公式。(6)如果f是合式公式，x是一个变量，且t是一

33、个与x类型相同的项，则(xtf)是一个合式公式。如果公式中的变量没有出现在形如xt的赋值量词中，我们称该变量是自由的。定义3.7 (在有限制的情况下)(1)如果R是一个n元谓词符号，且t1 , tn是具有适当类型的项，则R(t1 , tn)是一个合式公式(2)如果f和g是合式公式，则fg也是合式公式(3)如果f和g是合式公式，则f until g是合式公式。(4)如果f和g是合式公式，则f until_within_c g是合式公式。(5)如果f和g是合式公式，则f until_after_c g是合式公式。(6)如果f是合式公式，x是一个变量，且t是一个与x类型相同的项，则(xtf)是一个合

34、式公式。如果公式中的变量没有出现在形如xt的赋值量词中，我们称该变量是自由的。定义3.3 (1)如果R是一个n元谓词符号，且t1 , tn是具有适当类型的项，则R(t1 , tn)是一个合式公式(2)如果f和g是合式公式，则fg和g是合式公式(3)如果f和g是合式公式，则f until g和 nexttime f 是合式公式。(4)如果f是合式公式，x是一个变量，且t是一个与x类型相同的项，则(xtf)是一个合式公式。如果公式中的变量没有出现在形如xt的赋值量词中，我们称该变量是自由的。设h是具有自由变量x1,xl的一个子公式.第1种情况:h R(x1,xl)例如:h dist(x1, x2)

35、8假设对于每一个这样的原子谓词以及一个可能的实例化,都有一个算法可以返回当谓词成立时的时间间隔。对所有这样的元组以及与其相关联的时间间隔，可以计算得到一个关系Rh 。设Rf和Rg是根据子公式计算得到的两个关系，例如： Rf(x1,x2,x5, ts,te) Rg(x1,x4,x5, x7,ts,te)此时，得到的结果关系具有如下模式: Rh(x1,x2,x4,x5, x7,ts,te)假设对于实例,f在I1上满足且g在I2上满足。因此，通过计算Rf和Rg的连接结果得到结果关系Rh。 Rf和Rg的连接条件是相同的变量必须相等，同时时间间隔必须相交；每个结果元组的时间间隔为两个连接元组的时间间隔的

36、交。设Rf和Rg是根据子公式计算得到的两个关系,分别具有p+2和q+2个属性。考虑Rf的元组t1，设T1是在前p个属性值相同的所有元组的集合（即实例化相同的元组）。设I1是T1中的时间间隔集。类似，对Rg中的t2、T2以及I2做同样的假设。图为两个时间间隔有重叠的元组t1和t2如果f对于t1时间间隔上的实例化是成立的，则f until g在t1和t2时间间隔的并上成立。 t1 (f成立) t2 (g成立) ( f until g成立)下图这两个实例在时间间隔I1和I2上的完整集合t1 f成立t2 g成立 f until g成立而根据f until g的语义， f until g在t1和t2的时

37、间间隔链所对应的时间区间上是成立的，这里的时间区间起始于t1的某个时间间隔，终止于t2的某个时间间隔的右端。所以，按如下方法计算Rh ：根据变量的实例化结果计算Rf和Rg的连接并得到匹配的元组对集合。对于得到的两个时间间隔集I1和I2，计算它们的时间间隔极大链。对于每个极大链，构造一个结果元组，它的时间间隔等于该极大链的时间范围。另一种计算方法是：对任何有重叠的时间间隔对t1 和t2，计算它们的重叠结果，然后将所有的重叠结果合并成一个时间间隔，并将它们放入结果元组中返回。f until_within_c g断言从现在开始至多c个时间单位内存在一个未来时间使g成立，并且在这个未来时间之前f一直都

38、是满足的。设t1,t2是Rf和Rg中具重叠时间间隔的匹配元组对,d=maxt1.l, t2.l-c,则f until_within_c g在时间间隔d, t2.u上成立。下图说明了这种情况：Q是一个产生原子结果的查询。例如：y height(o)设Rf为f结果关系。项q是一个一般查询,能产生一个原子结果，以保证它可以赋给y，它通常含有一些自由变量。假设由yq产生的结果关系Rq 有p+3个属性,其中前面p个属性与q中的自由变量相关，第(p+1)个属性存储q的值，剩下的两个属性表示一个时间间隔。q 中自由变量的每一次实例化都会产生一个结果值，并存储在第(p+1)个属性中。如果这个实例化结果值在n个

39、不相交的时间间隔上都成立，那么我们就在Rq中存储n个相应的元组。我们有一个例子：(h yqf) Rq 有四个属性。第一个属性保存了对象标识，第三个和第四个属性描述了一个时间间隔，第二个属性给出了对象在这个时间间隔中的高度。h的结果关系Rh是由Rq和Rf连接得到的，连接条件是“对于Rq 中的元组t1和Rf中的元组t2,它们相同变量上的属性值相等，并且Rf中相应的y属性值等于t1中的查询结果值，同时t1和t2的时间间隔相交”。输出的结果元组包含了t1和t2中所有的变量属性值，除了对应变量y的属性以及t1和t2时间间隔的交。结果关系Answer(Q)可以按下面的方式来回答连续查询和即时查询。对一个时

40、钟周期t时的连续查询Q，如果实例化后元组的时间间隔包含t，则将这些元组显示给用户。例如，假设Answer(Q)包含元组(2,10,15)和(5,12,14),那么id=2的对象在时钟周期10和15之间显示给用户，而id=5的对象在时钟周期12和14之间显示给用户。对于即时查询Q，如果实例化元组的时间间隔包含当前时钟周期，则作为结果显示。位置更新-平衡更新代价和不精确性运动的空间对象需要将它们当前位置和速度的更新传送给数据库，为了数据库中的检索和查询提供最新的信息，并可以将查询结果的不确定性限定在一定范围内。频繁更新会导致过高代价并会影响性能，低频率更新可能导致位置查询返回过时的数据。另外，由于

41、对象位置存储在数据库中（即数据库位置），它们不可能和对象实际位置完全一致。因此，移动对象的位置具有固有的不精确性。无论我们使用什么样的策略更新对象的数据库位置，这种不精确性总存在。这一节，我们介绍推测定位策略。其定义为：无论何时只要对象的实际位置和其数据库位置的距离超过一个给定的阈值th(100米)就执行一次数据库更新。因此，这个阈值决定并且限定了位置不精确性的范围不确定性引出的两个相关但不同的概念：偏离和不确定性。移动对象m在特定时刻t的偏离是指t时刻m的实际位置与它的数据库位置之间的距离。在我们的例子中，偏离是指m的实际位置和(x,y)之间的距离。移动对象m在特定时刻t的不确定性是指包含m

42、所有可能的当前位置的区域大小。在我们的例子中，不确定性是以100米为半径的一个圆区域的大小。偏离(不确定性)的代价与偏离(不确定性)的大小成比例。因为移动对象通常装备有全球定位系统(GPS),因而可以生成位置更新并通过无线网络发送给数据库。这引入了第3个代价因素：通信或传输代价。通信代价和不精确性之间存在着一种显然的折中关系，因为通常通信代价越高，不精确性就越低。由此引出移动对象数据库中的信息代价模型问题。信息代价模型用来平衡不精确性和更新代价，同时它也能处理移动对象连接断开并且不能发送位置更新情况。移动对象的偏离代价依赖与偏离的大小以及它所持续的时间。偏离的大小影响着决策过程，偏离越大，则根

43、据移动对象当前位置做出可靠决策的难度越大，不精确性越高。假设每个时间单位里有一个检索移动对象位置的查询。如果偏移持续了n个时间单位，那么它的代价就是持续一个时间单位的偏离代价的n倍，因为所有n个查询(而不是一个查询)都必须接受偏离的惩罚。形式化地，对于一个给定移动对象，在开始时间t1和终止时间t2之间的偏离代价可通过一个返回非负数值的偏离代价函数COSTd(t1,t2)加以描述。假设在一个时间单位里偏离一个单位的惩罚权重是常量1，则偏离代价函数可以定义为COSTd(t1,t2)=t2t1d(t)dt d(t)表示偏离是一个时间的函数,是一个单值的偏离代价函数。在这种函数中，当一个时间单位中的偏

44、离低于给定的阈值th时，所产生的惩罚是0，否则产生的惩罚是1.更新代价C1是将一条位置更新信息从移动对象传送到数据库的代价。不同的移动对象可能有不同的更新代价，甚至同一个移动对象在同一次运动过程中也可能会有不同的更新代价(例如由于带宽、计算能力等资源的可获得性发生了变化)。一个时间单位中的更新代价和偏离代价之间的比率等于C1，因为我们已假设后者的代价是1。我们可得出结论：为了在一个时间单位里将偏离减少1，移动对象将需要传送1/C1条消息。不确定性代价依赖于不确定性的高低和它所持续的时间。不确定性越高，在回答查询时传递的可靠信息越少。对于一个给定的移动对象，在开始时间t1和终止时间t2的不确定性

45、代价可以通过一个返回非负数值的不确定代价函数COST(t1,t2)加以描述。设C2是一个不确定性单位的代价和一个偏离单位的代价之间的比率，因为我们假定了后一个代价等于1.所以，不确定性代价函数COST(t1,t2)可这样定义:COST(t1,t2)= C2u(t)dt u(t)是移动对象的属性loc.uncertainty的值，它是时间的一个函数。我们对不确定性和偏离因素的权重乃至重要性进行一些干预。对于回答查询”移动对象m当前位置是(x,y),其最大偏离是u个单位”，则强调结果的不确定性，则C2 应设置为大于1，否则小于1.在推测定位更新策略中，每一次发送给数据库的更新消息决定了一个新的不确

46、定性，但它并不一定比之前的值小。因此，增加通信可以减少偏移，但不一定能够减少不确定性。设t1和t2是两个连续的位置更新消息的发送时间，则在半开的时间间隔t1,t2)里的信息代价是COST1 (t1,t2)=C1+COSTd(t1,t2)+COSTu(t1,t2)这个结果包括了t1时的消息传送代价，但没有包括t2时的消息传送代价。因为每次位置更新消息都把移动对象的实际位置写入数据库，因此偏离就降低为0了。总的信息代价是汇总每一对连续更新时间t1和t2所对应的COST1 (t1,t2)值而得到的.设t1 , tn是移动对象所有更新消息的发送时间，移动对象运动开始时间为0，终止时间为tn+1，则移动

47、对象该次运动过程的总信息代价为COST1 (0, tn+1)= COSTd(0, t1)+ COSTu(0, t1)+本节考虑的是信息代价优化的问题。任意时刻都存在一个阈值th是所有推测定位更新策略的本质特征。我们根据移动对象的当前位置m和它的数据库位置之间的距离来检查这个阈值，所以数据库管理系统和移动对象都应当保存th的信息。当m的偏离超过了阈值th，m就向数据库发送一条位置更新信息。该信息包含了m的当前位置、预计速度和一个新的偏离阈值K.推测定位策略的目标是确定一个能够使总信息代价最小的阈值K，K存储在数据库管理系统的loc.uncertainty子属性中。首先，m可以预测偏离的未来行为和

48、方向。基于这一预测，我们计算从现在到下一次更新之间每个时间单位的平均代价f，并把f定义为新阈值K的一个函数。然后设置K使f最小化。优化策略与每个时间单位的平均代价相关，但与两个时刻t1和t2之间的总代价无关，因为总代价是随着时间间隔的延伸(直到下一次更新)而不断增加。如果两个连续更新之间的偏离可表示为一个时间的线性函数，我们可以为loc.uncertainty确定一个最优的K值。C1 表示更新代价, C2表示不确定性代价.t1和t2是两次连续位置更新的对应时刻.t1和t2之间的偏离为d(t)=a(t-t1),其中且a是一个正数常量。 loc.uncertainty的值为K，并且这个值在t1和t

49、2之间是固定不变的。结论是当时，在t1到t2的时间间隔里每个时间单位总信息代价最小。这个结论说明如下：我们以时间间隔t1,t2)中的信息代价计算公式为基础，得到如下公式：设f(t2)= COST1 (t1,t2)/(t1,t2)表示在更新时间t1 时t1和t2之间的每个时间单位的平均信息代价。因为t1和t2是两个连续的更新时间，所以在t2时偏离超过了阈值loc.uncertainty,因此K=a(t2-t1).用K/a+t1替换f(t2)中的t2得到f(K)=a C1/K+(0.5+ C2)K.通过推导，可得到当时f(K)取最小值。最后，我们检测移动对象和数据库之间连接断开的情况。此时移动对象

50、无法向数据库发送位置更新信息。我们需关注另一种推测定位策略。不确定性阈值loc.uncertainty在两次更新之间是持续减少的。举例说明，一个从常量K开始缓慢减少的阈值loc.uncertainty。这意味着自位置更新u之后的第1个时间单位里阈值是K，在u之后的第2个时间单位里阈值是K/2，在u之后的第i个时间单位里是K/i，这样一直持续到下一次更新，那时将确定一个新的K值。假设已知偏离的线性行为，则函数f(K)=(C1+0.5K+C2K(1+1/2+1/3+1/ )/位置更新策略是决定移动对象何时将什么样的实际位置更新值传送给数据库的规定或策略.该策略设置一个保存在loc.uncertai

51、nty子属性中的偏离上界(即阈值th),并使得总信息代价最小.速度推测定位(speed dead-reckoning,sdr)策略.在移动对象m开始运动时,它以某种特别的方式确定一个不确定阈值,并将它传送到数据库的loc.uncertainty子属性中.此阈值在整个运动过程中保持不变,并且无论何时移动对象m的偏离超过了loc.uncertainty,就更新数据库,更新信息包括m当前位置和当前速度.如果使用另外一种类型的速度值(例如,从上次更新以来的平均速度,自运动开始以来的平均速度,或者基于地形只是所预测的速度等),灵活性更好.自适应推测定位(adapative dead-reckoning,

52、adr)策略初始时与sdr策略类似，在开始运动时移动对象m任意选择一个偏离阈值th1并发送给数据库。此后m监视偏离情况，一旦偏离超过阈值th1就给数据库发送一条更新信息。更新消息包括当前速度，位置以及一个存储到loc.uncertainty属性中的新阈值th2 th2计算方式如下：假设t1表示从运动开始到偏离第一次超过th1时所经过的时间单位数量，I1表示这段时间里的偏离代价，并假设a1=2I1/t12.随后，有th2= 其中C1更新代价，C2是不确定性单位代价。当偏离达到了th2,m就会再次发送一个类似的更新。此时th3= 这里a2=2I2/t22. I2是从第1次更新到第2次更新这个时间间

53、隔内的偏离代价，t2是自第1次更新以来所经过的时间单位数量.就是说a1和a2的不同导致了th2和th3的不同.sdr策略以某种特定方式来确定阈值，adr策略是基于代价来确定阈值。在每一次更新时刻pi,adr策略优化每个时间单位的信息代价，并假设pi后面的偏离行为是一个线性函数d(t)=2tIi/ti2。t是pi之后所经过的时间单位数量， ti 是从上次更新到当前更新时刻pi之间的时间单位数。Ii是在同样时间间隔内的偏离代价adr通过一个斜率为2Ii/ti2的线性函数来模拟从上次更新到pi时刻的偏离代价，该函数在pi时刻的偏离代价(即Ii)与实际偏离代价是一致的；根据局部性原则，pi之后的adr

54、策略可以根据同一个近似函数的得到预测的偏离行为。断开检测推测定位(disconnection detection dead-reckoning,dtdr)策略。该策略回答了由于移动对象与数据库的连接断开(而不是由于偏离没有超过不确定性阈值)而导致没有产生更新的问题。在开始运动时，m向数据库发送一个任意的初始阈值th1。然后在第1个时间单位里，规定不确定性阈值loc.uncertainty从th1开始减少。在第2个时间单位里，不确定性阈值是th1/2，然后一直持续下去。接着m开始跟踪偏离。在t1时刻，当偏离达到当前不确定性阈值(即th1/ t1)时，m给数据库发送一条位置更新信息。该更新消息包含

55、当前速度，位置和一个新阈值th2并存储在loc.uncertainty子属性中。使用函数来计算th2因为f(K)使用了未来偏离的斜率参数a，所以我们首先估计这个偏离。设I1为运动开始以来的代价，a1=2I1/t12我么用ln( )来近似表示求和式1+1/2+1/3+1/由于ln(n)是第n个调和数的近似值。f(K)的近似函数就是g(K)=当K是等式ln(K)=d1/K-d2的解时，g(K)的偏离是0，这里d1=2C1/C2且d2=1/C2+4-ln(a1)通过著名的牛顿-拉夫逊法，我们能得到等式的一个数值解。根据这个解我们可以得出一个新阈值th2然后m将不确定性阈值loc.uncertaint

56、y设置为一个从th2开始逐渐减少的值. 在t2个时间单位后，偏离超过了当前的不确定性阈值th2/t2然后m发送一个包含新阈值th3的位置更新消息。th3可通过先前的公式计算得到，但要使用新斜率a2. I2是之前t2个时间单位里的偏离代价。这一处理过程在每一次更新时刻执行，并一直持续到运动过程结束。在每一次处理过程中，移动对象m结合当前偏离近似函数的常量C1和C2以及斜率ai来确定下一个优化的阈值.一个轨迹可以被看作为未来的一个运动规划，也可以用来表示移动历史。通常移动对象轨迹被建模为三维空间中一条折线。如果想表示不确定性方面特征，可以将轨迹建模为三维空间中的圆柱体，这样可以查询特定时间间隔里包

57、含在特定区域中的对象。由于引入了不确定性，我们可以更进一步地考虑对象的时态不确定性和区域不确定性，这样便可查询在某个时间间隔内有时或者一直（时态不确定性）位于某个区域内的对象。类似地，我们可以查询可能或者一定位于某个区域内的对象。u查询有可能会在1：00pm到1：10pm之间的某个时间出现在区域R中的卡车的当前位置u查询在4：30pm到4：45pm之间某个时间一定会出现在区域R中的飞机的数量。u查询可能会在9：20pm到9：50pm之间一直出现在区域R中的警车定义3.8 移动对象的轨迹是三维空间中的一条折线，其中两个维指向空间，第三维指向时间。它表示为一个点序列,这里t1tn给定一个轨迹tr，

58、它在xy平面上的空间投影称为tr的路线。移动对象的位置通过一个隐式的时间函数给出，移动对象在ti时刻的位置是(xi,yi),并且在每个时间区间ti, ti+1都假设移动对象以不变的速度沿着从(xi,yi)和(xi+1,yi+1)的直线移动。定义3.9 给定一个轨迹tr,移动对象在ti到 ti+1 (1in)之间的某个时间点t的预计位置可以通过(xi,yi)和(xi+1,yi+1)之间的线性插值得到。轨迹是一个描述了对象未来运动规划的点集，移动对象访问并遍历这个点集。这里假设在两个连续的点之间对象是沿最短路径运动的(即以不变的速度沿直线运动).我们为轨迹的每一个线段关联一个不确定性阈值th,我们

59、得到一个围绕着轨迹的三维圆柱形缓冲区域。则如果移动对象的实际位置偏离预计位置的距离达到或超过th，移动对象将更新数据库服务器。定义3.10 设th是一个正实数且tr是一个轨迹，则相应的不确定性轨迹为(tr,th),th的值称为不确定性阈值。定义3.11 设tr=是一个轨迹且th是不确定性阈值。对于沿着时间轴的每个点(x,y,t),它的th不确定性区域(或简称不确定性区域)是一个以(x,y,t)为圆心，半径为th的水平圆，这里(x,y)是t时刻的预计位置。定义3.12 设tr=是一个轨迹且th是不确定性阈值。函数集PMCtr,th中任意函数的图形，都是合理的运动曲线， PMCtr,th=f:t1

60、,tn-R2|f连续，且对所有t t1,tn,f(t)包含在t时刻tr预计位置的th不确定性区域中。它的二维空间投影称为合理路线。定义3.13 对一个不确定性轨迹(tr,th)以及tr的两个端点(xi,yi,ti)和 (xi+1,yi+1,ti+1)。(tr,th)在ti 和ti+1之间的线段轨迹体是所有属于某个合理运动曲线的点(x,y,t)(titti+1)的集合。线段轨迹体的二维空间投影称为线段不确定性区域。定义3.14 对一个轨迹tr=和一个不确定性阈值th,(tr,th)的轨迹体是所有ti和ti+1之间的线段轨迹体的集合(1ipoint返回时刻t时对象路线tr上的预计位置(即一个二维点

61、)。uwhenAt:trajectory* point -instants返回沿轨迹tr运动的移动对象到达预计位置l的时间。返回的结果可能是一个时间的集合，因为一个移动对象可能会不止一次经过某个特定位置。如果路线tr不经过位置l,则先确定该路线上所有最接近l的点的集合C，然后whenAt(tr,l)返回一个时间集合，在该时间集合中的每一个时间，移动对象的预计位置都恰好是C中的某个点。如果一个移动对象在给定时间间隔t1,t2内位于某个给定区域R中，则谓词为真。u查询移动对象在t1,t2内是有时满足条件还是总是满足条件(对谓词的有效性进行时态量化)u查询移动对象在区域R内是在某个位置满足条件还是在

62、所有位置都满足条件(空间量化)u查询移动对象是可能满足条件还是一定满足条件(通过不确定性对谓词的有效性进行量化)因为存在3种量化方式，因此有3!种不同顺序来排列。每一种确定的顺序有23种可能的方式组合3个方面的量化。但由于一个点不可能同时位于一个区域R内的所有位置，因此在下面的内容不讨论这种量化。因此仅有222!=8种可能的操作符这8种操作符定义如下：定义3.15 设r是一个简单查询区域。设ut=(tr,th)是一个不确定性轨迹(1)如果存在ut的一个合理的运动曲线c以及一个时刻tt1,t2,并且满足t时刻时c包含在r的内部，则谓词PossiblySometimeInside(ut,r, t1

63、,t2)为真(2)如果谓词PossiblySometimeInside(ut,r, t1,t2)为真，则谓词SometimePossiblyInside(ut,r, t1,t2)(3)如果存在ut的一个合理的运动曲线c，并且满足在任何tt1,t2时刻c都包含在r的内部，则谓词PossiblyAlwaysInside(ut,r, t1,t2)为真(4)如果对于任一tt1,t2时刻，都存在ut的一个合理的运动曲线，并且在t时刻与r相交，则谓词AlwaysPossiblyInside(ut,r, t1,t2)为真(5)如果对于任一tt1,t2时刻，ut的任一个合理的运动曲线都包含在r的内部，则谓词A

64、lwaysDefintelyInside(ut,r, t1,t2)为真(6)如果谓词AlwaysDefintelyInside(ut,r, t1,t2)为真，则谓词DefintelyAlwaysInside(ut,r, t1,t2)也为真(7)如果对于ut的任一合理的运动曲线c，存在一个时刻tt1,t2 使得在该时刻时c包含在r的内部，则谓词DefintelySometimeInside(ut,r, t1,t2)为真(8)如果存在一个时刻tt1,t2使得在该时刻时ut的所有合理的运动曲线都包含在r内部，则谓词SometimeDefintelyInside(ut,r, t1,t2)为真(1) P

65、ossiblySometimeInside中谓词有效性说明移动对象可能会运动在其不确定性区域内部的某条合理路线，且这条路线在t1,t2之间会与r相交。(3) PossiblyAlwaysInside对象的运动必须沿着至少一条特定的二维合理路线，该路线在整个查询时间间隔内全部包含在r内部。(4) AlwaysPossiblyInside要求在查询时间间隔内的任一时刻都存在着一条与r相交的合理运动曲线(5) AlwaysDefintelyInside即不管对象选择什么样的合理运动曲线，必须保证该曲线在整个查询时间间隔里都包含在查询区域r的内部(7) DefintelySometimeInside表

66、示无论移动对象选择不确定性区域内的哪一条合理曲线，该曲线都会在查询时间间隔内的某个时刻与查询区域相交(8) SometimeDefintelyInside无论移动对象位于哪一条合理运动曲线上，对象都将在某个特别的时刻t时包含在查询区域的内部。uPossiblySometimeInside SometimePossiblyInsideuPossiblyAlwaysInside=AlwaysPossiblyInsideuAlwaysDefintelyInside AlwaysDefintelyInsideuSometimeDefinitelyInside= DefinitelySometimeIn

67、side例：查询”检索出在对象A到达l1和l2位置之间的任何时刻都可能在区域r内的所有对象”PossiblyAlwaysInside(ut,r,whenAt(utA, l1),whenAt(utA, l2)下面介绍6个时空谓词的算法。设t1,t2是两个时刻，随时间而移动的二维空间对象可看作是三维对象，时间作为第3维。具有查询时间间隔t1,t2的查询多边形r可以表示为一个棱柱p(r)=(x,y,t)|(x,y) rt1t t2，称之为查询棱柱。设v(ut)表示t1和t2之间一个给定的不确定性轨迹ut=(tr,th)的轨迹体，且v(ut,r)是轨迹体和查询棱柱的交，即v(ut,r)= v(ut)p

68、(r)(tr)表示tr在xy-平面上的空间投影(即tr的路线)给定一个多边形q和一个半径为c的圆盘d(c)作为操作数，qd (c)的计算结果包含q边界上的所有点，q内部的所有点以及当圆盘中心沿着q的边运动时所”扫过”的所有点。因此对于一个凸多边形q，qd(c)的边界由q顶点之间的直线段以及顶点上的弧组成。谓词PossiblySometimeInside满足的条件是当且仅当轨迹体和查询棱柱的交非空(即v(ut,r)有如下算法：Algorithm PossiblySometimeInside(ut,r, t1,t2)构造rd (th)； If (tr)(rd(th)=then return fal

69、se else return true endifendv(ut,r)非空的条件是当且仅当(tr)和扩展多边形rd(th)相交。谓词PossiblyAlwaysInside为真的条件是当且仅当在t1,t2之间时v(ut,r)包含一条合理的运动曲线。Algorithm PossiblyAlwaysInside(ut,r, t1,t2)构造rd (th)；If (tr)完全位于rd(th)内then return true else return false endifend谓词DefinitelyAlwaysInside为真的条件是当且仅当v(ut,r)=v(ut)成立Algorithm Def

70、initelyAlwaysInside(ut,r, t1,t2)for tr的每一条直线段s doIf s的不确定性区域不包含在的不确定性区域不包含在r内内 then return false endifendfor;return trueend谓词SometimeDefinitelyInside为真的条件是当且仅当v(ut,r)包含一个完整的水平圆盘。Algorithm SometimeDefinitelyInside(ut,r, t1,t2)for tr的每一条满足(s)r的直线段s doIf r包含一个以s上的某个点为圆心，半径为th的圆then return trueendifendf

71、or;return falseend谓词DefinitelySometimeInside 为真的条件是当且仅当v(ut)p(r)在t1和t2之间不是连接的。否则t1和t2之间就必定存在着一条完全包含在v(ut)p(r)内的合理曲线，这样使得谓词不成立。对于查询区域r，可找到两条使谓词为真的路径，即从u到v和从w到z的路径。Algorithm DefinitelySometimeInside(ut,r, t1,t2) If 存在一条从l1的某个点到l2的某个点之间的一条路径P，该路径完全包含r的边and P完全包含在uz(ut)内then return trueelse return false endifend