- •Курс лекций для студентов заочной формы обучения
- •Содержание
- •Введение
- •1. Основные понятия и термины
- •2. Логическое и концептуальное моделирование бд
- •Процесс построения модели данных
- •3. Модели данных
- •3.1. Иерархическая модель данных
- •3.2. Сетевая модель данных
- •3.3. Модель данных “сущность - связь”
- •3.4. Бинарная модель данных
- •3.5. Реляционная модель данных
- •4. Проектирование реляционных баз данных
- •4.1. Основные понятия
- •4.2. Ключи отношений
- •5.3. Операции над отношениями
- •5.3.1. Реляционные операторы
- •3. Применяем оператор выбора,
- •4.3.2. Операции обновления отношений
- •4.3.3. Другие операции над отношениями
- •4.4. Функциональные зависимости
- •4.5. Нормальные формы схем отношений
- •4.5.1. Первая нормальная форма ( 1 нф)
- •4.5.2. Вторая нормальная форма ( 2 нф)
- •4.5.3. Третья нормальная форма ( 3 нф)
- •4.5.4. Нормальная форма Бойса-Кодда (нфбк)
- •4.5.5. Многозначные зависимости. Четвертая нормальная форма
- •4.6. Декомпозиция схем отношений
- •4.7. Целостность данных
- •5. Системы управления базами данных (субд)
- •5.1. Функции субд
- •5.2. Языки баз данных
- •5.3. Типовая организация современной субд
- •5.4. Структуры внешней памяти
- •5.5. Хранение отношений
- •5.6. Индексы
- •5.6.2. Хэширование
- •5.6.3. Доступ к данным на основе инвертированных списков
- •6. Сетевые базы данных
- •6.1. Субд в архитектуре "клиент-сервер"
- •6.1.1. Открытые системы
- •6.1.2. Клиенты и серверы локальных сетей
- •6.1.3. Системная архитектура "клиент-сервер"
- •6.1.4. Серверы баз данных
- •6.1.5. Принципы взаимодействия между клиентом и сервером
- •6.1.6. Протоколы удаленного вызова процедур
- •6.1.7. Разделение функций между клиентами и серверами
- •6.1.8. Требования к аппаратным возможностям и программному обеспечению клиентов и серверов
- •6.2. Распределенные бд
- •6.2.1. Разновидности распределенных систем
- •6.2.2. Однородные распределенные системы
- •6.2.3. Интегрированные или федеративные системы и мультибазы данных
- •7. Современные направления разработок баз данных
- •Список используемой литературы:
5.6.2. Хэширование
Альтернативным и все более популярным подходом к организации индексов является использование техники хэширования. Это очень обширная тема, которая заслуживает отдельного рассмотрения. Мы ограничимся лишь несколькими замечаниями. Общей идеей методов хэширования является применение к значению ключа некоторой функции свертки (хэш-функции), вырабатывающей значение меньшего размера. Свертка значения ключа затем используется для доступа к записи.
В самом простом, классическом случае, свертка ключа используется как адрес в таблице, содержащей ключи и записи. Основным требованием к хэш-функции является равномерное распределение значение свертки. При возникновении коллизий (одна и та же свертка для нескольких значений ключа) образуются цепочки переполнения. Главным ограничением этого метода является фиксированный размер таблицы. Если таблица заполнена слишком сильно или переполнена, но возникнет слишком много цепочек переполнения, и главное преимущество хэширования - доступ к записи почти всегда за одно обращение к таблице - будет утрачено. Расширение таблицы требует ее полной переделки на основе новой хэш-функции (со значением свертки большего размера).
В случае баз данных такие действия являются абсолютно неприемлемыми. Поэтому обычно вводят промежуточные таблицы-справочники, содержащие значения ключей и адреса записей, а сами записи хранятся отдельно. Тогда при переполнении справочника требуется только его переделка, что вызывает меньше накладных расходов.
Чтобы избежать потребности в полной переделки справочников, при их организации часто используют технику B-деревьев с расщеплениями и слияниями. Хэш-функция при этом меняется динамически, в зависимости от глубины B-дерева. Путем дополнительных технических ухищрений удается добиться сохранения порядка записей в соответствии со значениями ключа. В целом методы B-деревьев и хэширования все более сближаются.
5.6.3. Доступ к данным на основе инвертированных списков
К числу наиболее известных и типичных представителей таких систем относятся Datacom/DB компании Applied Data Research, Inc. (ADR), ориентированная на использование на машинах основного класса фирмы IBM, и Adabas компании Software AG.
Организация доступа к данным на основе инвертированных списков используется практически во всех современных реляционных СУБД, но в этих системах пользователи не имеют непосредственного доступа к инвертированным спискам (индексам). Стоит заметить, что внутренние интерфейсы реляционных СУБД очень близки к пользовательским интерфейсам систем, основанных на инвертированных списках.
Структуры данных
База данных, организованная с помощью инвертированных списков, похожа на реляционную БД, но с тем отличием, что хранимые таблицы и пути доступа к ним видны пользователям. При этом:
- строки таблиц упорядочены системой в некоторой физической последовательности;
- физическая упорядоченность строк всех таблиц может определяться и для всей БД;
- для каждой таблицы можно определить произвольное число ключей поиска, для которых строятся индексы. Эти индексы автоматически поддерживаются системой, но явно видны пользователям.
Манипулирование данными
Поддерживаются два класса операторов:
1. Операторы, устанавливающие адрес записи, среди которых:
- прямые поисковые операторы (например, найти первую запись таблицы по некоторому пути доступа);
- операторы, находящие запись в терминах относительной позиции от предыдущей записи по некоторому пути доступа.
2. Операторы над адресуемыми записями.
Ограничения целостности
Общие правила определения целостности БД отсутствуют. В некоторых системах поддерживаются ограничения уникальности значений некоторых полей, но в основном все возлагается на прикладную программу.