面向SPARQL查詢的地理語義空間索引構(gòu)建方法

段紅偉，孟令奎，黃長青，李 穎，李繼園

1.武漢大學(xué) 遙感信息工程學(xué)院，湖北 武漢430079；2.河南省氣象科學(xué)研究院，河南 鄭州450003

1 引 言

語義Web技術(shù)的發(fā)展推動了地理數(shù)據(jù)的語義化表達。隨著各種地理數(shù)據(jù)語義化項目，如GeoName［1］、OpenStreetMap［2］、Linked GeoData［3］等項目的不斷開展，地理語義數(shù)據(jù)愈加豐富和龐大，如何構(gòu)建適合的地理語義空間索引來快速有效地進行地理語義空間查詢變得愈加重要。

同傳統(tǒng)的地理數(shù)據(jù)相比，地理語義數(shù)據(jù)采用RDF（resource description framework）［4］定義數(shù)據(jù)模型，采 用 SPARQL［5］語 言（simple protocol and RDF query language）進行數(shù)據(jù)查詢，這種數(shù)據(jù)和查詢語言的特點要求地理語義數(shù)據(jù)采用RDF的三元組｛主語，謂詞，賓語｝對數(shù)據(jù)進行描述，地理語義空間查詢必須在三元組空間上進行空間關(guān)系和空間分析運算，并基于SPARQL查詢返回主語、謂詞或賓語這樣的RDF節(jié)點［6］，從而使得傳統(tǒng)的空間索引技術(shù)和RDF數(shù)據(jù)組織方法不能直接用于地理語義空間索引的構(gòu)建。

在傳統(tǒng)的空間索引技術(shù)方面，雖然傳統(tǒng)的空間索引技術(shù)已經(jīng)在二維［7］、三維［8］和二維三維混合幾何對象［9］上得到廣泛應(yīng)用，但是由于空間索引沒有對應(yīng)的地理語義數(shù)據(jù)到幾何對象的映射和鏈接模型，使得傳統(tǒng)的空間索引技術(shù)在地理語義空間索引。而在RDF數(shù)據(jù)組織方法方面，現(xiàn)有的方法如屬性表法（property table）［10］、垂直分割法（vertical partitioning）［11］、多索引結(jié)構(gòu)法（multipleindexing）［12］、六倍索引法（hexastore）［13］等方法，通過建立三元組要素主語、謂詞和賓語間的二元鏈接來實現(xiàn)對數(shù)據(jù)快速查詢。但是這些方法沒有定義空間數(shù)據(jù)類型，缺乏對空間信息的識別、組織和映射，因此并不適用于地理語義空間查詢。

針對上述問題，本文基于地理語義查詢在方法論［14］、本體詞表結(jié)構(gòu)［15］及實現(xiàn)框架［16］上的研究，將傳統(tǒng)空間索引技術(shù)和RDF數(shù)據(jù)組織方法進行結(jié)合，通過構(gòu)建合適的地理語義空間索引，實現(xiàn)高效的面向SPARQL的地理語義空間查詢，從而提供一種輕量級的地理語義空間查詢方案。

2 地理空間四元組模型

構(gòu)建地理語義空間索引需解決三個問題：①快速獲取地理語義數(shù)據(jù)獲得包含空間信息的RDF節(jié)點—空間RDF節(jié)點；②對空間RDF節(jié)點進行包裝和轉(zhuǎn)換來建立空間幾何對象，并利用空間索引對空間幾何對象進行索引；③在SPARQL語言層次上使用空間索引進行空間查詢，并正確返回RDF節(jié)點數(shù)據(jù)。

為了明確地理語義空間索引構(gòu)建中的對象及其關(guān)系，為地理語義空間索引的構(gòu)建提供抽象的模型和方法指導(dǎo)，本文基于地理語義數(shù)據(jù)的特點構(gòu)建了地理語義空間數(shù)據(jù)模型—地理空間四元組模型（簡稱GeoQuad），其模型結(jié)構(gòu)如圖1所示。可以看出，GeoQuad通過增加一個表示空間特征的空間類型戳來擴展RDF三元組結(jié)構(gòu)，從而提供地理語義數(shù)據(jù)的空間信息。

