Понятие индексов в базе данных. Техника хранения на основе B-деревьев. Методы хеширования.

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

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

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

Механизм мульти-индекса… Никому не нужен! Если нужен, то вот… используется для оптимизации эквисоединения таблиц. Суть в том что мульти-индексы организуются для таблиц с одинаковыми атрибутами (один или несколько из атрибутов становится ключом мульти-индекса). Значению ключа сопоставляется набор кортежей этих таблиц, значения выделенных атрибутов которых совпадают со значением ключа.

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

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

Механизм B-деревьев (B+) ориентирован на хранение во внешней памяти 2 типов страниц:

1. Внутренних – это последовательность значений ключей и ссылка на № следующей страницы, либо на листовую.

При этом выдерживаются следующие свойства:

i. ключ₁ < ключ₂ <...< ключ_m

ii. в странице дерева N_m находятся ключи k со значениями ключ_m <= k <= ключ_m+1.

 

1. Листовых

i. ключ₁ < ключ₂ <... < ключ_k;

ii. список_r – упорядоченный список идентификаторов кортежей (tid), включающих значение ключr;

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

 

B-дерево – сбалансировано (ветви до листьев одинаковой глубины).

Глубина ~log_m N, где m – число ключей во внутренней странице, N – число кортежей.

При создании дерева, в случае переполнения порождается новая страница, в которую переливается половина предыдущей. => частые расщепления и слияния.

Решение:

1. Упреждения расщепления (раннее расщепление по достижении некого уровня)
2. Переливание (равновесие соседних вершин)
3. Слияние 3-в-2 (а не 2-в-1)

Хеширование – способ организации индексов.

1. Классический случай – свертка ключа используется как адрес в таблице, содержащей ключи и записи. Основным требованием к хэш-функции является равномерное распределение значение свертки
2. Расширяемое хэширование (Extendible Hashing) – принцип использования деревьев цифрового поиска в основной памяти. В основной памяти поддерживается справочник, организованный на основе бинарного дерева цифрового поиска, ключами которого являются значения хэш-функции, а в листовых вершинах хранятся номера блоков записей во внешней памяти.
3. Линейное хэширование (Linear Hashing) – является то, что для адресации блока внешней памяти всегда используются младшие биты значения хэш-функции. Если возникает потребность в расщеплении, то записи перераспределяются по блокам так, чтобы адресация осталась правильной.

 

Виды проектирования баз данных. Недостатки проектирования в терминах отношений. Понятие информационной модели. Достоинства информационного моделирования. Средства автоматизации проектирования баз данных.

Проектирование БД.

Концептуальное

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

Логическое

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

Физическое

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

 

Ограниченность проектирования:

1. Реляционная модель данных не предлагает какого-либо механизма для разделения сущностей объектов предметной области и связей между ними,
2. Модель не обеспечивает достаточных средств для представления смысла данных,
3. Во многих прикладных областях трудно моделировать предметную область на основе плоских таблиц,
4. Хотя весь процесс проектирования происходит на основе учета зависимостей, реляционная модель не предоставляет какие-либо формализованные средства для представления этих зависимостей,
5. На ранних стадиях требуется участие специалистов данной ПО.

 

Информационная модель – способ представления понятий или объектов ПО, описание сущностей для данного предприятия совокупности объектов, их параметры, поведение и отношение между ними.

 

Достоинства информационного моделирования:

1. Построение мощной и наглядной концептуальной схемы БД позволяет более полно оценить специфику моделируемой предметной области и избежать возможных ошибок на стадии проектирования схемы реляционной БД
2. Информационная модель в виде документации (хотя бы в виде вручную нарисованных диаграмм и комментариев к ним), которая может оказаться очень полезной не только при проектировании схемы реляционной БД, но и при эксплуатации, сопровождении и развитии уже заполненной БД.
3. На рынке представлены CASE-системы, обеспечивает автоматизированное преобразование диаграммных концептуальных схем баз данных, представленных в той или иной семантической модели данных, в реляционные схемы, специфицированные чаще всего на языке SQL

 

CASE – computer aided software engineering.

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

 

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

Entity – Relation модель (сущность - связь) предназначается для описания ПО в целях проектирования БД(моделирование базовых понятий на простых графиках и диаграммах).

Основные понятия:

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

Атрибут (сущности) – любая деталь, которая служит для уточнения, идентификации, классификации, численной характеристики или выражения состояния сущности.

(Пример справа)

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

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

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

Обязательный конец связи изображается сплошной линией, а необязательный – прерывистой линией.

Примеры.

«Многие к одному»

• каждый БИЛЕТ предназначен для одного и только одного ПАССАЖИРА;
• каждый ПАССАЖИР может иметь один или более БИЛЕТОВ.

«Рекурсивная модель»

• каждый МУЖЧИНА является сыном одного и только одного МУЖЧИНЫ;
• каждый МУЖЧИНА может являться отцом одного или более МУЖЧИН.

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

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