2.3. Внутренняя схема баз данных фактографических аис

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

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

Рис. 2.10. Cocтаввнутренней схемы базы данных

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

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

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

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

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

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

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

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

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

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

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

Рис. 2.11. Общий принцип организации внутренней схемы базы данных

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

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

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

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

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

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

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

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

* Спенс Р. Сliрреr. Руководство по программированию. Версия 5.01 / Пер. с англ — Мн.: Tивали, 1994-480 с (с.428).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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