? This work was supported in part by ISF Grant No. 1295/15, BSF Grant No. 2014391 and by the Taub Foundation. ?? This work was supported in part by NSF Grants No. 1464327 and 1539856, and BSF Grant No. 2014391.
Preferences are statements about the relative quality or desirability of items.
Ever larger amounts of preference information are being collected and analyzed
in a variety of domains, including recommendation systems [
Preferences are often inferred from indirect input (e.g., a ranked list may be
inferred from individual choices), and are therefore uncertain in nature. This
motivates a rich body of work on uncertain preference models in the statistics
literature [
In this paper, we take the position that preference modeling and analysis
should be accommodated within a general-purpose probabilistic database
framework. Our framework is based on a deterministic concept that we proposed in
a past vision paper [
This paper is an abbreviated version of our PODS 2017 paper, where an interested reader can nd additional details about the formalism and proposed algorithmic solutions. A preference schema S is a relational schema with some relation symbols marked as preference symbols (and others as ordinary symbols ). Figure 1 gives an example of a preference database instance, with the ordinary symbols Candidates and Voters, and the preference symbol Polls.
An instance over a preference symbol (such as Polls in Figure 1) represents a collection of preferences among a set of items, where each such preference is
Candidates (o) cand party sex edu Trump R M BS Clinton D F JD Sanders D M BS Rubio R M JD
Voters (o) voter edu sex age Ann BS F 25 Bob BS M 35 Cat MS F 40
Dave MS M 45 A MAL-instance over Polls (p) voter date Preference model MAL( ; ) Ann Oct-5 hClinton; Sanders; Rubio; Trumpi; 0:3 Bob Oct-5 hTrump; Rubio; Sanders; Clintoni; 0:3 Polls (p) voter date lcand rcand Ann Oct-5 Sanders Clinton Ann Oct-5 Sanders Rubio Ann Oct-5 Sanders Trump Ann Oct-5 Clinton Rubio Ann Oct-5 Clinton Trump Ann Oct-5 Rubio Trump Bob Oct-5 Sanders Rubio Bob Oct-5 Sanders Clinton Bob Oct-5 Sanders Trump Bob Oct-5 Rubio Clinton Bob Oct-5 Rubio Trump
Bob Oct-5 Clinton Trump itself a binary relation called a session. A a binary relation over a set I = f 1; : : : ; ng of items is a (strict) partial order if it is irre exive and transitive. A linear (or total ) order is a partial order where every two items are comparable. By a slight abuse of notation, we often identify a linear order 1 n with the sequence h 1; : : : ; ni, and we call it a ranking.
Example 1. Our running example is on individual preferences among the set of US presidential candidates I = fClinton; Rubio; Sanders; Trumpg. The ranking = hClinton; Rubio; Sanders; Trumpi is an example ranking over I. tu
A preference relation instantiates a special relation symbol with a signature of the form ( ; Al; Ar), where is the session signature, and Al and Ar are the lefthand-side (lhs) attribute and right-hand-side (rhs) attribute, respectively. We use semicolon (;) to distinguish between the di erent parts and write ( ; Al; Ar). Example 2. We use the preference signature (voter; date; lcand; rcand) in our running example. Here the components , Al and Ar are (voter; date), lcand, and rcand, respectively. The table Polls of Figure 1 is an instance of this preference signature that contains two sessions. The session (Ann; Oct-5) is associated with the ranking hSanders; Clinton; Rubio; Trumpi. The tuple (Ann; Oct-5; Sanders; Clinton) denotes that in the session of the voter Ann on October 5th, the candidate Sanders is preferred to the candidate Clinton. tu
We now make the knowledge about voters' opinions probabilistic, interpreting the preference database of Figure 1 as one possible world of a probabilistic preference database. A probabilistic preference database (abbrv. PPD) over the preference schema S is a probability space over preference databases over S. A PPD can be represented by explicitly specifying the entire sample space; however, we wish to allow for standard compact representations of preferences.
A probabilistic preference model is a ( nite and typically compact)
representation M of a probability space over partial orders over a nite set of items;
we denote this probability space by JM K. A model family is a collection M of
probabilistic preference models. As prominent examples, we de ne two model
families: RIM is the family of RIM [
A Mallows model [
In the PPD representations we explore, termed RIM-PPD, each session is associated with the parameters of a RIM model. A RIM-PPD represents a probability space over preference databases, where a possible world is obtained by independently sampling a preference from the model of each session. Figure 1 gives an example of a MAL-instance over the p-symbol Polls that associates each session in Polls with a Mallows model. It is straight-forward to extend this representation to a mixture of Mallows, by associating each session with k components MAL1( 1; 1); : : : ; MALk( k; k), with the corresponding probabilities p1; : : : ; pk. A possible world would then be obtained by rst sampling component MALi( i; i) with probability pi independently for each session, and then sampling a preference from MALi( i; i). 3
We adopt the semantics of probabilistic databases [
We study the data complexity of evaluating Conjunctive Queries (CQs) over RIM-PPDs. We focus on CQs to which we refer as itemwise. Intuitively, these are CQs where items are connected only through preferences. We show a natural fragment of CQs where the itemwise CQs are precisely the CQs in which query evaluation can be done in polynomial time. In the fragment we consider, we prove that every query that is not itemwise is actually #P-hard, and therefore, we establish a dichotomy in complexity.
Let S be a preference schema, and let Q be a CQ over S. An atomic formula
of Q is called a p-atom if it is over a p-symbol, and an o-atom if it is over an
o-symbol. Let P (s1; : : : ; sk; tl; tr) be p-atom of Q. Each term si for i = 1; : : : ; k
is said to occur in a session position, and each of tl and tr is said to occur in
an item position. A session variable of Q is a variable that occurs in a session
position, and an item variable of Q is a variable that occurs in an item position.
We say that Q is sessionwise if all p-atoms of Q refer to the same session; that
is, if P (s1; : : : ; sk; tl; tr) and P 0(s01; : : : ; s0l; t0l; t0r) are p-atoms of Q, then P = P 0
and (s1; : : : ; sk) = (s01; : : : ; s0l). We say that Q is itemwise if Q is sessionwise,
and the joins between item variables occur only inside the p-atoms, or through
session variables. Put di erently, in an itemwise CQ with a constant session,
the o-atoms state properties of individual items but do not draw connections
between the items. In [
Example 3. Consider the following Boolean CQs. The query Q1 asks whether there is a voter with a BS degree who prefers a male Democratic candidate to a female Democratic candidate.
Q1()
P (v; ;l; r); V (v; BS; ; ); C(l; D; M; ); C(r; D; F; ) The query Q2 asks whether there is a voter who prefers a male candidate to a female candidate such that both candidates are of the same political party.
Q2()
P ( ; ;l; r); C(l; p; M; ); C(r; p; F; ) The query Q3 asks whether there is a voter who prefers a female candidate to both Trump and Sanders.
Q3()
P (v; d; l; Trump); P (v; d; l; Sanders); C(l; ;F; ) All of these CQs are sessionwise. Indeed, Q1 and Q2 involve a single p-atom (hence, they are sessionwise by de nition), and in Q3 both atoms have (v; d) in their session parts. CQs Q1 and Q3 are itemwise, while Q2 is not itemwise. tu
In [
We also prove that the class itemwise CQs are precisely the tractable ones (among the queries in the class), under conventional complexity assumptions. In other words, every Boolean CQ (in the class) that is not itemwise is necessarily hard to evaluate, and therefore, we establish a dichotomy.
Theorem 2. Let S be a preference schema, and let Q be a Boolean CQ over S such that Q has no self joins and Q has a single p-atom. If Q is not itemwise, then the evaluation of Q on RIM-PPDs over S is FP#P-hard.
In [