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

В соответствии с определением 7~ отношение СОТРУДНИКИ-ПРОЕКТЫ находится в 3NF. Однако тот факт, что имеются функциональные зависимости атрибутов отношения от атрибута, являющегося частью первичного ключа, приводит к аномалиям. Например, для того, чтобы изменить имя сотрудника с данным номером согласованным образом, нам потребуется модифицировать все кортежи, включающие его номер.

Определение 8. Детерминант

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

Определение 9. Нормальная форма Бойса-Кодда

Отношение R находится в нормальной форме Бойса-Кодда (BCNF) в том и только в том случае, если каждый детерминант является возможным ключом.

Очевидно, что это требование не выполнено для отношения СОТРУДНИКИ-ПРОЕКТЫ. Можно произвести его декомпозицию к отношениям СОТРУДНИКИ и СОТРУДНИКИ-ПРОЕКТЫ:

СОТРУДНИКИ (СОТР_НОМЕР, СОТР_ИМЯ)

Возможные ключи:

СОТР_НОМЕР

СОТР_ИМЯ

Функциональные зависимости:

СОТР_НОМЕР CОТР_ИМЯ

СОТР_ИМЯ СОТР_НОМЕР

СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН)

Возможный ключ:

СОТР_НОМЕР, ПРО_НОМЕР

Функциональные зависимости:

СОТР_НОМЕР, ПРО_НОМЕР CОТР_ЗАДАН

Возможна альтернативная декомпозиция, если выбрать за основу СОТР_ИМЯ. В обоих случаях получаемые отношения СОТРУДНИКИ и СОТРУДНИКИ-ПРОЕКТЫ находятся в BCNF, и им не свойственны отмеченные аномалии.

Ситуация, когда отношение будет находиться в 3NF, но не в NFBC, возникает при условии, что отношение имеет два (или более) возможных ключа, которые являются составными и имеют общий атрибут. На практике такая ситуация встречается достаточно редко, для всех прочих отношений 3NF и NFBC эквивалентны.

8.2 Многозначные зависимости. Четвертая нормальная форма

Рассмотрим пример следующей схемы отношения:

ПРОЕКТЫ (ПРО_НОМЕР, ПРО_СОТР, ПРО_ЗАДАН)

Отношение ПРОЕКТЫ содержит номера проектов, для каждого проекта список сотрудников, которые могут выполнять проект, и список заданий, предусматриваемых проектом. Сотрудники могут участвовать в нескольких проектах, и разные проекты могут включать одинаковые задания.

Каждый кортеж отношения связывает некоторый проект с сотрудником, участвующим в этом проекте, и заданием, который сотрудник выполняет в рамках данного проекта (мы предполагаем, что любой сотрудник, участвующий в проекте, выполняет все задания, предусмотренные этим проектом). По причине сформулированных выше условий единственным возможным ключем отношения является составной атрибут ПРО_НОМЕР, ПРО_СОТР, ПРО_ЗАДАН, и нет никаких других детерминантов. Следовательно, отношение ПРОЕКТЫ находится в BCNF. Но при этом оно обладает недостатками: если, например, некоторый сотрудник присоединяется к данному проекту, необходимо вставить в отношение ПРОЕКТЫ столько кортежей, сколько заданий в нем предусмотрено.

Определение 10. Многозначные зависимости

В отношении R (A, B, C) существует многозначная зависимость R.A R.B в том и только в том случае, если множество значений B, соответствующее паре значений A и C, зависит только от A и не зависит от С.

В отношении ПРОЕКТЫ существуют следующие две многозначные зависимости:

ПРО_НОМЕР ПРО_СОТР

ПРО_НОМЕР ПРО_ЗАДАН

Легко показать, что в общем случае в отношении R (A, B, C) существует многозначная зависимость R.A R.B в том и только в том случае, когда существует многозначная зависимость R.A R.C.

Каждая функциональная зависимость является многозначной, но не каждая многозначная зависимость является функциональной.

Дальнейшая нормализация отношений, подобных отношению ПРОЕКТЫ, основывается на следующей теореме:

Теорема Фейджина

Отношение R (A, B, C) можно спроецировать без потерь в отношения R1 (A, B) и R2 (A, C) в том и только в том случае, когда существует MVD A B | C.

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

