Максимов Н.В., Голицына О.Л., Васина Е.Н. Управление данными

Подождите немного. Документ загружается.

111

Рис. 4.16б. Пример разделения на связи и данные набора записей

табличного типа (связи)

В разделенном варианте получены три таблицы бинарных отно-

шений для трех вторичных ключей и одна таблица отношений в не ин-

вертированной форме, но упорядоченная по первичному ключу. Каждое

значение элемента данных представлено в одном экземпляре и имеет

идентификатор (порядковый номер - ключ). Связи элементов данных

также выделены в таблицы отдельно.

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

- каждый элемент таблицы – это один элемент данных;

- таблица не содержит одинаковых строк, т.е. содержащих по-

парно равных значений элементов данных;

- столбцы таблицы однородны (т.к. элементы данных каждого

столбца имеют общую природу) и могут быть однозначно идентифици-

рованы именованием.

Для более сложных случаев, например, древовидных структур, для

устранения зависимости от путей вводятся дополнительные ключевые

элементы данных.

Следует отметить, что дублирование некоторых элементов в таб-

лицах является логическим и не обязательно повлечет дублирование на

физическом уровне, так как можно воспользоваться указателями.

Однородность реляционных баз данных, построенных на основе

бинарных отношений, обеспечивает:

Связи

Год рожд

Ф.И.О.

1 4

2 2

3 3

4 11

5 12

6 10

6 13

7 5

7 1

8 14

8 9

9 7

10 8

11 6

Должн

Ф.И.О.

1 6

1 7

1 8

2 14

2 5

2 10

2 13

3 3

3 11

4 12

4 2

4 4

5 9

5 1

Кафедра

Ф.И.О.

1 3

1 12

1 2

1 14

1 5

1 9

1 6

2 11

2 4

2 10

2 13

2 1

2 7

2 8

Ф.И.О

Год

Рожд.

Должн

Каф

№

3 3 3. 1

12 5 4 1

2 2 4 1

14 8 2 1

5 7 2 1

9 8 2. 1

6 11 1 1

11 4 3 2

4 1 4 2

10 6 2 2

13 6 2 2

1 7 5 2

7 9 1 2

8 10 1 2

112

- унифицированность средств работы с базой: необходимы толь-

ко средства для работы с бинарными таблицами;

- простоту расширения состава логической записи.

В тоже время для получения ответа по комплексному запросу не-

обходимо обращаться к нескольким таблицам.

4.4. Архитектура файловой организации баз данных

Файловая структура и система управления файлами являются пре-

рогативой операционной среды, поэтому по отношению к базам данных,

ориентированным на работу с элементами данных и высокую интенсив-

ность обмена, эффективность операций ввода-вывода будет не опти-

мальна: стандартный язык СУБД намного богаче, чем набор операций

файловой системы.

Прямое использование файловой системы для организации хране-

ния и доступа к данным оказывается менее эффективным (отличие со-

ставляет, по крайней мере, 10%), поскольку при выполнении каждого

обращения к диску со стороны СУБД в работу включается дополнитель-

ный слой системного ПО. Хранение данных в файловой системе приво-

дит также к определенной потере емкости памяти. Файловая система,

например Unix, потребляет примерно 10% от форматированной емкости

дисков для метаданных о файлах и файловой системе. Более того, фай-

ловая система резервирует некоторое пространство, чтобы обеспечить

быстрый поиск свободного пространства в случае расширения файлов.

Это послужило причиной того, что СУБД берут на себя непосред-

ственное управление внешней памятью, минимально используя файло-

вую систему ОС.

4.4.1. Файл-ориентированная организация данных

Этот подход отражает точку зрения «идейно чистого» программи-

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

дур, ориентированных на обработку регулярных однородных данных

«сколько типов структур записей - столько и файлов».

Таким образом, БД физически состоит из нескольких файлов: ос-

новного, индексного, файла метаданных, файлов указателей и т.д. Тако-

го типа организация файловой структуры БД представлена в приложе-

