Замыкание множества функциональных зависимостей. Аксиомы Армстронга. Замыкание множества атрибутов

Замыканием множества FD S является множество FD S⁺, включающее все FD, логически выводимые из FD множества S.

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

В отношении СЛУЖАЩИЕ_ПРОЕКТЫ имеется также пара FD СЛУ_НОМ ОТД_НОМ и ОТД_НОМ ПРОЕКТ_РУК. Из них выводится FD СЛУ_НОМ ПРОЕКТ_РУК. Заметим, что FD вида СЛУ_НОМ ПРОЕКТ_РУК называются транзитивными, поскольку ПРОЕКТ_РУК зависит от СЛУ_НОМ «транзитивно», через ПРО_НОМ.

FD A C называется транзитивной, если существует такой атрибут B, что имеются функциональные зависимости A B и B C и отсутствует функциональная зависимость C A.

Подход к решению проблемы поиска замыкания S⁺ множества FD S впервые предложил Вильям Армстронг²⁸⁾. Им был предложен набор правил вывода новых FD из существующих (эти правила обычно называют аксиомами Армстронга, хотя справедливость правил доказывается на основе определения FD). Обычно принято формулировать эти правила вывода в следующей форме. Пусть A, B и C являются (в общем случае, составными) атрибутами отношения R. Множества A, B и C могут иметь непустое пересечение. Для краткости будем обозначать через AB A UNION B. Тогда:

1. если B A, то A B (рефлексивность);
2. если A B, то AC BC (пополнение);
3. если A B и B C, то A C (транзитивность).

Истинность первой аксиомы Армстронга следует из того, что при B A FD A B является тривиальной.

Справедливость второй аксиомы докажем от противного. Предположим, что FD AC BC не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t₁ и t₂, такие, что t₁{AC} = t₂ {AC} (a), но t₁ {BC} t₂ {BC} (b) (здесь t {A} обозначает проекцию кортежа t на множество атрибутов A). По аксиоме рефлексивности из равенства (a) следует, что t₁ {A} = t₂ {A}. Поскольку имеется FD A B, должно соблюдаться равенство t₁ {B} = t₂ {B}. Тогда из неравенства (b) следует, что t₁{C} t₂ {C}, что противоречит наличию тривиальной FD AC C. Следовательно, предположение об отсутствии FD AC BC не является верным, и справедливость второй аксиомы доказана.

Аналогично докажем истинность третьей аксиомы Армстронга. Предположим, что FD A C не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t₁ и t₂, такие, что t₁ {A} = t₂ {A}, но t₁ {C} t₂ {C}. Но из наличия FD A B следует, что t₁ {B} = t₂ {B}, а потому из наличия FD B C следует, что t₁ {C} = t₂ {C}. Следовательно, предположение об отсутствии FD A C не является верным, и справедливость третьей аксиомы доказана.

Можно доказать, что система правил вывода Армстронга полна и совершенна (sound and complete) в том смысле, что для данного множества FD S любая FD, потенциально выводимая из S, может быть выведена на основе аксиом Армстронга, и применение этих аксиом не может привести к выводу лишней FD. Тем не менее Дейт по практическим соображениям предложил расширить базовый набор правил вывода еще пятью правилами:

1. A A (самодетерминированность) – прямо следует из правила (1);
2. если A BC, то A B и A C (декомпозиция) – из правила (1) следует, что BC B; по правилу (3) A B; аналогично, из BC С и правила (3) следует A C;
3. если A B и A C, то A BC (объединение) – из правила (2) следует, что A AB и AB BC; из правила (3) следует, что A BC;
4. если A B и C D, то AC BD (композиция) – из правила (2) следует, что AС BС и BC BD; из правила (3) следует, что AC BD;
5. если A BC и B D, то A BCD (накопление) – из правила (2) следует, что BС BCD; из правила (3) следует, что A BCD.

Пусть заданы отношение R, множество Z атрибутов этого отношения (подмножество заголовка R, или составной атрибут R) и некоторое множество FD S, выполняемых для R. Тогда замыканием Z над Sназывается наибольшее множество Z⁺ таких атрибутов Y отношения R, что FD Z Y входит в S⁺.

Алгоритм вычисления Z⁺ очень прост. Один из его вариантов показан на рис. 7.2.

