Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Контрольная работа

Проектирование реляционных баз данных

• Нормализация отношений
• Функциональные зависимости
• Нормальная форма Бойса-Кодда
• Литература

Проектирование реляционных баз данных

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

В процессе проектирования баз данных могут возникнуть следующие проблемы:

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

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

Аномалии удаления - обратная проблема может возникнуть при удалении некоторых данных (возможна потеря полезной информации).

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

Первые три проблемы разрешаются в процессе нормализации отношений.

реляционная база функциональная зависимость

Нормализация отношений

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

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

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

Теперь в дополнение к 1НФ можно определить дальнейшие уровни нормализации - вторую нормальную форму (2НФ), третью нормальную форму (3НФ) и т.д. Считается, что таблица находится во 2НФ, если она находится в 1НФ и удовлетворяет, кроме того, некоторому дополнительному условию, суть которого будет рассмотрена ниже. Таблица находится в 3НФ, если она находится в 2НФ и, помимо этого, удовлетворяет другому дополнительному условию и т.д.

Таким образом, каждая нормальная форма является в некотором смысле более ограниченной, но и более желательной, чем предшествующая. Это связано с тем, что (n+1) - я нормальная форма не обладает некоторыми непривлекательными особенностями, свойственными n-й нормальной форме. Общий смысл дополнительного условия, налагаемого на (n+1) - ю нормальную форму по отношению к n-й нормальной форме, состоит в исключении этих непривлекательных особенностей.

Процедура нормализации отношений обратима. Например, множество отношений, находящихся в 3НФ, можно преобразовать в отношения, находящиеся в 2НФ. Это очень важное свойство нормализации означает, что в процессе нормализации информация не утрачивается.

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

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

Пусть X и Y - произвольные подмножества множества атрибутов отношения R. Y функционально зависит от X тогда и только тогда, когда каждое значение множества X связано в точности с одним значением множества Y. Обозначение: XY (читается как "X функционально определяет Y"). Левая и правая части символической записи называются детерминантом и зависимой частью соответственно.

Рис. 1. Таблица поставок ПОС

Иначе говоря, если два кортежа отношения R совпадают по значению X, то они также совпадают и по значению Y. Для пояснения рассмотрим приведенную на рис. 1 несколько измененную версию таблицы поставок, изображенной на рис. 2.

Все кортежи отношения ПОС с одинаковым значением атрибута П№ имеют одинаковые значения атрибута Гор. Значит, атрибуты Гор функционально зависят от атрибутов П№: {П№}{Гор}. Более того, в этом отношении присутствуют и другие постоянные функциональные зависимости: {П№, Д№}{Кол}, {П№, Д№}{Гор}, {П№, Д№}{Гор, Кол}, {П№, Д№}{П№}, {П№, Д№}{П№, Д№, Гор, Кол}, а также зависимости, которые являются функциональными в любой данный момент, но не все время, например, {П№}{Кол}.

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

Функциональные зависимости являются ограничениями целостности, поэтому при каждом обновлении базы данных они должны быть проверены. Очевидным способом сокращения множества функциональных зависимостей является исключение тривиальных зависимостей , т.е. таких, которые не могут не выполняться. Например, {П№, Д№}{П№}. Функциональная зависимость является тривиальной тогда и только тогда, когда правая часть символьной записи является подмножеством левой части. Такие зависимости не представляют никакого интереса с практической точки зрения.

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

Функциональные зависимости могут быть изображены при помощи диаграмм. Для базы данных поставщиков и деталей (рис.1) диаграмма функциональных зависимостей изображена на рис.2.

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

Нормальные формы, обоснованные функциональными зависимостями

Мы упоминали о первой нормальной форме (1НФ). Приведем более строгое ее определение, а также определения других нормальных форм.

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

Например, этим требованиям не удовлетворяет таблица, изображенная на рис.3 (данные в поле Д№ не атомарные):

Рис. 3. Пример таблицы, которая не является реляционным отношением

Такие таблицы даже не рассматриваются в реляционных моделях.

Если мы разрабатываем реляционную базу данных, то на первом этапе может быть создана таблица, объединяющая все рассматриваемые данные, например, Поставщики, Детали, Поставки. Таблица на рис.3 представляет собой корректное реляционное отношение. Его называют универсальным отношением проектируемой базы данных. В одно универсальное отношение включаются все представляющие интерес атрибуты и оно может содержать все данные, которые предполагается размещать в базе данных в будущем. Для малых баз данных универсальное отношение может использоваться в качестве отправной точки при их проектировании. Первичным ключом таблицы является комбинация полей П№ и Д№. Эта таблица удовлетворяет всем требованиям 1НФ.

Рис. 4. Отношение в первой нормальной форме

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

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

Вставка (Insert). Нельзя вставить данные о поставщике (П5), не указав деталь (Null-значение в ключевом поле недопустимо).

Удаление (Delete). При удалении некоторого кортежа приходится удалять слишком много другой информации (удаление информации о поставке удаляет информацию о поставщике).

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

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

Таблица находится во второй нормальной форме (2НФ), если она удовлетворяет определению 1НФ и все ее поля, не входящие в первичный ключ, связаны неприводимой зависимостью с первичным ключом (или находятся в полной функциональной зависимости с первичным ключом).

Функциональные зависимости отношений нашей базы данных, приведенных ко 2НФ, показаны на рис. 4, а соответствующие таблицы - на рис. 5.

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

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

Рис. 7. Отношения в 2НФ

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

Вставка - нельзя включить данные о некотором городе и его статусе, пока в нем нет поставщика.

Удаление - при удалении поставщика теряется информация о статусе города (очевидно, что причиной такой проблемы является совместная информация - в таблице содержится информация и о поставщиках, и о городе).

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

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

Эта процедура исключает транзитивную зависимость и разрешает все трудности.

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

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

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

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

А: (П№, Город) и (Город, Статус) (так было предложено ранее) и В: (П№, Город) и (П№, Статус)

Третий вариант декомпозиции на проекции (П№, Статус) и (Город, Статус) не может быть применен, поскольку выполняется с потерей информации - несколько городов могут иметь одинаковый статус, тогда будет потеряна информация о городе, где находится поставщик.

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

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

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

Каждая функциональная зависимость в отношении R является логическим следствием функциональных зависимостей в проекциях R1 и R2;

Общие атрибуты проекций R1 и R2 образуют потенциальный ключ, по крайней мере, для одной из них.

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

Идея нормализации с декомпозицией на независимые проекции предложена Риссаненом (Rissanen) и называется декомпозицией с сохранением зависимости .

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

До сих пор мы предполагали для простоты, что каждое отношение имеет только один потенциальный ключ - первичный ключ. Данное выше определение 3НФ не совсем подходит, если

