移动对象数据库-第2章.pptx

早期的时空数据库,针对双时态状态关系支持双时态事件关系,1。双时态元素,定义：双时态元素（BTE）定义为ITIV上的一个有限集合的并。ITIV是时间区间不相交的笛卡尔积。IT是事务时间TT的区间，IV是有效时间TV的区间。双时态元素是一个点集。点(tT,tV)表示在事务时间tT时数据库中有有效时间tV时对象的存在信息。,2。单形,定义：给定k+1个点v0,vkRn,集合v0,vk是几何无关的，并把由如下公式定义的点集称为包含顶点v0,vk的k维单形（k单形）：=k=pRn|p=vAND=1K单形都是由k+1个（k-1）单形构成。0单形是一个点1单形是一条直线或线段2单形是三角形（并非任意平面图形）3单形是四面体（并非任意立体图形）,3。单纯复形,定义（关联完整性）：一个单纯k复形C是一个有限的单形集合，同时还包含任意单形的面。C中任意两个单形或交集为空，或共用一个面。C中单形的最大维度为C的维度k。关联完整性指C中单形的不相容性和线顶点的相容性。,4。有向单形,定义：一个有向k单形是对包含顶点v0,vk的k单形指定一个顶点顺序。这样，有向k单形可以表示成=一个有向单纯复形是对一个单纯复形中的每个单形都赋予一个方向得到的。,5。边界和内部,定义：一个k单形k的边界k是该单形所有（k+1）个（k-1）单形的并。一个k复形C的边界C是包含其中所有k单形边界的对称差的最小复形。一个k复形的内部C是不属于C边界的所有（k-1）单形的并。计算时注意方向。,6。平面嵌入,定义：单纯复形C=s1,sn的平面嵌入定义为Emb(C)=siSi是单形。,7。共同精华,定义：单纯复形C1和C2的一个共同精华refine(C1，C2)是一个单纯复形，且emb(refine(C1，C2)=emb(C1)emb(C2)共同精华的结果通常不唯一。,8。ST单形,定义：ST单形R=（S,T）,S是一个单形，T是一个双时态元素。s（R）=St（R）=T,9。ST复形,定义：ST复形C是一个ST单形的有限集合，并且;1.其中ST单形的空间投影不相交；2.其中ST单形的空间投影能组合为一个复形。3.ST单形R,RC：s(R)是s(R)的一个面t（R）t（R）。单形投影不相容但相邻,空间双时态操作,=:ST-complexST-complexboolean(ST-equal)ST:ST-complexST-complexboolean(ST-subset):ST-complexST-complex(ST-boundary)s:ST-complexS-complex(S-project)t:ST-complexBTE(T-project):ST-complexST-complexST-complex(ST-product)ST:ST-complexST-complexST-complex(ST-union)ST:ST-complexST-complexST-complex(ST-intersection)ST:ST-complexST-complexST-complex(ST-difference)sX:ST-complexST-complex(S-select)t:ST-complexST-complex(T-select),10。ST复形子集、等价性,定义：CSTC(x,y,z,w)(S,T)C(S,T)C:(x,y,z,w)(S,T)C=STCCSTCCSTC第一条表明C在ST四维中被C完全覆盖时将是C的ST子集；第二条说明等价就要互为子集。,11。ST复形边界,定义：ST复形C的边界C=(S,T)|S(S(C)ST复形C的边界是一个ST复形，它的空间结构是C投影的边界。,12。ST复形的投影,定义：ST复形C=(S1,T1),(Sn,Tn)，则（1）S(C)=S1,Sn（2）t(C)=Ti一个ST复形的空间投影是一个复形，该复形表示了在所有事务时间和有效时间上的所有ST复形的空间范围信息。,13。空间双时态积,定义：BTEBTEBTE有ST复形C1和C2，以及操作。令单纯复形R为s(C1)和s(C2)的一个共同精华。定义C1C2为包含ST单形集合(S,(T1S,T2S)|SR的最小ST复形。T1S,T2S分别表示与s(C1)和s(C2)包含S的最小面所关联的双时态元素。选择不同共同精华所得的结果是等价的。,14。ST复形的交并差,定义：C1STC2=C1C2C1STC2=C1C2C1STC2=C1C2,15。空间选择,定义：令X=S1,S2,Sn是一个单纯复形，且Dx=(S1,TTTV),(Sn,TTTV)为ST复形。关于X的ST复形C上的空间选择操作就定义为Xs(C)=CSTDx。见图（e）,16。ST可比和最小集,定义：ST复形的一个集合C1,C2,Cn的元素是可比的当且仅当1ijn:CiSTCjCjSTCi。可比的ST复形的一个集合C1,C2,Cn的最小集定义为minST(C1,.,Cn)=C,使得CC1,.,Cn1in:C=STCiCSTCi,17。时态选择,定义：设(t)是一个一阶公式，他可能包含作为常量的双时态元素、作为函数的操作以及单个的自由变量t。那么ST复形C上关于的双时态选择操作就定义为t(C)=minST(C|C=(S,T)C|(T)。,时空数据库查询举例,地块1上的建筑物1958年是什么样子的？SelectS-project(T-select(_,1958),building)FromparcelsWhereparcel-id=1and(_,1958)inT-project(building)在什么时候某人拥有的一个地块还不是实际房产？地块4上的学校是什么时候建成的？,Parcels(parcel-id:integer,owner:string,area:ST-complex,building:ST-complex)Parcel-id地块标识符Owner地块拥有者Area地块区域的演变Building地块上建筑物的信息,时态差T-difference:BTEBTEBTESELECTparcel-id,owner,T-difference(T-project(area),T-project(building)ASundeveloped-areaFROMparcels用有建筑物的时间减去有地块的时间，列出SELECTmin(T-project(building)FROMparcelsWHEREparcel-id=4由于地块4上只有学校，找出其上建筑物存在的最早时间即可,2.SelelctT-project(building)fromparcelsWhereisempty(S-project(building)3.Selelctmin(T-project(p.building)FromparcelspWherep.parcel-id=4and(S-project(p.building)=school),基于事件方法的模型,思路：将时间戳ti和ti-1到ti之间的变化相关联。记录初始地图BM。部件内部使用栅格游程编码。,查询处理算法,查找在时间t时变化到gv的位置列表。线性查找，时间复杂度是O(ne+ce+kc)查找在时间间隔t1,t2内变化到gv的位置列表。时间复杂度为O(logne)+nf(ce+kc)查找在给定时间间隔和区域内变化到gv的总变化数。时间复杂度为O(ne),