空间查询优化分析

《空间查询优化分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1绪论对参与空间查询且建立了索引的空间数据集，我们讨论了如何基于索引来估算执行空间查询时读取操作对象的I/O代价，其中重点分析基于R-树代价模型。该部分的讨论以第三章为基础。②基于直方图的代价模型如前所述，由查询结果集的大小可估算出输出查询结果的I/O代价。直方图是估算查询结果集大小的一种有效方法。其中，研究者对欧拉直方图进行了较广泛和深入的研究。在本部分，我们研究了欧拉直方图存在的问题，提出了闭欧拉直方图并对其准确性进行证明，从而提高了基于欧拉直方图的代价估算的准确性。第六章：基于闭欧拉直方图的空间查询优化仿真实验。在理论研究的基础上，通过仿真实验，我们探讨了将闭欧拉直方图与实际查询优化器

2、结合、优化空间查询的可行性和有效性。第七章：总结。对本论文所做的空间查询优化研究进行总结，确定下一步研究的方向和工作。42空间查询优化技术2空间查询优化技术2.1空间对象一个简单的点或一组任意分布的多边形都是空间对象。空间对象存储在空间数据库中，它们由空间数据和属性数据来描述。空间数据描述空间对象的位置、形状和分布特征等空间信息，如距离某地10公里的城市。而属性数据描述空间对象的名称、专题属性等非空间信息，如城市的人口数量、地区降雨量、粮食产量等。我们将空间数据构成的集合称为数据集，这些空间数据描述了空间对象，故可将数据集称为空间对象集，简称对象集。2.1.1空间数据类型在实际应用中，空间数

3、据也常常被称为图形数据。空间数据有以下几种类型[74]：①点例如城市。点只表示其空间位置，不表示其范围。②线例如河流、道路、管道、航线、等高线、等降雨量线、通信或电力线路等。线不仅表示线上各点在空间的位置，而且还有长度，即表示它在空间中延伸的范围。③面（也称为区域）例如森林、湖泊、省市区域等面状对象。区域不但有位置，而且有面积、周长等参数，以表示其覆盖的范围。以上述三种基本空间数据类型为基础，还可以导出下面一些空间数据类型：①划分一个区域可以按其自然的、行政的或者其他特征，分成若干子区域，这些子区域互不相交，但它们的并集覆盖该区域，则这些子区域共同构成该区域的一个划分。国家的行政区域划分图、

4、土地利用图等都是划分的例子。划分可以嵌套，例如国家分成省、省分成县、县分成乡镇等。②网络网络是由若干点以及一些点和点之间的连线组成。公路网、河网、电力网、电话网、交通路线图等都是网络的例子。2.1.2空间数据的特点空间数据被视为一种特殊的数据，其最主要的特征是它的空间性，即它与空间[42]对象的空间位置有关。此外，空间数据还具有以下几个特点：52空间查询优化技术①结构复杂。有固定长度的关联数据库元组不适合存储空间数据。②动态性。该特点要求数据结构能适应频繁地插入、删除以及更新对象。③数据量不断增长。地理地图或者VLSI电路图往往需要数千兆字节的存储空间。④多维性。即在一个坐标位置上具有多个专

5、题和属性信息。该特点使得使用传统数据库索引方法（比如用B-树或线性散列法）来索引空间数据变得非常困难。因此，传统的关系数据库技术不适用于空间数据，我们必须从空间数据的这些特点出发来管理它们。2.1.3空间对象间的关系空间数据带有空间坐标，它不仅能表示对象本身的空间位置及形态，而且还包含了空间对象之间的空间关系这一信息。[39]空间关系是指空间对象之间的一些具有空间特性的关系。空间关系主要分[40]为度量、方位和拓扑等三大类关系。度量空间关系是用某种度量空间中的度量指标来描述的对象间的关系(Kreyszig1987,Robinsoneta1987)，例如对象间的距离；方位空间关系是用来描述对象

6、在空间中的某种顺序的关系(Kainz1990，Freeman1975，Hernandez1991)，如前后、上下、左右、东西南北等；拓扑空间关系是指拓扑变换下的拓扑不变量(Egenhofer1989，EgenhoferandHerring1990)，如空间对象的相交、重叠、包含等关系。一般说来，对象间的空间关系与对象的维数、形态、大小及其所在空间的维数有关，各类拓扑空间关系也存在着一定的联系，对象间空间关系的描述形式各不相同，因此对象间的空间关系是极为复杂多样的。空间推理(SpatialReasoning，SR)是指利用空间理论和人工智能(ArtificialIntelligence，AI)

7、技术对空间对象进行建模、描述和表示，并据此对空间对象间的空间关系进行定性或定量分析和处理的过程。空间关系表示和推理的研究将有助于设计有效的空间查询和数据处理方式。目前，空间关系的研究取得了长足的发展，涌现了大量的研究成果。我们的课题组自2000年来对空间关系表示和定性空间推[2,7,8]理进行了研究并取得了一定的进展。2.2空间查询及其类型空间数据的查询实质上是按照一定条件对空间对象的空间数据和属性数据进行查