SKYLINE查询解析

Parsing Skyline Queries

现有的研究工作只考虑如何对单个底层关系表进行skyline计算,即它们假定用户所提交的skyline查询不涉及任何传统的关系操作,并且所有skyline维度均落入同一个关系表中.显然,在实际应用中,由于这种假设的不成立,使得在多数情况下用户查询的效率极其低下.基于此,将skyline计算作为一个特殊的关系操作符,研究它与传统关系操作符间执行顺序变换的等价规则.从而,利用这些等价变换规则,通过改变skyline操作符与传统关系操作符之间的执行顺序来有效提高查询的效率.同时,给出充分的理论证明来论证所给等价变换规则的正确性,并通过实验验证其有效性.

The existing works only consider how to efficiently process skyline computation for a single table. That is, they assurne the issued skyline queries do not involve any traditional relational operator. Clearly, in most real applications, the query efficiency is extremely low because of this unreasonable assumption. Motivated by these facts, we regard skyline computation as a special relational operator and study the equivalence transformation rules of implementation order of it and traditional relational operators. Then based on these equivalence transformation rules, we can efficiently improve the query performance. Moreover, we present sufficient theoretical proofs to demonstrate the correctness of the proposed equivalence transformation rules. The extensive experiments also show that the after-wansforming solutions markedly outperform the before-transforming counterparts.