EN中文

Journal of Geo-information Science >

2017 , Vol. 19 >Issue 5: 581 - 586

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

Orginal Article

Study on Spatial Heuristic Rules for Query Plan Enumeration

  • CHENG Changxiu , * ,
  • SHEN Shi ,
  • YANG Shanli
Expand
  • 1. State Key Laboratory of Earth Surface Processes and Resource Ecology, Beijing Normal University, Beijing 100875, China;2. Key Laboratory of Environmental Change and Natural Disaster, Beijing Normal University, Beijing 100875, China;3. Faculty of Geographical Science, Beijing Normal University, Beijing 100875, China;4. Center for Geodata and Analysis, Beijing Normal University, Beijing 100875, China
*Corresponding author: CHENG Changxiu, E-mail:

Received date: 2016-12-16

  Request revised date: 2017-02-20

  Online published: 2017-05-20

Copyright

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

Abstract

Query plan enumeration and query cost estimation are two important steps in a query optimizer of DBMS. The query plan enumeration is responsible for enumerating some candidate query plans with best or better plan. The query cost estimation is used to choose the best plan for execution. However, if the candidate query plans in the first step are too many, the second step has to spend more time on estimating them. In order to save the cost of estimation time and improve execution efficiency of the system, spatial heuristic rules are used to eliminate some impracticable query plans. This paper firstly explained some basic concepts, i.e. query graph, joined tree, and query plan. Then, we put forward three heuristic rules for spatial equal classes and spatial constrained pairs. The first is that spatial join operators should be established on spatial equal classes or spatial constrained pairs. The second is that the orders of join operators should be equal classes, spatial equal classes, non-Cartesian products of ordinary attributes, spatial constrained pairs and Cartesian products of ordinary attributes. The last one is a recursion rules about spatial equal classes. It means, only the attributes in spatial equal classes of a query plan could be transmitted each other. After that, this paper puts forward two rules for spatial indexing tables. The first is that it's better to replace a spatial table with its spatial indexing, when there is a spatial predicate on some spatial attributes. The second is the spatial indexing table must be on the top of its original table in a query plan and there should be a TID join between spatial index table and its original table. In the following sections, we explains the rules mentioned above and analyses how to improve query efficiency by using low cost operation as soon as possible and how to filter out candidate data as few as possible. At last, we present a sample to show how to eliminate some impracticable query plans by those spatial heuristic rules. Those rules are not only for query optimizer, but also for SQL programmer.

Key words： spatial query; enumeration of query plans; spatial heuristic rules; spatial constrain pairs; join tree

Cite this article

CHENG Changxiu , SHEN Shi , YANG Shanli . Study on Spatial Heuristic Rules for Query Plan Enumeration[J]. Journal of Geo-information Science, 2017 , 19(5) : 581 -586 . DOI: 10.3724/SP.J.1047.2017.00581

1 引言

查询优化器对提高数据库系统的查询性能具有重要意义。在数据库内核中,查询优化器的主要任务是根据SQL语句涉及的表及相关的参数信息,生成多个有效的查询计划,再根据查询代价评估模型,选出代价最低（执行速度最快）的查询计划。空间查询优化通常分为查询计划生成和代价评估2个阶段。查询计划生成按某种规则罗列出所有可能的查询计划,并尽可能囊括最优计划。查询计划的生成包括树形枚举、表排列、操作枚举3个阶段。代价评估则是根据评估模型,选出代价最低（执行速度最快）的查询计划[1]。
本文的研究集中在查询计划生成的树形枚举、表排列阶段。早期计划生成的研究重点是将所有可行计划罗列出来,但是当参与查询的表（含索引表）数目过多时“搜索空间巨大”,导致数据库不能忍受优化器消耗的时间时,查询计划生成的研究开始转到尽量减小搜索计划空间的方向上来。例如,对于涉及n个表的查询语句,仅其连接树形有 C 2 n - 2 n - 1 n 种,每种连接树形又对应n!个表排列,故查询计划的枚举空间为上述两值的乘积。在如此巨大的枚举空间中,如何引入一些启发式规则、排除一些不可执行的查询计划,以减轻后续代价评估阶段的系统开销是值得研究的问题。
近年来,国内外在空间索引[2-5]、查询算法优化[6-11]、查询代价估算[12-15]等领域有一定的进展,但有关空间查询计划启发式策略的研究较少。这主要是因为空间查询计划生成与数据库系统内核的相关理论和代码关系密切,研究难度较大。本文在开源Ingres代码的基础上,针对查询优化的树形枚举、表排列两个阶段,结合空间数据类型、空间操作的特殊性,提出了一些生成空间查询计划的启发式策略,用于减少查询计划的搜索空间、减少参与运算的空间数据量,从而提高查询计划的执行效率。

