不确定数据库中基于x-tuple的高效Top-k查询处理算法

Efficient Processing of X-Tuple Based Top-k Queries in Uncertain Database

Top-k查询由于其广泛的应用而倍受欢迎.不确定数据库中通常考虑的两条生成规则是:独立和互斥,一个x-tuple是由一些互斥的元组组成的,构成一个x-tuple的各个元组称为该x-tuple的可选元组.U-kRanks查询考虑x-tuple中每个可选元组排在前k的概率,并返回最可能排在前k的k个元组.已有的Top-k语义都没有将x-tuple作为一个整体,因此,定义了一种新的Top-k查询语义,不确定x-kRanks查询(U-x-kRanks),该Top-k语义返回最可能排在前k的k个x-tuple而非元组.新语义考虑x-tuple中的每个可选元组位于前k的概率,并将之汇集,得到整个x-tuple位于前k的概率.提出了一种基于动态规划的有效算法处理U-x-kRanks查询,在最小的搜索空间内完成查询处理过程.不同数据集合上的综合实验显示,所提出的算法是高效的.

Like top-k in traditional databases,top-k queries in uncertain databases are quite popular and useful due to its wide application usage.However,compared with top-k in traditional databases,queries over uncertain database are more complicated because of the existence of exponential possible worlds.Often,two kinds of generation rules are considered in the uncertain database：independent and mutually exclusive.An x-tuple is the union of the tuples mutually exclusive.U-kRanks queries consider each alternative in x-tuple as single one and return the tuple which has the highest probability appearing at top k or a given rank.However,no matter which alternative（tuple） of an x-tuple appears in a possible world,it is undoubtedly believed that this x-tuple appears in the same possible world accordingly.Thus,instead of ranking each individual tuple,the authors define a novel top-k query semantic in uncertain database,uncertain x-kRanks queries（U-x-kRanks）,which return k x-tuples according to the score and the confidence of alternatives in x-tuples,respectively.In order to reduce the search space,they present an efficient algorithm to process U-x-kRanks queries,which can minimize the scan depth by terminating the scan process as soon as the answers are found.Comprehensive experiments on different data sets demonstrate the effectiveness of the proposed solutions.