Краткие итоги. Зачем нужна нормализация

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

13.Физические структуры данных.

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

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

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

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

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

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

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

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

Рис. 2.12. Линейная структура текстового файла

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

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

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

Такой подход применяется в широко используемых для создания «настольных информационных систем» (системы «рабочего стола») СУБД куста dBASE (dBase, FoxPro, C l ipper), которые создают и оперируют базами данных в формате так называемых dbf-файлов. Структура dbf-файла состоит из трех частей* — заголовка, блока описания структуры базы и информационной части (см. рис. 2.13). В заголовке последовательно представлены поля, которые определяют тип файла базы данных (с memo-полями или без них), дату последнего изменения, номер последней записи, смещение, с которого начинается информационная часть (записи), размер каждой записи. Блок описания структуры размещается после заголовка до информационной части и состоит из последовательности элементов, каждый из которых описывает определенное поле логической структуры (схемы) базы данных. Структура описания поля содержит последовательное описание имени поля, типа поля (числовое, текстовое, дата и т. д.), длины поля и заканчивается специальным символом для отделения описания одного поля от другого. Информационная часть состоит из последовательности групп байтов одинаковой длины без специальных разделителей, каждая из которых собственно и выражает содержимое конкретной физической записи.

Рис. 2.13. Линейная структура dbf-файла

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

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

Рис. 2.14. Нелинейная структура данных ни примере односвязного списка (поля указателей выделены жирными рамками)

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

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

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

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

Рис. 2.15. а. Пример нелинейной древовидной иерархической структуры данных

Если в процессе ведения базы данных какая-либо страница переполняется, то для нее образуется связанная страница-продолжение на основе техники односвязного списка.*

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

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

Однако во многих предметных областях АИС отношения между информационными объектами могут порождать ситуации наличия у определенных записей на стороне «Многие» сразу нескольких разных предков на стороне «Один» (см., например, рис. 2.3), что не вписывается в рамки подобных древовидных иерархических структур. Решение таких проблем обычно осуществляется через введение избыточности (дублирования) данных по связанным записям или другими способами.

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