2 查询计划树枚举阶段的一些基本概念和限定

查询图和连接树是数据库查询计划枚举阶段2个重要的概念。查询计划枚举的首要任务就是根据各表之间的连接关系（查询图）生成初步的查询计划（连接树）。

2.1 查询图

查询图中各节点表示查询语句涉及的关系R1,…,Rn,节点间的连接线则表示两端节点表间的连接谓词。查询图是包含R1,…,Rn的无向图,理论上包括链状、星状、树状、环状以及团状几种不同的类型,如图1所示。系统通常选用查询图中直接相连的两表参与连接。如果选择了查询图中不直接相连的表参与连接,则只能采用笛卡尔连接生成结果,即需要对两个表中所有记录一一连接,故算法复杂度大。查询图虽然给出了查询计划中所有可能的连接,但并不决定连接执行的顺序。
Fig. 1 Demonstration of query graph

图1 查询图的形状示意

2.2 连接树

连接树是数据库的内部连接顺序的一种表达形式,其作为逻辑和物理优化的基础,将直接决定查询计划的搜索空间。连接树主要有左深树、右深树、锯齿树、浓密树4种树形（图2）,但是将搜索空间严格限制为左深树。由于左深树与右深树执行过程相同,因此视为同一类树形。采用左深树有2个优势：① 在任一查询时刻,只有一个中间结果;② 基于左深树的表排列组合远远小于浓密树、锯齿树的表排列组合,从而极大地减小了计划搜索空间。因此,本文主要讨论基于左深树的查询计划。
Fig. 2 Different types of join tree

图2 连接树的类型

连接树通常可用一串数字表示。这串数字的第一个数值表示该树形具有的叶子数目,然后,按照广度优先的原则遍历整个连接树,并依次记录经历各节点的左右子节点包含的叶节点数目。例如,对于图3（a）所示的树形可以被标识为4312111,其中,4表示整颗树叶子节点的个数为4,3表示根节点左子节点下叶子节点的个数为3,其后的1表示根节点右子节点下的叶子点的个数为1,按广度遍历的原则依次类推。
Fig. 3 An example of join tree shape and one of its query plan

图3 连接树形与查询计划

另外,对于随机生成的表排列R2 R3 R0 R1,赋于图3（a）后,其生成的左深树连接计划如图3（b）所示。

3 空间启发式策略

空间启发式策略就是针对空间数据类型、空间操作的特殊性,为缩小查询计划的搜索空间、减少参与运算的空间数据量而制定的一系列策略。这些策略可以引导查询计划枚举向最（较）优的方向发展,提高系统执行效率。

3.1 空间等价类与空间约束对的规则

