DRKB Download О проекте Авторы Ссылки Благодарности Пожертвования Реклама

DRKB ➤ Базы данных ➤ Теория баз данных, архитектура и проектирование ➤ Математические основы реляционных СУБД

Математические основы реляционных СУБД

01.01.2007

Понятие отношения. Основные операции. Реляционная алгебра и реляционное исчисление. Понятие о нормализации. Первая, вторая, третья и четвертая нормальные формы.

4.1. Основные понятия

Дадим точное, математическое понятие терминов, используемых для реляционных баз данных.

Доменом называется некоторое множество значений определенного типа. Это множество может быть конечным, так и бесконечным. Например, доменом является множество {true, false}, множество всех целых чисел, множество всех символьных строк и т.д. Декартовым произведением доменов D1, D2,…., Dk, обозначаемое как D1ЧD2Ч….ЧDk называется множество всех кортежей (d1, d2,…., dk), где di принадлежит Di. То есть декартовое произведение состоит из всех возможных комбинаций значений из доменов. Общее число кортежей в декартовом произведении равно произведению размеров каждого домена. Кроме того, ничто не мешает умножать домены сами на себя.

Существенным в декартовом произведении является порядок доменов. Так, D1ЧD2 не равно D2ЧD1. При сравнении кортежей внутри одного произведения также важно учитывать порядок значений внутри кортежа - кортеж (0, 1) не равен кортежу (1, 0).

Отношением называется некоторое подмножество декартового произведения доменов. Это множество может быть пустым. Теоретически, ничто не мешает отношению состоять из бесконечного числа кортежей, но в приложении к базам данных имеет смысл рассматривать только конечные множества.

В реальных, практических задачах имеет смысл ввести именование доменов внутри декартового произведения (и, следовательно, построенного из него отношения), что позволит отказаться от нумерации доменов и использовать более привычное именование. Кроме того, в реляционных базах данных используется термин таблица вместо отношения, и термин запись или ряд вместо кортежа. Мы будем использовать эти термины в одном смысле, но при описании математических деталей будет использоваться термин “отношение”, а при рассмотрении конкретных задач - термин “таблица”.

Для представления реальных сущностей (объектов) используется следующая интерпретация приведенных выше математических понятий. Каждый домен, который мы договорились именовать, описывает некоторый атрибут, то есть ту или иную именованную характеристику реальной сущности, реального объекта. Например, это может быть “вес” (тогда домен представляет собой положительное целое), это может быть “имя” (тогда домен есть множество символьных строк) и т.д. Таблица описывает некоторую совокупность однотипных объектов реального мира (например, сотрудников на предприятии, список продаваемых товаров и т.д.), а каждая отдельная запись в отношении описывает некоторый конкретный объект (конкретного человека или конкретный товар). При этом каждая запись состоит из значений атрибутов, которые определяют характеристики этой сущности или объекта. Например, если мы описываем товары, то атрибутами будут (имеет смысл выбрать эти атрибуты) название, стоимость, условия хранения, вес, габариты и т.д. Какие именно атрибуты будут задействованы, какие именно названия будут им приписаны, зависит от предметной области, от того, как это будет реализовано разработчиками. Приведем пример таблицы, описывающей товары и имеющей атрибуты “товар” (определяет название товара), “производитель” (определяет фирму, которая произвела этот товар) и “адрес” (определяет адрес фирмы, произведшей данный товар):

-----------T--------------------------T-----------------+
¦ Товар   ¦ производитель            ¦ Адрес           ¦
+----------+--------------------------+-----------------+
¦ рога    ¦ АО Рога и Копыта         ¦ Одесса, п/я 13 ¦
¦ копыта ¦ АО Рога и Копыта         ¦ Одесса, п/я 13 ¦
¦ кеды    ¦ АО Рога и Копыта         ¦ Одесса, п/я 13 ¦
¦ джинсы ¦ ТОО Добро пожаловать     ¦ Энск, 5-е авеню ¦

L----------+--------------------------+------------------

Рис. 4.1. Пример таблицы “Товары”.

Отметим еще раз, что, так как атрибуты именованы, и порядок записей в таблице не важен, можно поменять порядок столбцов и строк, а таблица с точки зрения реляционной модели останется той же самой:

+--------------------------T---------T ----------------+
¦ производитель            ¦ Товар   ¦ Адрес           ¦
+--------------------------+---------+-----------------+
¦ АО Рога и Копыта         ¦ кеды    ¦ Одесса, п/я 13 ¦
¦ АО Рога и Копыта         ¦ копыта ¦ Одесса, п/я 13 ¦
¦ ТОО Добро пожаловать     ¦ джинсы ¦ Энск, 5-е авеню ¦
¦ АО Рога и Копыта         ¦ рога    ¦ Одесса, п/я 13 ¦