нии примерами организации данных dBase-подобных и документальных

баз данных.

Именно такой подход обеспечил возможность реализации надежных достаточно эффективных

СУБД, функционирующих по современным меркам в крайне скромных рамках наличных вычисли-

тельных ресурсов.

113

4.4.2. Страничная организация данных

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

в СУБД управление данными на всех уровнях – от логической обработ-

ки до управления пространством носителя. Создание сложных специа-

лизированных процедур эффективно работающих со сложными нерегу-

лярными структурами данных в сочетании с огромными ресурсами вы-

числительной мощности и оперативной памяти позволили реализовать

даже однофайловую

физическую структуру СУБД.

Приведем примерную логическую схему «страничной» организа-

ции хранения данных.

При распределении дискового пространства рассматриваются сле-

дующая схема структуризации пространства в зависимости от типов

данных:

Экстент — это непрерывная область дисковой памяти, включаю-

щая несколько страниц фиксированной длины. Новый экстент создается

после заполнения предыдущего и связывается с ним ссылкой, которая

располагается на последней странице экстента, либо в специальной кар-

те размещения. Учет свободных страниц ведется внутри экстента.

Каждый экстент используются для хранения одного из нескольких

типов страниц: страницы данных, страницы индексов, страницы blob-

объектов

(неструктурированных данных, например большие текстовые

или двоичные данные). Т.е., данные на одной странице являются одно-

родными: страница, например, может хранить только данные или толь-

ко индексы.

Основной логической единицей операций обмена (ввода-вывода)

является страница данных, хранящая данные в виде строк или других

специализированных структур.

Все страницы данных имеют одинаковую структуру, включаю-

щую:

- Заголовок страницы, содержащий номер страницы, номера пре-

дыдущей и следующей страниц, сведения о свободном пространстве на

странице;

- Содержание – строки данных (последовательность кодов), каж-

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

данных, который состоит из номера страницы и номера строки на стра-

нице;

- Дескрипторы строк, задающие смещение строки на странице и

длину строки, что позволяет при переупорядочении строк на страницах

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

производятся с дескрипторами.

Например, MS ACCESS.

Для СУБД важно знать, что этот объект надо хранить целиком и что размеры этих объектов от за-

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

114

Для организации быстрого доступа создаются страницы индексов,

которые организованы обычно в виде В-деревьев.

Рис. 4.17. Файл-ориентированная и страничная организация данных

4.5. Модели распределения данных по физическим носителям

Важным фактором, влияющим на производительность подсистемы

ввода-вывода, является распределение данных по дискам. Даже мини-

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

крайней мере четыре диска: один для операционной системы и области

подкачки (swap), один для данных, один для журнала и один для индек-

сов.

Размещение всех данных БД на одном и том же диске почти всегда

приводит к неудовлетворительной производительности. В частности,

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

записываться синхронно, в действительности будет выполняться в ре-

жиме произвольного, а не последовательного доступа к диску. Уже

только эта операция будет существенно задерживать каждую транзак-

цию обновления базы данных.

Кроме того, выполнение запросов, выбирающих записи из табли-

цы данных путем последовательного сканирования индекса, будет силь-

но увеличивать время ожидания ввода-вывода. Обычно сканирование

индекса выполняется последовательно, но в данном случае головка дис-

ка должна перемещаться для поиска каждой записи данных между вы-

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

функций на одних и тех же физических ресурсах приводит к резкому

увеличению времени подвода головок на диске.

Файл-ориентированная организация

данных

Страничная организация данных

Данные

Индексы

Метаданные

«Сколько типов структур записей –

столько и файлов»

Указатели

Содержание

Дескрипторы

Заголовок

Стр1

Стр2

…

СтрN

…

115

Примером, иллюстрирующим подход с точки зрения практических

компромиссов выбора решения, являются RAID-массивы. На рис. 4.18

приведены два варианта: RAID-0, обеспечивающий максимальную про-

изводительность при «стандартной» надежности, и RAID-1, обеспечи-

