Будь умным!


У вас вопросы?
У нас ответы:) SamZan.net

соединение и ее свойства

Работа добавлена на сайт samzan.net:

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 7.11.2024

2.3    Базы данных [5-7]  ТЕБЕНЬКОВ Е.С.

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

2.  Операция «соединение» и ее свойства.

3.  Разложение без потерь. Теорема. Примеры.

4.  Полностью соединимые отношения. Примеры.

5.  Операторы описания данных в SQL.

6.  Операторы манипулирования данными в SQL.

7.  Управление транзакциями.

8.  Технологии «клиент-сервер».

9.  Оператор select.

10.  Индексация. Достоинства и недостатки. Примеры.

11.  В-дерево. Добавление и удаление элементов.

12.  Методы прямого доступа.

13.  Архитектуры БД.

14.  Управление правами доступа в SQL.

15.  Модель Чена.

16.  Примеры бинарных связей.

17.  Правила Джексона для перехода от модели Чена к реляционной модели.

18.  Реляционная модель данных. 12 правил Кодда.

19.  Ограничения целостности в реляционной модели данных и их поддержка в SQL.

20.  Восстановление данных в БД.


   

   5Н.Ф.

  4Н.Ф.

3Н.Ф.                                              Н.Ф.Б.К.

2Н.Ф.

1Н.Ф.

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

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

Таблица находится в первой нормальной форме (1Н.Ф.), если все ее атрибуты атомарные.

Таблица находится во второй нормальной форме (2Н.Ф.), если она находится в 1Н.Ф. и все не ключевые атрибуты функционально полно зависят от ключа.

Таблица находится в третьей нормальной форме (3Н.Ф.), если она находится во 2Н.Ф. и устранены транзитивные зависимости внутри таблицы.

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

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

Таблица находится в пятой нормальной форме (5Н.Ф.), если она разложима без потерь.

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

фамилия

статус

Город пос-

тавщика

Название детали

вес

цвет

Город детали

количество

Иванов

70

Пермь

гайка

12

красный

Пермь

100

болт

13

синий

Кунгур

200

...

...

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

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

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

После данного разбиения первая таблица будет находится не только во второй нормальной форме, но и в третьей. А во второй таблице сохранятся аномалии технологических операций, т.е. вторую таблицу необходимо еще разбить на две: таблица 2.1 с полями - название детали, вес, цвет, город детали; таблица 2.2 с полями - фамилия поставщика, название детали, количество(эти две таблицы находятся в 3Н.Ф.).

Первая нормальная форма:

- запрещает повторяющиеся столбцы (содержащие одинаковую по смыслу информацию);

- запрещает множественные столбцы (содержащие значения типа списка и т.п.);

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

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

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

это расчетные столбцы, значения которых можно получить путем каких-либо

манипуляций с другими столбцами таблицы. Для приведения таблицы в третью

нормальную форму такие столбцы из таблиц надо удалить.

Таблица находится в первой нормальной форме (1Н.Ф.), если все ее атрибуты атомарные.

Таблица находится во второй нормальной форме (2Н.Ф.), если она находится в 1Н.Ф. и все не ключевые атрибуты функционально полно зависят от ключа.

Таблица находится в третьей нормальной форме (3Н.Ф.), если она находится во 2Н.Ф. и устранены транзитивные зависимости внутри таблицы.

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

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

Таблица находится в пятой нормальной форме (5Н.Ф.), если она разложима без потерь.

Метод  начинается с универсального отношения и основан на постепенном переходе к пятой нормальной форме.

Пример:

Фамилия автора

произведение

Пушкин

Евгений Онегин, Капитанская дочка, ...

Лермонтов

Герой нашего времени, Кавказский пленник, ...

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

автор

произведение

Пушкин

Евгений Онегин

Пушкин

Капитанская дочка

Пушкин

...

Лермонтов

Герой нашего времени

Лермонтов

Кавказский пленник

Лермонтов

...

Таблица находится в первой нормальной форме, является реляционной таблицей.

Пример:

r( поставщик, статус, город поставщика, деталь, количество) – это универсальное отношение.  Установим функциональные зависимости:

поставщик +деталь = первичный ключ;

П+Д         С (от поставщика и детали зависит статус);

П+Д         Г (город);

П+Д         К (количество);

Г           С;

П          С;

П           Г.

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

Т1(Поставщик, Статус, Город), Т2(Поставщик, Деталь, количество). Данные 2 находятся во второй нормальной форме. Установим функциональные зависимости для Т1:

П        С;

П        Г;

Г         С.

                                             П                    С   это транзитивная зависимость.

 


                                                                     Г            

В таблице Т1 сохраняются аномалии технологических операций: при удалении поставщика теряется зависимость  Город       Статус, не можем добавить нового поставщика пока не знаем статуса города. Следовательно необходимо таблицу Т1 разбить еще  на 2: Т11(П,Г) и Т12(Г,С).

Таблицы Т11, Т12, Т2 представляют нашу базу в третьей нормальной форме.

Пример:

Т(№служащего, фамилия, №проекта, название работы).

Предположим, что в таблице нет однофамильцев, тогда ключом является либо №служащего+№проекта, либо фамилия+№проекта,

тогда  №служащего       фамилия. Приведем таблицу в Н.Ф.Б.К., для этого разложим таблицу на две: Т1(№служащего, фамилия), Т2(№служащего, №проекта, Название работы).

Пример:

Т(№детали,№проекта,№поставщика).

№проекта+№детали       №поставщика;

№поставщика       №проекта. Следовательно  нужно разбить еще на 2:

Т1(№детали, №поставщика) и Т2(№поставщика,№проекта).

Чтобы перевести таблицу в 4Н.Ф. нужно многозначную Ф.З. выделить в отдельную таблицу,  в 5Н.Ф. все таблицы должны соединяться без потерь.


2. Операция «соединения» и ее свойства.

Реляционная алгебра.

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

Реляционная алгебра, определенная Коддом состоит из 8 операторов, составляющих 2 группы:

  1.  традиционные операции над множествами (объединение, пересечение, вычитание, декартово произведение);
  2.  специальные реляционные операции (выборка, проекция, соединение, деление).

В основе реляционной модели лежит понятие «отношение».

 Отношение представляет собой подмножество декартова произведения доменов.

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

 Декартовым произведением доменов D1, D2,...Dn  называется

 где D1 = {d1.1,d1.2,...d1.k}  и т.д.

множество всех кортежей состоящих из k элементов - по одному из каждого домена.

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

Математически отношение записывается как

 Кортежем называется элемент отношения.

Математическое отношение используется двояко:

  1.  Для представления набора объектов (набор объектов - это множество подобных объектов).
  2.  Для предоставления связей между наборами объектов.

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

 Схемой отношения называют список имен атрибутов отношения. Если отношение R, а его схема имеет атрибуты A1,A2,...Ak , то схема отношения записывается как

R(A1,A2,...Ak)

  Краткий обзор операторов реляционной алгебры.

            Выборка – возвращает отношение, которое содержит все кортежи определенного отношения, удовлетворяющие некоторым условиям. Операция выборки называется также операцией ограничения (restrict - ограничение, сейчас чаще принимается выборка - SELECT).

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

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

            Объединение  возвращает отношение, содержащее все кортежи, которые принадлежат или одному из двух определенных отношений, или обоим.

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

            Вычитание – возвращает отношение, содержащее все кортежи, которые принадлежат первому из двух определенных отношений и не принадлежат второму.

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

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

Договоримся, что малыми латинскими буквами мы будем обозначать таблицы, большими латинскими буквами – атрибуты и множества атрибутов. Например, r(R) – это таблица r со множеством атрибутов R.

R(A,B,C.D) – ключевые атрибуты подчеркиваются  - R={A,B,C,D}.

Операция соединения (основная).

Обозначение: Join или      .

Существует внутренняя операция соединения и внешняя, при этом внешняя делится на правую и левую.

  1.  Внутренняя

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

r(A,B,C)         s(A,B,D) = q(A,B,C,D)

  1.                      11a               112a
  2.                      11b              112b

     123                    42c              113a

  1.                                 113b
  2.   421c

операция соединения для таблиц с одинаковыми схемами равносильна операции пересечения:

r(A,B)          s(A,B) = q(A,B)

11                   11           11

12                   42           42

14

42

Операция соединения для таблиц с разными схемами равносильна декартовому произведению:

r(A,B)          s(C,D) = q(A,B,C,D)

11                cd                11cd     

12                c1d              11c1d

14                                    12cd

42                                    12c1d

                                       14cd

                                       14c1d

                                       42cd

                                       42c1d

б) Тета-соединение ().

Это соединение не обязательно по равенству, операция соединения происходит по любой операции сравнения(=(эквивалентное соединение),<>, <,>).

Тета-соединение осуществляется не обязательно по одноименным столбцам, а по разным тоже, но столбцы должны быть определены на одних и тех же доменах.

r(A,B,C)             s(D,E) = q (A,B,C,D,E)

                 B=D

a1c                          1e               a1c1e

a12c                       1e1             a1c1e1

a11c2                     2e               a2c2e

a13c                       2e1             a12c2e1

                                                a11c21e

                                                a11c21e1

r(A,B,C)            s(D,E) = q (A,B,C,D,E)

                  B>D

a1c                         1e               a12c1e

a12c                       1e1             a12c1e1

a11c2                     2e               a13c1e1

a13c                       2e1             a13c1e

                                                a13c2e

                                                a13c2e

  1.  Внешнее соединение. Рассмотрим на примере естественного соединения. тогда внешнее соединение выполняется по тем же правилам, что и естественное, но в ответ выписываются строки из левой таблицы, если соединение левое (из правой таблицы, если соединение правое).

Пример:

r(A,B,C)              s(A,D) = q(A,B,C,D)

                  left

1ac                           1d            1acd

2a1c                         2d            1acd1

1ac1                        1d1          2a1cd

3ac                                          1ac1d

4a1c                                        1ac1d1

                                              3ac null

                                              4a1c null

Свойства операции:

  1.  С помощью операции соединения можно выполнить операцию селекции, при этом операция селекции равносильна квантору существования. Если дано r (R) и необходимо выполнить операцию селекции , то ее можно выполнить с помощью операции соединения .

  1.  Операция соединения коммутативна.
  2.  Операция соединения ассоциативна: =
  3.  Операция соединения дистрибутивна относительно операций пересечения, объединения и разности.

  1.  свойство идемпотентности: qq=q; qr=q(qr)
  2.  свойство полусоединения: .

3. Разложение без потерь. Теорема. Примеры

Реляционная алгебра.

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

Реляционная алгебра, определенная Коддом состоит из 8 операторов, составляющих 2 группы:

  1.  традиционные операции над множествами (объединение, пересечение, вычитание, декартово произведение);
  2.  специальные реляционные операции (выборка, проекция, соединение, деление).

В основе реляционной модели лежит понятие «отношение».

 Отношение представляет собой подмножество декартова произведения доменов.

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

 Декартовым произведением доменов D1, D2,...Dn  называется

 где D1 = {d1.1,d1.2,...d1.k}  и т.д.

множество всех кортежей состоящих из k элементов - по одному из каждого домена.

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

Математически отношение записывается как

 Кортежем называется элемент отношения.