L--------------------------+---------+------------------

Рис. 4.2. Другой вариант представления таблицы “Товары” из рисунка 4.1.

4.2. Ключи

Для реальной работы с объектами, описанными в таблице, нужно уметь их различать. Один и тот же поставщик может поставлять два разных товара с одним и тем же названием (джинсы и джинсы). При этом могут совпадать и другие атрибуты (например, цена). Тем не менее, физически это будут разные товары. Для идентификации записей используются ключи. Ключ - это набор атрибутов, которые позволяет идентифицировать запись внутри таблицы, при этом никакое подмножество этих атрибутов не будет ключом. Ключ может быть простым и составным. Простой ключ состоит из одного атрибута, составной ключ - из двух и более. Атрибут, входящий в тот или иной ключ, называется ключевым атрибутом. Соответственно, ключ, который не входит ни в один из ключей, называется неключевым атрибутом.

Заметим, что ключ должен гарантировать уникальную идентификацию записи для всех возможных комбинаций записей в отношении. Например, в таблице с описанием товаров, представленной на рисунках 4.1. и 4.2., если смотреть по ее конкретному состоянию, поле “Товар” вроде бы может считать ключом (в этой таблице 4 записи, в поле “Товар” имеем 4 разных значения и каждая запись в данной ситуации может быть идентифицирована по полю “Товар”). Однако очевидно, что один и тот же товар может поставляться несколькими поставщиками и в общем случае в данной таблице поле “Товар” не может считаться ключевым. Более того, в той схеме, какую эта таблица имеет сейчас, вообще нет ключей.

Некоторый ключ, который разаработчики или проектировщики схемы базы данных выделяют и стараются использовать, называется первичным. Любой из ключей может считаться первичным, вопрос именно в предпочтении и простоте использования.

Ключи бывают естественными и искусственными. Естественный ключ состоит из реальных атрибутов, то есть атрибутов, которые существуют в предметной области и которые представляют интерес для решаемой задачи (например, фамилия-имя-отчество, номер счета и т.д.). Искусственный ключ вводится специально и используется как исскуственный атрибут именно для выполнения функции ключа. Потребность во введении искусственных ключей возникает по нескольким причинам. Первое, естественный ключ может состоять из большого числа атрибутов и работать с таким ключом очень неудобно. Второе, как показывает опыт, естественные ключи, то есть набор реальных атрибутов, действительно однозначно определяющих запись в отношении встречается очень редко. Даже такой, казалось бы, естественный ключ для идентификации человека, как номер внутреннего паспорта, не может быть естественным ключом (хотя бы по той причине, что паспорта выдаются только в 16 лет).

Вообще говоря, нигде нет ограничений на то, что ключ должен быть неизменным. Однако с точки зрения организации длительного использования информации, с точки зрения того, что данные могут храниться и использоваться в распределенной системе, использование изменяемого ключа может вызвать трудности.

Рассмотрим пример. Предположим, мы все же хотим ввести ключ в таблицу “Товары” (см. Рисунок 4.2.). Вообще говоря, товар может идентифицироваться по бар-коду, который дается данному изделию производителем.

---------T----------T ----------------------T-----------------+
¦ Товар ¦ Бар-код ¦ производитель        ¦ Адрес           ¦
+--------+----------+----------------------+-----------------+
¦ рога   ¦ 46131313 ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ копыта ¦ 46061235 ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ кеды   ¦ 01000004 ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ джинсы ¦ 02000551 ¦ ТОО Добро пожаловать ¦ Энск, 5-е авеню ¦

L--------+----------+----------------------+------------------

Рис. 4.3. Модифицированная таблица “Товары”.

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

---------T----------T ----------------------T-----------------+
¦ Товар ¦ id       ¦ Производитель        ¦ Адрес           ¦
+--------+----------+----------------------+-----------------+
¦ рога   ¦ #105     ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ копыта ¦ #106     ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ кеды   ¦ #214     ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ джинсы ¦ #157003 ¦ ТОО Добро пожаловать ¦ Энск, 5-е авеню ¦

L--------+----------+----------------------+------------------

Рис. 4.4. Таблица “Товары” с введеным искусственным ключом.

Требование наличия ключа в отношении, строго говоря, не является обязательным. Возможно, что в отношении вообще нет ключей. Это означает, что в отношении возможны дублирующие записи. Так как отношение предназначено для описания объектов или сущностей реальной предметной области, то возможность дублирования записей означает, что мы или имеем несколько идентичных записей об одном и том же объекте, или не можем различать эти объекты с помощью имеющегося набора атрибутов. И в том, и в другом случае такое отношение не представляет для нас практического интереса и в дальнейшем мы всегда будем предполагать, что для рассматриваемых отношений ключ всегда существует.

