学位论文 > 优秀研究生学位论文题录展示

基于改进PST的字符串谓词选择率估算算法研究

作　者: 张其旭
导　师: 李东; 张建军
学　校: 华南理工大学
专　业: 软件工程
关键词: 查询优化选择率估算字符串谓词 PST
分类号: TP391.1
类　型: 硕士论文
年　份: 2013年
下　载: 2次
引　用: 0次
阅　读: 论文下载

内容摘要

XML的自描述性、可验证性、可扩展性等优点使得它迅速被计算机界接受和广泛应用，随着它逐渐成为互联网中数据表示和数据交换的重要标准，XML数据的复杂性和规模都急剧增长，这就对海量XML数据的管理提出了需求。一种最有效、最直接的方法是以数据库技术管理海量XML数据。查询处理是数据库永恒的主题，XML查询优化算法的优劣直接影响到XML查询的性能好坏。在基于代价估算的查询优化算法中，谓词的选择率是估算查询代价的一个不可或缺的因素，其中值谓词的选择率一般通过查找XML文档值统计信息获得，但由于存储空间有限，XML文档值统计信息往往不完整，需要通过特定的估算策略估算值谓词的选择率。在现有的XML文档字符串型值统计信息技术中，主要以PST作为字符串型值概要统计信息存储结构，通过特定的选择率估算算法估算字符串谓词的选择率，但这些基于PST的估算算法都还存在着严重的选择率高估或低估，平均相对误差的精确度不高的问题。为了提高基于PST的字符串谓词选择率估算算法的估算精确度，本文通过分析现有典型算法KVI、MO的高估和低估产生的主要原因，提出了扩展PST（RPST）结构和新的剪枝策略，在RPST的基础上，提出了基于KVI算法和MO算法的改进算法EKVI和EMO，最后再描述了RPST在多字符串布尔查询谓词估算算法中的应用。实验比较了EKVI算法和EMO算法与传统的KVI算法和EMO算法，结果表明新算法在平均相对误差上明显优于传统算法，EMO算法总体效果最好。

全文目录

摘要  5-6
Abstract  6-10
第1章绪论  10-15
  1.1 课题研究背景与意义  10-13
  1.2 主要工作与章节安排  13-15
第2章基于代价估算的 XML 查询优化技术  15-25
  2.1 引言  15
  2.2 XML 查询处理技术  15-17
  2.3 查询代价估算技术  17-19
  2.4 XML 文档的值统计信息  19-24
  2.5 本章小结  24-25
第3章基于改进 PST 的字符串谓词选择率估算算法  25-40
  3.1 引言  25
  3.2 单字符串谓词选择率估算  25-33
    3.2.2 KVI 算法及 MO 算法  26-27
    3.2.3 PST 改进以及估算算法  27-33
  3.3 多字符串布尔查询谓词选择率估算  33-39
    3.3.1 计数后缀树结点压缩  33-35
    3.3.2 布尔查询估算算法  35-39
  3.4 本章小结  39-40
第4章基于改进 PST 的字符串谓词选择率估算算法在 XSQS 中的实现  40-54
  4.1 引言  40
  4.2 XSQS 系统简介  40-41
  4.3 字符串谓词选择率估算算法在 XSQS 中的实现  41-43
  4.4 实验评估  43-53
    4.4.1 实验环境  43-45
    4.4.2 实验结果及分析  45-53
  4.5 本章小结  53-54
总结  54-56
参考文献  56-60
攻读硕士学位期间取得的研究成果  60-61
致谢  61-62
附件  62

相似论文

海量多数据库集成系统的查询处理研究,TP311.13
海量数据存储与全文检索,TP333
PST/BA/AA可再分散乳胶粉的制备,TQ330.6
面向SaaS应用的租户多级定制模型研究,TP393.09
基于改进蚁群算法的数据仓库查询优化研究,TP311.13
哈尔滨产乙醇杆菌模式菌株YUAN-3Sau3AⅠ与PstⅠ酶切基因组文库的构建,Q78
分布式数据库有关连接查询优化算法的研究,TP311.13
基于遗传算法的分布式多连接查询优化系统设计与实现,TP311.13
基于堆栈的择优遗传禁忌查询优化算法的设计与实现,TP311.13
改进的城市公交查询算法研究,TP301.6
选择性估算的新算法研究,TP301.6
基于遗传退火算法的数据库多连接查询优化研究与应用,TP311.13
GA在数据库多连接查询优化中的应用研究,TP311.13
一种分页查询优化方法的研究与实现,TP311.13
分布式实时数据库查询优化技术研究,TP311.13
传感器网络数据管理系统查询机制的研究与实现,TP311.13
并行数据库查询优化的遗传算法,TP311.13
数据库管理系统中查询优化的设计和实现,TP311.13
web文档性质分类的研究与应用,TP393.09
基于Web Services和元数据的信息集成技术研究,TP393.09
关于XML数据库存储和访问技术研究,TP311.13