Московский государственный университет печати

Чертовской В.Д.


         

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

Учебное пособие


Чертовской В.Д.
Базы и банки данных
Начало
Печатный оригинал
Об электронном издании
Оглавление

Введение

Часть 1. ОСНОВНЫЕ ПОЛОЖЕНИЯ

Раздел 1. Основные понятия

1.

Глава 1. Общие сведения

1.1.

Данные, информация, знания

1.2.

Основные понятия и определения

1.3.

Классификация БД и СУБД

1.4.

Состав СУБД и работа БД

2.

Глава 2. Концепция баз данных

2.1.

Требования, предъявляемые к базам данных

2.2.

Концепция построения БД

2.3.

Методология проектирования баз данных

2.4.

Методология использования баз данных

Раздел 2. Теория баз данных

3.

Глава 3. Общая теория

3.1.

Модели представления данных

3.2.

CASE-технология

3.3.

CASE-средства

4.

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

4.1.

Математические основы теории

4.2.

Построение БД

4.3.

Использование БД

4.3.1.

Запросы к данным

4.3.2.

Синхронизация процессов доступа

Часть 2. Централизованные базы данных

Раздел 3. Реализация бд (модели БД)

5.

Глава 5. Реляционные БД SQL

5.1.

Логическая структура

5.2.

Создание БД

5.3.

Использование БД

5.3.1.

Язык SQL

5.3.2.

Язык QBE

6.

Глава 6. Сетевые БД

6.1.

Логическая структура

6.2.

Программная реализация

6.2.1.

Создание БД (ЯОД)

6.2.2.

Использование БД (ЯМД)

7.

Глава 7. Иерархические БД

7.1.

Логическая структура

7.2.

Программная реализация

7.2.1.

Создание БД (ЯОД)

7.2.2.

Использование БД (ЯМД)

8.

Глава 8. Взаимосвязь МД

8.1.

Сравнительная характеристика моделей данных

8.2.

Преобразование моделей данных

8.3.

Выбор моделей данных

9.

Глава 9. Физическая БД

9.1.

Вопросы программной реализации БД

9.2.

Организация хранения и доступ

9.3.

Доступ к данным и их обновление

Раздел 4. Современные направления развития БД

10.

Глава 10. Автоматизация проектирования

10.1.

Классический подход к проектированию

10.1.1.

Однопользовательский режим

10.1.2.

Многопользовательский режим

10.2.

Современный подход к проектированию

10.3.

Автоматизация проектирования

11.

Глава 11. Объектно-ориентированные базы данных

11.1.

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

11.2.

Состояние развития ООБД

11.3.

Сущность ООБД

11.4.

Недостатки и перспективы развития ООБД

Часть 3. Распределенные базы данных (РБД)

Раздел 5. Основы теории РБД

12.

Глава 12. Общая характеристика РБД

12.1.

Новые требования, предъявляемые к БД

12.2.

Состав и работа РБД

12.3.

Система клиент/сервер

Раздел 6. Основы теории РБД

13.

Глава 13. Создание РБД

13.1.

Обеспечение целостности

13.2.

Фрагментация и локализация

13.3.

Процесс интеграции

13.4.

Преобразование структуры и данных

13.5.

Однородные и неоднородные РБД

14.

Глава 14. Использование РБД

14.1.

Одновременный доступ

14.2.

Защита

14.3.

Восстановление РБД

14.4.

Запросы

Заключение

Контрольные вопросы

Литература

Указатели
11  именной указатель
360  предметный указатель
163  указатель иллюстраций
25  указатель компаний

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

В теории реляционных База данных реляционнаябаз данных выделяют теоретическое представление процедур:

    1) создания БД (с учетом целостности и защиты данных);

    2) запросов и обновления данных;

    3) синхронизации процессов многопользовательского доступа к данным.

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

Теоретическим инструментом двух первых процедур являются реляционная алгебра и реляционное исчисление.

4.1.
Математические основы теории

Основные понятия. В основе База данных реляционнаяреляционной БД лежит понятие «отношение», «связь».

Отношение r на множествах (доменах)Отношением r называется подмножество декартова произведения. Поля отношения (таблицы) могут располагаться в произвольном порядке. Чтобы установить определенный порядок для какой-либо конкретной реализации, вводят понятие «схема» R - множество упорядоченных имен атрибутов R(A1 , ..., An ). Говорят о схеме R отношения r или r (R). Любому имени Ai ставится в соответствие множество Di (домен или dom (Ai )). Схема - конечное множество кортежей tr, при этом t (Ai ) = Di .

ПарадигмаПарадигмой реляционных БД является ключ r отношения R - подмножество K = {B1 , ..., Bm }R, m≤n, с ограничениями:

    1) для любых двух кортежей t1 и t2 существует BK такое, что t1 (B) ≠t2 (B);

    2) t1 (K) ≠ (K);

    3) ни одно собственное подмножество K"K не обладает свойством ключа.

Ключи, явно перечисленные вместе с реляционной схемой, называются Ключ явныйявными; в противном случае - Ключ неявныйнеявными. Один из выделенных ключей называется Ключ первичныйпервичным. Если ключ K"KR, то K - Суперключсуперключ (составной ключ).

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

Например, пусть имеется отношение

R(Город, Адрес, Почтовый_индекс).

Очевидно, что атрибуты Город Адрес Почтовый_индекс. В то же время Почтовый_индекс Город (хотя и не адрес). Оба множества могут быть возможными ключами.

Универсум UУниверсум U - множество значений всех атрибутов. С учетом ключей схема R над U - совокупность отношений {R1 , ..., Rт }, где

Тогда реляционной БД d со схемой данных R называется совокупность отношений {r1 , ..., rn }, где для любой схемы R = {S, K} существует отношение в d, являющееся отношением со схемой S, удовлетворяющее любому ключу.

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

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

Возникает вопрос: каковы должны быть правила создания и преобразования таблиц?

Фактически для таблиц выделяют следующие составляющие:

    1) создание;

    2) обновление и запрос;

    3) синхронизация процессов доступа.

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

Начнем обсуждение операций преобразования таблиц.

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

    1) предикатами первого порядка;

    2) использованием правил Алгебра реляционнаяреляционной алгебры (РА) и Исчисление реляционноереляционного исчисления (РИ).

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

АлгебраАлгебра - исходное множество А с определенными на ней операциями вида f: An A, где n - размерность.

ИсчислениеИсчисление - совокупность правил оперирования с какими-либо символами.

РИ по своей сути проще, но его применение ограничено следующими обстоятельствами:

    1) многие алгоритмические проблемы еще не разрешены и не могут быть решены в рамках РИ;

    2) большая комбинаторная сложность реляционных схем не вскрывается РИ;

    3) практически не удается - в рамках РИ - доказать полноту проводимых операций преобразования.

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

Реляционная алгебра. Пусть C1(L) - множество всех замкнутых формул системы L.

Если формула φC1(L), то говорят, что модель М удовлетворяет φ (φ = M), если φ истинно на М.

Пусть γC1(L). Формула Ψ называется следствием γ (выводима из γ, если из Ψ = M следует γ = М для любой модели М.

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

Пусть по-прежнему U - универсум (множество атрибутов), D - множество доменов, dom - полная функция из U (dom: U D), R = {Ri , i = 1, p} - множество схем отношений, d = {ri , i = 1, p} - множество всех отношений ri (Ri ), = {≠, =, ≤, ≥, < , >} - множество бинарных отношений (условий над доменами из D), О - множество операторов (операций), использующих атрибуты из U и отношения из .

Реляционная алгебра над U, D, dom, R, d, Q называется семиместным кортежем B = {U, D, dom, R, d, , O}.

В реляционной алгебре выделяют следующие операции: проекция обозначается π или P (в разных источниках), селекция (σ или S), cоединение (J), объединение (U), разность (DF), деление, пересечение, декартово произведение (CP). Пусть имеется два отношения (A, B, C) и P (D, E, F). Объединения, пересечения и вычитания (разность) производятся над отношениями одинаковой арности.

1. Операция объединения U (R, P) - без повторений строк:

2. Разность (DF(R, P)) - из R удаляются строки, имеющиеся в P:

3. Пересечение RP - общие элементы множеств:

4. Декартово произведение (СР(R, P)):

5. Проекция πS(A) (R), где S(A) - список доменов результирующего отношения из числа доменов отношения R: выбираются и упорядочиваются столбцы и удаляется избыточность из строк:

6. Селекция (выбор) σF (R), где F(Ai , , «константа») - исходное отношение n-арности; Ai - атрибут отношения R; или m - логическое условие (< , >, =, < >, , , ┐ ):

7. Соединение JAmB (R, P) = Q = σAmB :

8. Если сравниваемые поля, имена которых лучше сделать одинаковыми, в результирующем отношении «считаются» только один раз, то говорят о естественном соединении (слиянии) NJ:

где - список совпадающих атрибутов в исходном отношении; 1, ..., m - упорядоченный список всех компонентов декартова произведения , за исключением , ..., .

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

9. Деление (X, Y)Y = X.

Операции идут на бинарном (делитель) и унарном (делимое) отношениях, а результат (частное) получается унарным отношением. x появляется в результирующем отношении, если пара <x, y> имеется в делимом для всех значений y, присутствующих в делителе. Частное - те левосторонние компоненты делимого, чьи правосторонние элементы включают любой компонент делителя.

Пусть имеется

Наиболее часто используются операции селекции (S), проекции (P) и соединения (J), называемые SPJ-операциями.

Рассмотрим свойства операцийссылка на источники литературы. В школьном курсе вводится алгебра: элементы - поля N, операции - сложение, вычитание, умножение, деление. Их основные свойства: коммутативность ab = ba, ассоциативность (ab)c = a(bc), дистрибутивность (a+b)c = ab+bc, идемпотентность a2 = a. В таком же плане рассмотрим свойства РА.

I. Коммутативность.

Унарные операции:

  1. SF1 (SF2 (R)) = SF2 (SF1 (R)),

  2. PA1 (PA2 (R)) = PA2 (PA1 (R)), если A1 = A2 ,

  3. SF1 (PA1 (R)) = PA1 (SF1 (R)), если Attr(F1 ) A1 ,

  4. PA1 (SF1 (R)) = SF1 (PA1 (R)), если Attr(F1 ) A1 ,

    Бинарные операции:

  5. JF (R, S) JF (S, R),

  6. U(R, S) U(S, R),

  7. CP(R, S) CP(S,R).

II. Ассоциативность бинарных операций:

  1. U(U(R, S), T) U(R, U(S, T)),

  2. CP(CP(R, S), T) CP(R, CP(S, T)),

  3. JF2 (JF1 (R, S), T) JF1 (R, JF2 (S, T)).

III. Идемпотентность унарных операций:

  1. PA1 (R) PA2 ((PA (R)), если A = A1 , AA2 ,

  2. SF1 (R) SF2 ((SF (R)), если F = F1 F2 .

IV. Дистрибутивность бинарных операций между бинарными:

  1. SF (U(R, S)) U(SF (R), SF (S)),

  2. SF (DF(R, S)) DF(SF (R), SF (S)),

  3. SF (CP(R, S)) CP(SF (R), S), если Attr(F)Attr(S),

  4. SF1 (JF (R, S)) JF1 (SF (R), SF (S)), если Attr(F)Attr(S),

  5. PA (U(R, S)) U(PA (R), PA (S)),

  6. PA (CP(R, S)) CP(PA (R), PA (S)).

V. Факторизация унарных операций:

  1. U(SF (R), SF (S)) SF (U(R, S)),

  2. CP(SFR (R), SFS (S)) SF (CP(R, S)), где F = FRFS,

  3. JF (SF (R), SF (S)) SF (JF (R, S)), где F = FRFS,

  4. DF(SFR (R), SFS (S)) SFR SFR (DF(R, S)), где FR FS,

  5. U(PA (R), PA (S)) PA (U(R, S)),

  6. CP(PAR (R), PAS (S)) PA (CP(R, S)), где A = ARAS.

Перечисленные правила используются прежде всего при формировании и оптимизации запросов (§ 4.3.1).

Алгебра реляционнаяРеляционная алгебра больше предназначена для описания процедур запросов и обновления.

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

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

Это удалось сделать с помощью функционального подхода (формул однозначных {1:1, 1:М} F- и многозначных {1:М и прежде всего М:М} MV-зависимостей) и, как следствие, путем выполнения процедуры нормализации.

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

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

Функциональные (однозначные) F-зависимости. Функциональные зависимости являются обобщением понятия ключа: значения кортежа на одном множестве X атрибутов определяют значения на другом множестве Y атрибутов; X, YR; R - схема отношения R.

Пусть имеется r(R) и X, YR.

Отношение удовлетворяет функциональной зависимости (ФЗ) X Y, если pY((R)) имеет не более одного кортежа для любого xX . Проверка проводится так (рис. 4.1.):Рис. 04.01. F-зависимость если кортежи (X) = (X), то должно удовлетворяться условие (Y) = (Y).

Такие однозначные зависимости называются F-зависимостями. Множество F-зависимостей также обозначается F. Иначе сказанное записывается в виде: FX Y влечет X Y или говорят об аксиоме вывода.

Аксиома вывода - правило: если отношение удовлетворяет некоторым F-зависимостям, то оно должно удовлетворять и другим F-зависимостям.

Пример 4.1. Пусть имеем расписание занятий РАСПИСАНИЕ (День, Время, Аудитория, Преподаватель, Группа). Введем две ФЗ:

f1 : День Время Аудитория Преподаватель Группа,

f2 : День Время Преподаватель Аудитория Группа.

Далее используем следующие ФЗ:

f1 : Студент Курсовая_работа,

f2 : Студент Преподаватель,

f3 : Преподаватель Кафедра,

f4 : Кафедра Факультет,

f5 : Студент Факультет.

Пусть R = {a, ..., A}; X, Y, Z, WR. Для любого r(R) справедливы следующие аксиомы вывода.

F1. X = X. Рефлексивность: πX (SX=x (r)) имеет не более одного кортежа. Например, Студент Студент.

F2. Транзитивность: если X Y и Y Z, то X Z. Если t1 (X) = t2 (X), то t1 (Y) = t2 (Y) по определению. Если t1 (Y) = t2 (Y), то и t1 (Z) = t2 (Z). Следовательно, если t1 (X) = t2 (X), то t1 (Z) = t2 (Z).

Иначе говоря из Студент Преподаватель и Преподаватель Кафедра следует Студент Кафедра.

F3. Пополнение: если X Y, то XZ Y.

Из X Y следует (), что πY (SX=x (R)) имеет не более одного кортежа для любого xX. Если Z R, то σXZ=xz (R)σX=x (R) и πYXZ=xz (R))πY (SX=x (R)) имеет не более одного кортежа.

Следовательно, если Студент Преподаватель, то Студент Кафедра Преподаватель. Или из A B следует AС B и AD B, ABC B, ABD B, ACD B, ABCD B.

F4. Псевдотранзитивность: если X Y, YZ W, то XZ W.

Если t1 (X) = t2 (X), то t1 (Y) = t2 (Y) по определению. Если t1 (YZ) = t2 (YZ), то и t1 (W) = t2 (W). Следовательно, из t1 (XZ) = t2 (XZ) имеем t1 (X) = t2 (X) и t1 из="../Ресурсы/t-1.htm"/>(Z) = t2 (Z), (Y) = t2 (Y), t1 (YZ) = t2 (YZ) и t1 (W) = t2 (W). Иначе, если Студент Преподаватель, Преподаватель Кафедра Факультет, то Студент Кафедра Факультет или из A B, BC D следует AC D.

F5. Аддитивность, если X Y и X Z, то X YZ.

По определению, πYX=x (R)) и πZX=z (R)) имеют не более одного кортежа. Если πYZX=x (R)) имеет более одного кортежа, то хотя бы одна зависимость имеет более одного кортежа.

Следовательно, если Студент Преподаватель, Студент Кафедра, то Студент Преподаватель Кафедра или из A B, A C следует A BC.

F6. Проективность (в определенной степени обратна аддитивности): если X YZ, то X Y и X Z.

По определению, πYZX=x (R)) и πZX=z (R)) имеют не более одного кортежа. Однако πYYZX=x (R))) = πYX=x (R)) и πYX=x (R)) тоже имеют не более одного кортежа, т.е. X Y.

Итак, если Студент Преподаватель Кафедра, то Студент Преподаватель и Студент ® Кафедра или если A BC, то A C и A B.

Система F1 - F6 является полной: с ее помощью можно получить (путем многократного применения) любую F-зависимость для множества F. Аксиомы F2, F5, F6 выводятся из F1, F3, F4. Покажем лишь два вывода.

Транзитивность F2 - частный случай аксиомы F4. Аксиома F5: если X Y, X Z, то из F1 следует YZ YZ, из F4 XZ YZ, из F4 X YZ.

Аксиомы F1, F3, F4 иногда называют Аксиомы Армстронгааксиомами Армстронга.

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

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

Лемма. Функциональная зависимость X Y выводима из аксиом Армстронга, если Y X+.

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

Вычисление F+ достаточно сложная процедура. Например, если F = {A1 B1 , ..., An Bn }, то F+

включает A Y, где Y - подмножества множеств {B1 , ..., Bn } и их количество составляет 2n.

Более того, если F-множество F-зависимостей над R и X R, то в F+ существует зависимость X Y такая, что подмножество Y максимально, т.е. Z Y для любой другой F-зависимости X Z в F+.

Если F = {A D, AB DE, CE G, E H}, то можно показать, что (AB)+ = ABCDEH.

Для F = {AB C, AE G, BC D, D E, B AE, EG K} (AB)+ = ABCDEGK.

Сложность алгоритма во времени зависит от размера входного множества F-зависимостей. Следовательно, надо стремиться к минимизации F-множества. Это способствует согласованности и целостности БД (меньше проверок при модификации).

Действительно, множество F = {A B, B C, A C, AB C, A BC} выводимо из множества G = {A B, B C}. Говорят, что множество G покрывает множество F (G эквивалентно F или G F).

На пути минимизации возникает две проблемы: неизбыточность; устранение постороннего атрибута (редуцирования).

Множество F-зависимостей F называется неизбыточным, если нет F"F такого, что F" F. В неизбыточном множестве могут быть посторонние атрибуты, которые могут быть удалены (множество может быть редуцировано).

Пусть имеется множество F-зависимостей F = {Xi Yi , i = 1, n}. Множество атрибутов Zi Yi называется посторонним в Xi , если (Xi \Zi ) φi может быть получено в замыкании F+.

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

Множество F-зависимостей F минимально, если оно содержит не более F-зависимостей, чем любое эквивалентное множество F-зависимостей.

Теория F-зависимостей используется при нормализации (1НФ - 3НФ), однако кроме F-зависимостей (отношения 1:1) могут существовать MV-зависимости (отношения 1:М). Для них используются несколько иные правила.

Функциональные многозначные MV-зависимости. Определение. Пусть R -реляционная схема; X и Y - непересекающиеся множества на R и Z = R - (XY). Отношение r(R) удовлетворяет многозначной MV-зависимости X –» Y, если для любых кортежей t1 и t2 из r, для которых t1 (X) = t2 (X), в r существует кортеж t3 такой, что t3 (X) = t1 (X), t3 (Y) = t1 (Y), t3 (Z) = t2 (Z) (рис. 4.2).Рис. 04.02. MV-зависимость

Из симметрии существует и кортеж t4 такой, что t4 (X) = t1 (X), t4 (Y) = t2 (Y) t4 (Z) = t1 (Z).

Лемма. Если отношение r(R) удовлетворяет MV-зависимости X –» Y и Z = R - (XY), то r удовлетворяет X –» Z, (XY) = .

Иначе говоря, если существуют кортежи fdp и fd"p", то должны быть и fd"p (и fdp").

Теорема. Пусть r - отношение со схемой R; X, Y, Z R такое, что Z = R - (XY). Отношение r(R) удовлетворяет MV-зависимости X –» Y тогда и только тогда, когда r без потери информации раскладывается в отношения со схемами R1 = XY и R2 = XZ.

AB –» BC и AB –» C имеет вид

Проверка выполнения X –» Y возможна двумя способами.

    1. {XY} NJ {X(R - XY)} = Z, где NJ - операция слияния.

    2. Пусть Z = R - (XY), R1 = XY, R2 = XZ. Если r1 = πR1 (r), r2 = πR2 (r), то (r1 )NJ(r2 )r.

Пусть для xX существует c1 кортежей в r1 и c2 в r2 со значением x. Пусть с - число кортежей в r. Если для любого xX = c1 +c2 , то r = (r1 )NJ(r2 ).

Пример 4.2. Введем обозначения:

CW [X = x](r) = |πWX=x (r))|, CABCD [AB = ab](r) = 4,

CC [AB = ab](r) = 2, CD [AB = ab](r) = 2, CABCD = CC ×CD и R1 = ABC;

Z = R - ABC=D; R2 = ABD.

Пусть R - схема отношений и X, Y, Z, WR.

Для MV-зависимостей существует ряд аксиом, которые по своему виду несколько отличны от аксиом F-зависимостей.

M1. Рефлексивность. X –» X.

M2. Пополнение. Если X –» Y, то XZ –» Y.

M3. Аддитивность. Если X –» Y и X –» Z, то X –» YZ. Эти аксиомы похожи на аксиомы F-зависимостей.

M4. Проективность. Если X –» Y и X –» Z, то X –» YZ, X –» Y - Z.

M5. Транзитивность. Если X –» Y и Y –» Z, то X –» Z - Y.

M6. Псевдотранзитивность. Если X –» Y и YW –» Z, то XW –» Z - YW.

Следующая аксиома не имеет аналога для F-зависимостей.

M7. Дополнение. Если X –» Y и Z = R - (XY), то X –» Z.

Докажем только аксиому M3, поскольку остальные доказательства похожи по своей идее.

Из X –» Y следует существование кортежа t1 со свойствами t3 (X) = t1 (X), t3 (Y) = t2 (Y), t3 (V) = t2 (V), где V = R - (XY).

Аналогично из X –» Z следует t4 (X) = t1 (X), t4 (Z) = t1 (Z), t4 (W) = t2 (W), где W = R - (XZ).

Надо найти кортеж t(X) = t1 (X), t(YZ) = t1 (YZ), t(U) = t2 (U), где U = R - (XYZ). Пусть t = t4 . Тогда t(X) = t4 (X), t4 (Z) = t(Z), t4 (Y) = t4 (YW) = t3 (YW) = t1(YW) = t (YW) и t4 (YZ) = t(YZ). Поскольку U (R-XY)(R - XZ) = VW, то t4 (X) = t4 (U) = t3 (U) = t(U).

Когда речь идет об MV-зависимостях, то вместе с ними могут существовать и F-зависимости. MV- и F-зависимости связаны двумя аксиомами.

С1. Копирование. Если имеется r(R) и X Y, то X –» Y.

C2. Объединение. Если X –» Y и Z –» W, где W Y и YZ = , то X –» W.

Можно показать, что:

    1) система М1 - М7 полна,

    2) система F1 - F6, M1 - M7, C1 - C2 для множеств F- и MV-зависимостей полна.

Свойства F- и MV-зависимостей используем в § 4.2 в процедуре нормализации.

В ней участвуют две составляющие:

    1) F-зависимости, которые дают возможность получить 1НФ, 2НФ, 3НФ, а также нормальную форму Бойса-Кодда (НФБК);

    2) MV-зависимости, связанные с 4НФ и 5НФ.

1. F-зависимости. Основное правило: необходимо, чтобы r(R) разлагалось на отношения (схемы), например R1 и R2 , без потерь, т.е.

R1 (r)}NJ{πR2 (r)} = r.

Нормализация возможна через декомпозицию или методом синтеза.

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

Говорят, что F-зависимость X Y применима к схеме R, если X Y является F-зависимостью над R. Пусть БД d = {r1 , ..., rn } со схемой R = {R1 , ..., Rn } и F - множество F-зависимостей над U. БД d удовлетворяет F, если любая F-зависимость X Y из F+ применима к схеме R и выполняется отношение r.

В общем случае F может быть избыточно и потому выявляют G F и G F. Говорят, что G навязан схеме R и используют G-зависимость для композиции.

Пусть G-множество всех F-зависимостей в F+, которые применимы к какой-либо схеме Ri R. Любая F-зависимость в G+ называется навязанной R, любая F-зависимость (F+ - G+) - ненавязанной R. Множество F навязано схеме R БД, если любая G-зависимость в F+ навязана R, т.е. G F.

Пример 4.3. Пусть R = {R1 , R2 , R3 }, R1 = ABC, R2 = BCD, R3 = DE и F = {A BC, C A, A D, D E, A E}. A D и A E неприменимы ни к одной схеме Ri . Однако F навязано R, так как G = {A BC, C A, C D, D E} F и каждая F-зависимость в G применима к некоторой схеме в R. F" = {A D} не является навязанной.

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

В реляционном исчислении выделяют исчисление доменов и исчисление кортежей.

Исчисление кортежей при прежних обозначениях определяется шестеркой

<U, D, dom, R, d > (4.1)

и имеет выражение {x(R)|f(x)}, где f -разрешенная формула над U; x - свободная переменная.

Исчисление кортежейИсчисление кортежей - формализованная система обозначений и правил для записи выражения нового правила.

Для описания операций в исчислении Кортежкортежей возможно использовать предложенный Кодд Э.Ф.Э. Коддом язык АЛЬФА. В нем ссылка на источники литературы используются следующие операторы: get w - получить из рабочей области w; range - область; hold - найти (первичный ключ запоминает место кортежей); put - включить; having - принадлежащий; update - обновить, insert - вставить, delete - уничтожить; up, down - (сортировка) по возрастанию, убыванию; count - считать (число записей); total - общий итог. Применяются следующие обозначения: Y.X - множество элементов данных из домена X в реляционном отношении Y; - существует; V - любой; - ИЛИ; - И; ┐ - НЕ; "x" - символ значения x.

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

Каждый пользователь обладает своей рабочей областью w (область связи между пользователем и моделью данных). В рабочую область w попадают данные, отобранные в результате поиска (рис. 4.3).Рис. 04.03. Схема выполнения запроса Рабочая область w содержит отношения, выделенные из МД посредством оператора get. Отношение имеет форму таблицы. После завершения работы оператора get содержимое w может обрабатываться любым способом, которые допускают базовые языки программирования. Оператор get обеспечивает всегда прямой поиск (по значениям, условиям для данных) последовательно, но не по адресу. Единицей доступа в языке РИ является экземпляр логической записи (кортеж). Пользователь может определить в операторе get любую выборку доменов из одного или нескольких отношений.

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

СТУД(СН, СФ, Балл, Курс, Группа, Кафедра),

ПРЕП(ПН, ПФ, Должность, Кафедра, Зарплата, Надбавка),

СТПР(СН, ПН, Часы),

где СТУД, ПРЕП, СТПР - отношения Студент, Преподаватель, Студент-Преподаватель; СН, СФ - № зачетной книжки и фамилия студента; ПН, ПФ - табельный № и фамилия преподавателя.

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

  1. Операции поиска:

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

    get w(СТУД.СФ);

    На языке SQL ему соответствует команда

    SELECT Студ.Сф FROM Студ;

    Более подробно язык SQL рассмотрен в главе 5;

    б) поиск с использованием кванторов є и и логических операций - существуют ли фамилии студентов такие, № преподавателя - 2486

    range СТПРx

    get w(СТУД.СФ): x (X.СН = СТУД.СНX.ПН = "2486").

  2. Операции обновления:

    а) простое обновление - заменить название кафедры ИиУс у преподавателя с № 2486

    hold w (ПРЕП.ПН, ПРЕП.Кафедра) : ПРЕП.ПН = 2486 w.Кафедра = ИиУС

    update w;

    б) простое включение - включить (put) в отношение запись о студенте 857 Петрове: балл - 3, курс - 4, группа А4, кафедра ИиУС

    w.СН = 857

    w.СФ = Петров

    w.Балл = 3

    w.Курс = 4

    w.Группа = А4

    w.Кафедра = ИиУС

    put w(СТУД);

    в) удаление - удалить данные о студентах, имеющих балл менее 3

    hold w(СТУД): СТУД.Балл < 3

    delete w;

    д) обновление основного ключа - с № 785 на № 127

    hold w(ПРЕП): ПРЕП.ПН = 785

    delete w

    w.ПН = 127

    put w(ПРЕП).

  3. Вычисляемые операции (библиотечные функции)

    а) количество записей о студентах

    get w(count(СТУД.СН));

    Исчисление доменов. В исчислении доменов, определяемом той же шестеркой элементов <U, D, dom, R, d q> (4.1), переменные используются на доменах и операции могут содержать несколько переменных.

    Запрос: найти номера, фамилии и баллы студентов 4 курса группы А4 кафедры ИиУС

    {X Y Z | СТУД (X Y Z 4 А4 ИиУС)}.

    Запрос: получить фамилии преподавателей и количество часов

    {X Y P | Z L M N Q(ПРЕП(Z ИиУС M N X P)СТПР(Q Z Y))}.

В общем виде - это выражения {a1 ... an | (b1 ) .. (bm ) (R1 (c11 .. c1k )) ... Rp (cp1 .. cpk ))},

где сij - некоторые значения ai , bi , появляющиеся не менее одного раза, или константы. Все переменные неявно связаны квантором существования и отображаются подчеркнутыми символьными строками. Неподчеркнутые строки являются константами. Вывод на печать помечается символом Р.(print), за которым возможно указание имени переменной (например, P.A.).

На основе исчислений кортежей и доменов созданы ссылка на источники литературы декларативные языки SQL и QBE (автор - Злуд М.М.М.М. Злуд) соответственно.

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

В свете сказанного закономерно возникает вопрос о сопоставлении РА и РИ в смысле полноты и замкнутости операций преобразования таблиц.

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

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

Доказано в ссылка на источники литературы однозначное соответствие групп операций реляционной алгебры и реляционного исчисления. Это одновременно является доказательством полноты и замкнутости системы операций в РИ и возможности перехода к декларативным языкам типа SQL.

4.2.
Построение БД

Построение База данныхБД предполагает построение структуры, ее заполнение данными, определение области доступа к данным и их защиту.

Построение структуры связано с Нормализациянормализацией.

Нормализация. В процессе нормализации строятся 1НФ - 5НФ.

1НФ является плоским файлом: в каждом поле может быть только атомарная запись и запись списка или другого сложного объекта не допускается.

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

Проведем построение 1НФ - 3НФ на основе рис. 4.4.Рис. 04.04. Соотношение реляционного исчисления и реляционной алгебры

Пример 4.5.

Очевидно, что таблица СТПР не находится в 1НФ, поскольку в полях ПН и Часы имеют место списки. Приведем таблицу к 1НФ:

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

Включение. Невозможно поставить номер студента СН, если не известен номер преподавателя ПН.

Удаление. Удаление часов удаляет остальную информацию.

Обновление. Изменение k1 требует просмотра нескольких записей.

Для устранения этих недостатков строится 2НФ (рис. 4.5).Рис. 04.05. Построение 2НФ

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

Из рис. 4.5, а) Рис. 04.05. а) Построение 2НФ видно, что полной зависимости от составного ключа СН ПН нет и таблица распадается на две (рис. 4.5, б):Рис. 04.05. б) Построение 2НФ

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

Однако и здесь в таблице С имеют место недостатки.

Включение. Если нет СН, нельзя ввести данные о факультете и кафедре.

Удаление. Удаление данных k1 влечет удаление данных о студенте.

Обновление. Изменение зависимостей Кафедра - Факультет потребует просмотра многих записей.

Необходима 3НФ. Третья нормальная форма устраняет избыточные зависимости между неключевыми атрибутами. Зависимость Кафедра - Факультет является транзитивной и удаляется, а таблица распадается на две: ФС и КС (рис. 4.6).Рис. 04.06. Построение 3НФ

Существует нормальная форма Бойса-Кодда (НФБК). Схема отношения R находится в НФБК относительно F-зависимости F, если для любого YR и любого атрибута AR \Y из Y A следует Y R, т.е. если Y нетривиально определяет произвольный атрибут R, то ключ Y есть суперключ K.

Если Y - не ключ в R, то R = (R \ A, YA).

НФБК существует не всегда.

3НФ является окончательной, если имеют место зависимости 1:1 и 1:М. Для отношений М:М процедура продолжается путем построения 4НФ и 5НФ для MV-зависимостей.

Формулировка 4НФ несколько разнится в ссылка на источники литературы и ссылка на источники литературы.

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

Пусть F - множество F-и MV-зависимостей над U. Схема отношения R находится в 4НФ относительно F, если для каждой MV-зависимости X –» Y, выводимой из F, и XYR - либо MV-зависимость тривиальна, либо X - суперключ для R. Схема БД R находится в 4НФ, если каждая входящая в нее схема отношения находится в 4НФ относительно F.

MV-зависимость X –» Y называется тривиальной для схемы R, содержащей XY, если любое отношение r(R) удовлетворяет X –» Y.

Пример 4.6. Отношение СБЫТ (табл. 4.1)

Таблица 4.1.

Отношение СБЫТ

Завод Товар Магазин
z1
z1
z1
z1
z2
t1
t1
t2
t2
t2
m1
m2
m1
m2
m2
удовлетворяет требованиям MV-зависимостей и может быть представлено в виде 4НФ: каждая из подсхем

Таблица 4.2.

Производство

Завод Товар
z1
z1
z2
t1
t2
t2

 

Таблица 4.3.

Снабжение

Завод Магазин
z1
z1
z2
m1
m2
m2
находится в 4НФ. Здесь возможна и другая трактовка (рис. 4.7):Рис. 04.07. Промежуточный ключ отношение М:М заменяется двумя отношениями 1:М с помощью промежуточного ключа, которым оказывается поле ЗАВОД. Нетрудно видеть, что схема табл. 4.1 обладает свойством соединения (табл. 4.2 и табл. 4.3) без потерь. Фактически отношение СБЫТ находится в 5НФ.

В то же время отношение СБЫТ1 (табл. 4.4)

Таблица 4.4.

Отношение СБЫТ1

Завод Товар Магазин
z1
z1
z1
z2

t1
t1
t2
t2

m1
m2
m1
m2
не отвечает требованиям MV-зависимостей и не может быть разложено на схемы Производство и Снабжение, поскольку, как легко видеть, из них при соединении не восстанавливается схема СБЫТ1.

Отношение находится в 5НФ ссылка на источники литературы, если его полная декомпозиция содержит во всех проекциях ключ-кандидат. Иными словами, отношение R разлагается на несколько схем, каждая из которых находится в 4НФ.

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

Ограничения целостности. Выделяют две группы ограничений.

I. В процессе проектирования:

    1) при получении достоверных данных из источников;

    2) при построении структуры;

    3) при заполнении БД данными (в том числе ссылочная целостность).

II. При эксплуатации:

    1) машинные сбои;

    2) ошибки оператора.

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

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

    1) ограничение сбора;

    2) правильность содержания;

    3) ясность целей;

    4) ограничение целей;

    5) гласность;

    6) индивидуальное участие;

    7) ответственность.

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

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

Использование реляционного исчисления (в СУБД FoxPro 3.0, Access) позволяет применять объектно-ориентированный подход и декларативный язык и задавать с помощью СУБД при формировании структуры триггеры (в качестве условий), уникальность ключей, связи таблиц (на их схеме) с помощью мыши. Может быть непосредственно использован язык SQL.

Защита. Управление доступом противодействует несанкционированному доступу в цепочке субъект - данные - процедуры.

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

Этот способ прост, но для БД недостаточно удобен, поскольку пароли все же можно и узнать.

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

Этот метод тоже недостаточно гибок.

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

4.3.
Использование БД

4.3.1.
Запросы к данным

Запросы, как показано ранее (§ 4.1), могут быть описаны на языках Алгебра реляционнаяреляционной алгебры и Исчисление реляционноереляционного исчисления.

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

  1. Селекция выполняется как можно раньше.

  2. Сортировка файлов или создание индексов путем соединения декартова произведения с последующей селекцией.

  3. Предварительное вычисление общих выражений.

  4. Выполнение селекции и проекции за один просмотр.

  5. Комбинирование проекции с предшествующими или последующими операциями.

  6. Объединение селекции с предшествующим декартовым произведением.

Алгоритмически это может быть представлено в таком виде.

Шаг 1. Селекцию SF1 ...SFn (E) представить как каскад селекций

SF1 (...(SFn (E))) - закон I.4 (§ 4.1).

Шаг 2. Переместить любую селекцию в дереве как можно ниже - законы I.4, IY.1, IY.3, IY.5.

Шаг 3. Переместить любую проекцию в низ дерева - законы I.2, IY.5, IY.6.

Шаг 4. Скомбинировать любой каскад селекций (проекций) в одиночную селекцию (проекцию) I.1, I.2, I.5 или селекцию с последующей проекцией.

Шаг 5. Разбить внутренние узлы дерева на группы: объединить двухместные операции с предшествующими или последующим узлу унарными операциями S и P.

Шаг 6. Перейти к более высокому уровню иерархии.

Пример оптимизации. Пусть дана ссылка на источники литературы база данных Библиотека:

КН[ИГИ](Название[_книги], Автор, Название-издательства, N_бк),

ИЗД[АТЕЛИ](Название_издательства, Место, Адрес_издательства),

ЧИТ[АТЕЛИ](Фамилия, Адрес, Город, N_форм[уляра]),

ВЫД[АЧИ](N_форм[уляра], N_бк, Дата), где бк - библиотечный каталог, а для обозначения таблиц и полей используем сокращения (без букв в квадратных скобках).

Запрос: найти, у кого находятся книги, выданные до 01.01.1997.Д

Ему соответствует на языке АЛЬФА запрос (рис. 4.8, а)Рис. 04.08. а) Дерево запроса

pНАЗВАНИЕ sДАТА J1.1.1997 pS (SF (ВЫД, ЧИТ, КН)),

где F = ЧИТ.N_форм = ВЫД.N_формКН.N_бк = ВЫД.N_бк,