4.3. Основные операции над таблицами и их интерпретация

Проекция - операция, заключающаяся в удалении некоторых столбцов в отношении. Среди оставшихся записей с меньшим числом атрибутов может проводиться удаление дупликатов (одинаковых записей). С математической точки зрения, проекция отношения D(d1, d2,…., dk) на набор атрибутов D1,D2,….,Dn, где n<=k есть множество записей P(p1, p2,…., pk) таких, что для каждой записи из P существует набор атрибутов {dk+1, dk+2,…., dn} такой, что запись {p1, p2,…., pk dk+1, dk+2,…., dn} принадлежит исходному отношению D. Смысл операции проекции заключается в выделении из отношения той информации, которая нам нужна. Например, проекция отношения “Товары” по атрибутам “Производитель” и “Адрес” даст нам список всех поставщиков с их адресами:

+----------------------T-----------------+
¦ Производитель ¦ Адрес ¦
+----------------------+-----------------+
¦ АО Рога и Копыта ¦ Одесса, п/я 13 ¦
¦ ТОО Добро пожаловать ¦ Энск, 5-е авеню ¦

+----------------------+-----------------+

Рис. 4.5. Проекция таблицы “Товары” для получения списка фирм-производителей.

Селекция - операция, заключающаяся в удалении некоторых записей в отношении на основе некоторого условия. Условие определяться как логическое выражение на значениями атрибутов. В этом логическом выражении можно использовать операции “больше”, “меньше”, “равно”, “принадлежит множеству” и т.д. Операция селекции, как и операция проекции, позволяет выделеть из отношения ту информацию, которая нам нужна. Но, в отличии от операции проекции, выбираются подходходящие записи, а не интересующие нас атрибуты. Например, селекция отношения “Товары” по условию “атрибут “Производитель” есть “АО Рога и Копыта”” позволит нам получить список всех товаров, поставляемых данной фирмой:

L----------+--------------------------+------------------

Рис. 4.6. Селекция таблицы “Товары” по условию.

Объединение - операция, заключающаяся в построении нового отношения на основе двух других (все отношения должны иметь одинаковое число атрибутов). В объединение попадают все записи как первого отношения, так и второго, и никакие другие записи. При этом совсем не обязательно, чтобы объединяемые таблицы, как и результирующая таблица имели одинаковые названия атрибутов (в случае, если мы используем именованные атрибуты). Конечно, не стоит забывать о том, что результирующее объединение должно быть осмысленным.

Операция объединения позволяет собрать информацию из разных источников. Например, если мы имеем отдельную таблицу со списком фирм-производителей товаров, и отдельную таблицу со списком фирм, которым мы поставляем некоторую продукцию, то объединив эти две таблицы мы можем получить список фирм-партнеров.

Таблица “Фирмы-производители”
+----------------------T-----------------+
¦ Производитель ¦ Адрес ¦
+----------------------+-----------------+
¦ АО Рога и Копыта ¦ Одесса, п/я 13 ¦
¦ ТОО Добро пожаловать ¦ Энск, 5-е авеню ¦

+----------------------+-----------------+

Таблица “Фирмы-потребители”
+----------------------T-----------------+
¦ Потребитель ¦ Адрес ¦
+----------------------+-----------------+
¦ ЗАО Антилопа Гну ¦ Приморск, Остапу¦
¦ ТОО Добро пожаловать ¦ Энск, 5-е авеню ¦

+----------------------+-----------------+

Результирующая таблица “Фирмы-партнеры”
+----------------------T-----------------+
¦ Партнер              ¦ Адрес           ¦
+----------------------+-----------------+
¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ ЗАО Антилопа Гну     ¦ Приморск, Остапу¦
¦ ТОО Добро пожаловать ¦ Энск, 5-е авеню ¦

+----------------------+-----------------+

Рис. 4.8. Объединение двух таблиц.

Декартово произведение - операция, заключающаяся в построении нового отношения на основе двух других путем попарной комбинации всех возможных записей из первого отношения и второго отношения. Если в первом отношении-операнде I записей и m атрибутов, а во втором - J и n соответственно, то в результирующей таблице будет I*J записей и m+n атрибутов. Декартово произведение позволяет связать разные объекты, объединить информацию, описывающую разные типы сущностей или объектов предметной области. Например, если мы имеем отдельную таблицу со списком фирм-производителей, и отдельную таблицу со списком всевозможных товаров, то декартово произведение этих двух таблиц позволит построить всевозможные пары “товар-производитель”:

