60. Декомпозиция без загуба и излишни кортежи
Специализирана тема С6 · Подготовка по програма № 19, СУ / ФМИ, 2026/2027 г. Авторски урок, пример и задача; не са официални отговори на СУ.
Цел: Да провериш дали JOIN възстановява точно оригинала, а не само дали връща всички стари редове.
Около 15–20 минути с четенето и задачата. При нужда раздели четенето и решаването на две кратки стъпки.
Основни понятия
Декомпозиция без загуба означава: за всяко допустимо състояние r естественият JOIN на неговите проекции е точно r. Първоначалните редове винаги могат да се получат обратно от собствените им проекции. Опасността е да се появят и излишни кортежи, които не са били първоначални факти.
При двукомпонентна декомпозиция R₁, R₂ и ограничения само от функционални зависимости критерият е: общите атрибути R₁ ∩ R₂ трябва да определят всички атрибути на поне една от двете компоненти. Запис: (R₁ ∩ R₂) → R₁ или (R₁ ∩ R₂) → R₂ следва от F. Това е гаранция за всички допустими екземпляри, не проверка само на текуща извадка.
„Без загуба“ не значи „не изтрихме нито една стойност“. Може да запазим всяка стойност, но да изгубим информация кои стойности са били заедно.
Практичен пример
R(Човек, Град, Хоби) съдържа (Ива, София, шах) и (Борис, София, плуване), без зависимости Град → Човек или Град → Хоби. Проекциите (Човек, Град) и (Град, Хоби) се съединяват в четири реда. Появяват се непосочени факти: Ива–плуване и Борис–шах. Общият град не пази първоначалните двойки човек–хоби.
Точно четене
СУ 11: Garcia-Molina, Ullman и Widom, Database Systems: The Complete Book, второ издание, §3.4.1, печатни 94–96 / PDF 131–133. Чети посочените раздели в тези страници; съседните упражнения са по желание. Примерите, условието, решенията и схемите тук са авторски.
Учебникът и официалната библиография.
Самостоятелна задача — около 5–10 минути
Условие
Дадена е R(Курсист, Група, Избор), множество без NULL, без допълнителни функционални зависимости. Всички редове са:
| Курсист | Група | Избор |
|---|---|---|
| У1 | Г1 | SQL |
| У2 | Г1 | ER |
Декомпозираме чрез проекция на R₁(Курсист, Група) и R₂(Група, Избор). JOIN свързва по Група. За последния въпрос разгледай хипотетична нова версия на правилата, изискваща Група → Избор; не приемай автоматично, че дадените редове я удовлетворяват.
- Запиши двете проекции.
- Кои четири реда получаваме след JOIN и кои от тях са излишни?
- Достатъчно ли е, че JOIN съдържа и двата оригинални реда, за да кажем „без загуба“?
- Ако изискваме Група → Избор, декомпозицията гарантирано без загуба ли е за допустимите по новото правило данни? Допустими ли са дадените два реда?
Изпрати отговорите по номера в разговора, после отвори картите за преговор.
Отговори за преговор — разгъвай поотделно
Авторски примерни отговори, затворени по подразбиране. Tab до заглавието, после Enter или Space.
Покажи отговор 1
R₁ = {(У1, Г1), (У2, Г1)}; R₂ = {(Г1, SQL), (Г1, ER)}.
Покажи отговор 2
Резултатът е {(У1, Г1, SQL), (У1, Г1, ER), (У2, Г1, SQL), (У2, Г1, ER)}. Излишни са (У1, Г1, ER) и (У2, Г1, SQL).
Покажи отговор 3
Не. Нужно е равенство, не само включване на оригиналните редове. Два нови кортежа означават, че информацията за първоначалното съчетаване е изгубена.
Покажи отговор 4
Да, общият атрибут Група ще определя цялата R₂, така че имаме гаранция без загуба. Но дадените два реда не са допустими по новото правило: една и съща Г1 има SQL и ER. Не можем да ги използваме като контрапример срещу гаранцията.