Архитектуры обработки информации

Теоретические основы БД

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

Объект (сущность) – нечто существующее и различимое, для которого существует название и способ отличать от другого объекта.

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

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

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

Т.о. возникает возможность устанавливать связи между объектами из разных наборов.

Информацию об объектах можно и нужно структурировать, т.к. структурированную информацию значительно легче обрабатывать.

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

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

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

Пример неструктурированных данных:

 

Иванов Петр, Дата рождения 31.05.76, №21

№22, Андрей Сергеенко, 31/05/76

Спицын Александр Павлович, 31 мая 1972 год, №56

 

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

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

Результат выполнения структуризации для рассматриваемого примера представлен в таблице 1.

Таблица 1. Структурирование данных

 

№	Фамилия	Имя	Дата свершения сделки
	Иванов	Петр	31/05/76
	Сергеенко	Андрей	31/05/76
	Спицын	Александр	31/05/72

Базы данных

В широком смысле слова база данных – это совокупность сведений о конкретных объектах реального мира в какой либо предметной области.

Предметная область – часть реального мира, подлежащего изучению для организации управления и автоматизации.

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

База данных – именованная совокупность взаимосвязанных данных, находящихся под управлением некоторой системы, которая называется СУБД.

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

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

1. Воспринимать и обрабатывать команды пользователей и приложений на выборку, изменение, добавление и удаление данных из БД.

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

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

4. Иметь механизмы оптимизации выполнения операций 1-3.

5. Иметь компонент, который хранит сведения обо всех объектах, которыми оперирует СУБД. Например, об объеме используемой ею памяти, активных соединениях и т.д. Т.е. различная техническая и справочная информация о состоянии СУБД и БД.

Модели баз данных

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

Модель данных – совокупность структур данных и операций по их обработке.

В терминологии моделей данных используются понятия «элемент данных» и правила связывания.

Элемент данных описывает любой набор данных.

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

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

 

Иерархическая модель данных

Типичным представителем (наиболее известным и распространенным) является Information Management System (IMS) фирмы IBM. Первая версия появилась в 1968 г. До сих пор поддерживается много баз данных, что создает существенные проблемы с переходом как на новую технологию БД, так и на новую технику.

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

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

Пример типа дерева (схемы иерархической БД):

Ошибка! Ошибка связи.

Рис. 4.

ЗдесьУниверситет является предком для Факультет и Подразделения, а Факультет и Подразделения - потомки Университет. Между типами записи поддерживаются связи.

База данных с такой схемой могла бы выглядеть следующим образом (мы показываем один экземпляр дерева):

Ошибка! Ошибка связи.

Рис. 5.

 

Все экземпляры данного типа потомка с общим экземпляром типа предка называются близнецами. Для БД определен полный порядок обхода - сверху-вниз, слева-направо.

Манипулирование данными

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

· Найти указанное дерево БД (например, факультет ФИПМ);

· Перейти от одного дерева к другому;

· Перейти от одной записи к другой внутри дерева (например, от отдела - к первому сотруднику);

· Перейти от одной записи к другой в порядке обхода иерархии;

· Вставить новую запись в указанную позицию;

· Удалить текущую запись.

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

 

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

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

– Необходимость использования той иерархии, которая была заложена в основу БД при ее проектировании;

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

 

Сетевая модель данных

Типичным представителем является Integrated Database Management System (IDMS) компании Cullinet Software, Inc., предназначенная для использования на машинах основного класса фирмы IBM под управлением большинства операционных систем. Архитектура системы основана на предложениях Data Base Task Group (DBTG) Комитета по языкам программирования Conference on Data Systems Languages (CODASYL), организации, ответственной за определение языка программирования Кобол. Отчет DBTG был опубликован в 1971 г., а в 70-х годах появилось несколько систем, среди которых IDMS.

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

Каждый элемент (потомок) может иметь более одного порождающего элемента (родителя).

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

Тип связи определяется для двух типов записи: предка и потомка. Экземпляр типа связи состоит из одного экземпляра типа записи предка и упорядоченного набора экземпляров типа записи потомка. Для данного типа связи L с типом записи предка P и типом записи потомка C должны выполняться следующие два условия:

· Каждый экземпляр типа P является предком только в одном экземпляре L;

· Каждый экземпляр C является потомком не более, чем в одном экземпляре L.

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

· Тип записи потомка в одном типе связи L1 может быть типом записи предка в другом типе связи L2 (как в иерархии).

· Данный тип записи P может быть типом записи предка в любом числе типов связи.

· Данный тип записи P может быть типом записи потомка в любом числе типов связи.

· Может существовать любое число типов связи с одним и тем же типом записи предка и одним и тем же типом записи потомка; и если L1 и L2 - два типа связи с одним и тем же типом записи предка P и одним и тем же типом записи потомка C, то правила, по которым образуется родство, в разных связях могут различаться.

· Типы записи X и Y могут быть предком и потомком в одной связи и потомком и предком - в другой.

· Предок и потомок могут быть одного типа записи.

Простой пример сетевой схемы БД:

Ошибка! Ошибка связи.

Рис. 6.

 