空间关系谓词是空间查询中最为常用的连接谓词,包括相等（Equals）、相离（Disjoint）、相交（Intersects）、相接（Touches）、跨越（Crosses）、包含（Within）、被包含（Contains）、交叠（Overlaps）[16]等。其中,仅Equals符合等价关系的定义[13],可用等价类的启发式规则。而其它空间谓词均不符合等价关系自反性、对称性和传递性的要求[17]。例如,Disjoint、Touches、Overlaps、Crosses不具备自反性和传递性,Within、Contains则不具备上述任一特性。将非等值空间谓词连接的属性定义为“空间约束对”,详细定义见文献[18]。空间等价类与空间约束对的启发式规则如下：
（1） 规则①：连接树的空间连接关系应建立在空间等价类、空间约束对之上。若连接关系不建立在空间等价类或空间约束对上,则只能采用笛卡尔积生成结果,此时不仅执行代价会较大,而且连接结果集也相当大,导致参与后续操作的数据量大,查询效率低。
（2） 规则②：自下而上,查询计划树中各类连接关系的放置顺序是非空间等价类、空间等价类、非笛卡尔积的属性连接对、空间约束对、笛卡尔积的属性约束对。本规则是按上述操作执行结果集从少到多、执行代价从低到高的顺序排列的。非空间等价类的连接结果集通常是最少的、而且执行代价较低,因此通常建议将其放在查询树的下端（第1位）先执行,空间等价类的连接结果集也很少,但其CPU代价略高于非空间等价类,故通常排在第2位执行。非笛卡尔积的属性对连接与空间约束对在连接结果集方面难以区分多少,但空间约束对的CPU代价明显高于非笛卡尔积的属性对连接操作,故非笛卡尔积的属性连接对、空间约束对分别排在第3位、第4位执行。尽管笛卡尔积的属性约束对的CPU代价不高,但若把它放置查询计划树的底端,其连接结果集往往非常大,将极大增加了后续操作的时间复杂度,故常常把它放在查询计划树的上端（最后）执行。
（3） 规则③：由于空间等价类的递推性,规则①的空间连接关系还可以建立在与某属性互为空间等价类的两属性上。例如,在T1.a1ST_EqualsT2.a2 and T2.a2ST_EqualsT3.a3的连接条件中,SQL语句显式地给出T1.a1和T2.a2、T2.a2和T3.a3是空间等价类,因此,可直接建立连接关系。由于等价类的传递性（即A⇔B、B⇔C,则A⇔C）,T1.a1和T3.a3也是空间 等价类,它们之间也可以进行连接。特别是当T1.a1ST_EqualsT3.a3的执行结果集较少时,先执行T1.a1和T3.a3之间的连接效率更高。

3.2 空间索引的放置规则

空间索引是加快空间查询执行速度的另一个利器。在空间数据库中,若存在空间索引、且SQL语句使用了空间拓扑关系谓词或几何对象列,则空间索引很可能会加入计划树中。在查询计划搜索中,空间索引树的放置通常应该遵守规则④和规则⑤。
（1）规则④：若查询语句中的空间谓词仅涉及到图形列的MBR,则可使用该空间表的索引表替代该表,即空间索引替换。因为空间索引的KEY列已经存储了图形的MBR信息。在执行阶段,基于空间索引的访问可以有效降低I/O次数,降低查询消耗的时间。
（2）规则⑤：若主空间表及其空间索引表同时出现在查询计划中,则其空间索引表不能出现在该表的连接操作之后,且索引表的连接结果必须与该表再进行空间元组号（Tuple ID,TID）连接,即以空间索引表为查询入口,根据索引中记录的TID查找原空间数据表记录的连接过程。若存在2个空间表T1、T2,其空间索引分别为I1、I2,图4则示出了几种符合该规则的表放置情况。图5给出了违反规则②的几种放置情况。在图5（a）中,第一步已经完成了T1和T2的精确连接,如果再与粗略的I1进行连接,该操作就失去了意义;在图5（b）和（c）中,空间表T1在经过投影-约束、连接操作后,就失去了TID信息,就无法实现与其索引I1进行关联。图中的“б”表示数据库中的选择操作,“п”表示数据库中的投影操作;“×”表示数据库中的连接操作,“×”后括号内的字符表示该连接类型。图中dicar表示笛卡尔连接;TID表示TID连接;Key表示Key连接,即2个空间表之间按某种空间算子进行关联的连接方法。
Fig. 4 Legal location of I1

图4 合法的I1位置

Fig. 5 Distribution of outliers detected by combined method

图5 联合校验异常点分布

4 启发式策略在缩小计划搜索空间 方面的作用

