高级数据库技术第10章空间数据库.ppt
2023/4/3,1,第10章 空间数据库,10.1 空间数据库概述,2023/4/3,2,10.1.1空间数据库的意义,从本体论的角度，研究和开发空间数据库的意义主要基于下述几个方面。1时间和空间是物质存在的基本方式 2空间数据是某些重要应用的基本形式3复杂的非空间数据可以作为空间数据处理,2023/4/3,3,10.1.2空间数据基本特征,1数据量大 结构复杂 数据联系多样化2查询过程复杂3空间对象间难以定义次序,2023/4/3,4,10.1.3空间数据库作为常规数据库扩充,由于空间数据库系统理论和技术还处于发展过程当中，而实际应用的需求又非常迫切，同时常规数据库（关系数据库）仍然是当今主流数据库，所以目前空间数据库是作为常规、传统数据库的扩充出现。在这种情况下，空间数据库主要包括下述一些方面的内容：,2023/4/3,5,空间数据模型 基于实际应用，引入各种必须的空间数据类型，并讨相应的数据操作。空间索引 由于空间对象之间难以合适的定义“序”，所以空间数据的索引就成为空间数据库技术的一个重要课题，在这方面已经取得了相当成熟的结果，并且应用到其他的领域。空间数据库管理系统 空间数据模型和当前主流数据模型关系数据模型具有较大的差异，需要研究如何在RDBMS基础上有效扩充空间数据管理功能的问题。,2023/4/3,6,10.2 空间数据模型,10.2.1空间数据模型空间数据模型与其它数据模型相比，一个突出的特点就是其模型的提出、引入与相应的实际应用密切相关。空间数据库的一个重要应用领域是GIS。人们通常就以GIS为应用背景，介绍其中的基本空间数据类型。我们这里的介绍主要以二维空间数据类型为主，但完全可以推广到三维以上的情形。,2023/4/3,7,在GIS中，基本空间数据类型由下述三种空间对象组成：（1）点（Point）例如城市。点只表示其空间位置，不表示其范围（extent）（2）线（Line）例如河流、道路、管道、航线、等高线、等降雨线、通信或电力线路等。线不仅表示线上各点在空间的位置，而且还有长度，即表示其在空间的延伸范围。（3）区域（Region）例如森林、湖泊、行政区域等。区域不但有位置，而且有面积、周长等参数，以表示其覆盖范围。,2023/4/3,8,以上三种是最基本空间数据类型，以此为基础，还可以导出下面两种空间数据类型：（4）划分（Partition）一个区域可以是按其自然、行政或其他特征，分成若干个区域。如果这些子区域互不相交，但其“并”覆盖该区域，则此子区域的集合就称为该区域的一个划分。国家行政区域划分图，土地利用图等都是划分的例子。划分可嵌套，例如国家分成省市，省市分成县区、县区分成乡镇等。,2023/4/3,9,（5）网络（Network）网络是由若干点和一些点与点之间的联线组成。例如公路网、河网、电力网、电话网、交通线路图等都是网络的例子。,2023/4/3,10,10.2.2空间对象所处的环境,1.欧氏空间 设R表示实数域，V是R上向量的非空集合，如果在V上定义了满足如下条件并称之为内积的一个二元函数，则称V为R的欧氏空间：非负性 0，=0 x=0，xV对称性=线性性=+，R；x，y，zV直线R，平面R2和空间R3通过适当的定义内积都是欧氏空间。,2023/4/3,11,2.在欧氏空间中讨论空间对象间的关系我们主要在欧氏空间的环境中定义所有空间对象相互间关系的，这些关系可以分为基于集合、拓扑、.方位和.度量的关系，我们在下面分别讨论。,2023/4/3,12,10.2.3 空间对象之间关系,1.基于集合的关系基于集合的空间对象关系主要有元素与集合的属于及不属于的关系，集合与集合的包含、相交、并等关系。在空间对象间的层次关系就适合用集合的关系理论来讨论，例如城市包含公园，公园包含树林等。,2023/4/3,13,2.基于拓扑的关系基于拓扑的空间对象关系主要有邻接（meet）、包含（within）和交叠（overlap），这三类拓扑关系也是空间数据查询中最有可能出现的情况。空间数据库中，基于拓扑的查询需要解决这样两个问题：查询所有与给定对象具有某种拓扑关系R的空间对象。对象A和B具有怎样的拓扑关系。,2023/4/3,14,在平面上，两个对象A和B之间的二元拓扑关系时基于以下对象成分的相交（insection）关系：A的内部A，A的边界A，A的外部A-。B的内部B，B的边界B，B的外部B-。,2023/4/3,15,对象的这六个部分分别构成九种相交情况：AB，AB，A B-；AB，A B，A B-；A-B，A-B，A-B-。,2023/4/3,16,考虑到0，1取值情况0，1，可以确定有29=512种二元拓扑关系，这里，人们研究其中的八种彼此互斥关系：相离（disjoint），邻接（meet），交叠（overlap），相等（equal），包含（contain），在内部（inside），覆盖（cover）和被覆盖（covered by）。,2023/4/3,17,3.基于方位的关系 绝对方位 即在全球定位系统背景下定义的方位，例如东、西、南、北，东南、西南、东北等。相对方位 即根据与给定目标的方向来定义的方位，例如左右、前后、上下等。基于观察者的方位 即按照专门指定的称为观察者参照对象来定义的方位。,2023/4/3,18,4.基于度量的关系设有一个集合E，如果在E上定义了一个二元函数d（x，y），x，yE，满足如下条件：（1）非负性 d（x，y）0（2）对称性 d（x，y）=d（y，x）（3）三角不等性 d（x，y）d（x，z）+d（z，y）则称V是一个度量空间，d（x，y）称为V上的度量函数。,2023/4/3,19,考察一个空间的“测度”，例如线段的长度，平面图形的面积，空间立体的体积，以及一个空间对象相对于另一个空间对象的距离等都是基于度量的关系。,2023/4/3,20,10.2.4空间数据操作的谓词描述,从理论上讲，空间数据操作特别是空间数据查询的基础是空间对象之间的相互关系，从实际上看，由于空间数据类型取决于实际应用，空间数据操作主要也由现实中的应用所决定。下面主要介绍一些从空间对象相互关系角度考虑的相对比较基本的通用操作，而由应用的多样性，与应用密切相关的操作不拟一一介绍。空间数据操作的描述可以有谓词形式、集合形式和代数形式三种。,2023/4/3,21,1.基本符号先定义空间数据操作中的一些记号。SDT 空间数据类型 ZS 大小为零（zero size）空间数据类型，例如点 NZS 大小非零（non-zero size）的空间数据类型，例如线、区域等 ADT 原子（atomic）空间数据类型 例如点、线、区域 CDT 集合型（collection）空间数据类型，例如网络、划分等,2023/4/3,22,PT 点 LN 线 RG 区域 PTN 划分 NTW 网络,2023/4/3,23,2.基于拓扑的描述两个同类型空间数据是否相等（=或）PTPT BoolLNLN BoolRGRG Bool空间数据SDT是否在区域RG中（INSERT）SDT RG Bool,2023/4/3,24,两个大小非零的空间数据是否相交（INTERSECTS）NZS NSZ Bool两个区域是否邻接（ISNEIGHBOROF）RGRGBool,2023/4/3,25,3.基于集合运算的描述（1）相交（Intersection）两条线相交为点的集合LNLNPT线与区域相交为线的集合LNRGLN区域与区域相交为区域的集合RGRGRG,2023/4/3,26,（2）重叠（OVERLAP）PTNPTNFG（3）中心点（CENTER）NZSPT,2023/4/3,27,4.基于度量的描述两点间距离（DIST）PTPT NUM DIST两空间图形间的最大、最小距离（MAXDIST，MINDIST）SDTSDTNUM MAXDIST或MINDIST,2023/4/3,28,多点的直径（DIAMETER）PT NUMDIAMETER线的长度（LENGTH）LN NUM LENGTH区域的周长（PERIMETER）或面积（AREA）RG NUM PERIMETER 或AREA,2023/4/3,29,10.2.5空间关系的集合描述与判断,在空间数据库中，空间关系主要用于查询。为了获得可以接受的查询效率，常常把空间对象用点、矩形和方盒等简单，规则的图形表示。因此，只需要讨论这些规则几何图形的空间关系即可。这里，规则的几何图形可以看做空间中标准的“点集合”，因此，空间数据操作的集合描述就是这些标准集合间关系的描述。,2023/4/3,30,1.一维空间中两个线段的关系一维空间中两个线段的7种可能的关系，分别用记号“=、%、/、|、”表示。图10-4表示了这些关系，其中，（1）（5）是相交关系，（6）（7）是非相交关系。设A、B线段的起点和终点分别为x1A，x2A，x1B，x2B，则（1）（5）的关系可以归纳为maxx1A，x1Bminx2B，x2B,2023/4/3,31,2023/4/3,32,2.二维空间中边平行于坐标轴矩形间的关系设A、B为这种矩形，其左下角坐标和右上角坐标分别为（x1A，y1A），（x2A，y2A）和（x1B，y1 B），（x2 B，y2 B）。可以得到，如果A和B在x轴和y轴上的投影分别相交，则A、B相交。因此，A，B相交的条件可以表示为max x1A，x1B min x2A，x2B 和max y1A，y1B min y2A，y2B,2023/4/3,33,10.2.6空间关系的代数描述与运算,空间代数运算的特点在于选择条件或连接条件中出现空间谓词。投影、集合运算不涉及空间谓词，与关系代数没有本质区别。下面讨论空间选择和空间连接。,2023/4/3,34,1.空间选择例10-1 写出下列空间选择表达式。选择广东省所有城市：F（城市）其中，F=CENTER（城市地图）INSIDE 广东;城市是关系名，其中有属性“城市名”、“人口”、“城市地图”。城市地图表示市区及其周边地区，“广东”是一个区域名称。显然，如果城市中心点在广东省区域内，则该城市一定属于广东省,2023/4/3,35,选择广东省的所有河流：F（河流）其中 F=ROUTE（河流）INSIDE广东;“河流”是关系名，其中有属性“河流流域图”。ROUTE是空间数据库中的一个函数，计算河流、道路等的中心线。选择距离广州小于等于100000米，人口大于等于50万的所有城市：F（城市，广东区域图）其中F=DIST（城市名，广州）500000;城市是个关系，“广州”是城市名，F中的第一个谓词是空间谓词，要用到广东省地图。,2023/4/3,36,2.空间连接例10-2 对每条河流找出沿河10000米的所有城市设“河流”、“城市”是两个关系。在关系“河流”中，有属性“河流流域图”。如果城市中心距离河流小于等于10000米，则该城市和河流匹配。可以用空间连接表示如下：河流名，城市名（河流 F城市）其中，F=Mindist（城市名，ROUTE（河流流域图）10000,2023/4/3,37,10.2.7空间数据查询语言,一般在SQL语言基础上扩充空间数据类型及其操作和相应的保留字。由于这些扩充与应用有关，目前还未形成标准，以下列举一些例子予以说明。,2023/4/3,38,例 10-3选择广东省所有城市及其人口：select 城市名，人口from 城市where center（城市地图）inside广东省；,2023/4/3,39,选择流经广东省所有河流的河流名及其在广东省境内的长度：select 河流名，length（intersection（route（河流流域图），广东）from 河流where route（河流流域图）intersects广东；,2023/4/3,40,选择距离广州小于等于100000米，人口大于等于50万的所有城市：select 城市名，人口from 城市，广东区域图where dist（城市名，广州）500000；,2023/4/3,41,例10-4 将例10-2表示的查询用SQL风格表示出来select 河流名，城市名from 河流，城市where mindist（城市名，ROUTE（河流流域图）=10000,2023/4/3,42,10.3 空间索引,空间数据库查询的开销一般比关系数据库大，特别是空间谓词求值的开销远比数值或字符串的比较要大。若采用顺序扫描方法进行查询，则效率就会很低，因此采取空间索引十分必要的。,2023/4/3,43,10.3.1空间索引概述,1.空间索引的思路为了减少开销，通常是采用近似规则图形例如边平行于坐标轴的最小矩形来代替不规则土星进行查询。这种矩形就称为不规则区域的最小限定矩形（minimum bounding rectangle，MBR）。设MBR左下角坐标为（x1，y1），右上角为（x2，y2），则x1，y1就分别为空间对象的最小横坐标和纵坐标，x2，y2分别为空间对象的最大横坐标和纵坐标。不但区域可以用MBR近似表示，线也可以用MBR近似表示；进一步，不但单个空间对象可以用MBR近似表示，有时MBR还可以包含多个空间对象。最小限定矩形如下图所示。,2023/4/3,44,2023/4/3,45,如果一个MBR还含有另外的MBR，则称其为目录MBR，否则就称为对象MBR。如果两个空间对象相交，则相应的MBR也相交；如果两个MBR不相交，则对应的两个空间对象也不相交。这样，用MBR代替空间对象检查相交情况，就可以排除一批不相交的对象。,2023/4/3,46,当然，两个MBR相交，并不能得出对应的空间对象一定相交，此时还需要用精确方法对MBR相交的空间对象逐个进行检验，找出真正相交的情形。先用高效率的近似方法进行粗选，再用精确方法 进行精选，这是空间数据库中常用的搜索方式。,2023/4/3,47,2.空间索引的特点,（1）索引对象的无序性（2）索引对象的不规则性（3）索引对象的交叉性,2023/4/3,48,10.3.2空间对象的近似表示,1.点点不但是基本的空间数据类型之一，而且多属性的检索也相当于多维空间点的搜索。有些规则图形也可以用高维空间的点表示。例如一维空间的线段a,b可以用二维空间的点（a，b）表示。二维空间的边平行于坐标轴的矩形（x1，y1），（x2，y2）可以用四维空间的点（x1，y1，x2，y2）表示，式中（x1，y1），（x2，y2）分别为矩形的左下角和右上角坐标。,2023/4/3,49,2.矩形或方盒矩形和方盒不但是近似表示不规则空间对象的简单、有效手段，也是划分子空间的首选图形。,2023/4/3,50,3.栅格（grid）用栅格表示空间对象，类似于用点阵、像素阵列表示二维图像，原则上可以推广到高维空间，但主要用于二维空间,2023/4/3,51,2023/4/3,52,2023/4/3,53,每个区域都可以近似表示为二进制串的集合。这种二进制串的集合称为该区域的Z元素（Z-element）。要检查两个区域是否相交或包含，可以按序比较两个区域的Z元素。比较时，如果一个二进制串是另一个二进制串的前缀，则后者所代表的区域必然包含于前者所代表的区域中，例如100101一定包含在1001中。,2023/4/3,54,用Z次序的栅格表示区域，可以把本是二维的空间对象，用一维的有序二进制串序列表示。因此，空间对象所占的区域，可以用二进制串作为索引键，组成一个B树。下面是A，B区域的Z元素，经扫描比较，可以找出它们的重叠部分。,2023/4/3,55,重叠部分：（A1,B1）,（A1,B2）（A1,B3），（B1,A2），（B1,A3），。在上面的重叠栏中，二元组的第一项覆盖第二项。,2023/4/3,56,10.3.3 基于大小非零空间对象查询的R树,空间索引按照其操作对象的不同可以分为两类。以空间点为查询对象的索引 例如kd树和G-树技术（kd树和G树可以参考有关的空间数据库书籍）。以非点的空间图形为查询对象的索引，例如R-树等技术。下面，我们主要讨论基于测度非零的空间图形的R-树技术。,2023/4/3,57,R树主要以矩形（Rectangle）为检索对象，这就是R树命名的 由来。R树是由Guttmann于1984年提出。与B+树相似，G树是一种平衡多分树；与B+树不同，R树不是通过逐级比较索引键的值来搜索要找的对象。而是通过逐级缩小搜索的空间范围来定位要找的对象。搜索的空间范围在二维空间中就用MRB表示。,2023/4/3,58,如果一个MRB中含有其他的MRB，则称其为目录MRB，否则就称为对象MRB。在R树中，每个索引项都是一个二元组（r，p），其中r表示MBR，p表示相应指针。对于叶结点，p指向r所近似表示的空间对象；在非叶结点，p指向含有r的子节点。,2023/4/3,59,一个结点最多可有M个索引项，至少有m个索引项。M一般在2与M/2之间选择。由于R树在分裂时涉及到区域的优化与调整，开销较大，为了减少分裂概率，m宜选择较低数值。有实验结果，m在0.4M左右可以获得较好的性能。,2023/4/3,60,R树具有如下基本性质根结点至少有两个索引项，除非个结点是R树的唯一结点；每个非叶结点有m到M个索引项；在上述约束条件下，保持树的平衡。下图（a）表示了外包矩形的取法，（b）是其对应的R树的取法。,2023/4/3,61,2023/4/3,62,2023/4/3,63,2.R树的查询设给定矩形Rq=（x1，y1），（x2，y2），其中（x1，y1），（x2，y2）分别为Rq的左下角和右上角坐标，要查询其中所包含的空间对象。在查询时，首先从R树的根结点开始。,2023/4/3,64,如果根结点中的索引项是对象，由于这些索引项是无序的，需要逐个检查每个对象MBR是否包含在Rq中，如果包含在Rq中，则此对象就是选中的对象之一。设对象MBR为R0=（x3，y3），（x4，y4），式中（x3，y3），（x4，y4），分别为R0的左下角和右上角坐标。R0包含在Rq中的条件为x3x1 and y3y1 and x4x2 and y4y2,2023/4/3,65,如果根结点中的索引项是目录MBR，则逐个检查个目录MBR是否与Rq相交。如果相交，则此目录MBR中的对象MBR就有可能包含在Rq中，需要沿此目录MBR继续搜索；如果目录MBR与Rq不相交，则其中的对象MBR就不可能包含在Rq中，就不必沿此目录继续向下搜索，相交的条件参见前述小节。当搜索到叶结点时，则与前面一样，逐个检查其中对象MBR是否包含在中。如果目录MBR之间有重叠，虽然重叠区中的对象只属于一个目录MBR，但是判定它属于哪一个目录MBR，仍然需要多路搜索。,2023/4/3,66,3.R树的插入插入是R树中开销最大的操作，对其性能影响很大，因而研究较多。设（R1，p）是待插入的对象MBR及其指向对象的指针。与R+树不同，插入哪个叶结点以及在叶结点的次序不是唯一的。R1插入哪个叶结点决定于它属于哪个目录MBR，至于它在叶结点中的次序是无关紧要的，因为空间对象本来是无序的。R1可能与多个目录MBR相交或相邻，这些目录MBR只要其中的对象MBR不超过最大值，经过必要的扩大后，都可被选来覆盖R1。因此，R1的插入方式可能有多种选择，这就存在一个优化问题。,2023/4/3,67,R树采用较简单的优化准则，即选择插入后面积扩大最小的目录MBR去覆盖。若有两个或多个目录MBR都满足此要求，则选择其中面积最小的。目录MBR选定以后，就可确定其所在的叶结点。如果叶结点中有空，则可直接插入，插入完成。如果叶结点在插入后溢出，则需要分裂为二。,2023/4/3,68,由于叶结点中索引项是无序的，索引项分组的方式也有多种选择，这将在R树的改进方案中讨论。叶结点分裂后，需要生成两个目录MBR，覆盖分裂后的两组对象MBR，以取代原来目录MBR中的。这就意味着叶结点的上一级结点要增加一个索引项。这又可能导致该结点分裂，这种分裂可传播至根。根分裂后，树就要增加一级。,2023/4/3,69,4.R树的删除在删除某个对象MBR时，先按照其对象MBR，从根搜索到它所在的叶结点，从叶结点中删除之。在删除该对象之后，可能引起叶结点下溢（underflow），即其中的索引项的个数可能低于最小值。在此情况下，可将此叶结点及其对应的目录MBR删除，且将其中剩余的对象MBR及其指向对象MBR的指针重插入树中。,2023/4/3,70,这实际上相当于把删除了的叶结点中剩余的对象MBR，分摊到与其相交或相邻的其他目录中。目录对象MBR的删除也会引起其所在的非叶结点的下溢，从而导致该非叶结点的删除。其中剩余的目录MBR对象可以重插到其他同级的非叶结点中。这个过程有可能继续到根结点的删除。当然，根结点删除时，其中只有一个索引项，可以直接删除，无需重插入，即R树降低一级。,2023/4/3,71,在重插入的过程中也可能引起结点的溢出，例如除被删除的叶结点外，其他的叶结点又分裂。通过这个过程，不但可以消除叶结点的下溢，而且在一定程度上改变了叶结点中索引项分配不均匀的情况。这在效果上相当于对R树的一次合理重组。,2023/4/3,72,R树是最早提出的大小非零空间对象的索引结构。由于R树具有B+树的特点，适用于多维空间对象的检索。它一经提出，就受到广泛关注，在空间数据库系统中得到较广的应用。在文献中，也提出了不少R树的变种，目标主要集中在R树性能的改善上。,
