计算机研究与发展 ＩＳＳＮ １０００—１２３９／ＣＮ １ １－１７７７门ｒＰ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒ＇ｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ ４７（１１）：１９４７—１９５３，２０１０ 一种处理Ｓｋｙｌｉｎｅ查询的有效方法 黄震华 向 阳 薛永生。 刘啸岭。 （同济大学电子与信息工程学院 上海 ２０００９２） （厦门大学信息科学与技术学院 福建厦门 ３６１００５） 。（复旦大学信息科学与工程学院 上海 ２００４３３） （ｊｕｋｉｅ．ｈｕａｎｇ＠ｇｍａｉｌ．ｃｏｒｎ） Ａｎ Ｅｆｆｉｃｉｅｎｔ Ｍｅｔｈｏｄ ｆｏｒ Ｐｒｏｃｅｓｓｉｎｇ Ｓｋｙｌｉｎｅ Ｑｕｅｒｉｅｓ Ｈ ｕａｎｇ Ｚｈｅｎｈｕａ ，Ｘｉａｎｇ Ｙａｎｇ ，Ｘｕｅ Ｙｏｎｇｓｈｅｎｇ。，ａｎｄ Ｌｉｕ Ｘｉａｏｌｉｎｇ。 （Ｓｃｈｏｏ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ，Ｔｏｎｇｊｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２０００９２） （Ｓｃｈｏｏ ｏｆ Ｉｎｒｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｘｉａｍｅｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉａｍｅｎ，Ｆｕｊｉａｎ ３６１００５） （Ｓｃｈｏｏ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ ｅｎｇｉｎｅｅｒｉｎｇ，Ｆｕｄａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２００４３３） Ａｂｓｔｒａｃｔ Ｓｋｙｌｉｎｅ ｑｕｅｒｙ ｐｒｏｃｅｓｓｉｎｇ ｈａｓ ｒｅｃｅｎｔｌｙ ｒｅｃｅｉｖｅｄ ａ ｌｏｔ ｏｆ ａｔｔｅｎｔｉ ｏｎ ｉｎ ｄａｔａｂａｓｅ ｃｏｍｍｕｎｉｔｙ． Ｔｈｉｓ ｉｓ ｍａｉｎｌｙ ｄｕｅ ｔｏ ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｏｆ ｓｋｙｌｉｎｅ ｒｅｓｕｌｔｓ ｉｎ ｍａｎｙ ａｐｐｌｉｃａｔｉｏｎｓ，ｓｕｃｈ ａｓ ｍｕｌｔｉ—ｃｒｉｔｅｒｉａ ｄｅｃｉｓｉｏｎ ｍａｋｉｎｇ，ｄａｔａ ｍｉｎｉｎｇ，ａｎｄ ｕｓｅｒ—ｐｒｅｆｅｒｅｎｃｅ ｑｕｅｒｉｅｓ．Ｇｉｖｅｎ ａ ｓｅｔ ｏｆ ｋ－ｄｉｍｅｎｓｉｏｎａｌ ｏｂｊ ｅｃｔｓ，ｔｈｅ ｓｋｙｌｉｎｅ ｑｕｅｒｙ ｆｉｎｄｓ ｔｈｅ ｏｂｊｅｃｔｓ ｔｈａｔ ａｒｅ ｎｏｔ ｄｏｍｉｎａｔｅｄ ｂｙ ｏｔｈｅｒｓ．Ｗｈｅｎ ｕｓｅｒｓ ｉｓｓｕｅ ｍｕｌｔｉｐｌｅ ｄｉｆｆｅｒｅｎｔ ｄｉｍｅｎｓｉｏｎａｌ ｓｐａｃｅ ｓｋｙｌｉｎｅ ｑｕｅｒｅｉｓ ｓｉｍｕｌｔａｎｅｏｕｓｌｙ，ａｌｌ ｔｈｅ ｅｘｉｓｔｉｎｇ ｗｏｒｋｓ ｏｂｔａｉｎ ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｔｈｅｓｅ ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓ ｆｒｏｍ ｔｈｅ ｏｒｉｇｉｎａｌ ｒｅｌａｔｉｏｎａｌ ｔａｂｌｅ ｆｒｏｍ ｓｃｒａｔｃｈ．Ｃｌｅａｒｌｙ，ｔｈｅ ｅｘｉｓｔｉｎｇ ａｐｐｒｏａｃｈｅｓ ａｒｅ ｅｘｔｒｅｍｅｌｙ ｉｎｅｆｆｉｃｉｅｎｔ ａｓ ｔｈｅ ｃａｒｄｉｎａｌｉｔｙ ｏｆ ｔｈｅ ｏｒｉｇｉｎａｌ ｒｅｌａｔｉｏｎａｌ ｔａｂｌｅ ａｎｄ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓ ｉｎｃｒｅａｓｅ．Ｍｏｔｉｖａｔｅｄ ｂｙ ｔｈｅ ａｂｏｖｅ ｆａｃｔ，ａｎ ｅｆｆｉｃｉｅｎｔ ｍｅｔｈｏｄ，ｃａｌｌｅｄ ＥＡＰＳＱ（ｅｆｆｉｃｉｅｎｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｐｒｏｃｅｓｓｉｎｇ ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓ），ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｒｅｔｕｒｎ ｍ ｉｓｓｕｅｄ ｄｉｆｆｅｒｅｎｔ ｄｉｍｅｎｓｉｏｎａｌ—ｓｐａｃｅ ｓｋｙｌｉｎｅ ｑｕｅｒｅｉｓ ｛ＳＱ１，…，ＳＱ ）ｕｓｉｎｇ ｐｒｅｓｔｏｒｉｎｇ ｓｋｙｌｉｎｅ ｓｅｔｓ｛ＰＲｌ，…，ＰＲ ）．Ｔｈｅ ＰＡＰＳＱ ａｌｇｏｒｉｔｈｍ ａｄｅｑｕａｔｅｌｙ ｃｏｎｓｉｄｅｒｓ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｔｈｅ ｓｔｏｒａｇｅ ｍｅｃｈａｎｉｓｍ ｏｆ ｐｒｅｓｔｏｒｉｎｇ ｓｋｙｌｉｎｅ ｓｅｔｓ，ａｎｄ ａｄｏｐｔｓ ｔｈｅ ｃｏｎｃｅｐｔ ｏｆ ｃｏｎｔｒｉｂｕｔｉｏｎ ｍａｒｇｉｎ ｉｎ ｅｃｏｎｏｍｉｃｓ．Ｔｈｕｓ ｉｔ ｃａｎ ｅｆｆｉｃｉｅｎｔｌｙ ａｃｈｉｅｖｅ ｔｈｅ ｏｐｔｉｍａｌ ｓｔａｔｅ ｆｏｒ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ Ｔｒ／ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓ ｂｅｔｗｅｅｎ ｐｒｅｓｔｏｒｉｎｇ ｓｋｙｌｉｎｅ ｓｅｔｓ．ｗｈｉｃｈ ｃａｎ ｍａｒｋｅｄｌｙ ｉｍｐｒｏｖｅ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｆｏｒ ｐｒｏｃｅｓｓｉｎｇ ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓ．Ｍｏｒｅｏｖｅｒ，ｄｅｔａｉｌｅｄ ｔｈｅｏｒｅｔｉｃａｌ ａｎａｌｙｓｅｓ ａｎｄ ｅｘｔｅｎｓｉｖｅ ｅｘｐｅｒｉｍｅｎｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈａｔ ｏｕｒ ａｌｇｏｒｉｔｈｍ ｉＳ ｂｏｔｈ ｅｆｆｉｃｉｅｎｔ ａｎｄ ｅｆｆｅｃｔｉｖｅ． Ｋｅｙ ｗｏｒｄｓ ｓｋｙｌｉｎｅ；ｑｕｅｒｙ ｐｒｏｃｅｓｓｉｎｇ；ｒｅｌａｔｉｏｎａｌ ｔａｂｌｅ；ｃｏｎｔｒｉｂｕｔｉｏｎ ｍａｒｇｉｎ；ｑｕｅｒｙ ｏｐｔｉｍｉｚａｔｉｏｎ 摘要ｓｋｙｌｉｎｅ查询是近年来数据库领域的一个研究重点和热点．当系统中存在多个不同维空间上的 ｓｋｙｌｉｎｅ查询时，现有的工作均直接从底层关系表中获取这些ｓｋｙｌｉｎｅ查询的结果集．显然，当底层关系 表的基数较大且ｓｋｙｌｉｎｅ查询的个数较多时，现有方法的处理效率极其低下．基于此，提出一种使用预存 储的 个ｓｋｙｌｉｎｅ集合｛ＰＲ ，…，ＰＲ ｝来回答用户提交的 个不同维空间上的ｓｋｙｌｉｎｅ查询｛ＳＱ ，…， ＳＱ ｝的有效方法ＥＡＰＳＱ（ｅｆｆｉｃｉｅｎｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｐｒｏｃｅｓｓｉｎｇ ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓ）．算法充分考虑预存储的 收稿日期：２００８ １２ ２２；修回日期：２０１０～０４ ２２ 基金项目：国家自然科学基金项目（６０９０３０３２，７０７７１０７７）；教育部博士学科点专项科研基金项目（２００９００７２１２００５６）；国家“八六三”高技术研 究发展计划基金项目（２００８ＡＡ０４Ｚ１０６）；上海市科委科研计划基金项目（０８ＤＺｌ１２２３００）；上海市信息委专项基金项目（２００９０１０１５）； 福建省自然科学基金项目（Ａ０３１０００８）；同济大学青年优秀人才培养行动计划基金项目（０８００２１９０９３） １９４８ 计算机研究与发展２０１０，４７（１Ｉ） ｓｋｙｌｉｎｅ集合的编码机制，采用经济学中边际贡献（ｃｏｎｔｒｉｂｕｔｉｏｎ ｍａｒｇｉｎ）的概念，使得ｍ个用户提交的 ｓｋｙｌｉｎｅ查询在 个预存储的ｓｋｙｌｉｎｅ集合间的分配达到最佳状态，从而显著提高了处理用户ｍ个 ｓｋｙｌｉｎｅ查询的效率．实验评估表明，ＥＡＰＳＱ算法具有有效性和实用性． 关键词ｓｋｙｌｉｎｅ查询；查询处理；关系表；边际贡献；查询优化 中图法分类号ＴＰ３１１．１３２．３ ０ 引 言 ｓｋｙｌｉｎｅ查询处理是近年来数据库学科的一个 研究重点．该查询最早由Ｂｏｒｚｓｏｎｙｉ等人［＝１ 引进到 数据库领域中．随后，Ｃｈｏｍｉｃｋｉ等人 。 在ＢＮＬ算 法的基础上提出一种先进行对象排序，再进行比较 的查询方法ＳＦＳ．基于索引的方法最早由Ｋｏｓｓｍａｎｎ 等人ｌ４ 提出．而Ｐａｐａｄｉａｓ等人 。 指出ＮＮ算法的 缺陷，并提出一种基于排序Ｒ一树节点的方法ＢＢＳ， ＢＢＳ算法克服了ＮＮ算法冗余比较节点的不足，且 比ＮＮ算法具有更强的剪枝能力．Ｓｈａｒｉｆｚａｄｅｈ等 人＿７ 首次在空间数据库上研究ｓｋｙｌｉｎｅ查询，并给出 空间ｓｋｙｌｉｎｅ查询的概念．Ｌｉ等人ｌ８ 将ｓｋｙｌｉｎｅ查询 技术引进到时间序列研究邻域 来克服维度危机问 题¨１ ．Ｐｅｉ等人ｌ＝１ 等人考虑如何在不确定的数据集 上进行有效的ｓｋｙｌｉｎｅ查询计算，并给出一种新颖的 概率ｓｋｙｌｉｎｅ模型来解决对象出现概率不确定的情 况．Ｔａｏ等人 首次考虑当数据动态更新时，如何 高效维护ｓｋｙｌｉｎｅ查询结果集．而Ｗｕ等人 研究 在具有ＣＡＮ体系结构的分布式网络ｌｌ副中如何进行 有效的ｓｋｙｌｉｎｅ查询．值得注意的是，文献［１—１３］所 研究的是单个固定维空间上的ｓｋｙｌｉｎｅ查询效率，并 且均直接从底层关系表中获取查询结果集．因此，当 底层关系表的基数较大且ｓｋｙｌｉｎｅ查询的个数较多 时，这些文献所给方法的处理效率极其低下． 与本文研究较为接近的是文献［１５ ２ｏ］中的工 作，它们均是考虑多个不同维空间上的ｓｋｙｌｉｎｅ查询 效率．Ｐｅｉ等人＿】 借鉴（）ＬＡＰ应用领域的立方体 格，研究了不同维空间上ｓｋｙｌｉｎｅ查询的语义．与文 献［１５—１６］不同，Ｔａｏ等人＿１ 首次提出ＳＵＢＳＫＹ 算法来获取任意数量的维空间ｓｋｙｌｉｎｅ查询结果集． Ｂａｒｔｏｌｉｎｉ等人口 在２００８年的ＴｏＤＳ国际期刊上针 对ＳＵＢＳＫＹ算法的３个性能缺陷，基于内存Ｒ一树 索引给出一个有效算法ＳａＬＳａ．在文献Ｉ－２ｏ］中，Ｊｉｎ 等人提出了３个新颖的概念，即最大支配维空间、最 大受支配维空间和最大等价空间，并基于这３个概 念给出一个随机采样算法ＷＡＭＺ，来快速返回任意 维空间上ｓｋｙｌｉｎｅ对象集合．然而，这些方法虽然解 决了文献［１ １３］不能处理多个维空间ｓｋｙｌｉｎｅ查询 的问题，但是这些方法至少需要一次将底层关系表 从磁盘调入内存中，因此当底层关系表较大且查询 个数较多时，这些方法的处理效率也将变得低下． 随着大容量廉价磁盘的出现，使得采用预存储 的 个ｓｋｙｌｉｎｅ集合｛ＰＲ ，…，Ｐ尺 ｝来有效回答用户 提交的Ⅲ个不同维空间上的ｓｋｙｌｉｎｅ查询｛ＳＱ１，…， ５Ｑ ｝，成为克服现有方法低效率的首选技术．另一 方面，Ｈｕａｎｇ等人［ ｕ给出的两阶段方法（ｉｎｃｒｅｍｅｎｔａｌ ｍａｉｎｔｅｎａｎｃｅ ａｌｇｏｒｉｔｈｍ ｆｏｒ ＳｋｙＣｕｂｅ ｂａｓｅｄ ｏｎ ｉｄｅｎｔｉｆｙ ａｎｄ ｒｅｆｒｅｓｈ，ＩＭＡＳＣＩＲ）能够高效地维护预 存储的ｓｋｙｌｉｎｅ集合，从而为本文方法的可行性提供 了保证．为了便于描述，在下面的章节中，我们将“预 存储的ｓｋｙｌｉｎｅ集合”简称为“ｓｋｙｌｉｎｅ快照”． 基于以上２个事实，本文从优化ｍ个ｓｋｙｌｉｎｅ 查询在ｎ个ｓｋｙｌｉｎｅ快照间的分组出发，提出了一种 新颖的处理ｓｋｙｌｉｎｅ查询的有效算法ＥＡＰＳＱ （ｅｆｆｉｃｉｅｎｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｐｒｏｃｅｓｓｉｎｇ ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓ）． ＥＡＰＳＱ算法充分考虑 个ｓｋｙｌｉｎｅ快照的编码机 制，采用经济学中边际贡献的概念，使得ｍ个用户 提交的ｓｋｙｌｉｎｅ查询在 个ｓｋｙｌｉｎｅ快照间的分配达 到最佳状态，从而显著提高了处理用户 个ｓｋｙｌｉｎｅ 查询的效率．实验评估表明，ＥＡＰＳＱ算法具有有效 性和实用性． １ 问题描述 不失一般性，本文假定外部磁盘上存储有ｎ （ｎ≤２ 一１）个ｓｋｙｌｉｎｅ快照ＭＶ＝｛ＰＲｌ，…，ＰＲ ｝， 每个ｓｋｙｌｉｎｅ快照对应某一维空间上的ｓｋｙｌｉｎｅ集 合．同时，我们假定用户提交的 （ ≤２ 一１）个维 空间上ｓｋｙｌｉｎｅ查询为Ｑ一｛Ｓ Ｑ】，…，ＳＱ ）．根据文 献［２２］可知，ｓｋｙｌｉｎｅ快照ＰＲ （１≤ｉ≤７２）能够用于 回答用户查询ＳＱ，（１≤ｊ＿≤ｍ），当且仅当ＰＲ所对 应的维空问 是ＳＱ 所对应的维空间 的超集， 黄震华等：一种处理Ｓｋｙｌｉｎｅ查询的有效方法 即 Ｖ ．显然，当Ｖ 一Ｖ，时，ＰＲ 恰为查询ＳＱ， 所返回的结果．另一方面，当Ｖ Ｖ 成立时，使用 ＰＲ 回答查询ＳＱ 的时间代价由２部分组成：第１ 部分将ｓｋｙｌｉｎｅ快照ＰＲ 文件ＨＣＳ 调入内存的开 销 Ｍｖ（ＰＲ ）；第２部分由ＨＣＳ 产生查询ＳＱ，结果 集的ＣＰＵ开销ｔ。（ＳＱ，，Ｐ Ｒ，）． 第１部分时间代价 ｗ（ＰＲ ）比较容易获得，如 式（１）所示： ＰＲ 啪 ， （１） 其中ｓｉｚｅ（ＨＣＳ ）为文件ＨＣＳ 的大小，ｂｌｏｃｋ—ｓｉｚｅ为 内存块大小，而ｔｂ…ｌｏｃ 为传输一个内存块的时间开销． 下面，我们给出第２部分的代价ｔ。（ｓＱ，ＰＲ ）． 不失一般性，令 一｛ ，｛． 定理１ｌ２ ．假定ｓｋｙｌｉｎｅ快照ＰＲ 在维空间 上满足联合分布函数Ｆ（ ）和联合密度函数厂（ ）， 其中ｌｚ一（３ｃ “， ），那么ＳＱ，结果集基数的期望 值Ｅ（｛ＰＲ ｌ， ）可表示为 ｌＰＲ Ｉ ｘ Ｉ ｆ（ ）（１一Ｆ（Ｊｃ）） 职ｒ。。 ｄＥ．（２） 定理２ ．假定ｓｋｙｌｉｎｅ快照ＰＲ 在维空间Ｖ， 上满足联合分布函数Ｆ（ ）和联合密度函数厂（ ）， 其中 一（ｏｒ ，…， ），那么第２部分的时间代价ｔ。 （ＳＱ ，ＰＲ）可表示为 Ｉ ＰＲ Ｉ ’ ’一Ｅ（ ｌ， ）×Ｅ（ 一１， ＋１） 一１． （３） ｘ＝２ 基于上面的分析，我们接下来给出本文的问题 定义． 问题定义．假定Ｍ Ｍ 为用来回答用户提 交的ｍ个ｓｋｙｌｉｎｅ查询Ｑ一｛ＳＱ ，…，ＳＱ ｝的 ｓｋｙｌｉｎｅ快照集合，且查询ＳＱ，（１≤ ≤ ）的结果集 从ｓｋｙｌｉｎｅ快照ｍｙ（ＳＱ ）（ （ＳＱ，）∈Ｍ ）的文件 ｈｃｓ（ＳＱ）中获取，那么这 个ｓｋｙｌｉｎｅ查询的总时 间代价由２部分组成：其中第１部分为将Ｍ 中所 有ｓｋｙｌｉｎｅ快照从磁盘调入内存的时间开销；第２部 分为由Ｍ 来获取 个ｓｋｙｌｉｎｅ查询结果集的时间 开销，即总时间代价可表示为 Ｔ ｌ（ＭＶ ，Ｑ）一∑ｔ￣（ＰＲ ）＋ ｐＲ∈Ｍｖ ∈Ｑ・～｛ｓＱ１ ∈＾Ⅳ ∑ｔＱ（ＳＱ ，ｍｙ（ＳＱ ））． （４） ｉ我们的目标是将每个ｓｋｙｌｉｎｅ查询ｓＱ，分配给 最合适的ｓｋｙｌｉｎｅ快照 ｕ（ｓＱ），使得总时间代价 Ｔ 。 最小． ２￣ＡＩ＇ＳＱ算法描述 由于要精确得到最优分配方案（即时间代价 Ｔ 。 取最小值）是ＮＰ—ｈａｒｄ问题，因此在这一节中我 们给出一个多项式时间复杂度的近似算法ＥＡＰＳＱ． 并且我们从理论上证明ＥＡＰＳＱ算法具有单调性以 及（ｅ一１）／ｅ≈Ｏ．６３的下界收益． ＥＡＰＳＱ算法的基本思想是：将每个￣ｋｙｌｉｎｅ查 询ｓＱ 分配给最合适的ｓｋｙｌｉｎｅ快照ｍ （ｓＱ，），从 而使得式（４）给出的总时间代价Ｔ （Ｍ ，Ｑ）最 小．基于边际贡献的概念，在每一次循环中，ＥＡＰＳＱ 算法完成如下３个方面的工作：１）获取收益最大的 ｓｋｙｌｉｎｅ快照Ｂｖｉｅｗ；２）对于未分配给任何ｓｋｙｌｉｎｅ 快照的每个查询ＳＱ ，如果Ｂｖｉｅｗ所对应的维空间 Ｖ 是ＳＱ 所对应的维空间 ，的超集，那么将ＳＱ， 分配给Ｂｖｉｅｗ来回答；３）对于在之前的循环中已分 配给其他ｓｋｙｌｉｎｅ快照的每个查询ＳＱ（记该 ｓｋｙｌｉｎｅ快照为ｆｖ），如果由Ｂｖｉｅｗ回答ＳＱ 的代价 低于由ｆｖ回答ＳＱ 的代价，那么将ＳＱ重新分配给 Ｂｖｉｅｗ来回答．当所有ｍ个用户提交的ｓｋｙｌｉｎｅ查 询均分配完毕，则ＥＡＰＳＱ算法停止． ＥＡＰＳＱ算法伪码如下所示． 算法１．ＥＡＰＳＱ（Ｍ ，Ｑ）． ／＊ＭＶ＝｛ＰＲ ，…，ＰＲ ）为ｓｋｙｌｉｎｅ快照集合； Ｑ一｛ＳＱ ，…，ＳＱ ）为用户提交的ｓｋｙｌｉｎｅ查询集 合＊｜ ①ＵＱ—Ｑ； ②ＬＭ—Ｍ ； ③Ｆｏｒ 一１ ｔｏ ｌ Ｑ ｌ Ｄｏ ④ 获取能回答ＳＱ，的所有ｓｋｙｌｉｎｅ快照构成 的集合ＣＭＶ（ｓＱ）； ⑤ ｍｉｎＴ（ＳＱ，）一 ｒａｉｎ （ （ ）＋ｔＱ（ＳＱ，， Ｖ ∈ Ｖ【 ） ））； ⑥Ｒｅｐｅａｔ ⑦ ￡Ｐ ＤＢ 一。。； ⑧ Ｆｏｒ ＵＭ中的每个ｓｋｙｌｉｎｅ快照ＰＲ Ｄｏ ⑨ 获取能被ＰＲ 回答的所有ｓｋｙｌｉｎｅ查询 构成的集合ＣＳ—Ｑ（ＰＲ ）； ⑩ △Ｑ—ＣＳ—Ｑ（ＰＲ ）ｎＵＱ； ⑥ ＡＣｏｓｔ￣－∑ａｒｉｎ Ｔ（ＳＱ，）； Ｖ △。 ⑥ ＶＣｏｓｔ—一Ｔ 。 （｛Ｐ尺：），△Ｑ）； ⑩ Ｂ ￣－－ＡＣｏｓｔ－－ＶＣｏｓｔ； ⑩ Ｉｆ Ｂ ＞ｔｅｍｐＢ Ｔｈｅｎ ⑥ ｆＰ Ｂ—Ｂ ；Ｂｖｉｅｗ＊－ＰＲ。； ⑩ ＡＳＱ（Ｂｖｉｅｗ）一△Ｑ； ⑩ ＵＱ—ＵＱ一△Ｑ； ⑩ ＣＡ＋一ＣＳＱ（Ｂｖｉｅｗ）一ＡＳＱ（Ｂｖｉｅｗ）； ⑩ ＦＳ一｛ｆｖ ｌ ｆｖＥ Ｍ ＾ｆｖ ＵＭ＾ＣＡ ｎ ＡＳ—Ｑ（＿厂 ）≠ ｝； ⑩ 调用函数尺ＡＱＶ（ＦＳ，Ｂｖｉｅｗ，ＣＡ）； ⑨ Ｍ一【 ～｛Ｂｖｉｅｗ｝； ③Ｕｎｔｉｌ ＵＱ一 ． 注意，在算法１中，步骤⑧～⑥完成ＥＡＰＳＱ 算法的第一方面Ｔ作，步骤⑩完成ＥＡＰＳＱ算法的 第二方面＿Ｔ作，而步骤⑩中的函数ＲＡＱ （ＦＳ， Ｂｖｉｅｗ，ｃＡ）完成ＥＡＰＳＱ算法的第三方面工作．下 面，我们具体给出函数ＲＡＱＶ（ＦＳ，Ｂｖｉｅｚｅ，ＣＡ）的执 行过程． 算法２．ＲＡＱ （ＦＳ，Ｂｖｉｅｗ，ＣＡ）． ／＊ＲＡＱＶ检查ＣＡ中每个ｓｋｙｌｉｎｅ查询ｑ，如果 ｇ已分配给ｓｋｙｌｉｎｅ快照ｆｖ∈ＦＳ，但是ｑ由Ｂｖｉｅｗ 回答的代价低于由ｆｖ回答的代价，那么将ｑ重新分 配给Ｂｖｉｅｗ来回答＊／ ①ＦＳＣｏｓｔ￣－Ｏ；ＢｖｉｅｗＣｏｓｔ￣－Ｏ； ②Ｆｏｒ ＦＳ中每个ｓｋｙｌｉｎｅ快照ｉｖ Ｄｏ ③ 获取已分配给ｆｖ回答的所有ｓｋｙｌｉｎｅ查 询构成的集合ＡＳ—Ｑ（ｆｖ￣； ④ ＡＱ（ｆｖ）一ＣＡｎＡＳ—Ｑ（ｆｖ）； ⑤ １ｆ ＡＱ（ｆｖ）＝ＡＳ—Ｑ（ｆｖ）Ｔｈｅｎ ⑥ ＦＳ—Ｃｏｓｆ—ＦＳ—Ｃｏｓｔ＋Ｔｔ ｌ（｛ ），△Ｑ）； ⑦ Ｅｌｓｅ ⑧ ＦＳＣｏ时一Ｆ５一Ｃｏ ＋∑ｔＱ（ｑ， ）； ｑＥＡＱ（ ） ⑨Ｂｖｉｅｗ—Ｃｏｓｔ一ｑＥ—∑ＡＱ（ ） ｔｏ（ｇ，Ｂｖｉｅｗ）； ⑩Ｉｆ Ｂｖｉｅｗ—Ｃｏｓｔ￣ＦＳ—Ｃｏｓｔ Ｔｈｅｎ ⑩ ＡＳＱ（Ｂｖｉｅｗ）一ＡＳＱ（Ｂｖｉｅｗ）Ｕ ＣＡ； ⑥Ｆｏｒ ＦＳ中每个ｓｋｙｌｉｎｅ快照－厂 Ｄｏ ⑩ ＡＳ—Ｑ（ｆｖ）＋一ＡＳ—Ｑ（ｆｖ）一ＡＱ（／、 ）； ⑩ Ｉｆ ＡＳＱ（ｆｖ）一 Ｔｈｅｎ ⑥ ＵＭ一【 ７ＭＵ｛． ）． ＥＡＰＳＱ算法具有如下３个重要性质：１）ＥＡＰＳＱ 算法在多项式时间复杂度内返回查询的分配方案； ２）ＥＡＰＳＱ算法具有单调性，即预存储的ｓｋｙｌｉｎｅ快 照越多，ＥＡＰＳＱ算法产生的分配方案越有效； ３）ＥＡＰＳＱ算法产生的分配方案的下界为（ｅ一１）／ｅ．ｅ 这３个性质保证了ＥＡＰＳＱ算法的有效性，即性质１ 计算机研究与发展２０１０，４７（１１） 保证ＥＡＰＳＱ算法能够快速返回用户所提交查询的 分配方案；性质２确保ＥＡＰＳＱ算法的响应时间与 磁盘空间成正相关性；而性质３保证了在最坏情况 下，ＥＡＰＳＱ算法所产生分配方案的运行效率不会 低于最优运行效率的（ｅ一１）／ｅ￣－－６３ ． 接下来，我们从理论上证明ＥＡＰＳＱ算法这３ 个性质的正确性． 定理３．ＥＡＰＳＱ算法的时间复杂度为ｏ（ＩＱＩ ・ ｌ ＭＶ｛），其中Ｉ Ｑ ｆ为用户提交的ｓｋｙｌｉｎｅ查询的个 数，而｛Ｍ ｆ为ｓｋｙｌｉｎｅ快照的个数． 定理４．假定Ｍ 和ＥＰ 分别为预存储的 ｓｋｙｌｉｎｅ快照集合以及在Ｍ 的基础上产生的查询 分配方案，令ＴＣ（ＥＰ ）为按分配方案ＥＰ 处理所 有查询的时间开销．那么有：Ｖ ，Ｙ，Ｍ Ｍ ＴＣ（ＥＰ ）≥ＴＣ（ＥＰ ）． 定理５．记使用ＥＡＰＳＱ算法获取分配方案ＥＰ 所需的ｓｋｙｌｉｎｅ快照个数为叫，而记精确得到最优分 配方案ＯＰ所需的ｓｋｙｌｉｎｅ快照个数为愚，并假定 尼≤ ．那么有 ＴＣ（ ＢＰ ）Ｔ ＯＰ Ｃ（ ） ≥ ｅ ￣ｏ．６３～ ，’ 其中方案ＢＰ为不使用任何ｓｋｙｌｉｎｅ快照，而ＴＣ （ＸＸ）为按分配方案ＸＸ处理所有查询的时间开销． ３算法实验评估 实验评估用到２类数据集：综合数据集ＳＮＤ， 由文献［１］中的数据产生器生成；实际数据集ＣＤＳ， 为Ｃｈｉｂａ医学院从１９８０年开始收集到１９９９年为止 的胶原质疾病统计数据．在实验中，我们产生ｗ个 ｓｋｙｌｉｎｅ查询，Ｗ的取值在１０～９Ｏ间变化；同时，我 们产生Ｋ个ｓｋｙｌｉｎｅ快照，其中Ｋ的取值在２Ｏ～６Ｏ 问变化．与ＥＡＰＳＱ算法比较的方法有６个：１）对于 每个ｓｋｙｌｉｎｅ查询ｑ，随机选择一个ｓｋｙｌｉｎｅ快照 来回答ｑ，我们称该方法为ＮＡＩＶＥ算法；２）对于每 个ｓｋｙｌｉｎｅ查询ｑ，选择回答ｑ代价最小的ｓｋｙｌｉｎｅ 快照ｍｙ来回答ｑ，我们称该方法为ＬＯＦＡ算法；３） 文献［１５—１６］给出的ＳＫＹＥＹ算法；４）文献Ｅ１７一］８Ｊ 给出的ＳＵＢＳＫＹ算法；５）文献Ｅ１９］中给出的ＳａＬＳａ 算法；６）文献［２Ｏ］给出的ＷＡＭＺ算法． ３．１综合数据集ＳＮＤ上的实验评估 在本节中，我们评估本文算法ＥＡＰＳＱ产生的 查询分配方案在综合数据集ＳＮＤ上的性能．实验分 为２组． 在第１组实验中，查询个数固定为７０，ｓｋｙｌｉｎｅ 黄震华等：一种处理Ｓｋｙｌｉｎｅ查询的有效方法 快照个数在２Ｏ～６０问变化．图１显示了该组的实验 结果． —斗一Ｎａｉｖｅ——；Ｉ（一ＬＯＦＡ －￣－－ＥＡＰＳＱ —＿．◆＿一ＳＫＹＥＹ—＿－ｒ．一ＳＵＢＳＫＹ—＿｜●一ＳａＬＳａ —— ＷＡＭＺ ＼ ｇ 兰 Ｎｕｍｂｅｒ ｏｆ Ｓｋｙｌｉｎｅ Ｓｎａｐｓｈｏｔｓ Ｆｉｇ．１ Ｑｕｅｒｙ ｔｉｍｅ ＶＳ．ｎｕｍｂｅｒ ｏｆ ｓｋｙｌｉｎｅ ｓｎａｐｓｈｏｔｓ ｏｎ ＳＮＤ ｄａｔａｓｅｔ． 图１ ＳＮＤ上查询运行时间随ｓｋｙｌｉｎｅ快照个数变化实验 从图１中，我们可以看出，本文算法ＥＡＰＳＱ产 生的查询分配方案的性能在各种情况下均优于其余 ６个算法．这主要是因为：ＥＡＰＳＱ算法充分考虑了 数据对象的存储机制，并且能够使得这７０个维 空间上ｓｋｙｌｉｎｅ查询在多个ｓｋｙｌｉｎｅ快照间的分配达 到最佳状态；对于Ｎａｉｖｅ和Ｉ ＯＦＡ算法来说，它们 虽然考虑了使用ｓｋｙｌｉｎｅ快照，但没有考虑其优化分 配策略；而对于ＳＫＹＥＹ，ＳＵＢＳＫＹ，ＳａＩ Ｓａ和ｗＡＭＺ 算法来说，它们需要将底层关系表从硬盘调入内存 中．另外，我们注意到，ＳＫＹＥＹ，ＳＵＢＳＫＹ，ＳａＩ Ｓａ和 ＷＡＭＺ这４个算法的运行时间与ｓｋｙｌｉｎｅ快照的个 数无关，这是显然的．因为这些算法的实施不涉及到 ｓｋｙｌｉｎｅ快照．此外，我们还发现当ｓｋｙｌｉｎｅ快照个数 逐渐增多时，ＥＡＰＳＱ算法的优越程度越来越高． 在第２组实验中ｓｋｙｌｉｎｅ快照个数固定为５０， 查询个数在ｌ０ｂ９０间变化．图２显示了该组的实验 结果． —｝一Ｎａ￣＇ｖｅ—－） 一ＬＯＦＡ －￣－－ＥＡＰＳＱ —＿． 一ＳＫＹＥＹ—■广ＳＵＢＳＫＹ—｜ —ＳａＬＳａ —｛ ～ＷＡⅣ【Ｚ 呐 ＼ ｇ 兰 Ｆｉｇ．２ Ｑｕｅｒｙ ｔｉｍｅ ｖｓ．ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓ 图２查询运行时间随ｓｋｙｌｉｎｅ查询个数变化实验 与第１组实验结果类似，在图２中，我们可以看 出，本文算法ＥＡＰＳＱ产生的查询分配方案的性能 在查询个数的各种取值下均优于其余６个算法．另 外，我们注意到，在这组实验中，ＳＫＹＥＹ算法的运 行时间与查询个数无关，而其余５个算法的运行时 间均与查询个数有关．这主要是因为ＳＫＹＥＹ算法 返回全部２５５个维空间上的ｓｋｙｌｉｎｅ查询结果集，而 其他５个算法确切返回实验参数所指定的维空间 ｓｋｙｌｉｎｅ查询结果集．此外，我们还发现，当查询个数 逐渐增大时，ＥＡＰＳＱ算法的优越程度越来越高．这 主要是因为ＥＡＰＳＱ算法产生的查询分配方案只需 要调入层次联合代理文件进内存即可，而不需要调 入ｓｋｙｌｉｎｅ快照本身，因此，ＥＡＰＳＱ算法产生的查 询分配方案能够节省大量的ｉ／ｏ开销． ３．２ 实际数据集ＣＤＳ上的实验评估 在本节中，我们评估本文算法ＥＡＰＳＱ产生的 查询分配方案在实际数据集ＳＮＤ上的性能．为了简 单，我们主要评估当ｓｋｙｌｉｎｅ快照个数变化时，ＥＡＰＳＱ 算法和Ｎａｉｖｅ，ＬＯＦＡ算法产生的查询分配方案的 运行时间．与３．１节的第１组实验设置相同，我们固 定查询个数为７Ｏ，并让ｓｋｙｌｉｎｅ快照个数在２０～６Ｏ 间变化．图３显示了该组的实验结果． —＋一Ｎａｉｖｅ— ＬｏＦＡ—ｌ×一ＥＡＰＳＱ ——◆一ＳＫＹＥＹ—１ 一ＳＵＢＳＫＹ—－－．＿一ＳａＬＳａ —＿Ｅ 一ＷＡＭＺ ＼ ｇ 芒． 兰 Ｆｉｇ．３ Ｑｕｅｒｙ ｔｉｍｅ ＶＮ．ｎｕｍｂｅｒ ｏｆ ｓｋｙｌｉｎｅ ｓｎａｐｓｈｏｔｓ ｏｎ ＣＤＳ ｄａｔａｓｅｔ． 图３ ＣＤＳ上查询运行时间随ｓｋｙｌｉｎｅ快照个数变化实验 从图３中，我们同样可以看出，本文算法ＥＡＰＳＱ 产生的查询分配方案的性能在各种情况下均优于其 他６个算法．另一方面，与图１中的曲线图相比我们 发现，在这组实验中，当ｓｋｙｌｉｎｅ快照个数逐渐增多 时，ＥＡＰＳＱ算法的优越程度没有图１中ＥＡＰＳＱ算 法的优越程度高．这主要是因为，图１中实验的综合 数据集基数为５×１Ｏ ，而在这组实验中，实际数据 集的基数仅约为２ ｘ １０ ．因此，在这组实验中，层次 １９５２ 联合代理文件所占ｓｋｙｌｉｎｅ快照容量的百分比较小， 从而导致ＥＡＰＳＱ算法的优越程度没有图１中 ＥＡＰＳＱ算法的优越程度高．另一方面，我们注意到 与综合数据集ＳＮＤ相比，这６个算法在实际数据集 ＳＮＤ上平均处理一个数据块（６４ ＫＢ）的时间较长． 这主要是因为实际数据集ＣＤＳ的反相关性比综合 数据集ＳＮＤ高，即实际数据集ＣＤＳ中的ｓｋｙｌｉｎｅ对 象所占的百分比较综合数据集ＳＮＤ大，因此它需要 更多的对象比较时问． ４结论与将来工作 本文从优化ｍ个用户ｓｋｙｌｉｎｅ查询在 个ｓｋｙｌｉｎｅ 快照间的分组出发，提出了一种新颖的处理ｓｋｙｌｉｎｅ 查询的有效算法ＥＡＰＳ Ｑ．ＥＡＰＳＱ算法充分考虑，２ 个ｓｋｙｌｉｎｅ快照的编码机制，采用经济学中边际贡献 的概念，使得 个用户提交的ｓｋｙｌｉｎｅ查询在 个 ｓｋｙｌｉｎｅ快照间的分配达到最佳状态，从而显著提高 了处理用户ｍ个ｓｋｙｌｉｎｅ查询的效率．实验评估表 明，ＥＡＰＳＱ算法具有有效性和实用性． 我们将来比较重要和感兴趣的后续Ｔ作包括： 设计比层次联合代理更有效的编码机制，从而进一 步降低算法的Ｉ／Ｏ开销和内存消耗；在构造查询分 配方案方面，引进参数因子来平衡构造查询分配方 案的时间开销与ｓｋｙｌｉｎｅ查询的时问开销． 参 考 文 献 Ｌ】］ Ｂｏｒｚｓｏｎｙｉ Ｓ，Ｋｏｓｓｍａｎｎ Ｄ，Ｓｔｏｃｋｅｒ Ｋ．Ｔｈｅ ｓｋｙｌｉｎｅ ｏｐｅｒａｔｏｒ ［ｃ］／Ｐｒｏｃ ｏｆ ｔｈｅ Ｉｎｔ Ｃｏｎｆ ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ．Ｌｏｓ Ａｌａｍｉｔｏｓ，ＣＡ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００１：４２１—４３０ ［ｚ３ Ｃｈｏｍｉｃｋｉ ｊ，Ｇｏｄｆｒｅｙ Ｐ，Ｇｒｙｚ ｊ，ｅｔ ａ／． Ｓｋ５ ｈｎｅ ｗｉｘｈ ｐｒｅｓｏｒｔｉｎｇ［ｃ］／Ｐｒｏｃ ｏｆ ｔｈｅ Ｉｎｔ Ｃｏｎ｛ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ． Ｌｏｓ Ａｌａｍｉｔｏｓ，ＣＡ，ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００３：７１ ７－７１９ ［３］ Ｈｕａｎｇ Ｚｈｅｎｈｕａ，Ｗａｎｇ Ｗｅｉ．Ａｎ ａｌｇｅｂｒａ ｆｏｒ ｓｋｙｌｉｎｅ ｑｕｅｒｙ ｐｒｏｃｅｓｓｉｎｇ ｄａｔａ ｃｕｂｅ口］．Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ，２００７，４４（６）：９９０－９９９（ｉｎ Ｃｈｉｎｅｓｅ） （黄震华，汪卫．Ｓｋｙｌｉｎｅ查询处理数据立方体代数［Ｊ］．计算 机研究与发展，２００７，４４（６）：９９０—９９９） Ｅ４３ Ｋｏｓｓｍａｎｎ Ｄ，Ｒａｍｓａｋ Ｆ，Ｒｏｓｔ Ｓ．Ｓｈｏｏｔｉｎｇ ｓｔａｒｓ ｉｎ ｔｈｅ ｓｋｙ： Ａｎ ｏｎｌｉｎｅ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓ［ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ Ｉｎｔ Ｃｏｎｆ ｏｎ Ｖｅｒｙ Ｌａｒｇｅ Ｄａｔａ Ｂａｓｅｓ．Ｓａｎ Ｆｒａｎｃｉｓｃｏ，ＣＡ：Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ，２００２：２９０—３０２ ［５］ Ｐａｐａｄｉａｓ Ｄ，Ｔａｏ Ｙ，Ｆｕ Ｇ，ｅｔ ａ１．Ｐｒｏｇｒｅｓｓｉｖｅ ｓｋｙｌｉｎｅ ｃｏｍｐｕｔａｔｉｏｎ ｉｎ ｄａｔａ ｓｙｓｔｅｍｓ［Ｊ］．ＡＣＭ Ｔｒａｎｓ ｏｎ Ｄａｔａｂａｓｅ Ｓｙｓｔｅｍｓ，２００５，３０（１）：４ｌ一８２ 计算机研究与发展２０１０，４７（１１） ［６］ Ｐａｐａｄｉａｓ Ｄ，Ｔａｏ Ｙ，Ｆｕ Ｇ，ｅｔ ａ１．Ａｎ ｏｐｔｉｍａｌ ａｎｄ ｐｒｏｇｒｅｓｓｉｖｅ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓ［ｃ］／［Ｐｒｏｅ ｏｆ ｔｈｅ ＡＣＭ ＳＩＧＭＯＤ Ｉｎｔ Ｃｏｎｆ ｏｎ Ｍａｎａｇｅｍｅｎｔ ｏｆ Ｄａｔａ．Ｎｅｗ Ｙｏｒｋ： ＡＣＭ，２００３：４６７－４７８ ［７］ Ｓｈａｒｉｆｚａｄｅｈ Ｍ，Ｓｈａｈａｈｉ Ｃ．Ｔｈｅ ｓｐａｔｉａｌ ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓ［ｃ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ Ｉｎｔ Ｃｏｎｆ ｏｎ Ｖｅｒｙ Ｌａｒｇｅ Ｄａｔａ Ｂａｓｅｓ．Ｎｅｗ Ｙｏｒｋ： ＡＣＭ，２００６：７５１—７６２ ［８］ Ｌｉ Ｑ．Ｌｏｐｅｚ Ｉ ，Ｍｏｏｎ Ｂ．Ｓｋｙｌｉｎｅ ｉｎｄｅｘ ｆｏｒ ｔｉｍｅ ｓｅｒｉｅｓ ｄａｔａ ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ， ２００４，１ ６（６）：６６９－６８４ ［９］ Ｄｕａｎ Ｊｉａｎｇｊｉａｏ，Ｘｕｃ Ｙｏｎｇｓｈｅｎｇ，Ｌｉｎ Ｚｉｙｕ，ｅｔ ａ１．Ａ ｎｏｖｅｌ ｈｉｄｄｅｎ Ｍａｒｋｏｖ ｍｏｄｅｌ—ｂａｓｅｄ ｈｉｅｒａｒｃｈｉｃａｌ ｔｉｍｅ－ｓｅｒｉｅｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ，２００６，４３（１）：６１—６７（ｉｎ Ｃｈｉｎｅｓｅ） （段江娇，薛永生，林子雨，等．一种新的基于隐Ｍａｒｋｏｖ模 型的分层时间序列聚类算法ＥＪ］．计算机研究与发展，２００６， ４３（１）：６ｉ－６７） ［ｉＯ］ Ｐａｐａｄｉｍｉｔｒｉｏｕ Ｓ，Ｙｕ Ｐ．Ｏｐｔｉｍａｌ ｍｕｌｔｉ ｓｃａｌｅ ｐａｔｔｅｒｎｓ ｉｎ ｔｉｍｅ ｓｅｒｉｅｓ ｓｔｒｅａｍｓ［ｃ］／Ｐｒｏｃ ｏｆ ｔｈｅ ＡＣＭ ＳＩＧＭＯＤ Ｉｎｔ Ｃｏｎｆ ｏｎ Ｍａｎａｇｅｍｅｎｔ ｏｆ Ｄａｔａ．Ｎｅｗ Ｙｏｒｋ：ＡＧＭ，２００６：６４７—６５８ ［１１］ Ｐｅｉ Ｊ，Ｊｉａｎｇ Ｂ，Ｌｉｎ Ｘ，ｅｔ ａ１．Ｐｒｏｂａｈｉｌｉｓｔｉｃ ｓｋｙｌｉｎｅｓ ｏｎ ｕｎｃｅｒｔａｉｎ ｄａｔａ［ｃ］／Ｐｒｏｃ ｏｆ ｔｈｅ Ｉｎｔ Ｃｏｎｆ ｏｎ Ｖｅｒｙ Ｌａｒｇｅ Ｄａｔａ Ｂａｓｅｓ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ，２００７：６４１—６５２ ［１２］ Ｔａｏ Ｙ，Ｐａｐａｄｉａｓ Ｄ．Ｍａｉｎｔａｉｎｉｎｇ ｓｌｉｄｉｎｇ ｗｉｎｄｏｗ ｓｋｙｌｉｎｅｓ ｏｎ ｄａｔａ ｓｔｒｅａｍｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ。２００６，１８（３）：３７７—３９１ ［ｉ３］ Ｗｕ Ｐ，Ｚｈａｎｇ Ｃ，Ｆｅｎｇ Ｙ，ｅｔ ａ１．Ｐａｒａｌｌｅｌｉｚｉｎｇ ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓ ｆｏｒ ｓｃａｌａｂｌｅ ｄｉｓｔｒｉｂｕｔｉｏｎ［ｃ］／［Ｐｒｏｃ ｏｆ ｔｈｅ Ｉｎｔ Ｃｏｎｆ ｏｎ Ｅｘｔｅｎｄｉｎｇ Ｄａｔａｈａｓｅ Ｔｅｃｈｎｏｌｏｇｙ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２００６： １１ ２－Ｉ ３０ ［Ｉ４］ Ｃａｍｐｂｅｌｌ Ｂ．Ａｍｏｒｔｉｓｅｄ ｍｅｍｏｒｙ ａｎａｌｙｓｉｓ ｕｓｉｎｇ ｔｈｅ ｄｅｐｔｈ ｏｆ ｄａｔａ ｓｔｒｕｃｔｕｒｅｓ［ｃ］／Ｐｒｏｃ ｏｆ ｔｈｅ １８ｔｈ Ｉｎｔ Ｃｏｎｆ ｏｎ Ｅｕｒｏｐｅａｎ Ｓｙｍｐ ｏｎ Ｐｒｏｇｒａｍｍｉｎｇ．Ｌｏｓ Ａｌａｍｉｔｏｓ，ＣＡ：［ＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００９：１９０—２０４ ［１５］ Ｐｅｉ Ｊ，Ｊｉｎ Ｗ，Ｅｓｔｅｒ Ｍ，ｅｔ ａ１．Ｃａｔｃｈｉｎｇ ｔｈｅ ｂｅｓｔ ｖｉｅｗｓ ｏｆ ｓｋｙｌｉｎｅ：Ａ ｓｅｍａｎｔｉｃ ａｐｐｒｏａｃｈ ｂａｓｅｄ ｏｎ ｄｅｃｉｓｉｖｅ ｓｕｂｓｐａｃｅｓ ［ｃ］ｆＷｒｏｅ ｏｆ ｔｈｅ Ｉｎｔ Ｃｏａｌ ｏｕｔ Ｖｅｒｙ Ｌａｒｇｅ Ｄａｔａ Ｂａｓｅｓ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ，２００５：３１５－３２６ ［１６］ Ｐｅｉ Ｊ，Ｙｕａｎ Ｙ，Ｌｉｎ Ｘ，ｅｔ ａ１．Ｔｏｗａｒｄｓ ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ ｓｕｂｓｐａｃｅ ｓｋｙｌｉｎｅ ａｎａｌｙｓｉｓ ＥＪ］．ＡＣＭ Ｔｒａｎｓ ｏｎ Ｄａｔａｂａｓｅ Ｓｙｓｔｅｍｓ，２００６，３１（４）：６４３—６９７ ［１７］ Ｔａｏ Ｙ，Ｘｉａｏ Ｘ，Ｐｅｉ Ｊ．Ｓｕｂｓｋｙ：Ｅｆｆｉｃｉｅｎｔ ｃｏｍｐｕｔａｔｉｏｎ ｏｆ ｓｋｙｌｉｎｅｓ ｉｎ ｓｕｂｓｐａｃｅｓ ＥＣ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ｌｎｔ Ｃｏｎｆ ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ．Ｌｏｓ Ａｌａｍｉｔｏｓ，ＣＡ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ， ２００６：６５－７４ ［１８］ Ｔａ。Ｙ，Ｘｉａｏ Ｘ．Ｅｆｆｉｃｉｅｎｔ ｓｋｙｌｉｎｅ ａｎｄ ｔｏｐ—ｋ ｒｅｔｒｉｅｖｅｌ ｉｎ ｓｕｂｓｐａｃｅｓ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ．２００７，１９（８）：１０７２—１０８８ ［１９］ Ｂａｒｔｏｌｉｎｉ Ｉ，Ｃｉａｃｃｉａ Ｐ，Ｐａｔｄｌａ Ｍ．Ｅｆｆｉｃｉｅｎｔ ｓｏｒｔ－ｂａｓｅｄ ｓｋｙｌｉｎｅ ｅｖａｌｕａｔｉｏｎ［Ｊ］．ＡＣＭ Ｔｒａｎｓ ｏｎ Ｄａｔａｂａｓｅ Ｓｙｓｔｅｍｓ，２００８，３３ （４）：１６３２—１６９５ 黄震华等：一种处理Ｓｋｙｌｉｎｅ查询的有效方法 Ｕｏ］ Ｊｉｎ Ｗ，Ｔｕｎｇ Ａ，Ｅｓｔｅｒ Ｍ，ｅｔ ａ１．（）ｎ ｅｆｆｉｃｉｅｎｔ ｐｒｏｃｅｓｓｉｎｇ ｏｆ ｓｕｂｓｐａｃｅ ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓ ｏｎ ｈｉｇｈ ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ［ｑ／Ｐｒｏｃ ｏｆ ｔｈｅ Ｉｎｔ Ｃｏｎｆ ｏｎ Ｓｃｉｅｎｔｉｆｉｃ ａｎｄ Ｓｔａｔｉｓｔｉｃａｌ Ｄａｔａｂａｓｅ Ｍａｎａｇｅｍｅｎｔ．１．ｏｓ Ａｌａｍｉｔｏｓ，ＣＡ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ， ２００７：１ ２－２ｌ ｌ ９５３ ［２Ｉ］ Ｈｕａｎｇ Ｚ，Ｗａｎｇ Ｗ．Ａ ｎｏｖｅｌ ｉｎｃｒｅｍｅｎｔａｌ ｍａｉｎｔｅｎａｎｃｅ ａｌｇｏｒｉｔｈｍ ｏｆ ｓｋｙｃｕｂｅ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ Ｉｎｔ Ｃｏｎｆ ｏｎ Ｄａｔａｂａｓｅ ａｎｄ Ｅｘｐｅｒｔ Ｓｙｓｔｅｍｓ Ａｐｐｌｉｃａｔｉｏｎｓ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２００６： ７８１—７９０ ［２２］ Ｈｕａｎｇ Ｚ．Ｇｕｏ Ｊ，Ｓｕｎ Ｓ，ｅｔ ａ１．Ｅｆｆｉｃｉｅｎｔ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｍｕｌｔｉｐｌｅ ｓｕｂｓｐａｃｅ ｓｋｙｌｉｎｅ ｑｕｅｒｉｅｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，２００８，２３（１）：１０３—１１１ Ｓ，Ｄａｌｖｉ Ｎ。Ｋａｕｓｈｉｋ Ｒ．Ｒｏｈｕｓｔ ｃａｒｄｉｎａｌｉｔｙ ａｎｄ ［２３］ Ｃｈａｕｄｈｕｒｉｃｏｓｔ ｅｓｔｉｍａｔｉｏｎ ｆｏｒ ｓｋｙｌｉｎｅ ｏｐｅｒａｔｏｒ Ｅｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ Ｉｎｔ Ｃｏｎｆ ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ．Ｉ ｏｓ Ａｌａｍｉｔｏｓ，ＣＡ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００６：６４ ７５ Ｈｕａｎｇ Ｚｈｅｎｈｕａ，ｂｏｒｎ ｉｎ １ ９８０．ＰｈＤ ａｎｄ ｌｅｃｔｕｒｅｒ． Ｍｅｍｂｅｒ ｏｆ Ｃｈｉｎａ Ｃｏｍｐｕｔｅｒ Ｆｅｄｅｒａｔｉｏｎ．Ｈｉｓ ｃｕｒｒｅｎｔ ｒｅｓｅａｒｃｈ ｉｎｔｅｒｅｓｔｓ ｉｎｃｌｕｄｅ ｄａｔａ ｗａｒｅｈｏｕｓｅ，ｄａｔａ ｍｉｎｉｎｇ， ｑｕｅｒｙ ｏｐｔｉｍｉｚａｔｉｏｎ，ｄａｔａ ｓｔｒｅａｍ ａｎｄ ｓｋｙｌｉｎｅ ｃｏｍｐｕｔａｔｉｏｎ． 刘啸岭，１９７９年生，博士研究生，计算机学会学生会员，主要 研究方向为数据库、数据流和商业智能． 黄震华，１９８０年生，博士，讲师，中国计算机学会会员，手要研 究方向为数据仓库、数据挖掘、查询优化、数据流和ｓｋｙｌｉｎｅ 计算． Ｒｅｓｅａｒｃｈ Ｂａｃｋｇｒｏｕｎｄ Ｓｋｙｌｉｎｅ ｑｕｅｒｙ ｐｒｏｃｅｓｓｉｎｇ ｈａｓ ｒｅｃｅｎｔｌｙ ｒｅｃｅｉｖｅｄ ａ ｌｏｔ ｏｆ ａｔｔｅｎｔｉｏｎ ｉｎ ｔｈｅ ｄａｔａｂａｓｅ ａｎｄ ｄｅｃｉｓｉｏｎ ｍａｋｉｎｇ ｃｏｍｍｕｎｉｔｉｅｓ．Ｉｎ ｔｈｅ ２００１ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ，ｓｋｙｌｉｎｅ ｑｕｅｒｙ ｐｒｏｃｅｓｓｉｎｇ ｔｅｃｈｎｏｌｏｇｙ ｉｓ ｆｉｒｓｔ ｉｎｔｒｏｄｕｃｅｄ ｉｎｔｏ ｔｈｅ ｄａｔａｂａｓｅ ｃｏｍｍｕｎｉｔｉｅｓ．Ｆｒｏｍ ２００５，ｔｈｅ ｒｅｓｅａｒｃｈｅｒｓ ｈａｖｅ ｔａｃｋｌｅｄ ｗｉｔｈ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｍｕｌｔｉｐｌｅ ｄｉｆｆｅｒｅｎｔ ｓｕｂｓｐａｃｅ ｓｋｙｌｉｎｅ ｑｕｅｒｅｉｓ．Ｔｈｅ ｒｅｐｒｅｓｅｎｔａｔｉｖｅ ｏｎｅ ｉｓ ｔｈｅ ＳＵＢＳＫＹ ａｌｇｏｒｉｔｈｍ ｗｈｉｃｈ ｉｓ ｐｒｏｐｏｓｅｄ ｂｙ Ｔａｏ Ｙ．Ｂａｓｅｄ ｏｎ ｔｈｅ ｄａｔａ ｄｉｓｔｒｉｂｕｔｉｏｎ，ｔｈｅ ＳＵＢＳＫＹ ａｌｇｏｒｉｔｈｍ ｃｒｅａｔｅｓ ａｎ ａｎｃｈｏｒ ｐｏｉｎｔ ｆｏｒ ｅａｃｈ ｃｌｕｓｔｅｒ，ａｎｄ ｂｕｉｌｄｓ ａ Ｂ ｔｒｅｅ ｏｎ ｔｈｅ Ｌ。。ｄｉｓｔａｎｃｅ ｂｅｔｗｅｅｎ ｅａｃｈ ｏｂｊ ｅｃｔ ｔｏ ｉｔｓ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ａｎｃｈｏｒ．Ｗｅ ｏｂｓｅｒｖｅ ｔｈａｔ ａｌｌ ｔｈｅｓｅ ｅｘｉｓｔｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｏｂｔａｉｎ ｔｈｅ ｓｋｙｌｉｎｅ ｓｅｔｓ ｆｒｏｍ ｔｈｅ ｏｒｉｇｉｎａｌ ｒｅｌａｔｉｏｎａｌ ｔａｂｌｅ ｆｒｏｍ ｓｃｒａｔｃｈ，ａｎｄ ａｒｅ ｉｎａｐｐｌｉｃａｂｌｅ ｔｏ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ｈｕｇｅ ｄａｔａ ｓｅｔ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｗｅ ｆｏｃｕｓ ｏｎ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ａｎｄ ｔｉｍｅ ｃｏｓｔ ｏｆ ｍｕｌｔｉｐｌｅ ｄｉｆｆｅｒｅｎｔ ｓｕｂｓｐａｃｅ ｓｋｙｌｉｎｅ ｑｕｅｒｅｉｓ．Ｏｕｒ ｓｏｌｕｔｉｏｎ ａｄｅｑｕａｔｅｌｙ ｃｏｎｓｉｄｅｒｓ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｔｈｅ ｓｔｏｒａｇｅ ｍｅｃｈａｎｉｓｍ ｏｆ ｐｒｅｓｔｏｒｉｎｇ ｓｋｙｌｉｎｅ ｓｅｔｓ，ａｎｄ ａｄｏｐｔｓ ｔｈｅ ｃｏｎｃｅｐｔ ｏｆ ｃｏｎｔｒｉｂｕｔｉｏｎ ｍａｒｇｉｎ ｉｎ ｅｃｏｎｏｍｉｃｓ．Ｏｕｒ ｗｏｒｋ ｉｓ ｓｕｐｐｏｒｔｅｄ ｂｙ ｔｈｅ Ｎａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｃｈｉｎａ ｕｎｄｅｒ ｇｒａｎｔ Ｎｏｓ．６０９０３０３２ ａｎｄ ７０７７１０７７，ｔｈｅ Ｄｏｃｔｏｒａｌ Ｆｕｎｄ ｏｆ ｔｈｅ Ｍｉｎｉｓｔｒｙ ｏｆ Ｅｄｕｃａｔｉｏｎ ｏｆ Ｃｈｉｎａ ｕｎｄｅｒ ｇｒａｎｔ Ｎｏ．２００９００７２１２００５６，ｔｈｅ Ｎａｔｉｏｎａｌ ８６３ Ｈｉｇｈ Ｔｅｃｈｎｏｌｏｇｙ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ Ｐｌａｎ ｏｆ Ｃｈｉｎａ ｕｎｄｅｒ ｇｒａｎｔ Ｎｏ．２００８ＡＡ０４Ｚ１０６，ａｎｄ ｔｈｅ Ｏｕｔｓｔａｎｄｉｎｇ Ｙｏｕｎｇ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｔｏｎｇｊｉ Ｕｎｉｖｅｒｓｉｔｙ ｕｎｄｅｒ ｇｒａｎｔ Ｎｏ．０８００２１９０９３．
