Бази от данни — Учебен материал

Курс на доц. д-р Димитър Димитров, ФМИ, СУ „Св. Климент Охридски"

Съдържание

Въведение — Бази от данни и СУБД
Модел „Същност-връзки" (E/R модел)
Релационен модел
Функционални зависимости
Нормализация — 1NF, 2NF, 3NF
BCNF, МЗ и 4NF
Релационна алгебра — Основи
Релационна алгебра — Разширена (Мултимножества)

1. Въведение

База от данни (БД)

БД е структурирана колекция от данни, организирана за ефективно съхранение, извличане и манипулиране.

Структурирана — данните са организирани по определен начин
Колекция — съвкупност от множество данни
Ефективно съхранение — бърз достъп
Извличане — намиране и четене на данни
Манипулиране — промяна, добавяне, изтриване

СУБД (Система за управление на бази от данни)

Софтуерна система за създаване, достъп, модификация и администриране на БД. Интерфейс между потребители и БД.

Защо не файлова система? При 1 млн. реда с едновременен достъп на множество потребители файловата система/spreadsheet не може ефективно да се справи.

Модели на данни

Релационен (най-разпространен)
Йерархичен
Същност-връзки (E/R) — за концептуално проектиране
Обектно-ориентиран
Графов

SQL

Категория	Команди
DDL (Data Definition Language)	CREATE, DROP, ALTER
DML (Data Manipulation Language)	SELECT, INSERT, UPDATE, DELETE
DCL (Data Control Language)	GRANT, REVOKE

Трислойна архитектура

Ниво	Роля
Presentation tier (Client)	Потребителски интерфейс
Application tier (Server)	Бизнес логика
Data tier	Базата от данни

ACID свойства на транзакциите

Свойство	Описание
A — Atomicity	Всичко или нищо — транзакцията се изпълнява изцяло или не се изпълнява въобще
C — Consistency	Транзакция води БД от едно консистентно състояние в друго
I — Isolation	Конкурентното изпълнение дава същите резултати като последователното
D — Durability	След commit транзакцията остава дори след срив

CAP теорема

Разпределена система може да удовлетвори най-много две от:

C — Consistency — всяко четене връща последно записаните данни
A — Availability — всяка заявка получава отговор
P — Partition tolerance — разделяне на системата не води до некоректни отговори

Компоненти на СУБД

Компилатор на заявки (Query compiler)
Машина за изпълнение (Execution engine)
Управление на индекси, файлове и записи
Управление на буфера (кеш)
Управление на транзакции (ACID)
Контрол на конкурентността (Deadlock prevention/detection)
Управление на логове и възстановяване

2. E/R Модел

Стъпки при проектиране на БД

Събиране на изисквания
Концептуален модел (E/R) — абстрактно, независимо от СУБД
Логически модел — повече детайли
Физически модел — специфичен за СУБД

Процес: Идеи → E/R диаграма → Релационна схема

Основни елементи на E/R модела

Елемент	Символ
Множество от същности	Правоъгълник
Атрибут	Овал
Ключов атрибут	Овал с подчертано име
Производен атрибут	Пунктиран овал
Многозначен атрибут	Двоен овал
Композитен атрибут	Вложени овали
Множество от връзки	Ромб
Слабо множество от същности	Правоъгълник с двойна рамка
Поддържаща връзка	Ромб с двойна рамка + стрелка
Is-a връзка	Триъгълник, сочещ суперкласа

Същност (Entity)

Реален обект или концепция (описва се със съществително)
Тип същности — категория (като клас в ООП)
Множество от същности — съвкупност от същности от един тип

Атрибути

Атомарни — числа, низове (напр. телефонен номер)
Композитни — напр. адрес (град, улица, номер)
С много стойности — напр. телефонни номера на човек
Производни — изчисляват се от други атрибути (напр. age от birthdate)

Ключ

Атрибут или списък от атрибути, които уникално определят всяка същност.

