ответы к зачёту по Базам Данных (2009) (1122570), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Добавление кортежа. Если некоторый уже участвующий в проектах служащий присоединяется к новому проекту, то к телу значения переменной отношения СЛУЖ_ПРО_НОМ требуется добавить один кортеж, соответствующий новому проекту.

Удаление кортежей. Если служащий прекращает участие в проектах, то данные о заданиях, которые он может выполнять, остаются в отношении СЛУЖ_ЗАДАНИЕ.

Модификация кортежей. При изменении одного из заданий служащего необходимо изменить значение атрибута СЛУ_ЗАДАН в одном кортеже отношения СЛУЖ_ЗАДАНИЕ.

Переменная отношения r находится в четвертой нормальной форме (4NF) в том и только в том случае, когда она находится в BCNF, и все MVD r являются FD с детерминантами – возможными ключами отношения r (нет многозначных зависимостей).

1. N-декомпозируемые отношения. Пример декомпозиции. Зависимость проекции/соединения.

В переменной отношения R с атрибутами (возможно, составными) A и B MVD AB называется тривиальной, если либо AB, либо A UNION B совпадает с заголовком отношения R.

Нетривиальная многозначная зависимость: существует многозначная зависимость A->>B|C, но нет функциональных зависимостей A->B и A->C.

Тривиальная MVD всегда удовлетворяется. При AB она вырождается в тривиальную FD. В случае A UNION B = HR требования многозначной зависимости соблюдаются очевидным образом.

Отношение называется n-декомпозируемым, есть его можно декомпозировать на n частей.

Для примера n-декомпозируемого отношения при n > 2 рассмотрим пятый вариант переменной отношения СЛУЖ_ПРО_ЗАДАН, в которой имеется единственно возможный ключ {СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН} и отсутствуют нетривиальные MVD. Пример значения переменной отношения приведен на рис. 9.3.

Рис. 9.3. Возможное значение переменной отношения СЛУЖ_ПРО_ЗАДАН (пятый вариант), результаты проекций и результат частичного естественного соединения

Как показано на рис. 9.3, результат естественного соединения проекций СЛУЖ_ПРО_НОМ и ПРО_НОМ_ЗАДАН почти совпадает с телом исходного отношения СЛУЖ_ПРО_ЗАДАН, но в нем присутствует один лишний кортеж, который исчезнет после выполнения заключительного естественного соединения с проекцией СЛУЖ_ЗАДАНИЕ. Читателям предлагается убедиться, что исходное отношение будет восстановлено при любом порядке естественного соединения трех проекций.

Зависимость проекции/соединения

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

В общем виде такое ограничение называется зависимостью проекции/соединения.

Формальное определение:

Пусть задана переменная отношения R, и A, B, …, Z являются произвольными подмножествами заголовка R (составными, перекрывающимися атрибутами). В переменной отношения R удовлетворяется зависимость проекции/соединения (Project-Join Dependency – PJD) *( A, B, …, Z) тогда и только тогда, когда любое допустимое значение r переменной отношения R можно получить путем естественного соединения проекций этого значения на атрибуты A, B, …, Z.

1. Аномалии, возникающие из-за наличия зависимости проекции/соединения. Пример декомпозиции, решающий проблему. 5НФ.

В переменной отношения СЛУЖ_ПРО_ЗАДАН выполняется PJD *({СЛУ_НОМ, ПРО_НОМ}, {ПРО_НОМ, СЛУ_ЗАДАН}, {СЛУ_НОМ, СЛУ_ЗАДАН}). Наличие такой PJD обеспечивает возможность декомпозиции отношения на три проекции, но возникает вопрос, зачем это нужно? Чем плохо исходное отношение СЛУЖ_ПРО_ЗАДАН? Ответ обычный: этому отношению свойственны аномалии обновления. Для примера предположим, что значением СЛУЖ_ПРО_ЗАДАН является отношение, показанное на рис. 9.4.

1. Добавление кортежей. Если к ТСПЗ1 (рис. 9.4) добавляется кортеж <2941, 1, A>, то должен быть добавлен и кортеж <2934, 1, A>. Действительно, в теле отношения появятся кортежи <2934, 1, B>, <2941, 1, A> и <2934, 2, A>. Ограничение целостности требует включения и кортежа <2934, 1, A>. Интересно, что добавление кортежа <2934, 1, A> не нарушает ограничение целостности и, тем самым, не требует добавления кортежа <2941, 1, A>.