Определение 11. Четвертая нормальная форма

Отношение R находится в четвертой нормальной форме (4NF) в том и только в том случае, если в случае существования многозначной зависимости A B все остальные атрибуты R функционально зависят от A.

В нашем примере можно произвести декомпозицию отношения ПРОЕКТЫ в два отношения ПРОЕКТЫ-СОТРУДНИКИ и ПРОЕКТЫ-ЗАДАНИЯ:

ПРОЕКТЫ-СОТРУДНИКИ (ПРО_НОМЕР, ПРО_СОТР)

ПРОЕКТЫ-ЗАДАНИЯ (ПРО_НОМЕР, ПРО_ЗАДАН)

Оба эти отношения находятся в 4NF и свободны от отмеченных аномалий.

8.3 Зависимость соединения. Пятая нормальная форма

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

Рассмотрим, например, отношение

СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ (СОТР_НОМЕР, ОТД_НОМЕР, ПРО_НОМЕР)

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

Поэтому отношение находится в 4NF. Однако в нем могут существовать аномалии, которые можно устранить путем декомпозиции в три отношения.

Определение 12. Зависимость соединения (читается как - звездочка X,Y,Z,…)

Отношение R (X, Y, ..., Z) удовлетворяет зависимости соединения * (X, Y, ..., Z) в том и только в том случае, когда R восстанавливается без потерь путем соединения своих проекций на X, Y, ..., Z.

Определение 13. Пятая нормальная форма

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

Введем следующие имена составных атрибутов:

СО = {СОТР_НОМЕР, ОТД_НОМЕР}

СП = {СОТР_НОМЕР, ПРО_НОМЕР}

ОП = {ОТД_НОМЕР, ПРО_НОМЕР}

Предположим, что в отношении СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ существует зависимость соединения: * (СО, СП, ОП)

На примерах легко показать, что при вставках и удалениях кортежей могут возникнуть проблемы. Их можно устранить путем декомпозиции исходного отношения в три новых отношения:

СОТРУДНИКИ-ОТДЕЛЫ (СОТР_НОМЕР, ОТД_НОМЕР)

СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, ПРО_НОМЕР)

ОТДЕЛЫ-ПРОЕКТЫ (ОТД_НОМЕР, ПРО_НОМЕР)

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

Лекция 9. Структуры внешней памяти

Реляционные СУБД обладают рядом особенностей, влияющих на организацию внешней памяти. К наиболее важным особенностям можно отнести следующие:

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

· Поддержание отношений-каталогов. Информация, связанная с именованием объектов базы данных и их конкретными свойствами (например, структура ключа индекса), поддерживается подсистемой языкового уровня. С точки зрения структур внешней памяти отношение-каталог ничем не отличается от обычного отношения базы данных.

· Регулярность структур данных. Поскольку основным объектом реляционной модели данных является плоская таблица, главный набор объектов внешней памяти может иметь очень простую регулярную структуру.

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

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

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

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

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

· журнальная информация, поддерживаемая для удовлетворения потребности в надежном хранении данных;

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

9.1 Хранение отношений

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

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

Поскольку гораздо более распространено хранение по строкам, мы рассмотрим немного более подробно этот способ хранения отношений. Типовой структурой страницы данных является следующая:

Рис. 9.1

К основным характеристикам этой организации можно отнести следующие:

· Каждый кортеж обладает уникальным идентификатором (tid), не изменяемым во все время существования кортежа. Структура tid следует из приведенного выше рисунка.

· Обычно каждый кортеж хранится целиком в одной странице. Из этого следует, что максимальная длина кортежа любого отношения ограничена размерами страницы. Возникает вопрос: как быть с "длинными" данными, которые в принципе не помещаются в одной странице? Применяются несколько методов. Наиболее простым решением является хранение таких данных в отдельных (вне базы данных) файлах с заменой "длинного" данного в кортеже на имя соответствующего файла. В некоторых системах (например, в предпоследней версии СУБД Informix) такие данные хранились в отдельном наборе страниц внешней памяти, связанном физическими ссылками. Оба эти решения сильно ограничивают возможность работы с длинными данными (как, например, удалить несколько байтов из середины 2-мегабайтной строки?). В настоящее время все чаще используется метод, предложенный несколько лет тому назад в проекте Exodus, когда "длинные" данные организуются в виде B-деревьев последовательностей байтов.

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

