5NF: join dependencies и project-join форма

4NF убирает избыточность от двух независимых многозначных фактов — там таблица корректно раскладывается на две проекции. Но бывает более тонкий случай: таблицу нельзя без потерь разбить на две части, а вот на три — можно. Этот случай описывает пятая нормальная форма (5NF), она же project-join normal form (PJ/NF).

5NF — самая высокая из «классических» нормальных форм и самый редкий на практике дефект. Но разобрать её стоит: она доводит до конца главную идею всей нормализации — «каждый факт хранится один раз» — и опирается на понятие join dependency, обобщающее всё, что мы видели раньше.

Join dependency: обобщение

Вспомним лестницу декомпозиций. FD позволяет вынести атрибуты в отдельную таблицу. MVD описывает разбиение таблицы на две проекции без потерь. Join dependency (JD), зависимость соединения, — следующая ступень обобщения: она описывает разбиение таблицы на любое число проекций.

Join dependency записывается как *(R1, R2, ..., Rn) и выполняется в таблице R, если R равна соединению своих проекций на наборы атрибутов R1, R2, ..., Rn. То есть: спроецировали R на каждый из наборов, соединили все проекции обратно — и получили ровно R, без единой лишней строки.

Иерархия обобщений выстраивается так:

MVD — это в точности join dependency на два компонента. JD на три и более компонента — это уже то новое, что не покрывается ни FD, ни MVD, ни, следовательно, 4NF.

Когда разбиение на две части не работает, а на три — да

Возьмём классический пример. Поставщики поставляют товары проектам. Таблица фиксирует: какой поставщик какой товар поставляет какому проекту.

SUPPLY(supplier, product, project)

Введём важное бизнес-правило, которое и создаёт join dependency. Правило-«цикл»:

Если поставщик S поставляет товар P (хоть кому-то), И товар P нужен проекту J, И поставщик S уже работает с проектом J (поставляет туда хоть что-то), ТО S поставляет P в J.

Это не выдумка — такое правило бывает реальным: «если поставщик в принципе возит товар, товар нужен проекту, а поставщик с проектом уже связан договором, то эта поставка обязана состояться». Из этого правила следует нетривиальная join dependency *(SP, PJ, SJ) — на три проекции:

SP(supplier, product)    SE-проекция: кто что поставляет
PJ(product, project)     PE-проекция: что нужно проекту
SJ(supplier, project)    SO-проекция: кто с каким проектом работает

Покажем на данных, что разбиение именно на три, и на две — не работает. Пусть таблица содержит:

supplier | product | project
---------+---------+--------
S1       | P1      | J2
S1       | P2      | J1
S2       | P1      | J1

Проекции:

SP            PJ            SJ
S1 | P1       P1 | J2       S1 | J2
S1 | P2       P2 | J1       S1 | J1
S2 | P1       P1 | J1       S2 | J1

Соединим сначала SP и PJ по product:

SP JOIN PJ (по product)
supplier | product | project
---------+---------+--------
S1       | P1      | J2
S1       | P1      | J1     <- этой строки в исходной таблице НЕТ!
S1       | P2      | J1
S2       | P1      | J2     <- и этой НЕТ!
S2       | P1      | J1

Соединение двух проекций породило две лишние строки — (S1,P1,J1) и (S2,P1,J2). Разбиение на две части SP и PJ оказалось lossy (с потерями — точнее, с появлением фантомных строк). Но если теперь соединить результат с третьей проекцией SJ по паре {supplier, project}, фантомные строки отсеются: пары (S1,J1)… (S1,J1) в SJ есть — значит (S1,P1,J1) проходит? Проверим аккуратно по правилу. Строка (S1,P1,J1) фантомная потому, что в исходных данных её не было; но бизнес-правило-цикл как раз говорит, что она должна быть, раз (S1,P1), (P1,J1), (S1,J1) все присутствуют. Значит исходная таблица из примера правилу не удовлетворяла — а в таблице, где правило соблюдено, соединение трёх проекций даст ровно её.

