EN中文

Journal of Geo-information Science >

2015 , Vol. 17 >Issue 9: 1009 - 1013

DOI: https://doi.org/10.3724/SP.J.1047.2015.01009

Orginal Article

Concept of Spatial Constrained Pairs and Its Implementation

  • CHENG Changxiu , 1, 2, * ,
  • YANG Shanli 1 ,
  • SONG Xiaomei 2 ,
  • WANG Lijun 3
Expand
  • 1. Academy of Disaster Reduction and Emergency Management,Beijing Normal University, Beijing 100875, China
  • 2. Institute of Geographic Sciences and Natural Resources Research, CAS, Beijing 100101, China
  • 3. China Internet Network Information Center, CNNIC, Beijing 100190, China
*Corresponding author: CHENG Changxiu, E-mail:

Received date: 2015-03-10

  Request revised date: 2015-04-20

  Online published: 2015-09-07

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

Equal classes play an important role in the generation and optimization of query plans. In order to reduce the search space of query plan, Ingres often takes two attributes that connected by a non-equal spatial topology relation operator as an equal class, and puts a spatial join operator between them to the bottom of the query plan tree. After filtering the spatial topology relation operator, the database system will have fewer data to proceed in the following operators, and produce higher efficiency. However, if take them as equal classes, just as in Ingres, it often results in building some errors in the spatial query plans especially for some queries with multiple spatial joins. Therefore, the non-equal spatial relation operators are not an equal relation. This paper analyzes the reason why non-spatial topology relation is not an equal relation and puts forward to use the spatial constrained pair instead of equal classes. The paper also gives a definition of a spatial constrained pair, which is an attributes pair connected by a non-equal spatial relation operator, or the spatial column of a table and the KEY column of its spatial index table. Spatial constrained pair is a sub-concept of equal class. It could adopt some heuristic strategies of equal class on building query plan except for transitivity. The paper explores a database implementation about the spatial constrained pairs in Ingres. Taking consideration of a query with multiple spatial joins, this paper conducts two tests. One takes the attributes pairs connected by a non-equal spatial relation operator as equal classes; the other one takes them as spatial constrained pairs. If follow the heuristic strategies of equal classes, it will produce some errors in the procedure of plan generation. However, if follow the heuristic strategies of spatial constrained pairs, it could help the system find the best query plan.

Key words： spatial database; query optimization; equal classes; spatial constrained pairs; spatial topology relation

Cite this article

CHENG Changxiu , YANG Shanli , SONG Xiaomei , WANG Lijun . Concept of Spatial Constrained Pairs and Its Implementation[J]. Journal of Geo-information Science, 2015 , 17(9) : 1009 -1013 . DOI: 10.3724/SP.J.1047.2015.01009

1 引言

