孙大烈，李建中

(哈尔滨工业大学 计算机科学与技术学院，150001哈尔滨，sdl@hit.edu.cn)

给定一个感兴趣的属性集合，Skyline查询返回这样的元组，这些元组在任何一个属性上都不受其他元组制约[1].例如，一名学生想要寻找一个合适的住处，他可能提交这样的查询:“返回价格便宜并且离学校距离近的公寓”.Skyline查询在决策系统中很有价值(用处).由于它的重要性，研究人员已经开始在商用数据库管理系统(DBMS)中实现 Skyline 查询[2－3].

现有的研究工作大多假设Skyline查询只局限于一个数据表，也就是说，所有待查的属性都来自于同一张数据表.然而，这种假设在互联网环境中不再成立，因为此时查询处理需要来自多源的数据.例如，数据库cheapoair.com提供机票预订服务，BookInHotels.com提供酒店预订服务.假设用户提交这样的查询“请列出所有在5月11日起飞的最廉价的航班，以及距离机场最近的四星级酒店”.这种查询与Skyline查询有共同的特点，但是它需要从多张数据表提取数据信息.在本文中，称这种类型的查询为Skyline-join.

处理Skyline-join查询的一个简单而原始的方法是，先连接所有相关的数据表，然后再应用现有的Skyline算法.然而，这种简单的算法往往效率低下，不能提供及时的结果.因此，本文提出一种新的基于 MapReduce框架[4－5]的分布式并行算法.该算法可以应用在计算机集群环境中，通过将计算分布在不同的节点上来提高处理速度.

1 Skyline-join查询

如前所述，不同于现有的操作，Skyline-join操作会涉及多张数据表.对于某单一数据表，如果当0≤i≤d时，vi≻v'i并且 ∃j(0≤ j≤d)∧(vj≻v'j)，这里定……