Title: The most probable database problem
Authors: Gribkoff, Eric ×
Van den Broeck, Guy
Suciu, Dan #
Issue Date: Jun-2014
Host Document: Proceedings of the First international workshop on Big Uncertain Data (BUDA) pages:1-7
Conference: International workshop on Big Uncertain Data (BUDA) edition:1 location:Snowbird, Utah, USA date:22 June 2014
Article number: 7
Abstract: This paper proposes a novel inference task for probabilistic databases: the most probable database (MPD) problem. The MPD is the most probable deterministic database where a given query or constraint is true. We highlight two distinctive applications, in database repair of key and dependency constraints, and in finding most probable explanations in statistical relational learning. The MPD problem raises new theoretical questions, such as the possibility of a dichotomy theorem for MPD, classifying queries as being either PTIME or NP-hard. We show that such a dichotomy would diverge from dichotomies for other inference tasks. We then prove a dichotomy for queries that represent unary functional dependency constraints. Finally, we discuss symmetric probabilities and the opportunities for lifted inference.
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
gribkoff-buda14.pdfOA article Published 263KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.