- отношение имеет два или более потенциальных ключа;

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

Поэтому определение 3НФ было дополнено нормальной формой Бойса-Кодда (Boyce-Codd) - НФБК . Его можно сформулировать так:

Отношение находится в нормальной форме Бойса-Кодда тогда и только тогда, когда детерминанты являются потенциальными ключами .

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

Комбинация таких условий не часто встречается на практике, поэтому для отношений без таких условий 3НФ и НФБК эквиваленты.

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

Рассмотрим пример, включающий два неперекрывающихся потенциальных ключа:

Поставщик (П№, Имя_П, Статус, Город),

где атрибуты П№ и Имя_П являются потенциальными ключами, а атрибуты Статус и Город совершенно независимы. Диаграмма функциональных зависимостей изображена на рис. 8. Это отношение находится в НФБК. Здесь все детерминанты являются потенциальными ключами, а все стрелки начинаются с потенциальных ключей.

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

Первый пример: Отношение Поставки (П№, Имя_П, Д№, Кол-во).

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

Поставщик (П№, Имя_П) и Поставки 1 (П№, Д№, Кол-во).

Второй пример: Отношение СДП (С, Д, П),

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

- Каждый студент изучает данный предмет у одного преподавателя;

- Каждый преподаватель ведет только один предмет (но каждый предмет может преподаваться несколькими преподавателями).

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

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

Нормальные формы, обоснованные более сложными зависимостями

Рис. 10. Ненормализованное отношение ДПУ

В следующих нормальных формах (4НФ и 5НФ) учитываются не только функциональные, но и многозначные зависимости и зависимости соединения между атрибутами отношения. Для знакомства с ними рассмотрим ненормализованное отношение, показанное на рис.10. Каждый кортеж отношения содержит название дисциплины, группу имен преподавателей, и набор учебников. Это значит, что каждый курс может преподаваться любым преподавателем с использованием любых учебников. Преобразуем это отношение в эквивалентное нормализованное. Для представленных данных функциональные зависимости не определены. Поэтому нет формальной основы для декомпозиции этого отношения и нормализованное отношение изображено на рис. 11.

Рис. 11. Нормализованное отношение ДПУ

Рис. 12. Проекции {Д,П} и {Д,У} отношения ДПУ

Очевидно, что отношение ДПУ характеризуется значительной избыточностью и приводит к возникновению аномалий обновления, например, при добавлении нового преподавателя надо вводить по кортежу на каждый учебник. Тем не менее, отношение является полностью ключевым и поэтому находится в НФБК. Возникающие проблемы вызваны тем, что преподаватели и учебники полностью независимы друг от друга. Проблема нормализованного отношения ДПУ не возникла бы, если бы первоначально были разделены все независимые повторяющиеся группы. В нашем случае можно было улучшить ситуацию, заменив отношение ДПУ проекциями {Д, П} и {Д, У} (рис.12). При этом обе проекции являются полностью ключевыми и находятся в НФБК, а их соединение дает исходную таблицу, то есть, декомпозиция выполнена без потерь. Такая декомпозиция не может быть выполнена на основе функциональных зависимостей, которых нет в этом примере. Ее можно осуществить на основе многозначной зависимости. Многозначные зависимости - это обобщение функциональных зависимостей в том смысле, что каждая функциональная зависимость является многозначной, у которой зависимая часть является одноэлементным множеством.

В отношении ДПУ есть две многозначные зависимости: ДП и ДУ.

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

Вторая многозначная зависимость интерпретируется аналогично.

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

Очевидно, что многозначная зависимость АВ выполняется только тогда, когда выполняется многозначная зависимость АС. Многозначные зависимости всегда образуют связанные пары: AB||C.

Возвращаясь к проблемам отношения ДПУ, можно сказать, что они связаны с существованием многозначных зависимостей, которые не являются функциональными (именно наличие таких зависимостей требует вставлять два кортежа, когда надо добавить данные еще об одном преподавателе физики). Проекции {Д, П} и {Д, У} не содержат многозначных зависимостей и поэтому являются более желательными. Прежде чем дать определение четвертой нормальной формы, познакомимся с теоремой Фейгина (R. Fagin):

Пусть А, В, С являются множествами атрибутов отношения R{А, В, С}. Отношение R будет равно соединению его проекций {А, В} и {А, С} тогда и только тогда, когда для отношения R выполняются многозначные зависимости АВ и АС.

Отношение R находится в четвертой нормальной форме (4НФ ) тогда и только тогда, когда в случае существования многозначной зависимости A B все остальные атрибуты R функционально зависят от A .

Другими словами:

Отношение R находится в 4НФ, если оно находится в НФБК и все многозначные зависимости отношения R фактически являются функциональными зависимостями от потенциальных ключей .

Отношение ДПУ не находится в 4НФ, поскольку содержит многозначную зависимость, не являющуюся функциональной зависимостью. Однако обе проекции {Д, П} и {Д, У} находятся в 4НФ, которая по сравнению с НФБК позволяет создать улучшенную структуру.

Отметим, что концепция независимых проекций Риссанена, основанная на функциональных зависимостях (отношение R{A,B,C}, удовлетворяющее функциональным зависимостям A>B и B>C, следует разбивать на проекции {A,B} и {B,C}, а не {A,B} и {A,C}), применима и к выбору пути декомпозиции, если вместо функциональных зависимостей присутствуют многозначные зависимости A>>B и A>>C. В Этом случае следует провести декомпозицию на отношения {A,B} и {A,C}.

Во всех рассмотренных до этого момента процедурах нормализации производилась декомпозиция одного отношения на два. Иногда это сделать не удается, но возможна декомпозиция на большее число отношений, каждое из которых обладает лучшими свойствами. Такое отношение называется n-декомпозируемым отношением, для которого n>2.

Рассмотрим, например, отношение П-Д-Пр (Поставщики-Детали-Проекты) (рис.13). Один и тот же поставщик может поставлять несколько типов деталей для разных проектов. Первичным ключом этого отношения является полная совокупность его атрибутов, отсутствуют функциональные и многозначные зависимости (многозначной зависимости нет, т.к. для П1 набор деталей зависит от проекта). Поэтому отношение находится в 4НФ. Однако в нем могут существовать аномалии (не всегда очевидные), которые можно устранить путем декомпозиции на три отношения (декомпозиция на два отношения невозможно, так как обратная операция не позволяет вернуться к исходному отношению). Причем, степень декомпозиции зависит от кортежей. Например, если в исходном отношении убрать один из первых трех кортежей или добавить кортеж (П2, Д1, Пр2), то его можно разделить на две проекции. Если же в исходном отношении убрать последний кортеж или заменить его кортежем (П2, Д1, Пр2), то его нельзя разделить ни на две, ни на три проекции без нарушения целостности данных. Декомпозируемость этого отношения может быть фундаментальным и независящим от времени свойством, если добавить дополнительное ограничение.

