I. Introduction
Ranking queries are a powerful concept in focusing attention on the most important answers to a query. To deal with massive quantities of data, such as multimedia search, streaming data, web data and distributed systems, tuples from the underlying database are ranked by a score, usually computed based on a user-defined scoring function. Only the top- tuples with the highest scores are returned for further inspection. Following the seminal work by Fagin et al [13], such queries have received considerable attention in traditional relational databases, including [23], [19], [36] and many others. See the excellent survey by Ilyas et al. [20] for a more complete overview of the many important studies in this area.