Lossless-join и dependency-preserving декомпозиция

В предыдущих уроках мы много раз разбивали таблицы на части и каждый раз утверждали: «декомпозиция lossless». Пришло время доказать это формально. У любого разбиения таблицы на части есть два свойства качества: lossless-join (соединение без потерь) и dependency-preserving (сохранение зависимостей). Первое обязательно всегда. Второе желательно, но, как мы видели на BCNF, достижимо не всегда.

В этом уроке — формальные тесты на оба свойства. Их полезно уметь применять руками: они превращают «декомпозиция выглядит правильной» в «декомпозиция доказанно корректна».

Зачем нужны два свойства

Когда мы заменяем одну таблицу R несколькими таблицами R1, R2, ..., мы должны быть уверены в двух вещах.

Первое — мы ничего не потеряли и ничего не выдумали. Если соединить R1, R2, ... обратно, должна получиться ровно исходная R. Не меньше строк (потеря данных) и не больше (фантомные строки). Это свойство lossless-join. Оно не обсуждается: декомпозиция, которая его нарушает, попросту неверна — она искажает данные.

Второе — мы не потеряли возможность проверять правила. Каждая функциональная зависимость исходной R — это бизнес-инвариант, который СУБД должна стеречь. После декомпозиции хочется, чтобы каждую FD можно было проверить локально, в пределах одной таблицы, обычным UNIQUE-ограничением. Если это так — декомпозиция dependency-preserving.

Lossless-join важнее: его нарушение делает базу неверной. Отсутствие dependency-preservation базу неверной не делает — но усложняет поддержание целостности, потому что часть правил приходится проверять соединением нескольких таблиц.

Тест на lossless-join для двух таблиц

Начнём с разбиения на две таблицы — самый частый случай. Пусть R разбили на R1 и R2.

Критерий (теорема о lossless-декомпозиции на две части). Разбиение R на R1 и R2 является lossless тогда и только тогда, когда их общие атрибуты образуют ключ хотя бы одной из таблиц. Формально: пусть common — множество атрибутов, входящих в обе таблицы (пересечение R1 и R2). Декомпозиция lossless, если выполнена хотя бы одна FD:

common -> R1        общие атрибуты являются ключом R1
   ИЛИ
common -> R2        общие атрибуты являются ключом R2

где common = пересечение атрибутов R1 и R2 (атрибуты, входящие в обе таблицы)

Интуиция простая. Соединение R1 и R2 идёт по общим атрибутам. Если общие атрибуты — ключ одной из таблиц, то каждой строке этой таблицы соответствует не более одной строки по совпадению ключа, соединение не «размножает» строки, и фантомов не возникает. Если же общие атрибуты не ключ ни для одной — соединение «многие ко многим» породит лишние комбинации.

Проверим на декомпозиции из урока про 3NF. Таблицу EMPLOYEES(emp_id, emp_name, dept_id, dept_name, dept_location) разбили на:

DEPARTMENTS(dept_id, dept_name, dept_location)
EMPLOYEES2(emp_id, emp_name, dept_id)

Общие атрибуты двух таблиц — common = {dept_id}. Проверяем критерий. Является ли dept_id ключом таблицы DEPARTMENTS? Да — dept_id это её первичный ключ, значит {dept_id} -> DEPARTMENTS выполнена. Критерий удовлетворён — декомпозиция lossless. Соединив EMPLOYEES2 и DEPARTMENTS по dept_id, мы точно восстановим исходную таблицу.

А теперь — пример lossy разбиения, чтобы увидеть, что бывает, когда критерий нарушен. Разобьём EMPLOYEES неудачно — по dept_name:

A(emp_id, emp_name, dept_name)
B(dept_name, dept_location)

Общие атрибуты — {dept_name}. Ключ ли dept_name для A? Нет (ключ A — emp_id). Ключ ли для B? Только если названия отделов уникальны. Если в компании два отдела с названием «Отдел продаж» в разных городах, то dept_name не ключ B, и соединение A и B по dept_name припишет сотруднику обе локации — появятся фантомные строки. Декомпозиция lossy, данные искажены.

Тест на dependency-preservation

Теперь второе свойство. Декомпозиция R на R1, ..., Rn является dependency-preserving, если набор всех FD исходной таблицы можно восстановить из FD, которые проверяемы внутри отдельных таблиц.

Формально вводят понятие проекции набора FD на таблицу. Проекция набора FD F на таблицу Ri — это все FD из замыкания F+, у которых и левая, и правая часть целиком лежат внутри атрибутов Ri. Такие FD таблица Ri может проверять сама. Декомпозиция dependency-preserving, если объединение проекций по всем Ri функционально эквивалентно исходному F (то есть из объединённых проекций выводится каждая исходная FD).