· Изменение схемы хранимого отношения с добавлением нового столбца не вызывает потребности в физической реорганизации отношения. Достаточно лишь изменить информацию в описателе отношения и расширять кортежи только при занесении информации в новый столбец.

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

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

9.2 Индексы

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

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

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

9.3 Журнальная информация

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

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

9.4 Служебная информация

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

· Внутренние каталоги, описывающие физические свойства объектов базы данных, например, число атрибутов отношения, их размер и, возможно, типы данных; описание индексов, определенных для данного отношения и т.д.

· Описатели свободной и занятой памяти в страницах отношения. Такая информация требуется для нахождения свободного места при занесении кортежа.

· Связывание страниц одного отношения. Если в одном файле внешней памяти могут располагаться страницы нескольких отношений (обычно к этому стремятся), то нужно каким-то образом связать страницы одного отношения. Тривиальный способ использования прямых ссылок между страницами часто приводит к затруднениям при синхронизации транзакций (например, особенно трудно освобождать и заводить новые страницы отношения). Поэтому стараются использовать косвенное связывание страниц с использованием служебных индексов. В частности, известен общий механизм для описания свободной памяти и связывания страниц на основе B-деревьев.

Лекция 10. Методы организации индексов

Существуют два класса методов, реализующих доступ к данным по ключу:

· методы поиска по дереву,

· методы хеширования.

10.1 Методы поиска по дереву

Определение: Деревом называется конечное множество, состоящее из одного или более элементов, называемых узлами, таких, что:

1. между узлами имеет место отношение типа "исходный-порожденный";

2. есть только один узел, не имеющий исходного. Он называется корнем;

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

4. отношение "исходный-порожденный" действует только в одном направлении, т.е. ни один потомок некоторого узла не может стать для него предком.

Число порожденных отдельного узла (число поддеревьев данного корня) называется его степенью. Узел с нулевой степенью называют листом или концевым узлом. Максимальное значение степени всех узлов данного дерева называется степенью дерева.

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

Упорядоченное дерево, степень которого не больше 2 называется бинарным деревом. Бинарное дерево особенно часто используется при поиске в оперативной памяти. Алгоритм поиска: вначале аргумент поиска сравнивается с ключом, находящимся в корне. Если аргумент совпадает с ключом, поиск закончен, если же не совпадает, то в случае, когда аргумент оказвается меньше ключа, поиск продолжается в левом поддереве, а в случае когда больше ключа - в правом поддереве. Увеличив уровень на 1 повторяют сравнение, считая текущий узел корнем.

Пример*: Пусть дан список студентов, содержащий их фамилии средний бал успеваемости (см. таблицу 1.1). В качестве ключа используется фамилия студента. Предположим, что все записи имеют фиксированную длину, тогда в качестве указателя можно использовать номер записи. Смещение записи в файле в этом случае будет вычислятся как ([номер_записи] -1 ) * [длина_записи]. Пусть аргумент поиска "Петров". На рисунке 10.1 показаны одно из возможных для этого набора данных бинарных деревьев поиска и путь поиска.

Таблица 1.1.

Студент	Балл
Васильев	4,2
Иванов	3,4
Кузнецов	3,5
Петров	3,2
Сидоров	4,6
Тихомиров	3,8

Рис. 10.1. Поиск по бинарному дереву.

Заметим, что здесь используется следующее правило сравнения строковых переменных: считается, что значение символа соответствует его порядковому номеру в алфавите. Поэтому "И" меньше "К", а "К" меньше "С". Если текущие символы в сравниваемых строках совпадают, то сравниваются символы в следующих позициях.

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

Определение: Бинарное дерево называют сбалансированным (balanced), если высота левого поддерева каждого узла отличается от высоты правого поддерева не более чем на 1.

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

Определение: В-деревом порядка n называется сильно ветвящееся дерево степени 2n+1, обладающее следующими свойствами:

1. Каждый узел, за исключением корня, содержит не менее n и не более 2n ключей.

