Модуль2_Проектирование БД

На этапе формулировки и анализа требований производится обследование и документирование предметной области (ПО). При этом необходимо выяснить следующее.

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

2.Цели и критерии деятельности лиц, принимающих решение в ПО.

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

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

Для анализа предметной области используются два подхода:

функциональный и предметный.

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

120

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

спомощью графической среды изображения и декомпозиции схем бизнес-

процессов BPWin Process Modeler компании Computer Associates.

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

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

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

Концептуальную схему представляют в виде, диаграммы Чена или ERдиаграммы (или одновременно несколькими моделями) . На данном этапе уместно использовать CASE средства для изображения и документирования

121

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

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

(Oracle, MS SQL Server, SQLBase и др.). При выборе сервера также учитывается стоимость, наличие средств разработки приложений для пользователей и сопровождения базы данных.

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

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

Каждая сущность в схеме данных представляет множество однотипных объектов предметной области и может быть задана своим отношением (таблицей). Атрибуты сущности образуют столбцы таблицы. Свойства атрибутов определяют типы и ограничения данных в столбцах. Особое значение для РБД имеет представление связей между сущностями. Способ представления связи зависит от ее типа. Связи типа «один к одному» (1:1) и «один ко многим» (1:М) между главной и вспомогательной сущностями реализуются добавлением дополнительных столбцов (внешнего ключа) во

122

вспомогательную сущность (М). Внешний ключ содержит значения, являющиеся ссылкой на соответствующий экземпляр главной сущности. В качестве ссылок обычно используется первичный ключ главной сущности. Например, поскольку каждый студент обучается определенной специальности и одной специальности обучается много студентов, связь СПЕЦИАЛЬНОСТЬ → СТУДЕНТ имеет тип 1 : М с главной (сильной) сущностью СПЕЦИАЛЬНОСТЬ и вспомогательной, слабой – СТУДЕНТ. Эта связь создается включением в таблицу, представляющую сущность СТУДЕНТ, дополнительных столбцов, образующих внешний ключ, значения которого содержат ссылку (первичный ключ) на соответствующую строку в таблице специальностей. Многоарные связи и бинарные связи типа «многие ко многим» (М:N) реализуются цепочкой связей 1:М и М:1. Для этого строится вспомогательная таблица, в которой будут размещаться столбцы, содержащие

ссылки на строки связываемых таблиц.	Например,	для реализации связи
«многие ко многим» между авторами	и книгами АВТОР ←→ КНИГА
создается структура из трех таблиц
АВТОР → АВТОРЫ_КНИГ ← КНИГА.
Строки связывающей таблицы АВТОРЫ_КНИГ		будут содержать

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

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

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

В построенных таблицах определяются первичные ключи.

123

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

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

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

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

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

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

Выбираются способы и средства обеспечения надежности (резервирования и восстановления) данных.

Наконец, создаются и исполняются сценарии формирования базы и ее объектов или база строится в диалоговом режиме.

Лекция 16. Основы физической организации БД

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

124

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

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

−файлы последовательного доступа,

−файлы прямого доступа

−индексные файлы:

−с плотным индексом,

−неплотным индексом,

−В-деревья,

−инвертированные списки.

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

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

основными структурами для баз данных.

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

125

положения записи по ее содержимому. Для ее решения существует несколько методов.

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

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

126

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

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

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

127

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

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

Особой разновидностью многоуровневых неплотных индексов являются В-деревья (balanced tree). Суть сбалансированных деревьев в том что, в каждом уровне индекса строятся неплотные индексы, блоки которых содержат одинаковое число строк. Получается полное сбалансированное дерево, количество обращений к блокам которого для поиска записи по значению ключа равно числу уровней индекса. Структура В-дерева показана на рис. 16.1.

Рассмотренные индексы особенно эффективны для первичных ключей.

128

Рис.16.1 Структура индексного сбалансированного дерева (В-дерева)

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

Лекция 17. Современное состояние и перспективы развития БД

Ставшие традиционными РБД имеют ряд принципиальных недостатков, обусловленных особенностями используемой модели данных:

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

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

-способы обработки не принадлежат информационным объектам базы. Поддерживаемые серверами БД хранимые процедуры и функции существуют

129