空间查询处理(数据库)

时间：2022-10-31 18:30:01 | 来源：信息时代

时间：2022-10-31 18:30:01 来源：信息时代

    空间查询处理 : 对数据库中大量的空间对象进行高效检索的过程。空间数据库的查询处理与关系数据库之间的主要区别是: ①空间数据库没有固定的算子集合可以充当查询计算的基本构件;②空间数据库要处理大量的复杂对象,这些对象具有空间范围,而且不能自然地排序成一维数组;③检测空间谓词需要用到计算代价高昂的算法,所以不能再假定I/O代价远超CPU代价。
1.空间查询操作的步骤
空间查询操作通常采用过滤精炼算法以高效地处理空间查询中所包含复杂数据类型。该算法的处理步骤为:
(1)过滤步骤: 空间对象表示为相对简单的近似(approximations),比如最小外接矩形,其结果是真实结果集的超集,也称为候选集。空间谓词也可以被替换成一个近似以简化查询优化器。有些空间算子,例如inside(在内部),north-of(在北部),buffer(缓冲区分析)可以近似成相应最小外接矩形之间的交叠关系。这样的转换能够保证最终结果中的元组不会在过滤步骤中被排除掉。
(2)精炼步骤: 检查候选集中每个元素的精确几何信息和精确的空间谓词。这通常需要使用计算密集型的算法。这一步骤有时可以在空间数据库以外的某个应用程序(如GIS)中进行,该应用程序会用到空间数据库在过滤步骤产生的候选集。
2. 空间查询操作的类型
空间查询主要包括以下四种类型的操作:
(1)更新操作:标准数据库操作(修改、创建等)。
(2)空间选择操作: 又分为点和范围两种。①点查询: 给定一个查询点P,找出所有包含它的空间对象O: PQ(p)={O|p∈O.G≠0},其中O.G为对象O的几何信息。②范围或区域查询: 给定一个查询多边形P,找出所有与之相交的空间对象O:PQ(p)={O|O.G∩P.G≠0}。当查询多边形是一个矩形时,称这个查询为矩形窗口查询。这些查询有时也称作范围查询。
(3)空间连接操作: 空间连接是更为重要的算子之一,类似于关系数据库中的连接算子。当两个表R和S基于一个空间谓词θ连接时,则该连接被称为空间连接。R⋈θS={(O,O’)|O∈R,O′∈S,θ(O.G,O′.G)}空间连接的一个变形是地图叠加(map overlay),它也是GIS中的一个重要算子。这个操作组合了两个空间对象集合以形成一个新的集合。这些新对象的集合的“边界”由叠加操作所指定的非空间属性来决定。
(4)空间聚集操作: 通常是最近邻居搜索问题的变体。给定一个对象O′,找出所有距离O′最近的对象O:NNQ(O′)={O|∀O″:dist(d.G,O.G)≤dist(O′.G,O″.G)}。
3. 空间操作采取的策略
除了更新操作是数据库的标准操作之外,上述其他空间操作都需要针对于空间数据和组织结构的不同而采取不同的策略:
(1)空间选择操作: 针对包含待查关系的文件的不同组织,空间选择有以下三个方法: ①数据未排序且没有索引: 采用穷举法(brute force)扫描整个文件并检查每一条记录是否满足谓词。根据关系的大小,两步(过滤加精炼)处理可能对计算相交谓词非常有用。这个处理与没有过滤而处理整个对象相比,代价是非常低的,扫描的代价为O(n)。对于点查询,过滤步骤包括检验一个点在矩形中的操作。②数据建立了空间索引: 使用空间索引(如R-树)可以避免扫描整个文件从而减少系统代价。采用搜索树的点查询通常可以在O(log n)时间内完成处理。使用索引树时查询的代价依赖于许多因素,包括数据矩形的分布、查询窗口的大小、树的高度以及用于构造索引树结点的组装算法等。采用R-树的一个缺点是不同分支的最小外接矩形允许交叠,这就可能导致沿着索引树的不同分支进行搜索。R-树的一个变体R⁺-树就避免了内部结点的交叠,R⁺-树的主要问题是数据矩形可能在多个内部结点上存在复本,这会导致搜索时间和结点溢出的增加。③空间填充曲线散列: 空间填充曲线通常的例子就是z曲线和Hilbert曲线,但它们都不具备如下属性: 即所有在多维空间中“位置邻近”的记录在映射后的范围空间中仍保持邻近。一旦数据按空间填充曲线“排序”,B树索引就可以用于排序后的记录以加快搜索速度。点查询的代价为O(log_B(n)),其中B为分块因子。范围查询的代价大约为

