TY - GEN
T1 - On the semantics and evaluation of top-k queries in probabilistic databases
AU - Zhang, Xi
AU - Chomicki, Jan
PY - 2008
Y1 - 2008
N2 - 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 semantics 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.
AB - 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 semantics 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.
UR - https://www.scopus.com/pages/publications/50249105848
U2 - 10.1109/ICDEW.2008.4498380
DO - 10.1109/ICDEW.2008.4498380
M3 - Conference contribution
SN - 9781424421626
T3 - Proceedings - International Conference on Data Engineering
SP - 556
EP - 563
BT - Proceedings of the 2008 - IEEE 24th International Conference on Data Engineering Workshop, ICDE'08
T2 - 2008 - IEEE 24th International Conference on Data Engineering Workshop, ICDE'08
Y2 - 7 April 2008 through 12 April 2008
ER -