Вордовские лекции (1121814), страница 9

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

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

Теорема Хита

r{A, B, C} и выполнены ФЗ A-B

Тогда r={r PROJECT{A,B}} NATURAL JOIN (r PROJECT {A, C})

||Всего в курсе три теоремы, одна лемма.

Пусть {a, b, c} принадлежит r

{a, b} принадлежит (r PROJECT {A, B}), {a, c} принадлежит (r PROJECT {A, C}) => {a, b, c} принадлежит r1

Если {a, b, c} принадлежит r1, to {a, b, c} prinadlezhit r {a, b} принадлежит (r PROJECT {a, b})

{a, c} принадлежит (r PROJECT {A, C}) => {a, b*, c} принадлежит r => b* = b

Обычно т. Хита используется, когда a – ключ.

Определение. Минимально зависимые атрибуты. B миним зависит от A, если имеется FD A->B, минимальный слева атрибут.

Мин слева атрибут полезная вещь, так как на них базируется первая НФ.

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

СЛУ_НОМ – > СЛУ_ЗАРП

{СЛУ_НОМ, СЛУ_ИМЯ} - > СЛУ_ЗАРП

Следующая тема:

Проектирование РБД на основе принципа нормализации

Что нужно делать для проектирования БД:

Стараться проектировать так, чтобы при изменениях приходилось делать минимум проверок:

Перва альтернатива – система позволяет делать изменения, но потом говорит, что неправильно всё, и стереть все результаты.

Вторая – триггеры.

Физическое проектирование: проектирование на уровне СУБД, формулирование, как я хочу выполнять запросы. Важный этап, но полностью зависит от того, как реализована СУБД. Сейяас у СУБД дикое количество рычажочков, ручечек, которые можно подкручивать.

Дополнительное Логическое проектирование. Которое не следует протоколам. Есть две области: online tracsaction processing – с бд выполняется много коротких транзакций с большими изменениями в бд. Вторая область – аналитическая – длинные транзакции с большими запросов, и там много агрегатных запросов. То есть я не прошу узнать год рождения конкретного человека, а обычно хочу узнать численность изменения по годам и районам от 1914 года до этого. Такие запосы обычно плохо выполняются над хорошо нормализованными данными.

Прежде чем ломать схему БД, надо сделать её сначала хорошей.

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

1NF – 2NF – 3NF – BCNF – 4NF – 5NF

1NF – конструкция, которая сущвует по историческим причинам, её ввёл Кодд, и по определениям лектора, они всегда не меньше первой нормальной формы

5NF – дальше улучшить свойства невозможно с помошью этого подъода

BCNF – придумали улучшенную формулировку НФ, которая принямала во внимание ...

БД 20.10.06

Лектор не читает лекцию, если на неё приходит менее 3 человек

2НФ

СЛУЖАЩИЕ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_УРОВ, СЛУ_ЗАРП, ПРО_НОМ, СЛУ_ЗАДАН}

СЛУ_УРОВ – разряд, Уровень служащего – определяет размер зарплаты

СЛУ_ЗАДАН – задание

Зависимости:

Таблица:

Кодд называет это аномалиями обновления, когда есть зависимости от части ключа, когда при изменениях надо делать дополнительные действия.

Тут есть ошибка добавления, так как считается, что человек может имеет задание, когда берём на работу. - на самом деле это не так. Проблема возникает в том

Удаление – человек завершает работу над последним проектом или удаляем последнего человека из проекта.

Изменение – при измении уровня человека надо поменять его во всех кортежах.

Номер проекта – характеристика проекта.

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

СЛУЖ {СЛУ_НОМ, СЛУ_ЗАРП, СЛУ_УРОВ}

СЛУЖ_ПРО_ЗАДАН {СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН}

В результате получаем хорошие ФЗ.

Если где-то при проектировании попалось бинарное отношение, то на него можно больше внимания не обращать. Они обладают всеми хорошие свойствами.

После выполнения такой декомпозиции все неприятноти пропали. Мы можем запросто принять нового человека. Мы можем спокойно оставить данные о человеке, который перестаёт учавствует в проектах. И если у человека меняется разряд, то это надо изменить только в одном месте. И теперь мы в этой БД можно сохранять такую информацию, которые мы не могли сохранять раньше. Более того, те кортежи, у которых не найдётся пара, не попадут в соединение.

Мы получили БД, которая в 2НФ.

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

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

Если посмотреть на СЛУЖ, то там всё равно есть аномалии обновления. Там зарплата зависит от уровня. Эффекты те же самые. Может быть потеряна об информации о соотв разряда и зарплаты, может поменяться зарплата за разряд. Зарплата является характеристикой не человека, а разряда. Тут проблема тоже решается простой декомпозицией.

СЛУЖ1 {СЛУ_НОМ, СЛУ_УРОВ}

УРОВ {СЛУ_УРОВ, СЛУ_ЗАРП}

В рез-те получим два бинарных отношения. На этом нормализацию можно закончить.

Мы получили 3НФ.

3НФ – это когда перем отн в 2НФ и каждый неключевой атрибут нетранзитивно зависит от возм ключа.

ФЗ называется нетранзитивной, если она не является транзитивной.

Как правило, на 3 НФ проектирование заканчивается. Даже несмотря на то, что на практике часто бывают отношения,Ю в которых много ключей, обычно эти ключи не связаны.

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

