Technical Report MSC-2018-17

Title: Query Engine System for Probabilistic Preferences
Authors: Uzi Cohen
Supervisors: Benny Kimelfeld
PDFCurrently accessibly only within the Technion network
Abstract: Models of uncertain preferences, such as Mallows, have been extensively studied due to their plethora of application domains. In a recent work, a conceptual and theoretical framework has been proposed for supporting uncertain preferences as rst-class citizens in a relational database. The resulting database is probabilistic, and, consequently, query evaluation entails inference of marginal probabilities of query answers. In this thesis, we embark on the challenge of a practical realization of this framework. We rst describe an implementation of a query engine that supports querying prob- abilistic preferences alongside relational data. Our system accommodates preference distributions in the general form of the Repeated Insertion Model (RIM), which gen- eralizes Mallows and other models. We then devise a novel inference algorithm for conjunctive queries over RIM, and show that it signi cantly outperforms the state of the art in terms of both asymptotic and empirical execution cost. We also develop performance optimizations that are based on sharing computations among di erent in- ference tasks in the workload. Finally, we conduct an extensive experimental evaluation and demonstrate that clear performance bene ts can be realized by a query engine with built-in probabilistic inference, as compared to a stand-alone implementation with a black-box inference solver.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2018
To the main CS technical reports page

Computer science department, Technion