Функциональные зависимости и аномалии вставки, обновления, удаления

R(A1, A2, . . . An) f(Ai1, Ai2, . . . Aik) → Al

X → Y ⇐⇒ || πY (σX=x(R)) || ≤ 1

Набор атрибутов Y функционально зависит от набора атрибутов X, если для любого значения X существует ровно одно значение Y.

1. Проанализируем БД и увидим, что имеют место некие соотношения. В некоторых состояниях БД имеются функциональные зависимости. Тем не менее, такие состояния могут быть легко нарушены и зависимость исчезнет. Такой подход хорошо согласуется с чистой теорией реляционных баз данных, поскольку в ней изменений не бывает.

2. Функциональные зависимости могут отражать законы природы и общества. Пример: Первые две цифры номера зачётной книжки совпадают с последними двумя цифрами года поступления. Такая зависимость, если она соблюдается, является законом природы, но такая интерпретация бесполезна для БД. Зависимость отражает свойства реального мира и является частью схемы.

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

Минимальное множество атрибутов, от которых зависят все атрибуты, называется возможным ключом. Возможный ключ - ключ, из которого нельзя выкинуть атрибуты так, чтобы оставшийся набор оставался ключом. Возможный ключ не обязательно единственный - множество «возможных» ключей может быть частично упорядоченным множеством без минимального элемента. Чтобы была уникальность строк, требуется уникальность возможного ключа. Первичный ключ: один из возможных ключей. Остальные ключи должны быть уникальны - можно вводить ограничения целостности.

Зависимости приводят к появлению избыточности. Пример:

Зависимости: AB → C B → D.

a1 b1 c1 d1

a2 b1 c2 d1

a3 b3 c3 d3

a4 b3 c4 d3

Зависимости: A → B B → C.

a1 b1 c1

a2 b1 c1

a3 b3 c3

a4 b3 c3

Невозможно сохранить <b,c>, если нет a.

Вверху значение атрибута D зависит только от B, но не от A. Избыточность с

остоит в том, что повторяются значения D, соответствующие значениям B. Повторяющиеся значения B не избыточны. Чуть ниже избыточность в C, но не в B. Избыточность плоха тем, что:

1. Избыточные данные занимают место.

2. Возникают сложности при обновлении. Функциональные зависимости должны быть удовлетворены - если меняем D, должны поменять и B, причём в нескольких местах.

3. Нет возможности отразить некоторые факты в БД. Нет возможности хранить только B и D, надо и A.

Аномалия обновления – появление в базе данных несогласованности данных при выполнении операций вставки, удаления, модификации записей.

Аномалии обновления – появление записей с противоречащими значениями в некоторых столбцах при изменении значений соответствующих полей одной записи.

Для отношения Студент (ФИО, Группа, Староста), где в столбце Группа хранится полное название группы, а столбец Староста содержит ФИО старосты группы, изменение значения Староста (например, для устранения ошибки) может привести к существованию более одного старосты одной и той же группы.

Аномалии удаления – удаление лишней информации при удалении записи.

16. Нормализация: декомпозиция отношений. Нормальные формы.

http://wiki.auditory.ru/%D0%91%D0%94:%D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%E2%84%9605,06

Наша цель - избавиться от зависимостей, преобразовав схему. Нормализация - процесс преобразования схемы базы данных в нормальные формы. Чем выше номер нормальной формы, тем лучше схема. Когда мы определяли модель, мы предполагали, что домены атомарны. Атрибуты должны быть атомарны. Положим, мы хотим рассмотреть более общую структуру данных, с неатомарными структурами. [21] Слева на рисунке показано составное отношение. 2 атрибута: первый - скалярный, второй - вложенное отношение. В сегодняшней теории они не считаются предосудительными, но реляционная теория их не рассматривает. Можно преобразовать в скалярное отношение – просто повторяем значения атомарного атрибута вместе с каждой строкой вложенного. Это преобразование называется преобразованием в первую нормальную форму. Концептуально можно не рассматривать сложные структуры. Здесь мы вводим очень большую избыточность; если есть функциональные зависимости, то, возможно, некоторые из них будут следовать из факта вложенности. Пример: По номеру группы иногда можно определить номер курса.

Неполная зависимость:

AB → C, B → D. Мы заменяем исходное отношение на две его проекции, чтобы устранить нежелательные зависимости внутри отношений. Первая проекция - атрибуты A, B, C, вторая проекция - атрибуты B и D. Можно восстановить исходное отношение, выполнив естественное соединение по B. Потери информации не происходит. Это называется устранением зависимости от неполного ключа. Результат - вторая нормальная форма.

Транзитивные зависимости:

A → B, B → C, A → C

Здесь тоже заменяем отношение на две проекции. (Общий приём. Если есть зависимость, разбиваем отношение на несколько проекций, чтоб исходное можно было возродить естественным соединением.) Результат - третья нормальная форма. Есть усиленная третья нормальная форма. Третья нормальная форма - последняя нормальная форма, которая общепризнана. способ нормализации неоднозначен. Можем получать разные схемы, нормализуя одни и те же отношения, при этом мы даже не можем сказать, что лучше, а что хуже. Есть вещи, лежащие за пределами модели.

