面向SPARQL查询的地理语义空间索引构建方法

段红伟，孟令奎，黄长青，李 颖，李继园

1.武汉大学 遥感信息工程学院，湖北 武汉430079；2.河南省气象科学研究院，河南 郑州450003

1 引 言

语义Web技术的发展推动了地理数据的语义化表达。随着各种地理数据语义化项目，如GeoName［1］、OpenStreetMap［2］、Linked GeoData［3］等项目的不断开展，地理语义数据愈加丰富和庞大，如何构建适合的地理语义空间索引来快速有效地进行地理语义空间查询变得愈加重要。

同传统的地理数据相比，地理语义数据采用RDF（resource description framework）［4］定义数据模型，采 用 SPARQL［5］语 言（simple protocol and RDF query language）进行数据查询，这种数据和查询语言的特点要求地理语义数据采用RDF的三元组｛主语，谓词，宾语｝对数据进行描述，地理语义空间查询必须在三元组空间上进行空间关系和空间分析运算，并基于SPARQL查询返回主语、谓词或宾语这样的RDF节点［6］，从而使得传统的空间索引技术和RDF数据组织方法不能直接用于地理语义空间索引的构建。

在传统的空间索引技术方面，虽然传统的空间索引技术已经在二维［7］、三维［8］和二维三维混合几何对象［9］上得到广泛应用，但是由于空间索引没有对应的地理语义数据到几何对象的映射和链接模型，使得传统的空间索引技术在地理语义空间索引。而在RDF数据组织方法方面，现有的方法如属性表法（property table）［10］、垂直分割法（vertical partitioning）［11］、多索引结构法（multipleindexing）［12］、六倍索引法（hexastore）［13］等方法，通过建立三元组要素主语、谓词和宾语间的二元链接来实现对数据快速查询。但是这些方法没有定义空间数据类型，缺乏对空间信息的识别、组织和映射，因此并不适用于地理语义空间查询。

针对上述问题，本文基于地理语义查询在方法论［14］、本体词表结构［15］及实现框架［16］上的研究，将传统空间索引技术和RDF数据组织方法进行结合，通过构建合适的地理语义空间索引，实现高效的面向SPARQL的地理语义空间查询，从而提供一种轻量级的地理语义空间查询方案。

2 地理空间四元组模型

构建地理语义空间索引需解决三个问题：①快速获取地理语义数据获得包含空间信息的RDF节点—空间RDF节点；②对空间RDF节点进行包装和转换来建立空间几何对象，并利用空间索引对空间几何对象进行索引；③在SPARQL语言层次上使用空间索引进行空间查询，并正确返回RDF节点数据。

为了明确地理语义空间索引构建中的对象及其关系，为地理语义空间索引的构建提供抽象的模型和方法指导，本文基于地理语义数据的特点构建了地理语义空间数据模型—地理空间四元组模型（简称GeoQuad），其模型结构如图1所示。可以看出，GeoQuad通过增加一个表示空间特征的空间类型戳来扩展RDF三元组结构，从而提供地理语义数据的空间信息。

图1 GeoQuad的模型结构图Fig.1 The structure of GeoQuad

基于RDF和空间数据定义，本文对GeoQuad中的对象作如下定义。

定义1（RDF三元组，RDF 节点）：给定URIref集合R、空节点集合B和文字类型节点L，如果一个三元组α∈（R∪B）×R×（R∪B∪L），则称α为一个RDF三元组（RDF Triple），而α的元素β∈（主语（Subject）∨谓词（Predicate）∨宾语（Object））称为RDF节点（RDF Node）。

定义2（空间三元组）：给定一个RDF三元组λ∈α，如果λ的宾语包含空间坐标信息，则称λ为一个空间三元组（Geo RDF Triple）。λ的主语称为地物节点（FeatureSub），谓词称为空间谓词（SpatialPredicate），宾语称为空间节点（GeoObj）。

定义3（空间类型戳）：一个空间类型戳（Geo－Type）由值空间（Value Space）、词法空间（Lexical space）和词—值（Lexical－to－Value）映射三部分组成。其中值空间是一组OGC定义的空间对象［17］（GeoElem）集合，可由词法空间解析生成；词法空间是一个包含空间节点的集合，由Unicode字符串表示；词－值映射将词法空间的空间节点映射为值空间的空间对象。

定义4（GeoQuad实例）：给定空间三元组λ，空间类型戳κ，GeoQuad实例为组合（λ，κ）。

根据GeoQuad模型，本文第3部分构建地理语义空间索引结构来对数据进行组织和索引，在第4部分探讨空间类型戳中空间节点到空间对象的封装与转换；在第5部分探讨SPARQL语言上的空间查询实现，从而对地理语义空间索引的三个问题进行解决。

3 地理语义空间索引结构

3.1 地理语义空间查询模式

地理语义空间索引（GeoQuadIndex）同地理语义查询模式紧密相关。地理语义空间查询遵循三元组的图匹配（Grapth Mactching）模式，即将查询变量映射为三元组的主语、谓词或宾语，然后以三元组的形式在数据中进行查找和匹配，其形式主要有：

