Consensus Answers for Queries over Probabilistic Databases
| dc.creator | Li, Jian | |
| dc.creator | Deshpande, Amol | |
| dc.date | 2008-12-10 | |
| dc.date.accessioned | 2026-07-07T12:11:56Z | |
| dc.date.available | 2026-07-07T12:11:56Z | |
| dc.description | We address the problem of finding a "best" deterministic query answer to a query over a probabilistic database. For this purpose, we propose the notion of a consensus world (or a consensus answer) which is a deterministic world (answer) that minimizes the expected distance to the possible worlds (answers). This problem can be seen as a generalization of the well-studied inconsistent information aggregation problems (e.g. rank aggregation) to probabilistic databases. We consider this problem for various types of queries including SPJ queries, \Topk queries, group-by aggregate queries, and clustering. For different distance metrics, we obtain polynomial time optimal or approximation algorithms for computing the consensus answers (or prove NP-hardness). Most of our results are for a general probabilistic database model, called {\em and/xor tree model}, which significantly generalizes previous probabilistic database models like x-tuples and block-independent disjoint models, and is of independent interest. | |
| dc.identifier | https://arxiv.org/abs/0812.2049 | |
| dc.identifier | http://arxiv.org/abs/0812.2049 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/210383 | |
| dc.subject | Databases | |
| dc.title | Consensus Answers for Queries over Probabilistic Databases | |
| dc.type | text |