Теория проектирования реляционных баз данных

Цели проектирования Понизить избыточность данных Повысить надежность и достоверность данных (т.е. устранить некоторые аномалии) 2

Вопросы проектирования Какие отношения включать в состав базы данных Сколько отношений включить в состав базы данных 3

База данных ПОСТАВКА ТОВАРОВ Информация о поставщике (Номер поставщика – Sid, Имя поставщика – SName, Место дислокации – City), информация о товаре (Номер товара – Pid, Название – PName, Стоимость – Price), какой поставщик поставляет тот или иной товар и в каком Количестве – Qty. Схема отношения: ПОСТАВКА ИЗДЕЛИЙ (Sid, SName, City, Pid, PName, Price, Qty) 4

Аномалии Аномалия обновления – ошибки из-за дублирования информации Аномалия включения – ни Sid, ни Pid не могут быть опущены Аномалия удаления – возможна потеря информации Главное требование – гарантированное поддержание целостного состояния базы данных 5

Ограничения целостности Внутренние ограничения категорная целостность ссылочная целостность Явные ограничения семантические зависимости функциональные зависимости 6

Функциональные зависимости (1) R(A 1 A 2 …A n ) – схема отношения U = {A 1, A 2, …, A n } – универсальное множество атрибутов X U и Y U – некоторые подмножества множества атрибутов схемы R 7

Функциональные зависимости (2) Говорят, что Y функционально зависит от X (или X функционально определяет Y: f : X Y ) тогда и только тогда, когда для любой допустимой реализации отношения r(R) каждое значение множества атрибутов X связано в точности с одним значением множества атрибутов Y. Здесь X – детерминант, а Y – зависимость 8

Примеры 9 a) PK A 1 A 2 …A n, а также и любое подмножество атрибутов из U b) Из рассматриваемого примера ПОСТАВКА ТОВАРОВ: Sid SName Pid PName (Sid,Pid) Qty

Влияние функциональных зависимостей Если для некоторой схемы R кроме функциональной зависимости PK R существуют еще и другие, типа A B, где A R и B R, то, вообще говоря, схема отношения R будет характеризоваться некоторой избыточностью 10

Замыкание множества функциональных зависимостей (1) Пусть F – множество функциональных зависимостей для схемы отношения R, и имеется еще одна функциональная зависимость f : X Y. Говорят, что функциональная зависимость X Y логически следует из F, если для любой реализации отношения r(R), удовлетворяющей всем зависимостям из F, удовлетворяется также и зависимость X Y 11

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

Правила вывода Полны – для заданного множества F функциональных зависимостей эти правила позволяют вывести все функциональные зависимости, принадлежащие F + Надежны (исчерпывающи) – используя их, нельзя вывести из F некоторую функциональную зависимость, не принадлежащую F + 13

Обозначения R(A 1 A 2 …A n ) – схема отношения U = {A 1, A 2, …A n } – универсальное множество атрибутов X U, Y U, Z U, W U – некоторые подмножества атрибутов из U XY – объединение атрибутов: X Y XY 14

1. Рефлексивность Если имеется некоторая совокупность атрибутов X = YZ (т.е. Y есть некоторое подмножество из X), тогда X Y. Тривиальная функциональная зависимость, в которой зависимость (правая часть) содержится в детерминанте (левой части). Следствие (если Z = ): X X 15

2. Пополнение (1) Расширение левой части Если существует функциональная зависимость X Y, то XZ YZ Функциональная зависимость X Y или принадлежит F, или может быть логически выведена из F с помощью описываемых правил 16

2. Пополнение (2) Пример: дана схема отношения R(A B C D), для которой определена функциональная зависимость A B 17 Дано Следует R(ABCD)A BAC BC a1b1c1d1a1b1a1c1b1c1 a2b2c1d1a2b2a2c1b2c1 a1b1c1d2a1b1a1c1b1c1 a3b2c2d3a3b2a3c2b2c2 a1b1c2d2a1b1a1c2b1c2

3. Транзитивность Если X Y и Y W, то X W 18 Дано:Следует: R(ABCD)A BиB CA C a1b1c2d1a1b1 c2a1c2 a2b2c1d2a2b2 c1a2c1 a3b1c2d1a3b1 c2a3c2 a3b1c2d3a3b1 c2a3c2

