Генералова - БД (стр. 4 )

Какие товары продает фирма, какова их цена, описание, и т. д. По выбранным товарам оформляются заказы. Кто (покупатели), когда и совершили заказ и какова общая сумма заказа?

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

Рис 1. Начальная схема отношений

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

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

Как нам известно, в теории реляционных баз данных существует пять нормальных форм [2]:

первая нормальная форма (1 NF); вторая нормальная форма (2 NF); третья нормальная форма (3 NF); четвертая нормальная форма (4 NF); пятая нормальная форма (5 NF).

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

Процесс проектирования.

1-ый шаг: 1 NF → 2 NF

Из схемы организации работы фирмы на рис. 1 определим схему отношений:

ТОВАРЫ-ЗАКАЗЫ

ТОВАРЫ {товарНом, товарНазв, товарОпис, товарРис, товарЦена, колНаСкладе, типНом, типНазв}

ЗАКАЗЫ {заказНом, заказДата, ПокупНом, ФИОПокуп, ЭлпочтаПокуп, адресПокуп, товарНом, количТовЗаказа, видДост, ценаДост, налогНДС, общСумма, заказСост}

В атрибутах «типНом» и «типНазв» содержится информация о типах товаров, например, название типа — Процессоры (типНом = 1), к которому относятся конкретные товары - Intel 386, Intel 486, AMD, и т. д. Атрибут «колНаСкладе» содержит общее количество товаров с данным номером на складе.

В одном заказе может заказываться несколько товаров с разными номерами. Атрибут «количТовЗаказа» содержит количество товаров данного типа, заказанных в данном заказе.

В атрибутах «ПокупНом», «ФИОПокуп», «ЭлпочтаПокуп», «адресПокуп» содержится информация о покупателе — номер, ФИО, Электронная почта и адрес.

В атрибутах «видДост», «ценаДост» хранится информация о доставке — номер, вид и цена доставки. Атрибут «заказСост» содержит состояние заказа, который может быть иметь значение «Сделка совершена» либо «Сделка выполнена неполно».

Для вычисления общей суммы заказа применяем формулу

общСумма = ТоварЦена*количТов + налогНДС + ценаДост.

На 1-м шаге проектирования форма 1NF приводится к виду 2NF. Для этого проверяем следующее определение:

Отношение R находится в второй нормальной форме (2NF) в том и только в том случае, когда находится в 1NF, и каждый неключевой атрибут полностью зависит от первичного ключа.

Рассмотрим отношение ЗАКАЗЫ. В этом отношении существует неполная функциональная зависимость от первичного ключа, поскольку все атрибуты, кроме товарНом и количТовЗаказа, зависят от ЗаказНом, а первичным ключом является заказНом, товарНом. И поэтому мы приводим отношение ко второй нормальной форме то есть, производим декомпозицию отношения ЗАКАЗЫ в два отношения ТИП ЗАКАЗА и ЗАКАЗЫ:

ТИП ЗАКАЗА {заказНом, товарНом, количТовЗаказа}

Первичный ключ:
заказНом, товарНом
Функциональные зависимости:
заказНом, товарНом → количТовЗаказа

ЗАКАЗЫ {заказНом, заказДата, ФИОПокуп, ЭлпочтаПокуп, адресПокуп, видДост, ценаДост, налогНДС, общСумма, заказСост}

Первичный ключ:
заказНом
Функциональные зависимости:
заказНом → заказДата
заказНом → ФИОПокуп
заказНом → ЭлпочтаПокуп
заказНом → адресПокуп
заказНом → видДост
заказНом → ценаДост
заказНом → налогНДС
заказНом → общСумма
заказНом → заказСост

Рассмотрим отношение ТОВАРЫ. В этом отношении первичным ключом является атрибут «товарНом», и оно уже находится во второй нормальной форме.