以某市某区的社区数据、公司数据以及建筑物数据的查询为例,展示空间启发式规则在缩小计划搜索空间方面的作用。查询语句如下：
select count(*)
from HDcompanies, HDbuiltups, HDcommunities
where HDcompanies.a04= HDbuiltups.ca_id
and HDcommunities.shape st_intersects HDbuiltups.Shape
其中,HDcommunities表为社区多边形数据,字段为fid、shape等;HDcompanies为公司点数据,字段为fid、shape、a04等;HDbuiltups表为建筑物多边形数据,字段为fid、shape、ca_id等;spidx_HDcommunities为HDcommunities表的索引表。
以图3（a）所示的节点数为4的左深树为例,若用R0、R1、R2、R3分别代替HDcompanies表、HDbuiltups表、HDcommunities表、spidx_HDcommunities表,则用穷举法,4个表有24种表排列,图5列出的所有可能的执行计划（共24种）。由于R0的a04字段和R1的ca_id字段互为非空间等价类,R1的shape字段和R2的shape字段、R2的shape字段和R3的MBR字段是空间约束对,而R0和R2、R0和R3之间不存空间等价类或空间约束对关系,故计划中R0与R2、R0与R3不应同时在同一层的叶节点上（参见规则①）,故图6中（c）-（f）、（m）、（n）、（s）和（t）的查询计划应该被淘汰。另外,由于R3是R2的空间索引,根据规则⑤,索引R3不应该出现在基表R2之上,故图6（a）、（g）、（i）和（j）的查询计划也应该将被淘汰。经上述启发式规则作用后,图6中剩下的可用计划仅有12个。淘汰计划超过了全计划的一半,极大减少了需要评估的查询计划数,提高了空间查询效率。
Fig. 6 All query plans of tree shape in Fig. 3 (a)

图6 图3（a）所示树形对应的所有查询计划

5 结论

针对空间等价类、空间约束对等概念和空间索引关键技术,提出了建立空间连接的相关规则以及放置空间索引的相关规则,这些规则可以减少参与运算的中间结果集、排除诸多不可行的查询计划,对减轻后续代价评估阶段的系统开销有重要意义。本文给出的规则有较高的通用性,不仅可以加入于空间查询优化器中,也可按这些规则编写空间查询语言,对提高空间数据库的查询效率有重要意义。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
王珊. 数据库系统概论(第四版)[M].北京:高等教育出版社,2008.

[Wang S.Introduction to database system (fourth edition)[M]. Beijing: Higher Education Press, 2008. ]

[2]
吴明光. 一种空间分布模式驱动的空间索引[J].测绘学报,2015,44(1):108-115.支持批量操作的空间索引中,空间数据的分解粒度、局部更新操作的整体影响处理是两个主要难点.本文基于空间分布模式分析,提出了一种空间索引—— Pattern-tree.针对批量操作的粒度问题,设计了一种基于空间分布模式探测的空间划分方法,采用一种自上而下与自下而上相结合的索引树构建算法;针对局部插入操作对索引树的整体影响与索引树的调整问题,提出了一种基于空间分布模式变化检测的索引更新方法.试验表明,本文所提出的空间索引结构比STLT、GBI以及SCB等方法具有更高的构建与窗口查询效率.

DOI

[Wu M G.A spatial distribution pattern-driven spatial index[J]. ActaGeodaetica et Cartographica Sinica, 2015,44(1):108-115. ]

[3]
龚俊,朱庆,张叶廷等.顾及多细节层次的三维R树索引扩展方法[J].测绘学报,2011,4(2):249-255.多细节层次表达是三维GIS的重要特征之一。为提高细节层次模型的管理效率，本文提出一种扩展多细节层次功能的三维R树索引方法，通过全局优化和三维聚类分析建立动态三维R树索引，研制了先自下而上、后自上而下全局搜索的节点选择算法和基于k-medoids聚类算法的节点分裂算法，保证节点尺寸均匀、形状规则以及重叠减少。基于良好的三维树形结构，本文扩展了传统的三维R树索引结构，实现R树索引和细节层次模型的无缝集成。为验证本文方法的有效性，通过仿真实验，结果证明了本文方法能很大程度地提升多细节层次三维城市模型数据库的空间查询效率，具有较好的应用前景和实用价值。

