- Пятая нормальная форма
-
Пятая нормальная форма (5NF) — одна из возможных нормальных форм отношения реляционной базы данных.
Содержание
Определение
Для определения пятой нормальной формы следует предварительно ввести понятие зависимости соединения, которое, в свою очередь основано на понятии декомпозиции без потерь.
Декомпозиция без потерь
Декомпозицией[1] отношения R называется замена R на совокупность отношений {R1, R2,... , Rn} такую, что каждое из них есть проекция R, и каждый атрибут R входит хотя бы в одну из проекций декомпозиции.
Например, для отношения R с атрибутами {a, b, c} существуют следующие основные варианты декомпозиции:
- {a}, {b}, {c}
- {a}, {b, c}
- {a, b}, {c}
- {b}, {a, c}
- {a, b}, {b, c}
- {a, b}, {a, c}
- {b, c}, {a, c}
- {a, b}, {b, c}, {a, c}
Рассмотрим теперь отношение R', которое получается в результате операции естественного соединения (NATURAL JOIN), применённой к отношениям, полученным в результате декомпозиции R.
Декомпозиция называется декомпозицией без потерь, если R' в точности совпадает с R.
Неформально говоря, при декомпозиции без потерь отношение «разделяется» на отношения-проекции таким образом, что из полученных проекций возможна «сборка» исходного отношения с помощью операции естественного соединения.
Далеко не всякая декомпозиция является декомпозицией без потерь. Проиллюстрируем это на примере отношения R с атрибутами {a, b, c}, приведённом выше. Пусть отношение R имеет вид:
R a b c Москва Россия столица Томск Россия не столица Берлин Германия столица Декомпозиция {a}, {b, c} имеет вид:
R1 a Москва Томск Берлин R2 b c Россия столица Россия не столица Германия столица Результат операции соединения этих отношений:
R' = R1 NATURAL JOIN R2 a b c Москва Россия столица Москва Россия не столица Москва Германия столица Томск Россия столица Томск Россия не столица Томск Германия столица Берлин Россия столица Берлин Россия не столица Берлин Германия столица Очевидно, что R' не совпадает с R, а значит такая декомпозиция не является декомпозицией без потерь. Рассмотрим теперь декомпозицию {a, b}, {a, c}:
R1 a b Москва Россия Томск Россия Берлин Германия R2 a c Москва столица Томск не столица Берлин столица Такая декомпозицией является декомпозицией без потерь, в чём читатель может убедиться самостоятельно.
В некоторых случаях отношение вовсе невозможно декомпозировать без потерь. Существуют также примеры отношений, для которых нельзя выполнить декомпозицию без потерь на две проекции, но которые можно подвергнуть декомпозиции без потерь на три или большее количество проекций[2].
Зависимость соединения
Пусть R — переменная отношения, а A, B, ..., Z — некоторые подмножества множества ее атрибутов.
Если декомпозиция любого допустимого значения R на отношения, состоящие из множеств атрибутов A, B, ..., Z, является декомпозицией без потерь, говорят, что переменная отношения R удовлетворяет зависимости соединения *{А, В, . . . , Z}[3].
Иными словами, переменная отношения R удовлетворяет зависимости соединения *{А, В, . . . , Z} тогда и только тогда, когда любое допустимое значение переменной отношения R эквивалентно соединению ее проекций по подмножествам A, B, ..., Z множества атрибутов.
Подобно тому, как функциональная зависимость есть частный случай многозначной зависимости, многозначная зависимость является частным случаем зависимости соединения. Зависимость соединения является предельным обобщением понятий многозначной и функциональной зависимости, то есть это наиболее общая форма зависимости между атрибутами отношения.
Важно понимать, что зависимость соединения определяется не для конкретного значения переменной отношения в тот или иной момент времени, а по всем возможным значениям. Поэтому понятие зависимости соединения определено не для отношения (конкретного значения), а для переменной отношения. Зависимость соединения определяется не механически по текущим значениям, а следует из внешнего знания о природе и закономерностях данных, которые могут находиться в переменной отношения. То же самое относится к многозначной и функциональной зависимостям.
Зависимость соединения *{A, B,..., Z} является тривиальной тогда и только тогда, когда по крайнем мере одно из подмножеств A, B, ..., Z является множеством всех атрибутов отношения (включает все атрибуты). В противном случае зависимость соединения является нетривиальной.
Формулировка определения
Отношение находится в пятой нормальной форме (иначе — в проекционно-соединительной нормальной форме) тогда и только тогда, когда каждая нетривиальная зависимость соединения в нём определяется потенциальным ключом (ключами) этого отношения[2].
Зависимость соединения *{A, B,..., Z} определяется потенциальным ключом (ключами) тогда и только тогда, когда каждое из подмножеств A, B, ..., Z множества атрибутов является суперключом отношения[2].
Условие «каждое из подмножеств A, B,..., Z множества атрибутов является суперключом отношения» можно эквивалентно сформулировать так: «каждое из подмножеств A, B, ..., Z множества атрибутов включает некоторый потенциальный ключ отношения».
Свойства 5НФ
Любое отношение в 5НФ автоматически находится также в 4НФ и, следовательно, во всех других нормальных формах. 5НФ является окончательной нормальной формой (по крайней мере в контексте операций проекции и соединения).
Рональд Фейгин в 1979 г. показал, что любая переменная отношения может быть подвергнута декомпозиции без потерь на эквивалентный набор переменных отношения в 5НФ, т.е. 5НФ всегда достижима. Однако К. Дейт отмечает, что процедура определения того, что некоторая переменная отношения все еще находится в 4НФ, а не в 5НФ, и, таким образом, существует возможность ее дальнейшей выгодной декомпозиции, все еще остается не вполне ясной. Это связано с тем, что задача определения всех зависимостей соединения для отношения может оказаться очень сложной, а по поводу отношения можно утверждать, что оно находится в 5НФ, только при условии известности всех его потенциальных ключей и всех его зависимостей соединения.
Очень редко отношение, находящееся в 4НФ, не соответствует 5НФ. Это те ситуации, в которых реальные правила, ограничивающие допустимые комбинации атрибутов, никак не выражены в структуре отношения (см. пример ниже). В таком случае, если отношение не приведено к 5НФ, бремя обеспечения логической целостности данных отчасти перекладывается на приложение, отвечающее за добавление, удаление и изменения данных. В этом случае существует риск возникновения ошибок. Пятая нормальная форма исключает возникновение таких аномалий.
Пример
Предположим, что нужно хранить данные об ассортименте нескольких продавцов, торгующих продукцией нескольких фирм (номенклатура товаров фирм может пересекаться):
Ассортимент (продавцы, фирмы, товары) Продавец Фирма Товар Иванов Рога и Копыта Пылесос Иванов Рога и Копыта Хлебница Петров Безенчук&Ко Сучкорез Петров Безенчук&Ко Пылесос Петров Безенчук&Ко Хлебница Петров Безенчук&Ко Зонт Сидоров Безенчук&Ко Пылесос Сидоров Безенчук&Ко Телескоп Сидоров Рога и Копыта Пылесос Сидоров Рога и Копыта Лампа Сидоров Геркулес Вешалка Если дополнительных условий нет, то данное отношение, которое находится в 4-ой нормальной форме, является корректным и отражает все необходимые ограничения.
Теперь предположим, что нужно учесть следующее ограничение: каждый продавец имеет в своём ассортименте ограниченный список фирм и ограниченный список типов товаров и предлагает товары из списка товаров, производимые фирмами из списка фирм.
То есть продавец не имеет право торговать какими угодно товарами каких угодно фирм. Если продавец П имеет право торговать товарами фирмы Ф, и если продавец П имеет право торговать товарами типа Т, то в этом случае в ассортимент продавца П входят товары типа Т фирмы Ф при условии, что фирма Ф производит товары типа Т.
Такое ограничение может быть вызвано, например, тем, что список типов товаров продавца ограничен имеющимися у него лицензиями, либо знаниями и квалификацией, необходимыми для их продажи, а список фирм каждого продавца определён партнёрскими соглашениями.
В рассматриваемом примере, в частности, предполагается, что продавец Иванов имеет право торговать товарами только фирмы «Рога и Копыта», продавец Петров — товарами только фирмы «Безенчук&Ко», зато продавец Сидоров не имеет право торговать хлебницами и сучкорезами и т.д.
Предложенное выше отношение не может исключить ситуации, при которых данное ограничение будет нарушено. Ничто не препятствует занести данные о торговле товаром, который данная фирма вообще не выпускает, либо данные о торговле товарами той фирмы, которую данный продавец не обслуживает, либо данные о торговле таким типом товара, который данный продавец не имеет право продавать.
Отношение не находится в 5NF, поскольку в нём есть нетривиальная зависимость соединения *{{Продавец, Фирма}, {Фирма, Товар}, {Продавец, Товар}}, однако подмножества {Продавец, Фирма}, {Фирма, Товар}, {Продавец, Товар} не являются суперключами исходного отношения.
В данном случае для приведения к 5NF отношение должно быть разбито на три: {Продавец, Фирма}, {Фирма, Товар}, {Продавец, Товар}.
Товары продавцов Продавец Товар Иванов Пылесос Иванов Хлебница Петров Сучкорез Петров Пылесос Петров Хлебница Петров Зонт Сидоров Телескоп Сидоров Пылесос Сидоров Лампа Сидоров Вешалка Фирмы продавцов Продавец Фирма Иванов Рога и Копыта Петров Безенчук&Ко Сидоров Безенчук&Ко Сидоров Рога и Копыта Сидоров Геркулес Товары фирм Фирма Товар Рога и Копыта Пылесос Рога и Копыта Хлебница Рога и Копыта Лампа Безенчук&Ко Сучкорез Безенчук&Ко Пылесос Безенчук&Ко Хлебница Безенчук&Ко Зонт Безенчук&Ко Телескоп Геркулес Вешалка Примечания
- ↑ Строго говоря, следует использовать термин «проекционная декомпозиция», или «декомпозиция на основе проекции», поскольку разделение исходного отношения выполняется через операцию проекции. Теоретически существуют другие варианты декомпозиции, например на основе операции сокращения (выборки), однако они являются экзотическими, вследствие чего под декомпозицией, если специально не оговорено иное, понимают именно проекционную декомпозицию.
- ↑ 1 2 3 Дейт К. Дж. Введение в системы баз данных. — 8-е изд. — М.: «Вильямс», 2005
- ↑ Читается «звёздочка А, B, ..., Z»
Литература
Отечественная
- Когаловский М.Р. Энциклопедия технологий баз данных. — М.: Финансы и статистика, 2002. — 800 с. — ISBN 5-279-02276-4
- Кузнецов С. Д. Основы баз данных. — 2-е изд. — М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2007. — 484 с. — ISBN 978-5-94774-736-2
Переводная
- Дейт К. Дж. Введение в системы баз данных = Introduction to Database Systems. — 8-е изд. — М.: Вильямс, 2005. — 1328 с. — ISBN 5-8459-0788-8 (рус.) 0-321-19784-4 (англ.)
- Коннолли Т., Бегг К. Базы данных. Проектирование, реализация и сопровождение. Теория и практика = Database Systems: A Practical Approach to Design, Implementation, and Management. — 3-е изд. — М.: Вильямс, 2003. — 1436 с. — ISBN 0-201-70857-4
- Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс = Database Systems: The Complete Book. — Вильямс, 2003. — 1088 с. — ISBN 5-8459-0384-X
Иностранная
- C. J. Date Date on Database: Writings 2000–2006. — Apress, 2006. — 566 с. — ISBN 978-1-59059-746-0, 1-59059-746-X
Нормальные формыКатегории:- Реляционная модель данных
- Теоретические основы баз данных
Wikimedia Foundation. 2010.