圖1 GeoQuad的模型結(jié)構(gòu)圖Fig.1 The structure of GeoQuad

基于RDF和空間數(shù)據(jù)定義，本文對GeoQuad中的對象作如下定義。

定義1（RDF三元組，RDF 節(jié)點）：給定URIref集合R、空節(jié)點集合B和文字類型節(jié)點L，如果一個三元組α∈（R∪B）×R×（R∪B∪L），則稱α為一個RDF三元組（RDF Triple），而α的元素β∈（主語（Subject）∨謂詞（Predicate）∨賓語（Object））稱為RDF節(jié)點（RDF Node）。

定義2（空間三元組）：給定一個RDF三元組λ∈α，如果λ的賓語包含空間坐標信息，則稱λ為一個空間三元組（Geo RDF Triple）。λ的主語稱為地物節(jié)點（FeatureSub），謂詞稱為空間謂詞（SpatialPredicate），賓語稱為空間節(jié)點（GeoObj）。

定義3（空間類型戳）：一個空間類型戳（Geo－Type）由值空間（Value Space）、詞法空間（Lexical space）和詞—值（Lexical－to－Value）映射三部分組成。其中值空間是一組OGC定義的空間對象［17］（GeoElem）集合，可由詞法空間解析生成；詞法空間是一個包含空間節(jié)點的集合，由Unicode字符串表示；詞－值映射將詞法空間的空間節(jié)點映射為值空間的空間對象。

定義4（GeoQuad實例）：給定空間三元組λ，空間類型戳κ，GeoQuad實例為組合（λ，κ）。

根據(jù)GeoQuad模型，本文第3部分構(gòu)建地理語義空間索引結(jié)構(gòu)來對數(shù)據(jù)進行組織和索引，在第4部分探討空間類型戳中空間節(jié)點到空間對象的封裝與轉(zhuǎn)換；在第5部分探討SPARQL語言上的空間查詢實現(xiàn)，從而對地理語義空間索引的三個問題進行解決。

3 地理語義空間索引結(jié)構(gòu)

3.1 地理語義空間查詢模式

地理語義空間索引（GeoQuadIndex）同地理語義查詢模式緊密相關(guān)。地理語義空間查詢遵循三元組的圖匹配（Grapth Mactching）模式，即將查詢變量映射為三元組的主語、謂詞或賓語，然后以三元組的形式在數(shù)據(jù)中進行查找和匹配，其形式主要有：

（1）（Constant｜Bindvariable，SpatialPredicate，？），主語為常量或綁定變量，空間謂詞給定，賓語為變量，通過三元組匹配和空間關(guān)系運算，得到滿足條件的賓語。

（2）（Constant｜Bindvariable，SpatialPredicate，Constant｜Bindvariable），主語和賓語為常量或綁定變量，空間謂詞給定，通過空間關(guān)系運算，查詢主語和賓語上的空間RDF Node是否在SpatialPredicate的關(guān)系上成立。

（3）（？，SpatialPredicate，Constant｜Bindvar iable），主語為變量，空間謂詞給定，賓語為常量或綁定變量，通過三元組匹配和空間關(guān)系運算，得到滿足條件的主語。

可以看出，地理語義空間查詢必須給定空間謂詞，這種查詢特點可以結(jié)合六倍索引方法中的POS結(jié)構(gòu)和垂直分割方法中的P（OS）結(jié)構(gòu)來構(gòu)建地理語義空間索引機構(gòu)。

3.2 地理語義空間索引結(jié)構(gòu)定義

地理語義空間索引結(jié)構(gòu)如圖2所示，分為地理RDF索引部分和映射結(jié)構(gòu)2個部分。

圖2 地理語義空間索引結(jié)構(gòu)Fig.2 The structure of geo semantic spatial index

3.2.1 地理RDF索引部分

