Студопедия — Корректные и некорректные декомпозиции отношений. Теорема Хита (с доказательством). Минимально зависимые атрибуты.
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Корректные и некорректные декомпозиции отношений. Теорема Хита (с доказательством). Минимально зависимые атрибуты.






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

 

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

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

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

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

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

Доказательство.

Прежде всего, докажем, что в теле результата естественного соединения (обозначим этот результат через 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 AB, то b = b* и, следовательно, {a, b, c} = {a, b*, c}. Конец доказательства.

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








Дата добавления: 2015-09-15; просмотров: 1485. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

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

Вопрос 1. Коллективные средства защиты: вентиляция, освещение, защита от шума и вибрации Коллективные средства защиты: вентиляция, освещение, защита от шума и вибрации К коллективным средствам защиты относятся: вентиляция, отопление, освещение, защита от шума и вибрации...

Задержки и неисправности пистолета Макарова 1.Что может произойти при стрельбе из пистолета, если загрязнятся пазы на рамке...

Кишечный шов (Ламбера, Альберта, Шмидена, Матешука) Кишечный шов– это способ соединения кишечной стенки. В основе кишечного шва лежит принцип футлярного строения кишечной стенки...

Принципы резекции желудка по типу Бильрот 1, Бильрот 2; операция Гофмейстера-Финстерера. Гастрэктомия Резекция желудка – удаление части желудка: а) дистальная – удаляют 2/3 желудка б) проксимальная – удаляют 95% желудка. Показания...

Ваготомия. Дренирующие операции Ваготомия – денервация зон желудка, секретирующих соляную кислоту, путем пересечения блуждающих нервов или их ветвей...

Studopedia.info - Студопедия - 2014-2024 год . (0.012 сек.) русская версия | украинская версия