随着GPS、无线通信等技术的快速发展,公众对矢量数据的查询性能提出了越来越高的要求[1-2]。查询优化器对提高数据库系统的查询性能有重要意义[3]。在数据库内核中,查询优化器的主要任务是根据SQL语句涉及的表及相关的参数信息,生成多个有效的查询计划,再根据查询代价评估模型,选出代价最低（执行速度最快）的查询计划。近年来,国内外在空间索引[4-6]、查询算法优化[7-12]、查询代价估算[13-14]等领域有一定的进展,但有关空间查询计划生成的研究较少。
在数据库内核中,等价类对空间查询计划的生成起着重要作用[15-16]。在关系数据库中,等价类主要有2种：（1）SQL语句的where子句中具有等值连接关系的属性。例如,查询语句中存在a.i=b.i的限定谓词,其表a的i属性与表b的i属性则属于同一个等价类;（2）索引表中存储基表各记录的地址指针（TIDP）与基表的各记录的地址（TID）,也属于同一个等价类。在查询树的启发式优化中,查询优化器常将同一等价类的连接操作移向查询树叶端先执行;因为等值连接的执行结果集往往很少,极大减少了参与后续运算的数据量,从而提高了查询速度[16]。
在空间数据库中,空间拓扑关系是各类空间查询的重要连接谓词[17-19]。常见的空间拓扑谓词有相交（Intersects）、相离（Disjoint）、包含（Within）、包含于（Contains）、相接（Touches）、交叠（Overlaps）、跨越（Crosses）、相等（Equals）等[20]。基于OME扩展的Ingres空间数据库管理系统[21],常将这些用空间拓扑谓词连接的空间属性视为等价类。Ingres是较早的数据库管理系统,始于加利福尼亚大学柏克莱分校的一个研究项目。从20世纪80年代中期,在Ingres基础上产生了很多商业数据库软件,例如,Sybase、Microsoft SQL Server、Informix等。80年代中期启动的后继项目Postgres,产生了PostSQL、Illustra。由此可见,Ingres是对关系数据库管理系统最经典、最全面、最具体的诠释。Ingres将这些用空间拓扑谓词连接的空间属性视为等价类的益处在于能将空间拓扑关系谓词沉入查询树底端先执行。经空间拓扑谓词连接的查询,其查询结果集往往较少;先进行空间连接可降低后续查询操作的复杂性,提高系统查询速度。此外,Ingres也将R-tree的TIDP与空间表的TID视为等价类。其益处在于在某些仅涉及MBR的查询中,可用有位置信息的索引表替换空间表,提高空间查询的效率。
但是,如Ingres一样,若将空间拓扑关系两端的属性视为等价类,或将空间表的TID及其索引的TIDP视为等价类,则无论在理论上、还是实践中都存在问题。本文分析了不能沿用数据库领域等价类概念的原因,提出了空间约束对的概念,并用空间约束对来表达这种空间约束关系;同时,对Ingres的内核进行了相应的改造,避免了简单将其视为等价类情况下的执行错误,展现了空间约束对在查询优化中的作用。

2 等价类与空间约束对

2.1 等价关系与等价类

定义1：设R为定义在集合A上的一个关系,若R是自反的、对称的、传递性的,则称R为等价关系[22]。自反性是指对集合中的每一个元素a都有a R a 成立;对称性是指对集合中的任意元素a、b,若a R b成立,则b R a也一定成立;传递性是指对集合中的任意元素a、b、c,若a R b、且b R c成立,则a R c一定成立。常见的等价关系有等于关系、三角形的相似关系等。等价关系可决定一个划分[22]。
定义2：设R为集合A上的等价关系,对于任何 a ∈ A ,集合 [ a ] R = { x | x ∈ A , a R x } 称为元素a形成的R等价类[22]。根据R的自反性、对称性、传递性,容易证明集合上的不同等价类两两互不相交,且其并等于原集合。
根据等价关系的定义,只有Equals关系才具有自反性、对称性和传递性,故仅以Equals连接的属性才能称为等价类。例如,在T1.a1 Equals T2.a2 and T2.a2 Equals T3.a3的连接条件中,T1.a1与T2.a2、T2.a2与T3.a3是显式的等价类,根据等价关系的传递性, T1.a1、T2.a2、T3.a3实际是同一等价类。
对于其他空间拓扑谓词（以下简称“非空等值空间谓词”）,严格地说Intersects仅满足自反性和对称性,但不满足传递性,即当A.geo Intersects B.geo,且B.geo Intersects C.geo时,并不能推出A.geo Intersects C.geo,如图1所示;而Disjoint、Touches、Overlaps、Crosses则仅具备对称性;对于Within、Contains则不具备等价关系的任何一个特性。因此,不能将非等值空间谓词视为等价关系。
Fig. 1 Demo of non-transitivity on intersects

图1 Intersects不具传递性示意图

2.2 空间约束对及其启发式规则

不能将非等值空间谓词视为等价关系,也不能将非等值空间谓词连接的属性视为等价类。但是,针对这些谓词,又需加入一些与等价类相似的启发式优化策略,故本文提出了空间约束对的概念。将非等值空间谓词连接的2个空间列、或某表的空间列与其空间索引表中的KEY列（记录了MBR）称为空间约束对。空间约束对仅表明2个空间属性间有约束关系,该关系不具备自反性、对称性和传递性。将非等值空间谓词连接的2个空间列称为第一类空间约束对,而将某表的空间列与其空间索引表中的KEY列称为第二类空间约束对。
在空间查询优化器中,对于第一类空间约束对要求计划枚举阶段,将操作沉到树的底端执行,但是不支持关系操作的自反、对称和传递;对于第二类空间约束对,则要求在仅涉及MBR的查询中,可用有空间索引的Key值替换基表的空间列。

