Skyband查询是决策支持领域一类非常重要的查询.为了使数据库系统有效支持Skyband查询,必须解决Skyband基数估计的问题,即估计Skyband查询结果中包含的Skyband元素数,因为Skyband基数估计对于扩展数据库系统查询优化器的代价模型以便能够对Skyband查询进行优化非常重要.基于容斥原理的推广形式对Skyband基数进行理论分析并给出了时间和空间代价很小的对Skyband基数进行估计的算法.实验结果表明,该方法能够准确地对Skyband基数进行估计.

Skyband queries are very important for decision-making applications. To incorporate the Skyband operator into the database system, the problem of Skyband cardinality estimation must be solved, i.e., estimating the number of the Skyband elements returned by Skyband queries, which is very important for extending the query optimizer’s cost model to accommodate Skyband queries. This paper proposes a space and time efficient approach to estimate the Skyband cardinality, which is based on the generalized form of the Inclusion-Exclusion Principle. Experimental results show that the proposed approach can estimate the Skyband cardinality accurately.

Supported by the National High-Tech Research and Development Plan of China under Grant Nos.2007AA01Z153, 2007AA01Z191 (国家高技术研究发展计划(863))