Московский государственный университет печати

Чертовской В.Д.


         

Базы и банки данных

Учебное пособие


Чертовской В.Д.
Базы и банки данных
Начало
Печатный оригинал
Об электронном издании
Оглавление

Введение

Часть 1. ОСНОВНЫЕ ПОЛОЖЕНИЯ

Раздел 1. Основные понятия

1.

Глава 1. Общие сведения

1.1.

Данные, информация, знания

1.2.

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

1.3.

Классификация БД и СУБД

1.4.

Состав СУБД и работа БД

2.

Глава 2. Концепция баз данных

2.1.

Требования, предъявляемые к базам данных

2.2.

Концепция построения БД

2.3.

Методология проектирования баз данных

2.4.

Методология использования баз данных

Раздел 2. Теория баз данных

3.

Глава 3. Общая теория

3.1.

Модели представления данных

3.2.

CASE-технология

3.3.

CASE-средства

4.

Глава 4. Теория реляционных баз данных

4.1.

Математические основы теории

4.2.

Построение БД

4.3.

Использование БД

4.3.1.

Запросы к данным

4.3.2.

Синхронизация процессов доступа

Часть 2. Централизованные базы данных

Раздел 3. Реализация бд (модели БД)

5.

Глава 5. Реляционные БД SQL

5.1.

Логическая структура

5.2.

Создание БД

5.3.

Использование БД

5.3.1.

Язык SQL

5.3.2.

Язык QBE

6.

Глава 6. Сетевые БД

6.1.

Логическая структура

6.2.

Программная реализация

6.2.1.

Создание БД (ЯОД)

6.2.2.

Использование БД (ЯМД)

7.

Глава 7. Иерархические БД

7.1.

Логическая структура

7.2.

Программная реализация

7.2.1.

Создание БД (ЯОД)

7.2.2.

Использование БД (ЯМД)

8.

Глава 8. Взаимосвязь МД

8.1.

Сравнительная характеристика моделей данных

8.2.

Преобразование моделей данных

8.3.

Выбор моделей данных

9.

Глава 9. Физическая БД

9.1.

Вопросы программной реализации БД

9.2.

Организация хранения и доступ

9.3.

Доступ к данным и их обновление

Раздел 4. Современные направления развития БД

10.

Глава 10. Автоматизация проектирования

10.1.

Классический подход к проектированию

10.1.1.

Однопользовательский режим

10.1.2.

Многопользовательский режим

10.2.

Современный подход к проектированию

10.3.

Автоматизация проектирования

11.

Глава 11. Объектно-ориентированные базы данных

11.1.

Недостатки реляционных баз данных

11.2.

Состояние развития ООБД

11.3.

Сущность ООБД

11.4.

Недостатки и перспективы развития ООБД

Часть 3. Распределенные базы данных (РБД)

Раздел 5. Основы теории РБД

12.

Глава 12. Общая характеристика РБД

12.1.

Новые требования, предъявляемые к БД

12.2.

Состав и работа РБД

12.3.

Система клиент/сервер

Раздел 6. Основы теории РБД

13.

Глава 13. Создание РБД

13.1.

Обеспечение целостности

13.2.

Фрагментация и локализация

13.3.

Процесс интеграции

13.4.

Преобразование структуры и данных

13.5.

Однородные и неоднородные РБД

14.

Глава 14. Использование РБД

14.1.

Одновременный доступ

14.2.

Защита

14.3.

Восстановление РБД

14.4.

Запросы

Заключение

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

Литература

Указатели
11  именной указатель
360  предметный указатель
163  указатель иллюстраций
25  указатель компаний

9.
Глава 9. Физическая БД

9.1.
Вопросы программной реализации БД

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

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

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

Режим 1. Получить все данные (последовательная обработка).

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

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

К База данных физическаяфизической модели предъявляются два основных противоречивых требования:

    1) высокая скорость доступа к данным;

    2) простота обновления данных.

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

Введем необходимые дополнительные термины.

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

Если одно и то же поле используется в индексе и для упорядочения записей файла, то индекс называют Индекс основнойосновным, а файл - Файл индексно-последовательныйиндексно-последовательным. В противном случае индекс называют Индекс вторичныйвторичным.

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

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

9.2.
Организация хранения и доступ

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

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

Эффективность храненияЭффективность хранения - величина, обратная среднему числу байтов вторичной памяти, необходимому для хранения одного байта исходной памяти.

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

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

Применительно к иерархической МД основные методы получили свои названия и аббревиатуры (рис. 9.1):Рис. 09.01. Методы хранения и доступа

    1) иерархический последовательный метод доступа (Hierarchical Sequential Access Method - HSAM);

    2) иерархический прямой метод (Hierarchical Direct Access Method - HDAM);

    3) иерархический индексно-последовательный метод (Hierarchical Indexed Sequential Access Method - HISAM);

    4) иерархический индексно-произвольный метод (Hierarchical Indexed Direct Access Method - HIDAM).

