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

高性能数据立方体及其语义研究

作　者: 师智斌
导　师: 黄厚宽
学　校: 北京交通大学
专　业: 计算机应用技术
关键词: 数据仓库数据立方体聚集形式概念分析概念格属性蕴含语义范围查询
分类号: TP311.13
类　型: 博士论文
年　份: 2010年
下　载: 229次
引　用: 0次
阅　读: 论文下载

内容摘要

数据立方体技术是联机分析处理的主要手段。随着数据规模的扩大和维数的增加,数据立方体的操作代价急剧增加,需要进行优化处理。目前数据立方体的研究包括:物化、索引、近似、压缩、约简以及联机聚集等。形式概念分析理论(FCA)是以形式化的概念和概念层次为基础的数学分析工具。研究发现,概念格作为FCA的核心结构与数据立方体格都基于序结构,并且以数据仓库中的基本表作为形式背景,FCA理论中与概念相对应的等价特征组与数据立方体的覆盖等价类对数据单元具有相同的划分结果。本文将FCA和概念格理论引入数据立方体的研究,进行高性能数据立方体及其语义研究。研究表明,FCA及相关理论的引入,为数据立方体研究提供了一个新的有力的分析工具,利用该工具可以从数据内部特性入手,实现结构简单、体积较小且性能较优的数据立方体,并使数据立方体语义的理解更深刻,更易于实现。主要的研究工作如下:(1)提出基于形式概念格结构表达的数据立方体。首先对数据立方体与形式概念格进行相关分析,以概念格结构表达数据立方体,提出聚集概念和聚集概念格结构(ACL)。ACL是一种完全的数据立方体结构,由于其内具有相同聚集值的若干单元用一个聚集概念表示,因此能实现与商立方体相同的约简。另外,ACL结构中概念间的泛化和例化关系反映了约简后数据之间的层次关联,可表达比商立方体更清晰的数据立方体语义关系。其次,在ACL基础上,本文提出约简聚集概念结构(RAC)。基于形式概念分析理论中G偏序关系的性质研究发现,由于基本表的完备性,基本表中各个元组与ACL结构中的对象概念一一对应,因此基本表可以看作是所有对象概念的集合。RAC结构对ACL进一步约简,去除所有对象概念和特殊概念(Ω,null)。与基本表联合,RAC仍然是完全的立方体结构,但能实现比商立方体和ACL结构更大的约简,且仍能保持所有非对象聚集概念之间的语义关系。第三,基于形式概念分析理论中M偏序集的性质,提出基于ACL和RAC高效的查询方法。该方法利用属性概念内涵m″确定在ACL和RAC上的查询搜索路径,避免全范围的搜索,查询效率较高。最后,对形式背景进行讨论,将概念格的属性约简理论应用于数据立方体,通过合并相对必要属性、删除绝对不必要属性实现形式背景的简化,最终实现数据立方体相关操作的简化。(2)研究形式背景的属性蕴含关系,采用关系系统存储,提出基于属性蕴含的约简聚集概念数据立方体结构(RAC-AI)。根据形式概念分析理论,研究形式背景中描述概念格的两类非平凡属性蕴含:前提是伪内涵的蕴含和前提是真前提的蕴含。研究通过属性蕴含而不再依赖概念格结构确定概念内涵。在RAC结构基础上,提出两种基于属性蕴含的约简聚集概念数据立方体结构(RAC-AI):基于前提是伪内涵和基于前提是真前提的RAC-AI结构。RAC-AI结构摒弃RAC复杂的概念格结构,增加属性蕴含表,记录形式背景中所有非平凡的蕴含,并采用主流的关系系统存储所有非对象聚集概念。理论分析和实验结果表明,RAC-AI体积小,结构简单,构建和增量维护代价较低,查询响应速度也较快,是目前综合性能较优的数据立方体。(3)数据立方体语义关系的挖掘和应用直接影响联机分析处理的各种操作。本文研究基于FCA和概念格理论的数据立方体语义操作实现。首先讨论形式背景的净化和约简,消除形式背景中的冗余信息。现有的数据立方体语义研究都未考虑对数据本身进行约简,大量冗余信息的存在干扰了对语义的理解和发现。其次,利用形式概念分析的M偏序集理论,将M偏序关系作为生成概念分层的一种启发式的规则,形成属性级别的概念分层语义,而现有的概念分层一般只进行到维级别。第三,利用M偏序关系和非平凡的属性蕴含,实现数据立方体单元之间的上卷和下钻语义操作。通过分析等价特征组上界和下界的特性,获得等价特征组的结构,实现具有相同聚集值单元之间的上卷和下钻语义操作。利用非平凡的属性蕴含获取任意概念的父概念和子概念的内涵,实现不同聚集值单元的上卷和下钻语义操作。该方法不依赖任何特殊结构,实现从数据立方体任意单元出发的上卷和下钻操作,重复这个过程,能在数据立方体格中漫游,而不必生成完整的数据立方体。现有的数据立方体上卷和下钻语义操作一般只进行到视图级别,能达到单元级别的一般要依赖复杂特殊的结构实现。(4)范围查询是应用于多维数据立方体的有效的分析工具,预计算技术是提高范围查询响应速度的一种方法。本文在现有prefix sum技术和分块技术基础上,提出基于前缀区域的不规则方体的分块方法PRC,这种分块方法利于从起始单元开始的前缀区域聚集值的计算。对d维数据立方体(假定每维的度都为n),PRC在分块及区域求和时使用回归分割技术,在不增加额外空间的基础上,实现范围查询和数据更新的代价都为O(log~dn)。

