期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于均衡割的无叉积分区连接算法

A Partition Join Algorithm Based on Balanced Cut Without Cross Products
原文传递
导出
摘要 连接序问题是数据库查询优化中最重要且最具挑战性的问题.传统的动态规划算法通常具有指数级复杂度.基于图形分割的相关理论,提出均衡割分区算法(BCP),通过均衡割将查询图分割成大小相对均衡的分区,避免一次性处理所有连接的关系.BCP算法分区不会产生叉积,并且可以轻易地集成进任何查询优化器中.在Postgre SQL上实现了该算法,并和Postgre SQL现有的分区算法——迭代动态规划算法(IDP)进行对比.实验结果表明:对25个关系以内的随机连接查询,BCP不仅在平均效率上优于IDP算法,而且对分区大小变化也有更好的适应性. Join ordering is the most challenging problems in database query optimization. Ordinary dynamic programming algorithms have exponential computational complexity. In this paper,we propose a balanced- cut partition（ BCP） algorithm based on the graph cut theory,which avoids considering all tables together by cutting the query graph into several balanced partitions. BCP does not generate cross products and can be integrated into any existing query optimizer. It is then realized on Postgre SQL and co MPared with Iterative Dynamic Programming（ IDP） algorithms implemented on Postgre SQL. The experiments of random query show that this algorithm has not only better performance but also more flexibility when partition size changes.
作者 贾连印 章永彬 李孟娟 丁家满 游进国 陈玮
机构地区 昆明理工大学云南省计算机技术应用重点实验室 昆明理工大学信息工程与自动化学院 云南师范大学图书馆
出处 《昆明理工大学学报（自然科学版）》 CAS 2016年第1期52-56,共5页 Journal of Kunming University of Science and Technology(Natural Science)
基金 国家自然科学基金项目(61562054 81360230 51467007 61462050) 云南省人才培养项目(KKSY201303095) 云南省教育厅重点项目(2012Z008)
关键词 查询优化 连接序 均衡割 分区动态规划 叉积 query optimization join ordering balanced cut partition dynamic programming cross product
分类号 TP311 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献17

  • 1Wu Y,Patel J M,Jagadish H V.Structural Join Order Selection for XML Query Optimization[C]//Proceedings of the 19th International Conference on Data Engineering.Los Alamitos,CA,USA:IEEE Computer Society,2003:443-454.
  • 2Neumann T,Weikum G.Scalable join processing on very large RDF graphs[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2009:627-640.
  • 3Gubichev A,Neumann T.Exploiting the query structure for efficient join ordering in SPARQL queries[C]//Proceedings of the17th International Conference on Extending Database Technology.New York,USA:ACM Press,2014:439-450.
  • 4Bornea M A,Dolby J,Kementsietsidis A,et al.Building an efficient RDF store over a relational database[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data.New York,USA:ACM,121-132.
  • 5贾连印,奚建清,李孟娟,游进国,刘勇,苗德成.Dtrie-allpair:高效的集合T-覆盖连接算法[J].华南理工大学学报（自然科学版）,2012,40(6):109-117. 被引量：2
  • 6Ibaraki T,Kameda T.On the optimal nesting order for computing N-relational joins[J].ACM Transactions on Database Systems,1984:482-502.
  • 7Steinbrunn M,Moerkotte G,Kemper A.Heuristic and randomized optimization for the join ordering problem[J].The VLDB Journal,1997,6(3):191-208.
  • 8Selinger P G,Astrahan M M,Chamberlin D D,et al.Access path selection in a relational database management system[C]//Proceedings of the 1979 ACM SIGMOD international conference on Management of data.New York,USA:ACM Press,1979:23-34.
  • 9Moerkotte G,Neumann T.Dynamic programming strikes back[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press.2008:539-552.
  • 10Moerkotte G,Neumann T.Analysis of two existing and on new dynamic programming algorithm for the generation of optimal bushy join trees without cross products[J].VLDB Endowment,2006:930-941.

二级参考文献16

  • 1Chaudhuri S, Ganti V, Kaushik R. A primitive operator for similarity joins in data cleaning [ C ]//Proceedings of the 22nd International Conference on Data Engineering. At- lanta : IEEE Computer Society ,2006:5-16.
  • 2Arasu A, Ganti V, Kaushik R. Efficient exact set-simila- rity joins [ C ] //Proceedings of the 32nd International Conference on Very Large Data Bases. Seoul:ACM Press, 2006:918-929.
  • 3Xiao C, Wang W, Lin X, et al. Efficient similarity joins for near duplicate detection [ C]//Proceedings of the 17th International Conference on World Wide Web. Beijing: ACM Press ,2008 : 131-140.
  • 4Hoad T, Zobel J. Methods for identifying versioned and plagiarized documents [ J ]. Journal of the American So- ciety for Information Science and Technology,2003,54(3): 203-215.
  • 5Li C, Lu J, Lu Y. Efficient merging and filtering algo- rithms for approximate string searches [ C ] //Proceedings of the 24nd International Conference on Data Enginee- ring. Canc6n : IEEE Computer Society, 2008 : 257- 266.
  • 6Helmer S, Moerkotte G. A performance study of four in- dex structures for set-valued attributes of low cardinality [ J]. The International Journal on Very Large Data Bases, 2003,12(3) :244-261.
  • 7Helmer S, Aly R, Neumann T, et al. Indexing set-valued attributes with a multi-level extendible hashing scheme [ C] //Proceedings of the 18th International Conference of Database and Expert Systems Applications. Regensburg: Springer-Verlag, 2007 : 98-108.
  • 8Mamoulis N. Efficient Processing of joins on set-valued at- tributes [ C ] //Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. San Di- ego : ACM Press, 2003 : 157-168.
  • 9Terrovitis M, Passas S, Vassiliadis P, et al. A combination of trie-trees and inverted files for the indexing of set-val- ued attributes [ C] //Proceedings of the 15th ACM Inter- national Conference on Information and Knowledge Man- agement. Arlington : ACM Press ,2006:728-737.
  • 10Hossain S,Jamil H M. A hybrid index structure for set- valued attributes using itemset tree and inverted list [ C ] // Proceedings of the 21st international Conference on Database and Expert Systems Applications. Bilbao:Sprin- ger- Verlag, 2010: 349 - 357.

共引文献1

昆明理工大学学报（自然科学版）
2016年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部