+----------------------+-----------------+

Таблица “Товары”
-----------T
¦ Товар   ¦
+----------+
¦ рога    ¦
¦ кеды    ¦

L----------+

Результирующая таблица “Товар-производитель”
-----------T--------------------------T-----------------+
¦ Товар   ¦ производитель            ¦ Адрес           ¦
+----------+--------------------------+-----------------+
¦ рога    ¦ АО Рога и Копыта         ¦ Одесса, п/я 13 ¦
¦ кеды    ¦ АО Рога и Копыта         ¦ Одесса, п/я 13 ¦
¦ рога    ¦ ТОО Добро пожаловать     ¦ Энск, 5-е авеню ¦
¦ кеды    ¦ ТОО Добро пожаловать     ¦ Энск, 5-е авеню ¦

L----------+--------------------------+------------------

Рис. 4.9. Декартово произведение двух таблиц.

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

4.4. Нормализация

Зачем нужна нормализация?

Представим себе ведомость на получение зарплаты. В ней содержится информация о всех сотрудниках некоего предприятия. Для каждого сотрудника имеется одна запись. В каждой записи первое поле содержит фамилию сотрудника, второе поле - сколько начислено денег, третье - сколько удержано, четвертое - сколько выдать на руки и т.д.

Если все эти данные собрать в единую таблицу, то есть описать с помощью таблицы людей, работающих на данном предприятии, и сколько каждый из них получал ежемесячно, и в каком отделе он работает и т.д., то получится таблица:

----T--------T--------T--------T--------T--------T-----T---------¬
¦ N ¦Фамилия ¦дата    ¦месяц, ¦месячная¦ дата   ¦отдел¦должность¦
¦   ¦        ¦рожден. ¦год     ¦зарплата¦ приема ¦     ¦         ¦
+---+--------+--------+--------+--------+--------+-----+---------+
¦ 1 ¦ Иванов ¦1.1.1955¦12,1994 ¦ 150000 ¦2.2.1986¦ОНТИ ¦инженер ¦
¦ 2 ¦ Петров ¦3.4.1966¦11.1994 ¦ 280000 ¦4.9.1992¦ВОХР ¦охранник ¦
¦ 3 ¦ Петров ¦3.4.1966¦12,1994 ¦ 350000 ¦4.9.1992¦ВОХР ¦охранник ¦
¦ 4 ¦ Сидоров¦7.1.1968¦12,1994 ¦ 350000 ¦1.7.1989¦ВОХР ¦охранник ¦
¦.. ¦   .... ¦ ....   ¦ ....   ¦ ....   ¦ ....   ¦.... ¦ ....    ¦

L---+--------+--------+--------+--------+--------+-----+----------

Рис. 4.10. Пример ненормализованеной таблицы.

Здесь мы использовали однотабличное представление данных. Строится такая глобальная таблица достаточно просто - берется самый общий объект (сущность), для него выделяются атрибуты и все это организуется в единую таблицу. Например, в нашем примере такой базовой сущностью является описание конкретного человека.

Недостатки такой универсальной таблицы следующие:

- жесткость;

- ненадежность (потенциальная противоречивость);

- повышенный расход ресурсов;

- громоздкость (избыточность).

Под жесткостью понимается обязательная модификация самой таблицы при изменении постановки задачи. Например, если потребовалось хранить количество детей и их возраст, то потребуется модифицировать структуру таблицы,

Причиной остальных недостатков является дублирование данных, повторение той информации, которую повторять не надо.

Если предыдущий пример был несколько надуманным, то схема базы данных из следующего пример может считаться классическим примером плохо нормализованного отношения. Предположим, мы создаем базу данных о поставщиках и товарах. Пусть имеется таблица о поставках товара, для каждого товара указывается производитель в виде названия фирмы и ее адреса:

L----------+--------------------------+------------------

Рис. 4.11. Таблица “Товары”.

Рассмотрим подробно недостатки такой схемы.

Избыточность - слова "АО Рога и Копыта" дублируются, то есть занимают лишнее место в системе хранения. Если размер таблицы большой, то это может привести к значительным дополнительным расходам на память и, следовательно, снизить общую производительность системы.

Потенциальная противоречивость - при попытке изменить адрес фирмы, поставляющей кеды, мы можем забыть изменить этот адрес у этой же фирмы для других изделий, получив в результате два адреса для одной и той же фирмы:

-----------T--------------------------T-----------------¬
¦ рога    ¦ АО Рога и Копыта         ¦ Москва, Бутырка ¦
¦ копыта ¦ АО Рога и Копыта         ¦ Одесса, п/я 13 ¦
¦ кеды    ¦ АО Рога и Копыта         ¦ Одесса, п/я 13 ¦
¦ ......   ¦ ....................     ¦ ............... ¦

L----------+--------------------------+------------------

Рис. 4.12. Последствия неполного обновления данных в ненормализованной таблице.

Этот недостаток опасен с точки зрения поддержания целостности, непротивноречивости данных в базе данных. Такое рассогласование в реальной жизни, случившееся по причине случайной ошибки программиста или оператора может служить причиной неоплаченных поставок, штрафных санкций и т.д.

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

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

В реальной жизни при решении реальных задач одной таблицей обойтись трудно. Например, при решении задачи полной автоматизации предприятия, надо хранить информацию и о стульях, выданных материально ответсвенным, и бюллетенях, и о размере зарплаты. Согласитесь, что собирать всю эту информацию в единую таблицу несколько противоестественно.

Процесс упорядочивания, структурирования представления данных называется нормализацией. Следствием нормализации будет набор таблиц с минимальным дублированием информации, достаточно гибкий и надежно работающий. Более подробно про нормализацию можно почитать в работах [kent, Ульман].

Первая нормальная форма

Отношение находится в первой нормальной форме, если значения атрибутов (то есть домены, из которых построено данное отношение) являются простыми, неделимыми значениями. С программистской точки зрения это означает, что тип данных, приписанный домену может быть целым (integer), символьной строкой фиксированной или переменной длины , логическим (Boolean) и т.д., но не может быть массивом, списком, множеством и т.д. Требование к тому, чтобы все отношения находились в первой нормальной форме является обязательным в том смысле, что СУБД может считаться реляционной только тогда, когда она допускает существование отношений только в первой нормальной форме.

Вторая нормальная форма

Приведение отношения ко второй нормальной форме позволяет убрать зависимость неключевых атрибутов от части ключа. Отношение имеет вторую нормальную форму, если она имеет первую нормальную форму и каждый атрибут отношения, не входящий ни в один ключ (то есть неключевой атрибут), полностью зависит от любого возможного ключа целиком, а не от его подмножества) [Мартин]. Зависимость в этом и следующих определениях означает, что существует функция, по которой зная один атрибут можно определить значение зависимого атрибута. Это может быть арифметическая функция, а может быть просто зависимость, как от ключа.

Если все ключи в отношении состоят только из одного атрибута, то отношение автоматически имеет вторую нормальную форму, так как по любому ключу всегда можно однозначно определить любой неключевой атрибут. Отношение может не находиться во второй нормальной форме только тогда, когда или вообще нет ключей, или существует составной ключ.

Рассмотрим примеры. Как мы уже договорились выше, варианты с отсутствием ключей не представляют практического интереса и рассматриваться не будут. Предположим, мы имеем таблицу “Товары” с описанием товаров и их производителей:

---------T----------------------T-----------------+
¦ Товар ¦ производитель        ¦ Адрес           ¦
+--------+----------------------+-----------------+
¦ рога   ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ копыта ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ кеды   ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ джинсы ¦ ТОО Добро пожаловать ¦ Энск, 5-е авеню ¦
¦ кеды   ¦ ТОО Добро пожаловать ¦ Энск, 5-е авеню ¦
| ...    | ...                  | ...             |

L--------+----------------------+------------------

Рис. 4.13. Таблица “Товары”.

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

Теперь предположим, что фирма может выпускать несколько видов продукции с одним и тем же названием. Но каждый вид продукции данного производителя является интересующим нас объектом предметной области и ему соответствует одна и только одна запись (то есть мы не рассматриваем варианты разной упаковки одного и тогоже товара, сезонных скидок и т.л.). Для идентификации записей о производителе добавим в нашу таблицу атрибут “бар-код”. Каждый товар в этом случае будет идентифицироваться своим бар-кодом. Два разных производителя не могут выпускать товар с одним и тем же бар-кодом (это реальное предположение, так как в бар-код зашивается уникальный номер производителя). В результате получается следующая таблица:

---------T----------T----------------------T-----------------+
¦ Товар ¦ Бар-код ¦ производитель        ¦ Адрес           ¦
+--------+----------+----------------------+-----------------+
¦ рога   ¦ 46131313 ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ копыта ¦ 46131235 ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ кеды   ¦ 01130004 ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ кеды   ¦ 01130006 ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ джинсы ¦ 02010551 ¦ ТОО Добро пожаловать ¦ Энск, 5-е авеню ¦
¦ кеды   ¦ 02010552 | ТОО Добро пожаловать ¦ Энск, 5-е авеню ¦
| ...    | ...      | ...                  | ...             |

