Теоремы приведения к НФ

Нормальные формы.

Отношение находится в 1 нф, если все его атрибуты атомарны (приним единств значение).

 

18 Восстановление БД

- возвращ-е БД в правил-е (корректн) состояние после сбоев. Для поддержки процесса восстановления предназначены транзакции.

Транзакция– послед-ть операций, выполн-х с БД, переводящая БД из одного согласов-го состояния в др. согласов-е состояние.(соглас. сост–сост при кот не нарушена целостн БД)

Напр, произв-ся 2 операции, кот д. б. или вместе выполн. или невыполн. Пусть 1-я выполн-сь успешно, а при выполн-и 2-й произойдет сбой, то в БД окажется противор-я инф. Такие операции д. б. объед-ны в транзакцию.

Свойства транзакции:

1. Атомарность. Транзакция либо выполняется целиком, либо не выполняется вообще.

2. Согласованность. До и после выполненя транзакции БД наход-ся в соглас-м состоянии.

3. Изолированность. Транз, конкурирующие за доступ к БД, выполн изолированно друг от др (или послед-но).

4. Долговечность. Если транз завершена успешно, то изме-нения, кот-е она выполнила, не могут быть потерны.

Вар-ты завершения транз

Транзакция м завершиться 2-мя способами:

1. Фиксация – Commit (обеспеч-е долговерч-ти)

2. Откат – Rollback (при этом аннулир-ся все действия, кот успели вып-ся, и БД перевод-ся в то сост-е, в кот. она была до начала транзакции.

При успешном заверш-и транзакции - фиксация, иначе – откат.

Структура журнала транз

Восстан-е БД в исх-е сост-е возможно благодаря журн транзакций – последов-й файл, в кот-й запис-ся все выполенные операции над БД (в рамках транз).

Фиксир-ся имя транз-и и её действ-я. Сущ-т 2 вида журналов:

1. С немедленным обновле-нием (изм-я в БД произв-ся по ходу)

Транз-я 1 запись до операции запись после операции

…..

Транз-я 1 Commit / Rollback

В случае неудачи - чтение журнала в обр. порядке и восстан-е.

2. С отложенным обновлен

Изм-я в БД не произв-ся – только обновл журнал. Если транз-я заверш-сь успешно, СУБД просматр-т журнал и выполняет все операции. Иначе-просто ничего не делается.

 

 

19 Физическая модель БД

Стр-ра хран-я данных: страницы

Единицы хран-я - хранимая запись. Состоит из двух частей:

1. Служебная часть. Испол-ся для идентиф-и записи, задания её типа и т.п. 2. Инф-я часть. содержит зн-я эл-в данных.

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

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

Кластеризация– физич-е упоряд-е записей, является методом совместного хране-ния родственных данных (таблиц). Кластер – это структура памяти, в кот. хранится набор таблиц (в одних и тех же блоках данных).

Внутрифайловая кл-я – физ.упоряд-е внутри 1 табл. иначе межфайл-я (если необ-мо частое обращ-е к неск. табл-м ).

Преимущ-во: Уменьш-ся обмен с диском, улучш-ся время доступа к кластериз-м таблицам и их соедин-м.

Совместное хран-е - на 1 странице (блоке памяти) хранятся данные из всех кластериз-х табл, имеющие одинаковое зн-е кластерного ключа (столбец или набор общий для класт-х тбл).

Индексы

Для ускор-я доступа к записям созд-ся спец струк-ра – индекс, кот. опред-т соотв-е зн-я атрибута (их группы) и местопол-я записи. => Струк-ра инд-го ф-ла: основ обл-ть и индексная обл. (хранит RID). RID-указатель – физич адрес записи. Табл в БД м. иметь больш кол-во строк, кот. хран-я в произв-м порядке, их поиск по задан-му зн-ю путем послед-го просмотра строк табл м. занимать много времени. Индекс формир-ся из зн-й 1 или неск столбцов табл и указателей на соотв-е стр табл (RID) , что позв-т находить нужную стр по задан. зн-ю.

20 Жизненный цикл информационной системы

Этапы жизненного цикла:

1.Анализ требований

2.Проектирование

3.Реализация ИС

4.Этап внедрения

5.Эксплуатац и сопровожд

Модель – последовательность этапов жизненного цикла.

1)Каскадная

