空间约束对概念的提出与实现
作者简介:程昌秀(1973-),女,博士,教授,研究方向为空间数据库管理系统与GIS应用。E-mail: chengcx@bnu.edu.cn
收稿日期: 2015-03-10
要求修回日期: 2015-04-20
网络出版日期: 2015-09-07
基金资助
国家自然科学基金优秀青年科学基金项目(41222009);国家自然科学基金面上项目(41271405)
Concept of Spatial Constrained Pairs and Its Implementation
Received date: 2015-03-10
Request revised date: 2015-04-20
Online published: 2015-09-07
Copyright
等价类对数据库查询计划的生成与优化有重要作用。为了减少查询计划的搜索空间,空间数据库管理系统(Ingres),将空间拓扑关系视为等价关系,并将空间拓扑关系沉入查询树底端先执行。由于非等值空间关系谓词不具备等价类的传递性,常常导致一些空间查询不能正确执行。本文提出了空间约束对的概念,即将非等值空间谓词连接的2个空间列、或某表的空间列与其空间索引表中的KEY列(记录了MBR)视为空间约束对。空间约束对除不具备等价关系的自反性、对称性和传递性外,其启发式策略仍可沿用等价类的相关规则。此外,本文还探讨了空间约束对在Ingres中的实现,并开展了相关的实证研究。实验表明:将空间拓扑谓词两端的属性视为空间约束对后,原本不能正确执行的查询语句,在改后的Ingres中能正确地找到较优执行计划。
程昌秀 , 杨山力 , 宋晓眉 , 王利军 . 空间约束对概念的提出与实现[J]. 地球信息科学学报, 2015 , 17(9) : 1009 -1013 . DOI: 10.3724/SP.J.1047.2015.01009
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.
Fig. 1 Demo of non-transitivity on intersects图1 Intersects不具传递性示意图 |
Fig. 2 Mask up spatial constrained pairs from list of equal classes图2 屏蔽等价类序列表中的空间约束对 |
Fig. 3 Test data图3 测试数据 |
Fig. 4 A building error before masking up spatial constrained pairs图4 空间约束对被屏蔽前的编译错误 |
Fig. 5 An optimal query plan in Ingres after masking up spatial constrained pairs图5 Ingres查询计划 |
The authors have declared that no competing interests exist.
[1] |
|
[2] |
|
[3] |
|
[4] |
|
[5] |
|
[6] |
|
[7] |
|
[8] |
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|
[13] |
|
[14] |
|
[15] |
|
[16] |
|
[17] |
|
[18] |
|
[19] |
|
[20] |
|
[21] |
|
[22] |
|
/
〈 |
|
〉 |