Общие понятия реляционного подхода к организации БД (1122811), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

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

Декомпозиция без потерь и функциональные зависимости, теорема Хита

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

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

Теорема Хита (Корректность декомпозиции).

Пусть задано отношение r {A, B, C} (A, B и C, в общем случае, являются составными атрибутами) и выполняется FD A B. Тогда r = (r PROJECT {A, B}) NATURAL JOIN (r PROJECT {A, C}).

Доказательство. Прежде всего, докажем, что в теле результата естественного соединения (обозначим этот результат через r₁) содержатся все кортежи тела отношения r. Действительно, пусть кортеж {a, b, c} r. Тогда по определению операции взятия проекции {a, b} (r PROJECT {A, B}) и {a, с} (r PROJECT {A, С}). Следовательно, {a, b, c} r₁. Теперь докажем, что в теле результата естественного соединения нет лишних кортежей, т. е. что если кортеж {a, b, c} r1, то {a, b, c} r. Если {a, b, c} r₁, то существуют {a, b} (r PROJECT {A, B}) и {a, с} (r PROJECT {A, С}). Последнее условие может выполняться в том и только в том случае, когда существует кортеж {a, b*, c} r. Но поскольку выполняется FD A B, то b = b* и, следовательно, {a, b, c} = {a, b*, c}. Конец доказательства.

Атрибут B минимально зависит от атрибута A, если выполняется минимальная слева FD A B.

Управление буферами основной памяти

Если бы при выполнении логических действий в базу данных сразу бы помещался результат этой операции, то скорость работы такой СУБД была бы сравнима со скоростью работы магнитных носителей. А скорости работы магнитных носителей всегда были и будут несравнимо ниже скорости работы оперативной памяти. Точно также, если при каждом обращении к страницам данных, СУБД будет лесть на внешнюю память, то произойдет тоже самое. На самом деле работа СУБД организована с помощью буферов в оперативной памяти. А именно с помощью буферного пула, в которой помещаются страницы данных или же индексные страницы, а также буфера журналльных записей, в который, соответственноЭ, помещаются все действия над журналом.

Когда СУБД требуется какая-то страницы данных, она копирует ее в буферный пул, и выполняет все изменения над ней в буферном пуле.

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

Но вопрос, какую из страниц?

В операционных системах в таком случае использовался алгоритм LRU. Тоесть, выталкивалась та страница, которая дольше всего не использовалась в прошлом( своеобразный прогноз на будущее). Но СУБД умнее. Она может более точно прогнозировать, какая страница понадобится в будущем, а какая нет. Например, при последовательном сканировании (NEXT без использования индекса) некоторой таблицы, можно заранее предугадать, какая страница дальше потребуется, и скопировать ее во внутреннюю память. Точно также, можно с уверенностью сказать, что индексные страницы будут успользоваться очень часто( имеются в виду страницы хранящие корни индексов). Поэтому, кроме такого прогноза, еще этот алгоритм LRU в СУБД снабжен системой приоритетов. Так, например страница корневой индексной информации будет иметь самый высокий приоритет и почти никогда не будет вытолкнута.

Физически согласованное состояние базы данных

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

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

Пример

Теневой механизм

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

Чтобы восстановить последнее согласованное состояние текущая таблица отображения заменяется теневой таблицей.

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

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

Иногда эти два журнала(логический и физический) хранят вместе, но обычно их разделяют на два

При создании новой точки физической согласованности:

1. Прекращается инициализация новых логических операций

2. После завершения всех лог операций, все страницы выталкиывются из буферного пула

3. Формируется и вуталкивается в буферный пул специальная запись о точке физического согласованного состояния

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

Ситуации, требующие восстановление базы данных:

1. Откат транзакций. Это может произойти путем выполнения операции ROLLBACK или же путем возникновения исключительной ситуации(например, деление на 0). Также транзакция может быть выбрана жертвой при возникновении тупиковой ситуации

2. Мягкий сбой.Теряется содержимое оперативной памяти(например, при аварийном отключении питания.)

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

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

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

Второй подход основывается на ведении общего журнала.

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

Индивидуальный откат транзакций

При индивидуальном откате транзакиций все операции, относящиеся к данной транзакции связывают в обратный список,в котором последней операцие всегда является операция начала транзакции. В общем случае для завершенной транзакции, результаты всех операций уже будут вытолкнуты из буферного пула, а значит первой операцией будет операция, завершающая транзакцию. Такие транзакции уже невозможно откатить. В случае, когда транзакция не завершена, какие-то даже уже выполненные операции могут быть из буфера не вытолкнуты и, соответственно, в журнале( по протоколу write ahead Log) находиться не могут. Тогда первой для такой транзакции будет некоторая операция транзакции.

1. Сначала по порядку из списка выбираются операции

2. Для выполнения отката индивидуальной транзакции, все операции из данного списка, заменяясь на противоположные( тоесть вставка заменяется на удаление удаление на вставку а обновление заменяется на обновление, производящще обратные действия)

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

4. Далее, в случае успешного завершения, журнале отражается операция завершения транзакции, и такая транзакция считается завершенной и зафиксированной.

Протокол Write Ahead Log.

При выполнении некоторых транзакций, действия изменения базы данных не сразу отражаются в базе данных, а сначала буферизуются, и когда в буфере нет места для вставки новой страницы, и некоторая страница выталкивается из буфера,и, если она отличается от страницы в во внешней памяти, то страница во внешней памяти заменчется на нее.Журнальная информация выталкивается из буфера в том случае, если этот буфер целиком заполнился. Вопрос состоит в том, в каком порядке нужно помещать информацию из буферов так, чтобы при возможности можно было восстановить БД при сбое во время такого выталкивания. Ответ дает протокол Write Ahead Log

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

Восстановление базы данных после жесткого сбоя

Самый простой способ восстановления:

Нужел логический журнал и архивная копия

1. Копирование Базы данных из архивной копии на носитель

2. Обратное выполнение всех операций из логического журнала

Если журнал утерян, то единственный способ-возврат к архивной копии.

Способы архивирования:

1. Администратор сам решает, когда нужно архивировать

2. Тогда, когда переполняется журнал

Но можно выполнять архивацию и реже, чем переполняется журнал.Можно выполнять архивацию самого журнала. В таком случае для восстановления БД нужна последняя версия логического журнала, последовательность архивов журналов и архивная копия БД.

Также архивные копии БД можно сжимать

1. Можно сжимать отдельную копию, оставляя только последнее действие над каким-то кортежем. Например, если последнее действие – удаление, то остальные действия можно не хранить

2. Можно аналогичным способом сжимать и последоватьельные архивные копии логического журнала.

Тоесть, для восстановления БД достаточно зранить архивную копию БД, сжатый архив журнала и последньь версию логического журнала.

Характеристики

Список файлов ответов (шпаргалок)