本部分包括POS和P（OS）兩部分。POS即Predicate－Object－Subject，采用三級索引結(jié)構(gòu)，這種方法適用于（？，SpatialPredicate，Constant）查詢，即謂語和賓語已知，查找未知主語的情況。P（OS）采用二級索引結(jié)構(gòu)，其優(yōu)勢在于當(dāng)主語和賓語未知時，不需像POS那樣遍歷O列表和S列表，該索引結(jié)構(gòu)適用于（？｜Bindvariable，SpatialPredicate，Bindvariable）或（Bindvariable，SpatialPredicate，？｜Bindvariable）查詢，即謂語已知，查詢主語和賓語。

3.2.2 映射結(jié)構(gòu)部分

本部分建立了空間節(jié)點到空間對象的映射、空間對象到GID（空間對象ID號）的映射，并建立空間索引結(jié)構(gòu)，是空間類型戳的直接體現(xiàn)。其中空間索引部分基于JTS組件［18］，可以調(diào)用JTS中的空間索引，也可以構(gòu)建新的空間索引。

算法1為GeoQuadIndex的構(gòu)建算法，主要包括4個步驟：

（1）對地理語義數(shù)據(jù)解析，獲得包含空間信息的三元組Geotriples，將Geotriples中的賓語GeoObj轉(zhuǎn)換為空間幾何對象GeoElem，并建立雙映射表 Map（GeoObj，GeoElem）和 Map1（GeoElem，GID）（第1—10行）。

（2）對Geotriples建立POS三級索引和P（OS）二級索引（第11—12行）。

（3）利用 Map1（GeoElem，GID）建立空間索引SpatialIndex（第13行）。

（4）利用上述建立的數(shù)據(jù)結(jié)構(gòu)（POS，P（OS），SpatialIndex，Map，Map1）構(gòu) 建 Geo－QuadIndex，并返回該數(shù)據(jù)結(jié)構(gòu)（第14行）。

4 空間節(jié)點到空間對象的封裝與轉(zhuǎn)換

空間節(jié)點在地理語義數(shù)據(jù)中表現(xiàn)為類型文字（type Literal），并按照某數(shù)據(jù)規(guī)范進行描述，如GeoSPARQL規(guī)范［19］利用 WKT Literal和GML Literal來描述空間信息?；谕ㄓ眯?，本文對GeoSPARQL規(guī)范中WKT和GML描述的空間節(jié)點轉(zhuǎn)換為空間對象。

WKT規(guī)范簡單，WKT描述的空間節(jié)點到空間對象的轉(zhuǎn)換采用JTS提供的解析包進行了轉(zhuǎn)換。GML規(guī)范復(fù)雜，GML描述的空間節(jié)點到空間對象的轉(zhuǎn)換需要利用JAXB（Java xml bindings）技術(shù)，其轉(zhuǎn)換過程如圖3所示。

圖3 GML描述的空間節(jié)點到空間對象的轉(zhuǎn)換圖Fig.3 The transform of GeoObj to GeoElm

如圖3所示，GML描述的空間節(jié)點到空間對象的轉(zhuǎn)換過程為：首先利用JAXB，將GML Schema中各種元素生成Java類集合；然后對這些Java類進行擴展和重寫，利用JTS加入幾何特性從而支持OGC定義的幾何要素；最后利用Unmashal編出一個Java實例對象，該實例對象即為轉(zhuǎn)換后的空間對象。

5 SPARQL空間查詢實現(xiàn)

本文基于Jena Graph擴展機制來實現(xiàn)Geo－QuadIndex的SPARQL空間查詢。Jena是一種基于Java的語義Web框架，采用Graph層、Enh－Graph層和 Model（Ontology）層的三層體系結(jié)構(gòu)。Graph層位于底層，定義了非RDF Triple類型的數(shù)據(jù)處理機制。

圖4為基于Jena Graph擴展機制實現(xiàn)地理語義空間查詢的類結(jié)構(gòu)圖，包括空間索引類Geo－QuadIndex、Graph擴展類SpatialGraph、空間運算類SpatialOp和SPARQL查詢語法處理類（NormalPropertyFunctionEval及其子類）。