Утверждение, что ПДПр равно соединению трех проекций ПД, ДПр, ПрП эквивалентно следующему утверждению:

ЕСЛИпара (П1, Д1) принадлежит отношению ПД

Ипара (Д1, Пр1) принадлежит отношению ДПр

Ипара (Пр,1П1) принадлежит отношению ПрП,

ТОтройка (П1, Д1, Пр1) принадлежит отношению ПДПр.

Это очевидно, так как тройка П1, Д1, Пр1 находится в соединении проекций ПД, ДПр, ПрП. Обратное утверждение также является истинным всегда.

С другой стороны, справедливо утверждение, что пара (П1, Д1) присутствует в отношении ПД, если тройка (П1, Д1, Пр2) присутствует в отношении ПДПр, пара (П1, Пр1) - в отношении ППр, если (П1, Д2, Пр1) есть в ПДПр, а пара (Д1, Пр1) - в отношении ДПр, если (П2, Д1, Пр1) есть в ПДПр. Тогда, если учесть наше первое утверждение, то в таком отношении должен присутствовать и кортеж (П1, Д1, Пр1)! Значит, чтобы обеспечить корректность отношения ПДПр в любой момент времени, необходимо ввести следующее ограничение:

Если кортежи (П1 , Д 1 , П р2 ), (П2 , Д 1 , П р1 ) и (П1 , Д 2 , П р1 ) принадлежат отношению ПДПр, то и кортеж (П1 , Д 1 , П р1 ) также принадлежит этому отношению .

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

Можно обратить внимание на то, что в рассматриваемом нами примере существует некоторая цикличность в данных. Критерием n-декомпозиции отношения для n>2 является некоторое циклическое ограничение. Что означает циклическое ограничение? Пусть в нашем примере последний кортеж означает, что Смитт поставляет гаечные ключи для Манхеттенского проекта. Первые три кортежа несут информацию о том, что Смитт поставляет гаечные ключи, Смитт является поставщиком для Манхеттенского проекта и гаечные ключи используются в Манхеттенском проекте. Но из этих утверждений не следует, что именно Смитт поставляет ключи для данного проекта. Если декомпозировать отношение ПДПр, состоящее из этих трех кортежей, на три проекции, то их соединение не будет равно исходному - появится "лишний" четвертый кортеж (П1, Д1, Пр1), о чем было сказано выше. Чтобы избежать такое несоответствие и вводится дополнительное ограничение, которое может быть легко реализовано декомпозицией отношения. Такая декомпозиция возможна без потерь информации только в случае существования зависимости соединения:

Отношение R (X,Y, . , Z ) удовлетворяет зависимости соединения * (X,Y, . , Z ) в том и только в том случае, когда R восстанавливается без потерь путем соединения своих проекций на X, Y, . , Z .

Рассмотрим два примера аномалий, которые существуют в отношении, на которое наложено 3D-ограничение.

2. В отношении, показанном на рис.15, кортеж (П2, Д1, Пр1) можно удалить без проблем. Но если удалять (П1, Д1, Пр1), то необходимо удалить один из оставшихся, чтобы не было некоторой цикличности в данных.

Сейчас теорему Фейгина можно сформулировать в таком виде:

Отношение R (А , В, С ) удовлетворяет зависимости соединения * (АВ , А С ) тогда и только тогда, когда оно удовлетворяет многозначным зависимостям А В и А С .

Зависимость соединения является обобщением понятия многозначной зависимости. Более того, это наиболее общая форма зависимости.

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

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

Менее строгое определение 5НФ:

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

Сейчас можно сказать, что после 3-декомпозиции отношения ПДПр его проекции ПД, ДПр и ППр находятся в 5 нормальной форме, так как для них вовсе нет зависимости соединения.

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

Для заданного отношения R можно утверждать, что оно находится в 5НФ при условии, что известны все потенциальные ключи и все зависимости соединения. Однако нет алгоритма, позволяющего определять все зависимости соединения. Но такие отношения чрезвычайно редки на практике.

Пятая нормальная форма - это последняя нормальная форма, которую можно получить путем декомпозиции. Ее условия достаточно нетривиальны, но она практически не используется.

Процедура нормализации и проектирования

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

исключение некоторых типов избыточности;

устранение некоторых аномалий обновления, включения и удаления;

проектирование макета базы данных, который являлся бы "хорошим" представлением реального мира, был интуитивно понятен и служил хорошей основой для дальнейшего развития;

упрощение процесса наложения ограничений целостности.

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

1. Унифицированное отношение должно быть приведено к 1НФ.

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

Другими словами, если отношение имеет составной первичный ключ вида (К1, К2) и включает также поле F, которое функционально зависит от части этого ключа, например, от К2, но не от полного ключа, то в этом случае рекомендуется сформировать другое отношение, содержащее К2 и F (первичный ключ - К2), и удалить F из первоначального отношения:

В результате такого действия будет получен набор отношений в 2НФ.

3. Отношения в 2НФ следует разбить на проекции для исключения любых транзитивных функциональных зависимостей. Другими словами, если отношение имеет потенциальный ключ К, не являющийся потенциальным ключом атрибут F1, который функционально зависит от К, и другой неключевой атрибут F2, который функционально зависит от F1, то рекомендуется удалить из исходного отношения атрибут F2 и сформировать другое отношение, содержащее F1 и F2, с первичным ключом F1.

В результате будет получен набор отношений в 3НФ.

5. Отношения в НФБК следует разбить на проекции для исключения всех многозначных зависимостей, которые не являются функциональными зависимостями. В результате будет получен набор отношений в 4НФ (на практике такие многозначные зависимости обычно исключаются при создании исходных отношений, отделяя независимые повторяющиеся группы).

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

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

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

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

1. Представить каждую независимую сущность таблицей базы данных (базовой таблицей) и определить первичный ключ этой базовой таблицы.

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

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

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

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

6. Указать ограничения целостности проектируемой базы данных и дать (если это необходимо) краткое описание полученных таблиц и их полей.

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

7. Пример проектирования базы данных

Назначение и предметная область

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

В базе данных должна храниться следующая информация:

Для каждого отдела: уникальный номер отдела, бюджет и уникальный номер руководителя отдела;

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

для каждого проекта: уникальный номер проекта и бюджет;

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

