• Познакомьтесь с пентестом веб-приложений на практике в нашем новом бесплатном курсе

    «Анализ защищенности веб-приложений»

    🔥 Записаться бесплатно!

  • CTF с учебными материалами Codeby Games

    Обучение кибербезопасности в игровой форме. Более 200 заданий по Active Directory, OSINT, PWN, Веб, Стеганографии, Реверс-инжинирингу, Форензике и Криптографии. Школа CTF с бесплатными курсами по всем категориям.

Нормализация реляционных баз данных.

  • Автор темы Golaih
  • Дата начала
G

Golaih

Нормализация реляционных баз данных.
Подобно другим отраслям информатики, в реляционной теории нет универсальных рецептов для проектирования надежной и эффективной в использовании базы данных. Разработчик волен выбирать различные инструменты и методы проектирования. Некоторые полагаются исключительно на интуицию и здравый смысл, другие используют различные вспомогательные средства, порой довольно изощренные.
Однако при всем разнообразии подходов все же есть некоторые каноны, нарушение которых весьма отрицательно скажется как при проектировании базы данных, так и при ее эксплуатации. Так, например, весьма актуальной является проблема нормализации баз данных. Пренебрежение нормализацией делает структуру базы данных запутанной, а саму базу - ненадежной в работе.
Итак, основная тема очередной статьи - нормализация баз данных. Однако перед тем как приступить к ее изучению, нам придется разобраться с некоторыми важными понятиями реляционной теории. Одно из них - понятие ключа.
Ключ
Раз уж мы взялись за изучение реляционной теории, а теория эта, как и информатика в целом, базируется на математике, то нам не обойтись без некоторого формализма, даже если кому-то формальный подход покажется излишне усложненным. После формальных определений я постараюсь прокомментировать их и изложить то же самое более доступным языком. Если же моя попытка не увенчается успехом и какие-то моменты останутся неясными - милости просим в мой раздел форума, разберем их подробнее.
Вспомним ранее пройденный материал. Мы уже знаем, что отношение состоит из кортежей (или, более простыми словами, таблица состоит из строк, хотя это не вполне корректно). Естественно, что функции системы управления базами данных не исчерпываются простым накоплением данных; мы хотим также манипулировать содержимым БД. Для этого необходимо иметь возможность каким-то образом отличать кортежи друг от друга.
Приходим к выводу, что кортеж должен содержать в себе какую-то уникальную метку, однозначно идентифицирующую его среди всех остальных кортежей отношения. Такой меткой и является ключ.
Определение. Пусть r - отношение, R - его схема. Ключом K отношения r называется подмножество атрибутов {A1, A2, , Am} <= R, обладающее следующим свойством: для любых двух различных кортежей t1 и t2 из r существует A?K такое, что t1(A) != t2(A). Т.е. не существует двух кортежей, которые бы имели одно и то же значение на всех атрибутах из K. Таким образом, K-значение кортежа однозначно идентифицирует кортеж в r. (Из-за ограничений символьного набора, доступного при публикации статьи на сайте, мне пришлось воспользоваться следующими обозначениями: здесь и далее символ "<=" означает "является несобственным подмножеством", символ "?" "означает принадлежит множеству", а "!=" означает "не равно").
То же самое неформальным языком: ключом отношения называется набор атрибутов отношения, однозначно определяющий кортеж. Или еще проще: ключ - это набор столбцов таблицы, значения которых уникально определяют строку.

