inf

1)hH; Bi = hH1; B1i hH2; B2i.

2)H1 è H2 не имеют общих им¼н атрибутов.

3)H := H1 [ H2, B := fs [ tj s 2 B1; t 2 B2g.

Проекция (), .

1)hH1; B1i = hH; Bi(a1; : : : ; am) = a1;:::;am(hH; Bi).

2)a1; : : : ; am имена некоторых атрибутов из заголовка H.

3)H1 := fha1; D1i; : : : ; ham; Dmig H, B1 := fs 2 T (H1)j 9t(s [ t 2 B)g. Следует отметить, что некоторые авторы для обозначения проекции используют фигурные или прямоугольные скобки: Rfa1; : : : ; amg èëè R[a1; : : : ; am].

Переименование [], .

1)hH1; B1i = a1=a(hH; Bi) = hH; Bi[a1=a].

2)a1 не является именем никакого атрибута из заголовка H.

3)Если a не является именем атрибута в H, то H1 := H è B1 := B.

Пусть a является именем некоторого атрибута ha; Di в H. Тогда H1 := (H n fha; Dig) [ fha1; Dig, B1 := ft[a1=a]j t 2 Bg, ãäå t[a1=a] := (t nfha; t(a)ig) [fha1; t(a)ig. Иными словами, переименование состоит в том, что имя a заменяется на новое имя a1 как в зоголовке, так и во всех кортежах отношения.

Выбор (или ограничение) .

Пусть hH; Bi отношение, ha1; D1i; ha2; D2i 2 H атрибуты (необязательно различныe). Атомарным условием выбора (или просто атомом) называется логическая формула вида a1P a2 èëè a1P v, где v константа, P допустимый бинарный предикат между элементами доменов D1 è D2 или соответственно между элементами домена D1 и константой v. Обычно в качестве допустимых предикатов берутся операции сравнения f<; ; =; ; >g. Их

семантика может зависеть от вида доменов: например, на числовых доменах это обычные операции сравнения чисел, на строковых доменах сравнения по лексикографическому порядку и т.д. Условие выбора определяется по индукции:

База: Любой атом является условием выбора.

Шаг: Если и условия выбора, то ^ , ^ - условия выбора; если условие выбора, то : условие выбора.

Иными словами, условие выбора это некая бескванторная формула логики предикатов, где в качестве предметных переменных фигурируют имена атрибутов, а предикатными символами являются символы допустимых операций сравнения. Условие выбора мож-

но применить к любому кортежу t 2 B. А именно, через (t) обозначим высказывание, которое получается из подстановкой конкретного значения a(t) вместо каждого имени атрибута a, входящего в .

1)hH1; B1i = (hH; Bi).

2)допустимое условие выбора.

3)H1 := H, B1 = ft 2 Bj (t) истинно в Bg.

2.2.2Другие операции

(Естественное) соединение (джойн) ./.

1)hH; Bi = hH1; B1i ./ hH2; B2i:

2)Атрибуты в H1 è H2 с одинаковыми именами совпадают (то есть одинаковым именам

соответствуют одинаковые домены).

3) H := H1 [H2, B := fs[tj s 2 B1 ^t 2 B2 ^8a 2 N(H)((ha; v1i 2 s^ha; v2i 2 t) ) v1 = v2)g. Иными словами, B состоит из объединений кортежей из B1 è B2, у которых совпадают значения общих атрибутов.

Соединение отношений R = hH1; B1i è S = hH2; B2i можно выразить с помощью простейших реляционных операций следующим образом. Пусть a1; : : : ; an имена атрибутов èç H1 \ H2, b1; : : : ; bk имена атрибутов из H1 n H2, c1; : : : ; cl имена атрибутов из H2 n H1. Пусть, кроме того, x1; : : : ; xn произвольные имена, которые не встречаются среди имен атрибутов в R и S. Вначале переименуем общие атрибуты в S:

T := S[x1=a1; : : : ; xn=an] = S[x1=a1] [xn=an]:

Далее, возьмем композицию декартова произведения и ограничения:

P := (R T ); ãäå := (a1 = x1 ^ ^ an = xn):

Оста¼тся взять проекцию, чтобы избавиться от лишних переименованных атрибутов:

R ./ S := P (a1; : : : ; an; b1; : : : ; bk; c1; : : : ; cl):

Глава 3

Нормализация баз данных

3.1Функциональные зависимости и декомпозиция

3.1.1Функциональные зависимости

Пусть H фиксированная схема (заголовок), X; Y H произвольные наборы атрибутов из H. Упорядоченную пару hX; Y i назов¼м функциональной зависимостью (или просто зависимостью) и обозначим е¼ X ! Y .

Определение 3.1 Пусть R = hH; Bi произвольное отношение. Говорят, что в R набор атрибутов Y функционально зависит от набора атрибутов X, или R удовлетворяет зависимости X ! Y , обозначение R j= X ! Y , если

8t1; t2 2 B(t1(X) = t2(X) ) t1(Y ) = t2(Y )):