L--------+----------+----------------------+------------------

Рис. 4.14. Таблица “Товары”.

В условиях наших предположений (то есть в нашей модели предметной области) в даной таблице есть только один ключ - это атрибут “бар-код”. Все остальные атрибуты являются неключевыми и зависят от него. Таким образом, данное отношение находится во второй нормальной форме, хотя при этом и остаются зависимости между неключевыми атрибутами (адрес по прежнему определяется фирмой-производителем).

Приведение отношения ко второй нормальной форме очень важно. Несоответсвие отношения второй нормальной форме может быть вызвано плохим анализом предметной области, как в нашем примере, когда не была предусмотрена возможность того, что один производитель может поставлять два вида товара с одинаковым названием. В нашем примере удалось привести отношение ко второй нормальной форме введением ключевого атрибута “Бар-код”. В большинстве других случаев более правильным способом приведения отношения ко второй нормальной форме будет расщепление его на два и более отношений. Атрибуты, которые зависят от части ключа должны быть выведены в отдельную таблицу:

Таблица “Товары”
---------T----------------------+
¦ Товар ¦ производитель        ¦
+--------+----------------------+
¦ рога   ¦ АО Рога и Копыта     ¦
¦ копыта ¦ АО Рога и Копыта     ¦
¦ кеды   ¦ АО Рога и Копыта     ¦
¦ джинсы ¦ ТОО Добро пожаловать ¦
¦ кеды   ¦ ТОО Добро пожаловать ¦
| ...    | ...                  |

L--------+----------------------+

Таблица “Адреса_производителей”
+----------------------T-----------------+
¦ Производитель ¦ Адрес ¦
+----------------------+-----------------+
¦ АО Рога и Копыта ¦ Одесса, п/я 13 ¦
¦ ТОО Добро пожаловать ¦ Энск, 5-е авеню ¦

+----------------------+-----------------+

Рис. 4.15. Приведение таблицы “Товары” во вторую нормальную форму.

Выделение отдельной таблицы для хранения адресов производителей (а, в более общем случае, для хранения любых атрибутов, специфичных для конкретной фирмы) позволит избежать аномалий вставки и удаления, повысить надежность системы и снизить затраты на хранение данных. А именно:

·	можно хранить информацию о фирме, которая в данный момент ничего для нас не производит, но собирается начать это делать;

·	удаление всех записей о товарах, производимых некоторой фирмой, не приведет к автоматической потери всей информации о данной фирме;

·	при изменении адреса у фирмы это потребуется сделать только в одном месте, если бы мы не разделили отношение на два, то такое изменение потребовалось бы сделать для каждой записи о товаре. Это повышает надежность системы и повышает скорость обработки подобных запросов;

·	адрес для каждой фирмы хранится в одном месте, дублирование же этой информации приводит к неоправданному расходу памяти.

Третья нормальная форма

Третья нормальная форма исключает транзитивную зависимость. Отношение находится в третьей нормальной форме, если оно имеет вторую нормальную форму и каждый неключевой атрибут нетранзитивно зависит от от любого ключа в данном отношении [Мартин]. Другими словами, неключевые атрибуты должны зависеть только от ключей. Например, если мы идентифицируем товары по бар-коду, и имеем следующую таблицу, находящуюся во второй нормальной форме и не находящуюся в третьей:

Преимущества, которые дает приведение отношения к третьей нормальной форме аналогичны тем, что дает и приведение ко второй нормальной форме.

---------T----------T ----------------------T-----------------+
¦ Товар ¦ Бар-код ¦ производитель        ¦ Адрес           ¦
+--------+----------+----------------------+-----------------+
¦ рога   ¦ 46131313 ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ копыта ¦ 46131235 ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ кеды   ¦ 01130004 ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ кеды   ¦ 01130006 ¦ АО Рога и Копыта     ¦ Одесса, п/я 13 ¦
¦ джинсы ¦ 02010551 ¦ ТОО Добро пожаловать ¦ Энск, 5-е авеню ¦
¦ кеды   ¦ 02010552 | ТОО Добро пожаловать ¦ Энск, 5-е авеню ¦
| ...    | ...      | ...                  | ...             |

L--------+----------+----------------------+------------------

Рис. 4.16. Другой вариант таблицы “Товары”.

Данное отношение не находится в третьей нормальной форме, так как адрес фирмы однозначно зависит от ее названия, а название (поле “производитель”) не являются ни ключом, ни частью ключа в данном отношении. Для того, чтобы привести данное отношение в третью нормальную форму, нужно разбить это отношение на два - убрать из данного отношения атрибут “Адрес” и завести новое отношение “Адреса фирмпроизводителей”.

