Законы оптимизации.
З-н коммутативности для соединения и декартова произведения. Если и
реляционные выражения, а
условие, налагаемое на атрибуты
и
,
то:
З-н ассоциативности для соединения и декартова произведения:
Законы, касающиеся операций селекции и проекции:
Каскад проекций:
если
Следствие:
если проекция по всем атрибутам отношения,
то она растворяется:
Каскад селекций:
Перестановка селекции и проекции:
.
Следствие:
Если
входят в F,
то
Перестановка селекции с декартовым произведением. Если все атрибуты, упоминающиеся в являются атрибутами , то
Если в F
входят только атрибуты выражения
то наоборот:
Следствия:
1. если
имеет вид
,
где
включает только атрибуты
,
а
только атрибуты
,
то в соответствии с законами 1, 4, 6 имеем:
если в используется только атрибут , а в – атрибуты
,
то
Таким образом, часть селекции может быть выполнена до произведения. Соединение всегда может быть выражено как декартово произведение с последующей селекцией, а в случае естественного соединения – проекцией.
Если имена атрибутов в и различаются, мы должны заменить атрибут в правой части формулы соответствующими именами в .
Перестановка селекции с объединением:
Перестановка селекции с разностью:
Перестановка проекции с декартовым произведением.
Пусть
и
– реляционные выражения;
список их атрибутов, причем
атрибуты выражения
,
а остальные
атрибуты выражения
,
тогда:
.
Перестановка проекции с объединением:
Если имена атрибутов
в
и (или)
отличны от имен атрибутов в
,
мы должны заменить
в правой части соответствующими именами.
Билет 39. Оптимизация запросов. Алгоритмы оптимизации выражений РА.
Исходные данные – дерево разбора, представляющее выражения РА. Выходные – тоже дерево, но оптимизированное (программа, для вычисления выражения).
Метод:
Каждую селекцию представляем в виде каскада по правилу 4):
;Перемещаем каждую селекцию насколько это возможно вниз по дереву, используя правила 5)-8);
Перемещаем каждую проекцию в дереве вниз настолько, насколько это возможно, используя правило 3), которое приводит к исчезновению некоторых проекций, следствие из 5), которое расщепляет на несколько, и правила 9) и 10);
Комбинируем каждый каскад селекций и проекций в одиночную селекцию, одиночную проекцию, или селекцию с последующей проекцией, используя правила 3) – 5);
Разбиваем внутренние узлы полученного в результате дерева на группы следующим образом. Каждый внутренний узел представляет собой двуместный оператор (\,
),
принадлежащий группе вместе с его
непосредственными предками, которые
помечены унарными операторами (
).
Включаем также в группу любую цепь
потомков данного узла, помеченных
унарными операторами, завершающуюся
в листе.
Исключением является случай, когда двуместный оператор представляет собой декартово произведение без последующей селекции, которая комбинировалась бы с произведением, образуя эквисоединение.
Создаем программу из нескольких шагов для вычисления каждой группы в любом порядке, но так, чтобы никакая группа не вычислялась раньше групп – ее потомков.
Шаги алгоритмов могут быть:
выполнение одиночной селекции или проекции;
выполнение декартового произведения, объединения, либо разности множеств, которые, возможно, предшествуют или за которыми следуют селекция или проекция, применяемая к одному или обоим операндам.
Пример:
Рассмотрим БД «библиотека», состоящую из отношений:
Книги (название;
автор; издательство; инв. №)
Издатель
(издательство; город; адрес)
Читатели (ФИО;
город; адрес; № читательского билета)
Выдача (инв. №; №
читательского билета; дата)
Для
того, чтобы знать, у кого находится какая
книга, можно использовать отношения
,
которые могут быть представлены следующим
образом:
(1)
F=(R3.№_читательского_билета=R4.№_читательского_билета) (R1.инвентарный_№=R4.инвентарный_№)=F1F2
X= название; автор; издательство; инв. №; ФИО читателя; город; адрес; № читательского билета; дата.
Опишем запрос: перечислить книги, которые были выданы до 01.01.2000.
После подстановки S в (1) получаем следующее дерево разбора:
1-й
шаг: расщепление
селекции
на две:
.
2-й
шаг: перемещаем
каждую из 3-х селекций как можно ниже в
дереве. Селекцию
перемещаем ниже проекции и двух селекций
по правилам 4) и 5).
Селекция
применяется к
,
и т.к. дата – единственный атрибут
,
то можно записать:
Селекция
не может быть перемещена ниже соединения,
т.к. в
используется отношение
и
.
Селекция
может быть применима к
.
3-й шаг: можно скомбинировать две проекции в одну по правилу 3):
4-й шаг: по обобщенному правилу 5) делаем замену:
5-й
шаг: применим
правило 9) с целью замены последней
проекции на
,
применим к
и
,
применим к левому операнду декартова
произведения более высокого уровня
(см. последний рисунок).
Последняя проекция взаимодействует с помещенной ниже селекцией по обобщенному правилу 5). В результате получаем каскад:
6-й шаг: последнюю проекцию можно записать в виде (она просеивается через декартово произведение по правилу 9) и частично через селекцию по правилу 5)):
Так как в проекции упоминаются все атрибуты , то ее удаляем. Каждое из декартовых произведений является фактически эквисоединением, если скомбинировать его с селекцией, находящейся выше в дереве.
Программа, выполняющая этот алгоритм, сначала будет выполнять нижнюю группу, затем верхнюю.
- - - – группы операторов.
|
|
Билет 40. Точная оптимизация для подмножества запросов, написанных на языке РИ.
Существует широкий класс запросов, называемых конъюнктивными, для которых можно найти точный оптимум. Для таких запросов можно минимизировать число соединений и декартовых произведений, необходимых при их обработке. Предположим, что при любом возможном критерии оценки оптимальный запрос содержит минимальное число соединений и произведений. Тогда становится реальным нахождение оптимального запроса эквивалентного заданному конъюнктивному запросу.
Конъюнктивным называется запрос, который может быть выражен в РИ с переменными на доменах следующим образом:
где
переменные на доменах или константа;
переменные на
доменах;
константы;
имеет вид
,
где
являются именами отношений, а
кортежи,
состоящие из
.
Тот факт, что
есть конъюнкция термов, дает название
запросу.
Два
запроса
и
эквивалентны т. и т.т., когда
Запрос
содержится
в
:
если для каждого отношения
имеем
.
Конъюнктивные запросы можно проверить
на эквивалентность, проверив:
.
Проверка справедливости отношения «содержится» для конъюнктивных запросов и основывается на существовании определенного вида отображений символов, используемых в , в символы, используемые в .
Пусть
Свёрткой
в
называется отображение
символов
в символы
,
такое, что:
;
константы неизменны,
и, следовательно,
должна быть
при некотором
;
является каким-либо
из
;Если – какой-либо терм
,
то
некоторый терм
,
где
,
примененное к кортежу
,
определяется равенством
.
Пример:
Теорема:
Запрос
,
если и только если найдется некоторая
свертка
в
Два запроса эквивалентны
,
если и только если найдется свертка
в
и
в
Минимизация конъюнктивных запросов.
Последняя
теорема может быть использована для
определения конъюнктивного запроса с
минимальным числом термов, эквивалентных
данному запросу
.
Минимизируя число термов, мы тем самым
минимизируем число операций соединения
и декартового произведения. Таким
образом, минимизация термов каждого
запроса является хорошим первым шагом,
за этим должны следовать другие: более
раннее выполнение селекции и проекции.
Свёртка как отображение термов.
Термы запроса Термы запроса
f
g f
f
– min-й запрос
g
f
g
Композиция двух свёрток также является свёрткой.
Теорема:
Для каждого конъюнктивного запроса
найдется эквивалентный ему конъюнктивный
запрос
с наименьшим возможным числом термов.
Любой
другой запрос
,
эквивалентный
,
имеющий минимальное число термов и не
содержащий каких-либо квантифицированных
переменных, является взаимно однозначным
переименованием символов
.
Следствие:
Для любого заданного конъюнктивного
запроса
можно найти эквивалент с минимальным
числом термов путем удаления из него
нуля или более термов и всех кванторов
,
таких, что переменная
не появляется больше ни в одном терме.
Билет 41. Параллельная обработка БД. Основные понятия и определения.
До сих пор рассматривалась концепция БД, при которой предусматривается одновременное исполнение только одной программы, осуществляется доступ БД. На практике это чаще всего и требуется. Однако существует целый ряд приложений, когда одновременно (параллельно) исполнение нескольких программ или различных прогонов одной и той же программы (система продажи авиабилетов). Главная проблема состоит в том, что если не позаботиться о правилах, регулирующих доступ к БД 2-х или более программ, то не исключается возможность продажи билетов на одно и то же место двум пассажирам. Т.е. нельзя допускать параллельное исполнение 2-х процессов, которые читают и изменяют значение одного и того же объекта. Если осуществляется только чтение, то для экономии времени желательно в максимальной степени использовать параллельные запросы к БД.
Различают файл-сервер и клиент-сервер:
БД с распределённой обработкой, когда файлы БД находятся на сервере, а программы обработки на рабочих станциях;
Распределённые БД – файлы БД находятся как на сервере, так и на рабочей станции.
БД коллективного пользования относят и к первому, и ко второму видам.
Распределённая БД состоит из нескольких, возможно пересекающихся или даже дублирующих друг друга частей, хранимых в различных ЭВМ вычислительной сети. Работа с такой базой осуществляется с помощью системы управления распределённой БД (СУРБД).
По способу доступа к данным БД разделяются на БД с локальным доступом и БД с удаленным сетевым доступом.
Основные понятия.
Транзакция – это разовый прогон программы. Одновременно возможно исполнение нескольких независимых прогонов одной и той же программы, и каждый из них является транзакцией.
Элементы – это части БД, которые можно блокировать, при этом выполняемая транзакция может препятствовать доступу другой транзакции к этому элементу до тех пор, пока не разблокирует его. Блок управления блокировками – компонент СУБД, который назначает, регистрирует блокировку.
В РБД могут выбираться большие элементы, включающие целые отношения, и малые – отдельные кортежи и компоненты кортежей, или часть отношения. Выбор больших элементов сокращает накладные расходы системы по поддержанию блокировок, малых элементов дает возможность параллельного исполнения многих транзакций. Должен быть разумный компромисс. Считается, что размер элемента выбран правильно, если средняя транзакция требует доступа к малому числу элементов. Так, в РБД если типичная транзакция читает или модифицирует один кортеж, то целесообразно трактовать кортежи как элементы. Если же типичная транзакция производит соединение двух или более отношений и тем самым требует доступа ко всем кортежам этих отношений, то в качестве элементов более уместно выбрать отношения.
Пример:
Пусть имеются 2 транзакции
и
.
Каждая из них осуществляет доступ к
элементу
,
имеющему целое значение, и увеличивает
его на 1. Обе эти транзакции представляют
собой прогоны програмы
,
имеющей следующий вид:
READ A
A=A+1
WRITE A
В результате 2-х транзакций и значение возросло только на 1. Это представляет серьезную проблему, если – число мест, проданных на определенный рейс.
Решение проблемы состоит в обеспечении блокировки для .Перед тем, как прочитать элемент , транзакция должна его блокировать. Это:
предотвратит доступ другой транзакции к нему до тех пор, пока не завершит работу с ;
Если уже блокировано другой транзакцией, то для транзакции
доступ к элементу
невозможен до тех пор, пока с ним не
завершится работа.
Существует 2 основных вида блокировки:
простая блокировка – не вводится различие блокировок для операции чтения или операции записи элемента .
Установить блокировку: LOCK X – предотвращает доступ к элементу X от других транзакций как по операции чтения, так и по операции записи до тех пор, пока этот элемент не будет разблокирован.
блокировка для чтения/записи.
В этой модели проводится различие между видами доступа к элементу :
доступ только для чтения;
доступ для чтения и записи.
Соответственно различают 2 типа команд блокировки:
Команда блокировки элемента по чтению. Транзакция, в которой требуется выполнить только чтение элемента , осуществляет блокировку по чтению. Блокировка по чтению запрещает любой другой транзакции выполнять запись нового значения элемента , пока он не будет разблокирован.
RLOCK X (READ-LOCK X)
Блокировку элемента по чтению могут установить несколько транзакций (т.е. допускается параллельная работа по чтению данных нескольких транзакций).
Команда блокировки элемента по записи. Эта команда соответствует команде блокировки в простой модели, т.е. предотвращает доступ к элементу от других транзакций как по чтению, так и по записи.
Пример: простая модель блокировки
:
LOCK A
READ A
A=A+1
WRITE A
UNLOCK A
Система предоставляет блокировку элемента транзакции, если никакая другая транзакция не заблокировала . Ввод блокировки позволяет сохранить целостность данных при параллельных запросах к БД.
Билет 42. Параллельная обработка БД. Бесконечные ожидания и тупики.
Пусть
транзакция
проводит работу с элементом
,
и доступ к элементу
заблокирован этой транзакцией;
находится в состоянии ожидания; транзакция
также
запрашивает блокировку
,
и этот запрос исполняется раньше, чем
запрос
.
Далее, в то время, когда блокировку
установила транзакция
,
ее запрашивает
,
чьё требование удовлетворяется после
разблокирования
транзакцией
и т.д. Не исключено, что транзакция
будет пребывать в состоянии бесконечного
ожидания.
Простой способ избежать этого: регистрировать все запросы и удовлетворять их в порядке очерёдности.
Вторая, более серьёзная проблема – тупики.
Пример: : READ A
: READ A
– возможно бесконечное ожидание.
: LOCK A : LOCK B
LOCK B LOCK A
UNLOCK A UNLOCK B
UNLOCK B UNLOCK A
Транзакция запрашивает блокировку и её запрос удовлетворяется. Точно так же удовлетворяется запрос транзакции на блокировку . Затем запрашивает блокировку и ждет, т.к. он заблокирован транзакцией . Аналогично запрашивает блокировку и должна ждать, пока разблокирует . Таким образом, ни одна транзакция не может продолжаться; каждая из них ожидает, пока другая разблокирует требуемый для нее элемент. Поэтому и будут ждать бесконечно долго.
Ситуация, в которой каждая транзакция из множества S, содержащего не менее 2-х транзакций, ожидает, когда ей будет предоставлена возможность заблокировать элемент, заблокированный в данный момент времени какой-нибудь иной транзакцией из данного множества S, называется тупиком.
Подход к решению этой проблемы:
Потребовать, чтобы каждая транзакция единовременно запрашивала все нужные ей блокировки. Система либо полностью удовлетворяет такой запрос, либо не предоставляет вообще никаких блокировок и заставляет данную транзакцию ждать, если один или более требуемых элементов заблокирован до транзакции. Это устраняет тупик из примера.
Вводится произвольное линейное упорядочивание элементов и все транзакции должны запрашивать блокировки в этом порядке. Это гарантирует установление очередности между транзакциями. Для транзакции, заблокировавшей некоторый элемент, гарантируется возможность заблокировать и все следующие за ним элементы.
Совсем иной способ борьбы с тупиками – ничего не предпринимать для их предотвращения, а периодически проверять запросы на блокировки и выявлять: не возникла ли тупиковая ситуация. Облегчает проведение такой проверки алгоритм построения графа, вершины которого обозначают транзакции, а ориентированная дуга
,
что транзакция
ожидает выполнения своего запроса на
блокирование элемента, заблокированного
в данный момент транзакцией
.
Возникновение тупика определяет наличие
в построенном указанным способом графе
цикла. Если цикла нет, то не существует
и тупиков.
В случае обнаружения тупика нужно произвести снятие всех блокировок (рестарт) хотя бы для одной из попавших в него транзакций (удалить дугу) или сделать откат транзакции (удалить вершину).
Билет 43. Протоколы и расписания. Простая модель транзакции.
Протоколы и расписание.
Каждая транзакция состоит из элементарных шагов (блокировка, чтение записи и т.д.).
Расписанием совокупности транзакций называется порядок, в котором выполняются элементарные шаги этих транзакций. Шаги любой транзакции должны появляться в расписании в порядке их вхождения в программу, прогоном которой является эта транзакция.
Расписание считается последовательным, если все шаги каждой транзакции выполняются последовательно; сериализуемым, если результат его реализации всегда эквивалентен результату некоторого последовательного расписания.
Для предотвращения несериализуемости расписания вводят протоколы, которые в наиболее общем смысле представляют собой ограничения на последовательность шагов, которые может выполнить транзакция. Например, протоколом является исключающая тупики стратегия запрашивания блокировок элементов в некотором фиксированном порядке.
Простая модель транзакции.
Изучим простейшую модель транзакции, которая позволяет говорить о сериализуемости. В этой модели транзакция рассматривается как последовательность операторов блокирования и разблокирования. Каждый блокированный элемент впоследствии должен быть разблокирован. Будем считать, что между шагами LOCK A и UNLOCK A транзакция осуществляет изменение значения .
Поставим
каждой паре шагов LOCK и UNLOCK однозначную
функцию f.
Вообще говоря, любой элемент
может быть заблокирован и разблокирован
достаточно большое число раз. Поэтому
будем рассматривать последовательность
функций
,
где
– начальное значение
до выполнения любых транзакций.
Пример: : LOCK A A B C
: LOCK B …
: LOCK C …
:
UNLOCK B
: LOCK B
:
UNLOCK
A
: LOCK A
:
UNLOCK
C
:
UNLOCK
A
: LOCK A
: LOCK C
:
UNLOCK
B
:
UNLOCK
C
:
UNLOCK A
Билет 44. Алгоритм проверки проверки сериализуемости расписания.