Распределенные базы данных

Т1: LOCK A; UNLOCK A;

T2: - - - - - - - -- - - - - - - - - - - - - - - -

T3: LOCK A; UNLOCK A; T4:LOCK A; UNLOCK A; T5:. .

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

Более серьёзная проблема, которая возникает при параллельной обработке - это так называемые «тупики».

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

Т1: lock A; lock B; unlock A; unlock B;

T2: lock B; lock A; unlock B; unlock A;

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

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

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

10.8.2 Способы предотвращения тупиков

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

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

Пусть в нашем примере А предшествует В, тогда затребовав блокировку А перед В, Т2 обнаруживает, что А уже заблокирована Т1. Элемент В не был ещё заблокирован для Т2. поэтому для Т1 доступна блокировка В, когда она будет запрашиваться. При завершении Т1 блокировки на А и В снимаются и Т2 может продолжаться.

3). Ничего не предпринимать для их предотвращения, а периодически проверять запросы на блокировки и выявлять, не возникло ли тупиковой ситуации. Облегчает предотвращение такой проверки алгоритм построения графа, вершины которого представляют транзакции, а дуга T1->Т2 означает, что транзакция Т2 ожидает выполнения её запроса на блокировку элемента, заблокированного в данный момент транзакцией Т2. каждый цикл указывает тупик. Если же циклов нет, не существует и тупиков. В случае обнаружения тупика следует произвести рестарт хотя бы для одной из попавших в него транзакций и её воздействие на БД должно быть аннулировано.

10.9 Расписание транзакций

Последовательное исполнение транзакции при использовании блокировок элементов замедляет процесс работы с БД, хотя и работает правильно.

Т1: LOCK A; UNLOCK A;

------------------------------------T2:LOCK A; UNLOCK A;

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

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

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

Т1: READ A; A:=A-10; WRITE A; READ B; B:=B+10; WRITE B;

T2: READ B; B:=B-20; WRITE B; READ C; C:=C+20; WRITE C;

Понятно, что любое последовательное расписание обладает свойством постоянства суммы A+B+C.

Пример расписания: А+В+С

Последовательное	Т1	Т2
	Read A
	A=A-10
	Write A
	Read B
	B=B+10
	Write B
		Read B
		B=B-20
		Write B
		Read C
		C=C+20
		Write C
Сериализуемое	Т1	Т2
	Read A
		Read B
	A=A-10
		B=B-20
	Write A
		Write B
	Read B
		Read C
	B=B+10
		C=C+20
	Write B
		Write C
Несериализуемое	Т1	Т2
	Read A
	A=A-10
		Read B
	Write A
		B=B-20
	Read B
		Write B
	B=B+10
		Read C
	Write B
		C=C+20
		Write C

Рис.10.9. Расписания транзакций

Отметим, что в последнем случае величина B увеличивается, а не уменьшается на 10 в силу того, что Т1 читает В прежде, чем Т2 записывает новые уменьшенные значения В. Предотвратить это сложно. В случае, когда допускаются произвольные операции с элементами невозможно проверить, дают ли два расписания одинаковый результат при всех начальных значениях элементов. На практике делаются некоторые упрощающие предположения относительно операций, выполняемых над элементами. Удобно предположить, в частности, что одинаковые их значения можно получить только при одной и той же последовательности операций. Поэтому нельзя считать, что (А+10)-20 и (А+20)-30 продуцируют одни и те же значения. Игнорируя алгебраические свойства арифметики, мы совершаем лишь «нефатальные» ошибки. Но зато расписание никогда не рассматривается как сериализуемое, если оно не является таким («фатальная» ошибка).

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

10.9.1 Протоколы и расписания

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

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

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

10.9.2 Модель транзакции

Рассмотрим простейшую модель транзакции, которая, однако, позволяет говорить о сериализуемости. В этой модели транзакция рассматривается как последовательность операторов блокирования и разблокирования

(LOCK и UNLOCK).