Всяко множество от същности трябва да има ключ
Може да има кандидат-ключове — само един се избира за първичен
Представяне: подчертаване на ключовите атрибути в диаграмата

Връзка (Relationship)

Асоциация между същности (описва се с глагол). Може да има собствени атрибути — характеристики, специфични за конкретната връзка (напр. salary в contracts).

Множественост (Cardinality)

Вид	Нотация	Описание
Много към много (M:N)	Линии без стрелки	Без ограничение
Много към едно (M:1)	Стрелка към „едно" страната	На всяка същност от E съответства 0 или 1 от F
Едно към едно (1:1)	Стрелки и в двете посоки	Взаимно ограничение

Задължително участие — двойна линия (total participation)
Заоблена стрелка — точно едно участие + референтна цялостност
Числови ограничения — <=10 или 0..N върху линията

Степен на връзките

Бинарни — свързват 2 множества (най-честият случай)
N-арни (тернарни при N=3) — свързват N множества

Роли

Едно множество от същности може да участва два пъти в една връзка в различни роли. Всяка роля се именува върху отделна дъга.

Пример: Employee — Works-for — Employee с роли Manager и Employee

Подкласове (is-a йерархии)

Подкласовете имат допълнителни атрибути или специфични връзки
Ключът идва от суперкласа (корена)
Правило: is-a се използва само когато подкласът е истински подтип на суперкласа

Пример: Movies → Cartoons, Mystery, Science-Fiction

Слабо множество от същности

Не може да се идентифицира само с собствените си атрибути
Разчита на поддържащо (силно) множество
Ключ = собствени атрибути + ключови атрибути на поддържащото множество
Поддържащата връзка не се преобразува в отделна релация

Принципи на добро проектиране

Съответствие — схемата отразява действителността
Без излишество — една информация не се представя по два начина
Простота — без излишни елементи
Правилен вид елементи — не добавяме връзки, следващи от други връзки

Атрибут vs. множество от същности: Ако сущността има само ключови атрибути и само M:1 връзки, може да се представи като атрибут. Иначе — отделно множество.

3. Релационен модел

Основни понятия

Понятие	Описание
Атрибут	Колона на таблица; описва значението на елементите
Схема на релация	Име + множество атрибути: `Movies(title, year, length, filmType)`
Кортеж	Един ред; по една стойност за всеки атрибут
Домейн	Допустими стойности за атрибут (напр. `year: цяло число`)
Екземпляр	Текущото множество от кортежи в релацията
Ключ	Атрибути, уникално определящи всеки кортеж

Релацията е множество от кортежи — редът на редовете и колоните няма значение. Всички стойности трябва да са атомарни.

Преобразуване E/R → Релационен модел

Множества от същности → Релации

Всяко множество от същности се превръща в релация с:

Същото име
Същите атрибути
Ключ от ключовите атрибути

Композитните атрибути → отделни атрибути (податрибутите). Производните атрибути → не се представят (изчисляват се при заявка).

Връзки → Релации

Атрибутите на релацията за връзка = ключовете на участващите същности + собствените атрибути на връзката.

Ключ на релацията за връзка:

M:N → ключовете на всички участващи множества
M:1 → ключовите атрибути само на "много"-страната

Комбиниране на релации (оптимизация)

При M:1 и 1:1 връзки не се създава отделна релация — атрибутите се добавят директно към релацията на "много"-страната.

Преди:  Movies(title, year, length, filmType)
        Owns(title, year, studioName)       ← M:1 връзка

След:   Movies(title, year, length, filmType, studioName)  ← обединени

При M:N — НЕ се комбинира (ще създаде излишество)
При 1:1 — може да се добави ключа в която и да е страна

При отсъстваща връзка → NULL стойности.

Слаби множества → Релации

Релацията включва: всички атрибути на слабото + ключовете на поддържащите множества. Поддържащата връзка не се преобразува отделно.

Преобразуване на is-a йерархии — 3 подхода

