Хэширование

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

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

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

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

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

Глава 12. Защита бд Обеспечение защиты данных в базе

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

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

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

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

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 без права доступа к этим атрибутам или изменения их значений.

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

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