摘要：传统的实验验证方式是不完全归纳的方式，理论说服力存在不足，通过严密的数学理论论证能够实现完备的证明。阐述了空间对象网格索引机制的原理，重点对多级网格索引做了详细介绍，尤其针对空间对象多级网格索引机制的优越性进行了完备的数学证明，从理论上论证了多级网格索引的有效性。
关键词：空间对象；多级网格索引；时态数据库
中图分类号：TP301.6文献标识码：A文章编号文章编号：1672-7800（2013）012-0022-04
作者简介：陈鹏（1986-），男，华南师范大学计算机学院硕士研究生，研究方向为数据库索引、空间对象索引；周旋珍（1988-），女，华南师范大学计算机学院硕士研究生，研究方向为时态XML数据库、移动对象数据库；陈瑞鑫（1988-），男， 华南师范大学计算机学院硕士研究生，研究方向为移动对象数据库。
0引言
当前数据库的发展方向中，时态数据库、空间数据库以及时空数据库是几个重要的热点领域。
本文主要围绕空间数据库中空间对象检索索引展开讨论。
近年来，地理环境信息、医学医疗成像、卫星遥感图像处理等各个方面的应用研究产生了大量的空间数据信息，从而关于大量空间数据的存储、管理以及查询和计算成为了重要的应用需求。由于传统关系型数据库在存储、管理、检索空间数据对象方面存在诸多不足，因此空间数据库的概念应运而生。一方面由于空间数据对象的数据量庞大，另一方面由于运行查询语句中包含的对空间数据进行操作的函数开销很大，因而采用顺序扫描的方法是不可取的，采用空间索引来提高查询效率尤为必要。当前研究多集中在空间数据索引的研究上。
空间对象是现实世界中客观存在的，是空间分析的对象和客体。空间对象具有位置、大小等多重属性。检索空间对象的索引方式有很多种，其中基于网格的索引方式得到了广泛的认可与应用。而网格索引的多级划分非常有效，之前的一些研究论证已经对此做了实例上的
仿真验证。但是仅仅进行实验论证是一种不完备的验证方式，是一种枚举有限例子验证的不完全归纳方法，从理论论证角度而言逻辑上不严密，不够完备。有学者对多级网格的有效性进行了初步的数学论证，是一个很好的探索尝试，本文则对空间对象多级网格索引技术的有效性进行了全面详尽的严密数学论证。
1空间对象及空间索引
1.1基本概念
空间对象：地理信息系统中空间分析的客体和对象，是现实世界中客观存在的实体。人们能通过其具有的多重属性，如空间位置、大小、颜、质地等感知空间对象的存在。
空间索引：一种介于空间对象和空间操作之间的辅助性数据结构，包含空间对象的指针、标识等必要信息，依据空间对象间的关系或空间对象的特征条件排列。通过其可以筛选排除不符合检索条件的空间对象，可以提高检索效率和检索速度，从而减少检索时间。
空间检索：依据给定的空间检索要求，利用空间索引机制对特定空间对象的查搜索。
空间检索在实际中有许多应用要求，比如查一处所寻地点，查一条河流、公路的大体形状，查居民区、草原的分布情况等。为了便于处理，不管查询对象如何，都可以将查询对象抽象为点、线、面3种数学模型。
1.2空间对象的模型抽象
根据空间查询检索的精度限制和实际要求，可以将不同的对象依据其位置形状抽象为点、线或面的二维数学模型。（由于三维及以上维度空间对象的相关讨论非本文研究内容，且过于复杂，本文暂不考虑三维及以上的空间对象。）
点对象：查询空间中所要检索的某一个高速路收费站、路边的加油站，或大海中航行的一艘货轮等对象，可以将其抽象为一个点。
线对象：查询空间中要检索的一条公路或铁路，一条河流或某一沿海地区的海岸线，可以将之看作是线对象。
面对象：查询空间中检索的一片森林，一个盆地或高原的分布，一片海洋区域等类似查询对象可以视为一个面。
与上述3种对象对应的检索方式分别是点、线、面检索，即查检索空间内满足给定查询条件的点、线、面，以及其附近空间对象的查询检索。由于点、线、面之间内在构成的数学性质，可以将线看作是点的集合，面可以看作是线的集合，进而可把线、面两种形式都降维至点这种情形，一方面确实是由于其构成的数学性质可以使之可行；另一方面通过这种降维方式也大大简化了复杂情况的处理难度。
2多级网格索引
2.1网格索引
网格索引的基本思想是用横向和纵向的线条将查询空间划分为许多个格网，检索、存储包含于每个网格中空间对象的局部分布，最后统一处理得到所查询对象的总体分布情况。
相较于普通以像素点为查询基本单位的方式，网格查询以网格作为查询检索的基本单位，对于每一个网格，首先进行一次扫描，如果格内没有检索对象的分布，则向后进行另一网格的扫描；如果通过首次扫描发现此格内含有查询对象或对象的某一部分，那么再进行格内每个像素点的检索查询。这样显然比逐个像素点的查询方法检索效率要高得多，可以大大提升查询速度。
网格中含有点、线、面对象的情形如图1所示。
网格索引数据结构采用桶链表表示，如图2所示。假设一幅图被分成M*N个格。记每个格左下角的点为其坐标原点，则每个格表示为Block[k，j]，0
网格索引中网格划分得越细，检索查询的精度就越高，但与此同时对技术要求也更高，空间耗费更大。网格索引是一种多对多的静态数据结构 。
2.2多级网格索引
为了兼顾提高查询检索的精度和节省存储索引空间两个方面，提出了多级网格索引。
多级网格索引的基本思想是在格中再分割为若干更小的格，依照这种思路可以推广到n级网格，但是随着网格级数增加，会造成存储空间开销大和查询时效降低等不良影响，所以一般情况下根据实际应用要求，划分级数为二级或三级即可满足需求。
多级网格中的包含与被包含关系为：对象或对象的某一部分包含于本级网格，则其必也包含于上一级网格中；而与之对应的，本级网格中虽然包含对象或对象的某一部分，但下一级网格却不因为包含于本级网格就必须包含对象或对象的某一部分。
3多级网格有效性的数学证明
3.1一级网格有效性的证明
前置假设：
①设定像素点为检索查询的最小基本单位，图幅像素点阵为m*n；
②检索范围为整个图幅，每个像素点的检索查询是相互独立的；
③设每个像素点被检索对象覆盖的概率为p。
一级网格检索机制将图幅划分为M*N个格， 如果格内不包含所要检索的对象，则检索只进行1次，否则将进行m/M*n/N+1次检索。如果直接在整幅图像上进行检索（经典检索机制），则需要检索每个像素点，即检索的次数为m*n。证明：令K=（m*n）/（M*N），则K是每个格内的像素点个数。根据假设③，像素点不被空间对象objx覆盖的概率为q=1-p。以像素点个数作为考察对象，设桶内有个像素点被objx覆盖，则Z为随机变量，Z空间歌曲查询符合二项分布，分布律为：
发布评论