вающий «двойную» надежность при «стандартной» производительно-

сти.

119 8 7 6 5 4 3 2 1

Физические диски

Логический файл

Время

чтения

Оче

RAID-0

самая высокая произ-

водительность при

низкой стоимости

Время установки головок чте-

ния-записи

Физический

диск

12 11 10 9 8 7 6 5 4 3 2 1

…

Логический файл

Время установки головок

чт

ния

записи

Зеркальный

физический

диск

Наивысшая отказоустойчивость

Время

чт

ния

RAID-1

Рис. 4.18. Распределение данных в RAID-массивах

116

Системы управления базами данных применяют по крайней мере два

механизма для распределения данных по дисковым накопителям. Для эф-

фективного распределения доступа к данным многие СУБД имеют воз-

можность осуществлять сцепление нескольких дисковых накопителей или

файлов. Если по запросам производится произвольный доступ к данным,

например, если пользователи независимо запрашивают разные записи, то

возможности сцепления дисков в СУБД полностью обеспечивают распре-

деление нагрузки по доступу к множеству дисков (при достаточно равно-

мерном заполнении пространства базы). Если обращения по своей природе

последовательны, в частности если один или несколько пользователей

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

ханизм расщепления дисков. Главное отличие между сцеплением и расще-

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

ляются друг с другом, последовательное сканирование представляет собой

тяжелую нагрузку для каждого из дисков, но эта нагрузка носит последова-

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

Расщепление дисков осуществляет деление данных на меньшие порции,

размещаемые на разные диски, позволяя тем самым всем дискам участво-

вать в обслуживании даже сравнительно небольшого запроса. В результате

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

выполнении последовательного доступа. Основными кандидатами для

расщепления являются обычно архивные и журнальные файлы, поскольку

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

чить общую производительность системы.

Контрольные вопросы

1. Перечислите типы физических записей. Приведите примеры, по-

казывающие соотношение физических и логических записей.

2. Перечислите факторы, влияющие на выбор метода размещения

данных (организацию файла).

3. Перечислите методы организации файлов, позволяющих оптими-

зировать доступ к записям.

4. Приведите пример организации данных в виде индексно-

последовательного файла.

5. Какие типы указателей можно использовать для реализации ие-

рархической структуры.

6. Какие типы указателей можно использовать для реализации сете-

вой структуры с последовательным размещением.

7. Придумайте схему реализации сетевой структуры для случая час-

то изменяемых данных.

8. Какие методы организации данных, применяемые для реализации

иерархических структур, неэффективны для реализации сетевых?

9. Приведите примерную структурную схему «страничной» органи-

зации хранения данных.

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

нием механизма расщепления.

117

Глава 5. Модели и этапы проектирования баз данных

5.1. Модели многоуровневой архитектуры систем баз данных

В области проектирования и разработки систем баз данных ис-

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

одной конкретной системы необходим целый комплекс моделей разного

назначения.

Опубликованный в 1975 году отчет ANSI/X3/SPARC зафиксиро-

вал не только широкое признание концепций многоуровневой архитек-

туры систем баз данных, но и необходимость явного выделения специ-

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

для всех ее приложений и независимого от них. Кроме этого уровня

предусматривались еще два уровня: внутренний уровень, который дол-

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

внешний, поддерживающий представления базы данных “с точки зре-

ния” приложений. На каждом архитектурном уровне предполось ис-

пользование той или иной модели данных. Кроме того, на внешнем

(прикладном, пользовательском) уровне таких моделей может быть не-

сколько. Модели, а также схемы, специфицируемые на их основе, назы-

ваются, соответственно, внешней, концептуальной и внутренней.

Как очевидно конечной целью проектирования является построе-

ние конкретной базы данных, в той или иной степени воплощающей

представление проектировщика о предметной области и задачах, решае-

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

базу данных как конкретную реализацию модели, мы по существу ус-

танавливаем порядок процесса, отделяя этап определения принципов

(то, какой база должна быть) от этапа воплощения этих принципов при