Математическое отношение используется двояко:

  1.  Для представления набора объектов (набор объектов - это множество подобных объектов).
  2.  Для предоставления связей между наборами объектов.

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

 Схемой отношения называют список имен атрибутов отношения. Если отношение R, а его схема имеет атрибуты A1,A2,...Ak , то схема отношения записывается как

R(A1,A2,...Ak)

  Краткий обзор операторов реляционной алгебры.

            Выборка – возвращает отношение, которое содержит все кортежи определенного отношения, удовлетворяющие некоторым условиям. Операция выборки называется также операцией ограничения (restrict - ограничение, сейчас чаще принимается выборка - SELECT).

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

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

            Объединение  возвращает отношение, содержащее все кортежи, которые принадлежат или одному из двух определенных отношений, или обоим.

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

            Вычитание – возвращает отношение, содержащее все кортежи, которые принадлежат первому из двух определенных отношений и не принадлежат второму.

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

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

Договоримся, что малыми латинскими буквами мы будем обозначать таблицы, большими латинскими буквами – атрибуты и множества атрибутов. Например, r(R) – это таблица r со множеством атрибутов R.

R(A,B,C.D) – ключевые атрибуты подчеркиваются  - R={A,B,C,D}

Условие разложения без потерь.

q(R,S)  r=    s=

r       s=     =q’

q’q(R,S) т.е.  q’ есть надмножество q

Если  q’=q, то это разложение без потерь.

Пример:

R(X,Y,Z)             r1(X,Y)         r2(X,Z)                r1       r2 = (X,Y,Z)

      123                      12                  13                      123

      323                      32                  33                      127

      117                      11                  17                      122

      132                      13                  12                      323

      417                      41                  47                      113

                                                                                  117

                                                                                  112

                                                                                  133

                                                                                  137

                                                                                  132

                                                                                  417

то есть это разложение с потерями.

Рассмотрим другое измерение:

r3(X,Y)             r4(Y,Z)                   r3      r4 = (X,Y,Z)

       12                    23                                          123

       32                    17                                          323

       11                    32                                          117

       13                                                                  132

  1.                     417

это разложение без потерь.

Альтернативное доказательство!!!

Теорема Хита.

Пусть задано отношение r {A, B, C} (A, B и C, в общем случае, являются составными атрибутами) и выполняется FD AB.

Рис. 1.  Результат естественного соединения отношений СЛУЖ и ЗАРП_ПРО

Тогда r = (r PROJECT {A, B}) NATURAL JOIN (r PROJECT {A, C}).

Доказательство. Прежде всего, докажем, что в теле результата естественного соединения (обозначим этот результат через r1) содержатся все кортежи тела отношения r. Действительно, пусть кортеж {a, b, c}  r. Тогда по определению операции взятия проекции {a, b}  (r PROJECT {A, B}) и {a, с}  (r PROJECT {A, С}). Следовательно, {a, b, c}  r1. Теперь докажем, что в теле результата естественного соединения нет лишних кортежей, т. е. что если кортеж {a, b, c}  r1, то {a, b, c}  r. Если {a, b, c}  r1, то существуют {a, b}  (r PROJECT {A, B}) и {a, с}  (r PROJECT {A, С}). Последнее условие может выполняться в том и только в том случае, когда существует кортеж {a, b*, c}  r. Но поскольку выполняется FD AB, то b = b* и, следовательно, {a, b, c} = {a, b*, c}.Конец доказательства.

Для иллюстрации общего случая применения теоремы Хита рассмотрим отношение СЛУЖАЩИЕ_ОТДЕЛЫ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_ОТД, ПРО_НОМ} (рис 2). Атрибут СЛУ_ОТД содержит номера отделов, в которых работают служащие, а ПРО_НОМ – номера проектов, в которых служащие принимают участие. Каждый служащий работает только в одном отделе, т. е. имеется FD СЛУ_НОМСЛУ_ОТД, но один служащий может участвовать в нескольких проектах.

Рис. 2.  Декомпозиция без потерь по теореме Хита. В отношении СЛУЖАЩИЕ_ОТДЕЛЫ_ПРОЕКТЫ  атрибут СЛУ_НОМ не является возможным ключом, но, как показано на рис 2., наличия FD СЛУ_НОМСЛУ_ОТД оказывается достаточно для декомпозиции этого отношения без потерь.


4. Полностью соединимые отношения. Примеры

Реляционная алгебра.

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

Реляционная алгебра, определенная Коддом состоит из 8 операторов, составляющих 2 группы:

  1.  традиционные операции над множествами (объединение, пересечение, вычитание, декартово произведение);
  2.  специальные реляционные операции (выборка, проекция, соединение, деление).

В основе реляционной модели лежит понятие «отношение».

 Отношение представляет собой подмножество декартова произведения доменов.

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

 Декартовым произведением доменов D1, D2,...Dn  называется

 где D1 = {d1.1,d1.2,...d1.k}  и т.д.

множество всех кортежей состоящих из k элементов - по одному из каждого домена.

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

Математически отношение записывается как

 Кортежем называется элемент отношения.

Математическое отношение используется двояко:

  1.  Для представления набора объектов (набор объектов - это множество подобных объектов).
  2.  Для предоставления связей между наборами объектов.

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

 Схемой отношения называют список имен атрибутов отношения. Если отношение R, а его схема имеет атрибуты A1,A2,...Ak , то схема отношения записывается как

R(A1,A2,...Ak)

  Краткий обзор операторов реляционной алгебры.

            Выборка – возвращает отношение, которое содержит все кортежи определенного отношения, удовлетворяющие некоторым условиям. Операция выборки называется также операцией ограничения (restrict - ограничение, сейчас чаще принимается выборка - SELECT).

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

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

            Объединение  возвращает отношение, содержащее все кортежи, которые принадлежат или одному из двух определенных отношений, или обоим.

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

            Вычитание – возвращает отношение, содержащее все кортежи, которые принадлежат первому из двух определенных отношений и не принадлежат второму.

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

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

Договоримся, что малыми латинскими буквами мы будем обозначать таблицы, большими латинскими буквами – атрибуты и множества атрибутов. Например, r(R) – это таблица r со множеством атрибутов R.

R(A,B,C.D) – ключевые атрибуты подчеркиваются  - R={A,B,C,D}

Условие полного соединения.

Дано r(R)   и s(S), тогда q(RS)=r       s

 , если выполняется равенство, то r полностью соединимо.

, если выполняется равенство, то s полностью соединимо.

Пример:

r(A,B)    s(A,B)       q(A,B,C)

   ab1         b1c            ab1c

   ab2

A,B

 ab    – неполное соединение

B,C

b1c     - полное соединение.

Для того чтобы было полное соединение необходимо, чтобы в соединяемых столбцах были все значения R и S.


5. Операторы описания данных в SQL

Data Definition Language (DDL) (язык описания данных) - это семейство компьютерных языков, используемых в компьютерных программах для описания структуры баз данных.

На текущий момент наиболее популярным языком DDL является SQL, используемый для получения и манипулирования данными в РСУБД, и сочетающий в себе элемены DDL и DML.

Функции языков DDL определяются первым словом в предложении (часто называемом запросом), которое почти всегда является глаголом. В случае с SQL эти глаголы - "create" ("создать"), "alter" ("изменить"), "drop" ("удалить"). Это превращает природу языка в ряд обязательных утверждений (команд) к базе данных.

Языки DDL могут существенно различаться у различных производителей СУБД. Существует стандарт SQL, установленный ANSI, но производители СУБД часто предлагают свои собственные "расширения" языка.

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

  1.  create database имя – создание базы данных;
  2.  close database – закрыть текущую базу данных;
  3.  open database имя – начать работу с существующей базой данных;
  4.  drop database имя – удаление БД;
  5.  create table имя  (поле тип атрибуты,

                                  поле1  тип   атрибуты...)

                                  атрибуты таблицы

Типы данных в SQL.

  1.  Integer – целое,занимает 4 байта;
  2.  Smallint - короткое целое, занимает 2 байта;
  3.  Serial- 4 байта, последовательность целых, испорльзуется в качестве ключа, генерируется автоматически, может быть последовательная генерация или случайная.
  4.  Float – число с плавающей точкой, занимает 8 байт;
  5.  Smallfloat – короткое число с плавающей точкой, занимает 4 байта;
  6.  decimal(P[,n]) – упакованное число,  Р – общее количество цифр в числе,  n- обозначает сколько чисел после запятой,  C положительное число,  D – отрицательное;
  7.  money(P,n) – для  представления денежных едениц;
  8.  date – для хранения дат;
  9.  datetime a to b – временный интервал от а до b, значения а и b могут быть следующие:

   year

   day

   month

   hour

   minute

   second

   fraction(1,2,3),

например, datetime year to hour                   2000-04-10-13

  1.  char – строки постоянной длины;
  2.  char(n) – строки постоянной длины до n;
  3.  varchar – строки до 255;
  4.  varchar(n) – строки до n;
  5.  text – произвольные тексты до 2ГБ;
  6.  byte произвольная последовательность байтов до 2ГБ;
  7.  null – пустое значение, причем 2 пустых значения не равны между собой.

Атрибуты, используемые для описания таблиц.

  1.  Атрибуты, описывающие характеристики столбца:

 Primary key - данное поле является первичным ключом;

References имя_таблицы (имя_поля) – данный столбец является внешним ключом, он взят из таблицы и поля, указанного в атрибуте;

Not null – в этом столбце не должно быть пустых значений;

Default значение – указывает значение, которое принимается по умолчанию.

Unique  -  все значения в этом поле должны быть уникальными, по умолчанию      поле Primary key должно быть Not null и Unique;

Check (Условие) – задает условие, которое должно быть истинным при заполнении информации в этом поле.

  1.  Атрибуты на уровне таблицы.

Check (Условие) – это значение должно быть истинным, чтобы компьютер признал все изменения правильными;

Unique (список полей) – все значения в комбинации полей должны быть уникальными;

Primary key (список полей) – указывается на уровне таблицы, если первичный ключ состоит из нескольких полей;

References имя_поля1  from имя_таблицы1 (поле1) – в нашей таблице имя_поля1 берется из таблицы1, поля1.

Обработка ссылочной целостности.

                        Restrict          - указывает каким образом поддерживается

On delete          cascade            процедура удаления в связующей таблице.

                         null

              

                        restrict            - указывае каким образом поддерживается      

On update       cascade              процедура изменения в связующей таблице.

                        null

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

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

Null указывает, что ключи связей получают значение null.

Рассмотрим  на примере оn update:

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

№поставщика

Фамилия

1

Петров

1

Петров

№поставщика

Название_детали

вес

количество

1

Болт

13

244

1

Гайка

12

200

Если в оn update стоит restrict, то при изменении №поставщика, например, на 10, будет выдано сообщение о том, что данный номер используется в связующей таблице, и изменение будет запрещено.

Если в оn update стоит cascade, то сначала произойдет изменение в №поставщика в связующей таблице, и только потом изменится №поставщика в первой таблице.

Если в оn update стоит null, то  в первой таблице №поставщика изменится с 1 на 10, а в связующей таблице вместо №поставщика будет записано null.

Примеры:

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

CREATE TABLE  Клиент

   (Фирма       VARCHAR(50) NOT NULL,

   Фамилия      VARCHAR(50) NOT NULL,

   Имя          VARCHAR(50) NOT NULL,

   Отчество     VARCHAR(50),

   ГородКлиента VARCHAR(50),

   Телефон      CHAR(10) NOT NULL)

