子空间SKYLINE查询若干关键问题的研究

子空间SKYLINE查询若干关键问题的研究

论文摘要

Skyline查询技术是近年来数据库邻域的一个研究重点和热点,这主要是因为该查询技术广泛应用于多标准决策系统、城市导航系统、数据挖掘和可视化、智能防御系统、以及地理信息系统等领域。现有的相关工作主要集中于研究全空间上的skyline查询,即它们假定用户所提交的是单个查询,并且查询所涉及的维度包含对象的所有属性。然而,在实际应用中,由于对象具有较大规模的全空间,而用户通常只对部分子空间上的skyline对象集合感兴趣;同时,不同的用户可能关注不同的子空间,因此,现有的算法和数据结构无法满足子空间skyline查询在有效性和可扩展性上的需求。基于此,本文着重研究子空间skyline查询技术中的效率问题,主要包括如下3个关键方面:(1)有效解析用户提交的子空间skyline查询现有的研究工作不考虑传统关系操作(如选择、卡氏积和连接等)存在于子空间skyline查询的情况,而且没有考虑系统中同时存在多个不同子空间skyline查询的情况。因此,本文的一个重要工作是从提高查询性能出发,在逻辑层面上,考虑如何优化它们之间的执行顺序来缩减子空间skyline查询的时间开销。我们将子空间skyline查询计算作为一个特殊的关系操作符(称之为子空间skyline操作符),研究它与传统关系操作符间执行顺序变换的等价规则,以及达到这种等价变换所需要的附加条件。从而,基于这些等价变换规则和附加条件,通过改变子空间skyline操作符与传统关系操作符之间的执行顺序来有效提高查询的效率。另一方面,我们提供充分的理论证明来表明这些等价变换规则的正确性;同时,给出执行顺序变换前后的时间开销的理论值来表明这些等价变换规则的有效性。最后,我们实施了大量的实验,实验结果表明,变换之后的时间开销显著低于变换之前的时间开销。(2)有效实施用户提交的子空间skyline查询由于传统关系操作的实施算法现已较成熟,而现有关于在物理层面上实施子空间skyline计算的相关工作比较有限,而且它们的计算效率通常较低。因此,本文的第二个重要工作是考虑如何有效实施子空间skyline计算。我们从减少对象间的比较次数出发,基于正规格结构,给出一种有效进行任意单个子空间上skyline计算的有效方法CDCA。CDCA算法通过单元格之间的三种支配关系来缩减对象间的比较次数,从而有效降低子空间skyline计算的时间开销。另一方面,为了有效降低多个并发的子空间skyline查询的总时间开销,我们给出子空间树序列的概念。基于子空间树序列,我们有效确定各子空间skyline查询的执行顺序,并提出一种优化其执行性能的高效算法APMSSQ。APMSSQ算法利用如下两个方面来优化多个子空间skyline查询的总响应时间:①各子空间skyline对象集合之间的关系;以及②树路径上的各节点间的共享重复值查找策略。理论分析和实验结果表明,我们的方法显著优于现有的相关方法。(3)在分布式网络环境中,高效处理多个子空间上的skyline查询由于分布式网络是现有多数企业和单位使用的网络模式,而早期的C/S架构的网络能够方便地升级到超级节点架构(Super Peer Architecture:SPA)的分布式网络,因此,本文的第三个重要工作是研究在SPA架构的分布式网络中,如何高效进行多个不同子空间上的skyline查询。与以往研究簇划分和路由策略的相关工作不同,我们主要研究子空间skyline查询本身,而假定分布式网络的簇划分和路由策略已经确定。由于网络传输代价以及子空间skyline计算的时间开销决定了在SPA架构的分布式网络中,返回子空间skyline查询结果集的效率。因此,我们主要从优化这两方面代价入手给出有效的解决方法。本文所给出的解决方法能够通过控制单个网络节点对之间的冗余数据传输以及采用对象编码机制来有效降低网络节点间的数据传输量;并使用本文给出的多子空间skyline查询优化算法APMSSQ(见本文的第二个重要工作)来有效进行子空间skyline计算。理论分析和实验结果表明,我们的方法显著优于现有的相关方法。