Дадим этим методам краткую характеристику ссылка на источники литературы.

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

Метод удобен для режима 1, однако быстродействие в режиме 2 мало: для его повышения необходимо использовать бинарный поиск (B- и B+-деревья). Время включения и удаления записей значительно.

Разновидностью метода является физически связанный (связанно-последовательный) метод, который называют также плотным. Имеются несмежные физические участки данных, используются указатели. Осуществляется динамическое перераспределение памяти: в одной и той же области памяти может выполняться несколько процессов или работают с данными, обладающими большой изменчивостью. При включении и удалении данных меняется только логика поиска. В режиме 1 время поиска мало, в режиме 2 - большое. Затраты на вторичную память малы. Применять бинарный поиск здесь нельзя из-за неплотной упаковки файлов и невозможности вычислять адреса.

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

Индексно-последовательный метод.Файл индексныйИндексный файл упорядочен по Ключ первичныйпервичному ключу (главному атрибуту физической записи). ИндексИндекс содержит ссылки не на каждую запись, а на группу записей (рис. 9.2).Рис. 09.02. Индексно-последовательный метод Последовательная организация индексного файла допускает, в свою очередь, его индексацию - многоуровневая индексация (рис. 9.3).Рис. 09.03. Индексно-последовательный метод

Процедура добавления возможна в двух видах.

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

  2. Если места в блоке основного файла нет, запись делится пополам и в индексном файле создается новый блок.

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

При произвольных методах записи физически располагаются произвольно.

Индексно-произвольный метод. Записи хранятся в произвольном порядке. Создается отдельный файл, хранящий значение действительного ключа и физического адреса (индекса). Каждой записи соответствует индекс. Общая схема показана на рис. 9.4.Рис. 09.04. Индексно-произвольный метод Идея метода отражена на рис. 9.5:Рис. 09.05. Идея метода хеширования: ПР - программа радомизации между вырабатываемым (относительным) Адрес относительныйадресом и физической записью (Адрес абсолютныйабсолютным адресом) существует взаимнооднозначное соответствие.

Разновидностью этого метода является наличие плотного индекса: кроме главного файла создается вспомогательный, называемый Индекс плотныйплотным индексом. Он состоит из записи (v, p) для любого значения ключа v в главном файле, где p - указатель на запись главного файла со значением ключа v.

Прямой метод. Имеется взаимнооднозначное соответствие между ключом записи и ее физическим адресом (рис. 9.6).Рис. 09.06. Прямой метод Выделяют два вида адресов (рис. 9.7):Рис. 09.07. Абсолютный и относительный адреса относительный и абсолютный.

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

Эффективность доступа равна 1, а эффективность хранения зависит от плотности ключей.

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

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

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

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

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

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

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

Простейшим алгоритмом хеширования может являться функция f(k)єk (mod 10), где k - ключ, целое число (табл. 9.1)

Таблица 9.1.

Прямой метод доступа

Исходные ключи Преобразованные объектные ключи Адрес хранения (относительный № блока)
X101
X102
X103
...
X199
Y100
Y101
01
02
03
...
99
100
101
01
02
03
...
99
100
101
X101
X102
X103
...
X199
Y500
Y501
. Такая функция не дает равномерного распределения, и потому используют более подходящие функции, например f = сумма цифр ключа (mod 10)+1.

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

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

9.3.
Доступ к данным и их обновление

Следует отдельно поговорить о методах поиска ссылка на источники литературы данных и выдаче результатов (в промежуточную память, на терминал) для последовательных методов обработки. Здесь используют поиск с помощью дерева (B-, бинарное, B+-деревья). Бинарное деревоБинарное дерево является разновидностью B-дерева. B-дерево допускает более двух ветвей, исходящих из одной вершины. Любая вершина состоит из совокупности значений первичного ключа, указателей индексов и (ассоциированных) данных. Указатель индекса используется для перехода на следующий, более низкий уровень вершин (рис. 9.8).Рис. 09.08. Использование В-дерева «Хранимые» в вершине данные фактически представляют собой совокупность указателей данных и служат для физической организации данных, определения положения данных, ключевое значение которых хранится в этой вершине индекса. Физическая организация ветвящейся вершины B-дерева подобна физической последовательной структуре. Алгоритм работы бинарного дерева (в вершинах) представлен на рис. 9.9.Рис. 09.09. Алгоритм поиска по В-дереву: КД - ключ данных

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

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

В B+-дереве его копия помещается в левую часть правого листа, что позволяет упростить операции добавления и удаления ссылка на источники литературы.

Подводя некоторые итоги части II, можно сделать следующие предварительные выводы.

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

  1. Автоматизация проектирования БД.

  2. Объектно-ориентированные базы данных (ООБД).

  3. Распределенные базы данных.

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

© Центр дистанционного образования МГУП