试论子空间skyline查询若干关键问题的研究

《试论子空间skyline查询若干关键问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、复旦大学博士学位论文子空间SKYLINE查询若干关键问题的研究姓名：黄震华申请学位级别：博士专业：计算机软件与理论指导教师：汪卫20080310子空间SKYLINE查询若干关键问题的研究摘要摘要Skyline查询技术是近年来数据库邻域的一个研究重点和热点，这主要是因为该查询技术广泛应用于多标准决策系统、城市导航系统、数据挖掘和可视化、智能防御系统、以及地理信息系统等领域。现有的相关工作主要集中于研究全空间上的skyline查询，即它们假定用户所提交的是单个查询，并且查询所涉及的维度包含对象的所有属性。然而，在实际应用中，由于对象具有较大规模的全空间，而用户通常

2、只对部分子空间上的skyline对象集合感兴趣；同时，不同的用户可能关注不同的子空间，因此，现有的算法和数据结构无法满足子空间skyline查询在有效性和可扩展性上的需求。基于此，本文着重研究子空间skyline查询技术中的效率问题，主要包括如下3个关键方面：(1)有效解析用户提交的子空间skyline查询现有的研究工作不考虑传统关系操作(如选择、卡氏积和连接等)存在于子空间skyline查询的情况，而且没有考虑系统中同时存在多个不同子空间skyline查询的情况。因此，本文的一个重要工作是从提高查询性能出发，在逻辑层面上，考虑如何优化它们之间的执行顺序来缩减

3、子空间skyline查询的时间开销。我们将子空间skyline查询计算作为一个特殊的关系操作符(称之为子空间skyline操作符)，研究它与传统关系操作符间执行顺序变换的等价规则，以及达到这种等价变换所需要的附加条件。从而，基于这些等价变换规则和附加条件，通过改变子空间skyline操作符与传统关系操作符之间的执行顺序来有效提高查询的效率。另一方面，我们提供充分的理论证明来表明这些等价变换规则的J下确性；同时，给出执行顺序变换前后的时间开销的理论值来表明这些等价变换规则的有效性。最后，我们实施了大量的实验，实验结果表明，变换之后的时间开销显著低于变换之前的时间

4、开销。(2)有效实施用户提交的子空间skyline查询由于传统关系操作的实施算法现已较成熟，而现有关于在物理层面上实施子空间skyline计算的相关工作比较有限，而且它们的计算效率通常较低。因此，本文的第二个重要工作是考虑如何有效实施子空间skyline计算。我们从减少对象间的比较次数出发，基于正规格结构，给出一种有效进行任意单个子空间上skyline计算的有效方法CDCA。CDCA算法通过单元格之间的三种支配关系来缩减对象间的比较次数，从而有效降低子空间skyline计算的时间丌销。另一方第4页子空间SKYLINE查询若干关键问题的研究摘要面，为了有效降低多

5、个并发的子空间skyline查询的总时间开销，我们给出子空间树序列的概念。基于子空间树序列，我们有效确定各子空间skyline查询的执行顺序，并提出一种优化其执行性能的高效算法APMSSQ。APMSSQ算法利用如下两个方面来优化多个子空间skyline查询的总响应时间：①各子空间skyline对象集合之间的关系；以及②树路径上的各节点间的共享重复值查找策略。理论分析和实验结果表明，我们的方法显著优于现有的相关方法。(3)在分布式网络环境中，高效处理多个子空间上的skyline查询由于分布式网络是现有多数企业和单位使用的网络模式，而早期的C／S架构的网络能够方便

6、地升级到超级节点架构(SuperPeerArchitecture：SPA)的分布式网络，因此，本文的第三个重要工作是研究在SPA架构的分布式网络中，如何高效进行多个不同子空间上的skyline查询。与以往研究簇划分和路由策略的相关工作不同，我们主要研究子空间skyline查询本身，而假定分布式网络的簇划分和路由策略已经确定。由于网络传输代价以及子空间skyline计算的时间开销决定了在SPA架构的分布式网络中，返回子空间skyline查询结果集的效率。因此，我们主要从优化这两方面代价入手给出有效的解决方法。本文所给出的解决方法能够通过控制单个网络节点对之间的冗

7、余数据传输以及采用对象编码机制来有效降低网络节点间的数据传输量：并使用本文给出的多子空间skyline查询优化算法APMSSQ(见本文的第二个重要工作)来有效进行子空间skyline计算。理论分析和实验结果表明，我们的方法显著优于现有的相关方法。关键词：子空间、skyline查询、格支配、多查询优化、SPA网络、正规格索引、等价变换规则、分布式环境、冗余传输中图法分类号：TP311．13第5页子空间sKYLINE奎塑董王叁堡塑壁堕翌壅一—笾苎苎!丝．二--．．-——-—-_-———_-·-_____—_——_———‘——。’。。‘。。o。。。‘。。。。。’’。

8、。。’。。’—————————————