Ranked Relations: Query Languages and Query Processing Methods for Multimedia

In this paper, we describe the notion of a ranked relation that incorporates to the relational data model the notion of rank, i.e. ordering among tuples or objects. The ordering of tuples may be based on a single rank information, or multiple ranks combined together. We show that such relations arise naturally in many applications, especially in applications that query outside sources and return ranked relations as answers to content based queries. We introduce an algebra for querying ranked relations and give examples of its use for various applications. We then prove various properties of the algebra with special emphasis on the preservation of the coherence property, which shows when different rank columns are guaranteed to induce the same ordering among tuples. We show how these properties can be used to produce approximate early returns. Finally, we give experimental results based on Internet search engines for our early returns method and show that our method provides meaningful and fast answers to the user.