Семантические утверждения (ограничения): Ни один сотрудник не является одновременно руководителем нескольких отделов; ни один сотрудник не работает одновременно более чем в одном отделе; ни один сотрудник не работает одновременно более чем с одним проектом; ни один сотрудник не имеет одновременно более одного кабинета; ни один сотрудник не имеет одновременно более одного телефона; ни один сотрудник не имеет одновременно более одного задания; ни один проект не дается одновременно более чем одному отделу; ни один кабинет не относится одновременно более чем к одному отделу.

Проектирование базы данных

Анализ определенных выше объектов и атрибутов позволяет выделить сущности проектируемой базы данных и построить ее инфологическую модель в виде "Таблицы-связи" (рис. 16).

Рис. 16. Информация о компании, которая должна храниться в базе данных

Исходную иерархическую структуру можно рассматривать как ненормализованное отношение:

ОТДЕЛЫ (ОТД№, БЮДЖЕТ_О, РУК№, СОТРУДНИКИ, ПРОЕКТЫ, КАБИНЕТЫ) CANDIDATE KEY (ОТД№) CANDIDATE KEY (РУК№)

Здесь смысл атрибутов ОТД№ (уникальный номер отдела), БЮДЖЕТ_О, РУК№ (номер руководителя) понятен из названий, а атрибуты СОТРУДНИКИ, ПРОЕКТЫ, КАБИНЕТЫ состоят из значений-отношений. Мы можем расписать их вложенные атрибуты:

ОТДЕЛЫ (ОТД№, БЮДЖЕТ, РУК№, СОТРУДНИКИ (СОТР№, ПРОЕКТ№, КАБ№, ТЕЛ№, РАБОТА (ТЕМА, ОПЛАТА (ДАТА, СУММА))), ПРОЕКТЫ (ПРОЕКТ№, БЮДЖЕТ_П), КАБИНЕТЫ (КАБ№, ПЛОЩАДЬ, ТЕЛЕФОН (ТЕЛ№))) CANDIDATE KEY (ОТД№) CANDIDATE KEY (РУК№)

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

ОТДЕЛЫ1 (ОТД№, БЮДЖЕТ_О, РУК№) PRIMARY KEY (ОТД№) ALTERNATE KEY (РУК№)

СОТРУДН1 (СОТР№, ОТД№, ПРОЕКТ№, КАБ№, ТЕЛ№) PRIMARY KEY (СОТР№)

РАБОТА1 (ТЕМА, СОТР№) PRIMARY KEY (ТЕМА, СОТР№)

ОПЛАТА1 (СОТР№, ТЕМА, ДАТА, СУММА) PRIMARY KEY (СОТР№, ТЕМА, ДАТА)

ПРОЕКТЫ1 (ПРОЕКТ№, БЮДЖЕТ_П, ОТД№) PRIMARY KEY (ПРОЕКТ№)

КАБИНЕТЫ1 (КАБ№, ПЛОЩАДЬ, ОТД№) PRIMARY KEY (КАБ№)

ТЕЛЕФОНЫ1 (ТЕЛ№, КАБ№) PRIMARY KEY (ТЕЛ№)

Отношения ОТДЕЛЫ1, СОТРУДН1, ОПЛАТА1, ПРОЕКТЫ1, КАБИНЕТЫ1 и ТЕЛЕФОНЫ1 уже находятся в 2НФ.

Отношение РАБОТА1 является проекцией отношения ОПЛАТА1, следовательно, оно несет избыточную информацию и его можно удалить без потери данных. В то же время, отношение ТЕЛЕФОНЫ1 является проекцией отношения СОТРУДН1, но при его удалении появятся аномалии обновления - данные о телефонах не будут существовать без данных о конкретных сотрудниках.

Покажем сейчас структуру базы данных, отношения которой приведены к 2НФ, используя язык моделирования "Таблица-Связь", который применяется в СУБД MS ACCESS:

Далее, исключая транзитивные зависимости, можно привести отношения к эквивалентной совокупности отношений в 3НФ. Единственным отношением, которое не находится в 3НФ, является отношение СОТРУДН, в котором атрибуты КАБ№ и ОТД№ транзитивно зависят от первичного ключа СОТР№ - КАБ№ через ТЕЛ№, а ОТД№ через ПРОЕКТ№ и, кроме того, через КАБ№ и ТЕЛ№. Тогда отношение СОТРУДН можно заменить совокупностью проекций, находящихся в 3НФ:

X (ТЕЛ№, КАБ№) PRIMARY KEY (ТЕЛ№)

Y (ПРОЕКТ№, ОТД№) PRIMARY KEY (ПРОЕКТ№)

Z (КАБ№, ОТД№) PRIMARY KEY (КАБ№)

Но отношение X - аналог отношения ТЕЛЕФОН2, Y - проекции отношения ПРОЕКТ2, Z - проекции КАБИНЕТ2 и, значит, могут быть удалены из модели базы данных. Следовательно, модель базы данных, отношения которой приведены к 3НФ, будет выглядеть так:

ОТДЕЛЫ3 (ОТД№, БЮДЖЕТ_О, РУК№) PRIMARY KEY (ОТД№) ALTERNATE KEY (РУК№)

СОТРУДН3 (СОТР№, ПРОЕКТ№, ТЕЛ№) PRIMARY KEY (СОТР№)

ОПЛАТА3 (СОТР№, ТЕМА, ДАТА, СУММА) PRIMARY KEY (СОТР№, ТЕМА, ДАТА)

ПРОЕКТЫ3 (ПРОЕКТ№, БЮДЖЕТ_П, ОТД№) PRIMARY KEY (ПРОЕКТ№)

КАБИНЕТЫ3 (КАБ№, ПЛОЩАДЬ, ОТД№) PRIMARY KEY (КАБ№)

ТЕЛЕФОНЫ3 (ТЕЛ№, КАБ№) PRIMARY KEY (ТЕЛ№)

Каждое из этих отношений находится в НФБК. Более того, они находятся в 4НФ - от возможных многозначных зависимостей мы избавились на этапе приведения модели к 1НФ. Все отношения не содержат видимых аномалий и поэтому можно предполагать, что база данных сконструирована правильно.

Литература

1. Бек, Кент Шаблоны реализации корпоративных приложений; М.: Вильямс, 2008. - 369 c.

2. Веймаер, Р.; Сотел, Р. Освой самостоятельно Microsoft SQL Server 2000 за 21 день (+ CD-ROM); М.: Вильямс, 2013. - 549 c.

3. Гандерлой, Майк; Харкинз, Сьюзан Сейлз Автоматизация Microsoft Access с помощью VBA; М.: Вильямс, 2013. - 416 c.

