The POOR-MAD approach: Preferred Objects Over Rich, Multi-Attribute Data

Abstract

Preferences about objects of interest are often expressed at diferent levels of granularity, not always matching the level of detail of stored data. For instance, we prefer rock to pop music, yet scheduled concerts only cite the name of the performer, with no reference to the musical genre. In this paper, we address this common mismatch by leveraging the vast amounts of data organized in taxonomies (such as those found in electronic catalogs and classification systems). We present a model to represent preferences and state the desirable properties of preference propagation, such as the fact that more specific preferences always prevail over more generic ones. We then illustrate an approach for propagating preferences along taxonomies complying with the stated properties and show how the best objects can thereby be identified.

1. Introduction

The information available in digital form is growing so fast that the search for data of interest (for attending events, buying products, planning a trip, etc.) is becoming increasingly dificult over time. For this reason, there has recently been a huge efort to develop efective methods and tools able to automatically suggest to any individual the items that better match what he/she is looking for [ 1 ]. In this framework, the availability of preferences, explicitly expressed by the users or somehow automatically derived from their actions, has been always considered an important ingredient [ 2, 3 ]. Unfortunately, preferences and data do not always match perfectly, even when they refer to the same domain of interest. This is mainly due to the fact that, usually, preferences are expressed in generic terms whereas data is very specific, as shown in the next example. Example 1. We are planning to reserve tickets for a series of concerts for which a general schedule is available, like the one in Figure 1. We prefer rock to pop concerts, yet we prefer a performance by Madonna to a rock concert. Due to work commitments, we also prefer concerts in August rather than in September. Furthermore, as for the concert venue, during autumn we prefer indoor places to stadiums. And, given two concerts by the same artist, we prefer to save money (say, if a concert costs less than 40$, then we prefer it to a concert by the same artist that costs more than 100$, whereas for intermediate prices other considerations are relevant). For the same reason, we would like to buy tickets only for (a subset of) the “best” available alternatives.

Concerts

Artist Bruce Springsteen Madonna Madonna Eminem Rihanna Bruce Springsteen

The example highlights that: (i) preferences can be expressed at diferent levels of detail, even for the same “dimension” of the problem (e.g., seasons vs months for the time dimension), and (ii) in general, preferences do not match the level of detail of data. Moreover, preferences can be conflicting when changing the level of detail (rock is better than pop, yet Madonna, a pop singer, is preferred to rock artists). Finally, additional knowledge is needed to choose the best alternatives using preferences. For instance, we need to know that Unipol Arena is an indoor place, whereas Verona Arena is a Roman amphitheater (thus an outdoor place).

This problem can be tackled by leveraging the great availability of shared and public taxonomies, that is, collection of terms in a domain arranged hierarchically according to an inclusion relationship (e.g., product catalogs, book classifications, biological categorizations, etc.). For instance, the availability of a classification of music artists according to diferent musical genres would allow us to understand that a preference on rock artists propagates to Springsteen.

In this paper, which is an extended abstract of [ 4 ], we present a principled approach to the problem of finding the best objects stored in a data repository on the basis of a set of preferences that are defined at a level of detail that does not match that of the data. As a preliminary step, we adopt a data model for representing taxonomies of values in specific domains (e.g., time or location) and propose a preference model for tuples over a given set of taxonomies. We then identify the general properties of preference propagation in the taxonomies, in particular, the fact that more specific preferences prevail over more generic ones. Thus, in the example above, a Madonna concert takes precedence over a Springsteen concert even if, in general, we prefer rock to pop. We then illustrate an algorithm for propagating preferences along taxonomies, complying with the stated properties. Finally, we present a technique for selecting the best tuples according to the propagated preferences. This technique would select tuples and as the best alternatives among the tuples in Figure 1 given the preferences discussed in Example 1.

2. Preliminaries

2.1. Data Model

