Exploiting Qualitative User Feedback in Deterministic and Probabilistic Databases
MetadataShow full item record
This dissertation consists of two parts. In the first part we investigate the use of qualitative user preferences in the context of deterministic databases. In the second part we study the same problem in the context of probabilistic databases. A qualitative preference is a partial order over a set of query-answers. In deterministic databases, they are used to identify the answers that are most interesting to the user. In the first part of this dissertation we adopt the framework of Prioritized Skylines, a popular approach for preference reasoning. Our contribution focuses on query evaluation: we introduce a novel output-sensitive algorithm, whose worst-case computational complexity depends explicitly on the size of the output. This is a very desirable property in the context of preference queries, as the output is expected to be, on average, only a small fraction of the input. Additionally, we show our algorithm exhibits linear complexity in the average-case scenario. The second part of this dissertation is dedicated to probabilistic databases. In this context, qualitative preferences are used to encode a set of logical implications between query-answers: if the user states that a query-answer implies another, then the marginal probability of the latter must be as large as the marginal probability of the former. Such information can be used to speed-up the training process of a probabilistic database. We introduce Beta Probabilistic Databases (B-PDBs), a generalization of tuple-independent probabilistic databases, designed to support Bayesian updates and parameter learning in an efficient, scalable way. The key feature of B-PDBs is that they can be trained using samples of query-answers as evidence; this way, the user is relieved from the need of specifying the model’s parameters explicitly, in a quantitative fashion. Additionally, B-PDBs can leverage qualitative user-feedback to speed-up the learning process.