II.6. Проектиране на схемите на релационните бази от данни — Разширена писмена разработка

Разширена писмена разработка. II.6. Проектиране на схемите на релационните бази от данни

Подробен авторски текст за подготовка по конспекта на СУ. Краткият вариант е запазен на основната страница на темата. За преговор използвай плана; за обосновка — определенията и разработените примери. Това не е официален изпитен образец.

Кратка разработка и уроци по темата · План за изпита · Покритие · Източници

Обхват от конспекта

Проектиране на схемите на релационните бази от данни. Аномалии. Декомпозиция на релации. Нормална форма на Бойс-Код. Декомпозиция в нормална форма на Бойс-Код. Възстановяване на информацията след декомпозиция. Трета нормална форма.

Покритие на конспекта

Всяка подточка води към съответния раздел на разработката.

  1. Проектиране на схемите на релационните бази от данни — 1. Защо е необходима нормализация
  2. Аномалии — 1. Защо е необходима нормализация
  3. Декомпозиция на релации — 2. Какво трябва да запази декомпозицията
  4. Нормална форма на Бойс-Код — 3. Нормална форма на Бойс–Код
  5. Декомпозиция в нормална форма на Бойс-Код — 3. Нормална форма на Бойс–Код
  6. Възстановяване на информацията след декомпозиция — 4. Възстановяване на информацията
  7. Трета нормална форма — 5. Трета нормална форма и синтез

Кратък план за изпита

  1. Цел на релационното проектиране и аномалии.
  2. Декомпозиция, беззагубност и запазване на зависимости.
  3. Определение и алгоритъм за BCNF.
  4. Проверка на възстановяването чрез съединение.
  5. 3NF, синтез и сравнение с BCNF.

1. Защо е необходима нормализация

Целта на релационното проектиране е фактите да се представят без ненужно повторение и с ограничения, които могат надеждно да се поддържат. Нормализацията използва зависимости, за да открива определени видове излишества и да разделя схемите. Тя не замества установяването на правилните бизнес правила и не обещава автоматично най-бързи заявки.

Нека ЗАПИСВАНЕ(Курсист, Курс, Преподавател, Имейл) описва текущи записвания. Всеки курс има един преподавател, а всеки преподавател — един текущ имейл. ФЗ са Курс → Преподавател и Преподавател → Имейл; кандидат-ключ е (Курсист, Курс). За всеки записан курсист повтаряме преподавателя и неговия имейл.

Аномалия при обновяване: сменяме имейла в някои редове, а в други оставяме стария. При вмъкване: не можем да запишем нов преподавател независимо от записване, без да въвеждаме липсващи или фиктивни участници. При изтриване: последното записване за курс може да заличи единствената информация кой го води. Трите проблема произлизат от смесването на различни факти в една релация.

2. Какво трябва да запази декомпозицията

Декомпозицията заменя схема R с подcхеми R₁, …, Rₙ, чието обединение от атрибути е R. От конкретен екземпляр r получаваме проекциите πR₁(r), …, πRₙ(r). Само покриването на атрибутите обаче не е достатъчно.

Беззагубност означава, че за всеки допустим r естественото съединение на проекциите възстановява точно r. Съединението винаги съдържа оригиналните кортежи, но лошо разделяне може да добави фиктивни комбинации. Запазване на зависимости означава, че всички оригинални ФЗ следват от обединението на проектираните зависимости и могат да се осигурят чрез локалните ограничения. Това е различно свойство: беззагубна декомпозиция може да не запазва всички зависимости.

В примера отделяме ПРЕПОДАВАТЕЛ(Преподавател, Имейл), КУРС(Курс, Преподавател) и ЗАПИСВАНЕ(Курсист, Курс). Всяко отношение представя един вид факт. Външните ключове осигуряват съществуването на посочените участници. След разделянето могат да се пазят и преподаватели без текущи записвания; възстановената широка релация на записванията съдържа само участващите в записвания преподаватели.

3. Нормална форма на Бойс–Код

Схема R е в BCNF спрямо F, когато за всяка нетривиална ФЗ X → Y от F⁺, приложима върху R, X е суперключ на R. Условието е за всички следствия, а не само за първоначално изписаните зависимости. Тривиалните ФЗ не нарушават формата.

Алгоритъмът избира нарушаваща ФЗ X → Y, премахва от Y атрибутите, които вече са в X, и разделя R на R₁ = X ∪ Y и R₂ = R − (Y − X). Общите атрибути са X, което определя R₁; така стъпката е беззагубна. За двете подcхеми се използват проекциите на зависимостите и процедурата се повтаря, докато няма нарушение.