First of all, it is useful to remind that a partial order ≤ on a domain is a subset of × , whose elements are denoted by 1 ≤ 2, that is: reflexive ( ≤ for all ∈ ), antisymmetric (if 1 ≤ 2 and 2 ≤ 1 then 1 = 2), and transitive (if 1 ≤ 2 and 2 ≤ 3 then 1 ≤ 3).

Our data model is a natural extension of the relational model in which the values in each domain can be arranged hierarchically according to a taxonomy [ 5, 6 ]. Each taxonomy is represented by a partial order ≤ on over a set of levels, each of which includes a set of values at a certain degree of granularity. For instance, a time taxonomy can be organized in levels such as day, month, season, and year, with day ≤ month ≤ year and day ≤ season. For each pair of levels 1 ≤ 2 in a taxonomy, we then assume the existence of a function 21 , called level mapping, that maps each value in 1 to a value in 2. For instance, we have: dmaoynth(23/07/2019) = 07/2019. The level mappings induce a partial order ≤ on the values of a taxonomy where 1 ≤ 2 if 1 ≤ 2 and 2 (1) = 2. 1 Example 2. Portions of the taxonomies relevant to our working example on concerts are shown in Figure 2. For the location of a concert we consider levels Venue, VenueType, and InOut. The values of this taxonomy are organized in the poset shown in Figure 3, where the level mappings are represented by arrows.

InOut VenueType

Venue Month

Season Day

PriceRange

Price

Genre Artist

The main constructs of the data model are the t-schema, the t-tuple, and the t-relation, which are natural extensions of the analogous notions in the relational model in which data domains can be taxonomies. For instance, a catalog of concerts in Italy can be represented by the t-relation shown in Figure 1 over the taxonomies in Figure 2 where we have used the levels as names of the attributes, assuming for simplicity that level names are unique. A partial order can than also be defined over t-schemas and t-tuples as follows: 1 ≤ 2 if for each ∈ 2 there is an element ∈ 1 such that ≤ and 1 ≤ 2 if: (i) 1 ≤ 2, and (ii) for each ∈ 2 there is an element ∈ 1 such that 1[ ] ≤ 2[]. Note that 2 may have fewer Indoor

Outdoor VenueType

Venue

Concert hall Amphitheater Stadium Unipol Arena Blue Note

Verona Arena

Stadio Olimpico attributes than 1. However, we assume without loss of generality that they have the same set of attributes, since we can add to 2 the missing attributes at the top level of the taxonomy.

2.2. Preference Model

In our approach preferences are represented by a binary relation ⪰ over t-tuples as follows: given a collection of taxonomies {1, . . . , } and a pair of t-tuples 1 and 2 over = 1 × . . . × , if 1 ⪰ 2 then we say that 1 is (weakly) preferable to 2. If 1 ⪰ 2 and 2 ̸⪰ 1 we say that 1 is strictly preferable to 2, denoted 1 ≻ 2. Then, the “best” t-tuples in a t-relation according to the preference relation ⪰ can be selected by means of the Best operator ⪰ () = { ∈ | ∄′ ∈ , ′ ≻ } [ 7 ].

We express preferences in a logic-based language, so that 1 ⪰ 2 if they satisfy the preference formula (1, 2): 1 ⪰ 2 ⇔ (1, 2). In particular, we consider formulas in which only builtin predicates are present and quantifiers are omitted, also called intrinsic preference formulas (ipf) [ 2 ]. Furthermore, without loss of generality, we assume that is in Disjunctive Normal Form (DNF) and call each disjunct of a preference clause, i.e.: (1, 2) = ⋁︀ =1 (1, 2).

Example 3. The preferences informally stated in Example 1 can be expressed by the formula (1, 2) = 1(1, 2) ∨ . . . ∨ 5(1, 2), where: 1(1, 2) = (1[Genre] = rock) ∧ (2[Genre] = pop) 2(1, 2) = (1[Artist] = Madonna) ∧ (2[Genre] = rock) 3(1, 2) = (1[Artist] = 2[Artist])∧

