实体数据库中多相似连接顺序选择策略  

Multi-Similarity Join Order Selection in Entity Database

作　　者：刘雪莉[1] 王宏志[1] 李建中[1] 高宏[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机科学与探索》2012年第10期865-876,共12页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金 Nos.61003046;61033015;61133002;国家重点基础研究发展规划(973) No.2010CB316200;高等学校博士学科点专项科研基金 No.20102302120054;中央高校基本科研业务费专项资金 No.2013064;RSE-NSFC交流项目 No.61111130189~~

摘　　要：按照元组描述的实体对其进行组织和查询处理是一种管理劣质数据的有效方法。考虑到同一个实体的同一属性存在多个描述值,因此基于实体的数据库上的连接是支持多个值的相似性连接。由于多表连接操作的连接顺序对连接性能有着重要的影响,研究了实体数据库上多表连接顺序选择方法,采用基于实体的马尔可夫链蒙特卡洛(Markov chain Monte Carol,MCMC)方法估计出实体数据库的相似性连接操作的结果大小,并以连接结果大小和有无索引作为主要代价,提出了基于实体的多连接顺序优化策略。进一步,通过实验证明了估计连接结果大小的算法在大规模数据上有着显著的优势。To organize and query entities described by relational tuples is an effective way to manage poor-quality data. Taking into account that the attribute of an entity has more than one description, the similarity join based on entity must consider multiple values. Due to importance effect to the join efficiency of multi-join order, this paper proposes a multi-join order selection algorithm which based on Markov chain Monte Carol （MCMC） method to estimate the size of entity similarity join, and raises a cost model to optimize the order of multi-relation of entity on join problem. Moreover, experimental results show that the estimating algorithm has good performance especially when the size of relations is large.

关 键 词：多连接 实体 相似连接 马尔可夫链蒙特卡洛(MCMC) 

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