4. Гетц, Кен; Джинберт, Майкл; Литвин, Пол Access 2000. Руководство разработчика. Том 1. Настольные приложения. том 1; Киев: BHV, 2008. - 576 c.

5. Голицына, О.Л. и др. Базы данных; Форум; Инфра-М, 2013. - 399 c.

6. Гринченко, Н.Н. и др. Проектирование баз данных. СУБД Microsoft Access; Горячая Линия Телеком, 2012. - 613 c.

7. Дейт, К. Дж. Введение в системы баз данных; К.: Диалектика; Издание 6-е, 2012. - 360 c.

8. Дэвидсон, Луис проектирование баз данных на SQL Server 2000; Бином, 2009. - 631 c.

9. Дюваль, Поль М. Непрерывная интеграция. Улучшение качества программного обеспечения и снижение риска; М.: Вильямс, 2008. - 497 c.

10. Каратыгин, С.; Тихонов, А. Работа в Paradox для Windows 5.0 на примерах; М.: Бином, 2011. - 512 c.

11. Каратыгин, Сергей Access 2000 на примерах. Руководство пользователя с примерами; М.: Лаборатория Базовых Знаний, 2012. - 376 c.

12. Кауфельд, Джон Microsoft Office Access 2003 для "чайников"; М.: Диалектика, 2013. - 439 c.

13. Каучмэн, Джейсон; Швинн, Ульрике Oracle 8i CertifiedProfessionaql DBA Подготовка администраторов баз данных; ЛОРИ, 2009. - 510 c.

Подобные документы

Понятие системы базы данных. Реляционная модель и ее характеристики. Целостность в реляционной модели. Реляционная алгебра. Вопросы проектирования БД. Нормальные формы отношений. Проектирование БД методом сущность-связь. ER-диаграммы. Язык SQL.

курс лекций , добавлен 03.10.2008


Использование нормализации. Вторая и третья нормальные формы. Нормальная форма Бойса-Кодда. Четвертая и пятая нормальная форма. Семантическое моделирование данных, ER-диаграммы. Основные понятия модели Entity-Relationship.

контрольная работа , добавлен 07.08.2007


Понятие нормализации таблиц базы данных и ее цели. Этапы процесса нормализации. Пример ненормализованных данных. Нормальные формы, к которым приводятся таблицы. Реляционная алгебра над учебной базой. База данных для предметной области "Учебные пособия".

контрольная работа , добавлен 30.07.2010


Создание структуры базы данных на примере "Школьного журнала" с использованием метода и принципа нормализации. Понятия базы данных, архитектуры БД и проектирования. Описание предметной области; приложения для работы с базой данных TTable и TQuery.

дипломная работа , добавлен 01.04.2012


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

курсовая работа , добавлен 22.02.2012


Авторизация с каталогами проектирования базы данных магазина. Задачи базы данных: учет всех товаров, поиск и выдача данных о клиентах, адрес, телефоны, цена и наличие товара. Этапы проектирования базы данных. Схема данных, создание запросов и их формы.

реферат , добавлен 22.10.2009


Основы проектирования реляционных баз данных. Схема взаимосвязей моделей и представлений сложной системы в процессе объектно-ориентированного анализа. Примеры графического изображения конкретных классов. Представление об информационной модели данных.

презентация , добавлен 14.10.2013


Определения, необходимые для понимания процесса проектирования реляционных баз данных на основе нормализации. Декомпозиция без потерь по теореме Хита. Аномальные обновления. Разработка моделей базы данных и приложений, анализ проблем при их создании.

презентация , добавлен 14.10.2013


Интегрированная база данных. Разработка концепции и структуры корпоративной базы данных для новой информационной системы. Подходы в методах проектирования баз данных: компонентная открытость и смысловая интероперабельность; разработка понятийных моделей.

доклад , добавлен 11.01.2011


Анализ предметной области, ее формализации с помощью функциональных зависимостей. Этапы минимизации системы функциональных зависимостей и на основании полученной редуцированной системы проектирование модели базы данных. Создание и моделирование запросов.

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

Введение

При проектировании базы данных решаются две основные проблемы.

• Каким образом отобразить объекты предметной области в абстрактные объекты модели данных, чтобы это отображение не противоречило семантике предметной области и было, по возможности, лучшим (эффективным, удобным и т. д.)? Часто эту проблему называют проблемой логического проектирования баз данных.
• Как обеспечить эффективность выполнения запросов к базе данных, т. е. каким образом, имея в виду особенности конкретной СУБД, расположить данные во внешней памяти, создания каких дополнительных структур (например, индексов) потребовать и т. д.? Эту проблему обычно называют проблемой физического проектирования баз данных.

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

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

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

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

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

В теории реляционных баз данных обычно выделяется следующая последовательность нормальных форм:

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

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

Концептуальное проектирование БД ИС является в значительной степени эвр"истическим процессом. Адекватность построенной в его рамках инфологической модели предметной области проверяется опытным путем, в процессе функционирования ИС.

Перечислим этапы концептуального проектирования:

* изучение предметной области для формирования общего пред­ставления о ней;

* выделение и анализ функций и задач разрабатываемой ИС;

* определение основных объектов-сущностей предметной области и отношений между ними;

* формализованное представление предметной области.

При проектировании схемы реляционной БД можно выделить сле­дующие процедуры:

*определение перечня таблиц и связей между ними;

*определение перечня полей, типов полей, ключевых полей каж­дой таблицы (схемы таблицы), установление связей между таб­лицами через внешние ключи;

*установление индексирования для полей в таблицах;

* разработка списков (словарей) для полей с перечислительными данными;

* установление ограничений целостности для таблиц и связей;

* нормализация таблиц, корректировка перечня таблиц и связей. Проектирование БД осуществляется на физическом и логическом уровнях. Проектирование на физическом уровне реализуется сред­ствами СУБД и зачастую автоматизировано.

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

Одной из важнейших задач логического проектирования БД явля­ется структуризация данных. Выделяют следующие подходы к проек­тированию структур данных:

*объединение информации об объектах-сущностях в рамках одной таблицы (одного отношения) с последующей декомпозицией на несколько взаимосвязанных таблиц на основе процедуры норма­лизации отношений;

* формулирование знаний о системе (определение типов исходных данных и взаимосвязей) и требований к обработке данных, полу­чение с помощью СА5Е-системы готовой схемы БД или даже го­товой прикладной информационной системы;

* осуществление системного анализа и разработка структурных

Информационные системы

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

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

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

 период системного применения ЭВМ. Для решения на ЭВМ комплекса задач создаются программные средства, оперирующие одними и теми же данными, использующие единую информационную модель объекта. Эти средства не зависят от характера объекта, его модели, их можно применять для информационного обслуживания различных задач. Человечество пришло к организации информации в информационных системах.

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

