没有合适的资源?快使用搜索试试~ 我知道了~
论文研究-封闭立方体反转索引查询优化技术.pdf
需积分: 9 0 下载量 63 浏览量
2019-07-22
23:23:27
上传
评论
收藏 535KB PDF 举报
温馨提示
试读
5页
处理用户复杂查询请求的速度是数据仓库关键性能之一。论述了在 QC算法产生的聚集表上建立反转索引和查询并还原出立方体上界的方法 ,查询算法包括位图查询算法和反转列表查询算法。最后进行了性能测试 ,结果表明这两种算法均能够提高查询的速度。
资源推荐
资源详情
资源评论
收 稿日期 : 2007-11-22; 修 回 日 期: 2008- 03- 28 基 金 项 目: 广 东 省 科 技 计 划 资 助 项 目 ( 2006B11301001) ; 广 州 市 科 技 计 划 资 助 项 目
( 2006Z3-D3081)
作 者简介 : 肖伟吉 ( 1983-) , 男, 广东 汕头人 , 硕士研 究生, 主 要研究 方向 为数据 仓库( xwjxwj238@ 163. com) ; 奚建 清 ( 1962- ) , 男, 江 苏人 , 教授 ,
博导, 主要 研究 方向为 数据 库和数 据仓库 、P2P 分布式 系统 、中 文信息 处 理、知 识管 理、软 件 开发 技 术; 欧 国 华 ( 1969- ) , 男, 广 东 清 远 人, 工 程 师, 主
要研究 方向为 计算 机应用 .
封 闭 立 方 体 反 转 索 引 查 询 优 化 技 术
*
肖伟吉, 奚建清, 欧国华
( 华南 理工 大学 计 算机 科学 与工 程学院 , 广州 510006)
摘 要: 处 理 用户 复 杂 查询 请 求 的速 度 是 数据 仓 库 关键 性 能 之一 。论 述 了 在 QC 算法 产 生 的聚 集 表 上建 立 反
转索 引和 查询 并还原 出立 方体 上界 的方 法, 查询 算法 包括 位图 查询 算法 和反转 列表 查询 算法 。最 后 进 行了 性 能
测试 , 结 果表 明这 两种 算法 均能 够提高 查询 的速 度。
关键 词: 封 闭立 方体 ; 位图 查询 算法 ; 反转列表 查询 算法
中图 分类 号: TP311 文献 标志码 : A 文章 编号 : 1001-3695( 2008) 10-2977-05
Inverted index search optimization technology of closed cube
XIAO Wei-ji, XI Jian-qing, Ou Guo-hua
( School of Computer Science & Engineering, South China University of Technology, Guangzhou510006, China)
Abstract: The speed of dealing withthe users’complex queries is one of the key performance of the datawarehouse. This pa-
per dissertated the methods of making inverted index on aggregate table by QC algorithmand searching and revertingthe upper
bound of the cube. The search methods included bitmap search algorithmand inverted lists search algorithm. Finally, carried
outperformance test. The result shows that these two algorithms can improve the query speed.
Key words: closed cube; bitmap search algorithm; inverted lists search algorithm
为了提高联机分析处理整体的查 询性能, 本文利用 QC 算
法
[ 1,2]
建立了封闭立方体, 并在其产 生的聚集 表的每 一个维 度
上建立反转索引。同时设计和 实现了 在反转 索引上 的两种 查
询算法, 即位图查询算法 和反转 列表查 询算法, 提高 了查询 的
性能。
1 立方体上界的生成
1. 1 封闭立方体的特性
李盛恩等人在文献[ 3] 中定义 了覆盖、基本元组 集和封 闭
元组的概念如下:
假设关系 R 的模式 是 R( A
1
, A
2
, …, A
n
, M) 。其中: A 作 为
维属性, 1≤i≤n; M作为度量属性; A
1
, A
2
, …, A
n
是 R的关 键
字。用 C 表示由 R 产生的数据立方体。
定义 1 t
1
∈C, t
2
∈ C, A
i
, 1≤ i≤ n, 如果 满足以 下 条
件, 则称 t
2
覆盖 t
1
或 t
1
被 t
2
覆盖:
如果 t
2
( A
i
) ≠all, 则 t
1
( A
i
) = t
2
( A
i
) ;
如果 t
2
( A
i
) =all, 则 t
1
( A
i
) 可以取任意值。
例如: 元组( * , 0, * , 40) 覆 盖元组 ( * , 0, 1, 30) , ( * , 0,
0,10) , ( 0, 0, * , 40) , ( 0, 0,1, 30) , ( 0,0, 0, 10) , ( * , 0, * ,
40) 。其中: 40 为度量值。
定义 2 元组 t 的基本元 组集为 BTS( t′) = { t′|t′∈ R, t∈
C, t 覆盖 t′} 。
例如: BTS( ( 0, 1, * , 80) ) = { ( 0, 1, 1, 20) , ( 0, 1, 2, 60) } ,
BTS( ( 0, 1,1, 20) ) = { ( 0, 1, 1, 20) } 。由 定义 1 和 2 可 知, 如
果 t
2
覆盖 t
1
, 则 BTS( t
1
) A BTS( t
2
) 。
定义 3 对于元组 t
1
∈C, 如果不 存在元 组 t
2
∈C, t
2
≠t
1
,
t
1
覆盖 t
2
, 并且 BTS( t
1
) = BTS( t
2
) , 则称元组 t
1
为封闭元组。
例如: 元组( * , * , * , 160) 不是封 闭元组, 因为 它覆盖 元
组( 0, * , * , 160) , 并且它们的 BTS 相等。
笔者还在上面定义的基 础上提 出了下 面两个 定理。为 本
文的查询优化算法提供了理论基础。
定理 1 在封闭数据立方体中对任意的聚集函 数, 均可 以
从某个封闭元组中得到非封闭元组的聚集函数值。
例如: 元组( * ,0, * ,40) 覆盖封闭元组 ( 0, 0, * , 40) , ( 0,
0,1, 30) 和( 0,0, 0, 10) , 因为元组( 0, 0, * , 40) 中出 现 all 的次
数最多, 所以 BTS( * , 0, * , 40) = BTS( 0, 0, * , 40) , 两者的 聚
集函数值相等。
定理 2 如果按照第 i, i +1, …, n +1 层的次序查找被 t 覆
盖的封闭元组, 并且如果在第 j ( j≥i) 层找到则 不必到第 j + 1
层继续查找。
根据文献[ 3] 中的定义和定理, 在检查 n 个满足 条件的 封
闭元组时, 不必把整个立方 体数据 全部读 入内存, 可 以按照 一
定的次序一部分一部分地加载, 当找到一个满足条件的封闭元
组时就停止查找。
通过上面的定义及定理, 封闭立方体中查找一个元组的过
程可以分解为两步: a) 利用 某种 存取方 法 ( 如索 引) 从 外存 上
找到满足上界条件的类, 并将这些类 一一读 到内存; b) 在内 存
中利用下界作最后的判断。由于只保存上界, 本文的查询优化
第 25 卷第 10 期
2008 年 10 月
计 算 机 应 用 研 究
Application Research of Computers
Vol. 25 No. 10
Oct. 2008
资源评论
weixin_39841882
- 粉丝: 443
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功