计算机科学与探索 ›› 2012, Vol. 6 ›› Issue (11): 994-1006.DOI: 10.3778/j.issn.1673-9418.2012.11.004

• 学术研究 • 上一篇    下一篇

利用控制关系分析优化不确定数据Top-k查询

张志强+,魏小燕,谢晓芹   

  1. 哈尔滨工程大学 计算机科学与技术学院,哈尔滨 150001
  • 出版日期:2012-11-01 发布日期:2012-11-02

Using Dominate Relationship Analysis to Optimize Top-k Queries on Uncertain Data

ZHANG Zhiqiang+, WEI Xiaoyan, XIE Xiaoqin   

  1. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
  • Online:2012-11-01 Published:2012-11-02

摘要: 由于概率维的存在,使得准确高效地处理不确定数据的Top-k查询成为一个急需解决的难题。提出了一种利用控制关系分析(dominate relationship analysis,DRA)的不确定数据Top-k查询算法。该算法通过分析元组之间的控制关系,将那些最有可能成为Top-k查询结果的元组选择出来,这样大大减少了参加运算的元组数量,显著提升了查询效率。并且在数据库更新时,能够判断出此更新是否影响到之前得到的查询结果,从而决定是否需要重查,减少了重查的计算量。

关键词: Top-k查询, 控制关系分析(DRA), 不确定数据, 可能世界模型

Abstract: The dimensions of probability make it very difficult to process Top-k queries on uncertain data accurately and efficiently. On the basis of the existing methods, this paper proposes a Top-k queries method on uncertain data based on dominate relationship analysis (DRA). The method extracts the tuples most likely to become Top-k result through the use of dominate relations among the tuples, greatly reducing the amount of data in query processing. When the database is updated, the method can determine whether this update affects the results obtained before. If the results need not be changed, the method can avoid unnecessary cost of query reprocessing.

Key words: Top-k query, dominate relationship analysis (DRA), uncertain data, possible world model