Efficient Evaluation of Numerical Preferences:Top k Queries, Skylines and Multi-objective Retrieval

Preferences: Specification, Inference, Applications

计算机科学;物理学

Wolf-Tilo Balke

Others  :  http://drops.dagstuhl.de/opus/volltexte/2006/400/pdf/04271.BalkeWolfTilo.ExtAbstract.400.pdf
PID  :  7275

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

Query processing in databases and information systems has developed beyond mere SQL- style exact matching of attribute values. Scoring database objects according to numerical userpreferences and retrieving only the top k matches or Pareto-optimal result sets (skylinequeries) are already common for a variety of applications. Recently a lot of database literature has focussed on how to efficiently evaluate queries basedon numerical preferences. Specialized algorithms using either top k retrieval (assuming asingle compensation function defined over all query predicates, i.e. a global utility function)or computing skylines (assuming all query predicates as pairwise incomparable) have beenshown to be capable of avoiding naïve linear database scans by pruning large numbers ofdatabase objects and thus vastly improve scalability. However, both paradigms are only twoextreme cases of exploring viable compromises for each user‘s objectives, which may or maynot be comparable. To find the correct result set for arbitrary cases of multi-objective query processing indatabases a novel algorithm for computing sets of objects that are non-dominated with respectto a set of monotonic objective functions representing a user's notion of utility, has recentlybeen presented. Naturally containing top k and skyline retrieval paradigms as special cases,this algorithm maintains scalability also for all cases in between. To be more precise, in bothspecial cases the multi-objective retrieval algorithm will behave exactly like the most efficientknown evaluation algorithms for top k and skyline queries respectively. This algorithm hasalso been proved to be correct and instance-optimal in terms of necessary object accesses.Moreover, it improves the psychological response behaviour by progressively producingresult objects as quickly as possible, while the algorithm is still running, so user can deal withresult objects at the earliest point in time.Our tutorial will discuss all state of the art algorithms for top k retrieval, skyline queries andmulti-objective retrieval and point to open problems, future extensions of the paradigm andresearch in numerical preferences. (DagstuhlSeminarSeriesNr04271.27.06.02.07.04G.Bosi,R.Brafman,J.Chomicki,W.Kießling:Preferences:Specification,Inference,Applications)