Фактографическая ИС - это массив фактов - конкретных значений данных об объектах реального мира.

Информация в фактографической ИС хранится в четко структурированном виде, поэтому она способна давать однозначные ответы на поставленные вопросы, например: «Кто является победителем Чемпионата России по гимнастике в 1999 году?», «Кому принадлежит автомобиль марки AUDI 80 с регистрационным номером РА899Р77?», «Какой номер телефона в бухгалтерии МГУ?», «Кто стал Президентом России на выборах в марте 2002 года?» и т. д. Фактографические ИС используются буквально во всех сферах человеческой деятельности - в науке, материальном производстве, на транспорте, в медицине, государственной и общественной жизни, торговле, криминалистике, искусстве, спорте.

Документальные информационные системы обслуживают принципиально иной класс задач, которые не предполагают однозначного ответа на поставленный вопрос. Базу данных таких систем образует совокупность неструктурированных текстовых документов (статьи, книги, рефераты, тексты законов) и графических объектов, снабженная тем или иным формализованным аппаратом поиска. Цель системы, как правило, - выдать в ответ на запрос пользователя список документов или объектов, в какой-то мере удовлетворяющих сформулированным в запросе условиям. Например: выдать список всех статей, в которых встречается слово «Пушкин». Принципиальной особенностью документальной системы является ее способность, с одной стороны, выдавать ненужные пользователю документы (например, где слово «Пушкин» употреблено в ином смысле, чем предполагалось), а с другой - не выдавать нужные (например, если автор употребил какой-то синоним или ошибся в написании). Документальная система должна уметь по контексту определять смысл того или иного термина, например, различать «ромашка» (растение), «ромашка» (тип печатающей головки принтера).

Экспертные системы (ЭС) - интеллектуальные системы, призванные играть роль «советчика», построены на базе формализованного опыта и знаний эксперта. Ядром ЭС являются базы знаний, в которых собраны знания экспертов (специалистов) в определенной области, на основе которых ЭС позволяет моделировать рассуждения специалистов из данной предметной области.

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

КОНСПЕКТ ОБЗОРНОЙ ЛЕКЦИИ

Для студентов специальности
Т1002 «Программное обеспечение информационных технологий»

(Л.В. Рудикова, к.ф.-м.н., доцент)

Вопрос 31. АРХИТЕКТУРА СУБД. РЕЛЯЦИОННАЯ МОДЕЛЬ ДАННЫХ

1. Понятие базы данных.

2. Трехуровневая архитектура базы данных.

3. Жизненный цикл базы данных.

4. Архитектура СУБД.

5. Реляционная модель данных.

6. Проектирование реляционных баз данных.

7. Нормальные формы отношений.

8. Реляционная алгебра.

1. Понятие базы данных.

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

Информационная система – автоматическая система, организующая данные и выдающая информацию.

Информационно-управляющая система – система, обеспечивающая информационную поддержку менеджмента.

Данные – разрозненные факты.

Информация – организованные и обработанные данные.

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

Каждая СУБД должна удовлетворять следующим требованиям:

· обеспечивать пользователю возможность создавать новые БД и определять их схему (логическую структуру данных) с помощью специального языка - языка определения данных ; поддерживать разнообразные представления одних и тех же данных;

· позволять «запрашивать » данные и изменять их с помощью языка запросов , или языка манипулирования данными ; допускать интеграцию и совместное использование данных различными приложениями;

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

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

Система с базой данных состоит из следующих компонентов:

· Пользователи, т.е. люди, которые используют данные.

· Приложения, т.е. программы пользователей, которым требуются данные из системы.

· СУБД – программное обеспечение, которое управляет доступом к данным и обеспечивает указанные функциональные возможности системы с базой данных.

· Данные, т.е. строки, хранящиеся в файлах.

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

Таким образом, систему с БД можно представить в виде следующей последовательности уровней:

На самом нижнем уровне находятся данные, хранящиеся в физических файлах (физическая память БД). На верхнем уровне – приложений с их собственными представлениями одних и тех же физических данных. Каждой представление БД – это определенная логическая структура, построенная из лежащих в основе физических данных. Чтобы обеспечить интерфейс между физической памятью БД и ее разнообразными логическими версиями (множеством поддерживаемых представлений) СУБД, в свою очередь должна состоять из нескольких уровней.

2. Трехуровневая архитектура базы данных.

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

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

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

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

Рис. Уровни СУБД

3. Жизненный цикл базы данных.

Процесс проектирования, реализации иподдержания системы базы данных называется жизненным циклом базы данных (ЖЦБД). Процедура создания системы называется жизненным циклом системы (ЖЦС).

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

ЖЦБД состоит из следующих этапов:

1. Предварительное планирование – планирование БД, выполняемое в процессе разработки стратегического плана БД. В процессе планирования собирается следующая информация:

· какие прикладные программы используются, и какие функции они выполняют;

· какие файлы связаны с каждым из этих приложений;

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

Данная информация помогает определить, как используется информация приложений, определить будущие требования к системе БД.

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

2. Проверка осуществимости . Здесь определяется технологическая, операционная и экономическая осуществимость плана создания БД, т. е.:

· технологическая осуществимость – есть ли технология для реализации запланированной БД?

· операционная осуществимость – есть ли средства и эксперты, необходимые для успешного осуществления плана создания БД?

· экономическая целесообразность – можно ли определить выводы? Окупится ли запланированная система? Можно ли оценить издержки и выгоду?

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

· Определяются цели системы путём анализа информационных потребностей. Здесь также обязательно указывается, какую именно БД следует создавать (распределённую, целостную) и какие коммуникационные средства необходимы. Выходной документ – комментарий, описывающий цели системы.

· Определение пользовательских требований: документация в виде обобщённой информации (комментарии, отчёты, опросы, анкеты и т. д.); фиксация функций системы и определение прикладных систем, которые будут выполнять эти требования. Данные представляются в виде соответствующих документов.

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

· Разработка плана поэтапного создания системы, включающий выбор исходных приложений.

4. Концептуальное проектирование – создание концептуальной схемы БД. Спецификации разрабатываются в той степени, которая необходима для перехода к реализации.

Основным выходным документом является единая инфологическая модель (или схема БД на концептуальном уровне ). При разработке данной модели используются информация и функции, которые должна выполнить система, определённые на этапе сбора и определения требований к системе. На данном этапе желательно также определить: 1) правила для данных; 2) правила для процессов; 3) правила для интерфейса.

5. Реализация – процесс превращения концептуальной модели в функциональную БД. Он включает в себя следующие этапы.

1) Выбор и приобретение необходимой СУБД.