Рис. 7.2. Алгоритм построения замыкания атрибутов над заданным множеством FD

Докажем корректность алгоритма по индукции. На нулевом шаге Z[0] = Z, FD Z Z[I], очевидно, принадлежит S⁺ (тривиальная FD «выводится» из любого множества FD). Пусть для некоторого Kвыполняется FD Z Z[K], и пусть мы нашли в S такую FD A B, что A Z[K]. Тогда можно представить Z[K]в виде AC, и, следовательно, выполняется FD Z AC. Но по правилу (8) мы имеем FD Z ACB, т.е. FD Z (Z[K] UNION B) входит во множество S⁺, что переводит нас на следующий шаг индукции.

Пусть для примера имеется отношение с заголовком {A, B, C, D, E, F} и заданным множеством FD S = {A D, AB E, BF E, CD F, E C}. Пусть требуется найти {AE}⁺ над S. На первом проходе тела цикла DOZ[1] равно AE. В теле цикла FOR EACH будут найдены FD A D и E C, и в конце цикла Z[1] станет равнымACDE. На втором проходе тела цикла DO при Z[2], равном ACDE, в теле цикла FOR EACH будет найдена FD CD F, и в конце цикла Z[2] станет равным ACDEF. Следующий проход тела цикла DO не изменит Z[3], и Z⁺({AE}⁺) будет равно ACDEF.

Алгоритм построения замыкания множества атрибутов Z над заданным множеством FD S помогает легко установить, входит ли заданная FD Z B в замыкание S⁺. Очевидно, что необходимым и достаточным условием для этого является B Z⁺, т. е. вхождение составного атрибута B в замыкание Z²⁹⁾.

Суперключом отношения R называется любое подмножество K заголовка R, включающее, по меньшей мере, хотя бы один возможный ключ R.

Одно из следствий этого определения состоит в том, что подмножество K заголовка отношения R является суперключом тогда и только тогда, когда для любого атрибута A (возможно, составного) заголовка отношения R выполняется FD K A. В терминах замыкания множества атрибутов K является суперключом тогда и только тогда, когда K⁺ совпадает с заголовком R.

Декомпозиция без потерь

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

Проекции Rj и R2 отношения R называются декомпозицией без потерь, если отношение R точно восстанавливается из них при помощи естественного соединения для любого состояния отношения R.

Теорема Хита

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

Теорема Хита: Если есть отношение R у которого есть атрибуты A, B, C, связанные зависимостью A -> B, то декомпозиция на r1(A, B) и r2(A,C) будет обратимой: R(A, B, C) = r1(A, B) join r2(A,C).

Например, вы с друзьями посидели в пабе. Имеет место отношение Pub (man, beer, payment).

man	beer	payment
Darth	Leffe Blonde	5$
Yoda	Heineken	10$
Jabba the Hutt	Amstel Light	8$

Каждый из вас пьет один определенный сорт пива. Это зависимость man -> beer.
Значит, по теореме Хита мы можем разделить данные на 2 отношения:

· man -> beer == beer_man (man, beer)

man	beer
Darth	Leffe Blonde
Yoda	Heineken
Jabba the Hutt	Amstel Light

· man -> payment == pay_man (man, payment)

man	payment
Darth	5$
Yoda	10$
Jabba the Hutt	8$

Этих данных достаточно, чтобы однозначно и правильно воссоздать оригинальное отношение Pub (man, beer, payment), используя natural join:

· beer_man JOIN pay_man = pub

P.S. На всякий случай напоминаю, что при natural join, о котором идет речь в теореме, все пары атрибутов из двух отношений, имеющих общее имя, приравниваются, а одна из пар равных атрибутов удаляется путем проекции.

Многозначные зависимости

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

Многозначная зависимость является обобщением функциональной зависимости и рассматривает соответствия между множествами значений атрибутов.

В качестве примера рассмотрим отношение ПРЕПОДАВАТЕЛЬ (ИМЯ, КУРС, УЧЕБНОЕ_ПОСОБИЕ), хранящее сведения о курсах, читаемых преодавателем, и написанных им учебниках. Пусть профессор N читает курсы "Теория упругости" и "Теория колебаний" и имеет соответствующие учебные пособия, а профессор K читает курс "Теория удара" и является автором учебников "Теория удара" и "Теоретическая механика". Тогда наше отношение будет иметь вид:

----------------------------------------------------

| ИМЯ | КУРС | УЧЕБНОЕ_ПОСОБИЕ |

----------------------------------------------------

| N | Теория упругости | Теория упругости |

| N | Теория колебаний | Теория упругости |

| N | Теория упругости | Теория колебаний |

| N | Теория колебаний | Теория колебаний |

| K | Теория удара | Теория удара |

| K | Теория удара | Теоретическая механика |

----------------------------------------------------

добавляем:

----------------------------------------------------

| K | Теория упругости | Теория удара |

| K | Теория упругости | Теоретическая механика |

----------------------------------------------------

Это отношение имеет значительную избыточность и его использование приводит к возникновению аномалии обновления. Например, добавление информации о том, что профессор K будет также читать лекции по курсу "Теория упругости" приводит к необходимости добавить два кортежа (по одному для каждого написанного им учебника) вместо одного. Тем не менее, отношение ПРЕПОДАВАТЕЛЬ находится в NFBC (ключевой атрибут - ИМЯ).

Заметим, что указанные аномалии исчезают при замене отношения ПРЕПОДАВАТЕЛЬ его проекциями:

--------------------------- -------------------------------

| ИМЯ | КУРС | | ИМЯ | УЧЕБНОЕ_ПОСОБИЕ |

--------------------------- -------------------------------

| N | Теория упругости | | N |Теория упругости |

| N | Теория колебаний | | N |Теория колебаний |

| K | Теория удара | | K |Теоретическая механика |

| K | Теория упругости | | K |Теория удара |

--------------------------- -------------------------------

Аномалия обновления возникает в данном случае потому, что в отношении ПРЕПОДАВАТЕЛЬ имеются:

1. зависимость множества значений атрибута КУРС от множества значений атрибута ИМЯ
2. зависимость множества значений атрибута УЧЕБНОЕ_ПОСОБИЕ от множества значений атрибута ИМЯ.

Такие зависимости и называются многозначными и обозначаются как

ИМЯ ->> КУРС ИМЯ ->> УЧЕБНОЕ_ПОСОБИЕ

Нетрудно показать, что многозначные зависимости всегда образуют связанные пары, поэтому их часто обозначают

ИМЯ ->> КУРС | УЧЕБНОЕ_ПОСОБИЕ

Очевидно, что каждая функциональная зависимость является многозначной, но не каждая многозначная зависимость является функциональной.

До сих пор мы предполагали, что единственной операцией, необходимой для устранения избыточности в отношении, была декомпозиция его на две проекции. Однако, существуют отношения, для которых нельзя выполнить декомпозицию без потерь на две проекции, но которые можно подвергнуть декомпозиции без потерь на три (или более) проекций. Этот факт получил названиезависимости по соединению, а такие отношения называют 3-декомпозируемые отношения (ясно, что любое отношение можно назвать "n-декомпозируемым", где n >= 2).

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

Определение пятой нормальной формы:

Отношение находится в 5НФ тогда и только тогда, когда любая зависимость по соединению в нем определяется только его возможными ключами.

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

Язык SQl

Типы данных

В языке SQL/89 поддерживаются следующие типы данных: CHARACTER, NUMERIC,DECIMAL, INTEGER, SMALLINT, FLOAT, REAL, DOUBLE PRECISION. Эти типы данных классифицируются на типы строк символов, точных чисел и приблизительных чисел.

К первому классу относится тип CHARACTER. Спецификатор типа имеет вид CHARACTER (length), где length задает длину строк данного типа. Заметим, что в SQL/89 нет типа строк переменного размера, хотя во многих реализациях они допускаются. Литеральные строки символов изображаются в виде "последовательность-символов"(например "example").

Представителями второго класса типов являются NUMERIC, DECIMAL (или DEC), INTEGER (или INT) и SMALLINT. Спецификатор типа NUMERIC имеет вид NUMERIC [(precision [, scale])]. Специфицируются точные числа, представляемые с точностью precision и масштабом scale. Здесь и далее, если опущен масштаб, то он полагается равным 0, а если опущена точность, то ее значение по умолчанию определяется в реализации.

Спецификатор типа DECIMAL (или DEC) имеет вид DECIMAL [(precision [,scale])]. Специфицируются точные числа, представленные с масштабом scale и точностью, равной или большей значения precision.

