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

Эта одна из первых работ, посвященных применению теории зависимостей для широкого круга других дисциплин. Этому также посвящена публикация [10.8] и несколько работ, упомянутых в списках литературы в главе 12.

10.4. Codd E.F. Further Normalization of the Data Base Relational Model Data Base Systems, Courant Computer Science Symposia Series 6. - Englewood Cliffs, N.J.: Prentice-Hall, 1972.

Впервые представлена концепция функциональной зависимости (не считая более раннего упоминания в одном из внутренних документов фирмы IBM). Понятие дальнейшая нормализация (Further Normalization), приведенное в заголовке, относится к некоторому типу специализированного макета базы данных, обсуждаемого в главе 11 (назначение этой статьи заключалось в демонстрации возможности использования идеи функциональной зависимости для решения проблем проектирования базы данных). Действительно, функциональные зависимости представляют собой одну из первых попыток разрешения этой проблемы. Однако идея ФЗ с тех пор доказала свою полезность и для более широкого практического применения.

10.5. Codd E.F. Normalized Data Base Structure: A Brief Tutorial Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access, and Control. - San Diego, Calif., November, 1971.

Вводное изложение идей, представленных в [10.4].

10.6. Darwen Н. The Role of Functional Dependence in Query Decomposition C.J. Date and H. Darwen. Relational Database Writings 1989-1991.- Reading, Mass.: Addison-Wesley, 1992.

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

могут использоваться для значительного повышения производительности СУБД, ее функциональности и удобства пользования.

10.7. Darwen Н. OObservations of а Relational Bigot Presentation to BCS Special Interest Group on Format Aspects of Computing Science. - London, UK, December, 1990.

10.8. Fagin R. Functional Dependencies in a Relational Database and Prepositional Logic IBM J.R&D. - November, 1977. - 21, № 6.

Показано, что аксиомы Армстронга [10.1] строго эквивалентны системе импликационных утверждений в логике высказываний. Иначе говоря, задается отображение между функциональными зависимостями и утверждениями в логике высказываний, а затем показывается, что данная зависимость f является последовательностью заданного множества зависимостей S тогда и только тогда, когда высказывание, соответствуюшее f, является логическим следствием множества высказываний, соответствуюших множеству S.

10.9. Lucchesi C.L., Osbom S.L. Candidate Keys for Relations J. Сотр. and Sys. Sciences. - 1978. - 17, № 2.

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

Ответы к некоторым упражнениям

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

10.5.

1. А -> В (дано)

2. С -> D (дано)

3. А -> В п С (зависимость соединения, 1)

4. С-В->С-В (самоопределение)

5. Au(C-B)->(BnC)u(C-B) (композиция, 3, 4)

6. Аи(С-В)->С (упрощение, 5)

7. Au(C-B)->D (транзитивность, 6, 2)

8. Au(C-B)->BuD (композиция, 1,7)

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

Использованные для доказательства правила указаны в скобках. Среди них есть правила, которые являются особыми случаями теоремы Дарвена: объединение, транзитивность, композиция и дополнение. Таким же особым случаем теоремы Дарвена является следующее полезное правило.

Если А -> В и АВ -> С, то А -> С.

10.7. Ниже приведен полный набор функциональных зависимостей (т.е. замыкание) для переменной-отношения SP.

SI, Р, QTY } -> { S#, Р, QTY }

SI, Р#, QTY } -> { SI, Р }

St, PI, QTY } { PI, QTY }

SI, PI, QTY } { SI, QTY }

SI, PI, QTY } -> { SI }

SI, Pt, QTY } { PI }

SI, PI, QTY } -> { QTY }

SI, PI, QTY } -> { }

SI, PI } -{ SI, PI, QTY }

SI, PI } { SI, PI }

SI, PI } -> { PI, QTY }

SI, PI } -> { SI, QTY }

SI, PI } -> { SI }

SI, PI } { PI }

SI, PI } { QTY }

SI, PI } -> { }

PI, QTY } { PI, QTY }

PI, QTY } -> { PI }

PI, QTY } { QTY }

Pt, QTY } { }

SI, QTY } -> { SI, QTY }

SI, QTY } { SI }

SI, QTY } { QTY }

SI, QTY } { }

SI } { SI } SI } -> { }

PI } { PI } Pt } { }

QTYt } { QTYI } QTYI } { }

} -> { }

10.8. {A,C} = {A, В, С, D, E}. Ha вторую часть вопроса следует дать утвердительный ответ.

10.11.Они эквивалентны. Пронумеруем функциональные зависимости из первого множества следующим образом.

1. А -> В

2. АВ -> С