论文目录

  • 目录
  • 摘要
  • Abstract
  • 第一章 绪论
  • 1.1 研究背景
  • 1.1.1 全空间skyline查询的概念
  • 1.1.2 Skyline查询结果集的特性
  • 1.1.3 子空间skyline查询的提出
  • 1.2 研究现状及其存在的问题
  • 1.3 研究内容和贡献
  • 1.4 本文组织结构
  • 第二章 相关研究工作
  • 2.1 全空间skyline查询及其应用
  • 2.2 子空间skyline查询及其应用
  • 第三章 有效解析子空间SKYLINE查询
  • 3.1 引言
  • 3.2 子空间skyline计算语义
  • 3.3 变换子空间skyline计算与关系操作间的执行顺序
  • 3.3.1 子空间skyline计算▽与选择σ间执行顺序变换的等价规则
  • 3.3.2 子空间级联skyline计算∞与选择σ间执行顺序变换的等价规则
  • 3.3.3 子空间skyline计算▽与投影π间执行顺序变换的等价规则
  • 3.3.4 子空间skyline计算▽与积×间执行顺序变换的等价规则
  • 3.3.5 子空间skyline计算▽与连接(?)间执行顺序变换的等价规则
  • 3.3.6 子空间skyline计算▽与并∪间执行顺序变换的等价规则
  • 3.4 执行顺序变换前后的代价评估
  • 3.4.1 子空间skyline计算▽与选择σ间执行顺序变换前后的代价评估
  • 3.4.2 子空间级联skyline计算∞与选择σ间执行顺序变换前后的代价评估
  • 3.4.3 子空间skyline计算▽与投影π间执行顺序变换前后的代价评估
  • 3.4.4 子空间skyline计算▽与积×间执行顺序变换前后的代价评估
  • 3.4.5 子空间skyline计算作▽与连接(?)间执行顺序变换前后的代价评估
  • 3.4.6 子空间skyline计算▽与并∪间执行顺序变换前后的代价评估
  • 3.5 实验评估
  • 3.5.1 实验一:查询时间随维度个数变化
  • 3.5.2 实验二:查询时间随表基数变化
  • 3.6 本章小结
  • 第四章 有效实施子空间SKYLINE查询
  • 4.1 引言
  • 4.2 SUBSKY算法
  • 4.3 有效处理任意单个子空间SKYLINE查询
  • 4.3.1 正规格索引结构
  • 4.3.2 CDCA算法描述利分析
  • 4.3.3 启发式剪枝技术
  • 4.4 优化多个子空间SKYLINE查询
  • 4.4.1 子空间树序列
  • 4.4.2 APMSSQ算法
  • 4.5 实验评估
  • 4.5.1 CDCA算法的性能实验
  • 4.5.2 ATP剪枝技术的性能实验
  • 4.5.3 APMSSQ算法的性能实验
  • 4.6 本章小节
  • 第五章 处理分布式网络中子空间SKYLINE查询
  • 5.1 引言
  • 5.1.1 SPA(Super Peer Architecture)架构的分布式网络
  • 5.1.2 现有工作存在的问题
  • 5.1.3 本章的研究内容和贡献
  • 5.1.4 本章的组织结构
  • 5.2 有效降低查询预处理阶段的数据传输量
  • 5.2.1 本文数据传输方法PDSQDN
  • 5.2.2 本文传输数据方法正确性和完备性
  • 5.3 有效处理超级节点上的子空间SKYLINE计算
  • 5.4 实验评估
  • 5.4.1 预处理阶段的性能评估
  • 5.4.2 评估总时间开销
  • 5.5 本章小节
  • 第六章 结论与展望
  • 6.1 结论
  • 6.2 展望
  • 参考文献
  • 博士阶段发表的论文
  • 参与的课题
  • 致谢
  • 相关论文文献

    标签:;  ;  ;  ;  ;  ;  ;  ;  ;  

    子空间SKYLINE查询若干关键问题的研究
    下载Doc文档

    猜你喜欢