top-k join查询返回用户最感兴趣的k个连接结果。近来top-k join已经成为一个重要的研究课题,其在Web数据库,信息抽取和数据挖掘中均有应用。星型模式的数据仓库在实际应用中也存在top-k join查询,如有时决策者只想查询星型连接结果中他最感兴趣的k个。然而,现有top-k join算法不适合星型模式。为了在星型模式上有效地支持top-k join查询,本文提出两种索引并基于这两种索引提出一个适用于星型模式的多路top-k join算法MTJS。该算法通过采用一个比现有算法更优的上界和一个剪枝策略获得了更高的效率。此外,实验也表明该算法比现有算法效率更高。获取精确的top-k join查询结果的代价是较高的,而且有时决策者希望牺牲top-k join查询结果的精确性来缩短查询的执行时间和资源消耗。更重要的是,我们发现现有的近似top-k join算法因没有充分考虑星型模式的固有特点而不适合星型模式,因而本文提出一个基于星型模式的近似多路top-k join算法MTJS? ?。MTJS ? ?是MTJS的一个变种算法,其通过引入一个参数ε来返回近似的top-k join结果。MTJS ? ?因使用了MTJS中的总上界和剪枝策略等优化,其性能优于现有近似的top-k join算法。此外,我们通过实验证明了MTJS ? ?的效率优于现有算法。而且还发现MTJS ? ?返回的结果的实际精确程度远远优于其近似度定义的精确程度。