Сопоставляя каждой паре шагов LOCK A и последующего за ним UNLOCK A однозначную функцию f, можно более формально рассмотреть поведение транзакций. Отметим, что для данного элемента А транзакция может иметь более одной такой пары, то есть мы можем блокировать и разблокировать один и тот же элемент более одного раза. Пусть А0 - начальное значение А до исполнения любых транзакций. Значения, которые может принимать А, являются тогда формулами вида: f1f2…fn (А0) где f_i - функции, ассоциируемые с парами шагов LOCK A - UNLOCK A соответствующих транзакций.

Блокировка: LOCK A

Разблокировка: UNLOCK A

fn … f3 f2 f1 (A)

Пример: На рис. 10.10 приведены три транзакции и функции, ассоциированные с каждой парой LOCK A - UNLOCK A соответствующих транзакций.

Рис.10.10. Модели транзакций

На рис.10.11 показано возможное расписание этих транзакций и результат их воздействия на элементы A, B, C.

Рис.10.11. Расписание транзакций:

Является ли данное расписание сериализуемым. Пусть Т1 предшествует Т2, тогда

1) Т1Т2: Т1 предшествует Т2. Тогда конечным значением В было бы f3(f2(B0)), а не f₂(f₃(B₀)

2) Если Т2Т1: Т2 предшествует Т1. Не может быть f6 (f1(f5(A0))).

3) Т2Т3Т1: Т2 предшествует Т3 и Т1, Т3 предшествует Т1. Не может быть f1(f7(f5)).

4) Т3Т2Т1: Т2 предшествует Т3 и Т2, Т2 предшествует Т1. Не может быть f1(f5(f7)).

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

Алгоритм 1. Проверка сериализуемости расписания.

Входные данные. Расписание S для совокупности транзакций T1, …, Tk.

Метод. Построим ориентированный граф G, называемый графом предшествований, узлы которого соответствуют транзакциям. Определим дуги графа G. Пусть S есть a1;a2;…,an, где ai - действие вида Tj: LOCK Am или Tj: UNLOCK Am и Tj указывает транзакцию, к которой относится данный шаг. Для ai имеющего вид Tj: UNLOCK Am ищем следующее за ним действие ap вида Ts: LOCK Am. Если оно существует, то строим дугу от Tj к Ts. Интуитивный смысл этой дуги заключается в том, что в любом последовательном расписании, эквивалентном S, Tj должно предшествовать Ts..

Если в графе G имеется цикл, то S-не сериализуемо. При отсутствии циклов находим такой линейный порядок транзакций, чтобы Ti предшествовала бы Tj всякий раз, когда существует дуга Ti -> Tj. Это всегда может быть сделано при помощи процесса так называемой топологической сортировки, определяемого следующим образом. Из ациклического G следует, что в нём существует некоторый узел Tj, который не имеет входящих дуг. Запишем Tj в список, удалив его из графа. Процесс повторяется до тех пор, пока в графе не останется узлов. Порядок перечисления узлов в списке даёт последовательный порядок транзакций.

Пример. Рассмотрим расписание, приведенное на рис.10.11. В графе G, изображенном на рис.10.12 имеются узлы Т1, Т2, и Т3.

Рис.10.12. Граф предшествований для транзакций расписания на рис.10.11.

Поскольку в графе существует цикл, расписание представленное на рис.10.11 не является сериализуемым.

10.9.3 Протокол, гарантирующий сериализуемость

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

Например, на рис.10.10 транзакции T1 и T3 - двухфазные, а T2 - нет.

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

В некотором смысле двухфазный протокол - наилучший среди реально возможных. Можно показать, что для любой транзакции T1, не являющейся двухфазной, найдётся какая-либо транзакция T2, совместно с которой T1 сможет выполняться в несериализуемом расписании. Пусть транзакция T1 - не двухфазная. Тогда в T1 существует шаг UNLOCK A, предшествующий шагу LOCK B. Пусть T2, имеет вид T2: LOCK A; LOCK B; UNLOCK A; UNLOCK B; Легко видеть, что расписание на рис. 10.11 несериализуемо, поскольку обработка А требует, чтобы Т1 предшествовала Т2, в то время как обработка В требует обратного порядка.