GeoQuadIndex類創(chuàng)建數(shù)據(jù)索引，并將空間節(jié)點同空間對象進行轉(zhuǎn)化和映射。GeoQuadIndex類包裝了JTS的Geometry對象（＿geo）和SpatialIndex索引對象（＿spatialIndex）；SpatialGraph類管理地理語義數(shù)據(jù)和數(shù)據(jù)索引，其中通過一個Graph對象（＿innerGraph）來管理地理語義數(shù)據(jù)，通過 GeoQuadIndex對象（＿index）來管理數(shù)據(jù)索引；SpatialOp類定義了支持空間查詢的各種算法，利用GeoQuadIndex類中的空間索引實現(xiàn)空間關(guān)系的快速運算；QueryParser類用于對查詢語句進行解析，從而明確地理語義數(shù)據(jù)采用P（OS）還是POS結(jié)構(gòu)，并最終得到一個SpatialGraph對象；Normal－PropertyFunctionEval及其子類定義了SPARQL查詢的空間操作算子。

圖4 SPARQL空間查詢實現(xiàn)Fig.4 The implement of SPARQL spatial query

6 試驗和分析

6.1 試驗環(huán)境和數(shù)據(jù)

本文試驗所采用的軟件包基于Jena［20］、ARQ［21］和JTS提供的API，并在Eclipse環(huán)境下利用Java語言編碼實現(xiàn)，所提索引方法（Geo－QuadIndex）的空間索引采用四叉樹索引。試驗平臺為一臺Win7系統(tǒng)的筆記本電腦，2.3GHz主頻的Intel Core i5處理器，4G內(nèi)存。試驗數(shù)據(jù)來自GeoName，并通過對原始數(shù)據(jù)進行編輯、合并獲得。試驗數(shù)據(jù)基于RDF XML語法，數(shù)據(jù)實例的空間信息可以同GeoSPARQL規(guī)范的WKT Literal數(shù)據(jù)類型兼容。表1所示為本文使用的8個測試數(shù)據(jù)集。

表1 試驗使用的地理語義數(shù)據(jù)集Tab.1 Geo semantic data sets for experiment

6.2 查詢測試方案

本文試驗包含Q1—Q5這5個地理語義查詢測試方案，查詢語句如表2所示。根據(jù)查詢特點可以將Q1—Q5分為兩個部分。

（1）測試對空間節(jié)點的獲取效率（Q1），該測試通過地物節(jié)點來查詢對應(yīng)的空間節(jié)點。

（2）測試語義空間查詢效率（Q2—Q5），考慮到空間關(guān)系在拓撲定義中通常是互逆或者包容的，本文選擇2個典型的空間查詢作為空間查詢測試方案，即 Within空間查詢（Q2—Q3）、Intersects空間查詢（Q4—Q5），其中Q2和Q4是純空間查詢，Q3和Q5是復(fù)合空間查詢。

表2 試驗查詢樣例Tab.2 Query samples in experiment

6.3 試驗結(jié)果與分析

6.3.1 Q1查詢

由于六倍索引法的高效性和代表性，本文在Q1查詢中將本文方法（GeoQuadIndex）、六倍索引法（Hexastore）以及無索引方法（No＿Index）進行對比，進而分析GeoQuad－Index的查詢效率。

Q1查詢的試驗結(jié)果如圖5所示，其中圖5（a）是 No＿Index、GeoQuadIndex、Hexastore的對比情況，圖5（b）是 GeoQuadIndex 和Hexasore的比較。

圖5（a）表明，無論是 GeoQuadIndex，還是Hexasore，其對空間節(jié)點的查詢效率均遠高于No＿Index。這 是 由 于 GeoQuadIndex 和Hexasore均對三元組的謂語、主語和賓語建立了HashMap映射表，從而不需要對3個部分進行遍歷，從而提高了圖匹配效率。

圖5（b）表明，GeoQuadIndex較 Hexasore略好，尤其當(dāng)數(shù)據(jù)量較大時，其效率更優(yōu)。這是由于Q1查詢中查詢語言“？s geo：hasGeometry？n”包含兩個變量，在這種情況下，GeoQuadIndex通過解析查詢語句選擇查詢效率更佳的P（OS）方法來查詢數(shù)據(jù)，通過減少對賓語和主語的遍歷從而獲得更好的查詢效率。