Добавить в таблицу Клиент поле для номера расчетного счета.

ALTER TABLE Клиент ADD Рас_счет CHAR(20)

Добавление ограничения внешнего ключа, реализующего декларативную ссылочную целостность.

ALTER TABLE Сделка ADD CONSTRAINT fk_Товар

FOREIGN KEY (КодТовара) REFERENCES Товар 

ON UPDATE CASCADE ON DELETE CASCADE


6. Операторы манипулирования данными в SQL

Data Manipulation Language (DML) (язык управления [манипулирования] данными) - это семейство компьютерных языков, используемых в компьютерных программах или пользователями баз данных для получения, вставки, удаления или изменения данных в базах данных.

На текущий момент наиболее популярным языком DML является SQL, используемый для получения и манипулирования данными в РСУБД. Другие формы DML использованы в IMS/DL1, базах данных CODASYL (таких как IDMS), и других.

Языки DML изначально использовались только компьютерными программами, но с появлением SQL стали также использоваться и людьми.

Функции языков DML определяются первым словом в предложении (часто называемом запросом), которое почти всегда является глаголом. В случае с SQL эти глаголы - "select" ("выбрать"), "insert" ("вставить"), "update" ("обновить"), и "delete" ("удалить"). Это превращает природу языка в ряд обязательных утверждений (команд) к базе данных.

Языки DML могут существенно различаться у различных производителей СУБД. Существует стандарт SQL, установленный ANSI, но производители СУБД часто предлагают свои собственные "расширения" языка.

  1.  Добавление информации в таблицу.

Insert into имя_таблицы (список полей)

values (список выражений)

добавление одной записи,

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

Insert into имя_таблицы [(список добавляемых полей)]

или использовать подзапрос

select список_полей into   целевая_таблица from   список_таблиц where  условие

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

  1.  Оператор обновления.

Update имя_таблицы set    поле=значение [where условие]

(все что записано в квадратных скобках это не обязательно, может быть, а может и не быть).

  1.  Удаление записи из таблицы.

Delete from имя_таблицы [where условие]

Если where условие опущено, то удаляются все записи.

  1.  Оператор поиска данных в таблицах

Select {all | distinct} список_полей

from   список_таблиц  

[where условие]

[group by список_полей]

[having условие]

[order by поля[asc,desc]]

[union [all] подзапрос]

  1.  distinct – режим, исключающий повторяющиеся записи в ответе.
  2.  All – режим, при котором в ответ включаются все записи. По умолчанию принято all, его можно не указывать.
  3.  Если одновременно присутствует where и having, то сначала будет выполняться where.
  4.  Если присутствует where, having, group by, то сначала выполнится where, потом group by, а потом having.
  5.  Select список_полей - указывает имена полей, которые должны содержаться в ответе;
  6.  from список_таблиц – указывает имена таблиц, которые участвуют в запросе;
  7.  where условие – задает условие отбора записей в ответ;
  8.  group by список_полей – задает условие группировки записей, группировка – это операция разбиения на группы, каждая из которых содержит одинаковые значения в отмеченных столбцах;
  9.  having условие задает условие отбора групп, если нет group by, то это условие применяется ко всей таблице;
  10.  order by поля[asc,desc] – задает тип сортировки записей в ответе, asc – это сортировка по возрастанию, desc – по убыванию, по умолчанию ставится asc;
  11.  union [all] подзапрос позволяет объединить главный Select с результатом подзапроса, подзапросом называется вложенный оператор Select.

SELECT [[ALL] | DISTINCT]{ * | элемент_SELECT [,элемент_SELECT] ...}

FROM  {базовая_таблица | представление} [псевдоним]

 [,{базовая_таблица | представление} [псевдоним]] ...

[WHERE  фраза]

[GROUP BY фраза [HAVING фраза]];

Элемент_SELECT - это одна из следующих конструкций:

[таблица.]* | значение | SQL_функция | системная_переменная

где значение – это:

[таблица.]столбец | (выражение) | константа | переменная

Синтаксис выражений имеет вид

( {[ [+] | - ] {значение | функция_СУБД} [ + | - | * | ** ]}... )

а синтаксис SQL_функций – одна из следующих конструкций:

{SUM|AVG|MIN|MAX|COUNT} ( [[ALL]|DISTINCT][таблица.]столбец )

{SUM|AVG|MIN|MAX|COUNT} ( [ALL] выражение )

COUNT(*)

Фраза WHERE включает набор условий для отбора строк:

WHERE [NOT] WHERE_условие [[AND|OR][NOT] WHERE_условие]...

где WHERE_условие – одна из следующих конструкций:

значение { = | <> | < | <= | > | >= } { значение | ( подзапрос ) }

значение_1 [NOT] BETWEEN значение_2 AND значение_3

