基于樹(shù)結(jié)構(gòu)的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)研究

劉建東　戚利娜

摘要：針對(duì)基于數(shù)據(jù)字典的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)存在時(shí)間復(fù)雜度較高的弊端，提出采用樹(shù)結(jié)構(gòu)的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)，并分析對(duì)比兩種技術(shù)的時(shí)間復(fù)雜度和空間復(fù)雜度。從對(duì)比結(jié)果來(lái)看，樹(shù)結(jié)構(gòu)的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)在時(shí)間性能上更優(yōu)，而空間效率略低。總體而言，樹(shù)結(jié)構(gòu)的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)是優(yōu)于基于數(shù)據(jù)字典的。

關(guān)鍵詞：空間數(shù)據(jù)庫(kù);樹(shù)結(jié)構(gòu);通用建庫(kù)技術(shù);數(shù)據(jù)字典

中圖分類號(hào)：TP311.13

文獻(xiàn)標(biāo)識(shí)碼：A

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

空間數(shù)據(jù)庫(kù)是傳統(tǒng)關(guān)系數(shù)據(jù)庫(kù)與GIS技術(shù)相結(jié)合的產(chǎn)物，相比傳統(tǒng)數(shù)據(jù)庫(kù)而言，需要存儲(chǔ)空間數(shù)據(jù)，因此，無(wú)論從存儲(chǔ)空間還是從數(shù)據(jù)庫(kù)之間的關(guān)系來(lái)說(shuō)，空間數(shù)據(jù)庫(kù)都比傳統(tǒng)數(shù)據(jù)庫(kù)更為復(fù)雜。當(dāng)然，從實(shí)踐效果來(lái)看，空間數(shù)據(jù)庫(kù)比傳統(tǒng)數(shù)據(jù)庫(kù)更能滿足實(shí)踐的需求。例如，中藥材資源數(shù)據(jù)庫(kù)不僅需要保存中藥材的名稱、屬性、作用，更重要的是保存每種藥材的生長(zhǎng)環(huán)境、地理位置，因?yàn)楹笳邔?duì)于中藥材的使用與利用更為關(guān)鍵，其余類似的包括礦產(chǎn)資源、農(nóng)業(yè)資源等。由此可見(jiàn)，空間數(shù)據(jù)庫(kù)的應(yīng)用范圍非常廣泛。建立空間數(shù)據(jù)庫(kù)是信息時(shí)代各行業(yè)資源得以有效利用的關(guān)鍵途徑，雖然現(xiàn)在已經(jīng)有較為成熟的建庫(kù)技術(shù)，如Arc、Geodatabase等，但這些技術(shù)一方面依賴于不同的平臺(tái)，此外，建庫(kù)過(guò)程還與具體的領(lǐng)域有關(guān)，因此不具有通用性，不同行業(yè)空間數(shù)據(jù)庫(kù)建庫(kù)速度沒(méi)有得到明顯提高。鑒于已有技術(shù)問(wèn)題，張龍?zhí)岢隽嘶跀?shù)據(jù)字典的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)[1]，本文目的也是解決已有技術(shù)通用性不強(qiáng)的問(wèn)題，主要在討論張龍?zhí)岢龅慕◣?kù)技術(shù)基礎(chǔ)上，提出基于樹(shù)結(jié)構(gòu)設(shè)計(jì)通用建庫(kù)技術(shù)。

1 相關(guān)研究

有關(guān)空間數(shù)據(jù)庫(kù)的研究，相關(guān)學(xué)者作出了較大貢獻(xiàn)。文獻(xiàn)[l]提出了利用數(shù)據(jù)字典設(shè)計(jì)通用建庫(kù)技術(shù);文獻(xiàn)[2]借鑒關(guān)系型數(shù)據(jù)庫(kù)設(shè)計(jì)方法與范式，探討了空間數(shù)據(jù)庫(kù)的設(shè)計(jì)原則與方法;文獻(xiàn)[3]從實(shí)踐角度出發(fā)描述了以GIS與Maplnfo等軟件為媒介，將相關(guān)數(shù)據(jù)導(dǎo)人空間數(shù)據(jù)庫(kù)的具體過(guò)程;不同領(lǐng)域的學(xué)者都在各自領(lǐng)域構(gòu)建了空間數(shù)據(jù)庫(kù)，不同領(lǐng)域?qū)W者分別在中藥資源信息[4]、礦山[5]、扶貧開(kāi)發(fā)[6]、非物質(zhì)文化c7]等領(lǐng)域構(gòu)建了空間數(shù)據(jù)庫(kù)。從已有研究來(lái)看，空間數(shù)據(jù)庫(kù)主要的問(wèn)題在不同平臺(tái)、不同領(lǐng)域構(gòu)建不同的空間數(shù)據(jù)庫(kù)，信息不具有共享性，技術(shù)不具備通用性。本文在文獻(xiàn)[l]的基礎(chǔ)進(jìn)一步提出更高效率的通用建庫(kù)技術(shù)。

2 基于數(shù)據(jù)字典的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)的原理與弊端

