基于参数化直方图的三路互相交连接选择性估计  

Selectivity Estimation of 3-Way Clique Intersect Joins Based on Parameterized Histograms

作　　者：张巨[1] 肖予钦[1] 熊伟[1] 景宁[1] 

机构地区：[1]国防科技大学电子科学与工程学院,湖南长沙410073

出　　处：《国防科技大学学报》2004年第1期24-28,共5页Journal of National University of Defense Technology

基　　金：国家高技术研究发展计划基金资助项目(2002AA131010;2002AA134010;2002AA134012;2002AA134020)

摘　　要：估计空间算子的选择性是设计空间查询优化器的关键技术之一。选择性估计不仅能以非常小的代价给出空间算子结果集大小的近似估计,而且也可以直接用于某些仅需要近似结果的空间查询和空间分析(如数据集间的相关性评价等)处理。互相交连接是一类常见而且具有特殊性质的多路空间连接。基于对命题"两两相交的多个矩形一定有一个公共的相交区域,而且这个区域也是矩形"的证明,提出了一种可以用于三路互相交连接选择性估计的参数化直方图方法,还通过多组比较实验证明了该方法的有效性和适应性。Selectivity estimation is crucial in a query optimizer for choosing a good execution plan for a given query. Selectivity estimates of spatial joins can be used as responses to the specialized user queries that seek approximate figures. Spatial join selectivity can also be used for evaluating the correlation between data sets. With the proof that mutually overlapped rectangles are sharing a common region which is also a rectangle, this paper gives a selectivity estimation technique for 3-way clique intersect joins. The efficiency of our algorithm has been validated by using synthesized and real-world data sets.

关 键 词：选择性估计 互相交连接 参数化直方图 空间查询优化器 空间算子 空间数据库管理系统 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]