Примерный набор операций может быть следующим:

· Найти конкретную запись в наборе однотипных записей (студента Щербинко);

· Перейти от предка к первому потомку по некоторой связи (к первому студенту гр. ИСМ-100);

· Перейти к следующему потомку в некоторой связи (от студента А к куратору Б);

· Перейти от потомка к предку по некоторой связи (найти группу куратора Б);

· Создать новую запись;

· Уничтожить запись;

· Модифицировать запись;

· Включить в связь;

· Исключить из связи;

· Переставить в другую связь и т.д.

+

–

 

Итак, иерархические и сетевые СУБД существовали в давнее время. Сильные места ранних СУБД:

+ Развитые средства управления данными во внешней памяти на низком уровне;

+ Возможность построения вручную эффективных прикладных систем;

Возможность экономии памяти за счет разделения подобъектов (в сетевых системах).

Недостатки:

– Слишком сложно пользоваться;

– Фактически необходимы знания о физической организации;

– Прикладные системы зависят от этой организации;

– Их логика перегружена деталями организации доступа к БД.

 

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

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

Основоположником реляционных БД считается сотрудник фирмы IBM доктор Кодд, опубликовавший 6 июня 1970 года свою статью. Будучи математиком, для обработки данных он предложил использовать аппарат теории множеств. Он доказал, что любой набор данных можно предстваить в виде двумерных таблиц особого вида, известных в математике как отношение. От английского слова “relation” и произошло название «реляционная модель данных».

Взаимосвязь отношений

Взаимосвязь отношений является важнейшим элементом реляционной модели данных. Она поддерживается внешними ключами (foreign key). Рассмотрим пример. В БД содержатся сведения: по университету (таблица Университет), о различных кафедрах университета (таблица Кафедры), а также сведения о сотрудниках этих кафедр (таблица Сотрудники). Первичным ключом таблицы Университет является поле ИД_Универ, ИД_Сотр и ИД_Каф. Сотрудники является поле ИД_Сотр, а таблицы Кафедры – поле ИД_Каф. Таким образом, поля ИД_Сотр и ИД_Каф таблицы Университет являются внешними ключами для связи с таблицами Кафедры и Сотрудники.

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

Рис. 8. Связывание таблиц

 

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

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

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

1. Каждое значение атрибута внешнего ключа должно являться значением соответствующего потенциального ключа. Причем обратная ситуация необязательно.

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

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

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

5. Для атрибутов внешнего ключа разрешается иметь значения NULL

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

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

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

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

Заметим, что крайне редко алгебра или исчисление принимаются в качестве полной основы какого-либо языка БД. Обычно (как, например, в случае языка SQL) язык основывается на некоторой смеси алгебраических и логических конструкций. Тем не менее, знание алгебраических и логических основ языков баз данных часто бывает полезно на практике.

Обзор реляционной алгебры

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

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

Далее рассмотрим основы реляционной алгебры.

Объединение

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

Синтаксис: A UNION B

Замечание. Объединение, как и любое отношение, не может содержать одинаковых кортежей. Поэтому, если некоторый кортеж входит и в отношение A, и отношение B, то в объединение он входит один раз.

Пример: Пусть даны два отношения A и B с информацией о сотрудниках (табл 3, 4).

Таблица 3. Отношение A Таблица 4. Отношение В

ИД_Сотр	Фамилия	Зарплата		ИД_Сотр	Фамилия	Зарплата
1	Иванов			1	Иванов
2	Путин			2	Пушнин
3	Сидоров			3	Сидоров

 

Объединение отношений A и B будет иметь вид:

ИД_Сотр	Фамилия	Зарплата
	Иванов
	Путин
	Сидоров
	Иванов
	Пушнин

 

Замечание. Как видно из приведенного примера, первичные ключи, которые были в отношениях A и B не наследуются объединением этих отношений. Поэтому, в объединении отношений A и B атрибут "ИД_Сотр" может содержать дубликаты значений. Если бы это было не так, и ключи наследовались бы, то это противоречило бы понятию объединения как "объединение множеств". Конечно, объединение отношений A и B имеет, как и любое отношение, первичный ключ, например, состоящий из всех атрибутов.

Пересечение

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

Синтаксис операции пересечения: A INTERSECT B

Пример 3. Для тех же отношений A и B (табл. 3, 4) пересечение имеет вид:

ИД_Сотр	Фамилия	Зарплата
	Сидоров

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

Вычитание

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

Синтаксис операции вычитания: A MINUS B

Пример 4. Для отношений A и B, что и в предыдущем примере вычитание имеет вид:

ИД_Сотр	Фамилия	Зарплата
1	Иванов
2	Путин

 

Декартовым произведением двух отношений A (A1, A2,… An) и B (B1, B2,… Bm) называется отношение, заголовок которого является сцеплением заголовков отношений A и B: (A1, A2,… An, B1, B2,… Bm), а тело состоит из кортежей, являющихся сцеплением кортежей отношений A и B: (a1, a2, … an, b1, b2,… bm), таких, что (a1, a2, … an)Î A, (b1, b2,… bm)Î B.

Синтаксис операции декартового произведения: A TIMES B