圖5 Q1查詢耗時對比Fig.5 Time consuming contrast of Q1

6.3.2 Within空間查詢

Within語義空間查詢（Q2—Q3）試驗結(jié)果見圖6。圖6（a）和 6（b）表 示 Q2 和 Q3 查詢，圖6（c）和6（d）則是對Q2和Q3的橫向比較。

從圖6中可以看出：

（1）相對于 No＿Index，GeoQuadIndex能夠較快的進行地理語義空間查詢，但查詢效率并未提高太大。這是因為在空間查詢前，QueryParser類首先對數(shù)據(jù)集進行了初步的查詢，從而獲得了數(shù)據(jù)量較小的初次查詢數(shù)據(jù)集合（Q1），這樣就減小了GeoQuadIndex和No＿Index的查詢范圍，查詢時間以及兩者的查詢時間差減小。

（2）在查詢時間變化上，GeoQuadIndex和No＿Index的查詢時間曲線呈階梯狀。這是由于本文采用HashMap進行索引構(gòu)造和數(shù)據(jù)查詢，由于HashMap采用負載因子對平衡數(shù)據(jù)的容量和查詢時間，使得Q2和Q3的查詢時間同數(shù)據(jù)大小、HashMap負荷因子以及HashMap處理的對象復(fù)雜度有著密切的關(guān)系。

（3）Q2查詢耗時明顯小于Q3查詢。這是因為相對于純空間查詢Q2，復(fù)合空間查詢Q3包含2組查詢，因此將進行2次圖匹配操作，查詢結(jié)果的數(shù)據(jù)轉(zhuǎn)換耗時以及圖匹配操作耗時導(dǎo)致Q3的時間比Q2的時間要長。

圖6 Within空間查詢（Q2—Q3）Fig.6 Within Spatial query（Q2—Q3）

6.3.3 Intersects空間查詢

Intersects空間查詢（Q4—Q5）的結(jié)果見圖7。由于采用相同的數(shù)據(jù)結(jié)構(gòu)和試驗環(huán)境，可以看出，Intersects語義空間查詢的結(jié)果特征同Within語義空間查詢十分相似。

圖7 Q4和Q5的查詢對比Fig.7 Comparison of Q4and Q5query

7 結(jié) 論

本文結(jié)合傳統(tǒng)RDF數(shù)據(jù)組織方法和空間索引技術(shù)，對地理語義空間索引構(gòu)建中的3個關(guān)鍵問題進行解決，最終實現(xiàn)面向SPARQL查詢的地理語義空間索引。試驗表明，該索引結(jié)構(gòu)能夠快速獲取包含空間信息的RDF節(jié)點，同時能在RDF的三元組空間中利用空間索引加快空間關(guān)系并返回RDF節(jié)點，方法高效可行。需注意的是，本文方法適用于空間信息表述遵從Geo－SPARQL規(guī)范的地理語義數(shù)據(jù)，即空間信息使用GeoSPARQL規(guī)范的WKT Literal和GML Literal進行描述。

［1］ BERNARD V，MONDECA，MARC W.GeoNamesOntology［EB／OL］. ［2012－11－20］.http：∥ www.geonames.org／ontology／documentation.html.

［2］ MIHAI C，GREGOR H，OLIVER K，et al.OSMonto：An Ontology of OpenStreetMapTags［EB／OL］.［2012－11－20］.http：∥wiki.openstreetmap.org／wiki／OSMonto.

［3］ CLAUS S，JENS L，KONRAD H，et al.LinkedGeoData：A Core for a Web of Spatial Open Data［J］.Semantic Web Journal，2012，3（4）：333－354.

［4］ FRANK M，ERIC M，BRIAN M.RDF Primer［EB／OL］.［2013－5－14］.http：∥ www.w3.org／TR／2004／REC－rdf－primer－20040210／.

