We formally investigate the problem of retrieving the best results complying with multiple preferences expressed in a logic-based language when data are stored in relational tables with taxonomic domains. We introduce two operators that rewrite preferences for enforcing transitivity, which guarantees soundness of the result, and specificity, which solves conflicts among preferences. We show that these two properties cannot be achieved together and identify the only two possibilities to ensure transitivity and minimize conflicts. Our approach proves efective when tested over both synthetic and real-world datasets.
Veneto
Verona Valpolicella
Tuscany
Piedmont Siena
Asti Roero Cuneo Langhe white rosé red Masi Bertani Montenidoli Casorzo Correggia Laficaia
Ceretto Arneis
Canaiolo
Amarone Barolo preferences so as to guarantee that they are transitive and specific . The latter property means that, in case of conflicts, the more specific preference overrides the more generic one. For instance the specific preference for Amarone over white wines counts more than the that for white wines over red ones.
We therefore study, from both a theoretical and a practical point of view, how transitivity and specificity can be obtained by suitable rewritings of the initial preferences. We tackle the problem by introducing two operators that rewrite preferences expressed as FO formulas: T to enforce transitivity and S to remove conflicts between preferences. We prove that it is unfortunately impossible to guarantee at the same time transitivity and a complete absence of conflicts, no matter the order in which T and S are considered and how many times they are applied. Intuitively, the removal of conflicts may compromise transitivity, whereas enforcement of transitivity may (re-)introduce conflicts. In spite of this, we formally show that: (i) the set of all possible sequences of operators can be reduced to a finite (and small) set, (ii) there are only two sequences that guarantee transitivity and minimize residual conflicts between preferences, and (iii) the best results obtainable via these two sequences may be very diferent.
A number of experiments shows that the computation of the best results largely benefits from the minimization of conflicts between preferences, while incurring a low overhead due to the rewriting process.
The full version of this paper has appeared in [
We consider a simple extension of the relational model in which the values of an attribute can be arranged in a hierarchical taxonomy, i.e., a poset = (, ≤ ), where is a set of values and ≤ is a partial order on .
Given a set of attribute-taxonomy pairs 1 : 1, . . . , : , let denote the set of all possible tuples over any schema that can be defined using such pairs. A preference relation is a relation ⪰ on × . Given 1 and 2 in , if 1 ⪰ 2 then 1 is (weakly) preferable to 2. If 1 ⪰ 2 but 2 ̸⪰ 1, then 1 is strictly preferable to 2, denoted by 1 ≻ 2.
We consider that preferences are expressed via an intrinsic preference formula [
Example 2. The preferences in Example 1 can be expressed as 1(, ) ∨ 2(, ) ∨ 3(, ) ∨ 4(, ), which can be compactly written as: 1 = white ⪰ red (short form of 1(, ) = ([Wine] ≤ white) ∧ ([Wine] ≤ red)), 2 = Amarone ⪰ white, 3 = Siena ⪰ Asti, 4 = Langhe ∧ aged ⪰ Langhe ∧ young.
Now we introduce two operators that can be applied to a preference relation: Transitive closure (T) and Specificity-based refinement ( S). Let ⪰ denote the initial preference relation; the resulting relation is indicated ⪰ T for T and ⪰ S for S. Multiple application of operators, e.g., first T and then S, leads to the relation (⪰ T)S, which we compactly denote as ⪰ TS. In general, for any sequence ∈ {T, S}* , ⪰ X is the preference relation obtained from the initial preference relation ⪰ by applying the operators in the order in which they appear in X. Notice that ⪰ = ⪰ , where denotes the empty sequence.
We describe the behavior of the two operators by means of suitable rewritings of a preference formula. Given a sequence X of operators, and an initial (input) formula (, ) inducing the preference relation ⪰ , X(, ) denotes the rewriting of that accounts for the application of the X sequence, yielding ⪰ X.
Transitive Closure. Transitivity of ⪰ , and consequently of ≻ , is a basic requirement of any
sound preference-based system. If ⪰ is not transitive then ≻ might contain cycles, a fact that
could easily lead either to empty or non-stable results [
The transitive closure operator, denoted T, given an input preference relation ⪰ X yields the
preference relation ⪰ XT. The transitive closure XT of an ipf X with statements 1, . . . ,
is still a finite ipf that can be computed as described in [
The fact that the transitive closure is computed with respect to the (possibly infinite) domain
of the tuples, and not with respect to a (finite) relation of tuples, is quite standard for
preference relations (see e.g., [
Example 3. Continuing with Example 2, the transitive closure of is the formula T that, among others, adds the following statements to : 5 = Amarone ⪰ T red
6 = Siena ⪰ T Langhe ∧ young Statement 5 clearly follows from 2 and 1, whereas 6 is obtained from 3 and 4, since there exists at least one winery that is both in the Asti province and in the Langhe region (Casorzo is one of them).
After applying the T operator, we simplify the formula as needed, and, in particular, we remove statements that are subsumed by other statements. Similarly, we also simplify statements by removing contradictory clauses and clauses subsumed within the same statement. Specificity-based Refinement. The most intriguing of our operators is S. As apparent from Example 2, conflicting preferences , such as ⪰ and ⪰ (induced by 1 and 2, resp.), may hold. To solve this problem we resort to a specificity principle , borrowed from nonmonotonic reasoning, stating that more specific information should prevail over more generic one. Therefore, giving the same importance to, e.g., 1 and 2, the former being more generic, contradicts the intuition.
The specificity principle we adopt for analyzing conflicting preferences is based on the extension of preferences statements, i.e., on the set of pairs of tuples in for which a statement is true.
Definition 1 (Specificity principle) . Let ⪰ X be a preference relation, and let X be the corresponding formula. Let and be two preference statements in X. We say that is more specific than if, for any pair of tuples 1, 2 ∈ such that (1, 2) is true, then (2, 1) is also true, and the opposite does not hold.
From Definition 1 we can immediately determine how a less specific statement has to be rewritten so as to solve conflicts.
Lemma 1. A preference statement (, ) is more specific than (, ) if (, ) implies (, ) (written (, ) → (, )) and the opposite does not hold.
According to Lemma 1, when (, ) implies (, ) the S operator replaces (, ) with ′(, ) = (, ) ∧ ¬(, ), so that and ′ do not induce any conflicting preferences. Example 4. Continuing with Example 3, the application of the S operator amounts to rewriting formula T by replacing the clause 1(, ) with 1(, ) ∧ ¬2(, ), since 2(, ) → 1(, ). This, after distributing ¬ over the two predicates in 2 and simplifying, leads to the new clause: 7 = white ⪰ TS red ∧ ¬Amarone.
In this section we analyze the efect of performing the operations described in the previous section, and prove some fundamental properties.
In order to clarify the relationships between the results of the diferent operations, we introduce the notions of equivalence and containment between sequences of operators. Definition 2 (Equivalence and containment). Let X, Y ∈ {T, S}* ; X is contained in Y, denoted X ⊑ Y, if for every initial preference relation ⪰ , ⪰ X⊆⪰ Y; X and Y are equivalent, denoted X ≡ Y, if both X ⊑ Y and Y ⊑ X.
We observe that T and S are idempotent, T is monotone and cannot remove preferences, while S cannot add preferences. In addition, the preference relation obtained after applying T on the initial preference relation ⪰ is maximal, in that it includes all other relations obtained from ⪰ by applying T and S in any way.
XTT ≡ XT
XT ⊑ YT
X ⊑ XT X ⊑ T
XSS ≡ XS
XS ⊑ X idempotence monotonicity inflation / deflation maximality (1) (2) (3) (4)
We call complete those sequences that include both T and S. A sequence X is transitive if, for every initial preference relation ⪰ , ≻ X is transitive. Eventually, our goal is to drop conflicting and less specific preferences while preserving transitivity. To this end, we add minimality with respect to ⊑ as a desideratum.
The following, non-trivial result shows that we can focus on just eight sequences, shown in Figure 2, because any sequence is equivalent to one of them.
Theorem 2. Let X ∈ {T, S}* . Then ∃Y ∈ {, T, S, TS, ST, TST, STS, STST} such that X ≡ Y.
T ST STST
STS ε S
TST TS
To give an intuition, we observe that i) consecutive repetitions of the same operator are idle (via idempotence) and ii) the repeated application of a TS sufix does not change the semantics of a sequence (i.e., XTS ≡ XTSTS).
Minimality and transitivity. Generally, any complete sequence not ending with S is nonminimal, in that it may contain conflicting preferences (possibly introduced by T) that turn out to be in contrast with other, more specific preferences. We exemplify this on ST using a single taxonomy about time.
Example 5. Let consist of 1 = autumn ⪰ sep and the more specific 2 = sep10 ⪰ oct10. By specificity, in S, 1 is replaced by the statement 3 consisting of two clauses: autumn ⪰ sep ∧ ¬sep10 and autumn ∧ ¬oct10 ⪰ sep. In ST, the clauses in 3 transitively combine into 1 again, since, e.g., the value sep30 is below sep but not sep10 and below autumn but not oct10; therefore oct10 ⪰ ST sep10 holds. However, in STS, 1 is again replaced by 3, so that oct10 ̸⪰ STS sep10, which shows that ST is not minimal.
All the containments indicated in Figure 2 are strict, as can be shown through constructions similar to that of Example 5, so no sequence ending with T is minimal in {T, S}* .
Transitivity is achieved for any sequence ending with T, while no sequence ending with S is transitive. Therefore, we summarize our finding in the following major result. Theorem 3. Let X ∈ {T, S}* . Then XT is not minimal and XS is not transitive, thus no sequence is both transitive and minimal.
Since transitivity and minimality cannot be both achieved at the same time, we enforce transitivity (which cannot be waived) and look for the minimal sequences among those that are transitive, which we call minimal-transitive sequences.
We first observe that all complete sequences starting with S are incomparable with those starting with T (also refer to Figure 2). Therefore, only three sequences are both complete and transitive: ST, TST and STST, the first of which contains the last one and is therefore not minimal. The remaining two sequences are transitive, incomparable, and, therefore, minimal in the set of complete and transitive sequences.
Theorem 4. The only minimal-transitive sequences are TST and STST.
The result of Theorem 3 is inherent and no finer granularity in the interleaving of T and S (e.g., by making S resolve one conflict at a time instead of all together) would remove this limitation. Furthermore, this limitation is unavoidable and we can prove that no method whatsoever (not just those based on the T and S operators) could solve it.
Given a relation ⊆ , the “best” tuples in according to the preference relation ⪰ can be
selected by means of the Best operator [
As shown in Section 3, TST and STST are incomparable, thus there will be relations and input preference relations ⪰ for which the best results delivered by the two semantics will difer. In order to quantify the diference between these results, we define, for any two sequences X and Y, Diff (X, Y, ) as the worst-case size of the diference in the results delivered by X with respect to those due to Y, for any given cardinality of the input relation . We have: Theorem 5. Diff (TST, STST, ) = Θ( ); Diff (STST, TST, ) = Θ( ).
From a practical point of view, Theorem 5 shows that there is no all-seasons minimal-transitive semantics. Furthermore, there can be cases (used in the proof of the theorem) in which the
TST STST T ε 25 ts()20 s e15 B r fo10 e itm 5 0
TST STST T ε average median (a) Cardinality of . number of best results from any of the two semantics is comparable to , whereas the other semantics returns (1) tuples.
For space reasons, we only give hints at our experimental results and refer the reader to [
In our experiments, as recognized in the germane literature [
The algorithm we adopt for computing is an improved version of BNL, exploiting a heuristics tailored to our scenario, which pre-sorts the input relation so that the tuples matching the left side of a clause and corresponding to more specific values in the taxonomies come first. The rationale is that these values are likely associated with a smaller amount of tuples, so that a smaller partial result can be found before scanning large amounts of data. Furthermore, such tuples are likely to be preferred to many others, in particular when specificity is a concern.
Besides testing real taxonomies, we experimented on a variety of synthetic datasets, generated according to various taxonomy topologies (regular, random, and scale-free), dataset sizes (up to 1M tuples), attributes (up to 5), and input preferences (up to 10). Figure 3a shows our results using default parameter values (regular taxonomy on 1 attribute, two conflicting preference statements, 10K tuples). The amount of relevant tuples is roughly 40% of the size of the dataset. Both T (i.e., only enforcing transitivity) and (i.e., no rewriting of the preference formula) retain about half of the relevant tuples (which is both the average and the median value we obtained), while TST and STST retain less than 2% in the median case (the average value goes up to 20% due to runs with unfocused input formulas referring to values not in the dataset). This is reflected in the computation times, shown in Figure 3b, which are consistently around 24 for T and 10 for , but nearly two orders of magnitude smaller in the median case for TST and STST.
This confirms that our approach is efective both in reducing the cardinality of and in achieving substantial speedup with respect to baseline strategies. Similar results are obtained in all other scenarios we tested.
We observe that the application of T alone corresponds to the work performed by preference
evaluation methods that only aim at guaranteeing transitivity, e.g., [
In this paper we have tackled the problem of finding the best elements from a repository on
the basis of preferences referring to values that are more generic than the underlying data
and may involve conflicts. To this aim, we have introduced and formally investigated two
operators for enforcing, in a given collection of preferences, the properties of specificity, which
can solve conflicts, and transitivity, which guarantees the soundness of the final result. We
have then characterized the limitations that can arise from their combination and identified
the best ways in which they can be used together. We have finally shown, with experiments
over both synthetic and real-world datasets, the efectiveness and practical feasibility of the
overall approach. We remark that the need to address conflicts arising from preferences was also
observed in [