Пример. Имеется расписание представленное на рис.3.13.

1 Т1:LOCK A

2 T1:UNLOCK A

3 T2:LOCK A

4 T2:LOCK B

5 T2:UNLOCK A

6 T2:UNLOCK B

7 T1:LOCK B

8 T1:UNLOCK B

Рис.10.13. Граф предшествований.

Так как в графе существует цикл, расписание несериализуемо.

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

10.10 Модели с блокировками для чтения и записи

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

1. Блокировки для чтения. RLOCK A (READ-LOCK A), что препятствует записи нового значения А любой другой транзакций во время чтения А транзакций Т. Однако блокировку А для чтения может одновременно установить любое число транзакций.

2. Блокировки для записи. WLOCK A (WRITE-LOCK). При блокировках для записи никакая другая транзакция не может установить для этого элемента блокировку для чтения, ни блокировку для записи. И блокировки для чтения, и блокировки для записи снимаются операторами UNLOCK (разблокировать). Два расписания эквивалентны, если

1. они продуцируют одно и то же значения для каждого элемента;

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

В системе поддерживается два типа блокировок:

1. Х - блокировка (XLOCK - eXclusive lock) - блокировка без взаимного доступа. WLOCK обозначает то же самое.

2. S - блокировка (SLOCK - Shared lock) - блокировка с взаимным доступом. RLOCK обозначает то же самое.

X - блокировка записи S - блокировка чтения.

1. Если транзакция Т блокирует кортеж А (Х-блокировка), то запрос любой другой транзакции к А будет отменён.

2. Если транзакция Т, блокирующая элемент А (S - блокировка), то

· запрос со стороны транзакции Т2 на Х-блокировку будет отвергнут

· запрос со строки Т2 на S-блокировку будет принят

Эти правила можно представить в виде матрицы совместимости (рис.10.14). Запрос транзакций Т1 и Т2 к одному элементу А. N-означает конфликтную ситуацию. Т2 - находится в состоянии ожидания. Y - полная совместимость, «-» - отсутствие блокировок.

Рис.10.14. Матрица совместимости транзакций

Проверка сериализуемости:

Алгоритм 2. Проверка сериализуемости расписаний с блокировками для чтения/записи.

Входные данные. Расписание S для совокупности транзакций T1,…,Tk.

Выходные данные. Получение ответа, является ли S сериализуемым.

Метод. Строим граф предшествованый G следующим образом. Узлы, как и прежде, соответствуют транзакциям. Дуги определяются следующими правилами:

1. Пусть в S транзакция Ti устанавливает блокировку элемента А для чтения, а Tj - следующая за ней транзакция (если она существует) - устанавливает блокировку А для записи. Тогда строим дугу из Ti в Tj.

2. Пусть транзакция Ti в S блокирует А для записи, а Tj - следующая за ней (если, конечно, такая существует) транзакция - устанавливает блокировку А для записи. Тогда строим дугу Ti -> Tj.

