【作者】 王永刚；

【导师】 王立松；

【作者基本信息】 南京航空航天大学 ， 计算机软件与理论， 2012， 硕士

【摘要】 目前无线传感器网络、网络流量监控、金融应用、通信数据管理等应用中处理的数据不再是存储在存储介质中的静态数据，而是实时、连续到达的数据流。与传统的静态数据相比，数据流具有无界、连续到达、数据动态变化等特点，所以传统的对静态数据的查询处理技术并不适用于对数据流数据的查询处理。由于对数据流的查询是长期、连续进行的，并且在查询过程中数据流的数据特性是多变的，所以数据流上的自适应查询处理是对数据流管理系统的重大挑战。目前，数据流自适应查询处理的研究中，最重要的成果是一个称为Eddy的自适应查询处理机制。它是一种基于路由的自适应查询处理技术，其核心是进行自适应路由调度的路由调度策略。但Eddy的主要不足在于：当前基于谓词独立性假设的路由策略在谓词相关的情况下，计算得到的路由可能是一个糟糕的查询计划，导致查询效率低下；当前的批处理路由调度策略的适应粒度为一个固定值K，如果K值取值不当，就会引入不必要的开销而降低查询效率。针对Eddy的这些缺陷，本文进行了研究和改进，主要工作包括以下几个方面：（1）研究了数据流的自适应查询处理方法，指出Eddy自适应查询处理机制中的不足；（2）针对Eddy当前基于谓词独立性假设的路由策略不能很好地处理查询谓词相关情况的数据流查询处理，提出了一种面向谓词相关的路由调度策略——自适应贪婪路由策略。该策略把谓词之间的相关性纳入考虑范围，在谓词相关的情况下，计算得到的路由更加接近实际的最佳路由。相关实验表明在谓词相关的情况下，本文设计的路由策略是有效的；（3）Eddy中的批处理路由策略的适应粒度为一个固定值K，如果K取值不当，会导致Eddy重复计算同一路由，从而产生不必要的开销并降低查询效率。本文对批处理路由策略进行了改进，使其能够获取数据流数据特性的变化，并自适应地调整适应粒度，确保无论数据流数据特性如何变化，都能获得较好的查询效率。相关实验结果和分析表明，这一改进策略是有效的。更多还原

【Abstract】 At present, in the fields of wireless sensor networks, network traffic monitoring, financialapplications, and communications data management and so on, data being processed is no longer thestatic data stored in the storage media, but data streams which real-time, continuouslyarrive. Compared with the traditional static data, data streams have the characteristics of unbounded,continuous arrival and dynamic changes, etc., so the traditional query processing technology of staticdata does not competent the query processing of data streams. Because of the query processing of datastreams is long-term, continuous, and the characteristics of data streams are varied during the query,so how to query the data streams adaptively is a major challenge of data stream management system.Currently, a query processing framework called Eddy is one of the most important researchresults of the adaptive query processing of data streams. Eddy is a route-based adaptive queryprocessing technique, the core of which is the routing policies used to schedule route adaptively. Butfor Eddy the main shortcomings are that the current routing policies based on the assumption thepredicates are independent of each other, but when the predicates are correlated with each other, theroute calculated by the current routing policies may be a bad query plan, resulting in inefficientqueries; and adaptation granularity of the current routing policy with batching is a fixed value K, ifthe value of K is not properly, it will introduce unnecessary overhead and reduce the queryefficiency. In this thesis we have studied and improved these shortcomings of Eddy. The primaryresearch of the thesis as follows:(1) Have a research on the adaptive query processing technology of data streams and point theshortcomings of Eddy;(2) For current routing policies based on the assumption the predicates are independent of eachother can not handle the query processing of data streams in the situation the query predicates arecorrelated well, we advises a routing policy oriented the correlation of the predicates called adaptivegreedy routing policy. This policy takes the correlations among the predicates into consider, so theroute calculated by which is closer to the actual best route in the situation the query predicates arecorrelated. Experiments show that this policy is effective in the situation the query predicates arecorrelated;(3) The adaptation granularity of the routing policy with batching is a fixed value K, if the valueof K chosen is not properly, Maybe Eddy will calculates the same route repeatedly. It will introduce unnecessary overhead and reduce the query efficiency. In this thesis, routing policy with batching hasbeen improved, it can obtain the changed characteristics of the data streams, and adaptively adjust thesize of the adaptation granularity, to ensure that no matter how the characteristics of the data streamschanges, it can provide better query efficiency. Experiments show that the improved routing policy iseffective.更多还原