ТОВАРЫ {товарНом, типНом, товарНазв, товарОпис, товарЦена, товарРис, типНазв, колНаскладе}

Первичный ключ:
товарНом
Функциональные зависимости:
товарНом → типНом
товарНазв
товарНом → товарОпис
товарНом → товарЦена
товарНом → товарРис
товарНом → колНаСкладе
типНом → типНазв

Рис. 2. Схема отношений в виде 1NF

2-ой шаг: 2 NF → 3 NF

На 2-м шаге проектирования форма 2NF приводится к виду 3NF. Для этого проверяется следующее определение:

Отношение R находится в третьей нормальной форме (3NF) в том и только в том случае, когда находится в 2NF, и каждый неключевой атрибут нетранзитивно зависит от первичного ключа.

При проверке на транзитивность определяется существования зависимостей R. X → R. Z и R. Z → R. Y и отсутствие зависимости R. Z → R. X. То есть при отсутствии последнего требования мы имели бы «неинтересные транзитивные зависимости» в любом отношении, обладающем несколькими ключами.

Имея в виду выше рассмотренные ФЗ отношения ТОВАРЫ, где атрибут типНазв напрямую не зависит от первичного ключа товарНом, а непосредственно зависит от его составного атрибута типНом, мы заключаем, что здесь имеется транзитивная ФЗ товарНом → типНом → типНазв. Другими словами, название типа товара на самом деле является характеристикой не товара, а типа товара, к которому он относится. В результате сказанного, мы приводим отношение Товары к третьей нормальной форме.

Теперь можно произвести декомпозицию отношения ТОВАРЫ в два отношения ТИП ТОВАРА и ТОВАРЫ:

ТИП ТОВАРА {типНом, типНазв}

Первичный ключ:
типНом
Функциональные зависимости:
типНом → типНазв

ТОВАРЫ {товарНом, тип_Ном, товарНазв, товарОпис, товарЦена, товарРис, колНаСкладе}

Первичный ключ:
товарНом
Функциональные зависимости:
товарНом → типНом
товарНазв
товарНом → товарОпис
товарНом → товарЦена
товарНом → товарРис
товарНом → колНаСкладе

В результате из одного отношения (таблицы) ТОВАРЫ получается два отношения (две таблицы) ТИП ТОВАРА и ТОВАРЫ.

Отношение ТОВАРЫ разделяется на отношения — ТИП ТОВАРА и ТОВАРЫ, где ТИП ТОВАРА — основная таблица, а ТОВАРЫ — подчиненная таблица.

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

Рис 3. Схема отношений в виде 3NF

Техническое решение

Приложение базы данных было выполнена в среде Access 2003. Определив все взаимосвязи между отношениями, получим окончательную схему данных (структуру данных):

Рис 4. Схема данных БД

Из схемы видно, что между отношениями существуют связи:

«Тип товара» и «Товары» имеют связь 1:∞ «Товары» и «Тип заказа» имеют связь 1:∞ «Тип заказа» и «Заказы» имеют связь 1:∞

Типы данных для каждого отношения приведены в следующих таблицах:

а) для отношения «Тип товара» б) для отношения «Товары»

в) для отношения «Типы заказа» г) для отношения «Заказы»

Функциональные зависимости отношений и математическое понятие функциональной зависимости

Функциональная зависимость атрибутов отношения напоминает понятие функциональной зависимости в математике. Но это не одно и то же. Для сравнения напомним математическое понятие функциональной зависимости:

Определение 2. Функциональная зависимость (функция) - это тройка объектов , где

- множество (область определения),

- множество (множество значений),

- правило, согласно которому каждому элементу ставится в соответствие один и только один элемент (правило функциональной зависимости).

Функциональная зависимость обычно обозначается как или .

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

Функциональная зависимость атрибутов отношения тоже напоминает это определение. Действительно:

  В качестве области определения выступает домен, на котором определен атрибут (или декартово произведение доменов, если является множеством атрибутов)

  В качестве множества значений выступает домен, на котором определен атрибут (или декартово произведение доменов)

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