3. Пусть далее Tm - какая-либо транзакция, блокирующая А для чтения после того, как Ti снимает свою блокировку для записи, но перед тем, как Tj устанавливает блокировку А для записи (если Tj не существует, то Tm - любая транзакция, которая блокирует А для чтения после того, как Ti разблокирует его. Тогда строим дугу Ti -> Tm.

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

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

Пример: Показано расписание 4-х транзакций.

(1) - - - - - - - - - - - - - WLOCK A

(2) - - - - - - - - - - - - - - - - - - - - - WLOCK B

(3) - - - - - - - - - - - - - UNLOCK A

(4) RLOCK A

(5) UNLOCK B

(6) WLOCK B

(7) RLOCK A

(8) UNLOCK B

(9) WLOCK B

(10) UNLOCK A

(11) UNLOCK A

(12) - - - - - - WLOCK A

(13) UNLOCK B

(14) - - - - - - - RLOCK B

(15) - - - - - - - - - - - - - - - - - - - - UNLOCK A

(16) - - - - - - - UNLOCK B

Т1 Т2 Т3 Т4

Рис.10.15. Расписание транзакций

Первый оператор UNLOCK A выполняется на шаге 3, когда T3 снимает свою блокировку элемента А для записи. За шагом 3 следует блокировка А для чтения транзакциями Т1 и Т2 (шаги 4 и 7) и блокировка этого элемента для записи транзакцией Т4 на шаге (12). Таким образом Т1, Т2 и Т4 должны следовать за Т3 и мы строим дуги из Т3 в эти узлы.

Рис.10.16. Граф проверки сериализуемости

В связи с тем, что Т4 снимает блокировку В для записи на шаге 5, а следующую блокировку В для записи устанавливает Т3 строится дуга из Т4 и Т3. Образуется цикл, свидетельствующий о том, что расписание не является сериализуемым.

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

10.11 Блокировки в Visual FoxPro

В Visual FoxPro можно устанавливать блокировки на всю таблицу или на отдельные записи таблицы.

Существуют: 1. Полная блокировка 2. Блокировка изменений

Для установки полной блокировки используется команда

SET EXCLUSIVE ON/OFF

Запрещается даже чтение посторонним

Для установки блокировки изменений таблицы используется функция

FLOCK - блокировка таблицы

Разрешается чтение посторонним клиентам

LOCK (RLOCK) - блокировка записи

Пример:

SET EXCLUSIVE ON

SELECT 0

USE SORT

DO WHILE .T.

If FLOCK (“SOTR”)

* вызов процедуры

DO PROC

* снимаем блокировку

UNLOCK IN SOTR

EXIT

ELSE

@ 10,10, SAY “Устанавливается блокировка, подождите”

ENDIF

ENDDO

Вопросы

1. Транзакция, что это?

2. Какие действия совершает транзакция по отношению к БД?

3. Что происходит с системой в случае аварийного завершения транзакции?

4. Какие операторы сигнализируют об успешном и неудачном завершении транзакции?

5. Назовите основные свойства транзакции.

6. Что означает термин параллелизм в среде СУБД?

7. Какие существуют проблемы параллельных процессов?

8. Причина потери результатов обновления элементов БД?

9. Из-за чего возникают “грязные данные”?

10. Какие конфликты возникают при параллельной работе транзакций?

11. Назовите графики запуска транзакций.

12. Какой график транзакций называется сериализуемым?

13. Назовите способы разрешения конкуренций между транзакциями.

14. Проблемы блокировок транзакций?

15. Назовите способы предотвращения «тупиков».

16. Какова формальная модель транзакций?

17. Как осуществляется проверка сериализуемости транзакций?

18. Протокол, гарантирующий сериализуемость?

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

11. Безопасность БД

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

Меры безопасности

1. Идентификация и установление подлинности

2. Предоставление полномочий

3. Обеспечение целостности БД

4. Кодирование информации

11.1 Идентификация и установление подлинности

Для установления подлинности пользователя употребляются пароли.

Пароли:

1. Простые пароли

2. Однократного использования. Пользователю выдается список из N паролей. Такие же N паролей хранятся в ЭВМ.

Данная схема обеспечивает большую степень безопасности, но она является и более сложной.

Пример: xyz xyz

абв абв

Trim Trim

3. «Запрос - ответ». В системе хранятся данные об идентификации личности. Машина задает вопросы пользователю, известные только ему.

4. Установление пользователем подлинности системы. Пароли используются не только для установления пользователя по отношению к системам, но и для обратного установления подлинности. Это важно, например, в сетях ЭВМ. Такую проверку называют процедурой в режиме “рукопожатия “.

Из машины посылается некоторое число х, на другой машине есть функция преобразования f(x). После преобразования посылается ответ f(х). Первая машина определяет: верна ли функция преобразования или нет. Число посылается открыто, а функция преобразования по линиям связи не передается.

Пример

Х f(x)

1312 4

4752 86

5472 76

6836 120

...

Пусть d1d2d3d4 - четырехзначное десятичное число

Функция преобразования может иметь следующий вид:

Пусть x=4752

Определение полномочий:

Наименование	ФИО	Квалифи- кация	Оклад	Транспорт	Прогноз объема продаж	Цена на покупку
Отдел кадров	11	11	11	00	00	00
Транс-ый отдел	00	00	00	11	00	00
Касса	01	00	11	00	00	00
Отдел сбыта	00	00	00	00	11	01
Отдел МТС	01	00	00	01	11	01
Исслед-ий отдел	01	01	00	01	01	01

Где

00 - запрос доступа

01 - право читать

10 - право записи

11 - право читать и писать

Механизм представления.

Механизм представления используется для скрытия данных.

CREATE VIEW <имя> [поля] AS<подзапрос>

CREATE VIEW spec 2202 AS SELECT *

FROM STUD

WHERE SPEC=”2202”

11.2 Система привилегий

Привилегии предоставляются с помощью:

оператора GRANT языка SQL

GRANT <привилегии> [ON_тип объекта] TO <пользователь>

GRANT SELECT ON TABLE stud TO Данилов

GRANT SELECT, UPDATE ON TABLE stud TO Огородников

GRANT ALL PRIVILEGES ON TABLE stud, disc, st TO Лаврентьева

GRANT SELECT ON TABLE stud TO PUBLIC

Пример

CREATE VIEW prim1 AS

SELECT fio, gr

FROM stud

GRANT SELECT ON prim1 TO Коля, Света

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

Пользователь U1 может предоставить привилегии пользователю U2 с возможностями GRANT (путем фразы WITH GRANT OPTION в предложении GRANT)

Далее U2 может в свою очередь предоставить привилегии U3 и т.д.

U1 ->U2 -> U3 WITH GRANT OPTION

Пользователь U1

GRANT SELECT ON TABLE STUD TO U2 WITH GRANT OPTION

Пользователь U2

GRANT SELECT ON TABLE STUD TO U3 WITH GRANT OPTION

Пользователь U3

…

Пользователь U4

Отмена полномочий может быть осуществлена оператором REVOKE

REVOKE <привилегии> [ON_тип объекта] FROM <пользователь>

REVOKE SELECT ON TABLE stud FROM U2

Если пользователь U1 отменит привилегии пользователю U2, то все остальные будут отменены каскадно.

11.3 Целостность данных

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

В БД сведения о предметной области хранятся в информационной модели. Любые изменения в ПО, значимое для построения модели, должно отражаться в БД.

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

Различаю следующие ограничения целостности:

1. Логические ограничения

2. Внутренние ограничения

3. Явные ограничения

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

Год окончания вуза должен превышать значение атрибута год рождения в записи типа служащий. В учебной группе по списку должно быть не более 35 человек. Возраст сотрудника не меньше 18 и не больше 80 лет.

Внутренние ограничения - связаны со структурой данных.

Пример: запись не может состоять из 250 полей. В иерархической модели связи должны быть древовидными.

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

Пример: 1) в БД не может быть двух записей с одинаковыми ключами. 2) Шифр детали представляется целым числом из 4х десятичных цифр.

