Preference construction for database querying
Jan Chomicki, Denis Mindolin · Dissertations & Theses @ SUNY Buffalo,ProQuest Dissertations & Theses Global · 2009
In this dissertation, we develop methods of constructing preferences in the binary relation preference framework. This framework has been introduced recently to allow querying databases using preferences. Preferences here are strict partial order binary relations over objects. The framework allows for finite and infinite preference relations (represented as finite formulas). Having a high expressive power, the binary relation framework lacks simple user-oriented methods of constructing preferences. Therefore, special query interfaces need to be developed to simplify the process of building preferences. In order to make preference construction easier, we pursue the following research directions. First, we study the problem of attribute importance in preference relations. We propose a class of preference relations called p-skylines which extend widely used skyline preference relations with the notion of attribute importance. We show that attribute importance in p-skylines can be captured as graphs. We study properties of p-skyline relations and show methods of checking containment and dominance testing in this framework. We introduce an algorithm of computing minimal extensions of p-skyline relations. Second, we propose to use the sets of the most preferred and the most unpreferred objects to discover importance of attributes in the underlying p-skyline relations. We study the complexity of the discovery problem and show an efficient algorithm for discovery of p-skyline relations given sets of most preferred objects. Third, we propose to view a variant of the CP-net framework to construct preferences as preference relations. CP-nets is a well established graphical model of preference specification, widely used in AI. We introduce an original variant of CP-nets, which allows to work with infinite domains. We develop an algorithm of constructing polynomial-size formulas representing the relations induced by given CP-net instances. Fourth, we develop a method of constructing preference relations by discarding subsets of existing preference relations. Discarding preferences is a common way of changing preferences in real life. The operation of preference contraction we develop here allows for contracting finite and infinite preference relations represented as formulas. We propose several variants of the preference contraction operator, study their properties, and introduce algorithms for their evaluation.