(1[PriceRange] = cheap) ∧ (2[PriceRange] = expensive) 4(1, 2) = (1[Season] = autumn) ∧ (2[Season] = autumn)∧

(1[InOut] = indoor) ∧ (2[VenueType] = stadium) 5(1, 2) = (1[Month] = august) ∧ (2[Month] = september)

3. Propagation of Preferences

The initial preference relation ⪰ completely ignores the structure of the poset on t-tuples ≤ , thus it treats as if it were a “flat” domain. This is because ⪰ includes all and only those preferences 1 ⪰ 2 such that the attribute values of 1 and 2 satisfy the preference formula, yet it does not take into account the taxonomies. The key observation justifying the downward propagation of preferences, is that, given a target t-schema , by exploiting the hierarchical organization of it is possible to extend ⪰ with more preferences that involve t-tuples with t-schemas , with ≤ .

Let ⪰ D denote the binary relation obtained by propagating, in some way to be described, the preferences in ⪰ . The basic idea underlying propagation is that, if we have t-tuples ′1 and ′2 such that ′1 ⪰ ′2, then this preference can be downward propagated to all t-tuples 1 and 2 such that 1 ≤ ′1 and 2 ≤ ′2. For instance, consider the t-schema in Figure 1 and the preference clause 1(1, 2) = 1[Genre] = Rock) ∧ (2[Genre] = Pop). From 1 we can obtain through propagation the preferences ⪰ D and ⪰ D , since Bruce Springsteen is a rock artist whereas Madonna is a pop singer.

In terms of logical formulas, downward propagation with respect to the target t-schema can be easily obtained by exploiting the level mappings. For instance, consider clause 5(1, 2) in Example 3. This can be rewritten as:

( DMaoynth(1[Day]) = august) ∧ ( DMaoynth(2[Day]) = september) so that it is applicable to values at the Day level. In order to simplify the notation, in the following level mappings are understood and we use =D in place of = to allow comparisons between values at diferent levels (similarly for other comparison operators, eg., ≤ would become ≤ ). Thus, the above clause can be more conveniently written as:

1[Day] =D august ∧ 2[Day] =D september.

Given an input formula , we denote by D the formula rewritten by means of level mappings.

3.1. Transitively Closing the Formula

Downward propagation does not guarantee that ⪰ D is a transitive relation, even because the very input relation ⪰ is not necessarily transitive. Although one may be tempted to circumvent this problem by adopting an algorithm for non-transitive preferences [ 8 ], algorithms of this type can discard a sub-optimal t-tuple only if the t-relation contains a t-tuple ′ that is directly (rather than transitively) better than .

Our approach is to transitively closing formula D with respect to the t-tuple domain , as described in [ 2 ] for the base case of flat domains. 1 The presence of taxonomies requires to extend the basic scheme adopted in [ 2 ], as the following example illustrates.

1Notice that the transitive closure of an ipf is finite and still an ipf [2].

Example 4. Given the formula (1, 2) = 5(1, 2) ∨ 4(1, 2), where 4 and 5 are as in Example 3, by means of downward propagation we obtain the formula: D(1, 2) = (1[Day] =D august ∧ 2[Day] =D september) ∨ (1[Day] =D autumn ∧ 2[Day] =D autumn ∧ 1[Venue] =D indoor ∧ 2[Venue] =D stadium).

Now, since some september days are in autumn, it is sound to add to the transitive closure of D, a formula that will be denoted as DT, the clause:

1[Day] =D august ∧ 2[Day] =D autumn ∧ 2[Venue] =D stadium.

We observe that D uses level mappings in order to understand when preferences expressed at diferent levels can be transitively combined. Indeed, this is the only additional complexity with respect to the procedure given in [ 2 ]. In particular, similarly to what done in Example 4, we have to compare values at diferent levels in a taxonomy (e.g., september and autumn) and determine if they have a non-empty intersection (so that the transitive step can be applied).