本節(jié)的內(nèi)容主要參考文獻(xiàn)[l]的核心思路，目的是討論該技術(shù)存在的弊端，為提出樹(shù)結(jié)構(gòu)的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)做好準(zhǔn)備。

文獻(xiàn)[8]認(rèn)為空間數(shù)據(jù)庫(kù)的核心是由要素?cái)?shù)據(jù)集、要素類、屬性數(shù)據(jù)集、屬性表、屬性項(xiàng)、屬性值域、柵格要素集、坐標(biāo)參照系及它們之間的關(guān)系等多個(gè)對(duì)象組成。以此為前提，基于數(shù)據(jù)字典的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)主要過(guò)程包括建立結(jié)構(gòu)模型、建立數(shù)據(jù)字典、結(jié)構(gòu)模型映射到數(shù)據(jù)字典、數(shù)據(jù)字典映射到物理模型。其中結(jié)構(gòu)模型的建立主要是通過(guò)組織相關(guān)專家參考國(guó)家標(biāo)準(zhǔn)以及相關(guān)行業(yè)的標(biāo)準(zhǔn)，確定圖、要素類等多個(gè)對(duì)象之間的關(guān)系。而結(jié)構(gòu)模型映射到數(shù)據(jù)字典階段則通過(guò)Excel建立圖、元素類、字段、下屬詞四個(gè)字典，并通過(guò)Access導(dǎo)入。前文提到的4個(gè)字典的格式分別如表l-表4所示。由4個(gè)表的結(jié)構(gòu)可以看出，一個(gè)圖件包含多個(gè)要素類，它們之間通過(guò)表2的“所屬圖件”進(jìn)行關(guān)聯(lián);一個(gè)要素類包含多個(gè)字段，它們之間通過(guò)表3的“所屬要素類”關(guān)聯(lián);每個(gè)字段有特定的屬性值，它們之間則通過(guò)表3的“下屬詞編碼”關(guān)聯(lián)。最后一個(gè)階段是數(shù)據(jù)字典到物理模型的映射。由于4個(gè)數(shù)據(jù)字典相互之間存在關(guān)系，因此可通過(guò)創(chuàng)建要素類一創(chuàng)建要素類包含的字段一創(chuàng)建字段對(duì)應(yīng)的下屬詞一創(chuàng)建包含要素類的圖件完成映射過(guò)程。

數(shù)據(jù)字典到物理模型的映射過(guò)程過(guò)程如圖1所示[1]，主要采用空間數(shù)據(jù)庫(kù)的接口進(jìn)行二次開(kāi)發(fā)完成。

基于數(shù)據(jù)字典的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)的弊端有兩點(diǎn)：①要素類不僅僅屬于一個(gè)圖件，即要素類字典與圖件字典是多對(duì)多的關(guān)系，按照數(shù)據(jù)庫(kù)設(shè)計(jì)理論，如果一個(gè)要素類屬于多個(gè)圖件，那么表2中所屬圖件存在重復(fù)或者冗余，增加后續(xù)數(shù)據(jù)字典到物理模型的映射階段的時(shí)間負(fù)擔(dān)，這點(diǎn)后續(xù)會(huì)詳細(xì)說(shuō)明;②從數(shù)據(jù)字典到物理模型的映射過(guò)程看出，需要?jiǎng)?chuàng)建要素類、字段、下屬詞、圖件。假設(shè)一個(gè)要素類平均包含Ⅳ個(gè)字段，有M個(gè)要素類，則總計(jì)有NxM個(gè)字段，每次由于要素類與字段具有對(duì)應(yīng)關(guān)系，因此每個(gè)要素類對(duì)應(yīng)的字段都要從Ⅳ×M個(gè)字段中查詢，其時(shí)間效率較低。圖件與要素也具有同樣的問(wèn)題，加上前文提到的重復(fù)與冗余，會(huì)進(jìn)一步降低效率。基于上述弊端的考慮，本文提出基于樹(shù)結(jié)構(gòu)的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)。

3 基于樹(shù)結(jié)構(gòu)的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)的提出

基于樹(shù)結(jié)構(gòu)的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)過(guò)程與上一節(jié)技術(shù)提到的過(guò)程類似，主要變化的是不再采用數(shù)據(jù)字典，而是采用樹(shù)型結(jié)構(gòu)。具體的結(jié)構(gòu)如圖2所示。

采用樹(shù)結(jié)構(gòu)后，樹(shù)結(jié)構(gòu)到物理模型的映射過(guò)程可直接按樹(shù)的深度遍歷算法從根節(jié)點(diǎn)開(kāi)始進(jìn)行遍歷，如圖2中虛線路徑即為其中一次遍歷過(guò)程。按照數(shù)據(jù)結(jié)構(gòu)理論，樹(shù)的深度遍歷算法的時(shí)間復(fù)雜度為O（n）。

4 兩種建庫(kù)技術(shù)的復(fù)雜度對(duì)比

