91. Сортиране: от релация към подреден списък

Специализирана тема С10 · Подготовка по програма № 19, СУ / ФМИ, 2026/2027 г. Авторски урок, пример и задача; не са официални отговори на СУ.

Цел: да задаваш приоритет на колоните за сортиране и да различаваш реда на представяне от релацията.

Около 10–15 минути с четенето и задачата.

Основни понятия

Релацията като множество или мултимножество няма присъщ ред. Операторът τ (тау) връща подреден списък от кортежи. Първо сравнява първия посочен атрибут; при равенство — втория, и т.н. Тук записваме ↑ за възходящо и ↓ за низходящо сортиране; това са пояснения за посока, не ER или FD стрелки.

Ако два кортежа са равни по всички посочени критерии, относителният им ред не е определен. За еднозначен ред можеш да добавиш уникален атрибут като последен критерий. Сортирането не премахва повторения. След съединяване не приемаме автоматично, че редът се е запазил: обикновено сортираме окончателния резултат.

Пример стъпка по стъпка

РЕЗУЛТАТИ — пример
НомерТочки
У28
У18
У310

τТочки↓, Номер↑(РЕЗУЛТАТИ)

Получаваме списъка [(У3, 10), (У1, 8), (У2, 8)]. Първо са по-високите точки, а двамата с 8 се подреждат по номерата. Това не добавя колона и не променя точките.

91. Сортиране: от релация към подреден списък — разгледан пример
91. Сортиране: от релация към подреден списък — разгледан пример. Схема на данни и операции, не ER диаграма. Отвори в пълен размер.

Точно четене

СУ 11: Garcia-Molina, Ullman и Widom, Database Systems: The Complete Book, второ издание, §5.2.6, печатни 219 / PDF 256. Чети посочените подраздели, а не всички съседни раздели на страниците. Примерът, чертежите и задачата тук са авторски.

Учебникът и официалната библиография · Учебен речник

Кратка задача — около 5 минути

Условие

Дадена е релацията РЕЗУЛТАТИ(Номер, Точки) с трите кортежа по-долу, без NULL. Номер е уникален. Числата се сравняват числово, а номерата — в ред У1 < У2 < У3. τТочки↓, Номер↑ означава първо низходящи точки, после възходящ номер при равенство. Квадратни скоби ще означават списък, в който редът има значение.

РЕЗУЛТАТИ — всички кортежи
НомерТочки
У280
У180
У390
91. Сортиране: от релация към подреден списък — изходни данни на задачата
91. Сортиране: от релация към подреден списък — изходни данни на задачата. Схема на данни и операции, не ER диаграма. Отвори в пълен размер.
  1. Запиши резултатния списък след зададеното сортиране.
  2. Само τТочки↓ определя ли еднозначно реда на У1 и У2?
  3. Сортирането променя ли схемата или стойностите на точките?
  4. Ако след сортирането съединим резултата с друга релация, можем ли без ново сортиране да обещаем същия ред?

Изпрати отговорите по номера в разговора, после отвори картите за преговор.

Отговори за преговор — разгъвай поотделно

Авторски примерни отговори, затворени по подразбиране. Tab до заглавието, после Enter или Space.

Покажи отговор 1

[(У3, 90), (У1, 80), (У2, 80)].

Покажи отговор 2

Не. У1 и У2 имат еднакви точки. Вторият критерий определя кое от тях е първо.

Покажи отговор 3

Не. Схемата остава (Номер, Точки), стойностите са същите; получаваме подредено представяне като списък.

Покажи отговор 4

Не. Съединяването не дава такава гаранция. Ако крайният ред е важен, задаваме сортиране на окончателния резултат.

91. Сортиране: от релация към подреден списък — решение за преговор
91. Сортиране: от релация към подреден списък — решение за преговор. Схема на данни и операции, не ER диаграма. Отвори в пълен размер.