Подход	Описание	Предимства	Недостатъци
E/R	Отделна релация за всяко множество	Чист дизайн, всички филми в една таблица	Данните за подклас са в много таблици
ОО	Релация за всяко поддърво (комбинация от подкласове)	Всички атрибути на подклас в една таблица	2ⁿ релации, дублиране на данни
Null	Една релация за цялата йерархия	Всичко на едно място, прост дизайн	Много NULL стойности, трудно добавяне на подклас

Ключове

Естествен ключ — произхожда от данните (напр. {title, year})
Сурогатен ключ — изкуствен атрибут без семантика (напр. movieId, UUID). Използва се ако естественият ключ е редактируем или ако няма подходящ естествен ключ.

NULL стойности

Използват се когато стойността липсва или не е известна
Неформална, но задължителна част на релационния модел

4. Функционални зависимости

Дефиниция

A → B (A функционално определя B): за всеки два кортежа от релацията, ако те съвпадат по атрибутите A, то те съвпадат и по B.

ФЗ е твърдение за схемата, не за конкретен екземпляр
ФЗ не могат да се определят само от данните — те идват от семантиката

Примери

Employee ID → Employee Name, Department ID
Department ID → Department Name
title, year → length, filmType, studioName   (но НЕ → starName)

Ключ (чрез ФЗ)

Множеството K е ключ за релацията R, ако:

K функционално определя всички атрибути на R
Никое собствено подмножество на K не удовлетворява (1)

Суперключ — удовлетворява (1), но не непременно (2). Ключът е минимален суперключ.

Тривиални и нетривиални ФЗ

Тривиална: B ⊆ A (напр. title, year → title)
Нетривиална: поне един атрибут от B не е в A
Напълно нетривиална: нито един атрибут от B не е в A

Правило: От дясната страна можем да премахнем атрибутите, присъстващи и в лявата: title, year → year, length → title, year → length

Аксиоми на Армстронг

Аксиома	Формулировка
А1. Рефлексивност	Ако Y ⊆ X, то X → Y
А2. Разширение	Ако X → Y, то XW → YW
А3. Транзитивност	Ако X → Y и Y → Z, то X → Z

Следствия (изводи)

Следствие	Формулировка
Обединение	Ако X → Y и X → Z, то X → YZ
Псевдотранзитивност	Ако X → Y и WY → Z, то XW → Z
Декомпозиция	Ако X → Y и Z ⊆ Y, то X → Z

Разделяне на дясна страна: A → B₁B₂…Bₙ ↔ A → B₁, A → B₂, …, A → Bₙ

Внимание: Лявата страна не може да се разделя в общия случай.

Намиране на ключове

При преобразуване от E/R:

Множество от същности → ключ от ключовите атрибути
M:N връзка → ключовете на участващите същности
M:1 връзка → само ключа на "много"-страната

5. Нормализация — 1NF, 2NF, 3NF

Аномалии при лош дизайн

Вид	Описание
Излишества	Информация се повтаря без нужда
Аномалия при обновяване	Неуспешна актуализация на всички срещания → неконсистентност
Аномалия при изтриване	При изтриване на кортеж се губи и друга информация

Декомпозиция

Декомпозиция на R = заместване с R₁, R₂, … такива, че:

Обединението на атрибутите покрива всички атрибути на R
Rᵢ е проекция на R по съответните атрибути
При естествено съединение на R₁ ⋈ R₂ ⋈ … трябва да получим обратно R (съединение без загуба)

Първа нормална форма (1NF)

Дефиниция: Всички домейни се състоят от атомарни (неделими) стойности — без множества, списъци, вложени таблици.

Привеждане в 1NF при многозначен атрибут:

Вариант 1: отделна релация
Вариант 2: повторение на кортежи (ключът включва многозначния атрибут)

Втора нормална форма (2NF)

Формална дефиниция: За всяка нетривиална ФЗ A₁…Aₙ → B: или B е елемент на ключ, или {A₁,…,Aₙ} не е собствено подмножество на никой ключ.