значение [NOT] IN { ( константа [,константа]... ) | ( подзапрос )

значение IS [NOT] NULL

[таблица.]столбец [NOT] LIKE 'строка_символов' [ESCAPE 'символ']

EXISTS ( подзапрос )

Кроме традиционных операторов сравнения (= | <> | < | <= | > | >=) в WHERE фразе используются условия BETWEEN (между), LIKE (похоже на), IN (принадлежит), IS NULL (не определено) и EXISTS (существует), которые могут предваряться оператором NOT (не). Критерий отбора строк формируется из одного или нескольких условий, соединенных логическими операторами:

AND - когда должны удовлетворяться оба разделяемых с помощью AND условия; OR - когда должно удовлетворяться одно из разделяемых с помощью OR условий; AND NOT - когда должно удовлетворяться первое условие и не должно второе; OR NOT - когда или должно удовлетворяться первое условие или не должно удовлетворяться второе, причем существует приоритет AND над OR (сначала выполняются все операции AND и только после этого операции OR). Для получения желаемого результата WHERE условия должны быть введены в правильном порядке, который можно организовать введением скобок.

Наконец, синтаксис фразы GROUP BY имеет вид

GROUP BY [таблица.]столбец [,[таблица.]столбец] ... [HAVING фраза]

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

С помощью фразы HAVING (синтаксис которой почти не отличается от синтаксиса фразы WHERE)

HAVING [NOT] HAVING_условие [[AND|OR][NOT] HAVING_условие]...

можно исключить из результата группы, не удовлетворяющие заданным условиям:

значение { = | <> | < | <= | > | >= } { значение | ( подзапрос )

| SQL_функция }

{значение_1 | SQL_функция_1} [NOT] BETWEEN

{значение_2 | SQL_функция_2} AND {значение_3 | SQL_функция_3}

{значение | SQL_функция} [NOT] IN { ( константа [,константа]... )

| ( подзапрос ) }

{значение | SQL_функция} IS [NOT] NULL

[таблица.]столбец [NOT] LIKE 'строка_символов' [ESCAPE 'символ']

EXISTS ( подзапрос )

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

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

Формат операции:

FROM имя_таблицы_1 {INNER | LEFT | RIGHT}

   JOIN имя_таблицы_2

ON условие_соединения

Операция тета-соединения в языке SQL называется INNER JOIN (внутреннее соединение) и используется, когда нужно включить все строки из обеих таблиц, удовлетворяющие условию объединения. 

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

Какая из таблиц будет ведущей, определяет вид соединения. LEFT - левое внешнее соединение, ведущей является таблица, расположенная слева от вида соединения; RIGHT - правое внешнее соединение, ведущая таблица расположена справа от вида соединения.

Пример:

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

SELECT Товар.Название, Month(Сделка.Дата)

   AS Месяц,  Sum(Товар.Цена*Сделка.Количество)  AS Стоимость

FROM Товар INNER JOIN Сделка   ON Товар.КодТовара=Сделка.КодТовара

WHERE Товар.Сорт="Первый"

GROUP BY Товар.Название, Month(Сделка.Дата)

Для товаров первого сорта установить цену в значение 140 и остаток – в значение 20 единиц.

UPDATE Товар SET Товар.Цена=140, Товар.Остаток=20

WHERE Товар.Сорт=" Первый "

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

SELECT Товар.*, Сделка.*

FROM Товар LEFT JOIN Сделка

ON Товар.КодТовара=Сделка.КодТовара;


7. Управление транзакциями

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

Операция считается транзакцией, если она удовлетворяет требованиям  ACID-теста (Atomicity, Consistency, Isolation, Durability атомарность, согласованность, изолированность, долговечность).

Атомарность - лозунг транзакции - "Все или ничего": при завершении транзакции оператором COMMIT результаты гарантированно фиксируются во внешней памяти (смысл слова commit - "зафиксировать" результаты транзакции); при завершении транзакции оператором ROLLBACK результаты гарантированно отсутствуют во внешней памяти (смысл слова rollback - ликвидировать результаты транзакции).

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

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

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

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

Транзакции и целостность баз данных

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

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

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

Уровни изоляции

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

  1.  Потерянные изменения. Транзакция Т1 читает данные. Транзакция Т2 читает те же данные. Транзакция T1 на основании прочитанного значения вычисляет новое значение данных, записывает его в базу данных и завершается. Транзакция T2 на основании прочитанного значения вычисляет новое значение данных, записывает его в базу данных и завершается. В результате значение, записанное транзакцией Т2, "затрет" значение, записанное транзакцией Т1.
  2.  Грязное чтение. Транзакция Т1 изменяет некоторые данные, но еще не завершается. Транзакция Т2 читает эти же данные (с изменениями, внесенными транзакцией Т1) и принимает на их основе какие-то решения. Транзакция Т1 выполняет откат. В результате решение, принятое транзакцией Т2 основано на неверных данных.
  3.  Неповторяющееся чтение. Транзакция Т1 в ходе своего выполнения несколько раз читает одни и те же данные. Транзакция Т2 в интервалах между чтениями транзакцией Т1 изменяет эти данные и фиксируется. В результате оказывается, что чтения одних и тех же данных в транзакции Т1 дает разные результаты.
  4.  Фантом. Транзакция Т1 в ходе своего выполнения несколько раз выбирает множество строк по одним и тем же критериям. Транзакция Т2 в интервалах между выборками транзакции Т1 добавляет или удаляет строки или изменяет столбцы некоторых строк, используемых в критерии выборки, и фиксируется. В результате оказывается, что одни и те же выборки в транзакции Т1 выбирают разные множество строк.

Определение уровней изоляции в стандарте:

Уровни изоляции SQL/92

АНОМАЛИИ

DB2

Oracle

Потерянные изменения

Грязное чтение

Неповторяющееся чтение

Фантом

READ UNCOMMITTED

нет

да

да

да

UNCOMMITTED READ

-

READ COMMITTED

нет

нет

да

да

CURSOR STABILITY

READ COMMITTED

REPEATABLE READ

нет

нет

нет

да

READ STABILITY

-

SERIALIZABLE

нет

нет

нет

нет

REPEATABLE READ

SERIALIZABLE

SQL-выражения для управления транзакциями

Для управления транзакциями имеется три выражения:

SET TRANSACTION - Начинает транзакцию и определяет ее поведение.

COMMIT - Сохраняет изменения, внесенные транзакцией, в базе данных и завершает транзакцию.

ROLLBACK - Отменяет изменения, внесенные транзакцией, и завершает транзакцию.

1. Запуск транзакции

В общем виде, синтаксис команды SQL для запуска транзакции:

SET TRANSACTION [Access mode] [Lock Resolution]

[Isolation Level] [Table Reservation]

Значения, принимаемые по-умолчанию:
выражение
SET TRANSACTION равносильно выражению

SET TRANSACTION READ WRITE WAIT ISOLATION LEVEL SNAPSHOT

Access Mode - определяет тип доступа к данным. Может принимать два значения: READ ONLY - указывает, что транзакция может только читать данные и не может модифицировать их. READ WRITE - указывает, что транзакция может читать и модифицировать данные. Это значение принимается по умолчанию.

Пример:

SET TRANSACTION READ WRITE

Isolation Level - определяет порядок взаимодействия данной транзакции с другими в данной базе. Может принимать значения:

  1.  SNAPSHOT - значение по умолчанию. Внутри транзакции будут доступны данные в том состоянии, в котором они находились на момент начала транзакции. Если по ходу дела в базе данных появились изменения, внесенные другими завершенными транзакциями, то данная транзакция их не увидит. При попытке модифицировать такие записи возникнет сообщение о конфликте.
  2.  SNAPSHOT TABLE STABILITY - предоставляет транзакции исключительный доступ к таблицам, которые она использует. Другие транзакции смогут только читать данные из них.
  3.  READ COMMITTED - позволяет транзакции видеть текущее состояние базы.

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

  1.  Транзакция пытается модифицировать запись, которая была изменена или удалена уже после ее старта. Транзакция типа READ COMMITTED может вносить изменения в записи, модифицированные другими транзакциями после их завершения.
  2.  Транзакция пытается модифицировать таблицу, которая заблокирована другой транзакцией типа SNAPSHOT TABLE STABILITY.

Lock Resolution - определяет ход событий при обнаружении конфликта блокировки. Может принимать два значения:

  1.  WAIT - значение по умолчанию. Ожидает разблокировки требуемой записи. После этого пытается продолжить работу.
  2.  NO WAIT - немедленно возвращает ошибку блокировки записи.

Table Reservation - позволяет транзакции получить гарантированный доступ необходимого уровня к указанным таблицам. Существует четыре уровня доступа:

  1.  PROTECTED READ - запрещает обновление таблицы другими транзакциями, но позволяет им выбирать данные из таблицы.
  2.  PROTECTED WRITE - запрещает обновление таблицы другими транзакциями, читать данные из таблицы могут только транзакции типа SNAPSHOT или READ COMMITTED.
  3.  SHARED READ - самый либеральный уровень. Читать могут все, модифицировать - транзакции READ WRITE.
  4.  SHARED WRITE - транзакции SNAPSHOT или READ COMMITTED READ WRITE могут модифицировать таблицу, остальные - только выбирать данные.

2. Завершение транзакции

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

  1.  COMMIT - сохраняет внесенные транзакцией изменения в базу данных. Это означает, что транзакция завершена успешно.
  2.  ROLLBACK - откат транзакции. Транзакция завершается и никаких изменений в базу данных не вносится. Данная операция выполняется при возникновении ошибки при выполнении операции (например, при невозможности обновить запись).


8. Технологии «клиент-сервер»

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

Клиент – это программа или компьютер, обращающийся к услугам сервера

Существуют разные технологии клиент-сервер.

Любая программа может быть представлена из нескольких частей:

  1.  Ввод/вывод (интерфейсная часть);
  2.  Вычисление на основе каких-либо бизнес правил;
  3.  Обращение к данным;
  4.  Управляющая часть, создает единый алгоритм.

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

1 вариант - файловый сервер.

Введем обозначения: К – клиент, С – сервер.

К выполняет 1,2,4 части, а на С содержится информация, необходимая для запроса, т.е. С выполняет 3 часть.

                                                      запрос

                 К                                      С   

                                                   ответ-файл   

В данной технологии основная нагрузка падает на клиента.

К

1,2

С

БД

    запрос

 курсор

 2 вариант – удаленный доступ.

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

Запросы пишутся на динамическом SQL. А в ответ получаем ту порцию информации, которую запросили, эта порция информации называется курсором.

Динамический SQL -  это  операторы SQL, которые передаются и выполняются на сервере.

Имеют место следующие операторы:

Prepare  имя_оператора from строка, Select, Insert, Delete, Update

Execute имя_оператора – позволяет выполнить запомненный на сервере оператор;

Drop имя_оператора – позволяет удалит оператор;

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

Exec sql “sql оператор”.

Описание курсора на SQL:

Declare  имя_курсора [scroll] cursor for  подзапрос [for update].

Курсор может быть обычным, то есть просматриваемым в одном направлении, от начала к концу, если стоит scroll, то просматривать курсор можно в любом направлении. Если стоит for update, то это значит, что курсор изменяемый, все изменения будут запоминаться на сервере.

Операции с курсором:

Open  имя_курсора – позволяет получить курсор;

Fetch  имя_курсора – позволяет перейти к следующей записи курсора, если перед именем курсора поставить Last, то перейдем к последней записи, First – к первой записи, Current к текущей;

Close имя_курсора – закрытие курсора, но он остается определенным;

Free имя_курсора – удаление курсора.

3 вариант – сервер Базы Данных.

К

1

С

2, БД

Запрос на SQL

Обработанные          данные

Бизнес-правила хранятся на сервере в виде  хранимых процедур. Хранимые процедуры – это программы, написанные на некотором языке хранимых процедур с SQL вставками. Их можно написать заранее и поместить в библиотеку.

Рассмотрим операторы для программирования хранимых процедур.

  1.  Create имя_процедуры (параметры)

          [return список выходных данных]

          тело

    End procedure  - создание процедуры;

  1.  Execute procedure имя (аргументы)[into список переменых] -– выполнение процедуры, созданной заранее;
  2.  drop procedure имя – удаление хранимой процедуры;
  3.  define список переменных – позволяет объявить переменные, которые являются локальными в хранимой процедуре;
  4.  call  имя (аргументы) into список переменных – позволяет вызвать другую процедуру;
  5.  переменная:=выражение – присвоение;
  6.  if условие then оператор [else оператор] end if – условный оператор;
  7.  операторы цикла

for  переменная:=целое1

to целое2 step целое

end for

while  условие                                    for each имя_курсора

тело                                                      операторы

end while                                             end for each

Среди операторов ТЕЛА используются следующие:

Exit - позволяет выйти из цикла до его завершения;

Continue – позволяет начать выполнение цикла, не заканчивая предыдущий шаг;

System – позволяет выполнить команды ОС;

Return – позволяет сформировать результаты и вернуть их из процедуры;

  Begin

  .             – блок, часть пограммы, в которой могут быть объявлены

  .                локальные переменные.

  end

4 вариант – сервер приложений.

Клиент,

1

Сервер приложений, 2

Сервер данных,

БД

Протокол API

SQL

результаты

данные

С помощью протокола API передается информация о том какие программы и в какой последовательности нужно выполнять.

В технологии клиент-сервер есть специальные активные программы, которые называют триггерами.

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

  1.  Create trigger имя событие_действие  - создание триггера;
  2.  Drop trigger  - удаление.

Запись события:

  1.  Insеrt on  имя_таблицы – наступает тогда, когда в таблицу заносится информация;
  2.  Delete on  таблица – наступает при удалении из таблицы;
  3.  Update of список_полей on имя_таблицы  - возникает при изменении заданных полей в указанной таблице.

Действия бывают трех видов:

  1.  Before (оператор) – перед добавлением, удалением, изменением;
  2.  Foreach row (оператор) – для каждой строки таблицы;
  3.  After (оператор) после добавления, удаления, изменения.

В триггерах есть возможность сослаться на одно и тоже поле до изменения и после:

  1.  Referencing old as имя – запомнить до изменения;
  2.  Referencing new as имя – запомнить после изменения;

When (условие)(оператор) – задает дополнительные условия для работы с триггерами.

Пример.

Изменить статус поставщиков только в том случае, если новый статус не меньше старого и не больше 100%.

Нужно создать триггер, который будет обновлять статус:

 Create trigger Sstat

Update of  статус on Поставщики

Referencing old as c1

Referencing new as c2

Foreach row

When ( с1.статус >=с2.статус)

 Execute procedure error  (с1.статус,с2.статус)

When   (с2.статус>100%)

Execute procedure error1 (с1.статус,с2.статус)

Модель сервера базы данных

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

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

      Модель сервера приложений.
      Использование этой модели позволяет разгрузить рабочие станции, то есть перейти к "тонким" клиентам. Конечно, сервер приложений можно организовать и с помощью хранимых процедур. Но для реализации хранимых процедур используют языки высокого уровня (например, в Oracle - язык PL/SQL ), поэтому программы получаются ресурсоёмкими. Причём возможности этих языков ограничены: с их помощью нельзя организовать обработку данных на уровне битов. Хранимые процедуры также не поддерживают распределённые приложения, т. е. они не обеспечивают автоматический запуск требуемой программы на другом сервере.


9. Оператор Select

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

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

Оператор SELECT имеет следующий формат:

SELECT [ALL | DISTINCT ] {*|[имя_столбца

 [AS  новое_имя]]} [,...n]

 FROM  имя_таблицы [[AS] псевдоним] [,...n]

 [WHERE  <условие_поиска>]

 [GROUP BY  имя_столбца [,...n]]

 [HAVING <критерии выбора групп>]

 [ORDER BY имя_столбца [,...n]]

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

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

Предложение FROM

Предложение FROM задает имена таблиц и просмотров, которые содержат поля, перечисленные в операторе SELECT. Необязательный параметр псевдонима – это сокращение, устанавливаемое для имени таблицы.

Обработка элементов оператора SELECT выполняется в следующей последовательности:

  1.  FROM – определяются имена используемых таблиц;
  2.  WHERE – выполняется фильтрация строк объекта в соответствии с заданными условиями;
  3.  GROUP BY – образуются группы строк , имеющих одно и то же значение в указанном столбце;
  4.  HAVING – фильтруются группы строк объекта в соответствии с указанным условием;
  5.  SELECT – устанавливается, какие столбцы должны присутствовать в выходных данных;
  6.  ORDER BY – определяется упорядоченность результатов выполнения операторов.

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

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

Предложение WHERE

С помощью WHERE-параметра пользователь определяет, какие блоки данных из приведенных в списке FROM таблиц появятся в результате запроса. За ключевым словомWHERE следует перечень условий поиска, определяющих те строки, которые должны быть выбраны при выполнении запроса. Существует пять основных типов условий поиска (или предикатов):

  1.  Сравнение: сравниваются результаты вычисления одного выражения с результатами вычисления другого.
  2.  Диапазон: проверяется, попадает ли результат вычисления выражения в заданный диапазон значений.
  3.  Принадлежность множеству: проверяется, принадлежит ли результат вычислений выражения заданному множеству значений.
  4.  Соответствие шаблону: проверяется, отвечает ли некоторое строковое значение заданному шаблону.
  5.  Значение NULL: проверяется, содержит ли данный столбец определитель NULL (неизвестное значение).

Сравнение

В языке SQL можно использовать следующие операторы сравнения: = – равенство; < – меньше; > – больше; <= – меньше или равно; >= – больше или равно; <> – не равно.

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

  1.  Выражение вычисляется слева направо.
  2.  Первыми вычисляются подвыражения в скобках.
  3.  Операторы NOT выполняются до выполнения операторов AND и OR.
  4.  Операторы AND выполняются до выполнения операторов OR.

Оператор BETWEEN используется для поиска значения внутри некоторого интервала, определяемого своими минимальным и максимальным значениями. При этом указанные значения включаются в условие поиска.

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

Предложение ORDER BY

В общем случае строки в результирующей таблице SQL-запроса никак не упорядочены. Однако их можно требуемым образом отсортировать, для чего в оператор SELECT помещается фраза ORDER BY, которая сортирует данные выходного набора в заданной последовательности. Сортировка может выполняться по нескольким полям, в этом случае они перечисляются за ключевым словом ORDER BY через запятую. Способ сортировки задается ключевым словом, указываемым в рамках параметра ORDER BY следом за названием поля, по которому выполняется сортировка. По умолчанию реализуется сортировка по возрастанию. Явно она задается ключевым словом ASC. Для выполнения сортировки в обратной последовательности необходимо после имени поля, по которому она выполняется, указать ключевое слово DESC.

Предложение GROUP BY

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

Предложение HAVING

При помощи HAVING отражаются все предварительно сгруппированные посредством GROUP BY блоки данных, удовлетворяющие заданным в HAVING условиям. Это дополнительная возможность "профильтровать" выходной набор.

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

Формат операции:

FROM имя_таблицы_1 {INNER | LEFT | RIGHT}

   JOIN имя_таблицы_2

ON условие_соединения

Операция тета-соединения в языке SQL называется INNER JOIN (внутреннее соединение) и используется, когда нужно включить все строки из обеих таблиц, удовлетворяющие условию объединения. 

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

Какая из таблиц будет ведущей, определяет вид соединения. LEFT - левое внешнее соединение, ведущей является таблица, расположенная слева от вида соединения; RIGHT - правое внешнее соединение, ведущая таблица расположена справа от вида соединения.

Пример:

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

SELECT Товар.Название, Month(Сделка.Дата)

   AS Месяц,

   Sum(Товар.Цена*Сделка.Количество)

   AS Стоимость

FROM Товар INNER JOIN Сделка

   ON Товар.КодТовара=Сделка.КодТовара

WHERE Товар.Сорт="Первый"

GROUP BY Товар.Название, Month(Сделка.Дата)

Для товаров первого сорта установить цену в значение 140 и остаток – в значение 20 единиц.

UPDATE Товар SET Товар.Цена=140, Товар.Остаток=20

WHERE Товар.Сорт=" Первый "

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

SELECT Товар.*, Сделка.*

FROM Товар LEFT JOIN Сделка

ON Товар.КодТовара=Сделка.КодТовара;


10. Индексация. Достоинства и недостатки. Примеры

Самая распространённая задача, которую решают приложения работающие с базами данных - это поиск необходимых записей по заданному критерию.

Внутренняя модель данных рассматривает задачу хранения информации на внешних носителях с целью:

  1.  уменьшения внешней памяти.
  2.  уменьшения времени доступа к требуемой информации.

Эти  цели достигаются при помощи использования факторизации и индексации.

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

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

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

Указатель же (ссылка) используется для адресации объектов в памяти и может быть:-  абсолютным адресом

- относительным адресом (состоящим из базы и смещения)

- каким-либо специальным символом или флажком, помечающим место  хранения объекта.

Индекс позволяет производить дихотомический или двоичный поиск.

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

Индекс можно хранить в памяти, так как он занимает мало места.

Виды индексов:

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

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

В Уникальном индексе только один указатель может быть связан с соответствующим ему ключом. Уникальные индексы - это индексы строящиеся по первичному ключу.

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

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

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

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

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

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

Производительность

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

B-деревья

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

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

Хэширование

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

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

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

В целом методы B-деревьев и хэширования все более сближаются.

Пример.

Файл а1:

адреса

А1

А2

А3

A0

d

1

F

A1

a

2

M

A2

C

3

F

A3

B

4

M

A4

Z

3

M

A5

I

2

F

A6

J

2

M

A7

k

5

M

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

Запишем файл упорядоченный по полю А1:

B

A1

адрес

B1

A

A1

B2

B

A3

B3

C

A2

B4

D

A0

B5

I

A5

B6

J

A6

B7

K

A7

B8

Z

A4

Создадим индекс второго уровня, для этого разбиваем индекс на группы по три записи:

A1

адрес

C

B1

J

B4

z

B7

В первом столбце записан старший ключ, во втором столбце младший ключ.

Рассмотрим, например поиск записи с ключом I.

Смотрим в последнюю таблицу и ищем где ключ больший I, это J, его адрес B4, теперь обращаемся ко второй таблице, находим тройку записей, у которой младший индекс B4, это тройка D,I,J, находим в ней I, смотрим какой она имеет адрес – A5, обращаемся в первую таблицу и находим запись с адресом А5.

Индекс с инвертированными списками. Инвертированный список хранит список ключей для каждого значения где это значение встречается.

А3

Список адресов

F

A0, A2,A5

M

A1,A3,A4,A6,A7


11. В-дерево. Добавление и удаление элементов

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

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

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

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

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

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

Левое поддерево поизвольной вершины X содержит ключи, не превосходящие key[X] ( значение вершины X ), правое - не меньшие key[X]. Разные бинарные деревья поиска могут представлять одно и то же множество. Время выполнения ( в худшем случае ) большинства операций пропорционально высоте дерева.

При представлении с использованием указателей для каждой вершины дерева нужно хранить помимо значения ключа key и дополнительных данных, также и указатели left, right, parent (на левое и правое поддерево, а также родителя). Если ребёнка ( или родителя - для корня ) нет, соответствующая переменная должна равняться NULL. Ключи в двоичном дереве поиска хранятся с соблюдением свойства упорядоченности: Пусть X - произвольная вершина двоичного дерева поиска. Если вершина Y находится в левом поддереве вершины X, то key[X]>=key[Y]. Если вершина Y находится в правом поддереве вершины X, то key[X]<=key[Y]

Типовые функции при работе с бинарным деревом.

Функция печати выводит на экран все ключи, входящие в дерево. x - вершина бинарного дерева, left[x] - левое поддерево, right[x] - правое поддерево, key[x] - ключ, p[x] - родитель вершины.

Печать(x)

Начало

1  если x не равен NULL

2  тогда Печать(left[x])

3  напечатать key[x]

4  Печать(right[x])

Конец

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

Поиск(x,k)

Начало

1  Пока x не равен NULL и k не равно key[x]

2    Начало

3        если k меньше key[x]

4            тогда x равно left[x]

5        иначе x равно right[x]         

6    Конец

7  Вернуть x   

Конец

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

Минимум(x)

Начало

1  Пока left[x] не равен NULL

2     Начало

3        x=left[x]

4     Конец

5  Вернуть x   

Конец

Максимум(x)

Начало

1  Пока right[x] не равен NULL

2     Начало

3        x=right[x]

4     Конец

5  Вернуть x   

Конец

Данный принцип демонстрируется на рисунке.

При поиске ключа 13 мы идём от корня по пути 15->6->7->13. Чтобы найти минимальный ключ 2, мы всё время идём налево. Чтобы найти максимальный ключ 20 направо.

Следующий и предыдущий элементы. Процедура возвращает указатель на следующий за x элемент или NULL в случае, если элемент x - последний в дереве.

ПолучитьСледующийЭлемент(x)

Начало

1  если right[x] не равен NULL

2     тогда вернуть Минимум(right[x])   

3  y равно p[x]   

4  пока y не равно NULL и x равно right[x]   

5     Начало

6        x равно y

7        y равно p[y]

8     Вернуть y

Конец

ПолучитьПредыдущийЭлемент(x)

Начало

1  если left[x] не равен NULL

2     тогда вернуть Максимум(left[x])   

3  y равно p[x]   

4  пока y не равно NULL и x равно left[x]   

5     Начало

6        x равно y

7        y равно p[y]

8     Вернуть y

Конец

Добавление.

Процедура добавляет заданный элемент в подходящее место дерево (такое место единственное), сохраняя свойство упорядоченности. Параметром процедуры является указатель z на новую вершину, в которую помещены значения key[z] ( добавляемое значение ключа), left[z]=NULL и right[z]=NULL. В ходе работы процедура меняет дерево T и возможно некоторые поля вершины z, после чего новая вершина c данным значением ключа оказывается вставленной в подходящее место (см. рисунок).

Вставка(T,z)

Начало

1  y равно NULL

2  x равно root[T]

3  пока x не равно NULL

4    Начало

5      y равно x

6      если  key[z] меньше key[x]

7         тогда x равно left[x]

8      иначе x равно right[x]

9    Конец

10  p[z] равно y

11  если y равно NULL

12     тогда root[T]  равно z

13  иначе если key[z] меньше key[y]

14     тогда left[y] равно z

15  иначе right[y] равно z  

16

Конец

Удаление. Параметром процедуры удаления явяляется указатель на удаляемую вершину. При удалении возможны случаи, указанные на рисунке ниже. Если у z нет детей, для удаления z достаточно поместить NULL в соответствующее поле его родителя ( вместо z ). Если у z есть один ребёнок, можно вырезать z, соединив его родителя напрямую с ребенком. Если же детей двое, требуются некоторые приготовления: мы находим следующий ( в смысле порядка на ключах) за z элемент y; у него нет левого ребёнка. Теперь можно скопировать ключ и дополнительные данные из вершины y в вершину z, а саму вершину y удалить описанным образом.

Удаление(T,z)

Начало

1   если left[z] равно NULL или right[z]=NULL

2      тогда y равно z

3   иначе y равно ПолучитьСледующийЭлемент(z)

4  если left[y] не равно NULL

5      тогда x равно left[y]

6  иначе x равно right[y]

7  если x не равно NULL    

8      тогда p[x] равно p[y]

9

10  если p[y] равно NULL

11     тогда root[T] равно x

12  иначе если y равно left[p[y]]

13     тогда left[p[y]] равно x

14  иначе right[p[y]] равно x  

15  если y не равен z

16     тогда key[z] равно key[y]

17     // Копируем дополнительные данные связанные с y

18  Удалить y

Конец

Пример.

Пусть у нас есть дерево третьего порядка,  с ключами 12, 8, 4, 9, 6, 13, 14, 16,100, 10.

Приходит ключ 12, его заносим в корень

12

8    12

Приходит 8, 8 меньше 12

Приходит 4, места в корне нет, разбиваем на 2

8

4

12

Приходит 9, она больше 8, но меньше 12, 12 сдвигаем, перед ней записываем 9, приходит 6 она меньше 8, но больше 4, записываем ее после 4:

8

4  6

9   12

После того как придет 13, 14, 16, 100, 10  вид дерева будет следующим:

12

8

14

9    10

4   6

13

16   100


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

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

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


Рис. 9.1.  Классификация файлов, используемых в системах баз данных

С точки зрения пользователя, файлом называется поименованная линейная последовательность записей, расположенных на внешних носителях. На рис. 9.2 представлена такая условная последовательность записей.

Так как файл — это линейная последовательность записей, то всегда в файле можно определить текущую запись, предшествующую ей и следующую за ней. Всегда существует понятие первой и последней записи файла

Файлы с постоянной длиной записи, расположенные на устройствах прямого доступа (УПД), являются файлами прямого доступа.

В этих файлах физический адрес расположения нужной записи может быть вычислен по номеру записи (NZ).


Рис. 9.2.  Файл как линейная последовательность записей

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

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

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

На данном ниже рисунке показана организация хэширования файла с B-участками.

  1.  Интерпретируем значения ключа как последовательность битов, формированную путем конкатенации значений всех полей ключа. Эта последовательность имеет фиксированную длину, поскольку каждое поле имеет фиксированную длину.
  2.  Делим последовательность битов на группы, состоящие из фиксированного числа битов, например 16-ти. Последнюю группу при необходимости дополняем нулями.
  3.  Складываем группу битов как целые числа.
  4.  Делим сумму на число участков и используем остаток как номер участка.

На рис. Показан справочник участков, состоящий из B указателей: по одному на каждый участок. Каждый указатель является адресом первого блока данного участка. Участок, содержащий только один блок (участок 1) имеет в этом блоке заголовок с null указателем. Участок из более чем одного блока содержит в заголовке первого блока указатель второго и т.д. Заголовок последнего – null.В каждом блоке предусматривается место для размещения фиксированного числа записей. Если значение требует r байт, то следующая запись начинается со смещения r от начала блока.

Поиск.

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

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

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

Модификация.

Пусть необходимо модифицировать одно или более полей записи со значением ключа V. Интерпретируем эту модификацию как удаление и включение.

Включение.

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

Удаление.

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

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

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

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

Методы разрешения коллизий

  1.  Метод последовательного перебора. Значение хэш-функции – отправная точка для дополнительного просмотра и поиска. Запись сохраняется в первом свободном месте.
  2.  Стратегия разрешения коллизий с областью переполнения. Область хранения разбивается на две части: основную и область переполнения. Значение хэш-функции – адрес записи, запись заносится в основную область. Если при вставке нового значения возникает коллизия, то новая запись заносится в область переполнения на первое свободное место, а  записи-синониме в основной области делается ссылка на адрес вновь размешенной записи в области переполнения. Следующая новая запись-синоним будет располагаться на втором месте списка. Т. о. для размещения новой записи требуется не более двух обращений к диску. Хорошим результатом может считаться наличие не более 10 синонимов.
  3.  Организация стратегии свободного размещения. Одна общая область замещения. Записи-синонимы организуются в двухсвязный список.
  4.  Если при вставке новой записи ее адрес занят  записью, которая не является заголовком списка, то она перемещается на свободное место с коррекцией указателей. А новая запись встает на ее место.
  5.  Если адрес занят заголовком списка, то новая запись располагается  на свободном месте, и для нее устанавливаются соответствующие указатели.
  6.  Если адрес свободен, то новая запись размещается в заданном месте и становится заголовком в списке синонимов.


13. Архитектуры БД

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

Традиционным методом организации информационных систем является двухзвенная архитектура "клиент-сервер" (рисунок 1.1). В этом случае вся прикладная часть информационной системы выполняется на рабочих станциях системы (т.е. дублируется), а на стороне сервера(ов) осуществляется только доступ к базе данных. Если логика прикладной части системы достаточно сложна, то такой подход порождает проблему "толстого" клиента. Каждая рабочая станция должна обладать достаточным набором ресурсов, чтобы быть в состоянии произвести прикладную обработку данных, поступающих от пользователя и/или из базы данных. Для того, чтобы клиенты могли быть "тощими", а зачастую и для повышения общей эффективности системы, все чаще применяются трехзвенные архитектуры "клиент-сервер" (рисунок 1.2). В этой архитектуре, кроме клиентской части системы и сервера(ов) базы данных, вводится промежуточный сервер приложений. На стороне клиента выполняются только интерфейсные действия, а вся логика обработки информации поддерживается в сервере приложений. В следующих частях курса мы рассмотрим возможные технологии организации трехзвенных архитектур

.

Рис. 1.1. Традиционная двухзвенная архитектура "клиент-сервер"

Рис. 1.2. Трехзвенная архитектура "клиент-сервер" с выделенным сервером приложений

Заметим, что некоторые черты трехзвенности могут присутствовать и в двухзвенной архитектуре. Если, например, используемый сервер баз данных поддерживает развитый механизм хранимых процедур (например, такой, как в Oracle V.7), то можно перебросить некоторую часть логики приложения на сторону баз данных. Заметим, что механизм хранимых процедур недостаточно полно специфицирован в стандарте языка SQL. Как только вы решаетесь использовать действительно развитые средства, то немедленно привязываете свою информационную систему к конкретному производителю серверов баз данных. Развязаться будет очень трудно.

Структурная схема терминов

1.1.2. Архитектуры БД

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

  1.  Локальная

Локальная (персональная) архитектура СУБД означает, что БД и СУБД располагаются на одном и том же локальном компьютере.

  1.  Архитектура "файл-сервер"

Архитектура "файл-сервер" также является локальной, т.к. предназначена для локальной сети, включает приложение и СУБД, расположенные на компьютере пользователя, и файл БД, находящийся на локальном сервере.

  1.  Архитектура удаленных БД ("клиент-сервер")

Архитектура "клиент-сервер" предназначена для работы с удаленными БД, состоит из приложения клиента, расположенного на компьютере пользователя, а также удаленной БД и СУБД, располагающихся на удаленном компьютере в глобальной сети (сервере).

Архитектура "клиент-сервер" может быть использована и в пределах локальной сети.

Удаленные БД называют также многопользовательскими.

СУБД в архитектурах "клиент-сервер" и "файл-сервер" позволяют работать с БД одновременно нескольким пользователям.

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

1.1.3. Достоинства и недостатки различных архитектур приложений БД

Достоинство архитектуры "файл-сервер" состоит в возможности одновременной многопользовательской обработки одной БД.

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

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

Приложение "клиент-сервер" формирует запрос к серверу на языке SQL. Удаленный сервер принимает запрос и переадресует его SQL-серверу БД (спец. программа, управляющая БД с помощью команд SQL). SQL-сервер выполняет запрос и возвращает результат.

Достоинства архитектуры "клиент-сервер":

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

Многозвенная архитектура "клиент-сервер"

Многозвенная архитектура "клиент-сервер" предполагает разбиение приложения-клиента на два звена: "тонкий" клиент, располагающийся на компьютере пользователя, и сервер приложений, находящийся на удаленном сервере, УБД и СУБД по-прежнему располагаются на удаленном компьютере.

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

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


14. Управление правами доступа в SQL

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

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

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

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

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

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

В стандарте SQL определены два оператора: GRANT и REVOKE соответственно предоставления и отмены привилегий.

Оператор предоставления привилегий имеет следующий формат:

GRANT {<список действий> | ALL PRIVILEGES }

 ON <имя_объекта>

 TO {<имя_пользователя> | PUBLIC }

 [WITH GRANT OPTION ]

Здесь список действий определяет набор действий из общедопустимого перечня действий над объектом данного типа.

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

<имя_объекта> — задает имя конкретного объекта: таблицы, представления, хранимой процедуры, триггера.

<имя_пользователя> или PUBLIC определяет, кому предоставляются данные привилегии.

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

Рассмотрим пример, пусть у нас существуют три пользователя с абсолютно уникальными именами user1, user2 и user3. Все они являются пользователями одной БД.

User1 создал объект Tab1, он является владельцем этого объекта и может передать права на работу с эти объектом другим пользователям. Допустим, что пользователь user2 является оператором, который должен вводить данные в Tab1 (например, таблицу новых заказов), а пользователь user 3 является большим начальником (например, менеджером отдела), который должен регулярно просматривать введенные данные.

Для объекта типа таблица полным допустимым перечнем действий является набор из четырех операций: SELECT, INSERT, DELETE, UPDATE. При этом операция обновление может быть ограничена несколькими столбцами.

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

GRANT {[SELECT][,INSERT][,DELETE][,UPDATE (<список столбцов>)]}

 ON <имя_таблицы>

 TO {<имя_пользователя> | PUBLIC } [WITH GRANT OPTION ]

Тогда резонно будет выполнить следующие назначения:

GRANT INSERT ON Tab1 TO user2

GRANT SELECT ON Tab1 TO user3

Эти назначения означают, что пользователь user2 имеет право только вводить новые строки в отношение Tab1, а пользователь user3 имеет право просматривать все строки в таблице Tab1.

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

GRANT SELECT, UPDATE (COST)   ON Tab1    TO user3

Если наш пользователь user1 предполагает, что пользователь user4 может его замещать в случае его отсутствия, то он может предоставить этому пользователю все права по работе с созданной таблицейTab1.

GRANT ALL PRIVILEGES ON Tab1 TO user4  WITH GRANT OPTION

В этом случае пользователь user4 может сам назначать привилегии по работе с таблицей Tab1 в отсутствие владельца объекта пользователя user1. Поэтому в случае появления нового оператора пользователя user5 он может назначить ему права на ввод новых строк в таблицу командой

GRANT INSERT ON Tab1 TO user5

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

GRANT SELECT, UPDATE, DELETE   ON Tab1    TO user4

WITH GRANT OPTION,

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

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

Так как представления могут соответствовать итоговым запросам, то для этих представлений недопустимы операции изменения, и, следовательно, для таких представлений набор допустимых действий ограничивается операцией SELECT. Если же представления соответствуют выборке из базовой таблицы, то для такого представления допустимыми будут все 4 операции: SELECT, INSERT, UPDATE и DELETE.

Для отмены ранее назначенных привилегий в стандарте SQL определен оператор REVOKE. Оператор отмены привилегий имеет следующий синтаксис:

REVOKE {<список операций> | ALL PRIVILEGES}

  ON <имя_объекта>

  FROM {<список пользователей> | PUBLIC }

       {CASCADE | RESTRICT }

Параметры CASCADE или RESTRICT определяют, каким образом должна производиться отмена привилегий. Параметр CASCADE отменяет привилегии не только пользователя, который непосредственно упоминался в операторе GRANT при предоставлении ему привилегий, но и всем пользователям, которым этот пользователь присвоил привилегии, воспользовавшись параметром WITH GRANT OPTION.

Например, при использовании операции:

REVOKE ALL PRIVILEGES

  ON Tab1

  TO user4 CASCADE

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

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

REVOKE ALL PRIVILEGES

  ON Tab1 TO user4 RESTRICT

не будет выполнена, потому что пользователь user4 передал часть cвоих полномочий пользователю user5.

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

Поэтому корректным будет следующее использование оператора REVOKE:

REVOKE INSERT    ON Tab1    TO user2,user4 CASCADE

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

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

Если вы хотите изменить это условие, то после создания хранимой процедуры необходимо записать оператор REVOKE.

REVOKE EXECUTE   ON COUNT_EX      TO PUBLIC CASCADE

И теперь мы можем назначить новые права пользователю user4.

GRANT EXECUTE

  ON COUNT_EX

  TO user4

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

GRANT CREATE TABLE,        ALTER TABLE,      DROP TABLE  

  ON DB_LIB 

  TO user1

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


15. Модель Чена

Модель Сущность-связь. Прежде, чем приступать к созданию системы автоматизированной обработки информации, разработчик должен сформировать понятия о предметах, фактах и событиях, которыми будет оперировать данная система. Для того, чтобы привести эти понятия к той или иной модели данных, необходимо заменить их информационными представлениями. Одним из наиболее удобных инструментов унифицированного представления данных, независимого от реализующего его программного обеспечения, является модель «сущность-связь» (entity - relationship model, ER - model). Она основывается на некой важной семантической информации о реальном мире и предназначена для логического представления данных и не определяет операций над данныим. Она определяет значения данных в контексте их взаимосвязи с другими данными. Важным для нас является тот факт, что из модели "сущность-связь" могут быть порождены все существующие модели данных (иерархическая, сетевая, реляционная, объектная), поэтому она является наиболее общей. Модель "сущность-связь" была предложена в 1976 г. Питером Пин-Шэн Ченом

Модель сущность-связь – используется для формального представления из предметной области.

Основные понятия:

Элементы модели. Сущность (entity) - это объект, который может быть идентифицирован неким способом, отличающим его от других объектов. Примеры: конкретный человек, предприятие, событие и т.д. Набор сущностей (entity set) - множество сущностей одного типа (обладающих одинаковыми свойствами). Примеры: все люди, предприятия, праздники и т.д. Наборы сущностей не обязательно должны быть непересекающимися. Например, сущность, принадлежащая к набору МУЖЧИНЫ, также принадлежит набору ЛЮДИ. Сущность фактически представляет из себя множество атрибутов, которые описывают свойства всех членов данного набора сущностей.

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

Для каждой модели Чена  выбирают  столько  атрибутов  объекта, чтобы отделить один экземпляр объекта  от  другого.  Множество таких атрибутов (отделяющих один экземпляр объекта  от другого называю ключом.

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

Первичных  ключей  может  быть несколько.  В таком случае их называют возможными ключами.

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

Выбранный ключ - это один ключ выбранный из множества возможных ключей.

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

   Связь 1:1 (один к одному)

Это  такой тип связи между объектами A и B, когда каждому экземпляру объекта  A  соответствует  один  и только один экземпляр объекта B и наоборот.

   Связь 1:M (один ко многим)

Это тип связи между объектами  A и B,  когда  одному  экземпляру объекта A может соответствовать 0,1 или  несколько экземпляров объекта B, однако каждому экземпляру объекта  B  соответствует только один экземпляр объекта A.

   Возможно также существование связи M:1 и M:N.

Различают также простые и многозначные связи:

При простой однонаправленной связи от объекта A к объекту B одному  и тому же экземпляру объекта A соответствует один и тот же экземпляр B. При этом обратная связь не  определена.  Идентификация экземпляров объекта B, экземплярами объекта A уникальна (однозначна).

При многозначной  однонаправленной  связи  от  объекта  A к объекту B одному и  тому  же экземпляру объекта A соответствует 0 или несколько экземпляров объекта B. При этом обратная связь не определена.

В диаграмме Чена есть 2 варианта:

  1.  ER диаграммы-экземпляров
  2.  ER диаграммы-типов.

Тип объекта – это множество значений, которые могут принимать объекты, и множество операций, которые можно проводить с ними.

Работаем не с каждым объектом отдельно, а объединяем их в типы.

Так представлены диаграммы – типов:

сущности      

 

 атрибуты                    -    первичный подчеркивают

отношения    

 

Пример.  Поставщики поставляют детали, нас интересует адрес и сколько деталей.

В предметной области две сущности

 

                                        n            поставка           n   

           Поставщик                          постав-                           деталь   

                                                          ляет

                                                      код пост     код дет.

                    ФИО           статус        внешний ключ          код        наимено

                                       степень                                    детали       вание

                                       доверия %         

       код пост          адрес                                                         адрес                  вес        

повторяющиеся значения

и пустые не допускаются

Связь имеет свои атрибуты

В поставке ключом является комбинация: код пост. и код дет., а по отдельности  - это внешние ключи. Существует также дополнительный код поставки – в данном случае это количество.

Пример:

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

ER-диаграмма экземпляров

преподаватель                        предмет

1                                                     1

2                                                     2

3                                                     3

4                                                     4

5


16. Примеры бинарных связей

Виды связи

Оно показывает, сколько экземпляров одного объекта вступает в связь со сколькими экземплярами другого объекта.

Вид связи это не абсолютная характеристика  и меняется в зависимости от предметной области, в которой и работает.

Виды связи бывают:

1:1, 1:n (один ко многим)

n:1 (многие к одному)

n:n (многие ко многим)

Класс принадлежности указывает все ли объекты вступают в связь или есть такие, которые не связаны. Бывает:

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

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

Пример видов связей. (16 – вариантов)

Предметная область – преподаватель читает некоторые лекции.

Пример: тип связи один ко одному.

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

ER-диаграмма экземпляров

преподаватель                        предмет

1                                                     1

2                                                     2

3                                                     3

4                                                     4

5

преподаватель

читает

предмет

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

                              1                           1                1

Другой вариант

- дисциплина читается обязательно одним преподавателем.    

преподаватель

читает

предмет

                                    1                              1  

Третий вариант

- преподаватели  все должны читать лекции, но есть предметы, которые не читаются.

                                                    1  

                                                    2

                                                    3   

                                                    4   

                                                    5

                                                    6  

преподаватель

читает

предмет

                                   1                             1   

Четвертый вариант

- преподаватель читает одну дисциплину, предмет читается один раз.

  1.     

                        1

преподаватель

читает

предмет

                        1

пример: тип связи один ко многим

- преподаватель читает несколько дисциплин, предмет читается не больше чем одним преподавателем.

 

                

преподаватель

читает

предмет

                                          1                             n

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

 

преподаватель

читает

предмет

                                   1                            n

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

                                                   5

                                                   6

  1.  n

преподаватель

читает

предмет

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

 

                                         5

                                         6

                                          7   

  1.  

преподаватель

читает

предмет

n       

Пример  многие к одному

- одна дисциплина может читаться несколькими преподавателями. Преподаватель не может читать несколько дисциплин.

 

   

преподаватель

читает

предмет

                                           n                            1                 

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

  

преподаватель

читает

предмет

                                            n                          1        

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

  

                                        n                           1        

преподаватель

читает

предмет

 

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

 

преподаватель

читает

предмет

                                  n                              1

   Пример многие ко многим  

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

                                       

преподаватель

читает

предмет

                                        n                            n  

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

  

преподаватель

читает

предмет

                                                 n                         n   

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

преподаватель

читает

предмет

                                            n                         n   

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

   

преподаватель

читает

предмет

                                       n                                    n  


17. Правила Джексона для перехода от модели Чена к реляционной модели

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

Их можно разделить на две группы:

1) формальные (математические, скорее теоретические), предполагающие разработку БД только человеком;

2) математические представления, рассчитанные на автоматизацию процесса проектирования БД («компьютерное представление»).

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

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

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