全文目录

致谢  5-6
中文摘要  6-8
ABSTRACT  8-14
1 绪论  14-21
  1.1 数据仓库和联机分析处理  14-15
  1.2 数据立方体概述  15-18
    1.2.1 数据立方体组织结构  15-16
    1.2.2 聚集函数  16-17
    1.2.3 数据立方体存储  17
    1.2.4 基于数据立方体的查询处理  17-18
  1.3 本文的研究内容和创新点  18-20
  1.4 本文的组织  20-21
2 数据立方体主要研究内容及研究现状  21-33
  2.1 数据立方体聚集计算方法  22-24
  2.2 数据立方体物化选择算法  24-26
  2.3 数据立方体近似技术  26-27
  2.4 数据立方体特殊查询方式  27-29
  2.5 数据立方体约简技术  29-31
  2.6 小结  31-33
3 ACL和RAC:基于形式概念格的约简数据立方体结构  33-66
  3.1 引言  33-34
  3.2 形式概念分析的理论基础  34-37
    3.2.1 基本概念  34-36
    3.2.2 相关研究内容  36-37
  3.3 数据立方体与形式概念格相关分析  37-41
  3.4 聚集概念格(Aggregate Concept Lattice，ACL)  41-45
    3.4.1 聚集概念格的定义  42-45
    3.4.2 聚集概念格结构的建立  45
  3.5 约简聚集概念结构(Reductive Aggegate Concept structure，RAC)  45-49
    3.5.1 问题的提出  45-47
    3.5.2 约简聚集概念结构(Reductive Aggegate Concept structure，RAC)  47-48
    3.5.3 约简聚集概念结构的构建  48-49
  3.6 基于ACL和RAC的数据立方体查询处理  49-56
    3.6.1 任意维组合的查询实现  49-52
    3.6.2 基于ACL结构的查询处理  52-54
    3.6.3 基于RAC的查询处理  54-55
    3.6.4 基于RAC的查询举例  55-56
  3.7 RAC性能分析及测试实验  56-60
    3.7.1 性能分析  56-58
    3.7.2 测试实验  58-60
  3.8 关于形式背景的约简讨论  60-65
    3.8.1 概念格属性约简定义和方法  61-63
    3.8.2 概念格属性约简方法在数据立方体中的应用  63-65
  3.9 小结  65-66
4 RAC-AI:基于属性蕴含的约简数据立方体结构  66-94
  4.1 引言  66-67
  4.2 动机  67-68
  4.3 属性蕴含  68-73
    4.3.1 属性蕴含的相关概念  68-69
    4.3.2 前件是伪内涵的完备且非冗余的蕴含集合  69
    4.3.3 前件是真前提的完备的蕴含集合  69-70
    4.3.4 两类属性蕴含之间的关系  70-71
    4.3.5 伪内涵和真前提的计算  71
    4.3.6 通过属性蕴含获取概念内涵  71-73
  4.4 RAC-AI:基于属性蕴含的约简数据立方体结构  73-88
    4.4.1 基于前件是伪内涵的属性蕴含的RAC-AI结构  74-80
    4.4.2 基于前件是真前提的属性蕴含的RAC-AI结构  80-82
    4.4.3 RAC-AI的增量更新  82-88
  4.5 RAC-AI性能分析和测试实验  88-93
    4.5.1 性能分析  88-89
    4.5.2 测试实验  89-93
  4.6 小结  93-94
5 基于FCA和概念格理论的数据立方体语义研究  94-115
  5.1 引言  94-95
  5.2 相关工作  95-98
  5.3 数据立方体语义研究  98-114
    5.3.1 形式背景的约简讨论  98-100
    5.3.2 概念分层语义  100-101
    5.3.3 具有相同聚集值单元之间的语义关系  101-107
    5.3.4 具有不同聚集值单元之间的语义关系  107-114
  5.4 小结  114-115
6 PRC:适用于范围查询的基于前缀区域的数据立方体结构  115-126
  6.1 引言  115-116
  6.2 相关工作  116-119
  6.3 PRC:基于前缀区域的数据立方体结构  119-125
    6.3.1 动机  119-120
    6.3.2 基本的前缀区域数据立方体(Basic Prefix Region Cube)  120-123
    6.3.3 PRC数据立方体的改进  123-124
    6.3.4 PRC数据立方体性能分析  124-125
  6.4 小结  125-126
7 结束语  126-129
  7.1 本文工作的总结  126-127
  7.2 进一步研究的展望  127-129
参考文献  129-138
作者简历  138-140
学位论文数据集  140

高性能数据立方体及其语义研究

内容摘要

全文目录

相似论文