空间数据库是近年的热点研究领域，是一门前沿的交叉学科。本书全面介绍了空间数据库的概念、应用领域、查询语言、空间数据的索引和存储机制、空间查询处理和优化等内容，对空间数据挖掘和空间数据仓库也有精彩的论述。本书条理清晰，叙述严谨，实例丰富，曾得到业内权威人士的赞誉。本书的每章之后都附有习题，帮助读者检验学习效果。本书既适合作为计算机及相关专业的本科生、研究生的教材，也适合IT业的研究人员、技术人员阅读。对于想了解空间数据库的初学者来说，本书也是一本极有价值的参考书。
无
近年来，许多计算机应用领域通过扩充数据库管理系统的功能来支持与空间相关的数据。空间数据库管理系统（spatial database management system, SDBMS）研究是找到有效处理空间数据的模型和算法的重要步骤。
经过20多年的发展，空间数据库已成为一个热点研究领域，其研究成果（如空间多维索引）开始应用于许多不同领域。正是已有应用的需求推动了空间数据库管理系统的研究，这些应用包括地理信息系统（geographical information system, GIS）和计算机辅助设计（computer-aided design, CAD），以及诸如多媒体信息系统、数据仓库、美国国家航空航天局（national aeronautics and space administration, NASA）的地球观测系统等潜在应用。这些空间应用拥有上百万的使用者。
商业数据库的主要厂商已推出专门处理空间数据的产品，其中包括ESRI开发的空间数据引擎（spatial data engine, SDE），以及Intergraph、Autodesk、Oracle、IBM和Informix等公司在对象-关系数据库服务器上开发的空间数据插件，研究的原型系统有Postgres、Geo2和Paradise。这些系统都提供一组空间数据类型（如点、线和多边形）和一组空间操作功能（求交（intersection）、闭合（enclosure）和距离（distance））。开放地理信息系统（Open Geographic Information System, OGIS）协会制定出一套空间数据类型和空间操作的现行标准，使得空间类型和操作可以像SQL3那样成为对象-关系查询语言中的一部分。为了增强性能，这些系统还为空间存取方法、空间范围查询以及空间连接提供了多维空间索引和算法。
把空间数据集成到传统数据库中意味着要在不同层次上解决许多重要问题，这些问题的范围广泛，从关于空间建模的深奥本体论问题（例如，“它应该是基于场的还是基于对象的”，很像物理学中的波粒二象性）到文件管理这类平凡但重要的问题。这些不同课题使空间数据库管理系统研究实际变为多学科的问题。
我们用一个国家数据集的例子来说明空间数据库的特别需求。一个国家至少有一个非空间的数据（国名）和一个空间数据（国界）。国名的存储或表示不会产生任何问题，但国界的存储或表示就不那么简单了。假定用一个直线段的集合表示国界，这时会要求数据库系统能支持空间数据类型“线”、“点”和“面”，以便对“国家”这个对象进行空间查询。操作和组合这些新的数据类型需要遵从某些固定的规则，于是空间代数便应运而生了。由于空间数据具有可视性和数据量庞大的性质，所以必须扩展数据库系统以提供可视化查询处理和特殊的空间索引。数据库的其他重要问题（如并发控制、批量加载、存储和安全机制等）也都必须重新加以考虑和调整，以便构建高效的空间数据库管理系统。
本书以明尼苏达大学的科学数据库（Csci 8705）这门研究生课程的讲义为蓝本。计算机科学系及其他系的研究人员与学生都认为该课程非常有用并能应用到他们的工作中。尽管这样的科目在学生中得到很好的反响并引起他们极高的兴趣，但市面上却找不到一本教材能满足听课者对多学科的需要。最近，[Scholl等，2001]写的一本书主要介绍了与查询语言和访问方法有关的传统主题，并没有涉及像空间网络（比如，道路地图）和空间模式的数据挖掘这类流行的主题。Adam和Gangopadhyay在1997年编篡了一本GIS领域中与数据库相关的问题的专著，但是没有提到业界的最新技术。另一本关注GIS的书[Worboys著，1995]也只有两章讨论了数据库问题。这类书多数没有采用像OGIS这样的行业标准，也缺乏适当的辅导，例如在每一章节后面提供习题和讨论问题，帮助学生理解主要概念。毫无疑问，从事数据库、并行计算、多媒体信息、土木机械工程和林业方面的学术研究的人员迫切需要一本详尽叙述空间数据库的教材。一项调查表明，业界的专业人员，包括GIS和CAD/CAM软件的开发者，也希望了解有关空间数据库的知识。
在开始撰写本书之前，我们完成了一份“空间数据库：成就和研究需求”（Spatial Databases: Accomplishments and Research Needs）的调研报告，发表在 IEEE Transactions on Knowledge and Data Engineering (1999年1月)上。我们发现计算机科学方面的文献多侧重于研究某些特定问题（例如空间索引、空间连接算法），而很少涉及其他许多重要问题（例如空间数据的概念建模）。在本书有关这些问题的章节中，我们参考了来自GIS业界和非计算机科学专业的GIS研究人员的很多思想和观念。
从1998年的假期开始，我们着手编写本书。通过充实原有的课程讲义，完成了许多章的初稿。本书的初稿在明尼苏达大学的数据库课程中使用。随后，利用审校人、同事和学生的反馈，对本书进行了修订。
本书的特点如下：
●本书旨在提供空间数据库管理系统的全面概述。它不仅涵盖传统主题（如查询语言、索引和查询处理），还包括许多目前流行的问题（如空间网络和空间数据挖掘）。
●每章都提供一组习题，读者可以测试自己对核心概念的理解，将这些概念应用于新的领域，甚至举一反三地应用该章内容。本书的网站还安排附加的教学辅导（例如实验、课程讲义等）。
●尽量将视野超越GIS。空间数据库管理系统技术在许多领域得到应用，包括多媒体信息、CAD/CAM、天文学、气象学、分子生物学和计算力学。
●每章都尝试给出对象-关系数据库的框架，这是商业数据库应用的发展趋势。在适当的情况下，该框架允许空间数据库重用关系数据库的功能，同时根据需要来扩展关系数据库的功能。
●采用符合标准（例如OGIS）的空间数据类型和操作来说明常见的空间数据库查询。这些遵从标准的类型和操作可以兼容像SQL-3这样的对象关系查询语言。
●本书内容自成一体，读者无需具备GIS或数据库的知识。
●完全覆盖空间网络的建模、查询和存储方法等各个方面。
●详尽讨论有关空间数据挖掘的问题。
●既有前沿研究的讨论，也有商业趋势的讨论。
●包含很多易于理解的常识性应用领域的例子。
本书组织方式
本书共有8章，每一章介绍空间数据库的一个重要部分。第1章介绍空间数据库的基本概念。第2章重点介绍空间数据模型，引入场和对象的二分概念，以及它们在数据库设计中的应用。第3章探讨如何扩展传统查询语言来支持空间数据库，广泛讨论各种扩展SQL空间能力的提议。第4章描述空间数据存储和索引方案。由于空间数据库处理的是海量数据，所以提供合理的存储、压缩和索引方法来提高查询处理的性能，对于数据库管理系统来说至关重要。第5章从查询语言和索引入手，继续讨论查询处理和优化。此时读者会发现，要放弃或从根本上修改传统数据库的许多标准技术才能使之应用于空间问题。该章还引入空间查询处理中的过滤-精炼策略。第6章说明如何将空间数据库技术应用于空间网络，该章还将介绍网络数据模型和查询语言。第7章全面涵盖新兴的空间数据挖掘领域。在这一章我们为读者揭示出空间数据集合普遍存在的空间依赖性，以及如何对其建模并整合到数据挖掘过程中。第8章讨论空间数据库的发展趋势。
序1
早在三万五千年前，克鲁马努猎人就在法国拉斯科附近的洞穴岩壁上绘制行走轨迹图形和有意义的刻符来描绘迁徙路线。从那时起，人们就使用带有地理信息的图形了。今天，地理信息系统（GIS）得到广泛的应用：从跟踪北美驯鹿和北极熊的迁徙路线，确定石油开采对野生动物的影响，协助农民最低限度地施用杀虫剂，帮助公司供应部门的经理预测配送仓库的最佳设立位置，直到建立降水和航空照片信息与湿地在每年特定季节变干之间的联系。
从最严格的意义上讲，地理信息系统是一个计算机系统，用于汇集、存储、操纵和显示与位置相关的数据。然而，现代地理信息系统通常要从多个不同来源接收各种形式的数据，以便处理查询和帮助分析信息。从广义上讲，地理信息系统不仅能将地理信息转换和存储为数字形式进行分析，也必须能在空间数据库中进行收集、变换、聚集、索引、链接和挖掘。现代地理信息系统能够集成用其他方法很难关联起来的信息，同时可以结合地图化的变量来构建和分析新变量。
Shekhar和Chawla正是从这种高度完成了一项展示地理信息处理的原理和趋势的非凡工作。本书是讲述概念与方法的力作，循序渐进地讲解模型、语言和算法，层次清晰，结构合理。作者不仅解释概念，而且使用大量例子加以说明。本书强调了将空间数据集成到传统数据库中的很多重要主题，从深奥的空间建模本体论问题到重要的文件管理问题无不涉及。每一章后面都有许多引人思索的习题，帮助读者更好地理解书中的概念和算法。本书最后所展示的空间数据挖掘和空间数据库未来发展趋势尤为精彩，有助于读者了解新兴的研究领域。
本书适合作为地理信息系统方面交叉学科的课程教材，也可以作为该领域从业人员的参考书。即使没有受过正规数据库方面的培训，读者也可以轻松地理解和应用从书中学到的概念和算法。其他学科背景的人也能从本书所讲述的技术中获益，使这些技术得以广泛地应用于政府、商业和工业等部门。
本书是空间数据库领域的第一本著作，作为本书的读者，我确信，从这个令人兴奋和有重要意义的领域中所学到的一切将使你获益匪浅。
Benjamin Wah
伊利诺斯大学电子与计算机工程系教授
IEEE计算机协会主席
序2
空间信息，也就是在某个空间框架（例如地球表面）中对象的位置信息，长期以来被视为特殊的计算问题。早在1972年，空间数据处理（spatial data handling）这一术语就开始使用，它是指一群研究人员的研究活动。这些研究人员承诺共同开发电子化的数据处理方法，用以提高诸如地图编撰、地图测量和空间数据分析等领域的生产率。在高层结构中经常会用到空间信息。尽管在20世纪60年代就开始出现的每一个经典数据库管理模型都对空间应用领域有所考虑，但不管是关系模型还是面向对象的建模都不能完全适合这一领域。关系模型能够较好地处理拓扑关系，但对表示横跨空间区域的复杂层次关系却无能为力；而面向对象模型能够处理拓扑和层次关系，但难以处理空间中重要的连续性现象。
阐述空间数据库这一内容纷繁的领域的书籍可谓凤毛麟角，因此本书一定会大受欢迎。它涵盖了整个空间数据库领域，以清晰的概念、有条理的结构和严谨的表述，介绍了从表现、查询到分析的各个方面。数据挖掘一章尤其受人欢迎，它不仅讲述传统的空间数据分析方法，而且介绍近几年来发展的许多新技术。这些技术利用当今的高速计算能力，能够在超大型空间数据库中自动搜索异常情况和模式。本书是为计算机系的学生编写的，但同样适用于那些具有其他学科背景又希望学到比一般地理信息系统教材更严谨和更基础的方法的学生。
空间数据库的重要性日益增加，其中一个原因在于其应用范围已超出传统GIS领域。位置和时间是鉴别和刻画信息的强有力方法，因为许多数据集都具有空间和时间的“印记”。地图和地球照片显然如此，而许多报告、书籍、照片以及其他类型的信息亦不例外。因此，位置信息成为在分布的信息源（如因特网）中搜索相关信息的强大基础。人们逐渐认识到，空间（和时间）提供了集成信息的重要方法，这些信息已经远远超出了传统的空间数据库和GIS领域。本书在最后一章探讨了其中一些问题，并对许多人深信空间数据库的重要地位在未来几年会快速提升的原因提出了自己的见解。
Michael F. Goodchild
美国国家地理信息及分析中心，加州大学地理系
(美)Shashi Shekhar,Sanjay Chawla：Shashi Shekhar: 明尼苏达大学计算机科学系教授，该校空间数据库研究组的负责人。在加州大学伯克利分校获得博士学位。他由于在空间数据库存储方法、数据挖掘以及地理信息系统等方面的贡献而成为IEEE特别会员。迄今为止发表了大量学术文章并担任多个组织在空间数据库专题方面的学术顾问。
Sanjay Chawla: 马萨诸塞州Vignette公司的高级技术顾问。在田纳西大学获得博士学位。
谢昆青 马修军 杨冬青 等：杨冬青: 1969年毕业于北京大学数学力学系数学专业，现任北京大学信息科学技术学院教授，博士生导师，网络与信息系统研究所副所长，数据库与信息系统研究室主任，中国计算机学会数据库专委会委员。多年来承担并完成973、863国家科技攻关、国家自然科学基金等多项国家重点科研项目;曾获国家科技进步二等奖、三等奖和多项省部级奖励;在国内外科技杂志及会议上发表论文百余篇，著译作十余部。目前的主要研究方向为数据库系统实现技术、Web环境下的信息集成与共享、数据仓库和数据挖掘、典型应用领域的数据库技术等。
空间信息是指与位置（特别是地理位置）有关的信息，它在信息中占有相当大的比例（有人统计可以达到80%）。然而，空间信息又有其特殊的一面，它具有诸如数据量巨大、结构复杂多样、操作是计算密集型的、具有自相关性等特性。随着IT技术的迅速发展，以GIS为代表的空间信息技术在各领域得到了应用，同时遥感等空间信息获取技术不断进步，现代社会对位置服务和分析决策的需要也日益迫切，因此深入研究和掌握空间信息技术的理论与方法的重要性也日益凸显出来。
本书深入浅出地介绍了空间数据库的相关内容和知识。作者以清晰、有条理和严谨的方式，系统地阐述空间数据库的表达、查询和分析等诸多方面，举例通俗恰当，各章都附有针对性练习。本书对空间数据挖掘和空间数据仓库等当前热点研究的精彩描述，得到了Benjamin Wah教授、Michael F. Goodchild教授以及微软的Jim Gray等业内权威人士的高度评价。空间数据库方面的专著可谓凤毛麟角，许多著作只是涉及其中的部分内容，而本书却系统全面地论述这个主题，并采用业界标准，兼顾前沿研究、商业化趋势以及初学者实践几个方面，是一本不可多得的教材。
本书的内容安排如下：
●第1章介绍空间数据库学科的应用领域和背景知识。
●第2章介绍空间数据模型。
●第3章介绍传统查询语言的空间扩展，并对扩展SQL的空间特性进行讨论。
●第4章论述空间数据存储和索引机制以及压缩方法，探讨提高查询处理性能的途径。
●第5章介绍空间查询处理和优化的方法，包括过滤-精炼策略。
●第6章是空间数据库技术在空间网络方面的应用，包括网络数据模型和查询语言。
●第7章介绍空间数据挖掘，包括空间依赖概念及其建模方法。
●第8章讨论栅格数据库、基于内容的检索方法以及空间数据仓库的发展趋势。
译 者
译者序
序1
序2
前言
图目录
表目录
第1章 空间数据库简介 1
1.1 概述 1
1.2 空间数据管理的适用人群 2
1.3 GIS和SDBMS 3
1.4 空间数据库的三类用户 4
1.5 一个SDBMS的应用案例 6
1.6 空间数据库概览 12
1.6.1 空间分类学和数据模型 12
1.6.2 查询语言 14
1.6.3 查询处理 14
1.6.4 文件组织和索引 18
1.6.5 查询优化 21
1.6.6 数据挖掘 22
1.7 小结 22
1.8 参考书目 23
1.9 习题 24
第2章 空间概念和数据模型 27
2.1 空间信息模型 28
2.1.1 基于场的模型 30
2.1.2 基于对象的模型 32
2.1.3 空间数据类型 32
2.1.4 空间对象的操作 33
2.1.5 动态空间操作 37
2.1.6 将空间对象映射到Java 38
2.2 数据库设计的三个步骤 41
2.2.1 ER模型 42
2.2.2 关系模型 45
2.2.3 将ER模型映射到关系模型 46
2.3 趋势：扩展ER模型表达空间概念 49
2.4 趋势：用UML构建面向对象数据模型 54
2.5 小结 57
2.6 参考书目 58
2.7 习题 58
第3章 空间查询语言 63
3.1 标准数据库查询语言 64
3.2 关系代数 66
3.2.1 选择和投影运算 67
3.2.2 集合运算 68
3.2.3 连接运算 69
3.3 SQL基础 71
3.3.1 DDL 71
3.3.2 DML 72
3.3.3 SQL查询的基本格式 73
3.3.4 SQL查询示例 73
3.3.5 RA和SQL小结 76
3.4 扩展SQL以处理空间数据 77
3.4.1 OGIS标准的SQL扩展 77
3.4.2 OGIS标准的局限性 79
3.5 强调空间的查询示例 79
3.6 趋势：对象-关系SQL 84
3.6.1 SQL3概览 85
3.6.2 对象关系模式 85
3.6.3 查询示例 88
3.7 小结 88
3.8 参考书目 89
3.9 习题 89
3.10 附录：州立公园数据库 93
第4章 空间存储和索引 99
4.1 存储：磁盘和文件 101
4.1.1 磁盘的几何结构和含义 102
4.1.2 缓冲区管理器 103
4.1.3 域、记录和文件 104
4.1.4 文件结构 105
4.1.5 聚类 107
4.2 空间索引 114
4.2.1 网格文件 116
4.2.2 R树 118
4.2.3 代价模型 123
4.3 趋势 123
4.3.1 用于对象分解的TR*树 123
4.3.2 并发控制 125
4.3.3 空间连接索引 127
4.4 小结 131
4.5 参考书目 132
4.6 习题 133
第5章 查询处理与优化 137
5.1 空间操作计算 138
5.1.1 概述 138
5.1.2 空间操作 138
5.1.3 对象操作的两步查询处理 140
5.1.4 空间选择技术 141
5.1.5 一般的空间选择 142
5.1.6 空间连接操作算法 143
5.1.7 空间聚集操作策略：最近邻居 146
5.2 查询优化 147
5.2.1 逻辑转换 148
5.2.2 基于代价的优化：动态规划 152
5.3 空间索引结构分析 154
5.3.1 枚举可选的计划 157
5.3.2 混合体系结构中的分解与归并 158
5.4 分布式空间数据库系统 158
5.4.1 分布式DBMS体系结构 160
5.4.2 半连接操作 161
5.4.3 基于Web的空间数据库系统 161
5.5 并行空间数据库系统 165
5.5.1 硬件体系结构 165
5.5.2 并行查询计算 167
5.5.3 应用：实时地形可视化 169
5.6 小结 172
5.7 参考书目 173
5.8 习题 174
第6章 空间网络 177
6.1 网络数据库示例 178
6.2 概念数据模型、逻辑数据模型和物理数据模型 179
6.2.1 逻辑数据模型 179
6.2.2 物理数据模型 182
6.3 图的查询语言 185
6.3.1 关系代数的缺陷 186
6.3.2 SQL CONNECT 子句 187
6.3.3 BART系统的查询示例 190
6.3.4 趋势：SQL3的递归 192
6.3.5 趋势：SQL3的网络ADT 193
6.4 图的算法 194
6.4.1 路径查询处理 195
6.4.2 图遍历算法 195
6.4.3 单对(v,d)最短路径的Best-first算法 199
6.4.4 趋势：层次策略 199
6.5 趋势：空间网络存取方法 203
6.5.1 网络操作的I/O代价度量 204
6.5.2 减少磁盘I/O的图分区方法 206
6.5.3 CCAM: 一种连接性聚集的空间网络存取方法 208
6.6 小结 209
6.7 参考书目 210
6.8 习题 210
第7章 空间数据挖掘简介 213
7.1 模式发现 214
7.1.1 数据挖掘过程 215
7.1.2 统计学和数据挖掘 216
7.1.3 将数据挖掘作为搜索问题 217
7.1.4 空间数据挖掘的独特性 218
7.1.5 历史上著名的空间数据探测案例 218
7.2 空间数据挖掘的动机 219
7.2.1 应用领域示例 219
7.2.2 空间形态和自相关的度量 221
7.2.3 空间统计模型 224
7.2.4 数据挖掘的三位一体 225
7.3 分类技术 227
7.3.1 线性回归 228
7.3.2 空间回归 228
7.3.3 模型评估 229
7.3.4 采用图相似度预测位置 231
7.3.5 马可夫随机场 232
7.4 关联规则发现技术 235
7.4.1 Apriori：计算频繁项集的算法 236
7.4.2 空间关联规则 238
7.4.3 同位规则 239
7.5 聚类 239
7.5.1 K-medoid聚类算法 243
7.5.2 聚类、混合分析和EM算法 245
7.5.3 大型空间数据库聚类的策略 248
7.6 空间孤立点检测 250
7.7 小结 256
7.8 附录：贝叶斯演算 257
7.8.1 条件概率 257
7.8.2 最大似然 258
7.9 参考书目 258
7.10 习题 259
第8章 空间数据库发展趋势 265
8.1 支持场实体的数据库 266
8.1.1 栅格与图像操作 267
8.1.2 存储和索引 270
8.2 基于内容的检索 271
8.2.1 拓扑相似性 272
8.2.2 方位相似性 273
8.2.3 距离相似性 274
8.2.4 属性关系图 274
8.2.5 检索步骤 276
8.3 空间数据仓库概述 276
8.3.1 聚集操作 277
8.3.2 几何聚集的例子 280
8.3.3 聚集层次 280
8.3.4 哪些地方用到聚集层次 283
8.4 小结 286
8.5 参考书目 287
8.6 习题 288
参考文献 293