Практический алгоритм проверки для одной FD X -> Y:

проверить, сохранена ли FD (X -> Y) при наборе FD F и таблицах R1..Rn:
    result = X
    repeat:
        for каждой таблицы Ri:
            common_i = пересечение result и атрибутов Ri
            t = пересечение (замыкание common_i по F) и атрибутов Ri
            result = result + t
    until result не меняется
    FD сохранена, если Y является подмножеством result

Идея: мы пытаемся «вычислить» зависимость X -> Y, пользуясь только теми кусками FD, что видны внутри отдельных таблиц. Если получилось дотянуться от X до Y — FD сохранена. Если все FD исходного набора прошли проверку — декомпозиция dependency-preserving.

Применим к удачной декомпозиции EMPLOYEES. Исходные FD: emp_id -> emp_name, emp_id -> dept_id, dept_id -> dept_name, dept_id -> dept_location. Таблицы: EMPLOYEES2(emp_id, emp_name, dept_id) и DEPARTMENTS(dept_id, dept_name, dept_location).

• emp_id -> emp_name: оба атрибута в EMPLOYEES2 — проверяема там. Сохранена.
• emp_id -> dept_id: оба в EMPLOYEES2 — сохранена.
• dept_id -> dept_name: оба в DEPARTMENTS — сохранена.
• dept_id -> dept_location: оба в DEPARTMENTS — сохранена.

Все четыре FD проверяемы локально. Декомпозиция dependency-preserving. И lossless мы уже доказали — значит разбиение EMPLOYEES идеально по обоим критериям.

Когда dependency-preservation теряется: возврат к BCNF

Теперь — обещанный случай, где decomposition lossless, но не dependency-preserving. Вернёмся к таблице TEACHING(student, subject, teacher) из урока про BCNF. FD:

FD1: {student, subject} -> teacher
FD2: {teacher} -> subject

BCNF-декомпозиция по нарушающей FD2 дала:

TEACHER_SUBJECT(teacher, subject)   -- из FD2
ENROLLMENT(student, teacher)        -- остаток

Lossless? Общие атрибуты — {teacher}. teacher — ключ таблицы TEACHER_SUBJECT (там FD teacher -> subject). Критерий выполнен — декомпозиция lossless.

Dependency-preserving? Проверяем FD1 {student, subject} -> teacher.

• FD2 teacher -> subject: оба атрибута в TEACHER_SUBJECT — проверяема. Сохранена.
• FD1 {student, subject} -> teacher: атрибут student есть только в ENROLLMENT, атрибут subject — только в TEACHER_SUBJECT. Нет ни одной таблицы, которая содержит и student, и subject, и teacher одновременно. Прогоним алгоритм: result = {student, subject}; пересечение с ENROLLMENT(student, teacher) даёт {student}, замыкание {student} по F — это {student}, добавлять нечего; пересечение с TEACHER_SUBJECT(teacher, subject) даёт {subject}, замыкание {subject} — {subject}, добавлять нечего. result остался {student, subject}, до teacher мы не дотянулись. FD1 не сохранена.

Декомпозиция TEACHING в BCNF lossless, но не dependency-preserving: FD1 «разъехалась» по двум таблицам, и проверить «студент по предмету учится у одного преподавателя» декларативным UNIQUE теперь нельзя — нужно соединять ENROLLMENT и TEACHER_SUBJECT и проверять уникальность на результате.

Сводка: как пользоваться двумя тестами

При любой декомпозиции прогоняйте оба теста.

Алгоритм-итог при нормализации: разбивайте таблицу по детерминантам FD — тогда lossless получается автоматически. Затем проверяйте dependency-preservation. Если до BCNF удаётся дойти, не теряя зависимостей, — отлично. Если BCNF ломает важную FD — останавливайтесь на 3NF: она гарантирует оба свойства.

Попробуй сам

Таблица PROJECTS(project_id, project_name, lead_id, lead_email) с FD: project_id -> project_name, project_id -> lead_id, lead_id -> lead_email. Её разбили на P1(project_id, project_name, lead_id) и P2(lead_id, lead_email).

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

1. Примените тест на lossless-join. Найдите общие атрибуты двух таблиц и проверьте, образуют ли они ключ одной из них. Lossless ли разбиение?
2. Примените тест на dependency-preservation для каждой из трёх FD. В какой таблице проверяема каждая? Сохранены ли все три?
3. Сделайте вывод: идеальна ли эта декомпозиция по обоим критериям?
4. Придумайте неудачное разбиение той же таблицы, которое было бы lossy, и объясните через критерий, почему соединение даст фантомные строки.