(2)空间连接操作: 进行空间连接需要采用一些特别的方法来避免执行笛卡儿积。如果只关注过滤-精炼两步策略中的过滤步骤。这样空间交叠操作简化为求矩形与矩形的交,与从二级存储器检索页面的I/O代价相比而言,这个代价是很小的。空间连接操作的处理方法根据数据上的索引情况可以有以下几种: ①没有索引的嵌套循环: 枚举两个关系所有可能的元组对,并用overlap函数检查。②有索引的嵌套循环: 如果其中一个关系建有索引,那么可以将有索引的关系作为内层循环以利用其优点,这样就不需要在每次循环中完全扫描整个内层关系。使用内层关系上的索引来检索能与存储在主存中的外层关系的元组相匹配的候选元组,可以取代范围查询。③树匹配: 如果两个关系都有空间索引(例如R-树),那么就可以使用树匹配策略。树结点包含形如(ref,rect)的记录,其中ref为指向子结点的指针。rect为子结点记录的最小外接矩形或是空间对象的最小外接矩形,这取决于该结点是否为叶结点。二级存储器中对应非叶结点的页称为目录页,对应实际数据的页称为数据页。该算法基于这样一条规律: 非叶结点的矩形能够容纳所有子结点中的矩形的MBR。因此,如果两个目录页中的记录Erl和Er2不交,那么必然其后子树中的所有数据矩形也不交。如果目录页中的记录相交,那么子树的数据矩形则有可能会相交。④基于分块的空间融合连接: 给定两个关系F和R,过滤步骤描述如下: 对F和R中的每个元组构造key-pointer元组,包含元组的唯一OID和空间属性的最小外接矩形,称新关系为F_kp和R_kp。如果关系F_kp和R_kp都可以装入主存,那么连接关系可以用平面扫描算法处理。如果关系太大而不能全部装入主存,则将两个关系都分成P块。F_1kp,…,F_Pkp和R_1kp,…,R_Pkp。分块必须满足两个约束: 对每一个F_ikp,R_kp中与之交叠的元素位于R_ikp;F_ikp和R_ikp都位于主存。
还有一些其他的空间连接策略,例如外部平面扫描或基于连接索引的方法。
(3)空间聚集操作: 最近邻居查询可以通过两遍检索解决这个问题。第一遍检索包含查询对象QO的数据页D,以确定D中任意对象到QO的最小距离d。第二遍通过一个范围查询检索与QO的距离在d之内的对象以确定最近邻居。这个方法重用了空间选择的算法,例如点查询和范围查询。
一遍处理最近邻居查询的搜索算法与上述方法不同,它从R-树的根结点开始遍历整棵树。例如,广度优先遍历将访问当前结点中所有内部结点的子结点的最小外接矩形,并利用规则进行剪枝。保留下来的子结点将在下一轮迭代中被展开。最后一遍将根据树的层次顺序对剩下的最小外接矩形进行剪枝,获得一组叶结点(数据库对象级)。该算法需要计算每个叶结点到查询点P的距离以决定最近邻居。也可以选择深度优先或其他R-树遍历方式。这个算法可以扩展为找到K个最近邻居,只需要稍稍修改剪枝规则就可以保留K个最好的候选。最后,剪枝规则同样适用于基于矩形的索引方法,比如栅格文件,四叉树等等。