基于树结构的空间数据库通用建库技术研究

时间：2024-05-18

刘建东　戚利娜

摘要：针对基于数据字典的空间数据库通用建库技术存在时间复杂度较高的弊端，提出采用树结构的空间数据库通用建库技术，并分析对比两种技术的时间复杂度和空间复杂度。从对比结果来看，树结构的空间数据库通用建库技术在时间性能上更优，而空间效率略低。总体而言，树结构的空间数据库通用建库技术是优于基于数据字典的。

关键词：空间数据库;树结构;通用建库技术;数据字典

中图分类号：TP311.13

文献标识码：A

DOI：10.15913/j .cnki.kj ycx.2019.09.012

空间数据库是传统关系数据库与GIS技术相结合的产物，相比传统数据库而言，需要存储空间数据，因此，无论从存储空间还是从数据库之间的关系来说，空间数据库都比传统数据库更为复杂。当然，从实践效果来看，空间数据库比传统数据库更能满足实践的需求。例如，中药材资源数据库不仅需要保存中药材的名称、属性、作用，更重要的是保存每种药材的生长环境、地理位置，因为后者对于中药材的使用与利用更为关键，其余类似的包括矿产资源、农业资源等。由此可见，空间数据库的应用范围非常广泛。建立空间数据库是信息时代各行业资源得以有效利用的关键途径，虽然现在已经有较为成熟的建库技术，如Arc、Geodatabase等，但这些技术一方面依赖于不同的平台，此外，建库过程还与具体的领域有关，因此不具有通用性，不同行业空间数据库建库速度没有得到明显提高。鉴于已有技术问题，张龙提出了基于数据字典的空间数据库通用建库技术[1]，本文目的也是解决已有技术通用性不强的问題，主要在讨论张龙提出的建库技术基础上，提出基于树结构设计通用建库技术。

1 相关研究

有关空间数据库的研究，相关学者作出了较大贡献。文献[l]提出了利用数据字典设计通用建库技术;文献[2]借鉴关系型数据库设计方法与范式，探讨了空间数据库的设计原则与方法;文献[3]从实践角度出发描述了以GIS与Maplnfo等软件为媒介，将相关数据导人空间数据库的具体过程;不同领域的学者都在各自领域构建了空间数据库，不同领域学者分别在中药资源信息[4]、矿山[5]、扶贫开发[6]、非物质文化c7]等领域构建了空间数据库。从已有研究来看，空间数据库主要的问题在不同平台、不同领域构建不同的空间数据库，信息不具有共享性，技术不具备通用性。本文在文献[l]的基础进一步提出更高效率的通用建库技术。

2 基于数据字典的空间数据库通用建库技术的原理与弊端

本节的内容主要参考文献[l]的核心思路，目的是讨论该技术存在的弊端，为提出树结构的空间数据库通用建库技术做好准备。

文献[8]认为空间数据库的核心是由要素数据集、要素类、属性数据集、属性表、属性项、属性值域、栅格要素集、坐标参照系及它们之间的关系等多个对象组成。以此为前提，基于数据字典的空间数据库通用建库技术主要过程包括建立结构模型、建立数据字典、结构模型映射到数据字典、数据字典映射到物理模型。其中结构模型的建立主要是通过组织相关专家参考国家标准以及相关行业的标准，确定图、要素类等多个对象之间的关系。而结构模型映射到数据字典阶段则通过Excel建立图、元素类、字段、下属词四个字典，并通过Access导入。前文提到的4个字典的格式分别如表l-表4所示。由4个表的结构可以看出，一个图件包含多个要素类，它们之间通过表2的“所属图件”进行关联;一个要素类包含多个字段，它们之间通过表3的“所属要素类”关联;每个字段有特定的属性值，它们之间则通过表3的“下属词编码”关联。最后一个阶段是数据字典到物理模型的映射。由于4个数据字典相互之间存在关系，因此可通过创建要素类一创建要素类包含的字段一创建字段对应的下属词一创建包含要素类的图件完成映射过程。

数据字典到物理模型的映射过程过程如图1所示[1]，主要采用空间数据库的接口进行二次开发完成。

基于数据字典的空间数据库通用建库技术的弊端有两点：①要素类不仅仅属于一个图件，即要素类字典与图件字典是多对多的关系，按照数据库设计理论，如果一个要素类属于多个图件，那么表2中所属图件存在重复或者冗余，增加后续数据字典到物理模型的映射阶段的时间负担，这点后续会详细说明;②从数据字典到物理模型的映射过程看出，需要创建要素类、字段、下属词、图件。假设一个要素类平均包含Ⅳ个字段，有M个要素类，则总计有NxM个字段，每次由于要素类与字段具有对应关系，因此每个要素类对应的字段都要从Ⅳ×M个字段中查询，其时间效率较低。图件与要素也具有同样的问题，加上前文提到的重复与冗余，会进一步降低效率。基于上述弊端的考虑，本文提出基于树结构的空间数据库通用建库技术。

3 基于树结构的空间数据库通用建库技术的提出

基于树结构的空间数据库通用建库技术过程与上一节技术提到的过程类似，主要变化的是不再采用数据字典，而是采用树型结构。具体的结构如图2所示。

采用树结构后，树结构到物理模型的映射过程可直接按树的深度遍历算法从根节点开始进行遍历，如图2中虚线路径即为其中一次遍历过程。按照数据结构理论，树的深度遍历算法的时间复杂度为O（n）。

4 两种建库技术的复杂度对比

基于数据字典的空间数据库通用建库技术采用数据字典存储通用的结构，通过主关键字关联图件字典、要素类字典、字段字典、下属词字典。因此，同一个字典实例可通过关键字做多次应用。例如某个字段通过所属要素类编号可关联多个要素，类似同一个要素类通过“所属图件编号”可关联多个图件。要素类存储实例如表5所示。

由表5可看出，最坏情况下，要素类字典需要重复存储多个实例，其空间复杂度为O（n）。

对于时间复杂度，具体分析过程如下。

由图1可知，要素类关联多个字段，每个字段关联下属词，每个图件关联多个要素类。上述字典之间的关系需要对应，对应的过程需要遍历字典列表。假设所有的字典实例数为n/4，数据字典映射到物理模型的过程需要循环遍历每个字典，因此其时间复杂度为D（ n4）。

而基于树结构的空间数据库通用建库技术由于采用树型结构，在存储上适合一对多的关系，但是图件与要素类，要素类与字段之间是多对多的关系，因此树形结构存储要重复多次，具体是0（ n2）。

对于时间复杂度而言，树结构到物理模型的映射通过树的深度遍历算法即可实现，时间复杂度为O（n）。

综上，两种建库技术的空间复杂度、时间复杂度对比如表6所示。

由表6的對比可知，相比基于数据字典的建库技术，虽然基于树结构的建库技术的空间复杂度更高一个量级，但是在时间复杂上远远降低了多个量级。总体而言，后者更优。