В действительности можно формально одно и то же отношение приводить к 3НФ разными способами. То, что нарисовал лектор – хороший способ. Мы получили в результате две рпоекции, которвые могут обновляться независимо друг от друга. Но может быть другая позиция:

СЛУЖ1 {СЛУ_НОМ, СЛУ_УРОВ}

СЛУЖ_ЗАРП {СЛУ_НОМ, СЛУ_ЗАРП}

Тут всё вроде правильно, но аномалии остаются. Проблема в том, что мы потеряли ФЗ СЛУ_УРОВ -> СЛУ_ЗАРП.

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

Теорема Риссанена (о независимых проекциях). Проекции r1 и r2 отношения r являются независимыми т и тт, когда

1. Каждая ФЗ в r логически следует из ФЗ в r1 и r2

2. Общие атрибуты r1 и r2 образуют возможный ключ хотя бы в одном из них

Лектор сам удивляется, почему он не будет её доказывать, но он решил, что доказывать её не надо.

Атомарными назыв отношения, которые невозможно декомпозировать на независимые проекции.

Пример:

СЛУЖ2 {СЛУ_НОМ, СЛУ_ЗАРП, ПРО_НОМ}

Конечно, мы можем разбить это отношение на два, это может принести вам счастье, но аномалий здесь и так нет.

Если делаем декомп в 3НФ, то надо, чтобы проекции были независимые. Для этого надо помнить теорему Р. Есть понытие атомарного отношения, которое нельзя декомп. Хорошо, ели есть атомарные, но если их нет, то это не есть плохо.

//педедыв

Через 4 занятия будет контрольная. Неявка на контрольную означает вероятность, что её придётся писать на экзамене.

В том случае, когда воз ключей несколько, далека не всегда это приводит к неприятностяям. И вот Б. И К. Ввели дополнительную НФ, воторая охватывает всё, что было в первых двух, но и ещё немного. Она охватывает случай, когда у ключи сост из неск атрибутов и даже когда эти атрибуты пересекаются.

Само по себе изм. Возможного ключа – не такая страшная вещь. Если при изм уник не меняется, то всё нормально. Да, придётся делать каскадное обновление (обновить все ссылки на этот ключ). В некрых случаях изменения в возможных ключах может приводить к аномалиям.

СЛУЖ_ПРО_ЗАДАН {СЛУ_НОМ, СЛУ_ИМЯ, ПРО_НОМ, СЛУ_ЗАДАН}

Формально требования первых 3 нф соблюдаются.

BCNF:

Перем отн в BCNF т. и т. т., когда у нетривиальной и минимальной ФЗ детерминантом является возможный ключ.

СЛУЖ_НОМ_ИМЯ {СЛУ_НОМ, СЛУ_ИМЯ}

СЛУЖ_НОМ_ПРО_ЗАДАН {СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН}

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

Вопрос, нужно ли всегда к этому (к BCNF) стремиться.

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

2. Задание могут выполнять несколько служащих

Возм ключи:

{СЛУ_НОМ, ПРО_НОМ}

{СЛУ_НОМ, СЛУ_ЗАДАН}

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

СЛУЖ_НОМ_ЗАДАН {СЛУ_НОМ, СЛУ_ЗАДАН}

ПРО_НОМ_ЗАДАН {СЛУ_ЗАДАН, ПРО_НОМ}

Вроде бы всё нормально, но. Каждый может выполнять в каждом проекте только одно задание. Поэтому, если мы хотим добавить кортеж 2934, D, то мы этого сделать не можем, атк как он уже выполняет задание A. Мы получили две проекции, которые не явл независимыми. Получается, чтло в исх отношении были аномалии и оно не было нормализовано, но нормализовать его не удаётся. Более того, она не удовл теореме Р. Поэтому 3НФ всегда можно получить, а BCNF – нет. И нужно определиться, что лучше – аномалии обновления или ограничения в БД.

Наличие перекрывающихся ключей не всегда мешает находиться в BCNF. От предыдущего он отличается тем, что в одном задании только один человек. Ключи здесь перекрываются, а BCNF выполняется. Легко видеть, что этому отношению, со схемой, которая была ранее, аномалии обновления не свойствены.

ФЗ являются основными во всех отношениях. И в определениях – они простые, и в утверждениях. Просто потому, что человек к понятию фугкция хорошо приспособлен. Ем не менее бывают случаи, когда трив зависимочтей нет, а аномалии обновления случаются. Пример: когда есть таблица, в которой перечислены все лектора, все учебные курсы, и все учебники. Три поля: имя курса, имя препода, имя учебника. Ограничение: все преподы, которые читают курс, должны пользоваться одними и теми учебниками. Это то, что называется многозначной зависимостью. В действительности, Кузнецов и Марков зависят исключительно от предмета, БД. У курса фик кол-во преподов, фик количество учебников. Эта зависимость назыв многозначной. И если она есть, то получается не очень-то здорово. В этом отношении есть только один возм ключ, который совпадает с заголовком. Тем не менее, аномалии возникают. Вот приходит распоряжение от Минобразовании: предписано в качестве основного учебника по курсу БД надо использовать учебник Васи Пупкина. Но пока не найдётся идиот, который не согласится по этой книге, в ьбазе эту информацию сохранить нельзя. С этим разобрался ... . Вокруг многозначных зависимостей есть некоторая теория, которая похожа на теорию ФЗ. (Фейджин). На след лекции лектор приведёт два утверждения (т. и лемму Фейджина), покажет, из-за чего возникает некая громоздкость, но всё останется также просто.

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

Список файлов лекций