（1）（Constant｜Bindvariable，SpatialPredicate，？），主语为常量或绑定变量，空间谓词给定，宾语为变量，通过三元组匹配和空间关系运算，得到满足条件的宾语。

（2）（Constant｜Bindvariable，SpatialPredicate，Constant｜Bindvariable），主语和宾语为常量或绑定变量，空间谓词给定，通过空间关系运算，查询主语和宾语上的空间RDF Node是否在SpatialPredicate的关系上成立。

（3）（？，SpatialPredicate，Constant｜Bindvar iable），主语为变量，空间谓词给定，宾语为常量或绑定变量，通过三元组匹配和空间关系运算，得到满足条件的主语。

可以看出，地理语义空间查询必须给定空间谓词，这种查询特点可以结合六倍索引方法中的POS结构和垂直分割方法中的P（OS）结构来构建地理语义空间索引机构。

3.2 地理语义空间索引结构定义

地理语义空间索引结构如图2所示，分为地理RDF索引部分和映射结构2个部分。

图2 地理语义空间索引结构Fig.2 The structure of geo semantic spatial index

3.2.1 地理RDF索引部分

本部分包括POS和P（OS）两部分。POS即Predicate－Object－Subject，采用三级索引结构，这种方法适用于（？，SpatialPredicate，Constant）查询，即谓语和宾语已知，查找未知主语的情况。P（OS）采用二级索引结构，其优势在于当主语和宾语未知时，不需像POS那样遍历O列表和S列表，该索引结构适用于（？｜Bindvariable，SpatialPredicate，Bindvariable）或（Bindvariable，SpatialPredicate，？｜Bindvariable）查询，即谓语已知，查询主语和宾语。

3.2.2 映射结构部分

本部分建立了空间节点到空间对象的映射、空间对象到GID（空间对象ID号）的映射，并建立空间索引结构，是空间类型戳的直接体现。其中空间索引部分基于JTS组件［18］，可以调用JTS中的空间索引，也可以构建新的空间索引。

算法1为GeoQuadIndex的构建算法，主要包括4个步骤：

（1）对地理语义数据解析，获得包含空间信息的三元组Geotriples，将Geotriples中的宾语GeoObj转换为空间几何对象GeoElem，并建立双映射表 Map（GeoObj，GeoElem）和 Map1（GeoElem，GID）（第1—10行）。

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

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

（4）利用上述建立的数据结构（POS，P（OS），SpatialIndex，Map，Map1）构 建 Geo－QuadIndex，并返回该数据结构（第14行）。

4 空间节点到空间对象的封装与转换

空间节点在地理语义数据中表现为类型文字（type Literal），并按照某数据规范进行描述，如GeoSPARQL规范［19］利用 WKT Literal和GML Literal来描述空间信息。基于通用性，本文对GeoSPARQL规范中WKT和GML描述的空间节点转换为空间对象。

WKT规范简单，WKT描述的空间节点到空间对象的转换采用JTS提供的解析包进行了转换。GML规范复杂，GML描述的空间节点到空间对象的转换需要利用JAXB（Java xml bindings）技术，其转换过程如图3所示。

图3 GML描述的空间节点到空间对象的转换图Fig.3 The transform of GeoObj to GeoElm

如图3所示，GML描述的空间节点到空间对象的转换过程为：首先利用JAXB，将GML Schema中各种元素生成Java类集合；然后对这些Java类进行扩展和重写，利用JTS加入几何特性从而支持OGC定义的几何要素；最后利用Unmashal编出一个Java实例对象，该实例对象即为转换后的空间对象。

5 SPARQL空间查询实现

本文基于Jena Graph扩展机制来实现Geo－QuadIndex的SPARQL空间查询。Jena是一种基于Java的语义Web框架，采用Graph层、Enh－Graph层和 Model（Ontology）层的三层体系结构。Graph层位于底层，定义了非RDF Triple类型的数据处理机制。

图4为基于Jena Graph扩展机制实现地理语义空间查询的类结构图，包括空间索引类Geo－QuadIndex、Graph扩展类SpatialGraph、空间运算类SpatialOp和SPARQL查询语法处理类（NormalPropertyFunctionEval及其子类）。

GeoQuadIndex类创建数据索引，并将空间节点同空间对象进行转化和映射。GeoQuadIndex类包装了JTS的Geometry对象（＿geo）和SpatialIndex索引对象（＿spatialIndex）；SpatialGraph类管理地理语义数据和数据索引，其中通过一个Graph对象（＿innerGraph）来管理地理语义数据，通过 GeoQuadIndex对象（＿index）来管理数据索引；SpatialOp类定义了支持空间查询的各种算法，利用GeoQuadIndex类中的空间索引实现空间关系的快速运算；QueryParser类用于对查询语句进行解析，从而明确地理语义数据采用P（OS）还是POS结构，并最终得到一个SpatialGraph对象；Normal－PropertyFunctionEval及其子类定义了SPARQL查询的空间操作算子。

