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

列数据库字符串类型操作研究与实现

作　者: 黄鑫铭
导　师: 汤德佑; 沈顺七
学　校: 华南理工大学
专　业: 软件工程
关键词: 列数据库字符串数据并行 AC算法
分类号: TP391.1
类　型: 硕士论文
年　份: 2013年
下　载: 8次
引　用: 0次
阅　读: 论文下载

内容摘要

列数据库系统将数据按列方式存储是现今数据库研究的一个重要方向，在大数据处理等领域具有重要应用价值。在课题组实现的列数据系统中，数据库操作被编译器转化为一系列以向量为操作对象的原语操作，由动态调度器调度原语在多核处理器上执行，以进一步提升数据库操作查询的性能。本文主要负责列数据库查询操作中字符串类型数据相关原语的设计和实现。通过优化字符串数据在主存的存储格式以及字符串查找匹配的并行实现来提升字符串相关原语的查询性能。本文的主要工作包括以下几个部分：1）给出了字符串数据文件的读取方法以及数据在主存的存储格式。通过读取数据文件的文件头信息，将数据文件存储的数据读取到连续的内存地址空间中，并定义了相应的数据结构存储字符串数据的起始地址等信息。读取后的字符串数据以4字节对齐的方式依次顺序存储在主存当中。2）设计和实现字符串类型相关的原语。包括STRING_Like（含通配符的查找）、STRING_In（查询是否与列表字符串匹配）、STRING_Between（查询字符串是否在指定范围）、STRING_Equal（精确查找）、SUB_String（提取子字符串）5个基本原语。本文研究并实现了5个原语分别对于定长和变长字符串数据的不同操作。3）给出了AC算法在字符串查找匹配中的应用和实现方法。AC算法是基于有穷状态机的多模式匹配算法，算法在匹配之前对所有待匹配模式串集合构建一个有穷模式匹配状态机，命名为AC自动机。在匹配时，AC自动机只需要对待匹配字符串列表进行一次扫描就可以找出字符串列表中达成匹配的字符串。AC算法进行字符串匹配的复杂度只与待匹配字符串列表的大小有关，而与模式串的大小无关。4）给出了字符串类型原语的并行实现。通过分治的方法实现字符串数据处理在文件级和字符串级的并行处理从而提升字符串原语在多核处理器的查询性能。

全文目录

摘要  5-6
Abstract  6-10
表目录  10-12
图目录  12-14
第一章绪论  14-17
  1.1 研究背景和意义  14
  1.2 本文主要工作  14-15
  1.3 论文的组织和安排  15-17
第二章字符串类型原语介绍  17-26
  2.1 向量格式简介  17
  2.2 STRING_LIKE 原语  17-19
  2.3 STRING_BETWEEN 原语  19-20
  2.4 STRING_IN 原语  20-22
  2.5 STRING_EQUAL 原语  22-23
  2.6 SUB_STRING 原语  23-25
  2.7 本章小结  25-26
第三章字符串类型原语的设计和实现  26-45
  3.1 字符串数据文件的存储格式  26-31
    3.1.1 文件头  26-27
    3.1.2 定长字符串数据文件的存储格式  27-28
    3.1.3 变长字符串数据文件的存储格式  28-29
    3.1.4 字符串数据在主存的存储格式  29-30
    3.1.5 定长字符串数据在内存的存储格式  30
    3.1.6 变长字符串数据在内存的存储格式  30-31
  3.2 字符串数据的读取方法  31-32
  3.3 STRING_LIKE 原语  32-40
    3.3.1 基于 AC 算法的字符串匹配  32-38
    3.3.2 字符串的 String_like 操作处理流程  38-40
  3.4 STRING_BETWEEN 原语  40-41
  3.5 STRING_IN 原语  41-42
  3.6 STRING_EQUAL 原语  42-43
  3.7 SUB_STRING 原语  43-44
  3.8 本章小结  44-45
第四章字符串类型原语的并行实现  45-52
  4.1 基于文件级查找的并行实现  45
  4.2 定长字符串分段  45
  4.3 变长字符串分段  45-46
  4.4 文件级并行查找处理流程  46-47
  4.5 超长字符串查找的并行实现  47-51
    4.5.1 超长字符串的分段处理  47-49
    4.5.2 超长字符串并行处理流程  49-51
  4.6 本章小结  51-52
第五章字符串类型原语测试报告  52-63
  5.1 测试环境  52-53
  5.2 字符串数据读取测试  53-54
    5.2.1 定长字符串数据读取  53-54
    5.2.2 变长字符串数据读取  54
  5.3 STRING_EQUAL 原语测试  54-55
    5.3.1 定长字符串 String_equal 原语测试  54-55
    5.3.2 变长字符串 String_equal 原语测试  55
  5.4 STRING_IN 原语测试  55-56
    5.4.1 定长字符串 String_in 原语测试  55-56
    5.4.2 变长字符串 String_in 原语测试  56
  5.5 STRING_BETWEEN 原语测试  56-57
    5.5.1 定长字符串 String_between 原语测试  56-57
    5.5.2 变长字符串 String_between 原语测试  57
  5.6 STRING_LIKE 原语测试  57-58
    5.6.1 定长字符串 String_like 原语测试  57
    5.6.2 变长字符串 String_like 原语测试  57-58
  5.7 SUB_STRING 原语测试  58-59
    5.7.1 定长字符串 Sub_string 原语测试  58
    5.7.2 变长字符串 Sub_string 原语测试  58-59
  5.8 超长字符串查找匹配测试  59
    5.8.1 定长字符串测试  59
    5.8.2 变长字符串测试  59
  5.9 原语测试结果  59-62
  5.10 本章小结  62-63
第六章总结与展望  63-65
  6.1 工作总结  63-64
  6.2 展望  64-65
参考文献  65-67
攻读硕士学位期间取得的研究成果  67-68
致谢  68-69
附件  69

列数据库字符串类型操作研究与实现

内容摘要

全文目录

相似论文