［5］ STEVE H，ANDY S.SPARQL 1.1Query Language［EB／OL］.［2013－5－14］.http：∥www .w3.org／TR／sparql11－query／

［6］ GRAHAM K，JEREMY J C.Resource Description Framework（RDF）：Concepts and Abstract Syntax［EB／OL］.［2013－5－15］.http：∥ww－w.w3.org／TR／rdf－concepts／.

［7］ YIN Zhangcai，LI Lin.Research of Spatiotemporal Indexing Mechanism Based on Snapshot－increment ［J］. Acta Geodaetica et Cartographica Sinica，2005，34（3）：257－261.（尹章才，李霖.基于快照－增量的時空索引機制研究［J］.測繪學(xué)報，2005，34（3）：257－261.）

［8］ GONG Jun，ZHU Qing，ZHANG Hanwu，et al.An Adaptive Control Method of LODs for 3DScene Based on R－tree Index［J］.Acta Geodaetica et Cartographica Sinica，2011，40（4）：531－534.（龔俊，朱慶，章漢武，等.基于R樹索引的三維場景細節(jié)層次自適應(yīng)控制方法［J］.測繪學(xué)報，2011，40（4）：531－534.）

［9］ WAN Yanmin，GUO Ming.A Combined 2Dand 3DSpatial Indexing of Very Large Point－cloud Data Sets ［J］.Acta Geodaetica et Cartographica Sinica，2012，41（4）：605－612.（王晏民，郭明.大規(guī)模點云數(shù)據(jù)的二維與三維混合索引方法［J］.測繪學(xué)報，2012，41（4）：605－612.）

［10］ WILKINSON K，SAYERS C，KUNO H A，et al.Efficient RDF Storage and Retrieval in Jena2［C］∥Proceedings of the First International Workshop on Semantic Web and Databases.Berlin：［s.n.］，2003：131－151.

［11］ ABADI D J，MARCUS A，MADDEN S R，et al.Scalable Semantic Web Data Management Using Vertical Partitioning［C］∥Proceedings of the 33rd International Conference on Very Large Data Bases.Vienna：ACM ，2007：411－422.

［12］ ANDREAS H，STEFAN D.Optimized Index Structures for Querying RDF from the Web［C］∥ Proceedings of the 3rd Latin American Web Congress.Washington DC：IEEE Computer Society，2005：71－80.

［13］ CATHRIN W，PANAGIOTIS K，ABRAHAM B.Hexastore：Sextuple Indexing for Semantic Web Data Management［J］.VLDB Endowment，2008，1（1）：1008－1019.

［14］ ZHAI X，HUANG L，XIAO Z.Geo－spatial Query Based on Extended SPARQL［C］∥ Proceedings of the 18th International Conference on Geoinformatics.Beijing：IEEE，2010：1－4.

［15］ LI Deren，CUI Wei.Geographic Ontology and SIMG［J］.Acta Geodaetica et Cartographica Sinica，2006，35（2）：143－148.（李德仁，崔巍.地理本體與空間信息多級網(wǎng)格［J］.測繪學(xué)報，2006，35（2）：143－148.）

［16］ MATTHEW S，PERRY.A Framework to Support Spatial，Temporal and Thematic Analytics over Semantic Web Data［D］.Dayton：Wright State University，2008.

［17］ Open Geospatial Consortium.Simple Feature Access－Part 1： Common Architecture ［S］. Wayland： OGC Press，2011.

［18］ JTS Topology Suite Project Team.JTS Topology Suite［EB／OL］.［2013－5－14］.http：∥tsusiatsoftware.net／jts／main.html.

［19］ Open Geospatial Consortium.GeoSPARQL－A Geographic Query Language for RDF Data［S］. Wayland：OGC Press，2011.

［20］ Apache Jena Project Team.Apache Jena［EB／OL］.［2013－5－14］.http：∥jena.apache.org／index.html.

［21］ Apache Jena Project Team.ARQ －A SPARQL Processor for Jena［EB／OL］.［2013－5－14］.http：∥jena.apache.org／documentation／query／index.html.