INTEGER специфицирует тип данных точных чисел с масштабом 0 и определяемой в реализации точностью. SMALLINT специфицирует тип данных точных чисел с масштабом 0 и определяемой в реализации точностью, не большей, чем точность чисел типа INTEGER.

Литеральные значения точных чисел в общем случае представляются в форме[+|-] <целое-без-знака> [.<целое-без-знака>].

Наконец, в классу типов данных приблизительных чисел относятся типы FLOAT, REAL и DOUBLE PRECISION. Спецификатор типа FLOAT имеет вид FLOAT[(precision)]. Специфицируются приблизительные числа с двоичной точностью, равной или большей значения precision.

REAL специфицирует тип данных приблизительных чисел с точностью, определенной в реализации. DOUBLE PRECISION специфицирует тип данных приблизительных чисел с точностью, определенной в реализации и большей, чем точность типа REAL.

Литеральные значения приблизительных чисел в общем случае представляются в виде <литеральное-значение-точного-числа>E<целое-со-знаком>.

Заметим, что, хотя с использованием языка SQL можно определить схему БД, содержащую данные любого из перечисленных типов, возможность использования этих данных в прикладных системах зависит от применяемого языка программирования. Весь набор типов данных можно прямо (без потребности в специальных библиотечных функциях) использовать, только если программировать на ПЛ/1. Поэтому в некоторых реализациях SQL типы данных с масштабом и точностью вообще не поддерживаются.

Хотя правила встраивания SQL в программы на языке Си не определены в SQL/89, в большинстве реализаций, поддерживающих такое встраивание, имеется следующее соответствие между типами данных SQL и типами данных Си: CHARACTER соответствует строкам Си; INTEGER соответствует long; SMALLINT соответствует short; REAL соответствует float; DOUBLE PRECISION соответствует double(именно такое соответствие утверждено в стандарте SQL/92).

Заметим еще, что в большинстве реализаций SQL поддерживаются некоторые дополнительные типы данных, например DATE, TIME, INTERVAL, MONEY. Некоторые из этих типов специфицированы в стандарте SQL/92, но в текущих реализациях синтаксические и семантические свойства таких типов могут различаться.

Запросы на выборку

Оператор выборки - это отдельный оператор языка SQL/89, позволяющий получить результат запроса в прикладной программе без использования курсора. Поэтому оператор выборки имеет синтаксис, отличающийся от синтаксиса спецификации курсора, и при выполнении оператора возникают ограничения на результат табличного выражения. Фактически, и то и другое диктуется спецификой оператора выборки как одиночного оператора SQL: при его выполнении результат должен быть помещен в переменные прикладной программы. Поэтому в операторе появляется раздел INTO, содержащий список переменных прикладной программы, и возникает то ограничение, что результирующая таблица должна содержать не более одной строки. Соответственно, результат базового табличного выражения должен содержать не более одной строки, если оператор выборки не содержит спецификации DISTINCT, и таблица, полученная применением списка выборки к результату табличного выражения, должна состоять только из строк-дубликатов, если спецификация DISTINCT задана.

Замечание: в диалекте SQL СУБД Oracle имеется расширенный вариант оператора выборки, результатом которого не обязательно является таблица из одной строки. Такое расширение не поддерживается ни в SQL/89, ни в SQL/92.

Однотабличные запросы

1) выборка всех строк и столбцов
Пример:

select * from klient
select code, fio, address from klient

2) Выборка отдельных столбцов
Пример:
Получить список наименований типов страховых случаев

select naim from tip

Отбор строк с помощью фразы where
во фразе where условие выборки строк может быть задано разными способами:
• С помощью операций отношения >, = ,5
where data between ’01.01.2011’and’31.12.2011’

Вывести коды и фамилии клиентов и общую сумму их договоров за 2011г для таких клиентов, которые заключили больше 2-х договоров за этот период.

select kod_kl, sum(summa) as sum
from dogovor
group by kod_kl
having count(*)>5
where data between ’01.01.2011’and’31.12.2011’

Упорядочение строк результирующего отношения

order by

Пример:
вывести сведения о договорах, упорядочивая их по датам, внутри дат по типам договоров и суммам.

select *
from dogovor order by data,kod_tip,summa