Замечание. Мощность произведения A TIMES B равна произведению мощностей отношений A и B, т.к. каждый кортеж отношения A соединяется с каждым кортежем отношения B.

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

Замечание. Перемножать можно любые два отношения, совместимость по типу при этом не требуется.

Пример 5. Пусть даны два отношения A и B с информацией о сотрудниках и должностях (табл. 5, 6).

Таблица 5. Отношение A (Сотрудники) Таблица 6.Отношение B(Должности)

ИД_Сотр	Фамилия	Стаж		ИД_Д	Должность	Зарплата
1	Иванов			1	Профессор
2	Путин			2	Доцент
3	Сидоров			3	Ассистент

 

Декартово произведение отношений A и B будет иметь вид:

ИД_Сотр	Фамилия	Стаж	Ид_Д	Должность	Зарплата
	Иванов			Профессор
	Иванов			Доцент
	Иванов			Ассистент
	Путин			Профессор
	Путин			Доцент
	Путин			Ассистент
	Сидоров			Профессор
	Сидоров			Доцент
	Сидоров			Ассистент

 

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

WHERE

ЭЛЕМЕНТЫ.НОМ_ЭЛЕМЕНТА=ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ.НОМ_ЭЛЕМЕНТА

AND ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ.ПРОЦЕНТ>90;

Невыразимость транзитивного замыкания реляционными операторами

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

Кросс-таблицы

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

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

Таблица 29 Данные о продажах

Товар	Месяц	Количество
Компьютеры	Январь
Принтеры	Январь
Сканеры	Январь
Компьютеры	Февраль
Принтеры	Февраль
Сканеры	Февраль
…	…	…

 

Требуется представить эти данные в виде таблицы, по строкам которой идут наименования товаров, по столбцам - месяцы, а в ячейках содержатся объемы продаж. Это и будет кросс-таблицей:

Таблица 30 Кросс-таблица

Товар	Январь	Февраль	…
Компьютеры			…
Принтеры			…
Сканеры			…

 

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

Проектирование БД

Цели и этапы проектирования

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

Отдельные БД, которые объединяют все данные, необходимые для решения одной или нескольких прикладных задач называют прикладными БД,

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

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

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

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

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

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

1. Реляционная модель данных - удобный способ представления данных предметной области.

2. Язык SQL - универсальный способ манипулирования такими данными.

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

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

Аномалии вставки (INSERT)

В отношение «Университет » нельзя вставить данные о сотруднике, который пока не ведет ни одну дисциплину (занятие). Действительно, если, например, на кафедре «ИЗИ» появляется новый сотрудник, Пушкин, и он пока не читает ни одну дисциплину, то мы должны вставить в отношение кортеж <ИЗИ, 317442,, null, null, Пушкин>. Это сделать невозможно, т.к. атрибуты Caf, Disp, Cat входит в состав потенциального ключа, и, следовательно, не может содержать null-значений.

Точно также нельзя вставить данные о новой кафедре.

Причина аномалии - хранение в одном отношении разнородной информации (и о сотрудниках, и о дисциплинах, и о видах занятий).

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

Аномалии удаления (DELETE)

При удалении некоторых данных может произойти потеря другой информации. Например, если закрыть кафедру "ИСИМ" и удалить все строки, в которых она упоминается, то будут потеряны все данные о дисциплине «ЗИ» и частично о сотруднике «Алешкине» и т.п.

Причина аномалии - хранение в одном отношении разнородной информации (и о сотрудниках, и о дисциплинах, и о кафедрах).

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

Теория нормализации

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

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

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

Основа нормализации – аппарат нормализации отношений.

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

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

Формы нормализации:

• первая нормальная форма (First Normal Form – 1NF);
• вторая нормальная форма (Second Normal Form – 2NF);
• третья нормальная форма (Third Normal Form – 3NF);
• нормальная форма Бойса-Кодда (Boice-Codd Normal Form – BCNF);
• четвертая нормальная форма (Fourth Normal Form – 4NF);
• пятая нормальная форма или нормальная форма проекции-соединения (Fifth Normal Form – 5NF или PJ/NF);

Теория нормализации основывается на наличии той или иной зависимости между атрибутами отношения.

Виды зависимостей:

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

Для устранения указанных аномалий (а на самом деле для правильного проектирования модели данных!) применяется метод нормализации отношений. Нормализация основана на понятии функциональной зависимости атрибутов отношения^

1) Пусть R - отношение. Множество атрибутов Y функционально зависимо от множества атрибутов X (X функционально определяет Y) тогда и только тогда, когда для любого состояния отношения R для любых кортежей r1,r2Î R из того, что r1X=r2X следует что r1Y=r2Y (т.е. во всех кортежах, имеющих одинаковые значения атрибутов X, значения атрибутов Y также совпадают в любом состоянии отношения R). Символически функциональная зависимость записывается X ® Y.

Замечание. Если атрибуты X составляют потенциальный ключ отношения R, то любой атрибут отношения R функционально зависит от X.

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

{Caf} ® Phone

{ Disp } ® Cat

Замечание. Приведенные функциональные зависимости не выведены из внешне