Пример: Пусть есть организация, есть сотрудники, отделы, руководители. Сотрудник работает ровно в одном отделе, у отдела есть только один руководитель, руководитель может руководить одним отделом, следовательно каждый сотрудник имеет ровно одного руководителя. 2 варианта нормализации:

– сотрудник и отдел, отдел и руководитель

– сотрудник и руководитель, руководитель и отдел

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

Другие нормальные формы устраняют многозначные зависимости, зависимости включения, зависимости

соединения.

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

• Четвёртой нормальной формой называется отношение, которое находится в нормальной форме Бойса-Кодда и не содержит нетривиальных многозначных зависимостей. Многозначная зависимость представляет такую зависимость между атрибутами A, B и C некоторого отношения, при которой для каждого значения атрибута A существуют соответствующие множества значений атрибутов B и C, причем оба эти множества не зависят друг от друга.

• Пятой нормальной формой называется отношение, которое не содержит зависимостей соединения. Отношение R с подмножествами атрибутов A,B,...,Z удовлетворяет зависимости соединения, если и только если каждое допустимое значение R равно соединению его проекций на подмножества A,B,...,Z.

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

Первая нормальная форма (1НФ) - отношение, в котором на пересечении каждой строки и каждого столбца содержится одно и только одно значение.

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

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

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

Нормализация отношений 2НФ с образованием отношений ЗНФ предусматривает устранение транзитивных зависимостей. Если в отношении существует транзитивная зависимость между атрибутами, то транзитивно зависимые атрибуты удаляются из него и помещаются в новое отношение вместе с копией их детерминанта.

Нормальная форма Бойса-Кодда (НФБК): отношение находится в НФБК тогда и только тогда, когда каждый его детерминант является потенциальным ключом.

Для проверки принадлежности отношения к НФБК необходимо найти все его детерминанты и убедиться в том, что они являются потенциальными ключами. Напомним, что детерминантом является один атрибут или группа атрибутов, от которой полностью функционально зависит другой атрибут.

Различие между ЗНФ и НФБК заключается в том, что функциональная зависимость А—>В допускается в отношении ЗНФ, если атрибут В является первичным ключом, а атрибут А не обязательно является потенциальным ключом. Тогда как в отношении НФБК эта зависимость допускается только тогда, когда атрибут А является потенциальным ключом. Следовательно, нормальная форма Бойса-Кодда является более строгой версией формы ЗНФ, поскольку каждое отношение НФБК является также отношением ЗНФ, но не всякое отношение ЗНФ является отношением НФБК.

Возможность существования в отношении многозначных зависимостей возникает вследствие приведения исходных таблиц к форме 1НФ, для которой не допускается наличие некоторого набора значений на пересечении одной строки и одного столбца. Например, при наличии в отношении двух многозначных атрибутов для достижения непротиворечивого состояния строк необходимо повторить в них каждое значение одного из атрибутов в сочетании с каждым значением другого атрибута. Подобный тип ограничения порождает многозначную зависимость и приводит к избыточности данных.

Четвертая нормальная форма (4НФ) - отношение в нормальной форме Бойса-Кодда, которое не содержит нетривиальных многозначных зависимостей.

5НФ: невозможно дальнейшее разложение без потерь

http://ru.wikipedia.org/wiki/%D0%9F%D1%8F%D1%82%D0%B0%D1%8F_%D0%BD%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0

Пусть существует некоторое отношение r со схемой R, а также два произвольных подмножества атрибутов . Пусть . В этом случае B многозначно зависит от A, тогда и только тогда, когда множество значений атрибута B, соответствующее заданной паре [a:A;c:C] отношения r, зависит от a и не зависит от c.

17. Язык запросов SQL: операции реляционной алгебры.

Язык запросов SQL (слайды: 3-query-processing, стр. 23)

(http://ru.wikipedia.org/wiki/SQL)

Многие думают, что ничего, кроме SQL в базах данных не бывает и никогда не было. Такие люди будут расстреливаться на месте.

Первое появление (IBM): 1983

Стандарты: 86, 89, 92, 1999, 2003, … ?

Считается, что поддерживается всеми СУБД

Уровни стандарта:

– DML (можно манипулировать данными, то есть делать выборку, вставлять, обновлять, удалять)

– Программный интерфейс

– DDL (можно описывать данные, то есть таблицы, вьюшки и т.д.)

Реляционные операции в SQL (слайды: 3-query-processing, стр. 23):

1. ограничение

Select * from person Where name=‘Анна’

2. проекция

Select distinct name, age From person

3. произведение

Select * From person, dept

4. соединение

(в этом примере, по сути, эквисоединение в реляционной алгебре -> inner join в SQL)

Select * From emp, dept Where emp.dno = dept.dno

Select * From emp join dept on emp.dno=dept.dno

5. внешнее соединение

Select * From dept Left join emp On dept.dno = emp.dno

18. Язык запросов SQL: вложенные подзапросы.

Конспект стр 30-31.

19. Язык запросов SQL: агрегирование и упорядочение.

Агрегирование - стр 31 конспект.