[Gong J, Zhu Q, Zhang Y T, et al.An efficient 3D R-tree extension method concerned with levels of detail[J]. ActaGeodaetica et Cartographica Sinica, 2011,4(2):249-255. ]

[4]
花杰,邢廷炎,芮小平.一种适合多源地球物理数据三维可视化的快速空间索引技术[J].地球物理学进展,2013,28(3):1626-1636.识别复杂地质条件下的地质构造,常需要融合多种地球物理探测技术的数据进行分析,应用地球物理数据三维可视化技术可以更好地解释复杂的地质现象,传统的可视化方法由于缺乏对多源地球物理数据一体化的存储管理与索引机制,使得在对大范围多源地球物理数据进行空间局部更加精细可视化时的效率很低.为了更有效地洞察研究区域的地下构造,本文研究了适合多源地球物理数据三维可视化技术的快速空间索引技术.首先根据各类地球物理数据空间分布特点,提出了一种改进的四叉树结构,用于建立对多源地球物理数据一体化存储与管理.接着利用该数据结构,文章现实了多源地球物理数据快速空间查询的机制.将此结构和机制服务于大规模多源地球物理数据精细尺度下的三维可视化,提高对特定空间范围的局部多源地球物理数据动态可视化的效率.最后给出了该数据结构下空间查询与可视化的效率分析,并通过实验对整个算法的效率进行了验证.实验表明,通过建立相应的索引机制,可在大规模多源地球物理数据条件下更高效地展示任意位置岩矿石多个物理特性之间的空间关系,为多源地球物理数据的三维可视化提供技术支撑.

DOI

[Hua J, Xing T Y, Rui X P.A fast spatial index method for 3D-visulization of multi-source geophysical data[J]. Progress in Geophysics, 2013,28(3):1626-1636. ]

[5]
Gilberto Gutiérrez, José R. Paramá, Nieves Brisaboa, et al.The largest empty rectangle containing only a query object in Spatial Databases[J]. GeoInformatica, 2014,18(2):193-228.Let S be a set of n points in a fixed axis-parallel rectangle , i.e. in the two-dimensional space (2D). Assuming that those points are stored in an R-tree, this paper presents several algorithms for finding the empty rectangle in R with the largest area, sides parallel to the axes of the space, and containing only a query point q. This point can not be part of S, that is, it is not stored in the R-tree. All algorithms follow the basic idea of discarding part of the points of S, in such a way that the problem can be solved only considering the remaining points. As a consequence, the algorithms only have to access a very small portion of the nodes (disk blocks) of the R-tree, saving main memory resources and computation time. We provide formal proofs of the correctness of our algorithms and, in order to evaluate the performance of the algorithms, we run an extensive set of experiments using synthetic and real data. The results have demonstrated the efficiency and scalability of our algorithms for different dataset configurations.

DOI

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

[Huang T, Zhang F.Improved cost model for spatial joins using R-trees[J]. Computer Engineering and Design, 2009,30(7):1691-1693. ]

[7]
付仲良,刘思远,俞志强.一种双映射变换的空间索引及空间连接算法研究[J].武汉大学学报·信息科学版,2014,39(10):1248-1251.空间索引会极大地影响空间连接操作的效率.提出了一种基于双映射变换的分布式空间索引,通过结合平面角变换和空间填充曲线的优点,对二维空间进行两次维度变换,使空间数据分片建立在一维的顺序存储队列基础上.在此基础上提出了一种空间拓扑连接算法,并进行了算法的四叉树优化和处理效率实验,对比了本文存储方法和传统R-tree存储在时效性和冗余度方面的效率.实验结果表明,本文方法能支持高效的空间连接.

DOI

[Fu Z L, Liu S Y, Yu Z Q.A novel spatial index with a high-performance spatial join[J]. Geomatics and Information Science of Wuhan University, 2014,39(10):1248-1251. ]

