61. Chase: символна проверка за възстановяване без загуба
Специализирана тема С6 · Подготовка по програма № 19, СУ / ФМИ, 2026/2027 г. Авторски урок, пример и задача; не са официални отговори на СУ.
Цел: Да проследиш малка таблица от символи и да разбереш защо един изцяло основен ред доказва липса на загуба.
Около 15–20 минути с четенето и задачата. При нужда раздели четенето и решаването на две кратки стъпки.
Основни понятия
Chase е алгоритъм за проверка, не команда за промяна на реалните данни. Правим символна таблица (tableau): по един ред за всяка компонента и по една колона за всеки атрибут на първоначалната схема. В колоните, които принадлежат на компонента, поставяме основните символи a, b, c…; в липсващите — различни помощни символи с индекс.
Ако два символни реда съвпадат по лявата страна на дадена FD, уеднаквяваме символите им отдясно. Основният символ има предимство пред помощния. Замяната важи за всички появи на съответния символ. Повтаряме до успех или докато няма повече промени.
Ако се появи ред само от основни символи, всяка комбинация, която JOIN може да създаде, вече е принудена да е оригинален ред: декомпозицията е без загуба. Ако алгоритъмът стигне до неподвижно състояние без такъв ред, гаранцията липсва. Не бива да спираме след произволна една стъпка и да обявяваме неуспех.
Практичен пример
За R(A, B, C), F = {A → B} и компоненти AB, AC започваме с редовете (a, b, c₁) и (a, b₂, c). Те имат еднакво A = a, следователно b₂ се заменя с b. Вторият ред става (a, b, c): успех. Помощното c₁ в първия ред не пречи — достатъчен е един изцяло основен ред.
Точно четене
СУ 11: Garcia-Molina, Ullman и Widom, Database Systems: The Complete Book, второ издание, §3.4.2–3.4.3, печатни 96–100 / PDF 133–137. Чети посочените раздели в тези страници; съседните упражнения са по желание. Примерите, условието, решенията и схемите тук са авторски.
Учебникът и официалната библиография.
Самостоятелна задача — около 5–10 минути
Условие
Схемата е R(A, B, C, D), F = {B → C, C → D}, само с тези зависимости и следствията им. Проверяваме декомпозицията на AB, BC и CD. Началната символна таблица е:
| Компонента | A | B | C | D |
|---|---|---|---|---|
| AB | a | b | c₁ | d₁ |
| BC | a₂ | b | c | d₂ |
| CD | a₃ | b₃ | c | d |
a, b, c, d са основни символи; всички индексирани символи са отделни неизвестни стойности, а не NULL. При равенство по лявата страна на FD уеднаквяваме дясната, като запазваме основния символ. Първо приложи B → C към редовете AB и BC; после приложи C → D към редовете с общо c.
- Кой символ се заменя при първото приложение B → C?
- След това кои символи се заменят, за да се изпълни C → D за трите реда?
- Кой ред става изцяло от основни символи и какво означава това?
- Трябва ли всички редове да станат (a, b, c, d), за да е успешна проверката?
Изпрати отговорите по номера в разговора, после отвори картите за преговор.
Отговори за преговор — разгъвай поотделно
Авторски примерни отговори, затворени по подразбиране. Tab до заглавието, после Enter или Space.
Покажи отговор 1
c₁ се заменя с c, защото AB и BC имат еднакво B = b. Първият ред става (a, b, c, d₁).
Покажи отговор 2
След първата стъпка и трите реда имат C = c. Затова d₁ и d₂ се заменят с основното d. Заменяме последователно всяко тяхно появяване.
Покажи отговор 3
Редът AB става (a, b, c, d). Следователно декомпозицията е без загуба спрямо дадените зависимости, за всяко допустимо състояние.
Покажи отговор 4
Не. Достатъчен е един такъв ред. Останалите могат да съдържат a₂, a₃, b₃; това не отменя доказателството.