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 -