Querying probabilistic preferences in databases

Batya Kenig, Benny Kimelfeld, Haoyue Ping, Julia Stoyanovich

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


    We propose a novel framework wherein probabilistic preferences can be naturally represented and analyzed in a probabilistic relational database. The framework augments the relational schema with a special type of a relation symbol - a preference symbol. A deterministic instance of this symbol holds a collection of binary relations. Abstractly, the probabilistic variant is a probability space over databases of the augmented form (i.e., probabilistic database). Effectively, each instance of a preference symbol can be represented as a collection of parametric preference distributions such as Mallows. We establish positive and negative complexity results for evaluating Conjunctive Queries (CQs) over databases where preferences are represented in the Repeated Insertion Model (RIM), Mallows being a special case. We show how CQ evaluation reduces to a novel inference problem (of independent interest) over RIM, and devise a solver with polynomial data complexity.

    Original languageEnglish (US)
    Title of host publicationPODS 2017 - Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
    PublisherAssociation for Computing Machinery
    Number of pages16
    ISBN (Electronic)9781450341981
    StatePublished - May 9 2017
    Event36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017 - Chicago, United States
    Duration: May 14 2017May 19 2017

    Publication series

    NameProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
    VolumePart F127745


    Other36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017
    Country/TerritoryUnited States


    • Probabilistic databases
    • Probabilistic preferences
    • Ranking distributions
    • Repeated insertion model

    ASJC Scopus subject areas

    • Software
    • Information Systems
    • Hardware and Architecture


    Dive into the research topics of 'Querying probabilistic preferences in databases'. Together they form a unique fingerprint.

    Cite this