2.3 空间约束对的实现

Ingres在查询解析阶段已将上述空间约束对加入等价类列中,如果严格地将空间约束对从等价类列表中抽取出来、重新申请内存存储、重新添加启发式策略的编码,这种实现不仅编码复杂、工作量巨大,同时可能也会影响到Ingres内的稳定。本文采取的方案是在Ingres中,仍将空间约束对存放在等价类列表中,沿用等价类的启发式优化规则,但等价关系在进行自反、对称和传递之后,计算当前节点的代价之前,需编写opn_clearuleseqcs(subquery, root)函数,将等价类列表的空间约束对删除,并在文件opnprocess.c的opn_process函数中调用该函数,具体如图2所示。
Fig. 2 Mask up spatial constrained pairs from list of equal classes

图2 屏蔽等价类序列表中的空间约束对

Ingres中opn_process函数的主要原理是：枚举出所有可以使用的索引的集合,将其加入到基表集合中;对所有编号生成排列组合;每生成一个排列,判断其是否满足等价类规则,以及本文提出的空间约束对规则,如果不符合就会根据当前排列去生成下一个排列;找到符合规则的排列,形成一个节点,将该节点放到代价计算函数中计算节点代价;存储不同树形不同排列的最小代价;结束退出。opn_ clearuleseqcs函数是在计算当前节点代价之前加载进去,以防空间约束对所关联的等价类在代价计算之后的“最优”计划编译和执行过程中造成影响。opn_clearuleseqcs函数遍历当前节点的所有等价类,判断该等价类是否是空间约束对,如果是,则将其从当前节点的等价类集合中去除;递归处理左子树;递归处理右子树;结束返回。

3 空间约束对改进前后的实验对比

以阿拉加斯加的树木区域（trees表,多边形数据）、草地（grassland表,多边形数据）和建筑物（builtups表,点数据）3个表为测试数据,结果如图3所示。在Ingres中,2个表间的查询将空间拓扑谓词视为等价类谓词,不会报错,但空间查询涉及3个或3个以上的表时,可能会出现错误。以下述SQL语句为例,测试其在改进前后的Ingres中执行情况,证明空间约束对修改的正确性和有效性。
Fig. 3 Test data

图3 测试数据

SELECT a.* FROM trees a, grassland b, builtups c
WHERE a.shape st_intersects b.shape and a.shape st_intersects c.shape and a.shape st_intersects ST_GEOMFROMTEXT('POLYGON((500000 3000000, 500000 5000000, 1500000 5000000, 1500000 3000000, 500000 3000000))', 32767)
在没有屏蔽空间约束对前,该查询在Ingres中不能正确执行。通过跟踪源码发现：系统卡在生成空间查询计划阶段。原因在于Ingres通过等价关系的递推性,为Intersects找到了一堆所谓等价的空间属性,将这些空间属性加入查询节点后,发现有些空间属性又不在查询节点的数据表中,导致一致性错误;故执行会报出图4所示的错误。
Fig. 4 A building error before masking up spatial constrained pairs

图4 空间约束对被屏蔽前的编译错误

在经上述的屏蔽空间约束对的相关修改、并更正Ingres相应的bug后,上述查询得以正确的执行;其查询计划如图5所示,执行时间为3 s。该计划首先对grassland和trees 2个表进行了投影-约束（Proj-rest…）操作;在grassland投影-约束操作中,主要对其143个元组进行了排序并集中存储,故磁盘页面由原来的7个减少为2个;在trees的投影-约束操作中,重点执行了空间POLYGON的过滤操作,将元组数从原来的444个减少到34个,由于没有对Trees建索引,故该计划没有涉及到索引操作;接下来的笛卡尔连接（Cart_Prod）是执行grassland.shape和过滤后的trees.shape的空间连接操作,表中相互intersects的对象一共有36对;最后,用36对元组中的trees.shape与buildups投影约束后的18条元组做intersects的连接,连接结果中有12条记录。
Fig. 5 An optimal query plan in Ingres after masking up spatial constrained pairs