* Деревом называется связный неориентированный граф без циклов (см., например Лекции по теории графов / Емелнчев В. А., Мельников О. И., Сарванов В.И., Тышкевич Р.И.—М.: Наука, 1990, или Асанов М.О. Дискретная оптимизация: Учебное пособие. —Екатеринбург: УралНАУКА, 1998.

Рис. 2.15, 6. Условное изображение средствами теории графов нелинейной древовидной иерархической структуры

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

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

14. Языки баз данных

База данных (БД) – сами данные, находящиеся в памяти ЭВМ и каким-либо образом структурированные. Система управления базой данных (СУБД) – совокупность программных средств, с помощью которых осуществляется управление базой данных и доступ к данным (запись данных, их выборка по запросам пользователей и прикладных программ, защита данных от искажений и несанкционированного доступа). Для работы с базами данных используются специальные языки баз данных. Чаще всего выделяется два языка: – язык определения данных (ЯОД) – служит для определения логической структуры БД; – язык манипулирования данными (ЯМД) – содержит набор операторов манипулирования данными (добавление данных в БД, удаление, модификация, выборка и т.д.). Во многих СУБД обычно поддерживается единый интегрированный язык, содержащий все необходимые средства для работы с БД, начиная от ее создания, и обеспечивающий базовый пользовательский интерфейс с базами данных. Стандартным языком реляционных СУБД является язык SQL (Structured Query Language, query – вопрос) – структурированный язык запросов, оперирует не отдельными записями, а группами записей. Реляционные СУБД (relation – отношение): 1970 г., показана возможность управления данными благодаря их описанию в терминах математической теории отношений – гибкая и простая реляционная модель данных стала доминирующей среди разработчиков и пользователей СУБД. Объектно-реляционные БД – объектно-ориентированные возможности (определение новых типов данных и функций их обработки) встраиваются в реляционное основание. Язык SQL сочетает средства ЯОД и ЯМД, то есть позволяет определять схему реляционной БД и манипулировать данными. Использование языка SQL обеспечивает: организацию данных – возможность изменять структуру представления данных, устанавливать соотношения между элементами БД; чтение данных (пользователем или приложением); обработку данных – добавление новых данных, удаление, модификация; управление доступом – ограничение возможности пользователя по чтению и изменению данных и защита их от несанкционированного доступа; целостность данных – защита БД от разрушения в результате несогласованных действий или отказа системы; совместное использование данных – пользователями, работающими параллельно (чтобы они не мешали друг другу).

15. Индексирование данных.

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

Как и для информационных массивов самих данных (таблиц), так и для индексных массивов применяются линейные и нелинейные структуры. В качестве линейных структур индексов в большинстве случаев выступают инвертированные списки. Инвертированный список строится по схеме таблицы с двумя колонками — «Значение индексируемого поля» и «Номера строк»* (см. рис. 2.16). Инвертированные списки чаще всего применяются для индексации полей, значения которых в разных строках-записях могут повторяться, к примеру, поле «Год рождения» таблицы «Сотрудники» (в реляционных базах данных такие поля не могут быть ключевыми).

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

Значение индексируемого поля ("Год рождения")	Номера, строк
	5, 17, 123, 256
	31, 32, 77
	11, 45, 58, 167, 231
	7, 8, 9, 10, 234, 235, 236

Рис. 2.16. Пример инвертированного списка

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

* Способы поиска в линейно упорядоченных структурах см., например, в работе: Вирт Н.. Алгоритмы и структуры данных: Пер. с англ.—М.: Мир, 1989.

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

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

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

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

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

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

где: Х _i – i-е значение индексируемого поля, при этом Х _i J X _{i+ 1} – указатель на вершину, содержащую значения индексируемого поля, меньшие или равные X _i.

Рис. 2.17. Структура внутренней вершины Б-дерева

Число n называется порядком Б-дерева.

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

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

Рис. 2.18. Структура листовой вершины Б-дерева

Сбалансированность Б-дерева означает одинаковое количество потомков до листовой вершины по любым разветвлениям от корневой вершины. В качестве примера на рис. 2.19 приведено Б-дерево 3-го порядка уровня 2, построенное для поля «Год рождения» таблицы «Сотрудники».

Рис. 2.19. Пример Б-дерева 3-го порядки уровня 2

Как правило, порядок Б-дерева выбирается таким, чтобы информация одной полностью заполненной вершины соответствовала странице файла данных. В силу того что объем одной страницы файлов данных существенно больше размера полей, то в большинстве случаев в одну полностью заполненную страницу вместе с указателями помещается большое количество значений индексируемого поля, исчисляемое сотнями и даже тысячами значений (n >> 100...1000). Это обстоятельство обусловливает сравнительно небольшой уровень Б-деревьев на практике (порядка 2...4) даже в тех случаях, когда количество строк в базовой таблице исчисляется десятками тысяч. В результате доступ к нужной записи по определенному значению индексируемого поля через Б-дерево осуществляется за небольшое количество страничных обменов между внутренней и внешней памятью по следующему алгоритму:

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

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

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

Анализ данного алгоритма показывает, что при поиске нужного значения индексируемого поля по индексу в виде Б-дерева требуется такое количество страничных обменов между внешней и внутренней памятью, которое равно уровню Б-дерева плюс единица. При достаточно большом значении n, а это, как уже отмечалось, наиболее распространенная ситуация, уровень m Б-дерева невелик (m >> 2..3), и, следовательно, количество страничных индексных обменов с памятью также невелико. При этом сбалансированность Б-дерева обусловливает одинаковые затраты по доступу к любой записи с любым значением индексируемого поля. Сбалансированность Б-деревьев обеспечивается легко алгоритмизируемым правилом их построения (роста) при включении нового значения индексируемого поля.

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

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

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

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

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

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

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

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

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

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

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

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

Структура Б-деревьев является эффективным способом индексации больших массивов данных и широко применяется в современных СУБД.