Модель сущность-связь – используется для формального представления из предметной области.

Основные понятия:

  1.  Сущность (объект) – активно действующий субъект в ПО, информация о котором важна с точки зрения данной ПО. Чаще всего сущность называется существительным.

В диаграмме Чена есть 2 варианта:

  1.  ER диаграммы-экземпляров
  2.  ER диаграммы-типов.

Тип объекта – это множество значений, которые могут принимать объекты, и множество операций, которые можно проводить с ними.

Работаем не с каждым объектом отдельно, а объединяем их в типы.

  1.  Атрибут (свойство) – это характеристика, которая показывает в чем сходство или различие конкретных экземпляров объекта. При этом мы должны использовать столько свойств, чтобы можно было отличить экземпляры.

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

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

  1.  Отношения (связи) между сущностями.

     Связи – это глаголы или отглагольные формы.

Так представлены диаграммы – типов:

 сущности      

 атрибуты                    - первичный подчеркивают

отношения    

Из модели Чена, используя эти правила, сразу можно получить нормальную форму.

  1.  Если отношения 1о:1о (индекс о означает обязательный класс принадлежности), то достаточно 1 таблицы, чтобы представить данное отношение.

Пример.

Растут деревья на участках леса:

  Дерево

Участок

Площадь

Сосна

