Consensus Answers for Queries over Probabilistic Databases

Details Consensus Answers for Queries over Probabilistic Databases Consensus Answers for Queries over Probabilistic Databases

2008-12-10

arxiv.org/abs/0812.2049v1

Computer Science

Databases

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Consensus Answers for Queries over Probabilistic Databases does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Consensus Answers for Queries over Probabilistic Databases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Consensus Answers for Queries over Probabilistic Databases will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-60099