基于數(shù)據(jù)字典的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)采用數(shù)據(jù)字典存儲(chǔ)通用的結(jié)構(gòu)，通過(guò)主關(guān)鍵字關(guān)聯(lián)圖件字典、要素類字典、字段字典、下屬詞字典。因此，同一個(gè)字典實(shí)例可通過(guò)關(guān)鍵字做多次應(yīng)用。例如某個(gè)字段通過(guò)所屬要素類編號(hào)可關(guān)聯(lián)多個(gè)要素，類似同一個(gè)要素類通過(guò)“所屬圖件編號(hào)”可關(guān)聯(lián)多個(gè)圖件。要素類存儲(chǔ)實(shí)例如表5所示。

由表5可看出，最壞情況下，要素類字典需要重復(fù)存儲(chǔ)多個(gè)實(shí)例，其空間復(fù)雜度為O（n）。

對(duì)于時(shí)間復(fù)雜度，具體分析過(guò)程如下。

由圖1可知，要素類關(guān)聯(lián)多個(gè)字段，每個(gè)字段關(guān)聯(lián)下屬詞，每個(gè)圖件關(guān)聯(lián)多個(gè)要素類。上述字典之間的關(guān)系需要對(duì)應(yīng)，對(duì)應(yīng)的過(guò)程需要遍歷字典列表。假設(shè)所有的字典實(shí)例數(shù)為n/4，數(shù)據(jù)字典映射到物理模型的過(guò)程需要循環(huán)遍歷每個(gè)字典，因此其時(shí)間復(fù)雜度為D（ n4）。

而基于樹(shù)結(jié)構(gòu)的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)由于采用樹(shù)型結(jié)構(gòu)，在存儲(chǔ)上適合一對(duì)多的關(guān)系，但是圖件與要素類，要素類與字段之間是多對(duì)多的關(guān)系，因此樹(shù)形結(jié)構(gòu)存儲(chǔ)要重復(fù)多次，具體是0（ n2）。

對(duì)于時(shí)間復(fù)雜度而言，樹(shù)結(jié)構(gòu)到物理模型的映射通過(guò)樹(shù)的深度遍歷算法即可實(shí)現(xiàn)，時(shí)間復(fù)雜度為O（n）。

綜上，兩種建庫(kù)技術(shù)的空間復(fù)雜度、時(shí)間復(fù)雜度對(duì)比如表6所示。

由表6的對(duì)比可知，相比基于數(shù)據(jù)字典的建庫(kù)技術(shù)，雖然基于樹(shù)結(jié)構(gòu)的建庫(kù)技術(shù)的空間復(fù)雜度更高一個(gè)量級(jí)，但是在時(shí)間復(fù)雜上遠(yuǎn)遠(yuǎn)降低了多個(gè)量級(jí)。總體而言，后者更優(yōu)。

5 結(jié)論

本文詳細(xì)討論基于數(shù)據(jù)字典的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)的建庫(kù)過(guò)程及其弊端，在此基礎(chǔ)上提出了基于樹(shù)結(jié)構(gòu)的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)，并對(duì)比了兩種建庫(kù)技術(shù)的復(fù)雜度。從空間復(fù)雜度來(lái)說(shuō)，前者更優(yōu);從時(shí)間復(fù)雜度來(lái)說(shuō)，后者更優(yōu)。總體而言，基于樹(shù)結(jié)構(gòu)的空間通用建庫(kù)技術(shù)更好。

參考文獻(xiàn)：

[l]張龍，汪新慶.基于數(shù)據(jù)字典的空間數(shù)據(jù)庫(kù)通用建庫(kù)技術(shù)[J].國(guó)土資源遙感，2014，26（1）：173-178.

[2]羅智勇，劉湘南.基于Geodatabase模型的空間數(shù)據(jù)庫(kù)設(shè)計(jì)方法[J].地球信息科學(xué)，2004（ 4）： 105-109.

[3]崔陽(yáng)，王華，喬淑娟.基于GIS的空間數(shù)據(jù)庫(kù)構(gòu)建與應(yīng)用研究[J].微計(jì)算機(jī)信息，2006（ 6）： 199-201.

[4]趙玉洋，孫成忠，楊澤東.中藥資源信息空間數(shù)據(jù)庫(kù)構(gòu)建[J].中國(guó)中藥雜志，2015，40（ 6）： 1219-1222.

[5]王莉，杜久升，景海濤.智慧礦山空間數(shù)據(jù)庫(kù)建設(shè)研究[J].工礦自動(dòng)化，2014，40（ 12）：25-30.

[6]劉一明，胡卓瑋，趙文吉，等.基于Geodatabase模型的扶貧開(kāi)發(fā)空間數(shù)據(jù)庫(kù)的設(shè)計(jì)與實(shí)現(xiàn)[J].工程勘察，2014，42（7）：44-49，63.

[7]李仁杰，傅學(xué)慶，張軍海.非物質(zhì)文化空間數(shù)據(jù)庫(kù)與地圖表達(dá)方法——基于蔚縣剪紙的實(shí)證研究[J].人文地理，2014，29（1）：20-25.

[8]徐翠玲.基于Geodatabase建立數(shù)字地質(zhì)圖數(shù)據(jù)庫(kù)的方法與實(shí)踐[J]測(cè)繪科學(xué)，2008（3）：176-177，186.