Иными словами, R j= X ! Y , если в отношении R набор значений атрибутов из X однозначно определяет набор значений атрибутов из Y . Если R известно из контекста, то вместо R j= X ! Y пишут просто X ! Y .

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

Понятие суперкюча и ключа могут быть строго определены с помощью функциональной зависимости. Супеключ это набор атрибутов X H такой, что X ! H. Говорят,

что Y зависит от X функционально полно, если Y функционально зависит от X, но не зависит ни от какого собственного подмножества X:

X ! Y ^ (X0 X ) X0 6!Y ):

(Потенциальым) ключом называется минимальный суперключ, т.е. X ключ тогда и только тогда, когда весь заголовок H функционально полно зависит от X.

Декомпозицией отношения R = hH; Bi на наборы атрибутов X1; : : : ; Xn называется его замена на набор проекций R(X1); : : : ; R(Xn), ãäå X1 [ [ Xn = H.

Через F обозначим множество всех функциональных зависимостей, которые логически следуют из F .

Пусть A множество аксиом и/или правил вывода одних функциональных зависимостей из других. Говорят, что f выводимо из F посредством A, или f A-выводимо из F ,

обозначение F `A f, если f может быть получена (многократным) применением аксиом и правил из A к функциональным зависимостям из F . Через FA обозначим множество всех функциональных зависимостей, которые A-выводимы из F .

Множество аксиом и/или правил вывода A назов¼м полным, если F = FA. Простой полный набор правил вывода был предложен В.В. Армстронгом (1974); эти правила вывода обычно называют аксиомами Армстронга (точнее говоря, аксиомой является только первое правило):

1.Рефлексивность: если Y X, то X ! Y .

2.Добавление: если X ! Y , то X [ Z ! Y [ Z для любого Z.

3.Транзитивность: если X ! Y и Y ! Z, то X ! Z.

Функциональная зависимость X ! Y , при которой Y X, называется тривиальной.

3.1.3Многозначные функциональные зависимости

Пусть R = hH; Bi произвольное отношение со схемой (заголовком) H, X; Y H произвольные наборы атрибутов из H.

Определение 3.4 Говорят, что в R набор атрибутов Y многозначно (функционально) зависит от набора X, обозначение R j= X Y или просто X Y , если

8t1; t2 2 B(t1(X) = t2(X) ) 9s 2 B (s(X [ Y ) = t1(X [ Y )^

s(H n (X [ Y )) = t2(H n (X [ Y )):

Переформулировка:

8x 2 R(X)8y1; y2 2 R(Y )8z1; z2 2 R(H n (X [ Y ))

(x [ y1 [ z1; x [ y2 [ z2 2 B ! x [ y1 [ z2; x [ y2 [ z1 2 B):

Иными словами, Y многозначно зависит от X, если у любых двух кортежей из R с одинаковыми значениями атрибутов набора X можно менять хвосты наборы значений всех атрибутов, кроме атрибутов из наборов X и Y .

Для x 2 R(X) и z 2 R(H n (X [ Y )), обозначим через Rxz(Y ) множество кортежей y 2 R(Y ) таких, что x [ y [ z 2 R. Целесообразно привести ещ¼ одну эквивалентную переформулировку многозначной зависимости:

Лемма 3.5 (Первоначальное определение Фейджина) X Y тогда и только тогда, когда 8x 2 R(X)8z1; z2 2 R(H n (X [ Y ))Rxz1 (Y ) = Rxz2 (Y ):

16 Глава 3. Нормализация баз данных

Иными словами, Y многозначно зависит от X, если Rxz(Y ) не зависит от z, т.е. R(Y ) не зависит от значений атрибутов, не входящих в X [ Y . В этом случае говорят, что наборы атрибутов Y и H n (X [ Y ) независимы или ортогональны .

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

Теорема 3.6 (Теорема Фейджина) Пусть R произвольное отношение с заголовком H = X [ Y [ Z, где Y \ Z X. Тогда R j= X Y если и только если R = R(X [ Y ) ./ R(X [ Z).

Доказательство. Докажем достаточность, пусть R j= X Y . Обозначим R = hH; Bi, R(X [ Y ) ./ R(X [ Z) = hH1; B1i. По лемме о декомпозиции H = H1 è B B1. Докажем обратное включение B1 B. Предположим, что t 2 B1. Тогда по определению операций соединения и проекции t = t1(X [Y )[t2(X [Z) = t1(X [Y )[t2(H n(X [Y )) для некоторых t1; t2 2 B, ïðè÷¼ì t1((X [ Y ) \ (X [ Z)) = t2((X [ Y ) \ (X [ Z)), ò.å. t1 è t2 принимают одинаковые значения на одинаковых атрибутах. Так как (X [Y ) \(X [Z) = X, то t1(X) = t2(X). Но по определению многозначной зависимости X Y существует кортеж s 2 B такой, что s(X [ Y ) = t1(X [ Y ) è s(H n (X [ Y )) = t2(H n (X [ Y )). Следовательно, t = s(X [ Y ) [ s(H n (X [ Y )) = s(H) = s 2 B. Тем самым доказано включение B1 B, а значит и равенство B = B1.

Докажем теперь необходимость, пусть R = R(X [ Y ) ./ R(X [ Z). Рассмотрим произвольные t1; t2 2 B такие, что t1(X) = t2(X). Òàê êàê (X [ Y ) \ (X [ Z) = X, òî s := t1(X [Y ) [t2(X [Z) 2 R(X [Y ) ./ R(X [Z) = R, а значит s 2 B. Осталось заметить, что s удовлетворяет логическому условию из определения многозначной зависимости.

Предложение 3.7 (Свойства многозначной зависимости) Пусть R(H) фиксированное отношение, X; Y H.

(i)Åñëè X ! Y , òî X Y .

(ii)Если X [Y [Z = H и Y \Z X, то X Y тогда и только тогда, когда X Z.

(iii)Åñëè X [ Y = H, òî X Y .

(iv)Åñëè X Y è X Z, òî X Y [ Z, X Y \ Z è X Y n Z.

Доказательство. (i) Пусть X ! Y . Тогда по теореме Хита R = R(X [Y ) ./ R(X [(H nY )). Отсюда по теореме Фейджина X Y .

(ii)Заметим, что в теореме Фейджина Y и Z равнозначны. Поэтому для доказательства достаточно двукратно применить эту теорему.

(iii)следует из (ii), так как X ! ?, а потому X ?.

(iv)Рутинная проверка по определению многозначной зависимости.

Пункт (i) предыдущей леммы показывает, что функциональная сводимость частный случай многозначной сводимости.

Если Y X или X [ Y = H, то многозначная зависимость X Y называется тривиальной.

3.2Нормальные формы

Нормализация это процесс поэтапного улучшения реляционной базы данных, суть

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

лизацией иногда целесообразна денормализация сознательный отказ от декомпозиции

отношений или даже их укрупнение ради роста эффективности работы с базой данных.

3.2.1Простейшие нормальные формы

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

По определению, всякое отношение уже находится в 1NF.

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

Определение 3.8 Отношение находится во второй нормальной форме (2NF), если в н¼м каждый неключевой атрибут функционально полно зависит от каждого ключа.

Говорят, что набор атрибутов Y транзитивно зависит от набора X, если

9Z H(X ! Z ^ Z ! Y ^ Z 6!X ^ ^Y 6 Z):

Определение 3.9 Отношение находится в третьей нормальной форме (3NF), если в н¼м нет транзитивных зависимостей неключевых атрибутов от ключей.

Заметим, что по этому определению 3NF 2NF. Действительно, пусть отношение R находится в 3NF, но не находится в 2NF. Тогда некоторый неключевой атрибут A функционально неполно зависит от некоторого ключа K, т.е. существует K0 K такой, что K0 ! fAg. Тогда получаем транзитивную зависимость неключевого атрибута от ключа: K ! K0 ! fAg (K0 6!K, так как в противном случае условие минимальности не выполнено для ключа K).

Лемма 3.10 (Заниоло) Отношение находится в 3NF тогда и только тогда, когда для любой функциональной зависимости X ! Y выполнено хотя бы одно из условий: (i)

Y X, (ii) X суперключ, (iii) Y n X состоит из ключевых атрибутов.

Доказательство. Докажем необходимость, пусть отношение R находится в 3NF и пусть X ! Y такая функциональная зависимость, что Y 6 X и X не является суперключом. Расммотрим произвольный атрибут A 2 Y nX. Предположим, что A неключевой, и пусть

K ключ такой, что A 62K. Тогда получаем транзитивную зависимость K ! X ! fAg, противоречие.

(ii) Докажем достаточность. Пусть отношение не находится в 3NF, тогда в нем существует транзитивная зависимость неключевого атрибута A от ключа K: K ! X ! fAg,

причем X 6!K и fAg 6 X. Полагая Y = fAg, получаем, что условия (i) и (iii) для функциональной зависимости X ! Y не выполнены. Так как X 6!K, то X не суперключ, т.е. не выполнено и условие (ii).

2NF и 3NF были предложены Э.Ф. Коддом в 1971 г.

Определение 3.11 Отношение находится в нормальной форме Бойса-Кодда (BCNF или 3,5NF), если из любой нетривиальной зависимости X ! Y следует, что X является

суперключом.

Включение BCNF 3NF следует из леммы Заниоло заметим, что отношение находится

в BCNF тогда и только тогда, когда для любой функциональной зависимости выполняется условие (i) или (ii) из этой леммы.

В большинстве практических задач для исключения аномалий достаточно приведения всех отношений в БД к 3NF или BCNF.

3.2.2Нормальные формы высших порядков

Определение 3.12 Отношение находится в четв¼ртой нормальной форме (4NF), если из любой нетривиальной многозначной зависимости X ! Y следует, что X является

суперключом.

Так как любая функциональная зависимость частный случай многозначной зависимости, то 4NF BCNF.

Определение 3.13 Пусть R отношение с заголовком H, X1 [ [Xn = H. Отношение

(X1; : : : ; Xn), åñëè

R = R(X1) ./ ./ R(Xn)

.

Иными словами, R удовлетворяет (X1; : : : ; Xn), если декомпозиция по проекциям X1; : : : ; Xn происходит без потерь.

Зависимость соединения (X1; : : : ; Xn) называется тривиальной, если хотя бы один из наборов X1; ; Xn совпадает со всем заголовком H.

Определение 3.14 Отношение находится в пятой нормальной форме (5NF), или нормальной форме проекции-соединения (PJ/NF), если в любой нетривиальной зависимости соединения (X1; : : : ; Xn) каждый набор Xi является суперключом.

Глава 4

Язык запросов SQL

SQL (англ. Structured Query Language структурированный язык запросов ) универ-

сальный язык управления реляционными базами данных, наиболее распростран¼нный на сегодняшний день. Язык SQL, под первоначальным названием SEQUEL, был разработан Д.Д. Чемберленом и Р.Ф. Бойсом в начале 1970-х годов для реляционной базы данных IBM System R. Язык SQL был стандартизован несколько раз, первый стандарт вышел в 1986 году (SQL-86), новейший - в 2008 году (SQL:2008).

Язык SQL делится на следующие части (подъязыки):

DDL (Data De nition Language) язык определения данных;

DML (Data Manipulation Language) язык управления данными;

DCL (Data Control Language) язык определения доступа к данным;

TCL (Transaction Control Language) язык управления транзакциями.

4.1Определение данных

Операторы языка DDL:

CREATE созда¼т объект в базе данных;

ALTER изменяет структуру существующего объекта;

DRIOP удаляет объект.

4.2Управление данными

Операторы языка DDL:

SELECT осуществляет выборку данных, удовлетворяющих определ¼нным условиям;