Замыкание атрибутов и поиск ключей

В прошлом уроке мы выводили зависимости по аксиомам Армстронга, шаг за шагом, как в школьной задаче на доказательство. Это полезно для понимания, но медленно. В этом уроке простой алгоритм, который отвечает на два практических вопроса: «что я узнаю, если знаю эти колонки?» и «какие у таблицы ключи?».

Цепочка догадок

Представь детектива. Он знает номер машины. По номеру находит владельца. По владельцу адрес. По адресу соседей. Каждый новый факт открывает следующие, пока цепочка не остановится. Всё, что детектив в итоге узнал, начав с номера машины, и есть замыкание.

Замыкание набора колонок X, его пишут X⁺, это все колонки, которые однозначно определяются по X через имеющиеся зависимости.

Данные

Берём таблицу из прошлого урока и добавляем кабинет: у каждого преподавателя свой кабинет.

enrollments_flat(student_id, student_name, course_id, course_title, teacher, room, grade)

F1: student_id            → student_name
F2: course_id             → course_title, teacher
F3: teacher               → room
F4: student_id, course_id → grade

Алгоритм

Алгоритм повторяет детектива:

1. Начни с множества, равного X.
2. Пройди по всем зависимостям. Если левая часть зависимости целиком лежит в множестве, добавь в множество её правую часть.
3. Если на шаге 2 добавилось хоть что-то, повтори шаг 2.
4. Когда проход ничего не добавил, множество и есть X⁺.

Посчитаем замыкание course_id:

старт:          { course_id }
F2 подходит:    { course_id, course_title, teacher }
F3 подходит:    { course_id, course_title, teacher, room }
F1, F4 нет:     student_id в множестве отсутствует
повторный проход ничего не добавил, стоп

{course_id}⁺ = { course_id, course_title, teacher, room }

F3 сработал, только когда F2 уже добавил teacher. Поэтому алгоритм ходит по зависимостям кругами, пока множество растёт: одна догадка открывает следующую.