Preference Queries over Taxonomic Domains

Paolo Ciaccia, Davide Martinenghi, Riccardo Torlone · 2025

Read Preference Queries over Taxonomic Domains by Paolo Ciaccia, Davide Martinenghi, Riccardo Torlone (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-05138.txt.

Introduction

Paolo Ciaccia, Davide Martinenghi, and Riccardo Torlone study how databases should honor user preferences, in a 2025 paper. A user may ask for the best rows under several likes at once — say, cheap and near. Those likes can clash, may be stated at a broad level while data sits at a fine one, and may even fail to line up in a clean order.

Data here live in tables whose values sit in taxonomies, trees that run from broad to narrow terms. The team add two tools that rewrite preferences so they line up in order and settle clashes by favoring the more specific like. They show the two goals cannot both be met in full. The work gives database builders firm rules for fair, sound answers to preference queries.

Catalog record

CREATORPaolo Ciaccia, Davide Martinenghi, Riccardo Torlone
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE99 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-05138

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Preference Queries over Taxonomic Domains Paolo Ciaccia, Davide Martinenghi, Riccardo Torlone Abstract When composing multiple preferences characterizing the most suitable results for a user, several issues may arise. Indeed, preferences can be partially contradictory, suffer from a mismatch with the level of detail of the actual data, and even lack natural properties such as transitivity. In this paper we formally investigate the problem of retrieving the best results complying with multiple preferences expressed in a logic-based language. Data are stored in relational tables with taxonomic domains, which allow the specification of preferences also over values that are more generic than those in the database. In this framework, we introduce two operators that rewrite preferences for enforcing the important properties of transitivity, which guarantees soundness of the result, and specificity, which solves all conflicts among preferences. Although, as we show, these two properties cannot be fully achieved together, we use our operators to identify the only two alternatives that ensure transitivity and minimize the residual conflicts. Building on this finding, we devise a technique, based on an original heuristics, for selecting the best results according to the two possible alternatives. We finally show, with a number of experiments over both synthetic and real-world datasets, the effectiveness and practical feasibility of the overall approach. 1 Introduction Preferences strongly influence decision making and, for this reason, their collection and exploitation are considered building blocks of content-based filtering techniques [ 12 , 69 , 68 ] . A key issue in this context is the mismatch that usually lies between preferences and data, which often makes it hard to recommend items to customers [ 50 ] . Indeed, whether they are collected by tracing the actions of the users or directly elicited from them, preferences are typically expressed in generic terms (e.g., I prefer pasta to beef), whereas available data is more specific (the menu might contain lasagne and hamburger). The problem of automatically suggesting the best solutions becomes even more involved when several preferences at different levels of granularity and possibly conflicting with each other are specified, as shown in the following example that will be used throughout the rest of the paper. Example 1 . We would like to select some bottles of wine from the list in Figure 1 available in an e-commerce store. We prefer white wines to red ones, yet we prefer Amarone (a famous red wine) to white wine. For the producer, we prefer Tuscan wineries located in the province of Siena to those in the Piedmont province of Asti. Moreover, if the winery lies in the Langhe wine region (which spans different provinces, partially including, among others, Asti and Cuneo) we prefer an aged wine (i.e., produced before 2017) to a more recent one. Finally, we would like to have suggestions only for the “best” possible alternatives. Wines Wine Winery Year Arneis Correggia 2019 a Amarone Masi 2014 b Amarone Bertani 2013 c Canaiolo Montenidoli 2015 d Barolo Laficaia 2014 e Arneis Ceretto 2019 f Figure 1: A list of wines We first observe that further information is needed in this example to identify the solutions that better fit all the mentioned preferences. For instance, we need to know the province and the wine region in which all the wineries are located. In addition, the example shows that there are two important issues that need to be addressed in such scenarios. First, conflicts can occur when preferences are defined at different levels of detail. Indeed, the preference for Amarone, which is a red wine, is in contrast with the more generic preference for white wines. Second, further preferences can be naturally derived from those that are stated explicitly. For instance, from the preference for wines from Siena to those from Asti and the preference for aged wines when they are from the Langhe region, we can also derive, by transitivity, a preference for wines from Siena to young wines from Langhe. In this paper we address the problem of finding the best data stored in a repository in a very general scenario in which, as in the above example: (i) preferences may not match the level of detail of the available data, (ii) there may be conflicts between different preferences, and (iii) known preferences can imply others. Specifically, unlike previous approaches that have only tackled the problem of mapping preferences to data (see, e.g., [ 53 ] ), we formally investigate the two main principles that need to be taken into account in this context: specificity and transitivity . Specificity is a fundamental tool for resolving conflicts between preferences by giving precedence to the most specific ones, as it is natural in practical applications. For instance, in our example, the specific preference for Amarone over white wines counts more than the generic preference for white wines over red ones. The specificity principle is indeed a pillar of non-monotonic reasoning, where a conclusion derived from a more specific antecedent overrides a conflicting inference based on a less specific antecedent [ 43 ] . On the other hand, transitivity, besides being a natural property, is important also from a practical point of view, since non-transitive preferences might induce cycles, a fact that could make it impossible to identify the best solutions [ 12 ] . To tackle the problem of dealing with non-monotonic preferences, we rely on a natural extension of the relational model in which we just assume that taxonomies , represented by partial orders on values, are defined on some attribute domains [ 60 ] . Thus, for instance, in a geographical domain we can establish that the value Italy is more generic than the value Rome , since the former precedes the latter in the partial order. We then call t-relations (i.e., relations over taxonomies) standard relations involving attributes over these taxonomic domains. We express preferences in this model in a declarative way, by means of first-order preference formulas specifying the conditions under which, in a t-relation, a tuple t_{1} is preferable to a tuple t_{2} . By taking advantage of the taxonomies defined over the domains, in a preference formula we can refer to values that are more generic than those occurring explicitly in a t-relation (e.g., the fact that we prefer white to red wines, as in Example 1 ). When evaluated over a t-relation r , a preference formula returns a preference relation that includes all the pairs of tuples (t_{1},t_{2}) in r such that t_{1} is preferable to t_{2} . Since the input preference formula may not induce a preference relation enjoying both transitivity and specificity, such a formula then needs to be suitably rewritten. Eventually, the rewritten formula is used to select the best tuples in r by means of the Best operator, which filters out all the tuples that are strictly worse than some other tuple [ 24 ] . How this rewriting has to be performed is thus the main focus of this paper. Problem. To study, from both a theoretical and a practical point of view, to which extent the properties of transitivity and specificity can be obtained by suitable rewritings of the initial preference formula. We tackle the problem by introducing and formally investigating two operators that

Read the complete text