Бор

1

Береза

Роща

2

Осина

Лиственный лес

3

  1.  Если 1о:1н, то для представления информации необходимо 2 таблицы, отдельная таблица для  необязательного класса принадлежности.

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

Участки

Площадь

Бор

1

Роща

2

Лиственный лис

3

Паленина

4

 

Дерево

Участок

Сосна

Бор

Береза

Роща

Осина

Лиственный лес

  1.  Если 1н:1н, то потребуется 3 таблицы.

Например, есть деревья, которые нигде не растут и есть участки, на которых ничего не растет.

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

  1.  Если 1о или нн, то потребуется 2 таблицы.   

В 1 таблицу записываем те объекты, которые относятся к типу связи М. Во вторую таблицу записываем собственно связь.

  1.  Если 1нн, то потребуется три таблицы.

Первая таблица описывает первый объект, вторая таблица описывает второй объект, а третья таблица описывает связь.

  1.  Если М:М, то всегда потребуется три таблицы.
  2.  Если n-объектных таблиц, и их надо связать, то всегда потребуется n+1 таблица, n таблиц отдельно описывают объекты, а n+1 таблица описывает связь между ними.

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

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


18. Реляционная модель данных. 12 правил Кодда.

В конце 60-х годов появились работы, в которых обсуждались возможности применения различных табличных даталогических моделей данных, т.е. возможности использования привычных и естественных способов представления данных. Будучи математиком по образованию Э.Кодд предложил использовать для обработки данных аппарат теории множеств (объединение, пересечение, разность, декартово произведение). Он показал, что любое представление данных сводится к совокупности двумерных таблиц особого вида, известного в математике как отношение – relation (англ.)

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

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

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