Суть в этом: при действующем правиле-цикле таблица SUPPLY равна соединению трёх проекций *(SP, PJ, SJ), но не равна соединению никаких двух из них. Это нетривиальная join dependency на три компонента.

Избыточность и определение 5NF

Чем плоха таблица SUPPLY в исходном виде? При действующем правиле-цикле часть строк выводима из остальных. Если в таблице есть (S1,P1,J2), (S1,P2,J1), (S2,P1,J1) и ещё какие-то строки, замыкающие цикл, то строка вроде (S1,P1,J1) обязана присутствовать — её существование не несёт новой информации, оно вынуждено. Это и есть избыточность: факт хранится, хотя полностью предопределён другими фактами. Отсюда — аномалии: добавив одну строку, можно нарушить правило-цикл, и придётся доставлять выводимые строки вручную.

Таблица находится в 5NF (PJ/NF), если она в 4NF и каждая нетривиальная join dependency в ней подразумевается candidate keys — то есть любое разбиение таблицы на проекции без потерь возможно только по наборам атрибутов, каждый из которых содержит candidate key.

Проще говоря: таблица в 5NF, если её нельзя разбить на меньшие проекции без потерь иначе как тривиальным способом (по superkey). Если же существует нетривиальная JD — таблицу надо декомпозировать по ней.

Тривиальная JD — та, где один из компонентов совпадает со всей таблицей, либо разбиение следует из candidate keys. Тривиальная JD избыточности не создаёт и декомпозиции не требует.

Декомпозиция SUPPLY в 5NF — это и есть разбиение по найденной JD на три таблицы:

SP(supplier, product)     PK = {supplier, product}
PJ(product, project)      PK = {product, project}
SJ(supplier, project)     PK = {supplier, project}

Теперь каждый факт элементарен: «S1 возит P1», «P1 нужен J2», «S1 работает с J2» — и хранится один раз. Выводимые строки больше не хранятся вовсе: они вычисляются трёхсторонним соединением, когда нужны. Все три таблицы в 5NF.

5NF и здравый смысл декомпозиции

Важная оговорка. Разложить таблицу на три проекции технически можно почти всегда — но это будет с потерями, если соответствующая JD на самом деле не выполняется. 5NF-декомпозиция корректна, только когда JD реально действует — то есть когда в предметной области реально есть то самое правило-цикл.

Если же правила-цикла нет, то SUPPLY не распадается на три проекции без потерь, она уже в 5NF, и дробить её на SP, PJ, SJ нельзя — соединение даст фантомные строки, которых в реальности не существует. Это та же логика, что и с MVD в прошлом уроке: декомпозиция привязана к зависимости, а зависимость берётся из бизнес-правил, а не из текущего снимка данных.

Есть и приятный теоретический итог. Существует результат: если у таблицы все candidate keys одноатрибутны (состоят из единственного атрибута), то таблица в 3NF автоматически находится и в 5NF. Это объясняет, почему на практике до 5NF доходит редко: проблемы 4NF и 5NF появляются в основном в таблицах из одних только составных ключей, где нет ни одного «обычного» зависимого атрибута, — а такие таблицы (чистые таблицы связей) сравнительно редки.

Попробуй сам

Дана таблица о навыках консультантов:

CONSULTING(consultant, skill, client)

В предметной области действует правило-цикл: если консультант владеет навыком, И этот навык требуется клиенту, И консультант уже работает с этим клиентом — то консультант применяет этот навык у этого клиента.

Выполните на бумаге:

1. Сформулируйте join dependency, которая следует из правила. На сколько проекций она раскладывает таблицу?
2. Придумайте набор из 3-4 строк и покажите, что соединение каких-то двух проекций даёт лишнюю строку, а соединение всех трёх — нет.
3. Объясните, в чём здесь избыточность: какая строка оказывается «вынужденной» при действующем правиле.
4. Выполните декомпозицию в 5NF. Затем ответьте на вопрос: если бы правила-цикла в предметной области НЕ было — можно ли было бы так разбивать таблицу? Почему?