Приведение отношения к третьей нормальной форме в большинстве случаев оказывается достаточным, чтобы избежать проблем, возникающих с ненормализованными отношениями. Методика нормализации будет рассмотрена ниже, здесь же рассмотрим следующие нормальные формы, используемые на практике существенно реже, чем третья, но от этого не менее интересные.

Нормальная форма Бойса-Кодда

Отношение находится в нормальной форме Бойса-Кодда, если оно находится в третьей нормальной форме, и существует некоторый неключевый атрибут A, который зависит от набора атрибутов X, и при этом X не включает A, то X должен обязательно включать некоторый ключ. Другими словами, если в таблице есть какие-то зависимые неключевые атрибуты, то они должны обязательно зависеть от ключа.

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

+--------+----------------------+--------+
¦ Город ¦ Улица                ¦ Индекс ¦
+--------+----------------------+--------+
¦ Москва ¦ Профсоюзная          ¦ 116321 ¦
¦ Москва ¦ Островитянова        ¦ 116321 ¦
¦ Москва ¦ Академическая        ¦ 117303 ¦
¦ Дмитров¦ Профсоюзная          ¦ 157400 ¦
¦ Клин   ¦ Профсоюзная          ¦ 190005 ¦
¦ Клин   ¦ Абрикосовая          ¦ 190006 ¦
| ...    | ...                  | ...    |

L--------+----------------------+--------+

Рис. 4.17. Таблицы “Почтовые индексы”.

Следовательно, данная таблица не находится в нормальной форме Бойса-Кодда.

Приведение таблицы к нормальной форме Бойса-Кодда позволяет устранить проблемы, которые не устраняет третья нормальная форма. Тем не менее, в нашем примере с индексами данная схема отношения приемлима для большинства приложений и, скорее всего, в данном случае, особых проблем не возникнет. В других случаях, когда отношение не находится в нормальной форме Бойса-Кодда имеет смысл проанализировать это отношение более тщательно.

Четвертая нормальная форма

В отличии от нормальных форм, рассмотренных выше, четвертая нормальная форма определяет требования к отношению не только на уровне зависимостей между атрибутами, но и на уровне зависимостей между разными записями внутри одного отношения.

Дадим определение многозначной зависимости, используемой при определении четвертой нормальной формы. В отношении R существует многозначная зависимость между набором атрибутов X и Y (Y многозначно зависит от X), если для любых двух записей r1 и r2, таких что они совпадают на множестве атрибутов X , то есть r1[X]=r2[X], всегда существует запись r3 такая, что

1.	r3 совпадает на множестве атрибутов X с записями r1 и r2, то есть r1[X]=r2[X]=r3[X],

2.	на множестве атрибутов Y запись r3 совпадает с r1, то есть r1[Y]=r3[Y],

3.	на множестве атрибутов, не входящих ни в X, ни в Y , запись r3 совпадает с r2, то есть r2[R-(X+Y)]=r3[R-(X+Y)].

Если попытатьться перефразировать это определение, то можно пояснить его смысл следующим образом: Если существует запись [x, y1, z1] и запись [x, y2, z2], то должна существовать запись [x, y1, z2] и (в силу симметричности определения) запись [x, y2, z1]. Многозначные зависимости проявляются при логическом группировании некоторых атрибутов, и их симметричном вхождении в отношении. Например, рассмотрим таблицу, в которой хранится информация о семинарах, проводимых в некотором Университете. Данная таблица может иметь следующие атрибуты:

+---------------+----------+-----------+--------+--------+
¦ Преподаватель ¦ Студент ¦ Аудитория | Время ¦ День   ¦
+---------------+----------+-----------+--------+--------+
¦ Бякин         ¦ Петров   ¦ 711       | 9:00 ¦ Понед ¦
¦ Бякин         ¦ Иванова ¦ 745       | 10:50 ¦ Понед ¦
| ...           | ...      | ...       | ...    | ...   ¦

L---------------+----------+-----------+--------+--------+

Рис. 4.18. Таблица “Семинары”.

Если предположить, что студенты Петров и Иванова учатся в одной группе, то, следовательно, они ходят на одни и те же занятия (болезни и прогулы для простоты не рассматриваются). Следовательно, в данной таблице должны быть и следующие записи:

7+---------------+----------+-----------+--------+--------+
¦ Преподаватель ¦ Студент ¦ Аудитория | Время ¦ День   ¦
+---------------+----------+-----------+--------+--------+
¦ Бякин         ¦ Петров   ¦ 711       | 9:00 ¦ Понед ¦
¦ Бякин         ¦ Иванова ¦ 745       | 10:50 ¦ Понед ¦
¦ Бякин         ¦ Петров   ¦ 745       | 10:50 ¦ Понед ¦
¦ Бякин         ¦ Иванова ¦ 711       | 9:50 ¦ Понед ¦
| ...           | ...      | ...       | ...    | ...   ¦

L---------------+----------+-----------+--------+--------+

Рис. 4.19. Таблица “Семинары” в случае отсутствия 4-й нормальной формы.

В этом случае атрибут “Студент” функционально зависит от атрибута “Преподаватель”.

Так вот, отношение R находится в четвертой нормальной форме, если оно находится в третьей нормальной форме, и существует набор атрибутов Y, который функционально зависит от Х, при этом Y не пусто, Y не является подмножеством и в R есть атрибуты, не входящие ни в Х, ни в Y, то Х должен содержать какой-либо ключ.

Если отношение не находится в четвертой нормальной форме, то обычно это означает, что при рассмотрении предметной области, при отображении ее в схему базы данных, были пропущены какие-то классы объектов или сущностей, которые стоило бы выделить в отдельные отношения. Например, в нашем примере с семинарами напрашивается введение отношения “Группы”, в котором будут перечислены студенты и для каждого студента будет указан номер группы. А преподаватель теперь будет проводить семинары не для студентов, а для группы.

Методика нормализации

Нормализация схемы базы данных призвана упорядочить схему, сделать ее более надежной и удобной в работе. То есть нормализация не должна рассматриваться как самоцель. Существуют специальные методики разбиения таблиц на две таблицы с целью приведения их к нормальным формам [Мартин, Мейер]. Здесь же мы рассмотрим несколько иной подход, а именно как изначально проектировать “правильную” схему базы данных так, что потребность в нормализации была минимальной.

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

·	Факт поставки (товар, кто поставил, когда поставил, контракт, условия поставки)

·	Товар (производитель, название)

·	Контракт (кто подписал, что предусматривает, срок действия)

·	Поставщик товара (название, адрес)

·	Производитель товара (название, адрес)

Следующий шаг в построениии схемы базы данных должен заключаться в поиске ключей. Атрибуты, входящие в ключ, должны быть тщательно проанализированы на тот факт, что они действительно всегда однозначно будут идентифицировать реальный объект или сущность. В противном случае, имеет смысл ввести искусственный ключ. Более того, хорошим тоном может считаться обязательное введение искуственного ключа и использование его в качестве первичного для всех (или почти всех) таблиц в базе данных.

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

адрес character)

После того, как схема базы данных таким образом формализована, нужно еще раз внимательно ее проанализирповать на предмет зависимостей и неточностей. Для упрощения этого анализа следует рассмотреть те действия, которые будут совершаться с информацией в базе данных. В нашем случае к таким действиям можно отнести занесение информации о контракте, занесение факта поставки, поиск фирмы, поставившей или сделавшей тот или иной товар и т.д. В частности, в нашей схеме есть один спорный момент и одна неточность.

Спорный момент в нашей схеме базы данных заключается в том, что контракт обычно содержит информацию о фирме, которая будет поставлять тот или иной товар. Поэтому, возможно, информацию об этой фирме не надо хранить в описании фактов поставок, а надо хранить в описаниях контрактов. С другой стороны, когда мы заключаем с какой-то фирмой договор о поставке, нас может не интересовать, каким образом она поставит нам этот товар. Возможно, она найдет субподрядчика и организует эту поставку через другую фирму. Если это так, или такие случаи возможны в будущем, то ссылку на поставку стоит оставить в описании фактов поставок.

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

адрес character)

Общие правила нормализации

Подводя итоги описания методики нормализации, можно выделить следующие правила “хорошего тона”:

1.	Помни про нормальные формы.

2.	Схема должна соответсвовать реальной предметной области

3.	Атрибуты должны зависеть от ключа, от всего ключа целиком и ни от чего другого, кроме ключа [П.Грей]

4.	Чем меньше зависимостей внутри таблицы, тем лучше.

5.	Естественные ключи на поверку редко оказываются ключами.

При разработке схемы базы данных важно учитывать и мировой опыт в смежных областях, а именно, помнить про следующие правила:

1.	Не надо плодить сущностей сверх меры [К.Прутков]

2.	Семь раз отмерь, один раз отрежь (семь раз подумай, один раз создай таблицу).

3.	Первый блин комом (первая схема редко бывает удачной).

Грачев А.Ю. Введение в СУБД Informix