图5 Ingres查询计划

由此可见：（1）不能简单地将非等值空间拓扑谓词视为等价关系;（2）若将空间拓扑谓词视为等价类谓词,涉及2个表的空间连接查询不会报错,但涉及3个或3个以上表的空间连接查询时,会导致错误;（3）将非等值空间拓扑谓词的空间列视为空间约束对,在Ingres源码中屏蔽相应的递推操作后,系统能找到较优执行计划,并执行。

4 结语

本文分析了非等值空间关系与等价关系的区别,提出了空间约束对的概念,并在Ingres中改进实现,实现了复杂空间查询的启发式优化策略,取得了较好的成效。
多年来,国内外空间数据库的研究大多集中在数据库系统的外围,缺乏对内核中相关理论方法的探讨。为了切实提高空间数据的查询性能,后续应针对空间数据、空间操作等的特点,进一步发展、完善GIS的数据管理理论体系和技术方法。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
朱进,胡斌,邵华,等.基于内存数据库Redis的轻量级矢量地理数据组织[J].地球信息科学学报,2014,16(2):165-172.

[2]
赵彦庆,陈荣国,袁琳.地理空间数据库性能测试软件的设计与实现[J].地球信息科学学报,2010,12(5):674-679.

[3]
程昌秀. 空间数据库管理系统概论[M].北京:科学出版社,2012.

[4]
吴明光. 一种空间分布模式驱动的空间索引[J].测绘学报,2015,44(1):108-115.

[5]
龚俊,朱庆,张叶廷,等.顾及多细节层次的三维R树索引扩展方法[J].测绘学报,2011,4(2):249-255.

[6]
花杰,邢廷炎,芮小平.一种适合多源地球物理数据三维可视化的快速空间索引技术[J].地球物理学进展,2013,28(3):1626-1636.

[7]
Gilberto G, José RP, Nieves B, et al.The largest empty rectangle containing only a query object in Spatial Databases[J]. GeoInformatica, 2014,18(2):193-228.

[8]
黄铁,张奋.改进的基于R-树的空间连接代价模型[J].计算机工程与设计,2009,30(7):1691-1693.

[9]
付仲良,刘思远,俞志强.一种双映射变换的空间索引及空间连接算法研究[J].武汉大学学报(信息科学版),2014,39(10):1248-1251.

[10]
Fabio G, CláudioSB, Clodoveu AD. Improving geographic information retrieval in spatial data infrastructures[J].GeoInformatica,2014,18(4):793-818.

[11]
Zhu Y, Hua L.[D]Optimization of RDF link traversal based query execution[J]. Journal of Southeast University(English Edition),2013,29(1):27-32.

[12]
张舜,邓亚丹,钟志农.一种基于访问图优化的缓存替换算法[J].计算机应用与软件,2010,27(9):46-48.

[13]
陈海珠. 基于闭欧拉直方图的空间查询代价模型[J].软件,2013,34(6):61-64.

[14]
李博涵,秦小麟,陈逸菲,等.基于PQR-tree的空间查询代价模型[J].计算机工程与科学,2012,34(5):161-167.

[15]
刘晓蔚. 基于等价类规则树的高效关联规则挖掘算法[J].计算机应用与软件,2015,32(1):313-315,319.

[16]
宋晓眉,叶晓俊,曾小青,等.PostgreSQL查询优化中的等价类研究与改进[J].计算机工程与应用,2014,50(14):31-38,126.

[17]
张伟松,任海英.GIS空间关系在北京市水务普查中的应用[J].北京测绘,2013,4(5):30-34,9.

[18]
顾珊. 面向空间拓扑关系的条件离群检测算法研究[D].南京:南京师范大学,2012.

[19]
程昌秀. 空间数据库管理系统概论[M].北京:科学出版社,2012.

[20]
郭庆胜,杜晓初,刘浩.空间拓扑关系定量描述与抽象方法研究[J].测绘学报,2005,34(2):123-128.

[21]
李新宇. Ingres空间扩展研究与应用[D].长沙:中南大学,2011.

[22]
左孝凌,李为鑑,刘永才.离散数学[M].上海:上海科学技术文献出版社,1982.

Options
Outlines

/

〈 〉