计算机工程与应用 ›› 2006, Vol. 42 ›› Issue (24): 13-.

• 博士论坛 • 上一篇    下一篇

一种自适应的数据预取与缓冲算法

朱鸿宇,刘瑰,唐福华,陈左宁   

  1. 解放军信息工程大学信息工程学院
  • 收稿日期:2006-03-21 修回日期:1900-01-01 出版日期:2006-08-21 发布日期:2006-08-21
  • 通讯作者: 朱鸿宇 zhylg zhylg

An intelligent prefetch algorithm on database query optimization

,,,   

  1. 解放军信息工程大学信息工程学院
  • Received:2006-03-21 Revised:1900-01-01 Online:2006-08-21 Published:2006-08-21

摘要: 文中提出了一种新的用于关系数据库查询缓冲和预取的方法。首先将数据查询语句抽象成由四元组组成的查询模版,同时保存了查询语句的实际参数。基于这些模版和参数,提出了两种智能预取算法以适合两类不同的数据查询需求。第一个算法基于蚁群规则,该算法能够用于预测将来具有最高可能性的查询。经过监控某个特定应用对于数据库所发生的大量查询,实际的模版数要远远小于发生的查询数。当通过考虑查询模版和跟踪历史查询记录来预测未来可能发生的查询时,提出了第二类算法,该算法基于惯性规则,它使用BP网络来跟踪用户的查询历史。相对于前面的算法,该算法更适合多应用共存的场合。在模拟实验中发现对于单个应用而言,查询具有很高的模版依赖性,而对于多应用的场合,惯性规则具有更好的适应性。

关键词: 数据预取, 蚁群规则, 惯性规则

Abstract: In this report, we explore a new approach toward intelligent caching and prefetching for data query of DBMS. First we abstract the data query statement into query patterns which consists of four units. We also consider the real query parameters which can be used to build real query from the query pattern. Base on the query pattern and the real query parameters, we develope two intelligent prefetch algorithms to fit two kinds of demand in data query. The first algorithm bases on ant-group rule. It can be used to predict the future query with highest probability. Our experiments show that in contrast to the substantially large number of queriescoming of the special application to the database system, the number of patterns of these differentqueries are quite limited. We take into consideration the query pattern and the historytrace of query reference when predicting future query and develop the second algorithm base on inertia rule which uses BP network to trace the history of user query. It is more fit for the multi-application situation than the previous. Our simulation shows the inter-query locality is highly query pattern dependable under single-application situation and the inertia rule has more flexibility under multi-application situation.

Key words: prefetch, ant-group rule, inertia rule