S = Название_книги, Автор, Название_издательства, N_бк, Фамилия, Адрес, Город,ДN_форм, Дата).

На рис. 4.8, а в условии F разделяют две селекции и перемещают как можно ниже в дереве. Селекция

sДАТА≤1.1.1997 (4.2)

ниже проекции и двух селекций по законам I.1, I.5.

Селекция (4.2) применяется к произведению (ВЫД×ЧИТ)×КН. Дата - единственный атрибут отношения ВЫД потому

sДАТА≤1.1.1997 ((ВЫД×ЧИТ)×КН)

на

(sДАТА≤1.1.1997 (ВЫД×ЧИТ))×КН

и

((sДАТА≤1.1.1997 (ВЫД))×ЧИТ)×КН.

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

sЧИТ.N_ФОРМ = sВЫД.N_ФОРМ может быть перемещена ниже и применена к произведению

sДАТА≤1.1.1997 ((ВЫД)×ЧИТ).

ВЫД.N_форм есть имя атрибута отношения, полученного в sДАТА≤1.1.1997 (ВЫД), ибо это атрибут отношения ВЫД.

По закону I.2 две проекции комбинируются в одну pНАЗВАНИЕ и результат отражается в рис. 4.8, б.Рис. 04.08. б) Дерево запроса

По закону I.4 pНАЗВАНИЕ и sкн.N_бк=выд.N_бк заменим на каскад

pНАЗВАНИЕ ,

sкн.N_бк=выд.N_бк ,

pназвание кн.N_бк, выд.N_бк . (4.3)

По закону IY.6 выражение (4.3) заменяется на pназвание кн.N_бк , примененное к отношению КН, и

pвыд.N_бк , (4.4)

примененное к левому оператору декартова произведения более высокого уровня (рис. 4.8, б).Рис. 04.08. б) Дерево запроса

Последняя проекция (4.4) взаимодействует с нижней селекцией по закону I.4 и получается каскад:

pвыд.N_бк ,

sчит.N_форм=выд.N_форм ,

pвыд.N_бк, чит.N_форм, выд.N_форм . (4.5)

Проекция (4.5) «просеивается» через декартово произведение по закону IY.6 и частично - через sДАТА≤1.1.1997 (ВЫД) по закону I.4. Кроме того, проекция pвыд.N_бк, выд.N_форм, дата - излишняя (это - все атрибуты ВЫД) и исключается. Тогда окончательный результат принимает вид рис. 4.9,Рис. 04.09. Преобразованное дерево запроса на котором группы операторов обведены пунктирными линиями. Любое из декартовых произведений является фактически эквисоединением, если его скомбинировать с селекцией, находящейся в дереве выше. Иными словами, селекция для ВЫД и проекция для ЧИТ могут быть скомбинированы в группы I и II, при этом сначала выполняются операции группы I, а затем - группы II.

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

Если принять в качестве критерия минимум соединений и декартовых произведений [ссылка на источники литературы c. 204], то для класса так называемых конъюнктивных запросов возможно провести однозначную оптимизацию.

4.3.2.
Синхронизация процессов доступа

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

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

Первоначально поговорим об однопользовательском режиме.

Под Транзакциятранзакцией понимается:

    1) входное сообщение, передаваемое в систему и отражающее некоторое реальное событие в компьютере (БД);

    2) процесс изменения в БД, вызванный передачей одного входного сообщения.

К транзакции преддъявляются следующие основные требования:

    1) она выполняется полностью или не выполняется совсем;

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

    3) транзакция должна быть воспроизводима: при воспроизводстве блокировку необходимо осуществлять до момента просмотра всех объектов.

Возможна двухфазная и трехфазная схема транзакции. Последняя болеe сложная и применяется в ограниченном объеме (например, в системе управления распределенной БД SDD-1) и будет рассмотрена позднее. Сейчас же поговорим о широко применяемой двухфазной схеме транзакции.

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

  2. По системному журналу транзакций происходит выполнение или возврат в прежнее положение (откат) в точки фиксации (точки контроля) - рис. 4.10.Рис. 04.10. Действие транзакций

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

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

Для любой транзакции ТР возможны две группы действий:

    1) изменение состояния (запись) - R;

    2) считывание (чтение) состояния - W.

Для двух взаимодействующих транзакций ТР1 и ТР2 возможны следующие случаи.

  1. Одновременное изменение ТР1 и ТР2 , при этом возможны наложение данных (потеря обновления) или ошибка в первой транзакции (взаимозависимость восстановления).

  2. Изменение R1 и считывание W2 с двумя возможными последствиями:

    а) изменение с помощью ТР1 значения, считываемого ТР2 (воспроизводимость считывания);

    б) откат перед окончанием работы ТР1 (поскольку нет изменений в ТР2 ) и возврат ТР1 в прежнее состояние.

  3. Чтение ТР1 и изменение ТР2 (нет гарантии воспроизводимости).

Для устранения этих нежелательных явлений возможны такие способы управления.

  1. Блокировка монопольная или согласованная.

  2. Отложенные изменения.

  3. Привязка по меткам времени работы компьютера (временная привязка) и трехфазная схема транзакции.

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

Блокировка выполняется только для одной транзакции и одного объекта.

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

  1. Перед обработкой объекта должна быть выполнена его блокировка.

  2. После обработки объект должен быть разблокирован.

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

  4. Неблокированный объект не должен освобождаться.

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

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

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

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

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

    в) рестарты с приоритетом по времени.

При использовании согласованных блокировок возможно:

    1) предупреждение о блокировке для всей области;

    2) блокировка части области, связанной с данной транзакцией.

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

© Центр дистанционного образования МГУП