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

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

Concept of Spatial Constrained Pairs and Its Implementation

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.