2. Корень содержит не менее одного и не более 2n ключей.

3. Все листья расположены на одном уровне.

4. Каждый нелистовой узел содержит два списка: упорядоченный по возрастанию значений список ключей и соответсвующий ему список указателей (для листовых узлов список указателей отсутствует).

Для такого дерева:

· сравнительно просто может быть организован последовательный доступ, т.к. все листья расположены на одном уровне;

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

Рис. 10.2. Сбалансированное дерево.

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

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

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

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

ключ(1) <= ключ(2) <= ... <= ключ(n);

в странице дерева Nm находятся ключи k со значениями ключ(m) <= k <= ключ(m+1).

Листовая страница обычно имеет следующую структуру:

Листовая страница обладает следующими свойствами:

ключ(1) < ключ(2) < ... < ключ(t);

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

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

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

Основной "изюминкой" B-деревьев является автоматическое поддержание свойства сбалансированности.

10.2 Автоматическое поддержание свойства сбалансированности B-деревьев при выполнении операций занесения и удаления записей

При занесении новой записи выполняется:

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

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

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

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

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

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

При удалении записи выполняются следующие действия:

· Поиск записи по ключу. Если запись не найдена, то значит удалять ничего не нужно.

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

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

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

· Чтобы устранить возможность доступа от корня к освобожденной странице, нужно удалить соответствующее значение ключа и ссылку на освобожденную страницу из внутренней страницы - ее предка. При этом может возникнуть потребность в слиянии этой страницы с ее левым или правыми братьями и т.д.

· Предельным случаем является полное опустошение корневой страницы дерева, которое возможно после слияния последних двух потомков корня. В этом случае корневая страница освобождается, а глубина дерева уменьшается на единицу. Как видно, при выполнении операций вставки и удаления свойство сбалансированности B-дерева сохраняется, а внешняя память расходуется достаточно экономно.

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

· упреждающие расщепления, т.е. расщепления страницы не при ее переполнении, а несколько раньше, когда степень заполненности страницы достигает некоторого уровня;

· переливания, т.е. поддержание равновесного заполнения соседних страниц;

· слияния 3-в-2, т.е. порождение двух листовых страниц на основе содержимого трех соседних.

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

10.3 Хэширование

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

Этот метод используется тогда, когда все множество ключей заранее известно и на время обработки может быть размещено в оперативной памяти. В этом случае строится специальная функция, однозначно отображающая множество ключей на множество указателей, называемая хеш-функцией (от английского "to hash" - резать, измельчать). Имея такую функцию можно вычислить адрес записи в файле по заданному ключу поиска. В общем случае ключевые данные, используемые для определения адреса записи организуются в виде таблицы, называемой хеш-таблицей.

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

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

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

Лекция 11. Защита БД

11.1 Обеспечение защиты данных в базе

С появлением централизованных баз данных возникла необходимость в защите данных. Термин «защита данных» означает, во-первых, предупреждение несанкционированного или случайного доступа к данным, их изменения или разрушения со стороны пользователей. И во-вторых, предупреждение изменения или разрушения данных при сбоях аппаратных и программных средств и ошибках в работе сотрудников группы эксплуатации.

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

Рассмотрим только техническую сторону методов обеспечения защиты данных в базе. В дальнейшем будем считать, что СУБД не должна разрешать выполнение какой-либо операции над БД пользователю, не получившему на это соответствующие права, и что санкционирование доступа к данным выполняется администратором базы данных.

При решении вопросов защиты данных в обязанности АБД входит:

1) классификация данных в соответствии с их использованием;

2) определение прав доступа отдельных пользователей к определенным группам данных в БД и ограничений на характер операций, выполняемых пользователем с этими данными;

3) организация системы контроля доступа к данным;

4) исследование возникающих случаев нарушения защиты данных и проведение политики их предотвращения.

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

Рассмотрим уровни доступа к БД для различных категорий пользователей:

1) неограниченный доступ ко всем отношениям в БД и их поколениям;

2) неограниченный доступ к группе отношений и их поколениям;

3) ограниченный доступ к группе отношений и их поколениям.

На уровне отношения различают следующие уровни доступа:

1) неограниченный доступ ко всему отношению для всех типов операций;

