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

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

Благодаря наличию исчерпывающего и полного множества правил вывода различных функциональных зависимостей, работать с ними удобнее, чем с ограничениями целостности вообще. В списках рекомендуемой литературы в конце этой и главы 12 даны ссылки на работы, в которых описывается несколько других типов ограничений (MVD, JD и 1ND); для них также существуют подобные наборы правил вывода. Однако в данной книге другие существующие типы ограничений столь же подробно и полно, как функциональные зависимости, не рассматриваются.

Упражнения

10.1. Пусть R является переменной-отношением степени п. Каково максимальное количество функциональных зависимостей (как тривиальных, так и нетривиальных), которые могут выполняться для переменной-отношения R?

10.2. Что конкретно имеется в виду, когда говорится, что правила Армстронга полны и исчерпывающи?

10.3. Докажите правила рефлексивности, дополнения и транзитивности, используя только определение функциональной зависимости.

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

10.5. Докажите общую теорему объединения, предложенную Дарвеном. Какие из перечисленных выше правил потребуются для этого? Какие правила можно вывести в виде особых случаев этой теоремы?

10.6. Дайте определение для а) замыкания множества функциональных зависимостей; б) замыкания множества атрибутов для заданного множества функциональных зависимостей.

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

10.8. Ниже приведено множество функциональных зависимостей, имеющих место для переменной-отношения R{A,B,C,D,E,F,G}.

А -> В ВС DE AEF G

Вычислите замыкание {А,С} для данного множества функциональных зависимостей. Подразумевается ли зависимость АСЕ -> DG одной из функциональных зависимостей этого множества?

10.9. Что означает понятие эквивалентности двух множеств функциональных зависимостей S1 и S2?

10.10.Что означает понятие неприводимости множества функциональных зависимостей? 10.П.Определите, эквивалентны ли два приведенных ниже множества функциональных зависимостей, установленных для переменной-отношения R{A,B,C,D,E}.

1. АВ АВС D->AC D->E

2. А -> ВС D -> АЕ

10.12.Найдите неприводимое покрытие приведенного ниже множества функциональных зависимостей, заданных для переменной-отношения R{A,B,C,D,E,F}.

АВ -> С С -> А ВС D ACD -> В BE -> С СЕ FA CF BD D EF

10.13.В переменной-отношении TIMETABLE определены перечисленные ниже атрибуты. D День недели (1-5) Р Период времени в течение дня (1-8) С Номер класса Т Имя учителя L Название урока

Кортеж {D:d, Р:р, С:с, T:t, L:l} является элементом этой переменной-отношения тогда и только тогда, когда урок 1 проводится учителем t в классе с в момент {D:d, Р:р}. Предположим, что длительность всех уроков равна одному периоду времени и, кроме того, каждый урок имеет название, уникальное по отношению ко всем урокам этой недели. Какие функциональные зависимости выполняются для этой переменной-отношения? Какие потенциальные ключи сушествуют для этой переменной-отношения?

10.14. Пусть задана переменная-отношение NADDR с атрибутами NAME (уникальное имя), STREET (улица), CITY (город), STATE (штат) и ZIP (индекс), где каждому индексу соответствует только один город и штат, а каждой улице, городу и штату соответствует только один индекс. Найдите неприводимое множество функциональных зависимостей для этой переменной-отношения. Какие потенциальные ключи существуют для этой переменной-отношения?

10.15.Пусть дана переменная-отношение R с атрибутами {A,B,C,D,E,F,G,H,I,J}, для которой выполняется приведенное ниже множество функциональных зависимостей.

ABD -> Е АВ -> G В -> F

с -> J CJ -> I G -> H

Является ли это множество неприводимым? Какие потенциальные ключи существуют для данной переменной-отношения?

Список литературы

юл. Armstrong W. W. Dependency Structures of Data Base Relationships Proc. IFIP Congress. - Stockholm, Sweden, 1974.

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

10.2. Casanova М.А., Fagin R., Papadimitriou С.Н. Inclusion Dependencies and Their Interaction with Functional Dependencies Proc. 1st ACM SIGACT-SIGMOD Symposium on Principles of Database Systems. - Los Angeles, Calif, March, 1982. Зависимости включения (inclusion dependencies - INDs) являются обобщением концепции ограничений целостности. Например, зависимость включения типа

SP.S# -> s.s#

(здесь символическая запись содержит несколько более длинную стрелку, подчеркивающую, что это зависимость другого типа) означает, что множество значений атрибута SP.St должно быть подмножеством (необязательно собственным подмножеством) множества значений атрибута S.SI. Это, конечно, частный случай ограничения целостности, в общем же случае для зависимости включения не существует никаких Офаничений на то, что левая часть является внешним ключом, а правая - потенциальным.

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

1. А-> А.

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

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

10.3. Casey R.G., Delobel С. Decomposition of а Data Base and the Theory of Boolean Switching Functions IBM J. R&D. - September, 1973. - 17, № 5.

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