Так это выглядит в теории. На практике возникает довольно каверзный вопрос: как убедиться, что данный набор атрибутов действительно является ключом? Казалось бы, проверить это элементарно: взять и отсортировать строки таблицы лексикографически, а потом пройтись по всем строкам и проверить, не имеют ли соседние строки одинаковых значений ключа?
Рецепт и вправду прост, но осложняется тем, что состояние отношения обычно не является константой: кортежи постоянно добавляются, удаляются или меняют значения атрибутов. В результате набор, который является ключом в данный момент, в общем случае вовсе не обязательно будет таковым через некоторое время.
Простой пример. Владелец маленькой фирмы заказал нам систему для ведения кадров и зарплаты. В ходе анализа выясняется, что у него в данный момент работают 3 человека: Иванов, Петров и Сидоров. Мы убеждаемся, что фамилия однозначно определяет работника, и принимаем решение: сделать атрибут "Фамилия" ключом в таблице, где хранится перечень работников.
Система работает некоторое время без проблем. Благодаря наведенному порядку фирма процветает все больше, и в конечном итоге персонал вырастает до сотни человек. Внезапно при приеме очередного работника система дает сбой. Выясняется, что его фамилия тоже Иванов. Таким образом, нарушается уникальность ключа, что делает невозможным дальнейшую работу системы.
Мы пытаемся спасти положение, расширяя ключ на столбцы "Имя" и "Отчество". Программа вновь оживает, но при этом мы знаем, что это всего лишь заметание мусора под ковер: проблема не решена окончательно, а всего лишь уменьшена вероятность очередного сбоя по причине нарушения уникальности ключа.
Итак, оказывается, одной математики здесь недостаточно. Нужно применить знание предметной области, чтобы гарантировать уникальность ключа. В данном случае опыт подсказывает нам, что однофамильцы - далеко не редкое явление в коллективе, а совпадение имени-отчества - тоже вполне предсказуемая ситуация.
Зачастую проблема решается введением так называемого суррогатного ключа: к имеющимся атрибутам, которые отражают свойство реального объекта, добавляется еще один (или более), искусственного происхождения, сам способ получения которого гарантирует уникальность. К суррогатным ключам относятся табельные номера сотрудников, регистрационные номера автомобилей, серийные номера изделий и т.д. Да и номерок, который вы получаете в гардеробе, также можно отнести к суррогатным ключам, которым гардеробщик однозначно помечает вашу персону, чтобы отличить ее от сотен подобных при выдаче вещей.
Здесь возникает довольно интересный вопрос. Предположим, что наше отношение r имеет в качестве ключа множество атрибутов {A1, A2, , Am}. Добавим к этому множеству еще один атрибут, Am+1. Является ли множество {A1, A2, , Am, Am+1} ключом r? Формально - безусловно является, поскольку ключ по-прежнему однозначно идентифицирует кортежи r. Однако чувствуется какой-то подвох. Во-первых, добавленный атрибут в ключе явно лишний, поскольку ключ справлялся с задачей идентификации и без него. Во-вторых, есть опасность, что одним атрибутом это добавление не ограничится, и нам придется иметь дело с целым множеством ключей. Как же ограничить ключевое множество атрибутов действительно необходимым минимумом?
Чтобы выкрутиться из данной ситуации, сделаем определение ключа несколько более строгим:
Ключом K отношения r называется подмножество атрибутов {A1, A2, , Am} <= R, такое, что для любых двух различных кортежей t1 и t2 из r выполняется t1(K) != t2(K), и при этом ни одно собственное подмножество K<K не обладает этим свойством.
Множество SK называется суперключом отношения r, если K - ключ r и K<=SK. Очевидно, что первоначально введенное определение ключа на самом деле относится к суперключу.
Функциональные зависимости
Наберемся еще немного терпения перед тем, как приступить к основной теме статьи - нормализации. Нам предстоит ознакомиться с весьма важным понятием функциональной зависимости (ФЗ).
Как неоднократно упоминалось ранее, хранение данных в реляционных базах данных преследует две цели: понизить избыточность данных и повысить их достоверность. Для этого необходимо иметь возможность накладывать некоторые ограничения как на сами хранимые данные, так и на взаимосвязи и взаимозависимости между ними, т.к. в противном случае вместо базы данных мы получим просто свалку, лишенную всякой структуры. Обычно эти ограничения вытекают из анализа предметной области, которая моделируется нашей информационной системой. Одним из средств формализации информации, полученной в результате такого анализа, являются зависимости между данными
Существует несколько разновидностей зависимостей, которые рассматриваются реляционной теорией: F-зависимости, MV-зависимости и J-зависимости. В настоящий момент наибольший интерес среди них для нас представляют функциональные зависимости, или F-зависимости.
Перед тем, как дать формальное определение функциональной зависимости, приведу пример (заимствованный из книги: Д.Мейер. Теория реляционных баз данных. - М: Мир, 1987). В этом примере используется отношение График(ПИЛОТ РЕЙС ДАТА ВРЕМЯ-ВЫЛЕТА):

Табл.1ПИЛОТ РЕЙС ДАТА ВРЕМЯ-ВЫЛЕТА
Кушинг 83 09 авг 10:15
Кушинг 116 10 авг 13:25
Кларк 281 08 авг 05:50
Кларк 301 12 авг 18:35
Кларк 83 11 авг 10:15
Чин 83 13 авг 10:15
Чин 116 12 авг 13:25
Коупли 281 09 авг 05:50
Коупли 281 13 авг 05:50
Коупли 412 15 авг 13:25
Данное отношение содержит информацию о полетах. Каждая строка таблицы расписания представляет собой один вылет и указывает, какой пилот поведет самолет какого рейса в данный день, а также в какое время совершается вылет.
Предположим, что не каждое сочетание данных является допустимым. На совокупность данных накладывается ряд ограничений:
Каждый рейс имеет определенное время вылета.
Данный пилот в данные день и время может участвовать только в одном рейсе.
Для данного рейса и даты назначается только один пилот.
Рассмотрев исходные данные с учетом этих ограничений, мы можем сделать ряд выводов:
ВРЕМЯ-ВЫЛЕТА функционально зависит от РЕЙСА.
РЕЙС функционально зависит от {ПИЛОТ, ДАТА, ВРЕМЯ-ВЫЛЕТА}.
ПИЛОТ функционально зависит от {РЕЙС, ДАТА}.
Итак, если значения кортежа на некотором множестве атрибутов единственным образом определяют значения на другом множестве атрибутов, говорят, что имеет место функциональная зависимость или, короче, F-зависимость.
Нормализация отношений
Под нормализацией отношения подразумевается процесс приведения отношения к одной из так называемых нормальных форм (или в дальнейшем НФ). Однако перед рассмотрением НФ следует сказать несколько слов, зачем нужна нормализация.
Как уже неоднократно упоминалось в данном цикле, база данных - это не просто хранилище фактов (с этой задачей способны справиться и незатейливые плоские файлы). При проектировании баз данных упор в первую очередь делается на достоверность и непротиворечивость хранимых данных, причем эти свойства не должны утрачиваться в процессе работы с данными, т.е. после многочисленных изменений, удалений и дополнений данных по отношению к первоначальному состоянию БД.

