Relational and Algebraic Calculi for Database Preferences

Relational methods in computer science have been studied intensively in the last decades, especially for program verification and correctness. In the present thesis we apply them to database preferences, which are a generalization of Skyline queries. This topic is connected to relations and algebra in various respects. The formal basis of databases is given by the relational data model, and preferences are strict order relations on tuples from a given data set. Moreover, preference operators and operands form an algebraic structure by themselves, which led to the research field of algebraic optimization of database preference queries. In this work we develop a coherent family of calculi for dealing with database preferences. Wherever possible, we use algebraic structures such as semirings, abstract relation algebras, and related concepts. The relational algebraic approach allows us to reason about many aspects of Skyline computation and preference term equivalences in a point-free way. We generalize and unify existing theorems in the scope of database preferences and simplify some of their proofs by means of algebraic structures. Next to this, we introduce the new field of preference decomposition. A subgoal of this is the characterization of the expressiveness of preference queries, i.e., the classification of orders constructed by a given class of preference terms. The results of this thesis have various applications regarding the correctness, soundness and efficiency of database preference implementations. In addition to our theoretical contributions we implemented the rPref package (available at CRAN) for handling preferences within the statistical computing software R. There is a tight connection between our calculi and the query language in that package. This allowed us to implement the algorithms and examples from the theoretical parts of this thesis, demonstrating the applicability of our results