论文摘要
空间数据库是随着地理信息系统的开发和应用而发展起来的数据库新技术。空间数据库的性能问题严重制约了它的应用与发展。空间数据库中最重要的一种空间查询是空间连接查询,即从两个数据集合中检索出所有满足某一空间谓词（如交、包含等）的空间对象。由于空间连接运算是空间数据库中最复杂、最耗时的基本操作,因此其处理效率在很大程度上决定了空间数据库的整体性能。尽管目前已经有许多空间连接算法,但空间连接运算的代价估计和查询优化仍然有待进一步研究。本课题在仔细研究目前多种空间数据库查询方法的基础上,提出了一种新的空间对象的近似—栅格近似。这种新的近似方法在MSQP中作为一种过滤器来处理空间连接,包括三种基本数据类型和它们之间不同的空间连接。论文提出了三色栅格图（3CRS——Three-Color Raster Signature）。3CRS是在4CRS的基础上提出的。3CRS是一种基于栅格单元的空间对象的压缩和近似表示。每一种颜色代表了对象和单元格之间的一种相交类型。事实上,3CRS是一个4CRS,其中4CRS中的Weak和Strong单元类型分别被Inconclusive单元类型所代替。Weak类型代表一种多边形,这种多边形和单元格相交的区域小于等于50%,而Strong类型代表了另一种类型的多边形,这种多边形与单元格相交的区域大于50%而小于100%。3CRS的Inconclusive类型代替了4CRS的这两种类型,它代表单元格和对象相交,但是并没有完全被多边形占据。这种特性使得3CRS能用来表示多线和点这两种空间数据类型。3CRS的优点是加快产生时间而且可以用于表示多边形,多线和点（没有任何具体特征）。同时,可以用算法来评估包含这三种数据类型的连接谓词。分析了3CRS单元格的基本类型,给出了3CRS的生成算法和标度变化算法。最后,给出了基于3CRS的空间连接比较算法。同时对其进行了分析,分析结果表明本文所提方法是有效的。