Неформална дефиниция: В 1NF + всеки неключов атрибут зависи от целия (кандидат-)ключ, не само от негово подмножество.

Нарушение: {customer_id, store_id} е ключ, но store_id → store_location — store_location зависи само от parte на ключа.

Алгоритъм за привеждане в 2NF:

Намери всички ключове
За всяка нарушаваща ФЗ A → B: добави всички атрибути, определени от A, в дясната страна
Премахни B от R
Създай нова релация (A ∪ B) с ключ A
Повтори за новите релации

Бележка: Ако ключът е съставен от един атрибут, релацията автоматично е в 2NF (не може собствено подмножество).

Трета нормална форма (3NF)

Формална дефиниция: За всяка нетривиална ФЗ A₁…Aₙ → B: или B е елемент на ключ, или {A₁,…,Aₙ} е суперключ.

Неформална дефиниция: В 2NF + никой неключов атрибут не е транзитивно зависим от (кандидат-)ключа.

Нарушение:

MoviesFull(title, year, length, studioName, studioAddress, producer)
title, year → studioName   и   studioName → studioAddress
⟹ транзитивна зависимост: title, year → studioAddress

Декомпозиция:

Movies(title, year, length, studioName, producer)
Studios(studioName, studioAddress)

Важни свойства на 3NF:

Декомпозицията винаги може да бъде избрана така, че ФЗ да се запазват
Релацията винаги може да се приведе в 3NF
3NF ⟹ 2NF ⟹ 1NF

Резюме на нормалните форми

НФ	Условие
1NF	Атомарни стойности
2NF	В 1NF + всеки неключов атрибут зависи от целия ключ
3NF	В 2NF + никой неключов атрибут не е транзитивно зависим от ключа

6. BCNF, МЗ и 4NF

Нормална форма на Бойс-Код (BCNF)