2) запрет на доступ к любым частям отношения для всех типов операций;

3) доступ к любой части отношения, но без права изменения ее содержимого;

4) доступ к любой части отношения, но с правом изменения значений только для атрибутов А₁, A₂, ..., A_r;

5) неограниченный доступ только к одному кортежу отношения для всех типов операций;

6) доступ только к одному кортежу отношения без права изменения содержимого этого кортежа;

7) неограниченный доступ к атрибутам А₁, A₂, ..., A_r отношения для всех типов операций и запрет доступа к остальным атрибутам отношения;

8) доступ только к атрибутам А₁, A₂, ..., A_r отношения без права изменения их значений и запрет доступа к остальным атрибутам отношения;

9) доступ только к атрибутам А₁, A₂, ..., A_r отношения с правом изменения значений только для атрибутов A_l, ..., A_p, где {A_l, ..., A_p}{А₁, A₂, ..., A_r}, и запрет доступа к остальным атрибутам отношения;

10) доступ в соответствии с пунктами 1, 3, 4, 5, 6, 7, 8, 9, но с ограничением по интервалу времени (с t₁ no t₂);

11) доступ в соответствии с пунктами 1, 3, 4, 5, 6, 7, 8, 9, но с разрешением изменения значений атрибутов только в случае выполнения условий F₁,F₂,…F_r соответственно на значения атрибутов А₁, A₂, ..., A_r (например, если значение атрибута не превышает некоторой величины z);

12) разрешение права применения вычислительных операторов (суммирование, вычитание и т. п.) к атрибутам А₁, A₂, ..., A_r без права доступа к этим атрибутам или изменения их значений.

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

Рассмотрим основные методы и приемы защиты данных.

11.1.1 Идентификация пользователя

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

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

11.1.2 Управление доступом

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

Однако в ряде случаев информация о составе разрешенных пользователю операций оказывается недостаточной для решения вопроса о допустимости выполнения этих операций с конкретными данными. Поэтому каждое групповое данное должно иметь связанный с ним набор ограничений доступа. Этот набор ограничений содержит: условие, которому должен удовлетворять пользователь, чтобы иметь доступ к групповому данному; пароль, предъявляемый при выборке некоторых комбинаций данных из группового данного;

пароль, предъявляемый при модификации этих данных, и т. п.

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

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

Аксиома безопасности. Если комбинация атрибутов Л доступна (запрещена) пользователю Х в зависимости от условия В, то каждая подкомбинация А также доступна (запрещена) пользователю Х по условию В.

Состав проверок может быть, например, следующим.

1. Все ли отношения, упомянутые в запросе, доступны пользователю X?

2. Все ли поколения, упомянутые в запросе, доступны пользователю X?

3. Все ли комбинации атрибутов, упомянутые в запросе, доступны пользователю X?

4. Задано ли квалифицирующее выражение, которое ограничивает для пользователя Х диапазон значений атрибутов, и если да, то лежат ли их значения внутри диапазона, доступного для X?

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

11.1.3 Защита данных при статистической обработке

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

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

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

Первый подход защиты данных заключается в том, что если и не исключить полностью возможность раскрытия индивидуальных данных, то по крайней мере сделать эту возможность достаточно трудной. Рассмотрим базу данных, содержащую п. записей. Пусть V={v₁, v₂, …, v_n} - множество значений некоторого неключевого поля этих записей. Линейным запросом называется сумма ,

где с_i - произвольные действительные числа.

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

если запись i принадлежит множеству S,

если запись i не принадлежит множеству S.

Если допускаются линейные запросы, продуцирующие (обрабатывающие) не менее т элементов (записей), и никакие два запроса не могут иметь более k общих элементов (общих записей) и если m>>k, то для вычисления некоторого неизвестного элемента (значения поля в интересующей нас записи) необходимо сделать не менее m/k запросов. Стратегия защиты заключается в увеличении этого отношения. Если ввести ограничения на структуру запросов, то можно исключить возможность раскрытия конкретных данных.

(Ограничить min размер группы и min количество общих элементов в группах).

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

(Запрет выборки по полному ключу).

11.1.4 Физическая защита

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

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

Лекция 12. Целостность БД

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

12.1 Целостность сущности и ссылок

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

