Skylines & Dominance

01 · Foundation

Dominance and the skyline

The complaint against top-k is that you must supply weights, and users rarely know theirs. Skyline queries answer the same question with no parameters at all.

The primitive is dominance. Tuple $t$ dominates tuple $s$, written $t \prec s$, when

— nowhere worse, and strictly better at least once. Note the convention flip: in skyline literature lower values are better, the opposite of the score-space convention in chapter 9. It is only a convention, but mixing the two mid-exercise is a reliable way to get the wrong answer.

The skyline of a relation is its set of non-dominated tuples. The same object appears in three literatures under three names: maximal vectors in computational geometry, Pareto-optimal solutions in multi-objective optimization, and the skyline in databases — the name coming from the 2D picture, where the non-dominated points trace the contour of the dataset like a city skyline.

The property that makes it the right notion:

Read the biconditional carefully, because January 2026 turned it into a multiple-choice question and only one of four phrasings was correct. Three things must all be right: the function must be monotone (not arbitrary — an arbitrary function can make any point win; and not merely linear, which is a strict sub-case); the tuple must be strictly better than every other tuple; and ties with itself are obviously exempt. A formulation using $\ge$ rather than $>$ is satisfied by any constant function and therefore says nothing.

This also means a skyline is not a top-k result in disguise: there is no scoring function that, on all possible instances, returns the skyline points in the first $k$ positions.

02 · SQL

Skylines in SQL

There is a proposed syntax, not part of the standard, and a literal translation that shows why a dedicated operator is worth having.

SELECT ... FROM ... WHERE ... GROUP BY ... HAVING ...
SKYLINE OF [DISTINCT] d1 [MIN | MAX | DIFF], ..., dm [MIN | MAX | DIFF]
ORDER BY ...

Each dimension is marked MIN (lower is better), MAX (higher is better), or DIFF (compare only within equal values — a grouping dimension). For hotels in Paris:

SELECT * FROM Hotels WHERE city = 'Paris'
SKYLINE OF price MIN, distance MIN;

which translates directly into standard SQL as a doubly-nested “nothing dominates me” test:

SELECT * FROM Hotels h
WHERE h.city = 'Paris' AND NOT EXISTS (
  SELECT * FROM Hotels h1
  WHERE h1.city = h.city
    AND h1.distance <= h.distance AND h1.price <= h.price
    AND (h1.distance < h.distance OR h1.price < h.price));

Correct, and very slow — the subquery re-scans the table for every candidate row. Hence the algorithms.

03 · Algorithms

BNL and Sort-Filter-Skyline

Both maintain a window of currently-undominated points. The difference is whether the input was sorted first — and that difference is where exams set their traps.

The reason SFS can drop the removal step is a one-line invariant: if the input is sorted by a monotone function, a later tuple can never dominate an earlier one. A dominating tuple is nowhere-worse and strictly-better somewhere, so any monotone function scores it strictly better, so sorting puts it first.

04 · Extension

The k-skyband

The skyline is the set of tuples dominated by nobody. Relax “nobody” to “fewer than k” and you get the structure that contains every possible top-k answer.

The k-skyband is the set of tuples dominated by fewer than $k$ tuples. Two immediate consequences:

• The skyline is the 1-skyband — dominated by fewer than 1, i.e. by none.
• Every top-k result set is contained in the k-skyband. If a tuple is dominated by $k$ or more others, each of those scores strictly better under any monotone function, so it cannot reach rank $k$.

Worked on the January 2025 hotel dataset: the skyline is {a, h, b, e, i}, and the 2-skyband adds d (dominated only by a), c (only by e) and g (only by i). The single excluded tuple is f, dominated by five others.

05 · Theory

Skyline versus convex hull

Every skyline point wins under some monotone function. It does not follow that it wins under some linear one — and the gap between those two statements is where recent exams live.

Restrict the scoring functions to weighted sums, $f(x, y) = w_1 x + w_2 y$ with non-negative weights. Geometrically, minimising such a function means sweeping a family of parallel lines toward the data and seeing which point they touch first. Only points on the convex hull of the dataset can be touched first; a skyline point sitting behind the hull’s boundary is always beaten by one of the hull points bracketing it, for every choice of weights.

January 2025 asks precisely this: of the skyline {a, h, b, e, i}, which hotels can be top-1 under a linear function? Only a, e and i — those on the hull. And then it tightens the screw: restrict further to $w_1 > w_2$, and i drops out too, because

$w_1 (0.8) + w_2 (0.1) \ge w_1 (0.6) + w_2 (0.2) \iff 0.2\,w_1 \ge 0.1\,w_2$

which holds for every admissible weight pair — so e always beats i. The argument must hold for all weights, not for one sample choice.

June 2026 runs the same idea in reverse. The director wants LUMEN to win on (Potential, Feasibility) and no weighted sum works, because LUMEN (8, 8) lies behind the segment joining AURIX (10, 7) and VERDE (7, 9). The bonus question asks for any monotone function that does the job — and non-linear ones exist:

A third recent variation, January 2026, asks what happens to the skyline when columns are removed. The intuition — fewer dimensions make domination easier, so the skyline should shrink — is usually right and not guaranteed. Dropping SL and DH costs MG its place (PZ now dominates it), but dropping SG as well brings MG back, because on the two remaining columns MG and PZ tie exactly, and ties are not dominance. So $\mathrm{sky}(D'')\not\subseteq \mathrm{sky}(D')$ even though $D''$ came from $D'$ by removing a column: the skyline may grow, shrink or stay the same.

06 · Comparison

Ranking versus skyline

The two approaches to multi-criteria “best”, with their trade-offs stated plainly.

Skylines are effective when nothing is known about the user’s preferences, and they need no parameters. Their weaknesses are the mirror image: too many objects are returned for large, anti-correlated datasets — where being good on one attribute tends to mean being bad on another, so almost nothing is dominated; computation is essentially quadratic; and they are agnostic to known preferences, unable to use the information that price matters more than distance even when the user has said so.

Top-k is the opposite on every line: exact cardinality control and full expression of trade-offs, at the cost of demanding weights the user may be unable to supply, and hiding the shape of the alternative space behind a single number.

In practice they compose. The k-skyband is the bridge: compute it once with no parameters, and every top-k query the user later poses — whatever weights they choose — draws its answer from inside it.