3.7.6 Восстановление информации из декомпозиции

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

Упростим ситуацию: рассмотрим отношение Л со схемой {А, В, Q и функиио-н;Ц1ьной зависимостью В-> С, нарушающей BCNF. Здесь, как и в примере 3.37, может существовать транзитивная цепь з;1висимостей, содержащая другую функциональную зависимость А-> В. В таком случае [А] - единственный ключ, и левая часть зависимости С не является надключом. Другая возможность состоит в том. что й- С-единственная нетривиальная зависимость и wikciom служит [А. В]. Но и в этом случае левая часть В С не является надключом. В любом случае требуемая декомпозиция, основанная на зависимости В- С, делит атрибуты на (/I, В) н \В.С).

с:о единение

проекция

Рнс. 3.S7. Соединении децх кортежей из проацироеонньа отношений

Пусть / - кортеж в Л и / (а, Ь, с), где а, Ь \л с - компоненты / для агрибутов А. В и С соответственно. Кортеж / проецируется как (й, Ь) дпи отношения со сче-.мой U1, В\ и как (А. с) для отнои1ения со схемой \В, С\.

Кортеж из [А, В] можно соединить с кортежем из \В. С) при условии, что они совпадают по компоненту В. Так, соединение (о, Л) с ф. с) дает исхо ный кортеж t=(a.b.c). Независимо от того, с какого кортежа / мы начинали, можно всегда соединить его проекции и снова получить i.

Однако восста1ювлсиие исходных кортежей ие гарантирует, что исходное отно-uienne /? правильно представлено лекомпоз1Н1ией. Что произойдет, если было два кортежа Л, например / = (а. h. с) и v = {d, Ь, е)? Проекция i на {А, В} дает и = (а, Ь). я проекция I- на {В. Q дает w=(h,e). как показано на рис. 3.37.

Кортежи и и If соединяются, так как они совпадают по В, и получается кортеж .\-= (д. Ь, е). Может ли х бытгь фиктивным кортежем, т.е. допустимо ли, что (о, Л, е) НС является кортежем Я?

Отист отрицательный, так как для R установлена функциональная зависимость

С. Вспомните, ведь она означает, что любые два кортежа R, совпадающие по компонентам В, должны совпадать и по компонентам С, Поскольку t к v совпадают по компонентам В (в них входит Ь), они совпадают и по компонентам С, Это значит, что с=е, т.е. два значения, которые мы считали различными, на самом деле совпадают. Значит, (й, Ь, е) совпадает с (п, Л, с), т.е. х = t.

Поскольку / входит в R, хтоже должен быть в R. Другими словами, пока функ-цнонапьная зависимость В- С истинна, соединение двух проецированных кортежей не может породить фиктивный кортеж. Более того, каждый полученный в результате соединения кортеж обязательно будет кортежем R.

Приведенный выще аргумент действует и в общем случае. Предполагалось, что Л, В и С - единичные атрибуты, но такое же обоснование применимо к множествам атрибутов. Возьмем любую зависимость, нарушающую BCNF, и пусть В-атрибуты левой части. С - атрибуты, которые находятся в правой части, но не входят в левую, к А - атрибуты, не входящие ни в одну из частей этой зависимости. Тогда можно сделать следующее заключение.

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

Если при декомпозиции отношений применяется метод, не основанный на функциональной зависимости, восстановить исходное отношение не всегда возможно. Приведем пример.

Пример S.41. Рассмотрим отношение R с прежней схемой [А, В, Q, но без зависимости В -> С. Оно может состоять из двух кортежей:

Проекциями R на отношения со схемами {А, В) и {В, Q будут

соответственно. Поскольку значение 2 атрибута В встречается во всех четы1зех кортежах, каждый кортеж одного отношения соединяется с обоими кортежами другого. Поэтому при попытке восстановить R получаем

I 2 h 2 2

Мы получаем слишком много -два фиктивных кортежа (1,2,5) и (4,2,3), которых не было ъ R. □

9 в ЭТО.М примере предполагается, что не существует двух идущих в прокате фильмов с одним иазпзнпем. хотя ранее предполагалось, что могуг быть фильмы с одним II тем же назианисм, сдел.1нные в ixdHbie голы.

3.7.7 Третья нормальная форма

Иногда трудности иызпапы тем. что схема отношения п ее записимости не \доп.пстпоряют BCNF. но эту схему 1гежелате.льно разлагать дш1ее. Приведем типич-ньи1 пример-Пример S.42. Рассмотрим отношение Bookings с атрибутами: I) title - название фильма:

3) theater - иазваиис кинотеатра, где демонстрируется фильм;

3) city - город, в котором находится кинотеатр.

Кортеж (т. г. с) означает, что фильм т сейчас демонстрируется в кинотеатре t города с.

Можно установить следующие зависимости:

theater -> city title city - theater

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

Сначала найдем ключи. Ни один атрибут сам по себе не является ключом. Например, title не ключ, так как фильм может демонстрироваться одновременно п нссколькнх кинотеатрах и нескольких городах. Атрибут theater тоже не является ключом. Несмотря на то что theater функинонально определяет city, есть кинотеатры, в нескольких залах которых демонстрируются разные фильмы одновременно. Поэтому theater не определяет title. И наконеи, city не является ключом, так как в городах обычно несколько кинотеатров, в которых идет множесгво фильмов.

Ключами могут быть два или три атрибута вместе. Ясно, что {title, city} - ключ, поскольку в силу заданной зависимости эти атрибуты определяют theater.

1Слючом яаляется и {theater, title}. Чтобы убедиться в этом, начнем с зависимости theater city. Из нее по правилу пополнения (см. упражнение З.б.З.а) получается theater, title-> city. Интуитивно ясно, что если один атрибут theater функционально определяет city, то уж theater и title тем более.

Оставшаяся пара атрибутов, city и theater, функционально не определяет title, поэтому не является ключом. Итак, существует только два ключа:

{title, city} {theater, title}

Нарушение BCNF очевидно. Была задана функциональная зависимость theater -> city, но ее левая часть ие является надключом. Значит, мы пытались применить разбиение иа два отношения

{theater, city} [theater, title}

нспопьзуя нарум1аюшую BCNF зависимость.

Проблема здесь связана с функциональной зависимостью title city -> theater. Для по.пученных при декомпозиции схем пюпт существовать текущие отношения,