Замыкание атрибутов и поиск ключей
Как по набору ФЗ механически найти все ключи отношения? Через замыкание атрибутов. Реализуем алгоритм на Python и запустим.
Замыкание набора атрибутов X⁺ — это множество всех атрибутов, которые функционально определяются набором X с учётом заданных ФЗ. Если X⁺ содержит все атрибуты отношения, то X — суперключ.
Зачем нужно замыкание
Аксиомы Армстронга позволяют выводить ФЗ, но вручную перебирать их следствия неудобно. Замыкание решает практические задачи механически: проверить, выполняется ли ФЗ X → Y (достаточно посмотреть, лежит ли Y в X⁺), найти все ключи отношения, проверить, является ли набор суперключом. По сути, замыкание — это рабочая лошадка всей теории нормализации.
Интуиция: «что я могу узнать, зная X»
Прежде чем смотреть на код, поймаем интуицию. Замыкание X⁺ отвечает на вопрос: «если мне известны значения атрибутов X для некоторого кортежа, значения каких ещё атрибутов я могу однозначно вычислить?». Зная номер заказа, я могу узнать дату и клиента (по ФЗ order_id → data, client_id); зная клиента, узнаю его имя и город; и так далее по цепочке. Замыкание — это всё, что «раскручивается» из X, если идти по ФЗ как по стрелкам. Если, раскрутив до упора, я получил все атрибуты отношения, значит, по X можно восстановить любой кортеж целиком — то есть X однозначно идентифицирует строку, X является суперключом. Эта картинка «раскручивания по стрелкам» — самый надёжный способ не запутаться: алгоритм ниже просто аккуратно её реализует, добавляя то, что становится известно, пока узнаётся что-то новое.
Алгоритм замыкания
Алгоритм прост и итеративен. Начинаем с самого набора X. Затем многократно проходим по всем ФЗ: если левая часть какой-то ФЗ уже целиком входит в наш текущий результат, добавляем в результат её правую часть. Повторяем, пока результат растёт. Когда за полный проход ничего не добавилось — замыкание найдено.
def closure(attrs, fds):
result = set(attrs)
changed = True
while changed:
changed = False
for left, right in fds:
if set(left) <= result and not set(right) <= result:
result |= set(right)
changed = True
return result
# ФЗ нашей "плоской" таблицы заказов
fds = [
(("order_id",), ("data", "client_id")),
(("client_id",), ("client_name", "client_city")),
(("product_id",), ("product_name", "cena")),
(("order_id", "product_id"), ("qty",)),
]
print("{order_id}+ =", sorted(closure(["order_id"], fds)))
print("{product_id}+ =", sorted(closure(["product_id"], fds)))
print("{order_id, product_id}+ =", sorted(closure(["order_id", "product_id"], fds)))Вывод:
{order_id}+ = ['client_city', 'client_id', 'client_name', 'data', 'order_id']
{product_id}+ = ['cena', 'product_id', 'product_name']
{order_id, product_id}+ = ['cena', 'client_city', 'client_id', 'client_name', 'data', 'order_id', 'product_id', 'product_name', 'qty']
Смотрите: замыкание {order_id, product_id} охватило все атрибуты отношения. Значит, эта пара — суперключ. А {order_id} и {product_id} поодиночке всё не определяют — суперключами они не являются.
Почему алгоритм всегда завершается и почему он верен
Стоит на секунду задуматься, почему этот простой цикл вообще даёт правильный ответ. Завершаемость: на каждой итерации мы либо добавляем хотя бы один новый атрибут, либо останавливаемся; атрибутов конечное число, значит, бесконечно добавлять нельзя — алгоритм гарантированно завершится. Корректность: каждый добавленный атрибут действительно следует из X по аксиомам Армстронга — мы добавляем правую часть ФЗ только когда её левая часть уже выведена (это транзитивность плюс пополнение). И наоборот, всё, что следует из X, мы рано или поздно добавим, потому что перебираем все ФЗ до тех пор, пока множество растёт. Таким образом, замыкание — это вычислительное воплощение аксиом Армстронга: то, что аксиомы описывают как правила вывода, алгоритм находит за конечное число шагов. Понимание этого превращает «магическую процедуру» в прозрачный и доказуемо верный инструмент.
Как искать все ключи системно
Полный перебор всех наборов атрибутов экспоненциален, но на практике поиск ключей сильно сокращается одним наблюдением. Атрибуты, которые не встречаются ни в одной правой части ФЗ, обязаны входить в каждый потенциальный ключ — ведь их нечем «вывести», их можно только задать напрямую. Поэтому начинают с таких «обязательных» атрибутов: вычисляют их замыкание; если оно уже покрывает всё отношение — это и есть единственный ключ. Если нет — по очереди добавляют недостающие атрибуты, пока замыкание не охватит всё, следя за минимальностью. Этот приём превращает пугающий перебор в управляемую процедуру. В нашем примере ни order_id, ни product_id не встречаются в правых частях — значит, оба обязаны быть в ключе; их замыкание покрывает всё отношение, и других ключей нет. Проверим это вычислением.
От замыкания к ключам
Чтобы найти потенциальный ключ: ищем минимальный набор, чьё замыкание равно всем атрибутам. Проверим формально, что наша пара — ключ, и что её части ключами не являются.
def closure(attrs, fds):
result = set(attrs)
changed = True
while changed:
changed = False
for left, right in fds:
if set(left) <= result and not set(right) <= result:
result |= set(right)
changed = True
return result
fds = [
(("order_id",), ("data", "client_id")),
(("client_id",), ("client_name", "client_city")),
(("product_id",), ("product_name", "cena")),
(("order_id", "product_id"), ("qty",)),
]
all_attrs = {"order_id", "product_id", "data", "client_id",
"client_name", "client_city", "product_name", "cena", "qty"}
cand = ["order_id", "product_id"]
print("Замыкание пары = все атрибуты?", closure(cand, fds) == all_attrs)
print("order_id один — ключ?", closure(["order_id"], fds) == all_attrs)
print("product_id один — ключ?", closure(["product_id"], fds) == all_attrs)Вывод:
Замыкание пары = все атрибуты? True order_id один — ключ? False product_id один — ключ? False
Вывод однозначен: единственный потенциальный ключ — это пара {order_id, product_id}, и она минимальна (ни одну часть убрать нельзя). Значит, первичные (prime) атрибуты — order_id и product_id; все остальные непервичные. Это понадобится буквально в следующем уроке для проверки нормальных форм.
Где замыкание применяется на практике
Замыкание — не абстрактное упражнение, а рабочий инструмент с тремя главными применениями. Первое — проверка, выполняется ли ФЗ X → Y в данной схеме: вычисляем X⁺ и смотрим, входит ли Y; если да — зависимость следует из набора, если нет — не следует. Второе — поиск всех ключей: перебираем наборы атрибутов и проверяем, чьё замыкание покрывает всё отношение (с учётом минимальности). Третье — проверка нормальных форм: чтобы понять, в 3NF или BCNF находится отношение, для каждой ФЗ нужно знать, является ли её левая часть суперключом, — а это вопрос «равно ли её замыкание всем атрибутам». Таким образом, один скромный алгоритм лежит в основе почти всего инструментария теории проектирования. Освоив его, вы получаете ключ (в прямом и переносном смысле) к нормализации, которой посвящены следующие два урока.
Проверка ФЗ на конкретных данных
Замыкание работает с ФЗ как с правилами. А как проверить, не нарушает ли текущий набор данных предполагаемую ФЗ? Сгруппируем кортежи по левой части: если у одинаковых X встречаются разные Y — ФЗ нарушена.
def holds(rows, X, Y):
seen = {}
for r in rows:
kx = tuple(r[a] for a in X)
ky = tuple(r[a] for a in Y)
if kx in seen and seen[kx] != ky:
return False # один X => два разных Y: нарушение
seen[kx] = ky
return True
rows = [
{"index": "101000", "city": "Москва", "street": "Тверская"},
{"index": "101000", "city": "Москва", "street": "Никольская"},
{"index": "190000", "city": "Санкт-Петербург", "street": "Невский"},
]
print("index => city :", holds(rows, ["index"], ["city"]))
print("index => street:", holds(rows, ["index"], ["street"]))Вывод:
index => city : True index => street: False
index → city выполняется (у индекса 101000 всегда «Москва»), а index → street — нет: у одного индекса две разные улицы. Так данные можно использовать, чтобы опровергнуть предполагаемую ФЗ (но не доказать её — отсутствие нарушений ещё не гарантия правила).
Типичные ошибки
- Считают набор ключом, не проверив минимальность. Замыкание равно всем атрибутам — это суперключ; ключ требует ещё и минимальности.
- Останавливают алгоритм рано. Замыкание нужно расширять до тех пор, пока за проход что-то добавляется; один проход часто недостаточен из-за транзитивности.
- Доказывают ФЗ данными. Данные могут опровергнуть ФЗ (нашли нарушение), но не доказать её — правило задаётся смыслом.
Итог
- Замыкание X⁺ — все атрибуты, определяемые набором X по заданным ФЗ.
- X — суперключ тогда и только тогда, когда X⁺ равно множеству всех атрибутов; ключ — ещё и минимален.
- Алгоритм итеративно добавляет правые части ФЗ, левые части которых уже накоплены.
- На конкретных данных ФЗ можно опровергнуть (найдя один X с разными Y), но не доказать.
