Skyline Operator Implementation into PostgreSQL

This is a web frontend to PostgreSQL 8.3.5 with our implementation of the skyline operator (SQL SKYLINE OF-clause) [Borzsonyi2001].

You may wish to consult the [PostgreSQL 8.3.5 Documentation].

Extended Query Syntax

TODO: describe extended query syntax

Skyline Query Examples

SELECT * FROM nba.players 
SKYLINE OF (h_feet * 12 + h_inches) MAX NULLS LAST, weight MAX NULLS LAST;

SELECT * FROM boot SKYLINE OF personen MAX, tiefgang MIN;

SELECT b.*, sb.segelflaeche FROM boot b JOIN sportboot sb ON (b.id = sb.id) 
SKYLINE OF b.personen MAX, b.tiefgang MIN, sb.segelflaeche MAX;

SELECT e.*, w.sumlaenge
FROM 
(
	SELECT mname, wname, wjahr, sum(punkte) as sumpunkte
	FROM erzielt
	GROUP BY mname, wname, wjahr
) as e JOIN
(
	SELECT name as wname, jahr as wjahr, sum(laenge) as sumlaenge
	FROM wettfahrt
	GROUP BY wname, wjahr
) as w ON (e.wname = w.wname AND e.wjahr = w.wjahr)
SKYLINE OF sumpunkte MAX, sumlaenge MIN;

Using different strategies and showing query plans

EXPLAIN ANALYZE SELECT * from rds3d('indep', 1000, 0) 
SKYLINE OF d1 MIN, d2 MIN, d3 MIN 
WITH BNL SLOTS=10;

EXPLAIN ANALYZE SELECT * from rds3d('indep', 1000, 0)
SKYLINE OF d1 MIN, d2 MIN, d3 MIN 
WITH EF EFSLOTS=5 SFS;

Available Datasets

• Synthetic datasets as described in [Borzsonyi2001] are available through a set of set returning functions. For e.g. SELECT * from rds2d('indep', 10, 0);, where the general syntax is as follows:

    random_dataset : "rds" dimension "d" "(" distribution_type "," rows "," seed ")"
    dimension := "1" | "2" | ... | "20"
    distribution_type := "'indep'" | "'corr'" | "'anti'"
    rows := "0" | "1" | ...
    seed := "0" | "1" | ...
  

  Examples:

  SELECT * from rds3d('anti', 100, 0) SKYLINE OF d1 MIN, d2 MIN, d3 MIN;
  
  SELECT * from rds4d('corr', 100, 1) SKYLINE OF d1 MIN, d2 MIN, d3 MIN, d4 MIN;
  

• The Datanmodellierung WS2007 dataset.
  TODO: add link
  TODO: add description
• The databaseBasketball.com 2.0 dataset (details), containing:
  • nba.coaches_career
  • nba.coaches_season
  • nba.draft
  • nba.player_allstar
  • nba.player_playoffs
  • nba.player_playoffs_career
  • nba.player_regular_season
  • nba.player_regular_season_career
  • nba.players
  • nba.team_season
  • nba.teams
• The pro-football-reference.com dataset (up to 2006) (details), containing:
  • football.master
  • football.seasons
  • football.games

Is there a dataset missing, that you'd like to query on? Let us know, and feel free to contact Hannes Eder.

Source Code / Patch

The source code for our implementation is available as patch, which applies against PostgreSQL 8.3-stable (currently 8.3.6):

skyline-of-200903111.patch.tar.gz

WIP (Work In Progress): We are currently porting our implementation to 8.4-devel.

Old versions

skyline-of-200811131.patch.tar.gz (applies only to PostgreSQL 8.3-stable as of 2008-11-13, which is outdated now; use a newer version from above)

The file skyline-of-200901261.patch.tar.gz is incomplete so it was taken offline.

Publications

• Hannes Eder: On Extending PostgreSQL with the Skyline Operator. Master's thesis, Vienna University of Technology, 2009.
  [ bib  | pdf (oneside)  | pdf (twoside) ]
• Hannes Eder, Fang Wei: Evaluation of Skyline Algorithms in PostgreSQL. 13th International Database Engineering & Application Symposium (IDEAS '09), Calabria, Italy, September 2009
  [ bib  | pdf ]

References

• [Borzsonyi2001] Börzsönyi, S.; Kossmann, D. & Stocker, K.: The Skyline Operator, In ICDE, 2001, 421--432