В SQL вводятся также операторы ограничения:

CHEK - ограничения на значение атрибута

NULL - возможность хранения неопределенного значения

DEFAULT - определение значения по умолчанию

UNIQUE - гарантирует уникальное значение в столбце

PRIMARY KEY - определяет первичный ключ

Пример: Для задания ограничений отдельного столбца стандарт ISO задает оператор

CREATE DOMAIN <имя_файла> [AS] тип данных

[DEFAULT <значение>]

[CHECK <условие>]

Например, имя столбца с указанием пола (SEX)

CREATE DOMAIN sex_type AS CHAR CHECK (Value IN(`M','F'))

В результате будет создан домен под именем Sex_type, состоящий из двух символов M и F. В таблице Sotr(fio, sex, dolgn, …) имеется столбец sex. Тогда столбец sex в таблице можно описать, используя домен sex_type.

11.4 Шифрование данных

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

Зашифрованное сообщение называется криптограммой

1. Шифр простой подстановки. Буквы кодируемого сообщения прямо заменяются буквами того же или другого алфавита.

АБВГД

ВЕЗКН

2. Шифр многоалфавитной подстановки.

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

C=(a*P+S)modK,

где a - десятичный коэффициент, Р - номер буквы, S - сдвиг.

3. Шифр Цезаря. Является частным случаем многоалфавитной подстановки.

С=Р+К*(mod27) 1<=K<=27

C=P+2*(mod27)

Пример:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

A B C D E F G H I J K L M N O P Q R S T

4. Шифр Вижинера (универсальный):

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

Например, необходимо закодировать слово DECODER. Пусть PIES - ключ

Вопросы

1. Что понимают под безопасностью баз данных?

2. Перечислите меры безопасности

3. Какие существуют методы идентификации и установления подлинности?

4. В каких случаях используют процедуру в «режиме рукопожатия»?

5. Для чего используется механизм представления?

6. Как на SQL организуется механизм представления?

7. Что позволяет оператор GRANT?

8. Как осуществляются факультативные возможности GRANT?

9. Какие существуют ограничения целостности данных?

10. Приведите примеры логических ограничений.

11. Назовите основные методы шифрования данных.

12. Хранилище данных

Согласно аналитическим оценкам объем информации в мире удваивается каждые 2-3 года. Этот потоп, цунами данных приходит из науки, бизнеса, Интернета и других источников. Среди самых больших баз данных в 2003г. France Telecom имела базу размером в 30000 миллиардов байт, а Alexa Internet Archive - 500000 миллиардов байт.

Еще в 1989г. 1 мегабайт считался размером для большой базы данных. В настоящее время предвидеться для астрономии иметь во много терабайт, а затем петабайт. (1 терабайт = 1000 миллиардов байт, а 1 петабайт = 1000 терабайт, 1 гигабайт = 1024 мегабайт).

Из-за огромного количества информации очень малая ее часть будет когда-либо увидена человеческим глазом. Надежда - применение Data Mining. Data Mining (называемая Knowledge Discovery In Data) - процесс нахождения (обнаружения) потенциально полезных знаний в базах данных.

В настоящее время многие предприятия широко используют в своей повседневной деятельности сбор, хранение и обработку информации на основе концепции базы данных. Системы подобного типа называются системами оперативной обработки транзакций или OLTP системами (Online Transaction Processing).

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

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

Так как поиск является сложной задачей, то появился класс программных систем, призванных облегчить работу людей, выполняющих анализ. Такие системы принято называть системами поддержки принятия решений - СППР (DSS, Decision Support System).

Задачи СППР:

- ввод данных - OLTP (Online transaction processing);

- хранение данных - СУБД и концепция хранилища данных (ХД);

- анализ данных.

Анализ данных может производится на основе следующих данных:

- ИПС на базе реляционных СУБД и запросов с использованием языка SQL;

- Подсистемы оперативного анализа OLAP (Online analytical processing);

- Подсистема интеллектуального анализа Data Mining (“добыча данных”).

12.1 Концепция хранилища данных

Первые сведения по ХД появились в 1988г. Г.Инмон подробно описал концепцию в своей монографии “Построение хранилищ данных”.

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

Хранилище данных - предметно-ориентированный, интегрированный, неизменчивый, поддерживающий хронологию набор данных, организованный для целей поддержки принятия решений.

В СППР разделение данных происходит в двух направлениях:

1) ОИД - оперативные источники данных (это оперативные БД, файлы, электронные таблицы и т.п.)

2) структуры данных, предназначенных для анализа - это ХД.

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

Рис.12.1. Схема системы поддержки принятия решений (СППР)

Все данные в ХД делятся на три категории:

- детальные данные (переносимые непосредственно из ОИД);

- агрегированные (получают путем суммирования числовых фактических данных по определенным измерениям);

- метаданные (данные о данных).

Большинство СППР работают не с детальными данными, а с агрегированными данными. Перенос данных в ХД называют ETL - процессом (E -extraction, T - transformation, L - loading) - извлечение, преобразование и загрузка.

12.2 Многомерная модель данных

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

Рис.12.2. Многомерная модель хранилища данных

Ребрами такого куба являются измерения, а ячейками - меры.

Измерения:

Исполнитель (предприятие - подразделение - отдел - служащий).

Время (Год - квартал - месяц - день).

Мера (measures) - представляет ячейку, которая хранит факты (объемы продаж, остатки на складе, издержки и т.п.).

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

Срез (Slice) - формирует подмножество многомерного массива данных.

Вращение (Rotate) - изменение расположения измерений.

Консолидация (Drill Up) - агрегирование.

Детализация (Drill Down)

12.3 OLAP - системы

OLAP (On-Line Analytical Processing) - технология оперативной аналитической обработки данных, использующая методы и средства для сбора, хранения и анализа многомерных данных в целях поддержки процесса принятия решений.

18 правил, предъявляемых к OLAP:

- многомерное концептуальное представление данных,

- доступность,

- архитектура “клиент - сервер”

- прозрачность,

- обработка ненормализованных данных,

- универсальность измерений и т.д.

OLAP система должна обеспечивать выдачу большинства ответов в пределах не более 5 сек.

Архитектура OLAP - систем

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

- MOLAP - используют многомерные БД,

- ROLAP - используют реляционные БД,

- HOLAP - используют и многомерные и реляционные БД.

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

Достоинство - быстрый поиск, так как база данных денормализована и содержит агрегированные данные. Недостаток - чувствительность к изменениям. Так при добавлении нового измерения приходится изменять структуру всей БД. Рекомендуется для небольших БД (не более нескольких гигабайт).

ROLAP

Реляционные БД дополняются средствами анализа. Распространены две основные схемы реализации многомерного представления данных с помощью реляционных таблиц: схема “Звезда” и схема “Снежинка”.

Основными составляющими таких схем являются денормализованные таблицы фактов (Fact Table) и массивы таблиц измерений (Dimension Table).

Фактами являются:

- события (телефонный звонок, снятие денег со счета и т.д.),

- “моментальные снимки” - рассматривается состояние объекта (например, банковского счета, объем продаж за день или дневная выручка).

Таблицы измерений содержат неизменяемые, либо редко изменяемые данные.

Рис.12.3. Модель хранилища данных по схеме «звезда»

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

HOLAP

Используют гибридную архитектуру, объединяющую технологии ROLAP и MOLAP. MOLAP лучше работает с более плотными данными, а ROLAP лучше, когда данные являются довольно разделимыми.

12.4 Интеллектуальный анализ данных

(Data Mining - добыча данных)

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

Пятницкий-Шапиро в 1996г. дали следующее определение добычи данных.

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

Свойства обнаруживаемых знаний:

- должны быть новые, ранее неизвестные,

- нетривиальны,

- практическими,

- доступными для понимания.

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

Вопросы

1. Дайте определение хранилища данных

2. Задачи СППР

3. На основе, каких средств, производится анализ данных?

4. Особенности многомерной модели данных

5. Дайте определение OLAP системам

6. Правила предъявляемые к OLAP системам

7. Способы реализации многомерных моделей данных

8. Определение Data Mining

9. Свойства обнаруживаемых знаний

Размещено на Allbest.ru

...