Рис. 9.4. Иллюстрации аномалий обновления в отношении СЛУЖ_ПРО_ЗАДАН при наличии зависимости соединения

1. Удаление кортежа. Если из ТСПЗ2 удаляется кортеж <2934, 1, A>, то должен быть удален и кортеж <2941, 1, A>, поскольку в соответствии с ограничением целостности наличие второго кортежа означает наличие первого. Интересно, что удаление кортежа <2941, 1, A> не нарушает ограничения целостности и не требует дополнительных удалений.

Устранение аномалий обновления в 3-декомпозиции

Рис. 9.5. Иллюстрация декомпозиции отношения с зависимостью соединения

После выполнения декомпозиции трудности с обновлением автоматически снимаются. Действительно, декомпозируем отношение СЛУЖ_ПРО_ЗАДАН на три отношения: СЛУЖ_ПРО_НОМ {СЛУ_НОМ, ПРО_НОМ}, СЛУЖ_ЗАДАНИЕ {СЛУ_НОМ, СЛУ_ЗАДАН} и ПРО_НОМ_ЗАДАН {ПРО_НОМ, СЛУ_ЗАДАН}. Результат декомпозиции значения переменной отношения СЛУЖ_ПРО_ЗАДАН с телом BСПЗ1 показан в верхней части рис. 9.5.

Теперь если мы хотим добавить данные о служащем с номером 2941, выполняющем задание A в проекте 1, то, естественно, вставим кортеж <2941, 1> в отношение СОТР-ПРО_НОМ, кортеж <2941, A> в отношение СОТР-ЗАДАНИЕ и кортеж <1, A> в отношение ПРО_НОМ-ЗАДАН. Результат этих операций показан в средней части рис. 9.5.

Но если выполнить естественное соединение декомпозированных отношений с телами, полученными после добавления данных о служащем с номером 2941, выполняющем задание A в проекте 1, то будет получено значение-отношение с заголовком отношения СЛУЖ_ПРО_ЗАДАН и телом BСПЗ2 (нижняя часть рис. 9.5). Тем самым, проведенная декомпозиция позволила избежать сложностей при выполнении добавления кортежей с получением корректных результатов.

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

В переменной отношения R PJD *( A, B, …, Z) называется подразумеваемой возможными ключами в том и только в том случае, когда каждый составной атрибут A, B, …, Z является суперключом R, т. е. включает хотя бы один возможный ключ R.

В переменной отношения R зависимость проекции/соединения *(A, B, …, Z) называется тривиальной, если хотя бы один из составных атрибутов A, B, …, Z совпадает с заголовком R.

Переменная отношения R находится в пятой нормальной форме, или в нормальной форме проекции/соединения (5NF, или PJ/NF – Project-Join Normal Form) в том и только в том случае, когда каждая нетривиальная PJD в R подразумевается возможными ключами R.

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

1. Подходы к физическому хранению отношений. Построчное хранение отношений. Понятие tid-а.

Возникают следующие разновидности объектов во внешней памяти базы данных:

1. Отношения – основная часть базы данных

2. Служебные отношения (хранят информацию о схеме, параметрах ключа и т.д.)

3. индексы - управляющие структуры, ускоряющие доступ

4. журналы (надежность хранения данных)

5. служебная информация, поддерживаемая для внутренних потребностей нижнего уровня системы (например, информация о свободной памяти).

Хранение Отношений:

1. Покортежное или построчное (быстрый доступ, занимает больше места).

Внешняя память – множество сегментов, разбитых на страницы.

tid – идентификатор кортежа (обычно, <№страницы, № кортежа>).

В случае перемещения кортежа меняется описание, но tid сохраняется.

1. Постолбцовое (сохранение места, но трудоемкая сборка). Редко применимо и дальше не рассматривается.

1. Понятие индексов в базе данных. Техника хранения на основе 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. Виды проектирования баз данных. Недостатки проектирования в терминах отношений. Понятие информационной модели. Достоинства информационного моделирования. Средства автоматизации проектирования баз данных.

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

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

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

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

Характеристики

Список файлов ответов (шпаргалок)