Для поддержания БД в устойчивом состоянии используется ряд механизмов, которые получили обобщенное название средств поддержки целостности. Эти механизмы применяются как статически (на этапе проектирования БД), так и динамически (в процессе работы с БД). Динамические средства поддержки целостности мы рассмотрим в следующих статьях, а сейчас обратим внимание на те ограничения, которым должна удовлетворять БД в процессе создания, независимо от ее наполнения данными. Приведение структуры БД в соответствие этим ограничениям - это и есть нормализация.
В целом суть этих ограничений весьма проста: каждый факт, хранимый в БД, должен храниться один-единственный раз, поскольку дублирование может привести (и на практике непременно приводит, как только проект приобретает реальную сложность) к несогласованности между копиями одной и той же информации. Следует избегать любых неоднозначностей, а также избыточности хранимой информации.
С этими требованиями трудно не согласиться, выглядят они вполне разумно. Но еще труднее следовать им на практике, если они сформулированы столь туманно и неопределенно.
Впрочем, для устранения всяческих неопределенностей и неоднозначностей традиционно используется формальный язык математики. Воспользуемся им и мы, тем более что для реляционных БД, построенных на солидном математическом фундаменте, формализмы достаточно хорошо проработаны.
Итак, наша цель - приведение отношений к НФ. Следует заметить, что в процессе нормализации постоянно встречается ситуация, когда отношение приходится разложить на несколько других отношений. Поэтому более корректно было бы говорить о нормализации не отдельных отношений, а всей их совокупности в БД. Однако в примерах для простоты я по возможности постараюсь иметь дело с отдельными отношениями, если это не приведет к неясностям. Нормализация реальных баз данных - гораздо более трудоемкий процесс.

Впрочем, не все обстоит так плохо. Нормализация может не представлять такую уж проблему, если БД проектируется сразу по определенным канонам. Другими словами, можно сначала сделать БД как попало, а потом нормализовать ее, или же с самого начала строить ее по правилам, чтобы в дальнейшем не пришлось переделывать. Сейчас мы пойдем первым путем, т.е. возьмем в качестве примеров никуда не годные БД и попытаемся привести их в порядок. При этом будем иметь в виду, что при профессиональном подходе к проектированию БД используется одна из хорошо проработанных технологий (я предпочитаю IDEF1X), и, возможно, какие-либо инструментальные средства, поддерживающие эту технологию (мой выбор - AllFusion Data Modeler производства Computer Associates).
Итак, что же представляет собой процесс нормализации? Фактически это не что иное, как последовательное преобразование исходной БД к НФ, при этом каждая следующая НФ обязательно включает в себя предыдущую (что, собственно, и позволяет разбить процесс на этапы и производить его однократно, не возвращаясь к предыдущим этапам). Всего в реляционной теории насчитывается 6 НФ:
1-я НФ (обычно обозначается также 1НФ).
2НФ.
3НФ.
НФ Бойса-Кодда (НФБК).
4НФ.
5НФ.
На практике, как правило, ограничиваются 3НФ, ее оказывается вполне достаточно для создания надежной схемы БД. НФ более высокого порядка представляют скорее академический интерес из-за чрезмерной сложности. Более того, при реализации абстрактной схемы БД в виде реальной базы иногда разработчики вынуждены сделать шаг назад - провести денормализацию с целью повышения эффективности, ибо идеальная с точки зрения теории структура может оказаться слишком накладной на практике.
Рассмотрим подробнее три первые НФ.
Если на интуитивном уровне понятно, что представляет собой F-зависимость, попробуем дать ее более строгое определение на основе реляционной алгебры.
Пусть r - отношение со схемой R, X и Y - подмножества R. Отношение r удовлетворяет функциональной зависимости X->Y, если (r WHERE (X=x))[Y] имеет не более одного кортежа для каждого X-значения x. Другими словами, возьмем любые два кортежа t1 и t2. Если X->Y и t1(X)=t2(X), то t1(Y)=t2(Y).
Не правда ли, данное определение весьма сходно с определением ключа из предыдущей главы? Это сходство не случайно. Фактически X является ключом отношения r[XY] (попробуйте убедиться в этом самостоятельно).
Теперь мы, пожалуй, достаточно подкованы теоретически, чтобы приступить к рассмотрению нашей основной темы - нормализации отношений.
 
E

etc

Kmet просвещение в массы, автор мессия :(
 
E

etc


 
Мы в соцсетях:

Обучение наступательной кибербезопасности в игровой форме. Начать игру!