图4 SPARQL空间查询实现Fig.4 The implement of SPARQL spatial query

6 试验和分析

6.1 试验环境和数据

本文试验所采用的软件包基于Jena［20］、ARQ［21］和JTS提供的API，并在Eclipse环境下利用Java语言编码实现，所提索引方法（Geo－QuadIndex）的空间索引采用四叉树索引。试验平台为一台Win7系统的笔记本电脑，2.3GHz主频的Intel Core i5处理器，4G内存。试验数据来自GeoName，并通过对原始数据进行编辑、合并获得。试验数据基于RDF XML语法，数据实例的空间信息可以同GeoSPARQL规范的WKT Literal数据类型兼容。表1所示为本文使用的8个测试数据集。

表1 试验使用的地理语义数据集Tab.1 Geo semantic data sets for experiment

6.2 查询测试方案

本文试验包含Q1—Q5这5个地理语义查询测试方案，查询语句如表2所示。根据查询特点可以将Q1—Q5分为两个部分。

（1）测试对空间节点的获取效率（Q1），该测试通过地物节点来查询对应的空间节点。

（2）测试语义空间查询效率（Q2—Q5），考虑到空间关系在拓扑定义中通常是互逆或者包容的，本文选择2个典型的空间查询作为空间查询测试方案，即 Within空间查询（Q2—Q3）、Intersects空间查询（Q4—Q5），其中Q2和Q4是纯空间查询，Q3和Q5是复合空间查询。

表2 试验查询样例Tab.2 Query samples in experiment

6.3 试验结果与分析

6.3.1 Q1查询

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

Q1查询的试验结果如图5所示，其中图5（a）是 No＿Index、GeoQuadIndex、Hexastore的对比情况，图5（b）是 GeoQuadIndex 和Hexasore的比较。

图5（a）表明，无论是 GeoQuadIndex，还是Hexasore，其对空间节点的查询效率均远高于No＿Index。这 是 由 于 GeoQuadIndex 和Hexasore均对三元组的谓语、主语和宾语建立了HashMap映射表，从而不需要对3个部分进行遍历，从而提高了图匹配效率。

图5（b）表明，GeoQuadIndex较 Hexasore略好，尤其当数据量较大时，其效率更优。这是由于Q1查询中查询语言“？s geo：hasGeometry？n”包含两个变量，在这种情况下，GeoQuadIndex通过解析查询语句选择查询效率更佳的P（OS）方法来查询数据，通过减少对宾语和主语的遍历从而获得更好的查询效率。

图5 Q1查询耗时对比Fig.5 Time consuming contrast of Q1

6.3.2 Within空间查询

Within语义空间查询（Q2—Q3）试验结果见图6。图6（a）和 6（b）表 示 Q2 和 Q3 查询，图6（c）和6（d）则是对Q2和Q3的横向比较。

从图6中可以看出：

（1）相对于 No＿Index，GeoQuadIndex能够较快的进行地理语义空间查询，但查询效率并未提高太大。这是因为在空间查询前，QueryParser类首先对数据集进行了初步的查询，从而获得了数据量较小的初次查询数据集合（Q1），这样就减小了GeoQuadIndex和No＿Index的查询范围，查询时间以及两者的查询时间差减小。

（2）在查询时间变化上，GeoQuadIndex和No＿Index的查询时间曲线呈阶梯状。这是由于本文采用HashMap进行索引构造和数据查询，由于HashMap采用负载因子对平衡数据的容量和查询时间，使得Q2和Q3的查询时间同数据大小、HashMap负荷因子以及HashMap处理的对象复杂度有着密切的关系。

（3）Q2查询耗时明显小于Q3查询。这是因为相对于纯空间查询Q2，复合空间查询Q3包含2组查询，因此将进行2次图匹配操作，查询结果的数据转换耗时以及图匹配操作耗时导致Q3的时间比Q2的时间要长。

图6 Within空间查询（Q2—Q3）Fig.6 Within Spatial query（Q2—Q3）

6.3.3 Intersects空间查询

Intersects空间查询（Q4—Q5）的结果见图7。由于采用相同的数据结构和试验环境，可以看出，Intersects语义空间查询的结果特征同Within语义空间查询十分相似。

图7 Q4和Q5的查询对比Fig.7 Comparison of Q4and Q5query

7 结 论

本文结合传统RDF数据组织方法和空间索引技术，对地理语义空间索引构建中的3个关键问题进行解决，最终实现面向SPARQL查询的地理语义空间索引。试验表明，该索引结构能够快速获取包含空间信息的RDF节点，同时能在RDF的三元组空间中利用空间索引加快空间关系并返回RDF节点，方法高效可行。需注意的是，本文方法适用于空间信息表述遵从Geo－SPARQL规范的地理语义数据，即空间信息使用GeoSPARQL规范的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］.测绘学报，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树索引的三维场景细节层次自适应控制方法［J］.测绘学报，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.（王晏民，郭明.大规模点云数据的二维与三维混合索引方法［J］.测绘学报，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.（李德仁，崔巍.地理本体与空间信息多级网格［J］.测绘学报，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.