地球信息科学学报 ›› 2015, Vol. 17 ›› Issue (9): 1009-1013.doi: 10.3724/SP.J.1047.2015.01009

• •    下一篇

空间约束对概念的提出与实现

程昌秀1,2(), 杨山力1, 宋晓眉2, 王利军3   

  1. 1. 北京师范大学减灾与应急管理研究院,北京 100875
    2. 中国科学院地理科学与资源研究所,北京 100101
    3. 中国互联网络信息中心,北京 100190
  • 收稿日期:2015-03-10 修回日期:2015-04-20 出版日期:2015-09-10 发布日期:2015-09-07
  • 作者简介:

    作者简介:程昌秀(1973-),女,博士,教授,研究方向为空间数据库管理系统与GIS应用。E-mail: chengcx@bnu.edu.cn

  • 基金资助:
    国家自然科学基金优秀青年科学基金项目(41222009);国家自然科学基金面上项目(41271405)

Concept of Spatial Constrained Pairs and Its Implementation

CHENG Changxiu1,2,*(), YANG Shanli1, SONG Xiaomei2, WANG Lijun3   

  1. 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
  • Received:2015-03-10 Revised:2015-04-20 Online:2015-09-10 Published:2015-09-07
  • Contact: CHENG Changxiu E-mail:chengcx@bnu.edu.cn
  • About author:

    *The author: SHEN Jingwei, E-mail:jingweigis@163.com

摘要:

等价类对数据库查询计划的生成与优化有重要作用。为了减少查询计划的搜索空间,空间数据库管理系统(Ingres),将空间拓扑关系视为等价关系,并将空间拓扑关系沉入查询树底端先执行。由于非等值空间关系谓词不具备等价类的传递性,常常导致一些空间查询不能正确执行。本文提出了空间约束对的概念,即将非等值空间谓词连接的2个空间列、或某表的空间列与其空间索引表中的KEY列(记录了MBR)视为空间约束对。空间约束对除不具备等价关系的自反性、对称性和传递性外,其启发式策略仍可沿用等价类的相关规则。此外,本文还探讨了空间约束对在Ingres中的实现,并开展了相关的实证研究。实验表明:将空间拓扑谓词两端的属性视为空间约束对后,原本不能正确执行的查询语句,在改后的Ingres中能正确地找到较优执行计划。

关键词: 空间数据库, 查询优化, 等价类, 空间约束对, 空间拓扑关系

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