4. Псевдотранзитивность Если X Y и YZ W, то XZ W 19 Дано:Следует: R(ABCD)A BиBC DAC D a1b1c1d1a1b1 c1d1a1c1d1 a1b1c2d2a1b1 c2d2a1c2d2 a2b2c1d1a2b2 c1d1a2c1d1 a1b1c2d2a1b1 c2d2a1c2d2

Псевдотранзитивность (вывод) Дано: X Y, YZ W. Требуется получить XZ W. В соответствии с правилом 2, из X Y следует XZ YZ. В соответствии с правилом 3, из XZ YZ (вывели) и YZ W (дано) следует XZ W. Из правила псевдо транзитивности, при Z = получим правило транзитивности 20

5. Аддитивность Если X Y и X Z, то X YZ 21 Дано:Следует: R(A(ABCD)A BиA CA BC a1b1c1d1a1b1a1c1a1b1c1 a2b2c1d1a2b2a2c1a2b2c1 a1a1b1c1d2a1b1a1c1a1b1c1 a3b3b3c2d3a3b3a3c2a3b3c2c2

Аддитивность (вывод) Доказательство Дано: X Y и X Z. Требуется получить X YZ. В соответствии с правилом 2, из X Z можно получить XY ZY (или YX YZ). В соответствии с правилом 4, так как X Y (по условию) и YX YZ (выведено), имеем XX YZ (или X YZ). 22

6. Декомпозиция Если X YZ, то X Y и X Z 23 Следует:Дано: R(A(ABCD)A BиA CA BC a1b1c1d1a1b1a1c1a1b1c1 a2b2c1d1a2b2a2c1a2b2c1 a1a1b1c1d2a1b1a1c1a1b1c1 a3b3b3c2d3a3b3a3c2a3b3c2c2

Декомпозиция (вывод) Доказательство Дано: X YZ. Требуется получить X Y и X Z. В соответствии с правилом 1 YZ Y и YZ Z. В соответствии с правилом 3, из X YZ и YZ Y следует X Y Аналогично, из X YZ и YZ Z следует X Z 24

7. Композиция Если X Y и Z W, то XZ YW 25 Дано:Следует: R(A(ABCD)A BиC DAC BD a1b1c1d1a1b1c1d1a1c1b1d1 a2b2c1d1a2b2c1d1a2c1b2d1 a1b1c1d1a1b1c1d1a1c1b1d1 a3b3c2d3a3b3c2d3a3c2b3d3d3

Композиция (вывод) Доказательство Дано: X Y и Z W. Требуется получить XZ YW. В соответствии с правилом 2, из X Y следует XZ YZ, а из Z W следует ZY WY (или YZ YW). В соответствии с правилом 3, из XZ YZ и YZ YW следует XZ YW 26

Определение ключа Если R – схема отношения с атрибутами A 1, A 2, …, A n и множеством функциональных зависимостей F, X U – некоторое подмножество атрибутов {A 1, A 2, …, A n }, то X называется ключом R, если: функциональная зависимость X A 1 A 2 …A n F +, ни для какого собственного подмножества Y X функциональная зависимость Y A 1 A 2 …A n F + 27

Свойства ключа X – первичный ключ отношения R: X A 1 A 2 …A n Из данной функциональной зависимости в соответствии с правилом 6 следуют функциональные зависимости X A i для i = 1, 2, …, n 28

Декомпозиция с соединением без потерь (1) Декомпозицией схемы отношения R(A 1, A 2, …, A n ) называется замена ее совокупностью подмножеств {R i } (подсхем) схемы R таких, что R 1 R 2 … R k = R. Не обязательно, чтобы R i R k = при i k 29

Декомпозиция с соединением без потерь (2) Декомпозиция реализации отношения r(R): r i = Ri (r), i = 1, 2, …, k Восстановление r из r i : s = r 1 r 2 … r k Где гарантия, что s r ? 30

Пример декомпозиции Исходное отношение Вариант 1: S 11 (Sid, City), S 12 (Sid, Status) Вариант 2: S 21 (Sid, Status), S 22 (Status, City) 31 S(Sid,Status,City) S130N1 S230N2N2

Вариант 1 Декомпозиция Восстановление 32 S 11 (Sid,City)S 12 (Sid,Status) S1N1S130 S2N2N2S2S230 s 11 s 12 = S(Sid,Status,City) S130N1 S2S230N2N2

Вариант 2 Декомпозиция Восстановление 33 S 21 (Sid,Status)S 22 (Status,City) S130 N1 S230 N2N2 s 21 s 22 = S(Sid,Status,City) S130N1 S130N2N2 S230N1 S220N2

Соединение без потери (1) Пусть R – схема отношения, R 1, R 2, …, R k – декомпозиция схемы, F – множество функциональных зависимостей для R. Говорят, что эта декомпозиция обладает свойством соединения без потерь относительно F, если каждая реализация r(R), удовлетворяющая F, может быть представлена в виде: r = R (r) R (r) … Rk (r) 34

Соединение без потери (2) Пусть R(A, B, C) – схема отношения с атрибутами (подмножествами атрибутов) A, B и C. Если данная схема отношения удовлетворяет функциональной зависимости A B, то осуществляется декомпозиция без потери на {R 1, R 2 }, где R 1 = {A, B} и R 2 = {A, C} 35

Соединение без потери (3) Исходное отношение: S(Sid, Status, City) Функциональные зависимости: Sid City, City Status Декомпозиция с соединением без потери: а) S 11 (Sid, City), S 12 (Sid, Status) б) S 21 (City, Status), S 22 (City, Sid) 36

Сохранение функциональных зависимостей (1) Проекцией множества функциональных зависимостей F на множество атрибутов Z ( Z (F)) называется множество зависимостей X Y в F +, таких, что XY Z Говорят, что декомпозиция сохраняет множество функциональных зависимостей F, если из объединения всех зависимостей, принадлежащих Ri (F), для i = 1, 2, …, k, логически следуют все зависимости, принадлежащие F 37

Сохранение функциональных зависимостей (2) Исходное отношение Функциональные зависимости: Sid City, City Status, Sid Status Вариант 1: S 11 (Sid, City), S 12 (Sid, Status) Вариант 2: S 21 (City, Status), S 22 (Sid, City) 38 S(Sid,Status,City) S130N1 S230N2N2 S3S340N3N3

Сохранение функциональных зависимостей (3) Вариант 1 Поставщик S2 переехал в город N3 какой статус города N3? 39 S 11 (Sid,City)S 12 (Sid,Status) S1N1S130 S2N2S230 S3N3S340

Сохранение функциональных зависимостей (4) Вариант 2 Поставщик S2 переехал в город N3 40 S21S21 (Sid,City)S22S22 (City,Status) S1N1 30 S2N2 30 S3N3 40

Сохранение функциональных зависимостей (5) Исходные функциональные зависимости: Sid City, City Status, Sid Status Вариант 1: S 11 (Sid, City), Sid City S 12 (Sid, Status), Sid Status City Status ??? Вариант 2: S 21 (City, Status), City Status S 22 (Sid, City), Sid City Sid Status – выводится !!! 41

Нормализация отношений Говорят, что отношение находится в некоторой нормальной форме, если оно удовлетворяет заданному набору условий 42

Определение 1НФ Отношение находится в 1НФ тогда и только тогда, когда все используемые домены содержат только скалярные (атомарные, простые) значения 43

Пример: поставщики Информация о поставщиках: номер поставщика Sid на домене НОМЕР имя поставщика SName на домене ИМЯ город City, в котором размещается поставщик, на домене ГОРОД код города Code на домене КОД 44

Пример: поставляемые товары Информация о поставляемых товарах: код товара Pid на домене НОМЕР, название товара PName на домене НАЗВАНИЕ, стоимость товара Price на домене ДЕНЬГИ, количество поставляемых товаров Qty на домене КОЛИЧЕСТВО 45

Ненормализованное отношение Составной домен ПОСТАВКА ( НОМЕР, НАЗВАНИЕ, ДЕНЬГИ, КОЛИЧЕСТВО) Ненормализованное отношение ПОСТАВКА ТОВАРОВ ( Sid : НОМЕР, SName : ИМЯ, City : ГОРОД, Code : КОД, PS : ПОСТАВКА) 46

Определение ПК Функциональные зависимости Sid SName, Sid City, City Code, Sid PS Из правила транзитивности Sid Code Из правила рефлексивности Sid Sid Из правила аддитивности Sid (Sid, SName, City, Code, PS) Sid – первичный ключ данного отношения 47

Реализация отношения ДоменНОМЕРИМЯГОРОДКОДПОСТАВКА АтрибутSidSNameCityCodPS S1SmithLondon20P1, Nut, 12, 200 P2, Bolt, 17, 100 P3, Screw, 17, 100 S2JonesParis10P1, Nut, 12, 150 P2, Bolt, 17,

Приведение к 1НФ Проблема обновления Проблема вставки Проблема удаления 49 ДоменНОМЕРИМЯГОРОДКОДНОМЕРНАЗВА- НИЕ ДЕНЬ- ГИ КОЛ- ВО АтрибутSidSNameCityCodPidPNamePriceQty S1SmithLondon20P1Nut12200 S1SmithLondon20P2Bolt17100 S1SmithLondon20P3Screw17100 S2JonesParis10P1Nut12150 S2JonesParis10P2Bolt17200

Функциональные зависимости Sid SName, Sid City, City Code Из правила транзитивности Sid Code Pid PName, Pid Price, (Sid, Pid) QTY Правило пополнения: из Sid Sname получим (Sid, Pid) (Sname, Pid). Правило рефлексивности: (Sname, Pid) SName. Правило транзитивности: (Sid, Pid) Sname 50

Определение ПК (Sid, Pid) SName, (Sid, Pid) City, (Sid, Pid) Code, (Sid, Pid) PName, (Sid, Pid) Price, (Sid, Pid) QTY (задано), (Sid, Pid) Sid, (Sid, Pid) Pid (правила рефлексивности). Правило аддитивности: (Sid, Pid) (Sid, SName, City, Code, Pid, Price, QTY) 51

2НФ Отношение находится в 2НФ тогда и только тогда, когда оно находится в 1НФ, и каждый его не ключевой атрибут функционально полно зависит от любого возможного ключа этого отношения 52

Нарушение 2НФ (Sid, Pid) QTY – функционально полная (Sid, Pid) SName или (Sid, Pid) Price – не функционально полные, так как есть Sid SName и Pid Price 53

Приведение к 2НФ (1) Из Sid SName, Sid City, Sid Code следует Sid (SName, City, Code) (1) Из Pid PName и Pid Price следует Pid (PName, Price) (2) Есть (Sid, Pid) QTY (3) Декомпозиция на основе (1): ПОСТАВЩИК (Sid, SName, City, Code) ПОСТАВЛЯЕМЫЙ ТОВАР (Sid, Pid, PName, Price, Qty)

Приведение к 2НФ (2) ПОСТАВЛЯЕМЫЙ ТОВАР (Sid, Pid, PName, Price, Qty) – нарушение 2НФ: (Sid, Pid) Qty, но Pid Pname и Pid Price Декомпозиция на основе (2): ТОВАР (Pid, PName, Price) ПОСТАВКА (Sid, Pid, QTY) 55

2НФ: проектирование в ER 56

3НФ Отношение находится в 3НФ тогда и только тогда, когда оно находится в 2НФ, и каждый его не ключевой атрибут не транзитивно зависит от ключа 57

Нарушение 3НФ ПОСТАВЩИК (Sid, SName, City, Code) Sid SName, Sid City, City Code Транзитивная зависимость Sid Code Проблема обновления Проблема вставки Проблема удаления 58

Приведение к 3НФ Декомпозиция на основе City Code: ПОСТАВЩИК ( Sid, SName, City) ГОРОД (City, Code) 59

3НФ: проектирование в ER 60

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

Нарушение НФБК ОБУЧЕНИЕ (S, P, T) S – студент, P – предмет, T – преподаватель Условия (функциональные зависимости): каждый студент изучает некоторый предмет под руководством только одного преподавателя: (S, P) T каждый преподаватель проводит занятия только по одному предмету: T P 62

Реализация отношения S (студент)P (предмет)T (преподаватель) Иванов Математика Петров Иванов ФизикаМихайлов Сидоров МатематикаИльин Сидоров ФизикаМихайлов Сергеев ХимияДымов Аномалии: удалить студента Сергеева. Что с преподавателем Дымовым? 63

Определение ключей Дано: (S, P) T и T P. Ключи: (S, P) и (S, T) 1. Из (S, P) T и (S, P) (S, P) следует (S, P) (S, P, T) (правило аддитивности) Не выводятся S (S, P, T) или P (S, P, T) 2. Из T P и (P, S) (P, S, T) (доказано выше) следует (T, S) (P, S, T) (правило псевдо транзитивности) Не выводятся T (S, P, T) или S (S, P, T) 64

Приведение к НФБК Декомпозиция на основе T P: E1(T, P) и E2(S, T) Такая декомпозиция не сохраняет функциональные зависимости: если вместо какого-либо преподавателя, проводящего занятия по предмету, назначается другой преподаватель, необходимо изменить соответствующие кортежи и в отношении E1, и в отношении E2 65

НФБК: проектирование в ER (1) 66

НФБК: проектирование в ER (2) 67

НФБК: проектирование в ER (3) 68 Отсутствует функциональная зависимость (G, C) P, нет ключа (G, C)

Расписание занятий Ненормализованное отношение 69 Учебный курс День занятий Студент C1C1Понедельник Среда Иванов Петров Сидоров C2C2Пятница Мягков Быков

Предположения Каждый курс может иметь произвольное количество дней занятий Каждый курс могут изучать произвольное количество студентов Дни занятий и студенты совершенно не зависят друг от друга, т.е. независимо от дня занятий состав группы студентов один и тот же День занятий может быть связан с любыми курсами Каждый студент может быть связан с любым курсом 70

Нормализация отношения CDSУчебный курс День занятий Студент C1C1Понедельник Иванов C1C1Понедельник Петров C1C1Понедельник Сидоров C1C1Среда Иванов C1C1Среда Петров C1C1Среда Сидоров C2C2Пятница Мягков C2C2Пятница Быков 71

Ограничения и проблемы Если в отношении существуют кортежи и, то также присутствуют и кортежи и Проблема вставки – добавить день занятий по курсу Проблема обновления – перенести день занятий по курсу Проблема удаления – отменить день занятий по курсу 72

Декомпозиция отношения CD(Учебный курс, День занятий) CS (Учебный курс, Студент) 73 CD Учебный курс День занятий CS Учебный курс Студент C1ПонедельникC1C1Иванов C1СредаC1C1Петров C2ПятницаC1Сидоров C2Мягков C2Быков

Многозначные зависимости (1) Сформулированы Фейгином (Fagin) в 1971 г. Пусть A, B, C – некоторое произвольное подмножество атрибутов схемы отношения R(A, B, C). Тогда B многозначно зависит от A (A B) тогда и только тогда, когда множество значений B, соответствующее заданной паре отношения R, зависит только от A, но не зависит от C 74

Многозначные зависимости (2) Для данного отношения R(A, B, C) многозначная зависимость A B выполняется тогда и только тогда, когда также выполняется многозначная зависимость A C: A B | C В приведенном примере Учебный курс День занятий | Студент 75

Декомпозиция отношения Пусть A, B, C – некоторые множества атрибутов схемы отношения R(A, B, C). Отношение R будет равно соединению его проекций R 1 (A, B) и R 2 (A, C) тогда и только тогда, когда для отношения R выполняется многозначная зависимость A B 76

4НФ Отношение R находится в 4НФ тогда и только тогда, когда в случае существования многозначной зависимости A B все атрибуты отношения R функционально зависят от A (В отношении отсутствуют многозначные зависимости) 77

4НФ: проектирование в ER (1) Диаграмма уровня сущностей 78

4НФ: проектирование в ER (2) Нарушение 4НФ 79

4НФ: проектирование в ER (3) Выполнение условий 4НФ 80

5НФ (1) Отношение R(A 1 A 2 …A n ), где A 1, A 2, …, A n – произвольные подмножества множества атрибутов R, удовлетворяет зависимости соединения *(A 1, A 2, …, A n ) тогда и только тогда, когда оно равносильно соединению своих проекций с подмножествами атрибутов A 1, A 2, …, A n (т.е. восстанавливается без потерь путем соединения своих проекций) 81

5НФ (2) Отношение R находится в 5НФ тогда и только тогда, когда любая зависимость соединения в отношении R следует из существования некоторого потенциального ключа отношения R (или каждая зависимость соединения в отношении R подразумевается потенциальными ключами отношения R). 5НФ – нормальная форма проекции – соединения 82