Отношение на доменах D1, D2, ..., Dn (не обязательно, чтобы все они были различны) состоит из заголовка и тела. На рис. 3.1 приведен пример отношения для расписания движения самолетов.

Заголовок  состоит из такого фиксированного множества атрибутов A1, A2, ..., An, что существует взаимно однозначное соответствие между этими атрибутами Ai и определяющими их доменами Di (i=1,2,...,n).

Рис. 3.1. Отношение с математической точки зрения (Ai - атрибуты, Vi - значения атрибутов)

Тело состоит из меняющегося во времени множества кортежей, где каждый кортеж состоит в свою очередь из множества пар атрибут-значение (Ai:Vi), (i=1,2,...,n), по одной такой паре для каждого атрибута Ai в заголовке. Для любой заданной пары атрибут-значение (Ai:Vi) Vi является значением из единственного домена Di, который связан с атрибутом Ai.

Степень отношения – это число его атрибутов. Отношение степени один называют унарным, степени два – бинарным, степени три – тернарным, ..., а степени n – n-арным. Степень отношения "Рейс"  – 8.

Кардинальное число или мощность отношения – это число его кортежей. Мощность отношения "Рейс" равна 10. Кардинальное число отношения изменяется во времени в отличие от его степени.

Поскольку отношение – это множество, а множества по определению не содержат совпадающих элементов, то никакие два кортежа отношения не могут быть дубликатами друг друга в любой произвольно-заданный момент времени. Пусть R – отношение с атрибутами A1, A2, ..., An. Говорят, что множество атрибутов K=(Ai, Aj, ..., Ak) отношения R является возможным ключом R тогда и только тогда, когда удовлетворяются два независимых от времени условия:

  1.  Уникальность: в произвольный заданный момент времени никакие два различных кортежа R не имеют одного и того же значения для Ai, Aj, ..., Ak.
  2.  Минимальность: ни один из атрибутов Ai, Aj, ..., Ak не может быть исключен из K без нарушения уникальности.

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

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