Второе требование называется требованием целостности по ссылкам и является несколько более сложным. Очевидно, что при соблюдении нормализованности отношений сложные сущности реального мира представляются в реляционной БД в виде нескольких кортежей нескольких отношений. Например, представим, что нам требуется представить в реляционной базе данных сущность ОТДЕЛ с атрибутами ОТД_НОМЕР (номер отдела), ОТД_КОЛ (количество сотрудников) и ОТД_СОТР (набор сотрудников отдела). Для каждого сотрудника нужно хранить СОТР_НОМЕР (номер сотрудника), СОТР_ИМЯ (имя сотрудника) и СОТР_ЗАРП (заработная плата сотрудника). При правильном проектировании соответствующей БД в ней появятся два отношения: ОТДЕЛЫ ( ОТД_НОМЕР, ОТД_КОЛ ) (первичный ключ - ОТД_НОМЕР) и СОТРУДНИКИ ( СОТР_НОМЕР, СОТР_ИМЯ, СОТР_ЗАРП, СОТР_ОТД_НОМ ) (первичный ключ - СОТР_НОМЕР).

Как видно, атрибут СОТР_ОТД_НОМ появляется в отношении СОТРУДНИКИ не потому, что номер отдела является собственным свойством сотрудника, а лишь для того, чтобы иметь возможность восстановить при необходимости полную сущность ОТДЕЛ. Значение атрибута СОТР_ОТД_НОМ в любом кортеже отношения СОТРУДНИКИ должно соответствовать значению атрибута ОТД_НОМ в некотором кортеже отношения ОТДЕЛЫ. Атрибут такого рода называется внешним ключом, поскольку его значения однозначно характеризуют сущности, представленные кортежами некоторого другого отношения (т.е. задают значения их первичного ключа). Говорят, что отношение, в котором определен внешний ключ, ссылается на соответствующее отношение, в котором такой же атрибут является первичным ключом.

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

Ограничения целостности сущности и по ссылкам должны поддерживаться СУБД. Для соблюдения целостности сущности достаточно гарантировать отсутствие в любом отношении кортежей с одним и тем же значением первичного ключа. С целостностью по ссылкам дела обстоят несколько более сложно.

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

Здесь существуют три подхода, каждый из которых поддерживает целостность по ссылкам.

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

2. При втором подходе при удалении кортежа, на который имеются ссылки, во всех ссылающихся кортежах значение внешнего ключа автоматически становится неопределенным.

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

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

12.2 Обеспечение целостности данных

Существует два основных вида ограничений целостности, которые должны поддерживаться СУБД:

1) структурные ограничения - задаются функциональными зависимостями и проверяются путем проверки равенства значений соответствующих данных в БД;

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

Существуют и другие ограничения целостности. Например, ограничения на условия выполнения параллельных операций над данными в базе; ограничения тина «старый» - «новый», когда БД переходит в новое состояние.

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

Рассмотрим различные тины ограничений целостности.

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

2. Отношение (файл) кроме первичного ключа может содержать возможные ключи, значения которых должны быть также уникальными. Для спецификации этого типа ограничений достаточно фразы UNIQUE (А) при описании модели данных, где А - атрибут или комбинация атрибутов.

Рассмотренные два примера соответствуют структурным ограничениям. Если отношение находится в четвертой нормальной форме, то фраз KEY и UNIQUE достаточно для спецификации всех функциональных зависимостей. Если отношение содержит некоторую дополнительную зависимость (т. е. не является нормализованным), эту зависимость необходимо специфицировать специальным выражением при описании данных.

3. В заданном отношении для каждого кортежа между значениями полей А и В должно всегда выполняться условие, что первое больше второго. Ограничение специфицируется специальным выражением.

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

5. Для некоторого атрибута (или комбинации атрибутов) может существовать конечный, небольшой по размеру набор допустимых значений (например, по атрибуту ОБРАЗОВАНИЕ могут быть только значения НАЧАЛЬНОЕ, НЕПОЛНОЕ СРЕДНЕЕ СРЕДНЕЕ, НЕПОЛНОЕ ВЫСШЕЕ, ВЫСШЕЕ). Ограничение специфицируется специальным выражением при описании данных.