Отличие от математического понятия отношения состоит в том, что, если рассматривать математическое понятие функции, то для фиксированного значения соответствующее значение функции всегда одно и то же. Например, если задана функция , то для значения соответствующее значение всегда будет равно 4. В противоположность этому в отношениях значение зависимого атрибута может принимать различные значения в различных состояниях базы данных. Например, атрибут ФАМ функционально зависит от атрибута Н_СОТР. Предположим, что сейчас сотрудник с табельным номером 1 имеет фамилию Иванов, т. е. при значении детерминанта равного 1, значение зависимого аргумента равно "Иванов". Но сотрудник может сменить фамилию, например на "Сидоров". Теперь при том же значении детерминанта, равного 1, значение зависимого аргумента равно "Сидоров".

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

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

Определение 1. Функциональная зависимость

В отношении R атрибут Y функционально зависит от атрибута X (X и Y могут быть составными) в том и только в том случае, если каждому значению X соответствует в точности одно значение Y: R. X (r) R. Y.

Определение 2. Полная функциональная зависимость

Функциональная зависимость R. X (r) R. Y называется полной, если атрибут Y не зависит функционально от любого точного подмножества X.

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

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

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

«Первичный ключ (primary key) – это ключ, который может быть выбран АБД (администратором базы данных) для представления таблицы. В оригинальной реляционной модели Кодда таблица должна иметь первичный ключ. Однако большинство теоретиков реляционной модели признают факт, что ключ есть ключ, и логически здесь нет ничего особенного относительно первичного ключа.

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

Вторичный ключ (secondary key) или ключ-кандидат (candidate key) – комбинация столбцов, отличная от комбинации, составляющей первичный ключ. Эти ключи могут сопровождаться уникальными (UNIQUE) и не пустыми (NOT NULL) ограничениями в SQL. Существует различие в SQL между уникальным ограничением (UNIQUE) и ограничением первичного ключа. Ограничение первичного ключа всегда NOT NULL у всех его столбцов, в то время как ограничение UNIQUE позволяет одно и только одно значение NULL в каждом столбце, если не наложено иного ограничения.

Простой ключ (simple key) – ключ, содержащий только один атрибут. В идеале мы бы хотели самый короткий и самый простой из возможных типов данных, чтобы операции объединения (JOIN) производились быстрее. С этой точки зрения нам больше всего подходит тип INTEGER или другой числовой тип данных, который имеет аппаратную поддержку для операций над ним и сравнений.

Сложный (compound) или составной ключ (composite key) – ключ, состоящий более чем из одного атрибута.

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

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

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

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

(рефлексивность) Если , то логически следует из . Данное правило позволяет выводить все тривиальные функциональные зависимости, т. е. зависимосте где правая часть является подмножеством левой. Использование этого правила не зависит от . (пополнение) Если и , то логически следует из (принадлежит ). (транзитивность) Если и , то .

Из указанных аксиом вытекает важное следствие. Если , то функциональная зависимость () справедлива тогда и только тогда, когда справедлива каждая функциональная зависимость ().

Подход к решению проблемы поиска замыкания S+ множества FD S впервые предложил Вильям Армстронг1). Им был предложен набор правил вывода новых FD из существующих (эти правила обычно называют аксиомами Армстронга, хотя справедливость правил доказывается на основе определения FD). Обычно принято формулировать эти правила вывода в следующей форме. Пусть A, B и C являются (в общем случае, составными) атрибутами отношения r. Множества A, B и C могут иметь непустое пересечение. Для краткости будем обозначать через AB A UNION B. Тогда:

если BA, то AB (рефлексивность); если AB, то ACBC (пополнение); если AB и BC, то AC (транзитивность).

Истинность первой аксиомы Армстронга следует из того, что при BA FD AB является тривиальной.