Отношение – Таблица (иногда Файл),
Кортеж – Строка (иногда Запись),
Атрибут – Столбец, Поле.

При этом принимается, что "запись" означает "экземпляр записи", а "поле" означает "имя и тип поля".

Необходимым условием работы с СУБД является знание реляционной модели БД. Это наиболее популярная модель хранения данных. Доктор Кодд определил 13 правил реляционной модели (которые называют 12 правилами Кодда).

12 правил Кодда. 

  1.  Реляционная СУБД должна быть способна полностью управлять базой данных, используя связи между данными.
  2.  Информационное правило - Вся информация в реляционной БД (включая имена таблиц и столбцов) должна определяться строго как значения таблиц.
  3.  Гарантированный доступ - Любое значение БД должно быть гарантированно доступным через комбинацию имени таблицы, первичный ключ и имя столбца.
  4.  Поддержка нулевого значения - СУБД должна уметь работать с нулевыми (пустыми) значениями. Нулевое значение - это неизвестное, независимое, неприменимое значение, в отличие от значений по умолчанию и обычных значений.
  5.  Активный, оперативный реляционный каталог - Описание БД и его содержимое должны быть определены на логическом уровне через таблицы, к которым можно применять запросы, используя DML (язык манипулирования данными).
  6.  Исчерпывающее подмножество языка данных - По крайней мере, один из поддерживаемых языков должен иметь четко определенный синтаксис и быть самодостаточным. Он должен поддерживать определение данных и манипулирование ими, правила целостности, авторизацию и транзакции.
  7.  Правило обновления представлений - Все представления, теоретически обновляемые, могут быть обновлены через систему.
  8.  Вставка, обновление и удаление - СУБД поддерживает не только запрос данных, но и вставку, обновление и удаление.
  9.  Физическая независимость данных - Логика программ-приложений остается прежней при изменении физических методов доступа к данным и структур хранения.
  10.  Логическая независимость данных - Логика программ-приложений остается прежней, в пределах разумного, при изменении структур таблиц.
  11.  Независимость целостности - Язык БД должен быть способен определять ограничения целостности. Они должны быть доступны из оперативного каталога, и не должно быть способа их обойти.
  12.  Независимость распределения - Запросы программ-приложений логически не затрагиваются при первом и последующих распределениях данных.
  13.  Несмешиваемость (может, кто-то знает более удачный перевод термина ?) - невозможность обойти ограничения целостности, используя языки низкого уровня.

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

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


19. Ограничения целостности в реляционной модели данных и их поддержка в SQL

Целостность (от англ. integrity – нетронутость, неприкосновенность, сохранность, целостность) – понимается как правильность данных в любой момент времени. Но эта цель может быть достигнута лишь в определенных пределах: СУБД не может контролировать правильность каждого отдельного значения, вводимого в базу данных (хотя каждое значение можно проверить на правдоподобность). Например, нельзя обнаружить, что вводимое значение 5 (представляющее номер дня недели) в действительности должно быть равно 3. С другой стороны, значение 9 явно будет ошибочным и СУБД должна его отвергнуть. Однако для этого ей следует сообщить, что номера дней недели должны принадлежать набору (1,2,3,4,5,6,7).

Целостность данных - это механизм поддержания соответствия базы данных предметной области.

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

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

  1.  Целостность по сущностям.
  2.  Целостность по ссылкам.
  3.  Целостность, определяемая пользователем.

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

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

Целостность ссылок Значение внешнего ключа должно либо:

  1.  быть равным значению первичного ключа цели;
  2.  быть полностью неопределенным, т.е. каждое значение атрибута, участвующего во внешнем ключе должно быть неопределенным.

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

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

Целостность определяемая пользователем. Для любой конкретной базы данных существует ряд дополнительных специфических правил, которые относятся к ней одной и определяются разработчиком. Чаще всего контролируется: уникальность тех или иных атрибутов, диапазон значений экзаменационная оценка от 2 до 5),принадлежность набору значений (пол "М" или "Ж").

В общем случае целостность данных может нарушаться по следующим основным причинам:

1) ошибки в создании структуры локальных БД и их заполнении;

2) просчеты в построении структуры РБД (процедуры фрагментации и локализации);

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

4) аварийная ситуация (неисправность технических средств) и восстановление РБД.

Логическая целостность

Логическая целостность – нарушается, если база некорректно обновлена.

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

Семантическая целостность

Семантическая целостность – соответствие данных в разных полях. Осуществляется проверка связи между данными, хранящимися в разных полях.

Например, дата окончания школы не может быть на 16 лет раньше рождения.

Механизмы поддержания семантической целостности:

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

Триггеры - средство, обеспечивающее автоматическое выполнение некоторых действий при каждой модификации таблицы.

Триггер характеризуется следующими классификационными признаками, которые должны быть заданы при его создании:

  1.  условие активизации - действие над таблицей, которое вызывает запуск триггера - такими действиями являются операции INSERT, DELETE, UPDATE;
  2.  время активизации - выполнение триггера до или после выполнения операции над таблицей;
  3.  область действия - выполнение триггера либо один раз для каждого оператора модификации таблицы, либо для каждой строки, изменяемой / удаляемой / вставляемой в таблицу.

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

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

Триггеры: Oracle

Триггер создается оператором языка SQL CREATE TRIGGER:

Отличия триггера Oracle от триггера DB2 (многие из них видны из самого синтаксиса оператора) состоят в следующем:

  1.  Оператор CREATE позволяет заменить триггер (в DB2 для этого нужно уничтожить триггер и создать его заново).
  2.  Триггер можно создавать и для представления (это связано прежде всего с более широкими возможностями изменения представлений в Oracle).
  3.  Введено новое условие активизации INSTEAD OF (триггер выполняется вместо оператора); оно применяется только для представлений и позволяет изменять базовые таблицы вместо неизменяемого представления.
  4.  Для триггера могут быть назначены несколько условий активизации (через операцию OR). В этом случае действие триггера может "узнать" по какому условию запущен триггер, проверяя значения предикатов INSERTING, DELETEING, UPDATING.
  5.  В условии фразы WHEN не допускаются запросы.
  6.  Собственно выполняемые действия триггера задаются в виде блока на языке PL/SQL.

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


20. Восстановление данных в БД

Если РБД обеспечивает целостные, непротиворечивые данные, говорят об ее корректном состоянии (корректности).

Восстановление (управление восстановлением) связано с приведением системы в корректное состояние после (аппаратного) сбоя.

Любой конкретный метод восстановления реагирует на определенный отказ РБД.

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

Система восстановления решает две группы задач:

1) при незначительной неисправности - откат в выполнении текущей транзакции;

2) при существенных отказах - минимизация работы по восстановлению РБД.

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

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

Журнал может содержать одну или более групп файлов регистрации и членов групп для физического сохранения изменений РБД. Любая группа включает один или более файлов, которые могут храниться на разных дисках, как это делается в СУБД Oracle [].

Процедура восстановления проводится следующим образом.

  1.  Устраняется аппаратный сбой.
  2.  Восстанавливаются испорченные файлы данных путем копирования архивных копий и групп регистрации транзакций.
  3.  Запускается процесс восстановления:

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

б) с отменой - отмена незавершенных транзакций, оставшихся после восстановления с применением транзакций.

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

Изучим подробнее процесс отказа.

Возможно выделить следующие основные состояния узла: исправный, неисправный (застопоривший, неуправляемый), восстанавливаемый.

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

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

Обсудим два возможных случая работы узлов в надежной сети: без дублирования и с дублированием данных.

При отсутствии дублирования не рассматриваются неуправляемые узлы (узлы с потерей управления).

Обычно одна транзакция при удаленном вызове (рис. 14.1) делится на серию субтранзакций.

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

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

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

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

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

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

Достоинствами метода основной копии являются единственная последовательность корректировки БД и уменьшение вероятности тупика.

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

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

Пример 14.2. Пусть узел 2 восстановился. Он запрашивает информацию о пропущенных транзакциях. Основной узел передает данные по транзакциям T1 , ..., Tn и добавляет узел 2 в список U. Однако транзакция Tn+1 , находящаяся в состоянии фиксации, имеет старый список и не будет записывать в узел 2.

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

Возможны и другие методы []:

1) выбор нового основного узла при отказе прежнего, при этом прежний узел должен быть восстанавливаемым, а новый - «видеть» обстановку, сложившуюся в прежнем узле. Доступ упрощается, но усложняется восстановление.

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

Схема восстановления одного из узлов показана на рис. 14.4.

Пусть в момент t1 отказал узел 2 и его БД разрушилась. Если узел 2 не будет исправлен до момента времени t5 , то отказ узла 1 или 2 приведет к серьезному сбою. Узел 2 выявляет свой отказ к моменту t2 и начинает восстанавливаться, используя «снимки» других узлов. На интервале t3 - t4 исправные узлы должны продолжать выполнение транзакций, которые должен запоминать узел 2 (и обрабатывать после момента t4 ). С момента t4 узел 2 присоединяется к остальным и система может выдержать второй отказ.

Меры преодоления проблем нарушения физической целостности:

  1.  введение копии базы данных

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

К.т.5

К.т.4

К.т.3

К.т.2

К.т.1

журнал

журнал

ж

сбой

сын

отец

дед

       

RAID-массивы

Рис.1

В 4 контрольной точке затирается дед, отец становится дедом, сын – отцом и появляется новый сын.

К.т.1

К.т.2

К.т.3

дед

Отец

дед

сын

отец

журнал

журнал

К.т.4

К.т.5

сбой

ж

RAID-массивы

сын

Рис.2

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




1. . Понятие о темпераменте
2. І Мета і завдання
3. Лабораторная работа 5 Тема-
4. Вариант 20 Фирма по производству мебели может выпускать письменные полки з типов- одноярусные двухъярусные
5. 1213 1 Син ~ Бар Булганны~ Барысы да
6.  Экономикогеографическое положение Природные условия 3
7. Определение допусков на составляющие звенья размерной цепи- Z11 8 ~ 11 ] 8 11 Z11 8 Z11 8 мм
8. Звуковые волны
9. Космический мусор угроза безопасности космических полетов
10. Развитие личности ребенка под влиянием факторов среды
11.  Комбинированные уроки Одинаковое соотношение образовательных воспитательных и оздоров
12. Общественные объединения
13. Влияние материнского отношения на состояние соматического и эмоционального благополучия младенца
14. а; после регистрации отзвонить Рубцову А.
15. В 1932 году общее количество безработных в капиталистических странах превышало 30 млн
16. ТЕМА- Гетерофункциональные соединения аминоспирты гидрокси и аминокислоты оксокислоты ЦЕЛЬ- Изучить ос
17. Рішення як форма здійснення управління Управління ~ це постановка цілей і організація впливу на об~єкт
18. Исследование Дальневосточного федерального округа
19. Свойство высокоэнергетических магнитов и их применение
20. В журнале указывают содержание операции номер документа на основании которого произведена запись сумму о