Эквивалентность
Подразделение
| Ном_подр | Тн_рук | Наим_подр |
| Адм.хох | ||
| План.эконом. | ||
| Реклама | ||
| Разработ | ||
| бухгалт |
Исполнитель
| Ном_исп | Имя_исп | Разряд | Ном_подр |
| Иванов | |||
| Козлов | |||
| Петров | |||
| гусев |
1.Сделать ограничение 2ой табл. По услов РАЗР=15 и получить на выходе 3табл.
| Иванов | |||
| Петров |
2.переименовать ном_подр в отношении 1 на ном_сект
3.соединить по условию ном_подр=ном_сект табл.5
| Ном_сект | Тн_рук | Наим_подр | Ном_исп | Имя_исп | Разр | Ном_подр |
| Рекл | Иванов | |||||
| Бухг | Петров |
4.проекция на ном_сект,тн_рук,наим_подр табл.6
3 2221 Рекл
7 6666 Бухг
5.соединить по условию тн-рук=ном_исп
3 2221 Рекл 2221 козлов 18 3
7 6666 Бухг 6666 Гусев 18 7
6.проекция на 1,3 и5
| Ном_подр | Наим_подр | Имя_исп |
| Рекл. | Козлов | |
| Бухг. | гусев |
Sql:
Select podr.nom_podr,podr.name_podr,isp.fam
From podr,isp
Where isp.razr=15
Механизм работы
Сотрудники Подразделение
 Ном_сотр
|
| Фам |
| Им |
| Отч |
| Ном_подр |
| Ном_подр |
| Назв_отд |
| телефон |
| Рук_отд |
SET RELATION TO N_OTD INTO PODR.dbf
USE PODR
INDEX ON N_PODR TO DEPART
BROWSE
SELECT 2
USE ISP
BROWSE
SET RELATION TO N_PODR INTO PODR.dbf
GO 3
SELECT 1
BROWSE
Эквивалентность реляционной алгебры и реляционного исчисления
Оба механизмы обладают одним важным свойством: они замкнуты относительно понятия отношения. Это означает, что выражения реляционной алгебры и формулы реляционного исчисления определяются над отношениями реляционных БД и результатом вычисления также являются отношения. В результате любое выражение или формула могут интерпретироваться как отношения, что позволяет использовать их в других выражениях или формулах.
Для любого допустимого выражения реляционной алгебры можно построить эквивалентную (т.е. производящую такой же результат) формулу реляционного исчисления и наоборот.
Все операции, выраженные реляционным исчислением, могут быть так же выражены реляционной алгеброй.
В реляционной модели реляционное исчисление альтернативно подходу основанному на алгебре. Можно сказать,что формулировка запроса в терминах исчисления носит описательный характер, а алгебраическая формулировка предписывающий. Иначе говоря алгебра имеет процедурный характер, а исчисления не процедурный.
СПЕЦ. РАЗРЯД=15=предикат
EXIST СПЕЦ (СПЕЦ.РАЗРЯД=15)
Транзакция.
Люб.бд является годной к использованию т.т.т. когда ее состояние соответствует состоянию предметн.области, такое состояние называется целостным. При переходе должно от 1 цлост.сост. к другому
Транзакция-атамарное действие над Б.Д., переводящее её из одного состояния в другое. ТР-последовательность операций, которые должны быть либо выполнены, либо нет. Метод контроля-ведение журнала(фиксация изменений) если во время обработки транзакции сбой-ТР откатывается.. Из журнала восстанавливается на момент начала транзакций. Начала может быть заданно явно Begin transaction.
Завершается:
1)успешно: все изменения внесены в Б.Д.
2)ошибочно: прерывает roll back(требуется откат).
Если работают 2 транзакции, то могут произойти коллизии. Грязное чтение - Т1 модифицировало некий элемент Б.Д. После этого Т2 прочитало этот элемент до окончания Т1. Если Т1 завершенна roll back, то получается, что Т2 прочитала несуществующие данные. Неповторяемое чтение -т1 прочитала содержимое элемента данных, после этого друг.т2 модфицировала или удалила это элемент Если Т1 прочитает содержимое, то оно получит новое значение или обнаружит, что элемент данных более не существует. Фантом-т1 прочитало содержимое нескольких элементов данных, удовлетворяющих некоторому условию после этого т2 создает элемент данных, удовлетворяющий этому условию и зафиксир., если т1 повторит чтение с тем же услов. Получит друг.набор данных.
5.во избежание коллизий возникло понятие сериализации-способы к упорядочиванию или параллельной обработке транзкаций
Сериализация – чередующееся выполнение множества транзакций будет верно, если их результат будет тот же, что и при последовательном выполнении транзакций.
Существуют два базовых подхода к сериализации транзакций - основанный на синхронизационных захватах объектов базы данных и на использовании временных меток. Суть обоих подходов состоит в обнаружении конфликтов транзакций и их устранении.
Для каждого из подходов имеются две разновидности - пессимистическая и оптимистическая. При применении пессимистических методов, ориентированных на ситуации, когда конфликты возникают часто, конфликты распознаются и разрешаются немедленно при их возникновении. Оптимистические методы основываются на том, что результаты всех операций модификации базы данных сохраняются в рабочей памяти транзакций. Реальная модификация базы данных производится только на стадии фиксации транзакции. Тогда же проверяется, не возникают ли конфликты с другими транзакциями.
Ограничимся рассмотрением более распространенных пессимистических разновидностей методов сериализации транзакций. Пессимистические методы сравнительно просто трансформируются в свои оптимистические варианты.
Принудительное упорядочивание транзакций обеспечив. С помощью мех.блок. или синх.захватов.
Механизм синхронизационных захватов или блокировок – если кортеж не изменяется непредсказуемо и без ведома Т, то он блокируется
Режимами сериализационных захватов является s-блокировка (по чтению) и x-блокировка (по записи). X-блокировка полностью закрывает доступ к запросам для этого элемента.
(при операциях изменения, добавления и удаления
1) Если ТР налагает на объ. Ч-блок. То люб.запрос друг. ТР с блок.этого объ.будет отвергнут
2) Если ТР налаг. Ы-блок.
А)запрос со стороны друг.ТР с ы-блок. Будет отвергнут
Б)запрос со стороны друг. ТР с ы-блок. На этот объ.будет приянт.
Существуют блокировки: 1) БД, 2) Таблицы, 3) Листа, 4) Кортежа, 5) Отдельного поля.
Мех синхр захват
(Если есть инфа по IS, IX, SIX захватам, прошу добавить).
Is верхний уровень six (is)
Самой большой проблемой захватов и блокировок являетсявозможность появления циклов. Это приводит к взаимной блокировке и тупику.
(Если не лево, то право, паутинкой накрест)
Захват может быть по одному объекту, а ожидание от многих.
Механизм временных меток - альтернативный метод сериализации транзакций.
Если T1 начался раньше T2, то система обеспечивает такой режим управления, как если бы T1 был целиком выполнен до T2.
Перед выполнением операций над объектом, проверяется, не закончился ли T, производившая действия над ним. Если нет, объект помечается и производится транзакция.
Если t(T) > t(T1), то есть T моложе T1, T получает новую временную метку, иначе – наоборот (?????).
К недостаткам можно отнести потенциально большее количество откатов, чем в случае синхронизационных захватов.
Вырабатываются глобальные метки (?????).
Гранулирован.
При применении этого подхода синх.захваты могут запрашиваться к объ.разн.уровня, файлам, отношениям, картежам, требуем уровням объектов определения, тем какая операция выполняется. Объ.захвата – отношение, а для выполнения удален.картежа-картеж. Объ.любого уровня м.б. захвачен в режиме s или х, ввод.спец протоколом гранулиров.захватов и нов.типы захватов. Перед захватом объ. В режиме s или х соотвествует более верхнему уровню должен быть захвачен в режиме is,ix,six. Примечание: при намеривания читать картежи из отношения R это отношение должно быть захвачено в режиме is, а до этого в таком же режиме должен быть захвачен файл. При намерении удалить картежи из отношения R это отношение должно быть захвачено в режиме ix (а до этого в таком же режиме должен быть захвачен и файл) при намерении удалить, если выполнить длинную(?) операцию просматривания картежей, то экономичнее всего захыватывать это отнощение в режиме six (и до этого файл в режиме is)
Предикатные
Несмотря на привлекательность гранулированного синхронизационного захвата он не решит проблему фантомов. Более привлекательными является механизм предикатных захватов, т.е. захватывается предикой (захватывается условие), которым удовлетворяют эти объекты. Проблема фантомов не возникает при использовании для синхронизации уровня отношений потому как отношение как логичный объект представляет собой неявные условия для входных в него кортежей. Захват отношения это простой и частный случай предикатного захвата. Поскольку любая операция над реляционной БД задается некоторым условием, т.е. в ней указывается неконкретный набор объектов БД над которым надо выполнять операцию, а условие которому должны удовлетворять объекты этого набора идеальным выбором было бы требовать синхронизационный захват в режиме S или X этого условия. Если посмотреть на общий вид условий например в SQL то становится абсолютно непонятно как определить совместимость 2-х предикатных захватов. Без этого исполнять предикатные захваты для синхронизации транзакции, невозможно. Эта проблема не разрешима. Эта проблема решится для простых условий.
9 Тупиковые ситуации параллельного исполнения транзакций. Механизм обработки тупиков.
Пример
О1 О2
Т1 Т2
В этом случае ни 1 из транзакций не может продолжить,блокир.О1 и о2 никогда не будут сняты. Выхода не существуют,его можно снять искусственно.
Основой обнаружения тупиков является постоянное поддержание графа транзакций.
Граф ожидания транзакции — ориентированный двудольный граф, в котором 2 вида вертикальных транзакций и?объектам?.
В этом графе существует дуга из транзакции к объекту, если для транзакции существует удовлетворенный захват объекта. Существует дуга из объекта к транзакции если транзакция ожидает удовлетворения захвата объекта.
Легко показать, что в системе тупик, если на графе есть цикл. Захваты могут быть по 1, но ожидать много. Для распознавания тупика производится граф транзакций. И в графе ищутся циклы.
Традиционной техникой нахождения циклов в орграфе является редукция графа.
1) Находим вершину в которой одинаковые стрелки (исход, вход)
2) Если находим значит не будет циклится, выключаем стрелку.
3) Далее так же стрелки из …
4) Повторяем шаги 1 и 2
5) Если таких вершин больше нет, а стрелки существуют, то есть циклы.
Разрушение тупика транзакции с выбора в цикле транзакции — жертвы, чтобы обеспечить работу других.
В жертву выбирается самая дешевая транзакция. После её многофакторного выбора производится её откат, полный или частичный. При этом освобождаются захваты и продолжается работа других.
Механизм временных меток.
Стоимость построения графа ожидания не велика, но становится слишком большой в распределенной субд. Альтернативный метод, хорошо работающий в условиях редких конфликтов и не требующий построения графи транзакций основан на использовании временных меток.
Основная идея:
Если т1 началась раньше транзакции т2, т. е. система обеспечивает как если бы т1 была целиком выполнена до начала т2. Для каждой транзакции метка т приписывается.
При выполнении действий над объектом транзакция т помечает это своей меткой с типом ожидания чтения. Перед выполнением операций т1 выполняет:
1) проверяет не закончилась ли транзакция т, помечает этот объект. Если т закончилась т1 помечает объект и выполняет операцию
2) если т не завершилось то т1 проверяет конфликтность операций. Если операции конфликтны при объекте остается метка с меньшим значением и т выполняет свою операцию.
3) Если т(Т)>т(Т1) производится откат
4) Если т(Т)<т(Т1) то т1 ставит новую метку и начинается снова.
К недостатку относится потенциально более частые откаты транзакции чем при синхронизационном откате. Связано с более грубыми определениями конфликтов.
10 Журнализация модификации данных в БД. Назначение, ситуации, требующие восстановления БД.
Поскольку основой поддержания целостности является механизм транзакций, поэтому механизм журнализации связан с транзакциями.
Ситуации требующие восстановления:
1) Индивидуальный откат транзакций ROLLBACK
Возможны случаи когда откат инициируется системой (возникает исключительная ситуация). Для отката нужно устранить модификации.
2) «Мягкий сбой» - потеря оперативной памяти.
3) «Жесткий сбой» - повреждение носителя
Архивные копии. Бывает поддержание только общего журнала.
2варианта ведения журнала
1) Для каждой транзакции поддерживать отдельный локальный журнал этой транзакции.
2) Поддержание только общего журнала(при индвиудуальных откатах)
11. Журнализация транзакций и буферизация. Восстановление данных при индивидуальном откате транзакции.
Журнал изменений тесно связан не только с управлением транзакций но и с буферизацией страниц БД в ОП, т.к объективно существует разницы в скорости работы процессора и памяти,и устройств внешней памяти. Буферизация страниц БД в ОП это единственный реальный способ достижения удовлетворит. Эффективности СУБД
Имеются 2 вида буферов:
-буфер журнала
-буфер страниц ОП,которые содержат связанную информацию
И те и другие могут выталкиваться во ВП. Проблема состоит в выработке политики выталкивания которое обеспечило бы возможность восстанавливать состояние БД после сбоя.
Проблема не возникает при индивидуальных откатах транзакций, поскольку в этих случаях содержимое ОП не утрачено и можно пользоваться содержимым буфера журнала так и буфером страниц.
Но если произошел мягкий сбой и содержимое буфера утрачено, для проведения восстановления БД необходимо иметь некоторые согласованные состояния журнала и БД на ВП.
Основным принципом согласованной политики выталкивания буф. журнала и буф. страниц, является то, что запись об изменении объекта БД должна попадать раньше чем измененный объект. Этот протокол состоит в том, что если требования выталкивания во ВП измененный объект, нужно выполнить гарантию выталкивания во ВП журнала записи о его изменении. Если во ВП БД находится объект БД по отношению которого выполнена операция модификация, то во ВП журнала находится запись соответствующая(соответственная-хз) этой операции. Обратное не верно.
Мин. Требованиям гар-м возможны требования согласованного состояния БД,является выталкивание при фиксации транзакции всех записей об изменении в БД этой транзакцией.
При этом последние записи в журнале производятся от имени данной транзакции. Явл. Спец запись о конце транзакции.
Восстановление данных после мягкого сбоя.
К числу основных проблем восстановления после мягк. сбоя относится то, что одна логическая операция изменения в БД может изменить несколько физических блоков БД. Например, страницу данных.
Страницы БД буферизуются в ОП и выталкиваются на физич. носитель БД, несмотря на применение протокола. Пиши сначала журнал (?!),после мягкого сбоя набор страниц ВП может оказаться несогласованным. Т.е. часть страниц ВП соответствует объекту до изменения, а др. часть после изменения.
Вводится понятие физической согласованности состояния ВП.
БД называется физически согласованной, если наборы страниц всех объектов согласованны, т.е. соответствуют состоянию объекта, либо после его изменения, либо до изменения.
Точки физической согласованности.
К моменту мягкого сбоя возможны след. вар. транзакций:
Для Транзакции Т1(все делать нужно по журналу)
Никаких действий производить не требуется, т.к. она закончилась до момента tфс и все результаты отражаются во ВП БД.
Для транзакции Т2
Нужно повторно выполнить оставшиеся операции (redo).На ВП полностью отсутствуют следы операции, которые выполнялись в Т2 после момента tфс. Следовательно, повторная прямая интерпретация корректна, и приведет к логически согласованному состоянию. Поскольку Т2 успешно завершилась до момента мягкого сбоя. В журнале содержатся записи всех изменений произведенной этой транзакцией.
Для транзакции Т3
Нужно выполнить в обратном направлении первую часть операции(undo) следовательно откатить ее во ВП БД. Полностью отсутствовавшие результаты операции Т3 которые были выполнены после момента tфс, с другой стороны во ВП, гарантирует присутствие операции Т3 которые были выполнены до момента tфс. Следовательно образованная интерпретация Т3 корректна и переведет к согласованному состоянию, целостность восстанавливается.
Поскольку Т3 не завершилась к моменту мягкого сбоя при восстановлении необходимо устранить все последствия ее выполнения.
Для транзакции Т4
Которая успела начаться после момента tфс и закончиться до момента мягкого сбоя нужно выполнить прямую интерпретацию, полную, повторно, всех операций,т.е. redo
ДЛЯ НАЧАВШЕЙСЯ после момента tфс и не успевшей завершиться к моменту мягкого сбоя.
Для транзакции Т5
Никаких действий предпринимать не требуется. Результат дл этой транзакции полностью отсутствует во ВП БД
