刘 萍

(甘肃民族师范学院计算机科学系，甘肃 合作 747000)

0 引言

S.Borzsony等在文献［1］中提出轮廓(Skyline)的概念，用来表述在多维的数据系统R中经过评估选出的占优的数据(元组)。多维评估的方法通常称为多元目标优化决策。假设R是有d维属性的数据系统，每一个属性的值都是能够比较优劣的域，通常用正实数表示属性的值。一般说来，一些属性值以大的数为优，另一些值则以小的数为优。以文献［1］中举的例子(很多文献都引用这个例子)为例，对于旅游胜地拿骚(巴哈马群岛)的旅馆，可以有多个指标来评估旅馆的优劣，如旅客关心的价格、旅馆到海滨的距离、旅馆的星级等。其中价格指标以小的数为优，星级指标以大的数为优。在旅游指南(列出所有旅馆的数据)中，游客不可能找到各项指标都占优的旅馆。旅客感兴趣的显然是这种旅馆，不存在一个在所有指标都超过它的旅馆。这种旅馆就是文献［1］中所说的旅馆集合中的Skyline。显然Skyline旅馆不是唯一的，这就方便旅客根据自己的偏爱做出选择。多元目标优化决策的应用非常广泛，促使了Skyline的研究。为了实现Skyline查询，文献［1］提出一种嵌套SQL查询(nested SQL query)。然而这种方法需要对于每一个旅馆和所有的旅馆作比较，开销太大，没有实用价值。因为实际应用的需要，近十多年出现很多计算效率高的Skyline的算法。

1 相关技术

设R是有d个属性D1，…，Dd的数据集合，R的数据简称为点。点x表示为x=(x1，…，xd)。对于任意两个点 x、y，如果 xi≤yi(i=1，…，d)，且存在 j使得xj＜yj，则称x支配y。如果不存在R中的点y支配x，则称x是R的Skyline点，简称为R的SP。……