The BNL⁺⁺ Algorithm for Evaluating Pareto Preference Queries

Abstract: Deeply personalized database applications require intuitive and powerful preference query languages like Preference SQL, employing preference constructors that are closed under strict partial order semantics. However, sophisticated preference query optimization and efficient evaluation techniques are essential for a large-scale and successful practical use. In this paper we focus on the evaluation of an important class of Pareto preference queries that frequently occur in practice, a subset of which are the well-known skyline queries. Our new algorithm, called BNL⁺⁺, succeeds in considerably speeding up the usual block-nested loop (BNL) algorithm. In fact, a careful analysis of the underlying `better-than' graph enables us to identify new and effective pruning conditions. The applicability of BNL⁺⁺ also covers complex situations, where existing index-based evaluation algorithms cannot be used. At this stage BNL⁺⁺ is preliminary work. The next step will be to evaluate the performance of BNL⁺⁺ with a large practical e-commerce use case.

Downloads:

• The BNL⁺⁺ Algorithm for Evaluating Pareto Preference Queries - (bnl.pdf, 129 KB)