реализации базы данных в конкретной среде СУБД, ОС и языках про-

граммирования. И, как показывает практика, между реализациями баз

данных и принципами их построения всегда есть расхождения. Различия

являются следствием разных причин, но чаще всего - это явный или не-

явный отказ от некоторых принципиальных ограничений, налагаемых,

например, моделью данных или базовыми (встроенными) алгоритмами

обработки, в пользу частного решения, которое, по мнению проекти-

ровщика, будет более эффективно, например, для понимания или обра-

ботки данных.

Важность отделения проектирования на абстрактном уровне от

физической реализации состоит в том что, объявляя принципы, мы кон-

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

и сложность задачи должна быть сокращена до такого уровня, чтобы

реализация стала возможной в данных конкретных условиях – ресурсах

среды, профессионализме проектировщика, подготовленности пользова-

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

118

значена для многофункционального использования различными пользо-

вателями, и в тоже время - для обслуживания запросов, не предвиденных

при проектировании, такое явное объявление принципов позволит не

вводить в заблуждение пользователя и не создавать приложения для ре-

шения задач, которые в силу своего принципиального отличия от тех,

которые рассматривались при проектировании, обусловят неэффектив-

ную обработку данных

Проектирование базы данных - это упорядоченный формализован-

ный процесс создания системы взаимосвязанных описаний

, т.е. таких

моделей предметной области, которые связывают (фиксируют) храни-

мые в базе данные с объектами предметной области, описываемыми

этими данными. Прикладное назначение таких описаний состоит в том,

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

зации данных в БД (физическом размещении в памяти данных и меха-

низмах их поиска), обращая запрос к базе, имел бы практическую воз-

можность получить адекватную информацию о состоянии объекта

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

Проектирование начинается с анализа предметной области и вы-

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

ме. Подробнее этот процесс будет рассмотрен ниже, а здесь отметим,

что проектирование обычно выполняется человеком (группой людей) –

системным аналитиком (а на практике чаще администратором базы дан-

ных), которым может быть как специально выделенный сотрудник, так и

будущий пользователь базы данных, достаточно хорошо знакомый с

машинной обработкой данных.

Объединяя отдельные представления о содержимом базы данных,

полученные в результате опроса пользователей, и свои представления о

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

системный аналитик сначала создает обобщенное неформальное описа-

ние создаваемой базы данных. Это описание, выполненное с использо-

ванием естественного языка, математических выражений, таблиц, гра-

фов и других средств, понятных всем людям, работающим над проекти-

рованием базы данных, называют инфологической моделью.

Такая человеко-ориентированная модель практически полностью

независима от физических параметров среды хранения данных, которой

может быть как память человека, так и ЭВМ. Поэтому инфологическая

Применяемые формальные языки представления предметной области не позволяют описывать все

отношения, которые проектировщик считает важными. С другой стороны, многие проекты (и, в част-

ности, рассматриваемые примеры) воспринимаются как достаточно простые, а проектные решения

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

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

нужной информации. Однако это означает отказ от единого формализма, что при увеличении коли-

чества данных и связей значительно усложняет проблемы управления базой и в частности – понима-

ние пользователем организации и методов доступа.

Такие описания реализуются, например, в виде схем.

119

модель не изменяется до тех пор, пока какие-то изменения в реальном

мире (той его части, которая отнесена к предметной области) не потре-

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

эта модель продолжала адекватно отражать предметную область.

Остальные модели являются машинно-ориентированными. С их

помощью СУБД дает возможность программам и пользователям осуще-

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

физическом расположении этих данных.

Так как доступ к данным осуществляется с помощью конкретной

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

этой СУБД. Такое описание, создаваемое по инфологической модели

данных, называют даталогической моделью данных.

Для размещения и поиска данных на внешних запоминающих уст-

ройствах СУБД использует физическую модель данных.

Представленная трехуровневая архитектура (инфологический, да-

талогический и физический уровни) позволяет обеспечить независи-