Справедливость второй аксиомы докажем от противного. Предположим, что FD ACBC не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t1 и t2, такие, что t1 {AC} = t2 {AC} (a), но t1 {BC} t2 {BC} (b) (здесь t {A} обозначает проекцию кортежа t на множество атрибутов A). По аксиоме рефлексивности из равенства (a) следует, что t1 {A} = t2 {A}. Поскольку имеется FD AB, должно соблюдаться равенство t1 {B} = t2 {B}. Тогда из неравенства (b) следует, что t1 {C} t2 {C}, что противоречит наличию тривиальной FD ACC. Следовательно, предположение об отсутствии FD ACBC не является верным, и справедливость второй аксиомы доказана.

Аналогично докажем истинность третьей аксиомы Армстронга. Предположим, что FD AC не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t1 и t2, такие, что t1 {A} = t2 {A}, но t1 {C} t2 {C}. Но из наличия FD AB следует, что t1 {B} = t2 {B}, а потому из наличия FD BC следует, что t1 {C} = t2 {C}. Следовательно, предположение об отсутствии FD AC не является верным, и справедливость третьей аксиомы доказана.

Можно доказать, что система правил вывода Армстронга полна и совершенна (sound and complete) в том смысле, что для данного множества FD S любая FD, потенциально выводимая из S, может быть выведена на основе аксиом Армстронга, и применение этих аксиом не может привести к выводу лишней FD. Тем не менее Дейт по практическим соображениям предложил расширить базовый набор правил вывода еще пятью правилами:

AA (самодетерминированность) – прямо следует из правила (1); если ABC, то AB и AC (декомпозиция) – из правила (1) следует, что BCB; по правилу (3) AB; аналогично, из BCС и правила (3) следует AC; если AB и AC, то ABC (объединение) – из правила (2) следует, что AAB и ABBC; из правила (3) следует, что ABC; если AB и CD, то ACBD (композиция) – из правила (2) следует, что AСBС и BCBD; из правила (3) следует, что ACBD; если ABC и BD, то ABCD (накопление) – из правила (2) следует, что BСBCD; из правила (3) следует, что ABCD.

Пусть заданы отношение r, множество Z атрибутов этого отношения (подмножество заголовка r, или составной атрибут r) и некоторое множество FD S, выполняемых для r. Тогда замыканием Z над S называется наибольшее множество Z+ таких атрибутов Y отношения r, что FD ZY входит в S+.

Алгоритм вычисления Z+ очень прост. Один из его вариантов показан на рис. 6.2.

Рис. 6.2.  Алгоритм построения замыкания атрибутов над заданным множеством FD

Докажем корректность алгоритма по индукции. На нулевом шаге Z[0] = Z, FD ZZ[I], очевидно, принадлежит S+ (тривиальная FD "выводится" из любого множества FD). Пусть для некоторого K выполняется FD ZZ[K], и пусть мы нашли в S такую FD AB, что AZ[K]. Тогда можно представить Z[K] в виде AC, и, следовательно, выполняется FD ZAC. Но по правилу (8) мы имеем FD ZACB, т. е. FD Z(Z[K] UNION B) входит во множество S+, что переводит нас на следующий шаг индукции.

Пусть для примера имеется отношение с заголовком {A, B, C, D, E, F} и заданным множеством FD S = {AD, ABE, BFE, CDF, EC}. Пусть требуется найти {AE}+ над S. На первом проходе тела цикла DO Z[1] равно AE. В теле цикла FOR EACH будут найдены FD AD и EC, и в конце цикла Z[1] станет равным ACDE. На втором проходе тела цикла DO при Z[2], равном ACDE, в теле цикла FOR EACH будет найдена FD CDF, и в конце цикла Z[2] станет равным ACDEF. Следующий проход тела цикла DO не изменит Z[3], и Z+ ({AE}+) будет равно ACDEF.