A query engine for probabilistic preferences

Uzi Cohen, Batya Kenig, Haoyue Ping, Benny Kimelfeld, Julia Stoyanovich

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 first-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 paper, we embark on the challenge of a practical realization of this framework. We first describe an implementation of a query engine that supports querying probabilistic preferences alongside relational data. Our system accommodates preference distributions in the general form of the Repeated Insertion Model (RIM), which generalizes Mallows and other models. We then devise a novel inference algorithm for conjunctive queries over RIM, and show that it significantly 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 computation among different inference tasks in the workload. Finally, we conduct an extensive experimental evaluation and demonstrate that clear performance benefits 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.

    Original languageEnglish (US)
    Title of host publicationSIGMOD 2018 - Proceedings of the 2018 International Conference on Management of Data
    EditorsGautam Das, Christopher Jermaine, Ahmed Eldawy, Philip Bernstein
    PublisherAssociation for Computing Machinery
    Pages1509-1524
    Number of pages16
    ISBN (Electronic)9781450317436
    DOIs
    StatePublished - May 27 2018
    Event44th ACM SIGMOD International Conference on Management of Data, SIGMOD 2018 - Houston, United States
    Duration: Jun 10 2018Jun 15 2018

    Publication series

    NameProceedings of the ACM SIGMOD International Conference on Management of Data
    ISSN (Print)0730-8078

    Other

    Other44th ACM SIGMOD International Conference on Management of Data, SIGMOD 2018
    CountryUnited States
    CityHouston
    Period6/10/186/15/18

    ASJC Scopus subject areas

    • Software
    • Information Systems

    Fingerprint Dive into the research topics of 'A query engine for probabilistic preferences'. Together they form a unique fingerprint.

    Cite this