3.2. Computing the Result with Specific Preferences

The propagation scheme described in the previous section is unable to deal with conflicting preferences, one of which is more specific than the other. In our working example, we have a generic preference for rock concerts over pop concerts (clause 1), yet we also have a more specific preference stating that a performance by Madonna takes precedence over any rock concerts (clause 2). Thus, according to 1 we would have, among others, ⪰ DT , whereas 2 would yield ⪰ DT , thus making and indiferent. We argue that giving the same importance to both preferences contradicts the intuition, as the more specific preference should take precedence over the more generic one.

We now detail how, given a formula DT, we can efectively solve conflicts by maintaining only more specific preferences.

If DT(1, 2) holds, we look at the clause that evaluates to true2 and, for each involved attribute, we consider the original level it has for both 1 and 2 (remind that DT has been obtained by applying level mappings). If an attribute does not appear in we set its level to the top level of its taxonomy (henceforth simply indicated by ⊤).

Example 5. Consider t-tuples and in Figure 1 and clause 2(1, 2) = (1[Artist] = Madonna) ∧ (2[Genre] = rock). Note that 2(, ) holds and the original levels when evaluating 2 for are (Genre, ⊤, ⊤, ⊤), while those for are (Artist, ⊤, ⊤, ⊤). Overall, this leads to a pair of t-schemas, spp(1, 2) = ⟨sig1,2(1), sig1,2(2)⟩. Notice that sig1,2(1) is the t-schema for 1 when we test if 1 is preferred to 2, which, in general, is diferent from sig2,1, i.e., the t-schema for 1 when we test if 2 is preferred to 1. This motivates the use of subscripts.

2Generalization to the case in which more than one clause is true is immediate.

Algorithm 1: Computing the best t-tuples in .

Input: t-relation with t-schema = {1 : 1, . . . , : }, formula DT.

Output: ≻ DT.

1. let := ∅ 2. for each ∈ 3. let := true 4. for each ′ ∈ 5. cases 6. DT(, ′) ∧ (DT(′, ) ∧ = MoreSpecificPref(, ′) ∨ ¬DT(′, )) :

:= ∖ {′} 7. DT(′, ) ∧ (DT(, ′) ∧ ′ = MoreSpecificPref(, ′) ∨ ¬DT(, ′)) :

let := false; break 8. if then := ∪ {} 9. return

When also DT(2, 1) holds, i.e., we have a conflict, we compare spp(1, 2) and spp(2, 1) = ⟨sig2,1(2), sig2,1(1)⟩ and conclude that the first preference is more specific than the second if sig1,2(1) ≤ sig2,1(1) and sig1,2(2) ≤ sig2,1(2), with at least one t-schema being strictly more specific.

Example 6. Assume we are comparing t-tuples and in Figure 1. From clause 1 in Example 3 (1(1, 2) = (1[Genre] = rock) ∧ (2[Genre] = pop)) we derive that ⪰ DT , whereas ⪰ DT follows from clause 2. For the first preference we have spp(, ) = ⟨(Genre, ⊤, ⊤, ⊤), (Genre, ⊤, ⊤, ⊤)⟩, whereas for the second we have spp(, ) = ⟨(Artist, ⊤, ⊤, ⊤), (Genre, ⊤, ⊤, ⊤)⟩. Although for the two t-schemas are the same, for Artist is strictly more specific than Genre, thus is strictly preferred to . In order to compute the best results according to the (transitively closed) rewritten formula DT we can use any algorithm developed for returning the best objects in a strict partial order, such as those in [ 9, 7 ], by suitably adapting it to work in our scenario. Algorithm 1 is such an adaptation of the well-known BNL algorithm [ 9 ]. In the algorithm the “specificity test” is performed by the procedure MoreSpecificPref(, ′), which returns if the preference ⪰ DT ′ is more specific than ′ ⪰ DT , ′ in the opposite case, and nil otherwise.

