On the semantics and evaluation of top-k queries in probabilistic databases
Authors:
- 1 April 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 556-563
Abstract
We formulate three intuitive semantic properties for top-k queries in probabilistic databases, and propose Global-Topk query semantics which satisfies all of them. We provide a dynamic programming algorithm to evaluate top-k queries under Global-Topk in simple probabilistic relations. For general probabilistic relations, we show a polynomial reduction to the simple case. Our analysis shows that the complexity of query evaluation is linear in k and at most quadratic in database size.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Top-k Query Processing in Uncertain Databases2007
- The Threshold Algorithm: From Middleware Systems to the Relational EngineIEEE Transactions on Knowledge and Data Engineering, 2007
- Evaluating top- k queries over web-accessible databasesACM Transactions on Database Systems, 2004
- Merging the Results of Approximate Match Operations2004
- Supporting Top-k Join Queries in Relational Databases2003
- Joining Ranked Inputs in Practice2002
- Optimal aggregation algorithms for middleware2001
- Combining Fuzzy Information from Multiple SystemsJournal of Computer and System Sciences, 1999
- An analysis of first-order logics of probabilityArtificial Intelligence, 1990
- Incomplete Information in Relational DatabasesJournal of the ACM, 1984