мость хранимых данных от использующих их программ. Хранимые дан-

ные могут быть переписаны на другие носители или может быть реорга-

низована их физическая структура, в том числе дополнена полями для

новых приложений, но это повлечет лишь изменение физической и, воз-

можно, даталогической модели данных. Главное, такие изменения физи-

ческой и даталогической моделей не будут замечены существующими

пользователями системы (окажутся "прозрачными" для них) так же, как

не будут замечены и вновь подключаемые пользователи. Кроме того, не-

зависимость данных обеспечивает возможность создания новых прило-

жений для решения новых задач без разрушения существующих.

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

данных” имел разное содержание. Для более глубокого понимания су-

щества отдельных понятий рассмотрим некоторые особенности исполь-

зования этого понятия в контексте эволюции баз данных, представлен-

ные в [11].

О понятии «модель данных». Первоначально понятие модели

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

зе данных. Структурная трактовка полностью согласовывалась с мате-

матическим определением понятия модели как множества с заданными

на нем отношениями. Но, следует отметить, что объектом моделирова-

ния в данном случае являются не данные вообще, а конкретная база дан-

ных. Разработки новых архитектурных подходов, основанных на идеях

многоуровневой архитектуры СУБД, показали, что уже недостаточно

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

Требовалось решение на метауровне, позволяющее оперировать множе-

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

заданной СУБД или, что эквивалентно, инструментальными средствами,

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

ность в термине, который обозначал бы инструмент, а не результат мо-

120

делирования, и соответствовал бы, таким образом, множеству всевоз-

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

баз данных должен включать не только средства структурирования дан-

ных, но и средства манипулирования данными. Поэтому модель данных

в инструментальном смысле стала пониматься как алгебраическая сис-

тема – множество всевозможных допустимых типов данных, а также оп-

ределенных на них отношений и операций. Позднее в это понятие стали

включать еще и ограничения целостности, которые могут налагаться на

данные. В результате проблема отображения данных в многоуровневых

СУБД и системах распределенных баз данных стала рассматриваться как

проблема отображения моделей данных.

Важно подчеркнуть, что для разработчиков и пользователей СУБД

точным определением реализованной в ней модели данных фактически

являются языковые средства определения данных и манипулирования

данными. Поэтому отождествлять такой язык со схемой базы данных

(результатом моделирования) – конкретной спецификацией в этом языке

– неправомерно.

Начиная с середины 70-х годов, под влиянием предложенной в тот

период концепции абстрактных типов само понятие типа данных в

языках программирования стало трансформироваться таким образом,

что в него стали вкладывать не только структурные свойства, но и эле-

менты поведения (изменения данных). В дальнейшем это послужило ос-

новой для формирования концепции объекта, на которой базируются со-

временные объектные модели.

В связи с этим был предложен новый подход, при котором модель

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

естественные возможности интеграции баз данных и языков программи-

рования, способствовал формированию направления, связанного с соз-

данием так называемых систем программирования баз данных. Трактов-

ке модели данных как системы типов соответствуют не только уже су-

ществующие широко используемые модели, но также объектные моде-

ли, завоевывающие все большее влияние.

О развитии и конкурировании моделей. По аналогии с ситуаци-

ей 70-х годов, когда велись споры о преимуществах сетевой, иерархиче-

ской и реляционной модели данных (как известно, завершившиеся “ни-

чейным” исходом открытой дискуссии Ч.Бахмана и Э.Кодда на Конфе-

ренции ACM SIGMOD в 1975 году), в настоящее время сформировалась

новая тройка конкурентов – реляционная, объектная и многомерная мо-

дели.

Хотя, строго говоря, здесь речь идет лишь о двух моделях. Дейст-

вительно, многомерные модели, коммерческие реализации которых поя-

вились в начале 90-х годов для поддержки технологий OLAP, не основа-

ны на каких-либо радикально новых идеях. Они представляют собой не-

которое расширение активно исследовавшейся в 70-80-х годах модели

универсальных отношений новыми операционными возможностями,