Дефиниция: За всяка нетривиална ФЗ A₁…Aₙ → B: {A₁,…,Aₙ} е суперключ (единственото условие — отпада изключението „B е в ключ").

Може да се нарече 3.5NF — по-строга от 3NF.

Пример за релация в 3NF, но не в BCNF:

R(A, B, C),  ключ: {A, B},  ФЗ: C → B
C не е суперключ ⟹ BCNF е нарушена
Но B е елемент на ключ ⟹ 3NF е спазена

Алгоритъм за BCNF декомпозиция: Ако нетривиалната ФЗ A → B нарушава BCNF (A не е суперключ):

Създай S(A ∪ B) — всички атрибути, определени от A
Създай T(A ∪ (R \ B)) — оригиналната релация без B
Повтори за S и T, ако не са в BCNF

Всяка релация с два атрибута е в BCNF (алгоритъмът е краен).

Проблем с BCNF: не гарантира запазване на ФЗ.

Пример за загуба на ФЗ:

Booking(title, theater, city)
ФЗ: theater → city,  title, city → theater
Ключове: {title, city} и {theater, title}

BCNF декомпозиция (по theater → city):
  R(theater, city)
  S(theater, title)
⟹ ФЗ "title, city → theater" е изгубена!

Сравнение 3NF vs BCNF

Свойство	3NF	BCNF
Елиминира излишества от ФЗ	В повечето случаи	Да
Запазва ФЗ	Да	Невинаги

Многозначни зависимости (МЗ / MVD)

Проблемът: Релация в BCNF може да има излишества поради независими многозначни атрибути.

Пример: Employees(name, phone, skill) — телефоните и уменията на служителя са независими едно от друго. Добавянето на нов телефон изисква копиране на всички умения.

Дефиниция на МЗ: A →→ B (A многозначно определя B): ако два кортежа съвпадат по A, техните B-стойности могат да се разменят и резултантните кортежи ще принадлежат на релацията.

Формално: ако t[A] = u[A], то трябва да съществува кортеж v, за който:

v[A] = t[A]
v[B] = t[B]
v[C] = u[C] (C = всички атрибути извън A ∪ B)

Пример: name →→ street, city в Stars(name, street, city, title, year)

Всяка ФЗ е и МЗ (но не обратното).

Свойства на МЗ

Свойство	Формулировка
Транзитивност	A →→ B и B →→ C ⟹ A →→ C
Допълнение	A →→ B ⟹ A →→ (R \ A \ B)
Обединение	A →→ B и A →→ C ⟹ A →→ B ∪ C

Важно: Дясната страна на МЗ не може да се разделя (за разлика от ФЗ).

Тривиална МЗ

A →→ B е тривиална, ако B ⊆ A, или A ∪ B съдържа всички атрибути на R.

Четвърта нормална форма (4NF)

Дефиниция: За всяка нетривиална МЗ A →→ B: A е суперключ.

4NF ⟹ BCNF (всяко нарушение на BCNF е и нарушение на 4NF)
Всяка релация с два атрибута е в 4NF

Алгоритъм за 4NF декомпозиция: Ако нетривиалната МЗ A →→ B нарушава 4NF:

Създай S(A ∪ B)
Създай T(A ∪ (R \ B))
Повтори

Пример:

Stars(name, street, city, title, year)
name →→ street, city  (нарушение)

Декомпозиция:
  StarAddresses(name, street, city)
  StarsIn(name, title, year)

Съединение без загуба при 4NF: S ⋈ T = R, т.с.т.к. за R е изпълнено: B ∩ C →→ B − C или B ∩ C →→ C − B.

Пълна йерархия на нормалните форми

1НФ ⊃ 2НФ ⊃ 3НФ ⊃ НФБК ⊃ 4НФ

НФ	Условие
1NF	Атомарни стойности
2NF	Без частични зависимости от ключ
3NF	Без транзитивни зависимости; за нетрив. A→B: B в ключ ИЛИ A е суперключ
BCNF	За нетрив. A→B: A е суперключ
4NF	За нетрив. A→→B: A е суперключ

Свойство	3NF	BCNF	4NF
Без излишества от ФЗ	Повечето	Да	Да
Без излишества от МЗ	Не	Не	Да
Запазва ФЗ	Да	Невинаги	Невинаги

Препоръка: Релационните схеми трябва да са поне в 3NF.

7. Релационна алгебра — Основи

Какво е релационна алгебра (РА)?

Операнди — релации (променливи или константи)
Операции — създават нови релации от съществуващи
Теоретична основа на SQL
Използва се от СУБД като вътрешен език за изпълнение на заявки

SQL заявка → [Parser] → РА израз → [Оптимизатор] → План → [Code Gen] → Код

Операции върху множества

Условие за приложимост (съвместимост по обединение):

R и S имат еднаква степен (брой атрибути)
Съответните домейни съвпадат

Операция	Символ	SQL
Обединение	R ∪ S	UNION
Сечение	R ∩ S	INTERSECT
Разлика	R − S	EXCEPT

Проекция (π)

π_L(R) — нова релация само с атрибутите от списъка L. Дублиращите се кортежи се премахват.

Намалява броя на колоните
SQL еквивалент: SELECT DISTINCT

π_filmType(Movie)  →  {(color)}  (само различните стойности)

Селекция (σ)

σ_C(R) — нова релация само с кортежите, удовлетворяващи условие C. Схемата остава непроменена.

Намалява броя на редовете
SQL еквивалент: клауза WHERE
Условия: aθb (θ ∈ {<, >, =, ≤, ≥, ≠})
Сложни условия: σ_{φ∧ψ}(R) = σ_φ(R) ∩ σ_ψ(R)

Декартово произведение (×)

R × S — всяка двойка кортежи (t от R, u от S).

Брой кортежи: |R| × |S|
При едноименни атрибути: преименуване R.A и S.A
SQL: FROM R, S или CROSS JOIN

Съединения (Joins)

Вид	Нотация	Описание
Тета-съединение	R ⋈_C S = σ_C(R × S)	Декартово произведение + селекция
Еквисъединение	Тета с само "="	Условието е само по равенство
Естествено съединение	R ⋈ S	Еквисъединение по всички едноименни атрибути + премахване на дублиращи

Преименуване (ρ)

ρ_{R2(A1,…,An)}(R1) — дава нова схема на R1. SQL: AS

Основни (примитивни) операции

Следните 6 са примитивни (всички останали се изразяват чрез тях):

∪, −, σ, π, ×, ρ

Изразяване чрез примитивни:

R ∩ S = R − (R − S)
R ⋈_C S = σ_C(R × S)

Частно (Division)

R ÷ S — всички кортежи от R (с атрибути A−B), асоциирани с всеки кортеж от S.

R ÷ S = π_{A-B}(R) − π_{A-B}((π_{A-B}(R) × S) − R)

Приоритет на операциите

Унарни: σ, π, ρ (най-висок)
×, ⋈
∩
∪, − (най-нисък)

Линейна нотация и дървета

Линейна нотация:

LongMovies    := σ_{length≥100}(Movie)
FoxMovies     := σ_{studioName='Fox'}(Movie)
Result        := π_title,year(LongMovies ∩ FoxMovies)

Дървовидно представяне: Листа = релации; вътрешни възли = операции.

Ограничения чрез РА

Форма	Значение
R = ∅	Релацията R не трябва да съдържа кортежи
R ⊆ S	Всеки кортеж от R трябва да е в S

Примери:

Референтен интегритет:
  π_producerC#(Movie) ⊆ π_cert#(MovieExec)

Функционална зависимост (name → address):
  σ_{MS1.name=MS2.name AND MS1.address≠MS2.address}(ρ_MS1(MS) × ρ_MS2(MS)) = ∅

Ограничение на домейн:
  σ_{gender≠'F' AND gender≠'M'}(MovieStar) = ∅

Оптимизация на заявки

Predicate Pushdown — селекциите се извършват по-близо до данните (намалява се размерът на междинните релации).

Projection Pushdown — само необходимите атрибути се пренасят нагоре.

Join Reordering — пренареждане на съединенията въз основа на статистики за намаляване на междинните резултати.

Декорелация — корелирани подзаявки се преобразуват в съединения.

8. Релационна алгебра — Разширена (Мултимножества)

Мултимножество (Bag)

Структура, подобна на множество, но един елемент може да се среща повече от веднъж. Редът на елементите няма значение.

Защо? SQL на практика работи с мултимножества. Дубликатите се елиминират само при SELECT DISTINCT.

Операции върху мултимножества

Операция	Правило
Обединение (R ∪ S)	Брой срещания = сума от срещанията в R и S
Сечение (R ∩ S)	Брой срещания = минимум от срещанията в R и S
Разлика (R − S)	Брой срещания = max(0, срещания в R − срещания в S)

Внимание: Не всички закони за множества важат при мултимножества! Напр. S ∪ S ≠ S.

Селекция и проекция върху мултимножества

Селекция (σ) — дубликатите се запазват (ако два еднакви кортежа удовлетворяват условието, и двата се включват)
Проекция (π) — дубликатите не се елиминират (за разлика от проекцията върху множества)

Допълнителни оператори

DELTA (δ) — Отстраняване на дубликати

δ(R)  →  само по едно копие на всеки кортеж

SQL: SELECT DISTINCT

TAU (τ) — Сортиране

τ_L(R)  →  кортежите на R, сортирани по атрибутите от списъка L

Единственият оператор, чийто резултат е списък, а не множество/мултимножество.

Разширена проекция (π_L)

Списъкът L може да съдържа:

Единичен атрибут
Преименуване: x → y
Аритметика: A + B

π_{A+B→C, A, B}(R)  →  добавя колона C = A + B

GAMMA (γ) — Групиране и агрегиране

γ_L(R)  →  групиране по атрибутите от L + агрегации

Агрегиращи функции: SUM, AVG, MIN, MAX, COUNT