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

基于最小生成树的数据流窗口连接优化算法 被引量：3

A Window Join Optimization Algorithm Based on Minimum Spanning Tree
在线阅读 下载PDF
导出
摘要 与传统关系数据库不同,数据流管理系统主要处理并发的连续查询.由于查询可能随时增删,所以其主要关注适合查询增删的并发连续查询优化,而不是单条查询优化.提出适合频繁增删查询环境下的数据流窗口连接优化算法.对于新注册的查询以类似最小生成树算法写出数据流的探测序列,然后在不更改其他查询探测序列顺序的情况下尽量合并,减少重复计算.注册或删除查询并不影响其他的查询计划,不需要执行繁琐的查询计划迁移.理论分析和实验证明,该算法简单,优化性能在可接受的范围内,尤其适合查询更新频率较高的系统. Different from traditional database systems, a data stream management system （DSMS） mainly processes concurrently continuous queries. Because queries would be added or deleted at any moment, the focus of query optimization for a DSMS is to find an algorithm that adapts to add and delete queries frequently. Furthermore, as window join is one of the highest cost operations of continuous queries, window join optimization will notably improve a DSMS performance. Therefore, a window join optimization algorithm is proposed. For each new query, all the probing sequences of each data stream are built like minimum spanning tree algorithm. To complete concurrent window joins, the probing sequences which start from a same stream should be built into one tree whose root node is the stream. If prefixes of probing sequences are the same, they can be grouped into one branch of the tree to reduce the duplicate calculation. Because the algorithm does not execute cost comparison of grouping common join predicate, adding or deleting a query does not influence other query not needed. Theoretics and experimental results show performance is acceptable. plans, and complicated dynamic plan migration is that the algorithm is simple and optimization
作者 钱江波 徐宏炳 董逸生 王永利 刘学军 杨雪梅
机构地区 宁波大学信息科学与工程学院 东南大学计算机科学与工程学院
出处 《计算机研究与发展》 EI CSCD 北大核心 2007年第6期1000-1007,共8页 Journal of Computer Research and Development
基金 江苏省高技术基金项目(BG2004034) 江苏省2004年度研究生创新计划基金项目(xm04-36)~~
关键词 窗口连接 多查询优化 最小生成树 连续查询 window join multiple query optimization minimum spanning tree continuous query
分类号 TP311.13 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献12

  • 1T K Sellis.Multiple query optimization[J].ACM Trans on Database Systems,1988,13(1):23-52
  • 2P Roy,S Seshadri,S Sudarshan,et al.Efficient and extensible algorithms for multi query optimization[C].In:Proc of ACM SIGMOD 2000.New York:ACM Press.2000.249-260
  • 3J Chen,D Dewitt.dynamic re-grouping of continuous queries[C].In:Proc of the 28th VLDB.San Fransisco:Morgan Kaufmann,2002.430-441
  • 4Y Zhu,E Rundensteiner,G Heineman.Dynamic plan migration for continuous queries over data streams[C].In:Proc of ACM SIGMOD 2004.New York:ACM Press,2004.431-442
  • 5A N Wilschut,P Apers.Dataflow query execution in a parallel main-memory environment[C].In:PDIS.Los Alamitos:IEEE Computer Society Press.1991.68-77
  • 6V Raman,A Deshpande,J M Hellerstein.Using state modules for adaptive query processing[C].In:Proc of the 19th Int'l Conf on Data Engineering(ICDE).Los Alamitos:IEEE Computer Society Press,2003.353-364
  • 7J Kang,J F Naughton,S Viglas.Evaluating window joins over unbounded streams[C].In:Proc of the 19th Int'l Conf on Data Engineering(IcDE).Los Alamitos:IEEE Computer Society Press,2003.341-352
  • 8L Golab,M T Ozsu.Processing sliding window multi-joins in continuous queries over data streams[C].In:Proc of the 29th Int'l Conf on VLDB.San Fransisco:Morgan Kaufmann,2003.500-511
  • 9S Viglas,J F Naughton,J Burger.Maximizing the output rate of multi-way join queries over streaming information sources[C].In:Proc of the 29th Int'l Conf on VLDB.San Fransisco:Morgan Kaufmann,2003.285-296
  • 10S Viglas,J F Naughton.Rate-based query optimization for streaming information sources[C].In:Proc of ACM SIGMOD 2002.New York:ACM Press,2002.37-48