2) Преобразование концептуальной (инфологической) модели БД в логическую и физическую модель данных:

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

· определяются, какие прикладные процессы необходимо реализовать в схеме данных как хранимые процедуры;

· реализовать ограничения, предназначенные для обеспечения целостности данных и реализации правил для данных;

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

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

· определить уровни доступа пользователей, разработать и внедрить правила обеспечения безопасности и аудита. Создать роли и синонимы для обеспечения многопользовательского доступа с согласованными уровнями полномочий доступа.

· разработать сетевую топологию БД и механизм бесшовного доступа к удалённым данным (реплицированная или распределённая БД).

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

4) Заполнение базы данных.

5) Создание прикладных программ, контроль управления.

6) Обучение пользователей.

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

Таким образом, ЖЦБД включает в себя:

· Изучение предметной области и представление соответствующей документации (1-3).

· Построение инфологической модели (4).

· Реализация (5).

· Оценка работы и поддержка БД (6).

4. Архитектура СУБД.

Рис. Главные компоненты СУБД

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

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

Менеджер памяти -получает требуемую информацию из места хранения данных и изменяет в нем информацию по требованию расположенных выше уровней системы.

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

· Менеджер файлов контролирует расположение файлов на диске и получает блок или блоки, содержащие файлы, по запросу менеджера буфера (диск в общем случае делится на дисковые блоки - смежные области памяти, содержащие от 4000 до 16000 байт).

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

Процессор «запроса» - обрабатывает запросы и запрашивает изменения данных или метаданных. Он предлагает лучший способ выполнения необходимой операции и выдает соответствующие команды менеджеру памяти.

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

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

Типичные СУБД позволяют пользователю сгруппировать несколько запросов и/или изменений в одной транзакции. Транзакция - это группа операций, которые необходимо выполнить последовательно, как одно целое.

Как правило, система БД поддерживает одновременно множество транзакций. Именно правильное выполнение всех таких транзакций и обеспечивает менеджер транзакций . Правильное выполнение транзакций обеспечивается ACID -свойствами (atomicity , consistency , isolation , durability ):

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

· непротиворечивость - состояние, при котором данные соответствуют всем возможным ожиданиям (например, условие непротиворечивости для БД авиационных линий состоит в том, что ни одно из мест в самолете не бронируется для двух пассажиров);

· изоляция - при параллельном выполнении двух или более транзакций их результаты должны быть изолированы друг от друга. Одновременное выполнение двух транзакций одновременно не должно привести к результату, которого не было бы, если они выполнялись последовательно (например, при продаже билетов на один и тот же рейс в случае свободного последнего места при одновременном запросе двух агентов, запрос одного должен быть выполнен, другого - нет);

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

Рассмотрим также 3 типа обращения к СУБД:

1. Запросы - вопросы по поводу данных могут генерироваться двумя способами:

a) с помощью общего интерфейса запросов (например, реляционная СУБД допускает запросы SQL , которые передаются процессору запросов, а также получает ответы на них);

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

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

3. Модификации схемы - это команды администраторов БД, которые имеют право изменять схему БД или создавать новую БД.

Архитектура клиент/сервер. Во многих вариантах современного ПО реализуется архитектура клиент/сервер : один процесс (клиент) посылает запрос для выполнения другому процессу (серверу). Как правило, БД часто разделяется на процесс сервера и несколько процессов клиента.

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

5. Реляционная модель данных.

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

Отношение представляет собой двумерную таблицу, содержащую некоторые данные. Математически под N -арным отношением R понимают множество декартова произведения D 1 D 2 … D n множеств (доменов ) D 1, D 2 , …, D n (), необязательно различных:

R D 1 D 2 … D n ,

где D 1 D 2 … D n – полное декартово произведение, т.е. набор всевозможных сочетаний из n элементов каждое, где каждый элемент берется их своего домена.

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

· Домен имеет уникальное имя (в пределах базы данных).

· Домен определен на некотором простом типе данных или на другом домене.

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

· Домен несет определенную смысловую нагрузку .

Атрибут отношения есть пара вида <Имя_атрибута: Имя_домена>. Имена атрибутов должны быть уникальны в пределах отношения. Часто имена атрибутов отношения совпадают с именами соответствующих доменов.

Отношение R , определенное на множестве доменов, содержит две части: заголовок и тело.

Заголовок отношения – это фиксированное количество атрибутов отношения:

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

Тело отношения содержит множество кортежей отношения. Каждый кортеж отношения представляет собой множество пар вида <Имя_атрибута: Значение_атрибута>:

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

Отношение обычно записывается в виде:

или короче

,

или просто

Число атрибутов в отношении называют степенью (или -арностью ) отношения. Мощность множества кортежей отношения называют мощностью отношения.

Схемой отношения называется перечень имен атрибутов данного отношения с указанием домена, к которому они относятся:

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

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

Пусть – схема отношения . – схема отношения после упорядочения имен атрибутов. Тогда

~

Таким образом, для эквивалентных отношений выполняются следующие условия:

· Таблицы имеют одинаковое количество столбцов.

· Таблицы содержат столбцы с одинаковыми наименованиями.

· Столбцы с одинаковыми наименованиями содержат данные из одних и тех же доменов.

· Таблицы имеют одинаковые строки с учетом того, что порядок столбцов может различаться.

Все такие таблицы есть различные изображения одного и того же отношения.

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

· В отношении нет одинаковых кортежей .

· Кортежи не упорядочены (сверху вниз) .

· Атрибуты не упорядочены (слева направо) .

· Все значения атрибутов атомарны .

Рис. Схематическое изображение отношения

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

6. Проектирование реляционных баз данных.

При проектирование реляционной БД должны быть решены следующие проблемы:

1) С учетом семантики предметной области необходимо наилучшим способом представить объекты предметной области в виде абстрактной модели данных (даталогическое проектирование). Т.е. - определиться со схемой БД: из каких отношений должны состоять БД, какие атрибуты должны быть у этих отношений, каковы связи между отношениями.

2) Обеспечить эффективность выполнения запросов к базе данных (физическое проектирование БД).

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

· Построение корректной схемы данных ориентируясь на реляционную модель данных.

· Описание схемы БД в терминах выбранной СУБД.

· Описание внешних моделей в терминах выбранной СУБД.

· Описание декларативных правил поддержки целостности БД.

· Разработка процедур поддержки семантической целостности БД.

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

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

Проектирование схемы БД можно выполнить двумя методами:

· Метод декомпозиции (разбиения) – исходное множество отношений, входящих в схему БД заменяется другим множеством отношений, являющихся проекциями исходных отношений! При этом число отношений возрастает.