В основном для структурированных задач, когда известно какая дб система.

+ можно четко спланиров кажд этап, время, рес-сы

- отсутств обр связи, ведет к накоплению ошибок

2)Каскадная с возвращением

+- как у 1

+ возм устранен ошиб

3)Спиральная

прототип и его эволюция

+ быстр получение прототипа, → более ранняя оц рисков

– на этапе прототипир можно зациклится, сложно опр бюджет проекта

 

 

 

Отношение нах-ся во 2нф, если оно находится в 1нф и в нем отсутствуют неполные функц-е завис-ти от ключа. R(A, B, C, D), {A, B} – ключ. {A, B} → C и {A, B} → D - по опред-ю ключа

B → C - неполная завис-ть от ключа (атрибут завис-т от части ключа)

Переход к 2нф – декомпозиция: R₁(B, C), B – ключ; R₂(A, B, D), {A, B} – ключ.

Отнош находится в 3нф, если оно находится в 2нф и в нем отсутствуют транзитивные зависимости от ключа.

R(A, B, C, D), A – ключ.

A → В, A → C, A → D - по опред-ю ключа

С → D - транзитивная зависимость от ключа

Переход к 3нф – декомпоз-я: R₁(C, D), C – кл; R₂(A, B, C), A – кл

Отношение находится в нормальной форме Бойса-Кодда (НФБК), если оно находится в 3нф и в нем отсутствуют функц-е завис-ти ключевых атрибутов от неключевых.

Отношение находится в 4нф, если оно находится в НФБК и в нем отсутст-т многозн-е завис-ти (кот. не явл-ся функцион-ми).

Декомпозиция- действия по раздел-ю 1 отнош на неск отнош. Пусть исх-я схема R с мн-м функц-х завис-ей F была приведена в рез-те декомпоз-и к схеме отнош-й R1,R2,…,Rk с мно-м функции-х завис-й F₁, F₂, … , F_k.

Свойства декомпозиции:

1. Соединения без потерь: люб. отнош-е r со схем. R удовл-т соотнош-ю: r(R) = π_R1(r) >< π_R2(r) >< … >< π_Rk(r) (>< - - соедин-е).

2. Сохранения зависимо-стей, если из объединения всех завис-й F₁, F₂, … , F_k м вывести все завис-ти F.

Теоремы приведения к НФ.

1. Всякая схема отнош-я R с мн-м функц-х завис-й F м. б. приведена к декомпоз-и в 3НФ с сохран-м завис-й и соедин-м без потерь.

2. Всякая схема отнош-я R с мн-м функц-х завис-й F и мн-м многозн-х завис-й M м. б. приведена к декомпоз-и в 4НФ с соедин-м без потерь.

 

 

Блокировка

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

Объекты блок-к: БД, табл, запись или группа записей, фиксация 1 конкр-го зн-я (ячейки).

2 вида блокировок:

1. Монопольная блок-ка (eXclusive) – никакая др. тран не м. обратится к данным (не позв-т вып дейст над тбл).

2. Блокировка с раздел-м доступом (Shared) – остальн транз м. читать данные (позв-т вып-ть чтение из табл).

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

Возник-т проблемы при выполн-и блок-ки =>

Тупик– когда обе транз ждут друг друга. Выход из тупика – выполн-е отката какой-либо транзакции. СУБД ч/з опред-е промеж-ки врем. провер-т сост-е транзак-й, строит схему (граф) - если находит цикл => тупик. Тогда СУБД оценив-т кажд. транз и выбир-т с наиб-м весом (напр. вес=кол-во транз-й ожидающ-х её)

Уровни изолированности транзакций.

Dirty Read (Uncomitted) – не зафиксир чтение. Транзакция м читать не зафиксир данные.

Read Commited – невоспроизводимое чтение. Транз-я м. видеть только зафиксированные данные.

Repeatable Read – воспроизводимое чтение. Видит только те данные к-е были на момент старта транз-и, т.е транц-я б. раб. с копией БД.

Serialized – сериализуемая. Транз выполн последов-но, ∀ блокирует БД а др ждут её.