An algebra of database preferences

• We describe database preferences within a typed abstract relation algebra, allowing point-free proofs for related theorems.
• The proofs can be done by off-the-shelf theorem provers, which is exemplified in the paper.
• We present a “join algebra” which purely algebraically handles typed relations.
• We give an algebraic presentation of a new kind of preferences together with some interesting properties.
• We algebraically characterise the relationship between normality and noetherity.

Preferences allow more flexible and personalised queries in database systems. Evaluation of such a query means to select the maximal elements from the respective database w.r.t. the preference, which is a partial strict-order. We present a point-free calculus of such preferences and exemplify its use in proving algebraic laws about preferences that can be used in query optimisation. We show that this calculus can be mechanised using off-the-shelf automated first-order theorem provers.