Exploring large databases

• You have a large database of buildings (or any other geometric object). A building is defined by its position (coordinates), height, length and width. The question is: which buildings are visible from a certain point in space? (Figure 1a)
• You have a database of hotels. Each hotel is characterized by its price, its distance to the beach, the standard of the rooms, restaurants, and extras such as swimming pool, spa, Internet connection, or air conditioning. The question is: what is the best hotel for me if I wish to spend my vacation in Bahamas? (Figure 1b)
• You have a database of purchase orders and sales representatives. The question is: which sales representative deserves a bonus or even an award?
• You subscribe to an online car market that posts offerings for used cars. You would like to have a Japanese car that is cheap and had at most two owners before. The question is: how do you filter out irrelevant offers?

All these questions have two things in common: (a) they are difficult to answer using today's generation of database systems; (b) a simple extension that we refer to as the „Skyline Operator“ enables a stateof-the-art database system to process all these questions efficiently.

The Skyline Operator determines interesting records from a potentially large set of records. A record is interesting if is not dominated by other records in terms of user-specified values; for instance, a hotel is interesting for a tourist if it is closer to the beach than other hotels and cheap at the same time. In this project, we explore possible applications
of the Skyline Operator, devise efficient algorithms to compute the Skyline Operator, show how it can be integrated into existing, state-of-the-art database systems (e.g., relational databases), and show how it can be extended in order to work in publish & subscribe systems.