Preferences and Preference-SQL

Preferences are present in our everyday life, they help to express personal appraisals such as "I prefer Y over X". At the same time, this statement should be defined intuitively and should further be valid for both numerical (quantitative) and categorical (qualitative) attribute domains (set of allowed values for X,Y). Besides these basic preferences there also exist complex preferences that are based on multipe attributes. Furthermore, there have to be elements which are not comparable.

Based on these requirements, prerequisites for a suitable preference-model can be infered:

• preferences are distinct from hard constraints
• preferences are not necessarily purely numerical
• preferences are not necessarily total orders

Besides such a postulated preferences-model which covers the points stated above, a corresponding querying-model is needed in order to integrate preferences into existing DBMS.

The formal preference-model defines preferences as strict partial orders. If two elements are unranked as a pair, they are called "indifferent elements". Elements which are not dominated by any other element are further called "maximal elements". The ranking of elements can additionally be visualized as a Hasse-diagram.

The constructor-based approach defines the following intuitive preferences based on categorial attributes:

• POS(A, POS-set)
• NEG(A, NEG-set)
• POS/NEG(A, POS-set; NEG-set)
• POS/POS(A, POS1-set; POS2-set)
• LAYERED_m(A, L)
• EXPLICIT(A, E-graph)

Furthermore, the following intuitive preferences are defined based on numerical attributes:

• AROUND(A, z)
• BETWEEN(A, [low, up])
• LOWEST(A)
• HIGHEST(A)

Finally, SCORE(A, f) defines a preference with numerical evaluation while the modification SCORE_d(A, f) enables a categorical view on numerical domains.

These categorical and numerical base preference constructors can further be combined via complex preference constructors to form extensive expressions in preference-algebra:

• ParetoPreference
• Prioritized Preference
• RankingPreference
• IntersectionPreference
• DisjointUnionPreference
• Linear Sum Preference

On the lines of the formal model a Best-Match-Only (BMO)-querying-model is defined which in contrast to standard SQL queries reduces the flooding effect and completely eliminates the empty result effect. Using BMO, preferences are characterized as soft constraints, meaning that an optimal result is returned (maximal elements) if it exists. If an optimal solution doesn't exist, the best alternatives are returned, thus avoiding an empty result set. The result of a BMO-query thus adapts to the quality of data contained in the database.

The queries are formulated in Preference-SQL and handed to the DBMS. Several modes of interlocking between the DBMS with PSQL are defined, beginning with a lose interconnection, hybrid interconnection up to a tight interconnection.

A more extensive overview about PSQL, preference algebra and BMO is provided in the following publications:

• W. Kießling  Foundations of Preferences in Database Systems
• W. Kießling  Preference Queries with SV-Semantics