Этап 1
80 мин: 10 минут (00:00–00:10) | 60 мин: 7 минут (00:00–00:07)
Организационный момент, проблемная мотивация и постановка цели
Преподаватель входит в аудиторию, приветствует обучающихся, отмечает присутствующих в журнале, включает проектор с титульным слайдом презентации «Нормализация БД: функциональные зависимости».
Преподаватель:
Здравствуйте, коллеги! Садитесь. На прошлом занятии мы завершили проектирование концептуальной схемы: объединяли локальные представления отделов, разрешали конфликты синонимов и омонимов. Теперь перед нами стоит следующий фундаментальный вопрос: как перенести полученные сущности в таблицы реляционной базы данных так, чтобы при промышленной эксплуатации система не захлебнулась в ошибках, избыточности и противоречиях?
Взгляните на экран (переключает на Слайд 2). Перед вами пример типичной ошибки начинающего разработчика — «универсальная» широкая таблица «Сотрудники и Проекты»:
Сотрудники_Проекты(EmpID, ФИО, DeptID, НазваниеОтдела, ТелефонОтдела, ProjID, НазваниеПроекта, Роль, Зарплата)
Преподаватель:
Казалось бы: все данные под рукой, никаких операторов JOIN писать не нужно, один запрос выбирает всё! Но давайте представим, что мы запустили эту систему в реальной компании. Что произойдет, если в Отделе разработки сменится рабочий номер телефона?
Студент:
Придется обновить номер телефона во всех строках, где указан этот отдел. Если в отделе 200 сотрудников — то в двухстах записях сразу!
Преподаватель:
Именно! Это называется аномалией обновления (Update Anomaly). Если сервер оборвет соединение на сотой строке, у нас в половине базы будет один телефон, а во второй — другой. А теперь второй вопрос: мы создали новый перспективный «Отдел искусственного интеллекта», но еще никого туда не наняли. Сможем ли мы вставить запись об этом отделе в таблицу, если первичный ключ включает EmpID?
Студент:
Нет, потому что EmpID не может быть NULL в первичном ключе! Придется либо придумывать фиктивного сотрудника, либо мы вообще не сохраним отдел.
Преподаватель:
Блестяще! Это аномалия вставки (Insertion Anomaly). А если уволится последний сотрудник из удаленного филиала, то вместе с удалением его строки мы потеряем адрес и телефон филиала — это аномалия удаления (Deletion Anomaly).
Чтобы навсегда избавить базы данных от этих пороков, Эдгар Кодд создал теорию нормализации. А фундаментом нормализации является строгий математический аппарат — функциональные зависимости. Сегодня мы научимся строго формулировать зависимости, выводить новые факты с помощью аксиом Армстронга, вычислять замыкания атрибутов и находить все истинные ключи отношения.
Этап 2
80 мин: 25 минут (00:10–00:35) | 60 мин: 20 минут (00:07–00:27)
Сообщение новых теоретических знаний: аппарат ФЗ и аксиоматика Армстронга
Преподаватель переключает презентацию на Слайд 3 и записывает формальное определение ФЗ на доске.
Преподаватель:
Запишем строгое определение. Пусть R(U) — схема отношения. Говорят, что множество атрибутов X функционально определяет множество Y (записывается X → Y), если во всех допустимых состояниях отношения для любых двух строк t₁ и t₂ равенство их значений в столбцах X гарантирует точное равенство значений в столбцах Y:
X → Y ⟺ ∀ t₁, t₂ ∈ r(R): ( t₁[X] = t₂[X] ⟹ t₁[Y] = t₂[Y] )
Преподаватель:
Левую часть X мы называем детерминантом, а правую часть Y — зависимой частью.
Запомните важнейшее правило: функциональная зависимость — это закон предметной области, а не сиюминутное совпадение в выборке! Если прямо сейчас в аудитории сидит 15 человек и у всех разные фамилии и разные оценки, мы не имеем права сказать: «Оценка однозначно определяет студента». Завтра придет второй студент с оценкой «отлично», и мнимая зависимость лопнет. Зависимость должна выполняться ВСЕГДА, при любых будущих данных.
Преподаватель переходит к Слайду 4 («Классификация ФЗ»).
Преподаватель:
Зависимости бывают разными:
- Тривиальные: когда то, что справа, уже содержится слева. Например,
{Паспорт, ФИО} → {ФИО}. Зная набор, мы автоматически знаем его часть. Это тавтология.
- Полные и частичные: если у нас составной детерминант, например
{СтудентID, ПредметID} → Оценка — это полная зависимость, так как ни по одному СтудентID, ни по одному ПредметID оценку не узнать. Но если в эту же таблицу поместить {СтудентID, ПредметID} → НомерГруппы, то номер группы зависит только от СтудентID. Это частичная зависимость, и именно она порождает дублирование и нарушает Вторую нормальную форму!
- Транзитивные: цепочка вида
Сотрудник → Отдел, а Отдел → Телефон. Отсюда косвенно следует Сотрудник → Телефон. Транзитивные зависимости нарушают Третью нормальную форму.
Преподаватель переключает на Слайд 5 и Слайд 6 («Аксиомы Армстронга»).
Преподаватель:
В 1974 году математик Уильям Армстронг доказал поразительную вещь: чтобы из известных зависимостей вывести ВСЕ остальные истинные следствия, достаточно всего ТРЕХ базовых аксиом:
- Рефлексивность: если
Y ⊆ X, то X → Y.
- Пополнение: если
X → Y, то приписав любые поля Z к обеим сторонам, мы получаем верную зависимость: XZ → YZ.
- Транзитивность: если
X → Y и Y → Z, то X → Z.
А на практике мы пользуемся удобными следствиями — правилом
объединения:
X → Y и
X → Z дают
X → YZ, и правилом
декомпозиции:
X → YZ распадается на
X → Y и
X → Z.
Остерегайтесь роковой ошибки! Можно ли расщеплять левую часть? То есть верно ли, что если
AB → C, то
A → C?
Студент:
Нет, конечно! Например, логин и пароль вместе открывают доступ к аккаунту: {Логин, Пароль} → Доступ. Но один логин без пароля доступ не дает!
Преподаватель:
Великолепный контрпример! Расщеплять можно ТОЛЬКО правую часть зависимости. Запомните это навсегда.
Этап 3
80 мин: 20 минут (00:35–00:55) | 60 мин: 15 минут (00:27–00:42)
Алгоритмический практикум: замыкание X+, поиск ключей (L-R-B-N) и Minimal Cover
Преподаватель переходит к Слайдам 7–10 и берет мел/маркер для работы у доски.
Преподаватель:
Теперь перейдем к главному вычислительному инструменту проектировщика — замыканию множества атрибутов X⁺. Замыкание X⁺ — это множество абсолютно всех атрибутов, которые можно однозначно вычислить, зная исходные поля X.
Разберем задачу. Дана схема R(A, B, C, D, E) со следующим набором зависимостей:
F = { A → BC, CD → E, B → D, E → A }
Преподаватель:
Найдем замыкание атрибута B, то есть {B}⁺. Чертим трассировочную таблицу:
Шаг 0: начинаем с самого {B}.
Шаг 1: смотрим на правила. Видим зависимость B → D. Левая часть {B} содержится в нашем наборе? Да! Добавляем правую часть: получаем {B, D}.
Шаг 2: проверяем остальные ФЗ. Чтобы сработало CD → E, нужны и C, и D. У нас есть D, но нет C. Правило A → BC требует A — у нас его нет. E → A требует E — его нет.
Новых атрибутов добавить нельзя. Алгоритм остановился!
Итог: {B}⁺ = {B, D}.
Преподаватель:
А теперь найдем все
потенциальные ключи этого отношения. Что такое потенциальный ключ? Это минимальный набор атрибутов, чье замыкание дает ВСЕ атрибуты отношения
U = {A, B, C, D, E}.
Чтобы не перебирать вслепую 32 комбинации подмножеств, воспользуемся инженерной классификацией
L-R-B-N:
- Смотрим, какие атрибуты стоят ТОЛЬКО слева (класс L): ни одного! Все атрибуты встречаются справа: A (в E→A), B и C (в A→BC), D (в B→D), E (в CD→E).
- Значит, все атрибуты входят в класс B (Both — и слева, и справа).
Давайте проверим одноэлементные множества:
- Проверим
{A}⁺: A → BC дает {A, B, C}; далее B → D дает {A, B, C, D}; далее CD → E дает {A, B, C, D, E} = U! Значит, {A} — кандидатный ключ!
- Проверим
{E}⁺: E → A сразу дает A, а замыкание A покрывает всё! Значит, {E} — тоже кандидатный ключ!
- А как получить ключ из пар? Мы знаем, что E получается из
CD. Проверим {C, D}⁺: по правилу CD → E получаем E, затем A, затем B! Значит, {C, D} — кандидатный ключ!
- А D можно получить из B? Да,
B → D! Заменим D на B в паре: проверим {B, C}⁺: B → D дает D, пара CD дает E, E дает A! Значит, {B, C} — четвертый кандидатный ключ!
Посмотрите, какая красивая математическая структура: у отношения целых четыре равноправных ключа:
{A},
{E},
{C, D},
{B, C}! Любой из них проектировщик может назначить первичным ключом (PK).
Преподаватель переключает на Слайды 11–13 («Минимальное покрытие»).
Преподаватель:
И последнее теоретическое орудие — Minimal Cover (минимальное покрытие). В реальных проектах аналитики приносят десятки требований, в которых половина правил дублирует друг друга. Минимальное покрытие очищает схему за три шага:
1. Расщепить правые части до одного поля (декомпозиция).
2. Удалить лишние поля из составных детерминантов слева.
3. Удалить целиком те зависимости, которые и так выводятся из оставшихся.
Этап 4
80 мин: 15 минут (00:55–01:10) | 60 мин: 12 минут (00:42–00:54)
Самостоятельная работа в интерактивном рабочем листе zanyatie.html
Преподаватель выводит на экран Слайд 14 с критериями оценивания и просит студентов открыть файл zanyatie.html в браузере.
Преподаватель:
Коллеги, открываем на компьютерах интерактивный рабочий лист
zanyatie.html. Вверху введите свою фамилию, имя и учебную группу. Обратите внимание: все ваши ответы автоматически кэшируются в локальной памяти браузера (localStorage), так что случайное закрытие вкладки ничего не сотрет.
Распределяемся по вариантам:
- Вариант 1 (1-я парта каждого ряда): Формальная схема
R(A, B, C, D, E) — вычисление {B}⁺, нахождение всех потенциальных ключей и минимизация покрытия.
- Вариант 2 (2-я парта): Прикладная база «Проекты и сотрудники» — определение составного ключа и доказательство наличия частичной зависимости, нарушающей 2НФ.
- Вариант 3 (3-я парта): Система «Логистика» — нахождение ключа накладных и выявление транзитивной зависимости адреса клиента, нарушающей 3НФ.
- Вариант 4 (4-я парта): Схема
R(X, Y, Z, W, V) — строгое доказательство X → W по аксиомам Армстронга и нахождение Minimal Cover с устранением постороннего атрибута.
Время на самостоятельное решение — 15 минут. Я подхожу и отвечаю на индивидуальные вопросы.
Студенты работают в веб-формах, проводят пошаговые вычисления замыканий, обосновывают ключи. Преподаватель обходит аудиторию, контролирует ход решения, предотвращает ошибки в расчете замыкания.
Этап 5
80 мин: 10 минут (01:10–01:20) | 60 мин: 6 минут (00:54–01:00)
Разбор ошибок, рефлексия, интернет-мем Bobby Tables и домашнее задание
Преподаватель привлекает внимание аудитории и переключает проектор на Слайд 15 с комиксом xkcd #327.
Преподаватель:
Время вышло. Нажмите кнопку «Сохранить ответы» в своих листах. Перед тем как подвести итоги по критериальной рубрике, взгляните на экран (Слайд 15). Это знаменитый комикс Рэндалла Манро про «Маленького Бобби Таблицу» (Little Bobby Tables).
Мама назвала сына именем Robert'); DROP TABLE Students;--, и когда школьная программа попыталась записать его в базу без должной обработки, таблица студентов была уничтожена. Почему этот мем мы смотрим на занятии по функциональным зависимостям?
Студент:
Потому что когда проектировщики бросают базу ненормализованной, в одной огромной таблице хранятся и студенты, и их оценки, и факультеты. И любая ошибка уничтожает вообще все данные сразу, потому что ключи и связи не были изолированы!
Преподаватель:
В точку! Денормализованная база — это пороховая бочка. Четкое выделение функциональных зависимостей и ключей позволяет разбить схему на независимые, надежно изолированные сущности. Если в нормализованной схеме повредится запись об одном студенте, справочники факультетов и предметов останутся невредимыми.
Оценивание: Ваши работы оцениваются по 4-балльной шкале:
2 балла за безошибочное вычисление замыкания, 1 балл за нахождение всех ключей отношения и 1 балл за минимизацию покрытия и аналитические ответы.
Домашнее задание: В папке материалов находится файл domashnee_zadanie.html. Это резервное дистанционное задание. Обратите внимание на плашку: вы выполняете его только в том случае, если вам назначена дистанционная отработка или требуется пересдача. Срок сдачи — до начала следующей пары.
Спасибо за отличную математическую работу! Урок окончен.