Multi-objective Query Processing for Database Systems

TitleMulti-objective Query Processing for Database Systems
Publication TypeConference Paper
Year of Publication2004
AuthorsBalke, W. - T., and U. Güntzer
Conference Name30th International Conference on very Large Databases (VLDB 2004)
Conference LocationToronto, Canada

Query processing in database systems has developed beyond mere exact matching of attribute values. Scoring database objects and retrieving only the top k matches or Pareto-optimal result sets (skyline queries) are already common for a variety of applications. Specialized algorithms using either paradigm can avoid naïve linear database scans and thus improve scalability. However, these paradigms are only two extreme cases of exploring viable compromises for each user‘s objectives. To find the correct result set for arbitrary cases of multi-objective query processing in databases we will present a novel algorithm for computing sets of objects that are non-dominated with respect to a set of monotonic objective functions. Naturally containing top k and skyline retrieval paradigms as special cases, this algorithm maintains scalability also for all cases in between. Moreover, we will show the algorithm’s correctness and instance-optimality in terms of necessary object accesses and how the response behavior can be improved by progressively producing result objects as quickly as possible, while the algorithm is still running.

vldb04.pdf432.65 KB