TY - GEN

T1 - Querying probabilistic preferences in databases

AU - Kenig, Batya

AU - Kimelfeld, Benny

AU - Ping, Haoyue

AU - Stoyanovich, Julia

N1 - Funding Information:
This work was supported in part by the US National Science Foundation (NSF) Grants No. 1464327 and 1539856, by the US-Israel Binational Science Foundation (BSF) Grant No. 2014391, and by the Israel Science Foundation (ISF) Grant No. 1295/15. Benny Kimelfeld is a Taub Fellow, supported by the Taub Foundation.
Publisher Copyright:
© 2017 ACM.

PY - 2017/5/9

Y1 - 2017/5/9

N2 - 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.

AB - 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.

KW - Probabilistic databases

KW - Probabilistic preferences

KW - Ranking distributions

KW - Repeated insertion model

UR - http://www.scopus.com/inward/record.url?scp=85021212391&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85021212391&partnerID=8YFLogxK

U2 - 10.1145/3034786.3056111

DO - 10.1145/3034786.3056111

M3 - Conference contribution

AN - SCOPUS:85021212391

T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

SP - 21

EP - 36

BT - PODS 2017 - Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

PB - Association for Computing Machinery

T2 - 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017

Y2 - 14 May 2017 through 19 May 2017

ER -