· Метод синтеза – компоновка схемы БД из заданных исходных элементарных зависимостей между объектами предметной области.

Классическое проектирование БД связано с теорией нормализацией , которая основана на анализе функциональных зависимостей между атрибутами отношений. Функциональные зависимости определяют устойчивые отношения между объектами и их свойствами в рассматриваемой предметной области.

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

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

В теории реляционных БД обычно выделяют следующие нормальные формы:

первая нормальная форма (1 NF );

· вторая нормальная форма (2 NF );

· третья нормальная форма (3 NF );

· нормальная форма Байса-Кодда (BCNF );

· четвертая нормальная форма (4 NF );

· пятая нормальная форма или форма проекции - соединения (5 NF или PYNF ).

Основные свойства нормальных форм:

· каждая следующая нормальная форма в некотором смысле лучше предыдущей;

· при переходе к следующей нормальной форме свойства предыдущих нормальных свойств сохраняются.

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

7. Нормальные формы отношений.

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

· Аномалии вставки (INSERT) – хранение в одном отношении разнородной информации.

· Аномалии обновления (UPDATE) –избыточность данных отношения из-за хранения разнородной.

· Аномалии удаления (DELETE) – хранение разнородной информации в одном отношении.

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

Нормализация – разбиение таблицы на несколько, которые обладают лучшими свойствами при обновлении, вставке и удалении данных. Т.е. нормализация представляет собой процесс последовательной замены таблицы ее полными декомпозициями до тех пор, пока все они не будут находиться в 5НФ, однако, на практике достаточно привести таблицы к НФБК.

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

Если заменить на время нормализации коды первичных (внешних) ключей, то следует рассмотреть 2 случая:

1. Таблица имеет составной первичный ключ, например и поле , которое функционально зависит от части этого ключа, например, от (от полного ключа не зависит). Рекомендуется сформировать другую таблицу, содержащую и ( – первичный ключ), и удалить из первоначальной таблицы:

Заменить , первичный ключ , ФЗ

на , первичный ключ

и , первичный ключ .

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

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

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

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

Если потенциальный ключ является простым, то отношение автоматически находится в 2НФ.

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

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

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

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

При приведении отношений при помощи алгоритма нормализации к отношениям в 3НФ предполагается, что все отношения содержат один потенциальный ключ. Это не всегда верно. Бывают случаи, когда отношение может содержать несколько ключей.

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

Если отношение находится в НФБК, то оно автоматически находится в 3НФ, что следует из определения 4. Чтобы устранить зависимость от детерминантов, не являющихся потенциальными ключами, следует провести декомпозицию, вынося эти детерминанты и зависимые от них части в отдельное отношение.

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

Опр.5. Отношение находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей.

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

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

Опр.6. Отношение находится в пятой нормальной форме (5НФ) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной.

Опр.6. тождественно также следует определению.

Опр.7. Отношение не находится в 5НФ, если в отношении найдется нетривиальная зависимость соединения.

Т.о. если в каждой полной декомпозиции все проекции исходного отношения содержат возможный ключ, можно сделать вывод о том, что отношение находится в 5НФ. Отношение, не имеющее ни одной полной декомпозиции также находится в 5НФ.

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

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

Взаимно-независимые атрибуты – это атрибуты, не зависящие один от другого. Если в отношение существует несколько ФЗ, то каждый атрибут или набор атрибутов, от которого зависит другой атрибут, называется детерминантом отношения.

9. Реляционная алгебра.

Реляционная алгебра представляет собой основу доступа к реляционным данным. Основная цель алгебры – обеспечить запись выражений. Выражения могут использоваться для:

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

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

· определение (именованных) виртуальных отношений , т.е. представление данных для их визуализации через представления;

· определение снимка, т.е. определение данных для сохранения в виде «мгновенного снимка» отношения;

· определение правил безопасности, т.е. определение данных, для которых осуществляется контроль доступа;

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

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

В реализациях конкретных реляционных СУБД сейчас не используется в чистом виде ни реляционная алгебра, ни реляционное исчисление. Фактическим стандартом доступа к реляционным данным стал язык SQL (Structured Query Language).

Реляционная алгебра, определенная Коддом состоит из 8 операторов, составляющих 2 группы:

• традиционные операции над множествами (объединение, пересечение, вычитание, декартово произведение);
• специальные реляционные операции (выборка, проекция, соединение, деление).

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

Краткий обзор операторов реляционной алгебры.

Выборка – возвращает отношение, которое содержит все кортежи определенного отношения, удовлетворяющие некоторым условиям. Операция выборки называется также операцией ограничения (restrict - ограничение, сейчас чаще принимается выборка - SELECT ).

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

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

Объединение – возвращает отношение, содержащее все кортежи, которые принадлежат или одному из двух определенных отношений, или обоим.

Пересечение – возвращает отношение, содержащее все кортежи, которые принадлежат одновременно двум определенным отношениям.

Вычитание – возвращает отношение, содержащее все кортежи, которые принадлежат первому из двух определенных отношений и не принадлежат второму.

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

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

ЛИТЕРАТУРА

1. Дейт К.Дж. Введение в системы баз данных, 6-е издание: Пер. с англ. – К.; М.; СПб.: Издательский дом «Вильямс», 2000. – 848 с.

2. Конноли Т., Бегг К., Страчан А. Базы данных: проектирование, реализация и сопровождение. Теория и практика, 2-е изд.: Пер. с англ. – М.: Издательский дом «Вильямс», 2000. – 1120 с.

3. Карпова Т.С. Базы данных: модели, разработка, реализация. – СПб.: Питер, 2001. – 304 с.

4. Фаронов В.В., Шумаков П.В. Delphi 4. Руководство разработчика баз данных. – М.: «Нолидж», 1999. – 560 с.

5. Дж. Грофф, П.Вайнберг. SQL: Полное руководство: Пер. с англ. – К.: Издательская группа BHV, 2001. – 816 с.

6. Кен Гетц, Пол Литвин, Майк Гилберт. Access 2000. Руководство разработчика. Т.1, 2. Пер. с англ. – К.: Издательская группа BHV, 2000. – 1264 с, 912 c.

7. Маклаков С.В BPwin и EPwin. CASE-средства разработки информационных систем. – М.: ДИАЛОГ-МИФИ, 2001. – 304 с.

8. Ульман Д., Уидом Д. Введение в системы баз данных / Пер. с англ. – М.: «Лори», 2000. – 374 с.

9. Хомоненко А.Д., Цыганков В.М., Мальцев М.Г. Базы данных: Учебник для высших учебных заведений / Под ред. Проф. А.Д.Хомоненко. – Спб.: КОРОНА принт, 2000. – 416 с.