空间网络数据库(数据库)

时间：2022-10-31 16:30:01 | 来源：信息时代

时间：2022-10-31 16:30:01 来源：信息时代

    空间网络数据库 : 能够支持基于连通性的空间实体的高效存储和查询的一类空间数据库。应用于运输规划、空中交通管制、管网设施、电话网络、河道运输、灌渠管理等领域。在空间网络数据库中,起根本作用的是基于连通性的关系。
1. 空间网络数据的图操作
空间网络数据通常被建模为图,其结点是嵌在空间上的点。路径估算和最短路径计算操作的高效实现通常是基于结点之间的连通性,而不是欧几里得距离。图可以用关系数据库中的结点表和边表来表示。邻接矩阵(adjacency-matrix)和邻接表(adjacency-list)可以用于图的实现。
在邻接矩阵中,行和列表示图的顶点,矩阵中元素的取值为1或0,即对应的两个顶点之间有边则为1,否则为0。如果是无向图,那么矩阵是对称的。邻接矩阵结构对于回答边的查询是很有效的,例如,边(u,v)是否在图G中。
邻接表是一个指针数组,数组的每个元素对应图中的一个顶点,而指针则指向该顶点的一个直接后继顶点表。邻接表结构对于涉及枚举图的顶点查询是高效的,例如,找出v的所有邻近顶点。
基于关系代数的查询语言(如SQL)对许多图操作(如最短路径问题)无能为力,因为这些图操作要用到传递闭包操作。传递闭包的处理可以采用广度优先搜索或者深度优先搜索策略,而计算部分的传递闭包更多的是用Dijkstra算法。最短路径计算还有特别的策略(A*算法,层次算法)。
2. 空间网络查询
空间网络上常用的查询可以分为三类: 单遍扫描查询、连接查询和网络分析查询。单遍扫描查询包括点和范围查询,例如,点查询、边查询、前驱查询、后继查询以及路径估算操作。连接查询是多个空间网络的图形叠加。网络分析查询是一组基于传递闭包的查询,它们包括最短路径、连接性确定、最短旅行路线、定位和布局等。其中最短路径问题和图遍历问题的算法,用于处理大多数网络分析查询,同样也用于处理单遍扫描查询和连接查询。
路径查询处理是空间网络应用中的一个重要部分,本质上可以归结为提供基于相关应用准则的路径选择。最基本的路径查询是确定网络中两个点A和B之间的最短路径,“最短”可以是距离、旅行时间或者其他用户指定的约束。
路径计算可以分为三类:
(1)单对:给定一个图G=(V,E)和N中的顶点u与v,找出u与v之间的最优路径。
(2)单源: 给定一个源结点u,找出G中从u到所有可达(reachable)结点的最优路径。这也是所谓的部分传递闭包(partial transitive closure)问题。
(3)所有对: 在G中找出N的所有结点对u和v之间的最优路径。这是有关传递闭包的问题。
对于空间网络,只有点和范围查询的I/O度量方法是不够的,因为网络中的关系是基于连接性而不是基于邻近性的。就网络操作的I/O代价而言,一种简单并且直观的度量方法与非分离边的数目有关。如果一条边的两个端点位于同一个磁盘页中,那么它是非分离的,否则就是分离的。
连接性剩余率(connectivity residue ratio,CRR):CRR=非分离边总数/总边数。连接性剩余率是一种数据结构无关的度量,其最大化的存储和访问方法可以提高图操作的I/O效率。已经有专用的连接性聚簇的空间网络存取方法,它采用最小分割的图分区算法来聚集结点记录,以使连接性剩余率最大化。此外,还可以采用辅助的二级索引来支持点查询、边查询、前驱查询和后继查询操作。选择二级索引可以针对应用作调整,有些采用了带Z序的B⁺-树。为了适于应用,还可以创建其他存取方法(如R-树和grid文件)作为二级索引。