В широкото ЗАПИСВАНЕ зависимостта Преподавател → Имейл нарушава BCNF, защото преподавателят не определя курсиста и курса. Отделянето ѝ оставя (Курсист, Курс, Преподавател). Там Курс → Преподавател също нарушава BCNF и дава останалите две релации. При заявените ФЗ крайният проект е в BCNF, беззагубен и запазва зависимостите. Последното е вярно за този пример, но не е обща гаранция на BCNF алгоритъма.

4. Възстановяване на информацията

За бинарна декомпозиция на R на R₁ и R₂, разглеждана спрямо ФЗ, критерият за беззагубност е общите атрибути да определят поне едната цяла подcхема: (R₁ ∩ R₂) → R₁ или (R₁ ∩ R₂) → R₂ да следва от F. При повече части може да се използва chase проверка; последователност от доказано беззагубни бинарни стъпки също дава беззагубна обща декомпозиция.

r(A,B,C) = {(a1,b,c1), (a2,b,c2)}
πAB(r) = {(a1,b), (a2,b)}
πBC(r) = {(b,c1), (b,c2)}

Съединението по B дава четири реда, включително (a1,b,c2) и (a2,b,c1), които не са в r. Ако бизнес правилата не налагат B → A или B → C, това разделяне не е гарантирано беззагубно. Общата колона сама по себе си не е достатъчна.

При chase се съставя таблица с ред за всяка подcхема и колона за всеки атрибут на R. Наличните атрибути получават общи отличени символи, а липсващите — отделни нови символи. ФЗ налагат отъждествяване на символи в редове, които съвпадат по лявата страна. Ако се получи ред с всички отличени символи, възстановяването е беззагубно спрямо тези ФЗ. Методът проверява логическата гаранция, а не случайно успешното съединение на един пример.

5. Трета нормална форма и синтез

Атрибут е ключов (prime), ако участва в поне един кандидат-ключ. R е в 3NF, когато за всяка нетривиална ФЗ X → A с един атрибут отдясно X е суперключ или A е ключов атрибут. BCNF удовлетворява първата алтернатива за всички такива зависимости и следователно винаги е в 3NF. Обратното не е вярно.

Например за R(Студент, Предмет, Преподавател) приемаме точно ФЗ (Студент, Предмет) → Преподавател и Преподавател → Предмет. Кандидат-ключовете са (Студент, Предмет) и (Студент, Преподавател). Преподавател → Предмет нарушава BCNF, но Предмет участва в кандидат-ключ, така че схемата е в 3NF. Беззагубното разделяне на (Преподавател, Предмет) и (Студент, Преподавател) не запазва първата ФЗ локално: отделните таблици могат да разрешат студент с двама преподаватели по един и същ предмет.

Синтезът на 3NF започва от минимално покритие с единични десни страни. За всяка ФЗ X → A създава схема XA, по желание групира еднаквите леви страни и премахва схеми, включени изцяло в други. Ако никоя получена схема не съдържа кандидат-ключ на оригиналната, добавя се релация с такъв ключ. Правилният алгоритъм гарантира 3NF, запазване на зависимостите и беззагубност. Добавената ключова релация има конкретна роля за възстановяването и не бива механично да се пропуска.

Следователно BCNF дава по-силно отстраняване на излишества от ФЗ, а 3NF позволява компромис за локално поддържане на всички ФЗ. На изпит разграничаването на нормална форма, беззагубност и запазване на зависимости е по-важно от механичното изброяване на таблици.

Литературна опора и граници на сверяването

Официална библиография на СУ — номерата по-долу са от нея.

  • СУ 11 — Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom, Database Systems: The Complete Book, 2. изд., Prentice Hall, 2008. Пълен текст, наличен в проекта и използван за сверка.
  • Точно четене: §3.3–3.5.3; печатни 85–104 / PDF 122–141. PDF страниците са поредни от началото на локалния файл; в това копие печатната страница + 37 дава PDF страницата.
  • Страница на авторите за второто издание. Примерите тук са авторски. Означенията са обяснени в текста; SQL уточненията са разграничени от класическия модел.

Текстът и примерите са авторска учебна разработка, а не официален отговор или указание на изпитна комисия на СУ. Номерацията на разделите в плана е авторска. Препратките показват опората за понятията, а не че примерите са преписани от учебник.

Обратно към кратката разработка и уроците