二级参考文献13

  • 1B. Babcock, S. Babu, M. Datar, etal. Models and issues in data streams. In: Proc. ACM Symp on Principles of Database Systems. New York: ACM Press, 2002. 1～16.
  • 2S. Chandrasekaran, O. Cooper, A. Deshpande, et al.TelegraphCQ: Continuous dataflow processing for an uncertain world. The 1st Biennial CIDR, Asilomar, 2003.
  • 3D. Carney, U. Cetinternel, M. Cherniack, et al. Monitoring streams-A new class of data management applications. In: Proc.28th Int'l Conf. VLDB. San Fransisco: Morgan Kaufmann,2002. 215～226.
  • 4R. Motwani, J. Widom, A. Arasu, et al. Query processing,approximation, and resource management in a data stream management system. The 1st Biennial CIDR, Asilomar, 2003.
  • 5A.N. Wilschut, P. M. G. Apers. Dataflow query execution in a parallel main-memory environment. Distributed and Parallel Databases, 1993, 1(1): 103～128.
  • 6T. Urhan, M. J. Franklin. XJoin: A reactively-scheduled pipelined join operator. IEEE Data Engineering Bulletin, 2000,23(2): 27～33.
  • 7V. Raman, A. Deshpande, J. M Hellerstein. Using state modules for adaptive query processing. In: Proc. 19th Int' l Conf.Data Engineering(ICDE). Los Alamitos: IEEE Computer Society Press, 2003. 353～364.
  • 8R. A vnur, J. M. Hellerstein. Eddies: Continuously adaptive query processing. In: Proc. ACM SIGMOD Int'l Conf.Management of Data. New York: ACM Press, 2000. 261～272.
  • 9L. Golab, M. T. Ozsu. Processing sliding window multi-joins in continuous queries over data streams. In: Proc. 29th Int'l Conf.VLDB. San Fransisco: Morgan Kaufmann, 2003. 500～511.
  • 10S. Madden, M. Shah, J. M. Hellerstein, et al. Continuously adaptive continuous queries over streams. In: Proc. ACM SIGMOD Int'l Conf. Management of Data. New York: ACM Press, 2002. 49～61.

共引文献9

同被引文献48

  • 1杨宜东,孙志挥,张净.基于核密度估计的分布数据流离群点检测[J].计算机研究与发展,2005,42(9):1498-1504. 被引量：9
  • 2钱江波,徐宏炳,董逸生,刘学军,王永利,杨雪梅.共享连接结果的连续查询处理[J].东南大学学报（自然科学版）,2007,37(1):5-8. 被引量：1
  • 3Gedik B, Wu K, Yu P S, et al. GRUBJOIN:An adaptive multiway windowed stream join with time correlation-aware CPU load shedding[J]. Transactions on Knowledge and Data Engineering, 2007,19(10) : 1363 - 1380.
  • 4Yin X, Han J, Yang J, et al. CrossMine: efficient classification across multiple database relations[C]. Proc. of the 20th International Conference on Data Engineering, Boston, 2004.
  • 5Atramentov A, Leiva H, Honavar V. A multi-relational decision tree learning algorithm-implementation and experiments [C]. Proc. of lLP, Szeged, Hungary, 2003.
  • 6Sourc forge research data[OL], http://www. nd. edu/-oss/ Data/data. html,2002.
  • 7Han J, Kamber M. Data mining:concepts and techniques[M]. San Francisco : Morgan Kau fmann , 2000.
  • 8Babcock B, Babu S, Datar M, et al. Models and issues in data stream systems[C]. Proc. of the 21th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. Wisconsin : Madison, 2002 : 1 - 16.
  • 9Gaber M M, Zaslavsky A, Krishnaswamy S. Mining data streams : A review[J]. ACM SIGMOD Record, 2005, 34 (2) : 18 - 26.
  • 10Garofalakis M N, Gehrke J, Rastogi R. Querying and mining data streams:you only get one look[C]. Proc. of the 28th Int. Conf. on Very Large Data Bases, Hong Kong, 2002.

引证文献3

二级引证文献42

计算机研究与发展
2007年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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