[8]
Fabio Gomes de Andrade, Cláudio de Souza Baptista, Clodoveu Augusto Davis Jr. Improving geographic information retrieval in spatial data infrastructures[J]. GeoInformatica, 2014,18(4):793-818.In recent years, spatial data infrastructures (SDIs) have gained great popularity as a solution to facilitate interoperable access to geospatial data offered by different agencies. In order to enhance the data retrieval process, current infrastructures usually offer a catalog service. Nevertheless, such catalog services still have important limitations that make it difficult for users to find the geospatial data that they are interested in. Some current catalog drawbacks include the use of a single record to describe all the feature types offered by a service, the lack of formal means to describe the semantics of the underlying data, and the lack of an effective ranking metric to organize the results retrieved from a query. Aiming to overcome these limitations, this article proposes SESDI (Semantically-Enabled Spatial Data Infrastructures), which is framework that reuses techniques of classic information retrieval to improve geographic data retrieval in a SDI. Moreover, the framework proposes several ranking metrics to solve spatial, semantic, temporal and multidimensional queries.

DOI

[9]
Zhu Y Q, Hua L.Optimization of RDF link traversal based query execution[J]. Journal of Southeast University(English Edition), 2013,29(1):27-32.Aiming at the problem that only some types of SPARQL (simple protocal and resource description framework query language) queries can be answered by using the current resource description framework link traversal based query execution (RDF-LTE) approach, this paper discusses how the execution order of the triple pattern affects the query results and cost based on concrete SPARQL queries, and analyzes two properties of the web of linked data, missing backward links and missing contingency solution. Then three heuristic principles for logic query plan optimization, namely, the filtered basic graph pattern(FBGP) principle, the triple pattern chain principle and the seed URIs principle, are proposed. The three principles contribute to decrease the intermediate solutions and increase the types of queries that can be answered. The effectiveness and feasibility of the proposed approach is evaluated. The experimental results show that more query results can be returned with less cost, thus enabling users to develop the full potential of the web of linked data.

DOI

[10]
张舜,邓亚丹,钟志农.一种基于访问图优化的缓存替换算法[J].计算机应用与软件,2010,27(9):46-48.针对目前数据库缓存替换算法替换策略单一,无法预测即将执行 SQL语句的不足,提出了一种基于访问图优先的缓存替换算法CG-ABR(Call Graph Optimizing Adaptive Buffer Replacement).该算法通过查询优化器获得当前数据访问类型,自动调整缓存替换算法以适应实时变化的访问类型,改进了缓存访问的管理方法,并根 据SQL语句的应用逻辑执行顺序来构造访问图Call Graph,基于Call Graph以预测将要执行的SQL语句,替换出未来不会被访问的页面缓存,以达到缓存空间优化的目的.实验结果与分析表明,CG-ABR算法是有效的,对 实时变化的访问类型有较好的缓存命中率,具有良好的应用价值.

DOI

[Zhang S, Deng Y D, Zhong Z N.A buffer replacement algorithm based on call graph optmisation[J]. Computer Applications and Software, 2010,27(9):46-48. ]

[11]
赫高进,熊伟,陈荦,等.基于MPI的大规模遥感影像金字塔并行构建方法[J].地球信息科学学报,2015,17(5):515-522.lt;p>影像金字塔是实现影像数据多分辨率组织的重要方式,是提高影像可视化性能的有效手段。传统串行金字塔构建算法,对大规模影像数据的构建性能已无法满足遥感影像快速浏览的预处理需求。故此,其成为一个亟待解决的问题,而利用多核、多节点的高性能集群计算环境和并行机制是一个重要的技术途径。本文在共享外存的高性能集群环境下,提出使用消息传递接口(MPI)的金字塔并行构建算法,对构建遥感影像金字塔过程中的重采样与I/O 过程进行并行处理,大大缩短了遥感影像金字塔构建时间。实验结果表明:(1)该算法比传统串行构建方法的加速效果明显,对于单波段遥感影像,其加速效果可达到GDAL的5 倍以上,而对于多波段遥感影像,加速效果可达到GDAL的2 倍以上;(2)遥感影像数据量越大,并行构建算法加速效果越显著,对于大规模的遥感影像,本文提出的金字塔并行构建算法的速度可达到GDAL的10 倍左右。</p>

DOI

