СЛУЖАЩИЕ_ПРОЕКТЫ

Корректные и некорректные декомпозиции отношений. Теорема Хита

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

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

На рис. 6.3 приведены две возможные декомпозиции отношения СЛУЖАЩИЕ_ПРОЕКТЫ(для экономии места мы сократили и слегка изменили тело отношения с рис. 6.1).

СЛУ_НОМ	СЛУ_ИМЯ	СЛУ_ЗАРП	ПРО_НОМ	ПРОЕКТ_РУК
	Иванов	22400.00		Иванов
	Иваненко	22000.00		Иваненко

Декомпозиция (1). Отношения СЛУЖ и СЛУ_ПРО

СЛУ_НОМ	СЛУ_ИМЯ	СЛУ_ЗАРП
	Иванов	22400.00
	Иваненко	22000.00

СЛУ_НОМ	ПРО_НОМ	ПРОЕКТ_РУК
		Иванов
		Иваненко

Декомпозиция (2). Отношения СЛУЖ и ЗАРП_ПРО

СЛУ_НОМ	СЛУ_ИМЯ	СЛУ_ЗАРП
	Иванов	11,400
	Иваненко	11,400

СЛУ_ЗАРП	ПРО_НОМ	ПРОЕКТ_РУК
11,400		Иванов
11,400		Иваненко

Рис. 6.3. Две возможные декомпозиции отношения СЛУЖАЩИЕ_ПРОЕКТЫ

Анализ рис. 6.3 показывает, что в случае декомпозиции 1 мы не потеряли информацию о служащих – про каждого из них можно узнать имя, размер зарплаты, номер выполняемого проекта и имя руководителя проекта. Вторая декомпозиция не дает возможности получить данные о проекте сслужащего, поскольку Иванов и Иваненко получают одинаковую зарплату, следовательно, эта декомпозиция приводит к потере информации. Что же привело к тому, что одна декомпозиция является декомпозицией без потерь, а вторая – нет?

Во-первых, заметим, что реально при проведении декомпозиции мы использовали операцию взятия проекции. Каждое из отношений СЛУЖ, СЛУ_ПРОи ЗАРП _ ПРОявляется проекцией исходного отношения СЛУЖАЩИЕ_ПРОЕКТЫ. В случае декомпозиции (1) отсутствие потери информации означает, что в результате естественного соединения отношений СЛУЖи СЛУ_ПРОмы гарантированно получим отношение, заголовок и тело которого совпадают с заголовком и телом отношения СЛУЖАЩИЕ_ПРОЕКТЫ. Следует отметить, что это произойдет для любых допустимых (и согласованных) значений переменных отношений СЛУЖАЩИЕ_ПРОЕКТЫ, СЛУЖ и СЛУ_ПРО, поскольку у всех этих переменных атрибут СЛУ_НОМ является возможным ключом.Однако если выполнить естественное соединение отношений СЛУи ЗАРП _ ПРО, то будет получено отношение, показанное на рис. 6.4.

СЛУ_НОМ	СЛУ_ИМЯ	СЛУ_ЗАРП	ПРО_НОМ	ПРОЕКТ_РУК
	Иванов	22400.00		Иванов
	Иваненко	22000.00		Иваненко
	Иванов	22400.00		Иваненко
	Иваненко	22000.00		Иванов

Рис. 6.4. Результат естественного соединения отношений СЛУЖ и ЗАРП_ПРО

Схема этого отношения, естественно (поскольку соединение – естественное), совпадает со схемой отношения СЛУЖАЩИЕ_ПРОЕКТЫ, но в теле появились лишние кортежи, наличие которых и приводит к утрате исходной информации. Интуитивно понятно, что это происходит потому, что в отношении ЗАРП _ ПРОотсутствуют функциональные зависимости СЛУ_ЗАРП®ПРО_НОМи СЛУ_ЗАРП® ПРОЕКТ_РУК, но точно наличие потерь информации в этом случае мы объясним несколько позже.

Корректность же декомпозиции 1 следует из теоремы Хита:

Теорема Хита.

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

Доказательство: Во-первых, докажем, что в теле результате естественного соединения (обозначим этот результат через r1) содержатся все кортежи тела отношения r. Действительно, пусть кортеж { a, b, c } Î r. Тогда по определению операции взятия проекции { a, b } Î (r PROJECT { A, B }) и { a, с } Î (r PROJECT { A, С }). Следовательно, { a, b, c } Î r1. Теперь докажем, что в теле результата естественного соединения нет лишних кортежей, т.е., что если кортеж { a, b, c } Î r1, то { a, b, c } Î r. Если { a, b, c } Î r1, то существуют { 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 }.

Для иллюстрации общего случая применения теоремы Хита рассмотрим отношение СЛУЖАЩИЕ_ОТДЕЛЫ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_ОТД, ПРО_НОМ} (рис. 6.5). Атрибут СЛУ_ОТД содержит номера отделов, в которых работают служащие, а ПРО_НОМ – номера проектов, в которых служащие принимают участие. Каждый служащие работает в одном и только одном отделе, т.е. имеется FD СЛУ_НОМ ® СЛУ_ОТД, но один служащий может участвовать в нескольких проектах.

Дата добавления: 2014-01-03