星型模型的轮廓连接查询算法*

doi:10.3778/j.issn.1673-9418.2010.05.003

计算机科学与探索 ›› 2010, Vol. 4 ›› Issue (5): 410-419.DOI: 10.3778/j.issn.1673-9418.2010.05.003

星型模型的轮廓连接查询算法*

徐忠华^1,2, 张剡^1,2+, 陈玲^1,2, 柏文阳^1,2

1. 南京大学计算机软件新技术国家重点实验室, 南京 210093
2. 南京大学计算机科学与技术系, 南京 210093

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-05-11 发布日期:2010-05-11
通讯作者: 张剡

Skyline-Join Algorithm in Star Model*

XU Zhonghua^1,2, ZHANG Yan^1,2+, CHEN Ling^1,2, BAI Wenyang^1,2

1. State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210093, China
2. Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China

Received:1900-01-01 Revised:1900-01-01 Online:2010-05-11 Published:2010-05-11
Contact: ZHANG Yan

摘要/Abstract

摘要： 轮廓查询在多标准决策中具有重要应用价值, 对于单表轮廓查询已有大量研究, 但在实际中, 轮廓查询的属性很可能分布在多张表中。如果在多表连接之后进行轮廓查询, 随着维度和元组数目的增加, 计算代价会越来越大。为此, 针对数据仓库中星型模型的数据特点, 提出了三种此模型下的多表连接轮廓查询算法并对算法进行了实验比较分析。结果表明, 此算法比先连接再做单表轮廓查询的算法更为有效, 并且这三种算法在不同特点的数据集合下会表现出各自的优势。

关键词: 轮廓查询, 多表连接, 数据仓库, 星型模型

Abstract: Skyline query is valuable in multi-criteria decision making. Most of the exiting work is based on single table skyline query. However, the data retrieved by users for the targeting skyline may often be stored in multiple tables, especially in star model of data warehouse. As a result, the costs on computing skylines on the joined table will increase dramatically due to its increasing dimensionality and cardinality. Thus, based on the data characteristic of star model, three solutions to skyline-join in star model in data warehouse are proposed. Experiments demonstrate that the algorithms are better than naive skyline query, and they dominate others in its own data set.

Key words: skyline-join, multi-relation, data warehouse, star model

中图分类号:

TP301

徐忠华1,2 , 张剡1,2+ , 陈玲1,2 , 柏文阳1,2 . 星型模型的轮廓连接查询算法*[J]. 计算机科学与探索, 2010, 4(5): 410-419.

XU Zhonghua^1,2, ZHANG Yan^1,2+, CHEN Ling^1,2, BAI Wenyang^1,2. Skyline-Join Algorithm in Star Model*[J]. Journal of Frontiers of Computer Science and Technology, 2010, 4(5): 410-419.

[1]	王梅，邢露露，孙莉. 混合存储下的MapReduce启发式多表连接优化[J]. 计算机科学与探索, 2014, 8(11): 1334-1344.
[2]	聂章艳，李川，唐常杰，徐洪宇，张永辉，杨宁. 面向OLGP的多维信息网络数据仓库模型设计[J]. 计算机科学与探索, 2014, 8(1): 51-60.
[3]	覃雄派. 星型模型上的高效百分点计算方法[J]. 计算机科学与探索, 2013, 7(5): 385-393.
[4]	夏小玲, 张红+ . 为物化视图选择构造搜索空间的新策略IMVPP *[J]. 计算机科学与探索, 2010, 4(5): 473-479.
[5]	林子雨+, 林琛, 冯少荣, 张东站. MESHJOIN：实时数据仓库环境下的数据流更新算法[J]. 计算机科学与探索, 2010, 4(10): 927-939.
[6]	丁晓锋+,卢炎生,赵娜. 基于TPU-tree的Skyline分支定界查询算法[J]. 计算机科学与探索, 2009, 3(2): 162-172.
[7]	信俊昌+,王国仁,张小艺. 无线传感器网络中滑动窗口轮廓查询算法[J]. 计算机科学与探索, 2009, 3(1): 37-50.

星型模型的轮廓连接查询算法*

Skyline-Join Algorithm in Star Model*

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics