2015-05-23
4291. Основные типы архитектур параллельных СУБД.
Разделяемая память, разделяемые диски, без разделения выч. ресурсов
2. Эталонная архитектура СУРБД
3. Трехуровневая архитектура ANSI/SPARC локальных СУБД
4. Методы поддержки распределенных данных
Фрагментация – разбиение БД или таблицы на несколько частей и хранение этих частей на разных узлах РБД.
Репликация – создание и хранение копий одних и тех же данных на разных узлах РБД.
Распределенные ограничения целостности – ограничения, для проверки выполнения которых требуется обращение к другому узлу РБД.
Распределенные запросы – это запросы на чтение, обращающиеся более чем к одному узлу РБД.
Распределенные транзакции – команды на изменение данных, обращающиеся более чем к одному узлу РБД.
5. Прозрачность именования
6. Типы фрагментации. Правила фрагментации. Дерево фрагментации
а) горизонтальная - разделении множества кортежей глобального отношения на подмножества. Структуры фрагментов совпадают со структурой исходного отношения.
б) вертикальная - разбиении множества атрибутов а подмножества и нахождении проекций глобального отношения по этим подмножествам. Структуры фрагментов различны.
в) смешанная - последовательное применение двух предыдущих.
Полнота: если отношение R разбивается на фрагменты R1, R2,…, Rn, то
URi = R (Каждый кортеж должен входить хотя бы в один фрагмент).
Восстановимость: должна существовать операция реляционной алгебры, позволяющая восстановить отношение R из его фрагментов. Это правило гарантирует сохранение функциональных зависимостей.
Непересекаемость: если элемент данных dj Ì Ri, то он не должен присутствовать одновременно в других фрагментах. Исключение составляет первичный ключ при вертикальной фрагментации. Это правило гарантирует минимальную избыточность данных.
7. Типы эквивалентных преобразований реляционных выражений
· Коммутативность(а) и идемпотентность(б) унарных операций
U1U2R <-> U2U1R UR <-> U1U2R
· Коммутативность операндов и ассоциативность бинарных операций
RBS <-> SBR RB(SBT) <-> (RBS)BT
· Дистрибутивность(а) и факторизация(б) унарных операций по отношению к бинарным операциям
U(RBS) -> (UR)B(US) (UR)B(US) -> U(RBS)
8. Коммутативность операций соединения и объединения
(R’ UN R’’) JNF (S’ UN S’’) <-> UN ((R’ JNF S’), (R’ JNF S’’), (R’’ JNF S’), (R’’ JNF S’’))
9. Алгебра квалифицированных отношений
Квалифицированное отношение – расширенное путем указания квалификатора, [R: qr]
SLF[R:qr] ->:[SLFR: qr∩F]
PJA[R:qr] -> [PJAR: qr]
[R:qr]CP[S:qs] -> [R CP S: qr∩qs]
[R:qr]DF[S:qs] -> [R DF S: qr]
[R:qr]UN[S:qs] -> [R UN S: qrνqs]
[R:qr]JNF[S:qs] -> [R JNF S: qr∩qs∩F]
[R:qr]SJF[S:qs] -> [R SJF S: qr∩qs∩F]
10. Профиль базы данных
11. Программа полусоединения
Алгоритм AHY определения программ полусоединения – эвристический метод, декомпозиция запроса на простые подзапросы.
Применение алгоритма Parallel (оценка затрат передачи отношения, сокращ за счет полусоед по единств атрибуту соед)
Применение алгоритма Response (прим для каждого отношения графа запроса в отдельности и порождает наилуч план для каждого из них)
Выбор узла исполнения запроса
12. Свойства транзакций
Транзакция – последовательность операций, производимых над БД и переводящих БД из одного непротиворечивого состояния в другое непротиворечивое (согласованное), осуществляет доступ к БД с использованием примитивов чтения и записи. Согласованное (целостное) состояние БД – выполнены все ограничения целостности.
T3: Begin read(Y) Y=Y+1 write(Y) end commit или компактно b3, r3(Y), w3(Y), e3, c3
Свойства транзакций (ACID):
• атомарность (atomicity): транзакция либо выполняется полностью, либо вообще не выполняется;
• согласованность (consistency): выполнение транзакции не нарушает целостности базы данных;
• изолированность (isolation): данные, используемые транзакцией, не могут быть затронуты другой транзакцией. Транзакция протекает так, как будто других транзакций в то же время не выполняется (за исключением того, что она может быть приостановлена до завершения другой);
• устойчивость (живучесть, durability): после завершения транзакции результаты её выполнения не могут быть потеряны из-за каких либо сбоев ПО или оборудования.
13. Сериализуемое расписание
Расписание(график)транз – порядок выполнения элементарных операций, образующих транз.
Сериализуемость – это способность расписания быть эквивалентным последовательному выполнению транзакции. Свойством сериализуемости обладают транзакции, подчиняющиеся двухфазному протоколу.
Двухфазный протокол – это правило, требующее от каждой транзакции в 1ой фазе заблокировать все ресурсы, а во второй фазе симметрично их разблокировать.
14. Основные проблемы параллелизма
Параллелизм транзакций - режим функционирования, при котором каждому пользователю казалось бы, что БД доступна только ему, обеспечивается сериализуемостью.
Проблема потери результатов обновления. (перезапись другой транзакцией значения)
Проблема незафиксированной зависимости (чтение "грязных" данных, неаккуратное считывание). (откат транзакции привел к уничтожению данных, с которыми работала другая транзакция)
Проблема несовместимого анализа.
15. Особенность проблем несовместимого анализа
Неповторяемое считывание (повторное считывание дает результат, внесенный в промежутке другой транзакцией)
Фиктивные элементы (фантомы) (повторное считывание выборки строк привносит новую строку от транзакции B, вклинившийся между считываниями)
Собственно несовместимый анализ (длинная транзакция по всей таблице, которой мешает другая, изменяющая данные)
16. Возникновение тупиковых ситуаций
При использовании протокола доступа с исп блокировок возникают тупики
Проблема потери результатов обновления – dead lock
Проблема незафиксированной зависимости +
Неповторяемое считывание +
Фиктивные элементы (фантомы) не разрешено
Несовместимый анализ – dead lock
17. Коммутативность операций чтения и записи
Write – копирование значения локальной переменной X в переменную БД x
Read - копирование значения переменной x в локальную переменную БД X
P1 и p2 коммутативны, если:
- они оперируют различными элементами (w1(x) коммутирует с w2(y) and r2(y))
-обе являются операциями чтения (r1(x) коммутирует с r2(x))
18. Конфликтные операции
W1(x) конфликтует с w2(x)
W1(x) конфликтует с r2(x)
19. Эквивалентность по конфликтам
S1 и S2 с тем же самым набором транзакций являются эквив по конфликтам, если конфликтные операции упорядочены в обоих расписаниях одинаковым образом или одно мб получено из другого путем серией коммутативных обменов.
20. Эквивалентность по представлению
S1 и S2 с тем же самым набором транзакций являются эквив по представлению, если выполняются следующие свойства:
· Если Ti читает исходное значение объекта А в S1, то она также должна читать исх значение А в S2
· Если Ti считывает значение А, записанное Tj в S1, то она также должна прочитать значение А, записанное Tj в S2
· Для каждого объекта данных А транзакция (если есть), выполняющая его окончательную запись в S1, должна также выполнять окончательную запись объекта данных А в S2
21. Понятие правильно построенной транзакции
Удовлетворяет следующим условиям:
· Перед обработкой объекта БД должна быть выполнена его блокировка
· После обработки объект должен быть разблокирован (освобожден)
· Перед освобождениеи блокированного объекта не должна выполняться его повторная блокировка
· Неблокированный объект не должен разблокироваться (освобождаться)
22. Методы анализа сериализуемости расписаний
· Построение и анализ графа зависимостей (дуга из Тi в Tj, значит, Tj использует те же данные, что и Тi, если есть кольцо, то не сериализуемо)
· Построение и анализ графа предшествования (дуга из Тi в Tj, значит, Tj блокирует объект после разблокировки от Тi, если есть кольцо, то не сериализуемо)
· Построение и анализ графа ожидания (дуга из Тi в Tj, значит, Ti ждет разблокировки от Tj, если есть кольцо любой длины, то не сериализуемо)
23. Теорема Есварана
Если все транзакции в смеси подчиняются протоколу двухфазной блокировки, то для всех чередующихся графиков запуска (параллельных расписаний) существует возможность упорядочения.
Протокол двухфазной блокировки:
1.Перед выполнение каких-либо операций с некоторым объектом, транзакция должна заблокировать этот объект.
2.После снятия блокировки, транзакция не должна накладывать никаких других блокировок.
24. Варианты 2PL
· Усовершенствования консервативного 2PL (late locking - задержка блокирования до фактического использования объекта или early unlocking - разблокирование сразу же по последней операции транзакции с ним)
· Строгий (Strict 2PL (S2PL)) (все блокировки на запись не снимаются до окончания транзакции, а не операции)
· Жесткий 2PL (все блокировки на чтение и запись не снимаются до окончания всей транзакции)
25. Методы блокирования
· Разделяемое и монопольное блокирование (S(нежесткая) – разделяемый захват объекта для выполнения чтения и X(жесткая) – монопольный захват объекта для выполнения операций занесения, удаления и модификации, полное ограничение доступа для других)
· Преднамеренное блокирование (разные маркеры для объектов для различного характера блокировки)
· Предикатное блокирование (блокировка условий, а не самих объектов)
26. Матрица совместимости S- и X-блокировок
S – чтение, разделяемый режим блокировки
X – запись, монопольный режим блокировки
| Транзакция В пытается наложить блокировку | ||
| Транзакция А наложила блокировку | S-блокировку | X-блокировку |
| S-блокировку | Да | Нет (конфликт R-W) |
| X-блокировку | Нет (конфликт W-R) | Нет (конфликт W-W) |
W-W, вторая транз пытается изменить объект, измененный незакончившейся транз 1
R-W, транз 2 пытается изменить объект, прочитанный незакончившейся транз 1
W-R, транз 2 пытается читать объект, измененный незакончившейся транз 1
27. Типы блокировок метода преднамеренного блокирования
· Взаимного доступа (IS) накладывается на некот. составной объект О и означает намерение блокировать некоторый входящий в О объект в режиме S-блокировки
· Без взаимного доступа (IX) накладывается на некот. составной объект О и означает намерение блокировать некоторый входящий в О объект в режиме X-блокировки
· С возможностью взаимного доступа и без него (SIX) накладывается на некот. составной объект О и означает разделяемую блокировку всего этого объекта с намерением впоследствии блокировать какие-либо входящие в него объекты в режиме X-блокировок
| Попытка блокировки от В | |||||
| Блокировка от А | IS | S | IX | SIX | X |
| IS | Да | Да | Да | Да | нет |
| S | Да | Да | нет | нет | нет |
| IX | да | нет | Да | нет | нет |
| SIX | Да | нет | нет | нет | нет |
| X | нет | нет | нет | нет | нет |
Сила блокировок на убывание: X - > SIX -> S & IX -> IS
28. Способы «ожидание-гибель» и «ранение-ожидание»
«ожидание-гибель»
· Если T1 старше Т2, тогда старшая Т1 находится в состоянии ожидания блокировки
· Если же Т1 младше Т2, то младшая Т1 откатывается
«ранение-ожидание»
· Если Т1 старше Т2, тогда старшая Т1 «ранит» молодую Т2, ранение смертельное и молодая Т2 откатывается, если к моменту получения ранения Т2 не оказывается уже завершенной. Если завершена Т2, то «выживает» и откат не происходит
· Если же Т1 младше Т2, тогда младшей Т1 разрешается находиться в состоянии блокировки
29. Базовый протокол упорядочения временных меток
Метод временных меток - альтернативный метод сериализации транзакций, хорошо работающий в условиях редких конфликтов транзакций и не требующий построения графа ожидания транзакций, основан на использовании временных меток.
Основная идея: если транзакция T1 началась раньше транзакции T2, то система обеспечивает такой режим выполнения, как если бы T1 была целиком выполнена до начала T2. Каждой транзакции T предписывается временная метка t, соответствующая времени начала T. При выполнении операции над объектом r транзакция T помечает его своей временной меткой и типом операции (чтение или изменение).
Перед выполнением операции над объектом r транзакция T1 выполняет следующие действия:
· Проверяет, не закончилась ли транзакция T, пометившая этот объект. Если T закончилась, T1 помечает объект r и выполняет свою операцию.
· Если транзакция T не завершилась, то T1 проверяет конфликтность операций. Если операции неконфликтны, при объекте r остается или проставляется временная метка с меньшим значением, и транзакция T1 выполняет свою операцию.
· Если операции T1 и T конфликтуют, то если t(T) > t(T1) (то есть транзакция T является более "молодой", чем T1), производится откат T и T1 продолжает работу.
· Если же t(T) < t(T1) (T "старше" T1), то T1 получает новую временную метку и начинается заново.
30. Модифицированный протокол упорядочения временных меток. Правило Томаса.
· Проверяет, не закончилась ли транзакция T, пометившая этот объект. Если T закончилась, T1 помечает объект r и выполняет свою операцию.
· Если транзакция T не завершилась, то T1 проверяет конфликтность операций. Если операции неконфликтны, при объекте r остается или проставляется временная метка с меньшим значением, и транзакция T1 выполняет свою операцию.
· Если операции T1 и T конфликтуют, то если t(T) > t(T1) (то есть транзакция T является более "молодой", чем T1), производится откат T и T1 продолжает работу.
· Если же t(T) < t(T1) (T "старше" T1), то T1 отменяется. (правило Томаса – игнорирование устаревшей записи)
31. Методы многоверсионного управления конкурентным доступом
Один из механизмов обеспечения одновременного конкурентного доступа к БД, заключающийся в предоставлении каждому пользователю т. н. «снимка» БД, обладающего тем свойством, что вносимые данным пользователем изменения в БД невидимы другим пользователям до момента фиксации транзакции. Этот способ управления позволяет добиться того, что пишущие транзакции не блокируют читающих, и читающие транзакции не блокируют пишущих. В бд допускается существование нескольких «версий» одного и того же элемента данных
32. Мультиверсионное управление параллелизмом на базе упорядочения временных меток
Планировщик обрабатывает операции таким образом, чтобы суммарный результат выполнения операций был эквивалентен последовательному выполнению транзакций. При этом их порядок задается порядком временных меток, которые получают транзакции во время старта. Временные метки также используются для идентификации версий данных при чтении и модификации – каждая версия получает временную метку той транзакции, которая ее записала. Планировщик не только следит за порядком выполнения действий транзакций, но также отвечает за трансформацию операций над данными в операции над версиями, т.е. каждая операция вида “прочитать элемент данных x”, должна быть преобразована планировщиком в операцию: “прочитать версию y элемента данных x”.
Временная метка, полученная транзакцией ti в начале ее работы, - ts(ti). Операция чтения транзакцией ti элемента данных x - ri(x). Транзакция ti читает версию элемента данных x, созданную транзакцией tk, - ri(xk). Транзакция ti записывает версию элемента данных x, - wi(x).
1. Планировщик преобразует операцию ri(x) в операцию ri(xk), где xk – это версия элемента x, помеченная наибольшей временной меткой ts(tk), такой что ts(tk) <= ts(ti).
2. Операция wi(x) обрабатывается планировщиком следующим образом.
a. Если планировщик уже обработал действие вида rj(xk), такое что ts(tk) < ts(ti) < ts(tj), то операция wi(x) отменяется, а ti откатывается.
b. В противном случае wi(x) преобразуется в wi(xi).
3. Завершение транзакции ti (commit) откладывается до того момента, когда завершатся все транзакции, записавшие версии данных, прочитанные ti.
33. Многоверсионное управление параллелизмом на базе блокирования
Пессимистическое. Система блокировок не допускает, чтобы изменение данных одними пользователями влияло на других пользователей. После того как действие пользователя приводит к блокировке, до тех пор пока инициатор ее не снимет, другие пользователи не могут выполнять действия, которые могут вызвать конфликт с блокировкой. Это называется пессимистическим управлением, поскольку в основном применяется в средах с большим количеством конфликтов данных, где затраты на защиту данных с помощью блокировок меньше затрат на откат транзакций в случае конфликтов параллелизма.
Оптимистическое. При оптимистическом управлении параллелизмом пользователи не блокируют данные на период чтения. Когда пользователь обновляет данные, система проверяет, вносил ли другой пользователь в них изменение после считывания. Если другой пользователь изменял данные, возникает ошибка. Как правило, при получении сообщения об ошибке пользователь откатывает транзакцию и начинает ее заново. Это называется оптимистическим управлением, поскольку в основном применяется в средах с небольшим количеством конфликтов данных, где затраты на периодический откат транзакции меньше затрат на блокировку данных при считывании.
34. Параллелизм в распределенных БД
35. Методы блокирования в распределенных БД
