XML查询缓存中替换策略的研究与设计

摘要

XML(eXtensible Markup Language，可扩展标记语言)自发布之日起就以其良好的可扩展性受到业界的普遍欢迎和支持，越来越多的应用领域已经将其作为主要的存储格式和传输媒体。随着XML应用规模和复杂性的飞速增长，快速有效地处理XML查询成为当前研究的热点。 随着对XML查询优化问题的不断深入研究，针对XML查询的缓存技术受到越来越多的关注。通过对“热”数据(频繁查询模式)进行缓存，可以有效地提高数据库的处理效率和响应能力。由于缓存空间是有限的资源，在保持缓存性能的同时，需设计出适当的替换策略来决定哪些频繁查询模式最适合驻留在缓存中，因此缓存中的替换策略又是XML查询缓存中需要着重解决的问题。 本文将基于XML查询的语义缓存机制作为改进XML查询系统的有效手段。在对现阶段XML文档查询系统研究和分析的基础上，本文设计了一个引入语义缓存机制的XML文档查询系统。在讨论了该系统各主体模块的功能后，本文着重就XML查询缓存的替换策略展开了深入的研究，并提出了一个有效的方法。该方法按如下三个阶段进行实施： 首先使用数据挖掘中聚类的方法基于语义将XML查询进行聚类，使具有相似信息的查询被分到同一组中。分析频繁有根子树的挖掘算法并使用算法FastXMiner从XML查询中发现频繁有根子树，在此基础上提出了一个新颖的方法基于语义聚类XML查询。 其次，对正关联规则和负关联规则的概念进行介绍和研究分析。FastXMiner从用户查询中挖掘出了频繁的XML查询模式，一旦缓存已满，不频繁查询模式的查询区域将首先被回收。然而FastXMiner中的基于频繁查询模式的技术忽视了用户查询的临时特性。本文在对XML查询聚类的基础上，提出了一个从XML缓存的用户查询中挖掘关联规则的有效算法。为了发现关联规则，着重强调了用户查询间的临时序列关系，因此与只强调频繁性或最近性的方法相比，能更可靠地预测接下来可能的用户查询和规则的置信度。该算法执行后，正关联规则和负关联规则可以被同时挖掘出来。 最后，对现有的缓存替换策略进行了分析和研究，根据前面挖掘出的关联规则的知识设计出一个合适的XML查询缓存替换策略。本文进行了实验测试，分别对查询聚类和XML查询缓存替换策略给出了实验结果与性能分析，实验结果显示与其它算法相比，本文的方法更显著地提高了缓存性能。

目录

文摘

英文文摘

原创性声明及关于学位论文使用授权的声明

第1章引言

1.1背景介绍

1.2国内外研究现状

1.3论文主要工作

1.4论文的组织

第2章引入语义缓存机制的XML查询系统

2.1系统总体架构

2.2系统框架内各部分模块的功能描述

2.3 XML查询缓存

2.4本章小结

第3章聚类挖掘XML查询模式

3.1 XML及其查询语言

3.1.1 XML简介

3.1.2 XQuery语言概述

3.2聚类基础知识及分类

3.2.1聚类的概念和性能

3.2.2聚类的分类

3.3发现频繁有根子树

3.3.1 XML查询模式树

3.3.2树的包含

3.3.3频繁有根子树的挖掘算法

3.3.4有根子树的包含算法

3.4聚类XML查询的方法

3.4.1聚类标准

3.4.2聚类方法

3.5实验结果及性能分析

3.6本章小结

第4章关联规则的挖掘及替换策略的设计

4.1基本概念

4.1.1关联规则的概念

4.1.2关联规则的分类

4.1.3正关联规则和负关联规则

4.2 XML查询聚类间正、负关联规则的挖掘算法

4.3 XML查询缓存的替换策略

4.3.1缓存替换策略分析

4.3.2 LRU_AR替换策略

4.4实验结果与性能分析

4.5本章小结

第5章总结与展望

5.1工作总结

5.2未来工作

参考文献

致谢

攻读学位期间发表的主要学术论文