Распределенные базы данных и распределенная обработка данных

Стратегия разрешения коллизий с областью переполнения

Область хранения разбивается на 2 части:

· основную область;

· область переполнения.

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

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

Рассмотрим механизмы поиска произвольной записи и удаления записи для этой стратегии хэширования.

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

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

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

Организация стратегии свободного замещения

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

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

РАСПРЕДЕЛЕННЫЕ БАЗЫ ДАННЫХ И РАСПРЕДЕЛЕННАЯ ОБРАБОТКА ДАННЫХ

Распределённые базы данных (РБД) — совокупность логически взаимосвязанных баз данных, распределённых в компьютерной сети. Пример – поисковая БД Google. Основные цели создания распределенных БД – повышение производительности, надежность, экономия средств (один очень быстрый компьютер стоит дороже 10 медленных, суммарная производительность которых при распределенной работе = производительности быстрого компьютера).

Объединение БД-х связано с решением следующих задач:

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

2. Организация доступа к данным

3. Защита целостности данных

4. Организация обновления данных.

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

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

1. Регистрация пользователей

2. Пароли

3. Предоставление доступа только к определенным каталогам и файлам.

4. Назначение пользователям опекунских прав (ограничение работы пользователей)

5. Установление маски наследования прав (т.е. наличие доступа к каталогу не дает полного доступа к его подкаталогам).

Различают 8 типов прав:

1. Тип S – Supervisory – супервизорный тип (есть все права)

2. Тип R – Read – чтение

3. Тип W – Write – запись (право открывать и модифицировать файлы)

4. Тип С – Create – создание

5. Тип Е – Erase – удаление

6. Тим M – Modify – изменение атрибутов файлов (но не их содержание)

7. F-File Scan – пользователи могут видеть каталоги и файлы внутри каталогов

8. Тип A – Access Control – управление доступом (право назначать и модифицировать опекунские права)

S – Supervisory Это право, присваиваемое пользователю на определенном каталоге, предоставляет возможность пользоваться всеми существующими правами и давать их другим пользователям или группам по отношению к данному каталогу или его подкаталогу. Само право Supervisory для доверенного лица автоматически распространяется на все подкаталоги того каталога, в котором оно было предоставлено.

R-Read

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

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

C-Create – если никаких других прав на уровне подкаталогов не предоставлено, доверенное лицо может только создавать каталоги или файлы внутри них

E-Erase

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

M-Modify

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

F-File Scan

Благодаря File Scan пользователи или группы могут видеть каталоги и файлы внутри каталогов.

A-Access Control

Access Control предоставляет пользователю или группе возможность модифицировать права доверенных лиц или состояние маски наследования прав по отношению к каталогу или файлу. Оно не дает пользователю возможности присваивать право Supervisory, но позволяет присваивать другим права, которых сами эти пользователи не имеют.