Содержание

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

1. Общие теоретические положения

1. Основные определения

     Систематическая организация данных и способов их обработки осуществляется в банках данных. Банк данных = база данных + СУБД.

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

     Элемент описания - наименьшая единица описания в базе данных. Совокупность элементов описания, объединенных отношением принадлежности к одному объекту называется записью.

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

1. Сокращение избыточности информации.
2. Обеспечение целостности информации. Целостность - свойство базы данных в любой момент времени содержать только достоверные данные.
3. Разграничение доступа к информации.
4. Обеспечение независимости представления данных. Независимость представления данных - независимость физического и логического представления информации.

2. Понятие “Ключ”

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

     Кортеж  должен обладать двумя свойствами:

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

3. Понятие «нормализации»

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

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

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

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

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

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

4. Понятие "сущность" и "связь"

     Сущность – некоторый объект или процесс предметной области, который может быть идентифицирован некоторым образом.

     Набор сущностей – множество сущностей одного типа. Сущность представляет из себя множество атрибутов.

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

     Связь – некоторая ассоциация установленная между несколькими сущностями.

     Набор связей – некоторое отношение между n-сущностями.

     Если  объединять 2 сущности – бинарная связь. Если больше двух n-арная связь.

2. Общесистемный раздел

1. Модели  данных.

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

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

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

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

1. Иерархическая МД;
2. Сетевая МД;
3. Реляционная МД.

2.   Иерархические системы

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

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

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

     Эта модель данных является самой быстрой. Как показано на Рис.1 все связи  идут строго сверху вниз, что соответствует  структуре «дерева». Это обеспечивает быстрый и достоверный поиск  необходимой информации.

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

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

3. Сетевые системы

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

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

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

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

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

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

      Таблица 1.1

3. Представление данных с помощью  модели сущность-связь (ER- модель).

     На  использовании разновидностей ER-модели основано большинство современных  подходов к проектированию баз данных (главным образом, реляционных). ER- модель основывается на некоторой важной семантической информации о предметной области предназначенная для логического представления данных. Является наиболее общей моделью и от нее могут быть поражены все остальные модели данных. ER- модель разработал Питер Чен в 1976 году. Любой фрагмент может быть представлять множество сущностей между которыми множество связей.

1. Нормальные  формы ER-схем

     Как и в реляционных схемах баз  данных, в ER-схемах вводится понятие  нормальных форм, причем их смысл очень  близко соответствует смыслу реляционных  нормальных форм. Заметим, что формулировки нормальных форм ER-схем делают более понятным смысл нормализации реляционных схем.

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

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

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

2. Получение реляционной схемы  из ER-схемы

     Шаг 1. Каждая простая сущность превращается в таблицу. Простая сущность - сущность, не являющаяся подтипом и не имеющая подтипов. Имя сущности становится именем таблицы.

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

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

     Шаг 4. Связи многие-к-одному (и один-к-одному) становятся внешними ключами. Т.е. делается копия уникального идентификатора с конца связи "один", и соответствующие столбцы составляют внешний ключ. Необязательные связи соответствуют столбцам, допускающим неопределенные значения; обязательные связи - столбцам, не допускающим неопределенные значения.

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

4. Проектирование  реляционных БД

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

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

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

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

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

     какие атрибуты должны быть у этих отношений.

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

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

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

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

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

• первая нормальная форма (1NF);
• вторая нормальная форма (2NF);
• третья нормальная форма (3NF);
• нормальная форма Бойса-Кодда (BCNF);
• четвертая нормальная форма (4NF);
• пятая нормальная форма, или нормальная форма проекции-соединения (5NF или PJ/NF).

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

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

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

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

     Таблица, находится в 1НФ тогда и только тогда, когда ни одна из ее записей:

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

     Таблица, находящаяся во 2НФ должна удовлетворять следующим требованиям:

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

     Таблица, находящаяся в 3НФ должна удовлетворять следующим требованиям:

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

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

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

2. Специальная часть

1. Описание  предметной области

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

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

     Разделы, рубрики и подрубрики имеют свое наименование и обладают номером  или кодом. Каждая рубрика имеет номер, кратный, например, десяти, а все подрубрики, входящие в рубрику, имеют коды в пределах этого десятка. Аналогично, разделы имеют «базовый» номер, кратный ста. Не допускается существование пустых (без рубрик) разделов и рубрик (без подрубрик), пустые же подрубрики (без объявлений) допускаются.

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

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

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

     Объявление  имеет текст. Оно может быть платным  или бесплатным. Для платных объявлений указывается способ оплаты.

2. Исследование  предметной области и разработка модели

     Итак, рассмотрим подробнее предметную область  и перейдём к построению модели. Для представления данных предметной области в реляционной базе данных удобнее сначала построить модель «сущность-связь» (далее ER-модель). Построим её используя нотацию IDEF1X. Для этого выделим в предметной области сущности и связи.

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

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

     Итак, иерархия сущностей такова:

1. разделы содержат рубрики
2. рубрики содержат подрубрики
3. подрубрики имеют часто используемые слова и включают объявления
4. способы оплаты определены для объявлений
5. типы выпусков определены для выпусков
6. выпуски хранят объявления, объявления принадлежат выпускам
7. объявления содержат способы связи
8. адреса, телефоны и электронные адреса являются видом способа связи для способов связи
9. способы связи ссылаются на контактные лица

     Рассмотрим теперь тип каждой связи. Итак, выделены виды связи: содержат, имеют, включают, определены для, хранят/принадлежат, указаны для, ссылаются на. Они различаются типом и кардинальностью.

     Так, например, связи 1 и 2 имеют вид «содержат». Это очевидно из предметной области, так как разделы не могут существовать без одной или нескольких рубрик, а рубрики, в свою очередь – без подрубрик. Аналогичный вид применён для связи 7, так как для каждого объявления обязательно указывается один или несколько способов связи. Таким образом, данный вид связи будет идентифицирующей связью с кардинальностью 1,M.

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

     Связи 4 и 5 «определены для» подразумевают, что родительские сущности используются как справочники. Поскольку элемент справочника может существовать без указания его где-либо, то родительская сущность будет независимой, а, следовательно, и связь – неидентифицирующая. Каждый элемент справочника может быть указан в нескольких записях, каждая запись должна ссылаться на один, и только на один элемент справочника. Связь – неидентифицирующая с кардинальностью 1,M.

     Связь 6 имеет вид «хранят/принадлежат». Исходя из предметной области объявление может выходить в нескольких выпусках, каждый выпуск включает множество объявлений. Объявления не могут существовать без выпусков, в которых выходят, выпуски не существуют без объявлений. Отсюда - идентифицирующая связь «много к многому».

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

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

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

     Итак, графическое представление схемы  модели, описанной выше, исполненное в AllFusion ERWin 4.1 представлено на рисунке.

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