Нормальная форма Бойса-Кодда (НФБК)


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

    Таблица 13
    Таблица 13 НОМЕР ЗАРПЛАТА 1 1000 2 1000 Таблица 12 Отношение По данным проекциям, имеющие общий атрибут "НОМЕР", исходное отношение восстанавливается в точном виде. Тем не менее, нельзя сказать, ч...
    Таблица 14
    Таблица 14 НОМЕР ФАМИЛИЯ ЗАРПЛАТА 1 Иванов 1000 2 Петров 1000 2 Сидоров 2000 Таблица 13 Отношение Кажется, что этого не может быть, т.к. значения в атрибуте "НОМЕР" повторяются. Но мы же ничего не...
    Таблица 15
    Таблица 15 НОМЕР ФАМИЛИЯ 1 Иванов 2 Петров 2 Сидоров Таблица 14 Отношение...
    Таблица 16
    Таблица 16 НОМЕР ЗАРПЛАТА 1 1000 2 1000 2 2000 Таблица 15 Отношение Естественное соединение этих проекций будет содержать лишние кортежи:...
    Таблица 17
    Таблица 17 НОМЕР ФАМИЛИЯ ЗАРПЛАТА 1 Иванов 1000 2 Петров 1000 2 Петров 2000 2 Сидоров 1000 2 Сидоров 2000 Таблица 16 Отношение Вывод . Таким образом, без дополнительных ограничений на отношение не...
    Теорема (хеза)
    Теорема (Хеза) . Пусть является отношением, и - атрибуты или множества атрибутов этого отношения. Если имеется функциональная зависимость , то проекции и образуют декомпозицию без потерь. Доказате...
    Теорема доказана
    Теорема доказана . Замечание . В доказательстве теоремы Хеза наличие функциональной зависимости не использовалось при доказательстве включения . Это означает, что при выполнении декомпозиции и пос...
    Выводы
    Выводы При разработке базы данных можно выделить несколько уровней моделирования: Сама предметная область Модель предметной области Логическая модель данных Физическая модель данных Собственно баз...
    Глава 7. Нормальные формы более высоких порядков
    Глава 7. Нормальные формы более высоких порядков В предыдущей главе были рассмотрены нормальные формы вплоть до третьей нормальной формы (3НФ). В большинстве случаев этого вполне достаточно, чтобы...
    Нфбк (нормальная форма бойса-кодда)
    НФБК (Нормальная Форма Бойса-Кодда) При приведении отношений при помощи алгоритма нормализации к отношениям в 3НФ неявно предполагалось, что все отношения содержат один потенциальный ключ. Это не...
    Пример 1
    Пример 1 . Пусть требуется хранить данные о поставках деталей некоторыми поставщиками. Предположим, что наименования поставщиков являются уникальными. Кроме того, каждый поставщик имеет свой уника...
    Таблица 1
    Таблица 1 Номер поставщика PNUMНаименование поставщика PNAMEНомер детали DNUMПоставляемое количество VOLUME 1 Фирма 1 1 100 1 Фирма 1 2 200 1 Фирма 1 3 300 2 Фирма 2 1 150 2 Фирма 2 2 250 3 Фирма...
    Таблица 2
    Таблица 2 Номер поставщика PNUM Наименование поставщика PNAME 1 Фирма 1 2 Фирма 2 3 Фирма 3 Таблица 2 Отношение "Поставщики"...
    Таблица 3


    Таблица 3 Номер поставщика PNUMНомер детали DNUMПоставляемое количество VOLUME 1 1 100 1 2 200 1 3 300 2 1 150 2 2 250 3 1 1000 Таблица 3 Отношение "Поставки-2"...
    Определение 1
    Определение 1 . Отношение находится в нормальной форме Бойса-Кодда ( НФБК ) тогда и только тогда, когда детерминанты всех функциональных зависимостей являются потенциальными ключами . Замечание ....
    Таблица 4
    Таблица 4 Номер поставщика PNUMНаименование поставщика PNAME 1 Фирма 1 2 Фирма 2 3 Фирма 3 Таблица 4 Отношение "Поставщики"...
    Таблица 5
    Таблица 5 Наименование поставщика PNAMEНомер детали DNUMПоставляемое количество VOLUME Фирма 1 1 100 Фирма 1 2 200 Фирма 1 3 300 Фирма 2 1 150 Фирма 2 2 250 Фирма 3 1 1000 Таблица 5 Отношение "Пос...
    Пример 2
    Пример 2 . Предположим, что нам по-прежнему необходимо учитывать поставки, но каждый акт поставки должен иметь некоторый уникальный номер (назовем его "сквозной номер поставки"). Отношение может и...
    Таблица 6
    Таблица 6 Номер поставщика PNUMНомер детали DNUMПоставляемое количество VOLUMEСквозной номер поставки NN 1 1 100 1 1 2 200 2 1 3 300 3 2 1 150 4 2 2 250 5 3 1 1000 6 4нф (четвертая нормальная форма)
    4НФ (Четвертая Нормальная Форма) Рассмотрим следующий пример. Пусть требуется учитывать данные об абитуриентах, поступающих в ВУЗ. При анализе предметной области были выделены следующие требования...
    Таблица 7
    Таблица 7 Абитуриент Факультет Предмет Иванов Математический Математика Иванов Математический Информатика Иванов Физический Математика Иванов Физический Физика Петров Математический Математика Пет...
    Таблица 8
    Таблица 8 Номер АбитуриентаНомер ФакультетаНомер Предмета 1 1 1 1 1 2 1 2 1 1 2 3 2 1 1 2 1 2 Таблица 8 Модифицированное отношение "Абитуриенты-Факультеты-Предметы"...
    Таблица 9
    Таблица 9 Номер Абитуриента Абитуриент 1 Иванов 2 Петров Таблица 9 Отношение "Абитуриенты"...
    Таблица 10
    Таблица 10 Номер Факультета Факультет 1 Математический 2 Физический Таблица 10 Отношение "Факультеты"...
    Таблица 11
    Таблица 11 Номер ПредметаПредмет 1 Математика 2 Информатика 3 Физика Таблица 11 Отношение "Предметы" Теперь каждое наименование встречается только в одном месте. И все-таки как в исходном, так и в...
    Определение 2
    Определение 2 . Пусть - отношение, и , , - некоторые из его атрибутов (или непересекающиеся множества атрибутов). Тогда атрибуты (множества атрибутов) и многозначно зависят от (обозначается ), тог...
    Определение 3
    Определение 3 . Многозначная зависимость называется нетривиальной многозначной зависимостью , если не существует функциональных зависимостей и . В отношении "Абитуриенты-Факультеты-Предметы" имеет...
    Теорема (фейджина)
    Теорема (Фейджина) . Пусть , , - непересекающиеся множества атрибутов отношения . Декомпозиция отношения на проекции и будет декомпозицией без потерь тогда и только тогда, когда имеется многозначн...
    Определение 4
    Определение 4 . Отношение находится в четвертой нормальной форме ( 4НФ ) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей . Отношение "А...
    Таблица 12
    Таблица 12 Факультет Абитуриент Математический Иванов Физический Иванов Математический Петров Таблица 12 Отношение "Факультеты-Абитуриенты"...
    Таблица 13
    Таблица 13 Факультет Предмет Математический Математика Математический Информатика Физический Математика Физический Физика Таблица 13 Отношение "Факультеты-Предметы" В полученных отношениях устране...
    5нф (пятая нормальная форма)
    5НФ (Пятая Нормальная Форма) Функциональные и многозначные зависимости позволяют произвести декомпозицию исходного отношения без потерь на две проекции. Можно, однако, привести примеры отношений,...
    Пример 3
    Пример 3 . Рассмотрим следующее отношение :...
    Таблица 14
    Таблица 14 X Y Z 1 1 2 1 2 1 2 1 1 1 1 1 Таблица 14 Отношение R Всевозможные проекции отношения , включающие по два атрибута, имеют вид:...
    Таблица 15
    Таблица 15 X Y 1 1 1 2 2 1 Таблица 15 Проекция R1=R[X,Y]...
    Таблица 16
    Таблица 16 X Z 1 2 1 1 2 1 Таблица 16 Проекция R2=R[X,Z]...
    Таблица 17
    Таблица 17 Y Z 1 2 2 1 1 1 Таблица 17 Проекция R3=R[Y,Z] Как легко заметить, отношение не восстанавливается ни по одному из попарных соединений , или . Действительно, соединение имеет вид:...
    Таблица 18
    Таблица 18 X Y Z 1 1 2 1 1 1 1 2 2 1 2 1 2 1 1 Таблица 18 R1 JOIN R2 Серым цветом выделен лишний кортеж, отсутствующий в отношении . Аналогично (в силу соображений симметрии) и другие попарные сое...
    Определение 5
    Определение 5 . Пусть является отношением, а , , …, - произвольными (возможно пересекающимися) подмножествами множества атрибутов отношения . Тогда отношение удовлетворяет зависимости соединения т...
    Теорема фейджина (другая формулировка)
    Теорема Фейджина (другая формулировка) . Отношение удовлетворяет зависимости соединения тогда и только тогда, когда имеется многозначная зависимость . Т.к. теорема Фейджина является взаимно обратн...
    Определение 6
    Определение 6 . Зависимость соединения называется нетривиальной зависимостью соединения , если выполняется два условия: Одно из множеств атрибутов не содержит потенциального ключа отношения . Ни о...
    Определение 7
    Определение 7 . Зависимость соединения называется тривиальной зависимостью соединения , если выполняется одно из условий: Либо все множества атрибутов содержат потенциальный ключ отношения . Либо...
    Определение 8
    Определение 8 . Отношение находится в пятой нормальной форме ( 5НФ ) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной . Определения 5НФ может стать более пон...
    Определение 9
    Определение 9 . Отношение не находится в 5НФ , если в отношении найдется нетривиальная зависимость соединения . Возвращаясь к примеру 3, становится понятно, что не зная ничего о том, какие потенци...
    Продолжение алгоритма нормализации (приведение к 5нф)
    Продолжение алгоритма нормализации (приведение к 5НФ) В предыдущей главе был описан алгоритм нормализации как алгоритм приведения отношений к 3НФ. Теперь мы можем продолжить этот алгоритм, доведя...
    Шаг 4 (приведение к нфбк)
    Шаг 4 (Приведение к НФБК) . Если имеются отношения, содержащие несколько потенциальных ключей, то необходимо проверить, имеются ли функциональные зависимости, детерминанты которых не являются поте...
    Шаг 5 (приведение к 4нф)
    Шаг 5 (Приведение к 4НФ) . Если в отношениях обнаружены нетривиальные многозначные зависимости, то необходимо провести декомпозицию для исключения таких зависимостей....
    Шаг 5 (приведение к 5нф)
    Шаг 5 (Приведение к 5НФ) . Если в отношениях обнаружены нетривиальные зависимости соединения, то необходимо провести декомпозицию для исключения и таких зависимостей....
    Выводы
    Выводы Обобщением 3НФ на случай, когда отношение имеет более одного потенциального ключа, является нормальная форма Бойса-Кодда. Отношение находится в нормальной форме Бойса-Кодда ( НФБК ) тогда и...
    Глава 8. Элементы модели "сущность-связь"
    Глава 8. Элементы модели "сущность-связь" Моделирование структуры базы данных при помощи алгоритма нормализации, описанного в предыдущих главах, имеет серьезные недостатки: Первоначальное размещен...
    Определение 1
    Определение 1 . Сущность - это класс однотипных объектов, информация о которых должна быть учтена в модели. Каждая сущность должна иметь наименование, выраженное существительным в единственном чис...
    Примерами сущностей могут быть...
    Примерами сущностей могут быть такие классы объектов как "Поставщик", "Сотрудник", "Накладная". Каждая сущность в модели изображается в виде прямоугольника с наименованием: Рис. 1...
    Определение 2
    Определение 2 . Экземпляр сущности - это конкретный представитель данной сущности. Например, представителем сущности "Сотрудник" может быть "Сотрудник Иванов". Экземпляры сущностей должны быть раз...
    Определение 3
    Определение 3 . Атрибут сущности - это именованная характеристика, являющаяся некоторым свойством сущности. Наименование атрибута должно быть выражено существительным в единственном числе (возможн...
    Примерами атрибутов сущности "сотрудник"...
    Примерами атрибутов сущности "Сотрудник" могут быть такие атрибуты как "Табельный номер", "Фамилия", "Имя", "Отчество", "Должность", "Зарплата" и т.п. Атрибуты изображаются в пределах прямоугольни...
    Определение 4
    Определение 4 . Ключ сущности - это неизбыточный набор атрибутов, значения которых в совокупности являются уникальными для каждого экземпляра сущности. Неизбыточность заключается в том, что удален...
    Определение 5
    Определение 5 . Связь - это некоторая ассоциация между двумя сущностями. Одна сущность может быть связана с другой сущностью или сама с собою. Связи позволяют по одной сущности находить другие сущ...
    Пример разработки простой er-модели...
    Задав дополнительные вопросы менеджеру, мы выяснили, что фирма имеет несколько складов. Причем, каждый товар может храниться на нескольких складах и быть проданным с любого склада. Куда поместить...
    Концептуальные и физические er-модели
    Концептуальные и физические ER-модели Разработанный выше пример ER-диаграммы является примером концептуальной диаграммы . Это означает, что диаграмма не учитывает особенности конкретной СУБД. По д...
    Выводы
    Выводы Реальным средством моделирования данных является не формальный метод нормализации отношений, а так называемое семантическое моделирование . В качестве инструмента семантического моделирован...
    Глава 9. Транзакции и целостность баз данных
    Глава 9. Транзакции и целостность баз данных В данной и в последующих главах изучается фундаментальное понятие транзакции. Это понятие не входит в реляционную модель данных, т.к. транзакции рассма...
    Пример нарушения целостности базы...
    . Пусть имеется система, в которой хранятся данные о подразделениях и работающих в них сотрудниках. Список подразделений хранится в таблице DEPART(Dep_Id, Dep_Name, Dept_Kol), где Dept_Id - иденти...
    Таблица 1
    Таблица 1 Dept_Id Dept_Name Dept_Kol 1 Кафедра алгебры 3 2 Кафедра программирования 2 Таблица 1 DEPART...
    Таблица 2
    Таблица 2 Pers_Id Pers_Name Dept_Id 1 Иванов 1 2 Петров 2 3 Сидоров 1 4 Пушников 2 5 Шарипов 1 Таблица 2 PERSON Ограничение целостности этой базы данных состоит в том, что поле Dept_Kol не может з...
    Шаг 1. Вставить сотрудника в таблицу...
    Шаг 1. Вставить сотрудника в таблицу PERSON: INSERT INTO PERSON (6, Муфтахов, 1) Шаг 2. Увеличить значение поля Dept_Kol: UPDATE DEPART SET Dept=Dept+1 WHERE Dept_Id=1 Если после выполнения первой...
    Понятие транзакции определение 1
    Определение 1 . Транзакция - это последовательность операторов манипулирования данными, выполняющаяся как единое целое (все или ничего) и переводящая базу данных из одного целостного состояния в д...
    Ограничения целостности
    Ограничения целостности Свойство (С) - согласованность транзакций определяется наличием понятия согласованности базы данных....
    Определение 2
    Определение 2 . Ограничение целостности - это некоторое утверждение, которое может быть истинным или ложным в зависимости от состояния базы данных....
    Примерами ограничений целостности могут служить следующие утверждения: пример 2
    Примерами ограничений целостности могут служить следующие утверждения: Пример 2 . Возраст сотрудника не может быть меньше 18 и больше 65 лет....
    Пример 3
    Пример 3 . Каждый сотрудник имеет уникальный табельный номер....
    Пример 4
    Пример 4 . Сотрудник обязан числиться в одном отделе....
    Пример 5
    Пример 5 . Сумма накладной обязана равняться сумме произведений цен товаров на количество товаров для всех товаров, входящих в накладную. Как видно из этих примеров, некоторые из ограничений целос...
    Пример 3 представляет ограничение...
    Пример 3 представляет ограничение, реализующее целостность сущности. Пример 4 представляет ограничение, реализующее ссылочную целостность. Другие ограничения являются достаточно произвольными утве...
    Определение 3. База данных находится в согласованном (целостном) состоянии
    , если выполнены (удовлетворены) все ограничения целостности, определенные для базы данных. В данном определении важно подчеркнуть, что должны быть выполнены не все вообще ограничения предметной о...
    Классификация ограничений целостности
    Классификация ограничений целостности Ограничения целостности можно классифицировать несколькими способами: По способам реализации. По времени проверки. По области действия....
    Классификация ограничений целостности по способам реализации
    Классификация ограничений целостности по способам реализации Каждая система обладает своими средствами поддержки ограничений целостности. Различают два способа реализации: Декларативная поддержка...
    Определение 4
    Определение 4 . Декларативная поддержка ограничений целостности заключается в определении ограничений средствами языка определения данных (DDL - Data Definition Language). Обычно средства декларат...
    Определение 5
    Определение 5 . Процедурная поддержка ограничений целостности заключается в использовании триггеров и хранимых процедур. Не все ограничения целостности можно реализовать декларативно....
    Примером такого ограничения может...
    Примером такого ограничения может служить требование из примера 1, утверждающее, что поле Dept_Kol таблицы DEPART должно содержать количество сотрудников, реально числящихся в подразделении. Для р...
    Классификация ограничений целостности...
    Определение 6 . Немедленно проверяемые ограничения проверяются непосредственно в момент выполнения операции, могущей нарушить ограничение. Например, проверка уникальности потенциального ключа пров...
    Определение 7
    Определение 7 . Ограничения с отложенной проверкой проверяется в момент фиксации транзакции оператором COMMIT WORK. Внутри транзакции ограничение может не выполняться. Если в момент фиксации транз...
    Примером ограничения, которое...
    Примером ограничения, которое не может быть проверено немедленно является ограничение из примера 1. Это происходит оттого, что транзакция, заключающаяся во вставке нового сотрудника в таблицу PERS...
    Классификация ограничений целостности...
    Ограничения домена...
    Определение 8
    Определение 8 . Ограничения целостности домена представляют собой ограничения, накладываемые только на допустимые значения домена. Фактически, ограничения домена обязаны являться частью определени...
    Определение 9
    Определение 9 . Ограничение целостности атрибута представляют собой ограничения, накладываемые на допустимые значения атрибута вследствие того, что атрибут основан на каком-либо домене. Ограничени...
    Определение 10
    Определение 10 . Ограничения целостности кортежа представляют собой ограничения, накладываемые на допустимые значения отдельного кортежа отношения, и не являющиеся ограничением целостности атрибут...
    Пример 6
    Пример 6 . Атрибут "Возраст сотрудника" в таблице "Спецподразделение", может иметь дополнительное ограничение "Возраст сотрудника не менее 25 и не более 45", помимо того, что этот атрибут уже имее...
    Пример 7
    Пример 7 . Для отношения "Сотрудники" можно сформулировать следующее ограничение: если атрибут "Должность" принимает значение "Директор", то атрибут "Зарплата" содержит значение не менее 1000$. Эт...
    Пример 8
    Пример 8 . В накладной можно установить следующую взаимосвязь атрибутов - "Цена*Количество=Сумма", связывающую атрибуты "Цена", "Количество", "Сумма". Данный пример кажется неестественным, т.к. су...
    Таблица 3
    Таблица 3 Наиме-нование атрибута Описание атрибута Базовый ли атрибут Формула для вычислимого атрибута Name Наименование товара Да N Количество Да P1 Учетная цена товара Да S1 Учетная сумма на все...
    Определение 11
    Определение 11 . Ограничения целостности отношения представляют ограничения, накладываемые только на допустимые значения отдельного отношения, и не являющиеся ограничением целостности кортежа. Тре...
    Пример 9
    Пример 9 . Ограничение целостности сущности (см. гл. 3), задаваемое потенциальным ключом отношения, является ограничением отношения, т.к. для его проверки необходимо иметь информацию обо всех корт...
    Пример 10
    Пример 10 . Ограничение целостности, определяемые наличием функциональных, многозначных зависимостей и зависимостей соединения, являются ограничениями отношения....
    Пример 11
    Пример 11 . Предположим, что в отношении PERSON (см. пример 1) задано следующее ограничение - в каждом отделе должно быть не менее двух сотрудников. Это ограничение можно сформулировать так - коли...
    Пример 12
    Пример 12 . Ограничение целостности, определяемое требованием, что некоторая таблица должна быть не пуста, являются ограничениями отношения. Проверка ограничения . К моменту проверки ограничения о...
    Определение 12
    Определение 12 . Ограничения целостности базы данных представляют ограничения, накладываемые на значения двух или более связанных между собой отношений (в том числе отношение может быть связано са...
    Пример 13
    Пример 13 . Ограничение целостности ссылок (см. гл. 3), задаваемое внешним ключом отношения, является ограничением базы данных....
    Пример 14
    Пример 14 . Ограничение на таблицы DEPART и PERSON из примера 1 является отношением базы данных, т.к. оно связывает данные, размещенные в различных таблицах. Проверка ограничения . К моменту прове...
    Общие принципы реализации ограничений средствами sql
    Общие принципы реализации ограничений средствами SQL Стандарт SQL не предусматривает процедурных ограничений целостности, реализуемых при помощи триггеров и хранимых процедур. В стандарте SQL 92 о...
    Синтаксис ограничений стандарта sql
    Синтаксис ограничений стандарта SQL Понятие ограничения используется во многих операторах определения данных (DDL). Ограничение check ::= CHECK Предикат Ограничения таблицы ::= [ CONSTRAINT Имя ог...
    Примеры предикатов различного...
    Примеры предикатов различного вида приведены в главе 5. Ограничение типа CHECK может быть использовано как часть описания домена, таблицы, столбца таблицы или отдельного ограничения целостности -...
    Пример ограничения типа check...
    Пример ограничения типа CHECK: CHECK (Salespeaple.Salary IS NOT NULL) OR (Salespeaple.Commission IS NOT NULL) Данное ограничение утверждает, что каждый продавец должен иметь либо ненулевую зарплат...
    Таблица 4
    Таблица 4 X Y 1 Aa 1 Bb 2 Cc 2 Dd 3 Ee 3 Ff Таблица 4 таблица A (Родительская)...
    Таблица 5
    Таблица 5 Z X Y 1 1 Aa 2 1 Null 3 Null Cc 4 Null Null 5 4 Gg Таблица 5 Таблица B (Дочерняя) Таблица A имеет первичный ключ (X, Y). Таблица B имеет первичный ключ Z, и внешний ключ (X, Y), ссылающи...
    Таблица 6
    Таблица 6 Колонки X и Y таблицы B допускают null-значения Колонки X и Y таблицы B не допускают null-значений MATCH отсутствует 1 строка - допустима, совпадает с 1 строкой таблицы A. 2 строка - доп...
    Синтаксис операторов sql, использующих ограничения
    Синтаксис операторов SQL, использующих ограничения Стандарт SQL описывает следующие операторы, в которых может быть использованы ограничения: CREATE DOMAIN - создать домен ALTER DOMAIN - изменить...
    Пример 18
    Пример 18 . Приведенный ниже оператор создает домен Salary на основе целочисленного типа данных, причем значения из этого домена не могут принимать неположительные значения (но могут принимать зна...
    Определение столбца
    Определение столбца ::= Имя столбца { Имя домена | Тип данных [ Размер ]} [ Ограничение столбца… ] [ DEFAULT Значение по умолчанию ] Этот оператор (синтаксис приведен не полностью - пропущены опци...
    Пример 19
    Пример 19 . CREATE TABLE Salespeaple (Salespeaple_Id Id_Nums PRIMARY KEY, Fam CHAR(20) NOT NULL, Im CHAR(15), BirthDate DATE, Salary Salary_Domain DEFAULT 1000, City_Id INTEGER REFERENCES City ON...
    Определение столбца
    Определение столбца } | { ALTER [ COLUMN ] Имя столбца { SET DEFAULT Значение по умолчанию | DROP DEFAULT }} | { DROP [ COLUMN ] Имя столбца RESTRICT | CASCADE } | { ADD Ограничение таблицы } | {...
    Пример 20
    Пример 20 .CREATE ASSERTION Check_Pay CHECK (Salespeaple.Salary IS NOT NULL) OR (Salespeaple.Commission IS NOT NULL) DEFERRABLE INITIALLY IMMEDIATE DROP ASSERTION Имя утверждения Этот оператор поз...
    Выводы
    Выводы Транзакция - это неделимая, с точки зрения воздействия на СУБД, последовательность операций манипулирования данными, выполняющаяся по принципу " все или ничего ", и переводящая базу данных...
    Глава 10. Транзакции и параллелизм
    Глава 10. Транзакции и параллелизм В данной главе изучаются возможности параллельного выполнения транзакций несколькими пользователями, т.е. свойство (И) - изолированность транзакций. Современные...
    Работа транзакций в смеси
    Работа транзакций в смеси Транзакция рассматривается как последовательность элементарных атомарных операций. Атомарность отдельной элементарной операции состоит в том, что СУБД гарантирует, что, с...
    Определение 1
    Определение 1 . Набор из нескольких транзакций, элементарные операции которых чередуются друг с другом, называется смесью транзакций ....
    Определение 2
    Определение 2 . Последовательность, в которой выполняются элементарные операции заданного набора транзакций, называется графиком запуска набора транзакций. Замечание . Очевидно, что для заданного...
    Проблемы параллельной работы транзакций
    Проблемы параллельной работы транзакций Каким образом транзакции различных пользователей могут мешать друг другу? Различают три основные проблемы параллелизма: Проблема потери результатов обновлен...
    Проблема потери результатов обновления
    Проблема потери результатов обновления Две транзакции по очереди записывают некоторые данные в одну и ту же строку и фиксируют изменения....
    Таблица 1
    Таблица 1 Транзакция A Время Транзакция B Чтение --- --- Чтение Запись --- ---
    Проблема незафиксированной зависимости (чтение "грязных" данных, неаккуратное считывание) Транзакция B изменяет данные в строке. После этого транзакция A читает измененные данные и работает с ними...
    Таблица 2
    Таблица 2 Транзакция AВремяТранзакция B --- Чтение --- Запись Чтение --- Работа с прочитанными данными
    Проблема несовместимого анализа Проблема несовместимого анализа включает несколько различных вариантов: Неповторяемое считывание . Фиктивные элементы ( фантомы ). Собственно несовместимый анализ ....
    Неповторяемое считывание
    Неповторяемое считывание Транзакция A дважды читает одну и ту же строку. Между этими чтениями вклинивается транзакция B, которая изменяет значения в строке....
    Таблица 3
    Таблица 3 Транзакция A Время Транзакция B Чтение --- --- Чтение --- Запись ---
    Фиктивные элементы (фантомы) Эффект фиктивных элементов несколько отличается от предыдущих транзакций тем, что здесь за один шаг выполняется достаточно много операций - чтение одновременно несколь...
    Таблица 4
    Таблица 4 Транзакция A Время Транзакция B Выборка строк, удовлетворяющих условию . (Отобрано n строк) --- --- Вставка новой строки, удовлетворяющей условию . --- Фиксация транзакции Выборка строк,...
    Собственно несовместимый анализ
    Собственно несовместимый анализ Эффект собственно несовместимого анализа также отличается от предыдущих примеров тем, что в смеси присутствуют две транзакции - одна длинная, другая короткая. Длинн...
    Таблица 5
    Таблица 5 Транзакция A Время Транзакция B Чтение счета и суммирование. --- --- Снятие денег со счета . ---
    Конфликты между транзакциями
    Конфликты между транзакциями Итак, анализ проблем параллелизма показывает, что если не предпринимать специальных мер, то при работе в смеси нарушается свойство (И) транзакций - изолированность. Тр...
    Определение 3
    Определение 3 . Транзакции называются конкурирующими , если они пересекаются по времени и обращаются к одним и тем же данным. В результате конкуренции за данными между транзакциями возникают конфл...
    Определение 4
    Определение 4 . График запуска набора транзакций называется последовательным , если транзакции выполняются строго по очереди, т.е. элементарные операции транзакций не чередуются друг с другом....
    Определение 5
    Определение 5 . Если график запуска набора транзакций содержит чередующиеся элементарные операции транзакций, то такой график называется чередующимся . При выполнении последовательного графика гар...
    Определение 6
    Определение 6 . Два графика называются эквивалентными , если при их выполнении будет получен один и тот же результат, независимо от начального состояния базы данных ....
    Определение 7
    Определение 7 . График запуска транзакции называется верным ( сериализуемым ), если он эквивалентен какому-либо последовательному графику. Замечание . При выполнении двух различных последовательны...
    Блокировки
    Блокировки Основная идея блокировок заключается в том, что если для выполнения некоторой транзакции необходимо, чтобы некоторый объект не изменялся без ведома этой транзакции, то этот объект долже...
    Таблица 6
    Таблица 6 Транзакция B пытается наложить блокировку: Транзакция A наложила блокировку: S-блокировку X-блокировку S-блокировку Да НЕТ (Конфликт R-W) X-блокировку НЕТ (Конфликт W-R)НЕТ (Конфликт W-W...
    Решение проблем параллелизма при помощи блокировок
    Решение проблем параллелизма при помощи блокировок Рассмотрим, как будут себя вести транзакции, вступающие в конфликт при доступе к данным, если они подчиняются протоколу доступа к данным....
    Проблема потери результатов обновления
    Проблема потери результатов обновления Две транзакции по очереди записывают некоторые данные в одну и ту же строку и фиксируют изменения....
    Таблица 7
    Таблица 7 Транзакция A Время Транзакция B S-блокировка - успешна --- Чтение --- --- S-блокировка - успешна --- Проблема незафиксированной зависимости (чтение "грязных" данных, неаккуратное считывание)
    Проблема незафиксированной зависимости (чтение "грязных" данных, неаккуратное считывание) Транзакция B изменяет данные в строке. После этого транзакция A читает измененные данные и работает с ними...
    Таблица 8
    Таблица 8 Транзакция A Время Транзакция B --- S-блокировка - успешна --- Чтение --- X-блокировка - успешна --- Неповторяемое считывание
    Неповторяемое считывание Транзакция A дважды читает одну и ту же строку. Между этими чтениями вклинивается транзакция B, которая изменяет значения в строке....
    Таблица 9
    Таблица 9 Транзакция A Время Транзакция B S-блокировка - успешна --- Чтение --- --- X-блокировка - отвергается --- Фиктивные элементы (фантомы)
    Фиктивные элементы (фантомы) Транзакция A дважды выполняет выборку строк с одним и тем же условием. Между выборками вклинивается транзакция B, которая добавляет новую строку, удовлетворяющую услов...
    Таблица 10
    Таблица 10 Транзакция A Время Транзакция B S-блокировка строк, удовлетворяющих условию . (Заблокировано n строк) --- Выборка строк, удовлетворяющих условию . (Отобрано n строк) --- --- Вставка нов...
    Собственно несовместимый анализ
    Собственно несовместимый анализ Длинная транзакция выполняет некоторый анализ по всей таблице, например, подсчитывает общую сумму денег на счетах клиентов банка для главного бухгалтера. Пусть на в...
    Таблица 11
    Таблица 11 Транзакция A Время Транзакция B S-блокировка счета - успешна --- Чтение счета и суммирование. --- --- X-блокировка счета
    Разрешение тупиковых ситуаций Итак, при использовании протокола доступа к данным с использованием блокировок часть проблем разрешилось (не все), но возникла новая проблема - тупики: Проблема потер...
    Таблица 12
    Таблица 12 Транзакция A Время Транзакция B Блокировка объекта - успешна --- --- Блокировка объекта -успешна Блокировка объекта - конфликтует с блокировкой, наложенной транзакцией B Преднамеренные блокировки
    Преднамеренные блокировки Как видно из анализа поведения транзакций, при использовании протокола доступа к данным не решается проблема фантомов. Это происходит оттого, что были рассмотрены только...



Содержание раздела