4. Conclusions

In this paper we have studied preference propagation along several taxonomies, when the levels at which preferences are stated and that of the stored data difer. The preference model we have proposed is able to deal with conflicting preferences in an efective way, thus propagating only the most specific preferences.

The specificity principle we use in this paper was also considered in [ 10, 11 ], although on a preference model using strict rather than weak preferences and in a diferent scenario regarding preferences combined across diferent contexts (not preference formulas): if ≻ holds in context , and ≻ in context ′, then ≻ prevails if is more specific than ′. The problem of dealing with preferences defined on diferent schemas, which is the main focus of the present paper, was not addressed at all in [ 10, 11 ].

The interplay between specificity and transitivity is studied in depth in [ 12 ].

Propagation of preferences in OLAP systems is considered in [ 13 ], where an algebraic language is adopted. Propagation occurs along hierarchies of levels, however no issue concerning combination of conflicting preferences is considered. Unlike most works studying the problem of managing qualitative preference queries on databases [ 3 ], in which the preference relation is a strict partial order ≻ , in this paper we have considered “weak" preferences ⪰ . This choice originates from the observation that, while propagating preferences between diferent t-schemas, transitivity cannot be guaranteed and a transitive closure is needed. However, enforcing transitivity might lead to cycles, which are harmless in our model but cannot occur in strict partial orders.

Future work includes the study of eficient methods for computing the transitive closure of the preference formula, the development of ad hoc algorithms for determining the best objects that scale over very large datasets, and an experimental evaluation on real-world scenarios.

References

[1] F. Ricci , L. Rokach , B. Shapira , Introduction to recommender systems handbook , in: Recommender Systems Handbook , Springer, 2011 , pp. 1 - 35 .

[2] J. Chomicki , Preference formulas in relational queries , TODS 28 ( 2003 ) 427 - 466 .

[3] K. Stefanidis , G. Koutrika , E. Pitoura , A survey on representation, composition and application of preferences in database systems , TODS 36 ( 2011 ) 19 : 1 - 19 : 45 .

[4] P. Ciaccia , D. Martinenghi , R. Torlone , Finding preferred objects with taxonomies , in: ER , 2019 , pp. 397 - 411 .

[5] D. Martinenghi , R. Torlone , Querying databases with taxonomies , in: ER , 2010 , pp. 377 - 390 .

[6] D. Martinenghi , R. Torlone , Taxonomy-based relaxation of query answering in relational databases , VLDB J . 23 ( 2014 ) 747 - 769 .

[7] R. Torlone , P. Ciaccia , Which are my preferred items? , in: RPEC , 2002 , pp. 217 - 225 .

[8] C. Y. Chan , H. V. Jagadish , K. Tan , A. K. H. Tung , Z. Zhang , Finding k-dominant skylines in high dimensional space , in: SIGMOD , 2006 , pp. 503 - 514 .

[9] S. Börzsönyi , D. Kossmann , K. Stocker , The skyline operator , in: ICDE , 2001 , pp. 421 - 430 .

[10] P. Ciaccia , D. Martinenghi , R. Torlone , Foundations of context-aware preference propagation , J. ACM 67 ( 2020 ) 4: 1 - 4 : 43 .

[11] P. Ciaccia , R. Torlone , Modeling the propagation of user preferences , in: ER , 2011 , pp. 304 - 317 . Best paper award.

[12] P. Ciaccia , D. Martinenghi , R. Torlone , Preference queries over taxonomic domains , Proceedings of the VLDB Endowment ( 2021 ) to appear.

[13] M. Golfarelli , S. Rizzi , P. Biondi, myOLAP: An approach to express and evaluate OLAP preferences , TKDE 23 ( 2011 ) 1050 - 1064 .