《基于执行代价的空间查询优化方法》基于传统关系空间查询优化方法与理论，结合空间数据数据量大、结构复杂、操作代价昂贵等特殊性，详细阐述了空间数据在计划枚举、代价计算和选择率估计等关键问题上的相关研究成果，并在开源数据库Ingres中研发实现，为空间查询优化的理论方法创新与实际应用做出贡献。

　　《基于执行代价的空间查询优化方法》：
　　R—树是最为经典并普遍公认的空间索引。自Guttman（1984）首次提出动态的空间索引R—树以来，国内外学者开展了大量R—树族的研究。1987年，Sellis等设计了R+—。树以解决兄弟结点的重叠而产生的多路径查询问题；但R+—树同时也带来了其他的一些问题，例如，冗余存储增加了树的高度，使树的连锁更新操作更为复杂。1990年，Beckmann等提出了R*树。他们认为区域重叠并不意味着平均检索性能很差，如何插入节点才是提高检索性能的关键。Karnel和Faloutsos（1995）提出了使用n—to—m（m>n）的节点分裂方法，这使得动态R—树的构建节点更为密集，可以有效地节省空间资源和提升检索速度。
　　上面提到的都是动态索引。所谓动态索引是指在整个系统运行期间，树的结构随着数据的增删随时调整，以保持最佳的搜索效率；其优点是在插入或者删除数据时索引树能够自动调整；缺点是实现算法复杂。而静态索引结构通常在初始创建、数据装入时就已经定型，而且在整个系统运行期间，树的结构不发生变化，只是简单更新树结构内的数据而已；其优点是结构稳定，建立方法简单，存取方便；缺点是不利于更新；随着数据的不断增删，索引效率逐渐降低。当然上述动态索引也可以作为静态索引来使用，但这样必然会带来不必要的开销，因此大静态索引不断涌现。第一个静态R—树索引是由Roussopoulos等在1985年提出PackedR—树。其基本思想是根据空间对象MBR的一个角点的x坐标或y坐标对空间对象进行排序，然后按照这个顺序将空间对象装载（packing）到树的叶节点，并在叶节点上构建索引节点和根节点；按照MBR某角点的某维坐标进行排序并不能保证空间对象的聚集性，因此节点的空间利用率并不高。1993年，Kamel和Faloutsos提出一种基于分形曲线的静态R—树压缩算法。分形Hilbert曲线将已知空间数据的中心点进行一维映射。根据Hilbert值进行装载树节点可以获得较好的数据集簇，从而提高R—树性能。2001年，Huang等提出了CompactR—树，即采用新的分裂算法提高存储利用率，减少结点分裂次数。2002年，Brakatsoulas等认为R—树的本质上是一个典型的聚类问题，通过研究R—树构建原理，采用通用的K—means聚类算法提出cR—树。由此可见，R—树变种很多，在不同环境、不同优化思路下，需要R—树的理解做出适当的调整。
　　……

前言
第1章 绪论
1.1 背景与意义
1.2 研究范畴
1.3 研究目标及贡献
1.3.1 空间查询计划生成方法
1.3.2 空间查询代价评估模型
1.3.3 空间直方图选择率估计

第2章 空间数据库基础知识介绍
2.1 关系数据库系统内核基础知识
2.1.1 元组标识（TID）
2.1.2 物理存储格式
2.1.3 主索引与辅助索引
2.1.4 查询图
2.1.5 连接树
2.1.6 等价类
2.1.7 执行操作算子
2.2 空间扩展的相关基础知识
2.2.1 几何数据类型
2.2.2 空间操作与函数
2.2.3 空间索引
2.2.4 空间数据的表结构
2.2.5 空间数据库的执行操作算子
2.3 数据库查询处理流程与Ingres程序框架
2.3.1 数据库查询处理流程
2.3.2 Ingres查询处理的程序框架

第3章 空间查询计划的生成
3.1 查询计划生成方法综述
3.1.1 穷举法
3.1.2 动态规划法
3.1.3 贪婪法
3.1.4 概率法
3.1.5 复合算法
3.1.6 小结
3.2 一种复合的空间查询计划生成方法
3.2.1 连接树形的生成
3.2.2 基于分块约束的表排列生成
3.2.3 操作枚举
3.2.4 空间启发式策略的加入
3.3 空间启发式策略的实现与实验
3.3.1 空间约束对在Ingres中的改进与实现
3.3.2 启发式策略在缩小计划枚举空间方面的作用

第4章 空间代价评估模型
4.1 空间代价评估研究综述
4.1.1 基于R-树的空间选择代价
4.1.2 空间连接操作及其执行代价
4.1.3 空间算子的CPU代价
4.1.4 小结
4.2 基于查询树的Ingres代价评估模型
4.2.1 代价模型推演框架
4.2.2 连接代价的计算
4.2.3 计划树的代价
4.2.4 Ingres代价评估示例（改进前）
4.3 扩展的空间代价模型
4.3.1 空间查询代价估算的特殊性
4.3.2 空间扫描代价
4.3.3 空间连接代价
4.3.4 Ingres代价评估示例（改进后）

第5章 空间直方图及其选择率估计
5.1 空间选择率估计研究
5.2 现有空间直方图综述
5.2.1 MinSkew直方图
5.2.2 SQ直方图
5.2.3 CD直方图及其修正估计方法
5.2.4 Euler直方图及其扩展
5.2.5 PH直方图
5.2.6 GH直方图
5.2.7 PostGIS直方图
5.2.8 小结
5.3 累计AB直方图的相关概念及核心操作
5.3.1 AB直方图
5.3.2 累计AB直方图
5.3.3 核心操作函数
5.4 累计AB直方图的选择率估算
5.4.1 空间选择的选择率估计
5.4.2 空间连接的选择率估计
5.5 累计AB直方图的推演
5.5.1 面向空间选择的直方图推演
5.5.2 面向空间连接的直方图推演
5.6 实现与实验
5.6.1 相关系统实现
5.6.2 空间选择操作的选择率估计实验
5.6.3 空间连接操作的选择率估计实验
5.6.4 累计直方图的推演实验
5.7 小结

第6章 总结与展望
6.1 内容总结和结论
6.2 存在的问题与进一步的工作
参考文献