空间数据库_查询与优化

1、空间查询与优化一、查询处理概览查询概念：提取需要的数据出来从数据库中提取数据的一系列活动查询步骤：语法分析与翻译（将查询语句变为关系代数表达式）、优化、执行查询优化概念：为关系代数式的计算选择最有效的查询计划的过程。包括1.查询执行计划、2.执行原语（关系代数运算加了如何执行的注释）、3.根据选择算法对数据记录进行操作空间查询优化关键技术：空间索引（数据存取角度，有效读写海量数据）、查询处理算法（提高具体查询执行效率角度）、代价模型（指导查询过程的角度）查询优化过程：1.通过语法分析语翻译器，将查询语句变为一种内部表达2.代数优化 进行表达式变化，力图等价但效率更高3.选择执行策略 4.选择代

2、价最小的执行计划查询处理优化可行性：1. 可能性：SQL语言与关系代数表达式的非过程化（做什么，而不用说明怎么做）特点2. 可行性：优化器集中了最优秀的程序员的经验与智慧；优化器能对多种策略逐一进行考虑；优化器实时更新优化 具有多种可使用信息二、空间操作计算空间操作计算与关系数据运算的区别：1. 空间数据没有公认标准的定义，而关系数据库中的运算很固定2. 空间对象的位置和范围在二维或多维上定义，不能自然排序成一维数组3. 数据流读写：空间关系运算代价非常高空间操作基本类型：查询1.更新：空间对象的创建、修改和删除2.空间选择（貌似就是查询）：查询出空间对象中满足查询窗口中特定微词的对象。包括点

3、查询（）和范围查询（）3.空间连接：4.空间聚类：空间操作两步处理：1.过滤步骤-主过滤：最小外包络矩形近似处理，大大减低计算复杂度2.精炼步骤-次过滤：利用精确几何信息求算空间选择查询点查询：SELECT FROM forest_stand WHERE within (:point , f.geometry);范围查询：SELECT FROM forest_stand WHERE intersects (:window, f.geometry);实现方法依赖于数据文件的存储组织查询的三种算法1.未排序无索引的数据文件：穷举法，代价O（n），n是forest_sta

4、nd存储的页面数2.具有空间索引的数据文件：多采用R树，按照MBR索引，代价O(log n) , n为树的层3.空间填充曲线散列：z排序和Hilbert曲线映射为一维坐标，然后采用B树或B+树索引点查询代价O(log n)，范围查询代价为O(log n)+。R+树？一般空间选择（空间谓词问题）1. 组合形式下，空间谓词计算代价高且差别大，处理顺序对总代价影响大（顺序性）2. 考虑空间谓词的选择性与代价以确定顺序： 等级=（选择性-1）/特征代价 选择性=输出p的集合大小/输入p的集合大小，p是一个谓词特征代价是谓词对单个元组的计算代价，体现CPU的代价输出与输入集合之比，体现了I/O代价3.

5、按照代价等级的升序依次计算空间谓词空间连接操作算法采用粗过滤-精确判断两步方式例：查找有河流穿过的林分SELECT * From forest-stand F, river R Where overlap ( F.Geometry, R.Flood-plain )假定：关系forest-stand占用M个页面，每页PF个元组，关系river占N个页面，每页PR个元组，一对对象执行overlap函数的平均时间为T，算法过程如下：1. 嵌套循环：枚举所有可能的元组队，并用overlap函数进行检查，伪码语言：For all tuple fF For all tuple rR If overlap(

6、 F.Geometry, R.Flood-plain ) then add to result 未优化的算法：扫描外层关系F，对每个f匹配扫描关系R，则I/O代价为(M*N)*T优化算法，如果有B个可用的缓冲区页面，先读取关系F的B-2页，用剩下的一页缓冲区读取关系R，用另外剩下的缓冲区页回写，I/O代价为(M/(b-2)*N)*T有空间索引的嵌套循环，在Overlap时可以使用索引来判断，提高工作效率2. 分块 过滤步骤：分别对F和R中的元组构造K-Pointer元组， 由唯一OID和外包络矩形构成，新关系称为Fkp 和Rkp 。如果新关系都可以装入主存，则采用平面扫描算法处理。否则，将两个