[He G J, Xiong W, Chen L, et al.An mpi-based parallel pyramid building algorithm for large-scale RS Image[J]. Journal of Geo-information Science, 2015,17(5):515-522. ]

[12]
朱焰炉,程昌秀,陈荣国,等. 基于直方图的空间查询选择率估计研究[J].计算机科学,2010,37(12):125-148.

[Zhu Y L, Cheng C X, Chen R G, et al.Selectivity estimation for spatial query based on histogram[J]. Computer science, 2010,37(12):125-148. ]

[13]
陈海珠. 基于闭欧拉直方图的空间查询代价模型[J].软件,2013,34(6):61-64.欧拉直方图是空间查询代价估算 的一种简便而有效的方法。有许多的研究基于这种方法。但是欧拉直方图对空间对象的统计存在计数错误的问题,以MBR近似描述二维空间对象,文[1]提出了 闭欧拉直方图并证明了其统计方法的正确性。文[2]以简单凸多边形近似描述二维空间对象,证明了闭欧拉直方图和欧拉公式同样适用于估算在此描述上的空间选 择代价。基于简单多边形的近似描述,改进原有的计数方法,可进一步扩展闭欧拉直方图的使用范围。此外,本文给出了该代价模型的一个应用。

DOI

[Chen H Z.The cost model of spatial queries based on closed eulerhistogram[J]. Soft ware, 2013,34(6):61-64. ]

[14]
李博涵,秦小麟,陈逸菲等.基于PQR-tree的空间查询代价模型[J].计算机工程与科学,2012,34(5):161-167.lt;p>空间信息处理和地理信息系统等领域的数据管理涉及到海量、高维空间数据对象的处理。本文针对传统数据索引结构在处理这类空间数据时所存在的内存使用过大、I/O消耗过多等问题，通过改进选择查询的代价模型，给出了基于PQRtree的查询和代价模型，以提高空间数据查询的性能。提出了基于PQRtree的三阶段并行查询的方法，分别在任务创建、分配、执行阶段进行优化。提出在任务创建和任务分配阶段应用于空间查询中过滤和精炼阶段的有效算法。测试表明，本文算法在处理各种不同分布类型数据集过程中有效降低了空间数据处理对时间和空间的代价和需求，并且并行机制下的代价模型在预测和评估方面也具有较好的精确度。</p>

DOI

[Li B H, Qin X L, Chen Y F, et al.A cost model for spatial queries based on PQR-tree[J]. Computer Engineering&Science, 2012,34(5):161-167. ]

[15]
颜勋,陈荣国,程昌秀,等.内嵌式空间数据库优化器代价评估框架及实现[J].武汉大学学报·信息科学版,2011,36(6):726-730.

[Yan X, Chen R G, Cheng C X, et al.Optimizer cost estimation framework and implementation for spatially-enabled database[J]. Geomatics and Information Science of Wuhan University, 2011,36(6):726-730. ]

[16]
郭庆胜,杜晓初,刘浩.空间拓扑关系定量描述与抽象方法研究[J].测绘学报,2005,34(2):123-128.具有复杂形状的空间区域之间拓扑关系的表示与抽象是空间信息多尺度表达和可视化中必须解决的问题。本文讨论区域之间拓扑关系边界交集成分的定性描述方法，并在此基础上提出度量化边界交集成分描述方法，运用这种详细的描述方法，探讨空间区域之间拓扑关系抽象的规律，可为地图自动综合中空间关系的维护提供有关的理论基础。

DOI

[Guo Q S, Du X C, Liu H.Research on quantitative representation and abstraction of spatial topolpgical relation between two regions[J]. ActaGeodaetica et CartographicaSinica, 2005,34(2):123-128. ]

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

[Zuo X L, Li W J, Liu Y C.Discrete mathematics[M]. Shanghai: Shanghai Scientific&Technical Publishers,1982. ]

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

DOI

[Cheng C X, Yang S L, Song X M, et al.Concept of spatial constrained pairs and its implementation[J]. Journal of Geo-information Science, 2015,17(9):1009-1013. ]

Options
Outlines

/

〈 〉