7、关系都分成p块，即F1kp Fpkp和R1kp Rpkp 。分块约束条件：Fkp 和Rkp 都位于主存；对于每个 Fkp ，在Rkp 中与之对应的元素位于某个分块Rikp空间聚集-最近邻居算法一般算法：逐个读取查询对象的数据页D；通过一个范围查询，检索D中任意对象到查询对象的距离；如果搜索顺序和剪枝规则选取得当，可以有效减少系统在大规模空间检索中的结点访问量。距离量度算法：距离度量包括min-distance(Point P,Rectangle R和min-max-distance(Point P,Rectangle R);说明分别是什么；R树的构造就满足MBR中点O满足Distance(o,

8、p)min-max-distance(o,R),则可以排除掉MBR M如果 distance(o,M)min-distance(o,R)，则可以排除掉MBR R三、 OracleSpatial空间查询空间查询基本思路基于主次过滤的查询模型主过滤：空间数据检索次过滤：空间计算优化用于主过滤检索的空间数据索引是提高性能的关键。空间查询分片法索引的特点：1排他性2 覆盖性 空间彻底性主过滤操作：SDO_FILTER 判断两个几何体是否有相交！SDO_FILTER只能用于WHERE子句中SDO_FILTER(geometry1 MDSYS.SDO_GEOMETRY,geometry2 MDSYS.SD

9、O_GEOMETRY, params VARCHAR2)；geometry1是图层中的已建立空间索引的SDO_GEOMETRY字段；geometry2是做过滤条件的SDO_GEOMETRY对象,它可以来自于图层,也可以动态创建,可以是索引过的,也可不是;当连接操作使用主过滤时，geometry2必须来自于图层，并且要求该图层与geometry1的图层具有相同类型R-tree/QuadTree和相同参数的索引；params定义本操作符的过滤准则: querytype=window|join idxtab1= idxtab2= , querytype:规定主过滤类型:窗口主过滤(空间列与空间对象之

10、间)/连接主过滤(空间列与空间列之间)idxtab1和idxtab2是所用索引表名称，是可选的，默认是主索引；idxtab2仅用于连接主过滤。返回值: TRUE 或 FALSE大写字符串。使用静态查询窗时的空间索引使用方式：指定空间关系进行查询SDO_RELATESDO_RELATE 操作符（只能用于WHERE子句中）用于主次过滤SDO_RELATE(geometry1 MDSYS.SDO_GEOMETRY, geometry2 MDSYS.SDO_GEOMETRY, params VARCHAR2)给定范围操作符SDO_WITHIN_DISTANCESDO_WITHIN_DISTANCE（只

11、能用于WHERE子句中）返回落在给定几何体距离范围内的几何体,不适用于空间连接查询，它可以是精确比较也可以是近似比较；SDO_WITHIN_DISTANCE(geometry1 MDSYS.SDO_GEOMETRY, Geom MDSYS.SDO_GEOMETRY, params VARCHAR2)最近邻操作SDO_NNSDO_NN（只能用于WHERE子句中） 确定与给定几何体距离最近的几何对象SDO_NN(geometry1 MDSYS.SDO_GEOMETRY,geometry2 MDSYS.SDO_GEOMETRY, params VARCHAR2,tag NUMBER)最近邻辅助操作S

12、DO_NN_DISTANCESDO_NN_DISTANCE返回SDO_NN操作得到的NN与给定几何体间的距离，单位由相应SDO_NN操作的unit参数定义；Tag参数关联使用SDO_NN操作SDO_NN_DISTANCE(tag NUMBER)空间操作符与空间函数比较数据源 使用环境使用范围 返回值 空间连接与窗口查询的区别窗口查询分析的是同一图层不同空间对象间的拓扑关系，而空间连接针对的是不同图层间空间对象的拓扑关系分析窗口查询选定的空间对象可以没有空间索引，而参与空间连接的空间对象必须有相同类型的空间索引，如果是四叉树模型，还必须有形同的SDO_LEVEL四、 查询优化计算执行计划的标准实

13、质就是执行查询所需要的时间。传统数据库查询度量重点在I/O代价，因为数据类型和函数都很简单；空间数据库包含了复杂的数据类型和CPU密集型函数，优化策略更复杂查询优化器数据库管理系统的模块，用于产生不同的计算计划，并确定合适的执行策略逻辑转换语法分析语法分析器查询树SELECT L.Name FROM Lake L，Facilities Fa WHERE Area(L Geometry ) 20 AND FaName=campground AND Distance(Fa.Geometry, L.GeoMetry)将非空间的选择操作下推如果Area函数的计算密集度比Distance函数高出几个数量

14、集启发式规则之一：在连接和二元操作之前进行选择和投影启发式规则之二：谓词P的等级概念各种运算的优化依据选择：多个选择可以组合为一个，因此将非空间条件右移。选择条件可以按任何顺序是进行判定，最好先判定非空间条件投影：可以将多个投影组合为一个笛卡尔积和连接：满足交换律和结合律选择、投影和连接广义笛卡尔积；选择；投影；连接；除运算。1. 什么是空间数据库？其主要特点是什么？空间数据库是将众多空间数据集合起来进行统一管理的数据结构。存储和管理空间数据的场所可变长性、海量性、结构不定性、空间性、空间关系性应用广泛 既有属性数据又有空间数据 2. 数据库技术的发展经历了哪些阶段？各个个阶段有什么的特点？文件型数据库文件-关系型数据库关系型数据库对象型数据库关系-对象数据库3. 简述空间实体抽象的三个层次，并画图说明9. 简述矢量和栅格数据模型的优缺点，以及二者的比较10. 什么是空间数据引擎？举例说明空间数据引擎的体系结构、工作原理。11. 如何进行空间数据分层组织？分层有哪些原则？分层有哪些方法？12. 什么是空间索引？建立空间索引的目的？13. 空间索引建立的基本原理和