Бази данни

Ще опитам да сложа набързо всичко важно в една страничка (в по-малко не може :-/).

Релационна алгебра

Това е науката стояща зад SQL..
По-конкретно, когато пишете заявки (SQL) те се parse-ват и от тях се получават формули в релационна алгебра. После се прави план за изпълнение на израза, който накрая се компилира (и изпълнява).

Кортеж def

Това е друго наименование на ред от таблица в БД. По-конкретно - състои се от атрибути, които имат име и тип.
Например кортеж описващ студент би могъл да бъде двойката ("Петър", 80001), където "Петър" е стойността на атрибута име от тип string, а 80001 стойността на атрибута ФН от целочислен тип.

Релация def

Това е (мулти)множество от кортежи. Разбира се кортежите трябва да имат еднакви атрибути. Може да си го поредставяте като таблица пълна с някакви данни.
Обикновенно се отбелязва $R(A_1, A_2, \dots, A_n)$ - това ще рече релация на атрибутите (колоните) $A_1, A_2, \dots, A_n$.

Забележка: Релационната алгебра се занимава с множества от кортежи, а разширената релационна алгебра с мултимножества от кортежи. Ще гледам да обяснявам по-надолу кое твърдение за кое се отнася, по default е релационна алгебра.

Основни операции

Става дума за операциите дефинирани в релационната алгебра - значи оперират върху релации.

Множествени - обединение, сечение, разлика

Enough said! (освен че релациите трябва да имат кортежи от еднакъв вид, т.е. да са съвместими).

Проекция (Project)

Това е унарна операция, която на релация съпоставя нова, в която участват същите кортежи като в началната, но без определени атрибути (колони).

(1)

\begin{align} \pi_{\mbox{[attr list]}}(R) \end{align}

Например:

(2)

\begin{align} \pi_{A_1, A_3}(R(A_1, A_2, A_3)) = R(A_1, A_3) \end{align}

Селекция (Select, Restrict)

Това филтрира релацията, така че да останат само кортежи отговарящи на дадени условия.
Условията са просто функции на атрибутите, например $A_2 \ge 30 \And A_1 = "FMI"$.

(3)

\begin{align} \sigma_{\mbox[predicate]}(R) \end{align}

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

Това сменя имената на атрибутите на кортежите в дадена релация.

(4)

\begin{align} \rho_{\mbox{[new names]}}(R) \end{align}

Например

(5)

\begin{align} \rho_{B_1, B_2}(R(A_1, A_2)) = R(B_1, B_2) \end{align}

Това не сменя типа на атрибутите, само имената.

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

Е, знаете какво е декартово произведение - всеки кортеж от едната релация се залепя за всеки кортеж от друага релация и новополученото множество е новата релация.

(6)

\begin{align} R_1 \times R_2 \end{align}

Пример

(7)

\begin{align} R_1(A_1, A_2) \times R_2(B_1) = R(A_1, A_2, B_1) \end{align}

До тук бяха основните операции, всички други се получават с помощта на тези

Видове join

Theta join

Това е просто декартово произведение с условие, т.е след декартовото произведение остават само тези релации, удовлетворяващи условието. Да, това е просто декартово + селекция:

(8)

\begin{align} R \ltimes\!\!\!\!\!\!\rtimes_{\mbox{[predicate]}} S = \sigma_{\mbox{[predicate]}} (R \times S) \end{align}

Equijoin

Като Theta join, но условието е само съвпадение на колони.

Natural join

Като Theta join, но условието е всички атрибути с еднакви имена да имат еднакви стойности (т.е подтип на Equijoin).

(9)

\begin{align} R \ltimes\!\!\!\!\!\!\rtimes S \end{align}

Разширена релационна алгебра

По принцип в базите данни се работи с мултимножества. Там важат малко по-различни операции.

Обединение на мултимножества

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

Сечение на мултимножества

Всеки елемент се среща толкова пъти, колкото е минимума от срещания в двете начални.

Изваждане на мултимножества

Всеки елемент се среща толкова пъти, колкото е разликата между срещанията в първото и срещанията във второто (ако тази разликае положителна - иначе не се среща този елемент)

Unique - delta

Тази операция отстранява еднакви кортежи от релация. Т.е. остава релация, в която всеки кортеж се среща точно веднъж и всеки от началнaтa релация се среща (веднъж).

(10)

\begin{align} \delta(R) \end{align}

Sort - тау

Тази операция сортира по ред атрибути (първо по първия, ако има равни, по втория, и т.н.).

(11)

\begin{align} \tau_{\mbox{[attribute list]}}(R) \end{align}

Например:

(12)

\begin{align} \tau_{A_1, A_2}(R) \end{align}

Сортира първо по $A_1$ после по $A_2$.

Групиране - gamma

Вече знаете какво правят GROUP BY и MIN, MAX, AVG - е това е операцията от релационната алгебра която им съответства.

(13)

\begin{align} \gamma_{\mbox{[attributes to group by], [aggregate function list]}}(R) \end{align}

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

outher join

Това е като natural join, само че кортежите от ляво (или дясно), които не успеят да се "хванат" за нищо от дясно (или ляво) не се разкарват, а пак присъстват в резултата, само че в атрибутите на десния (левия) кортеж има NULL (демек нищо :)).

(14)

\begin{align} R \overset{\circ}{\ltimes\!\!\!\!\!\rtimes} S \end{align}

Разширена проекция

Това е проекция, разрешаваща преименуване на атрибути, както и аритметични операции между тях.

(15)

\begin{align} \boldsymbol{\pi}_{\mbox{[expression list]}}(R) \end{align}

Например

(16)

\begin{align} \boldsymbol{\pi}_{B \to C, A + B \to S}(R(A, B)) = R(C, S) \end{align}

Някой да сложи картинки с GraphViz.
Борих се 1-2 часа с него и не успях да го накарам да слага насочени и ненасочени стрелки в една диаграма.

Entry-Relationship(E/R) Model

Сега разбира се ще рисуваме картинки за да задоволим мениджърите и децата до 3 годишна възраст.
Ще описваме таблиците, редове, колоните и private/foreign keys в една база чрез подходящи схеми.
Извинявам се, имах предвид релациите, кортежите и връзките между тях.
Или както ще ги наричаме тук: същности, атрибути и връзки.

Същност - entity

Реален обект, концепция, събитие.
С други думи - това което пазим в една таблица - демек студент, покупка.

Множество същности - entity set

Е няма да казвам какво е това. (студенти, покупки).

Атрибут

Свойство на една същност. Например студента ще има име и ФН, покупката ще има количество и продукт.
Има ключови атрибути - множество от атрибути, които са уникални за всеки кортеж се нарича ключ (това значи че може да има няколко ключа …. да).

Връзка

Взаимоотношение между същности. Например - студент прави покупка. Т.е някои от същностите студенти са свързани с някои от същностите покупки.

Слаба същност

Ако една същност не е уникална даже да вземем всичките и атрибути, но е уникална ако включим връзката и с друга същност, то тя се нарича слаба същност.
Например: Ако записваме дати на login в таблица, като следим няколко hosts едновременно, може да се получи че в 2 хоста има логин в една дата, т.е трябва да имаме 2 екземпляра от датата в таблицата за логин, което е невъзможно (защото датата е единстврения атрибут, и той не е уникален). Решението е да сложим reference към зависимия тип (в случая host), така таблицата ще пази (date, hostId), отделно ще има таблица с хостовете (hostId, hostName).
Това на диаграмите се отбелязва с плътен правоъгълник (слабата същност) и плътен ромб за връзката ѝ с поддържащата плътност.

E/R диаграми

Ще рисуваме правоъгълници за всяко множество същности, балончета за всеки атрибут (свързват се към същностите) и ромбчета за всяка връзка, ромба се свързва с 2+ правоъгълника.

Екземпляр на E/R диаграми

Конкретен набор от данни, описани от дадена диаграма (демек snapshot на базата данни в определен момент).

Връзки

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

Множественост

С колко обекта се свързваме. Може 1 и 1+ (бележи се с $N$). Например всеки студент може да прави много покупки, но всяка покупка е на точно един студент (слагаме 1 на стрелката към покупката и $N$ на стрелката към студента).

Степен

Колко връзки има даден ромб (връзка) - т.е. колко същности са свързани от тази връзка. Поне 2 (студент прави покупка), но може и 3+ (договора свързва филма, звездата и студиото).

Роли

Всеки участник (entity set) в една връзка може да участва няколко пъти в нея (например връзката шеф свързва 2 обекта от таблицата Employee).

Забележка: Връзките също могат да си имат атрибути. Мен ако питате, това си е нов Entity set с връзки към останалите Entity set-ове, но кой ли ме пита. Всъщност точно това е начина по който една връзка от по-висока степен се превръща в нов Entity set + множество (толкова колкото е била степента) връзки от 2^ра степен.

Наследяване

Oh, well… ОО fanboys никога не спят.
Всеки entity set може да си има бащин Entity set, като всичките му ключови атрибути трябва да са на бащата (т.е. няма право да си добавя нови ключови атрибути). Отбелязва се с триъгълник с надписа "is a" сочещ към бащата.

Диаграми —> Схема

Релационна схема

Името на релацията и множеството от атрибутите ѝ се нарича схема на релацията.

Схема на базата данни

Това е съвкупността от всички релационни схеми за всички релации.

Домейн

Всеки атрибут може да заема само стойности от домейна. Например трябва да е целочислен, с плаваща запетая, низов (това съотвества на типа, който слагаме на всяка колона в SQL).

Домейните на атрибутите трябва да са прости - например дата не е прост атрибут, защото има ден, година, месец. (В SQL се използват и делими, но за теорията това е лошо :)).

Екземпляр на релацията

Това са конкретни данни, в една релация (множеството от кортежите). Те се променят сравнително често (като пишете INSERT, UPDATE,…). Самата Релация не се променя толкова често (само при ALTER TABLE .. и другите от същия чишит).

Преобразуване

Основни правила:

• Всяка същност се преубразува в релация (т.е множество от кортежи/tuples), като атрибутите на същността стават атрибути на релацията.
• Всяка връзка се преобразува в релация, имаща атрибути - ключовите атрибути от свързаните ѝ същности + всички атрибути на връзката.

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

• Понякога се обединяват същност със свързаната ѝ връзка (особено ако множествеността на връзката от другата страна е 1).
  • Ако релацията е 1:N тогава записваме ключа на релацията която е 1 в друата релация. Напеример ако имаме хора и покупки, всеки човек може да прави много покупки, но една покупка е на точно един човек (т.е хора 1:N покупки). Това значи че може в релацията за покупки да запишем ключа на релацията хора.
  • Ако връзката е 1:1 тогава трябва да решим в коя от 2те релации ще сложим ключа на другата (т.е да запишем самата връзка в една от 2те релации). Например ако имаме хора и номера на паспорти - всеки човек има един номер на паспорт (или няма) и всеки номер на паспорт има един човек (т.е човек 1:1 паспорт). Трябва да решим дали да сложим ключа на релацията паспорт към релацията човек, или ключа на релацията човек в релацията паспорт. (разбира се може да има отделна таблица в двойки (passport_id, person_id), но това прави схемата по-сложна). Rule of thumb: Ако едното притежава другото в някакъв смисъл (т.е е на по-високо ниво) тогава то държи ключа. В случая хора държи ключа към паспорти. (разбира се и да го направите наобратно няма да има кой знае каква разлика :)).
• Слабите същности не могат да си имат таблица самостоятелно - те се свързват с поддържащите ги същности - мен ако питате е точно като в случая с 1:N (1:1) - виж горната точка, поне се обработва по абсолютно същия начин.
• IS-A връзките (наследяването) трябва да се обработи по-внимателно. Има 3 подхода:
  • E/R подход - създаваме по една релация за всеки връх в дървото на наследяване (включително корена) и добавяме ключа на корена, ако не сме корен. Например: Person(person_id, name, birth_date), Teacher [is-a Person](university), Student [is-a Person](fn) - това дърво се преобразува в релациите Person(person_id, name, birth_date), Teacher (person_id, university), Student (person_id, fn). Както сами разбирате - нуждаем се по един join ако искаме да вземем информация която се намира по-нагоре в дървото.
  • OOP подход - това не го разбирам добре. За всяко поддърво (което тя май разбира всеки свързан граф….?) се прави таблица, която включва всички атрибути в това поддърво. Мен ако питатате това в слайдовете е грешно и това е просто разширение на горния подход, при който всяка същност си пази всички атрибути до корена (и не се нуждае от join за да ги получи). Т.е горния пример става: Person(person_id, name, birth_date), Teacher(person_id, name, birth_date, university), Student(person_id, name, birth_date, fn) - с други думи inline-ваме наследяването и забравяме за него (направили сме го по селския начин и не сме наследявали никъде). За повече инфо¹;
  • NULL value подход - обединяваме всичко в една таблица - т.е абсолютно всеки атрибут в дървото го има в таблциата. Ако съответния обект няма този атрибут записваме NULL стойност на това място. Забележка: На практика се добавя един атрибут, който казва съответния кортеж/ред коя точно същност отразява, но това го няма в лекциите.

Функционални изисквания

В тази и следващите глави ще опитаме формално да опишем кога една схема е добра, и кога не е. Добрите схеми нямат излишна информация и не страдат от insert/update/delete аномалии (т.е ако изтрием даден ред това да счупи конситентността в базата).

Мен ако питате всичко това е абсолютен bullshit, защото е много по-лесно човек да види аномалията/излишъка в базата от колкото да опита да обясни на теория защо е така, в коя нормална форма е схемата и после на тази база да я нормализира повече (да я направи по-добра). Това е все едно да ни учат защо TRUE && FALSE == FALSE на дълго и на широко. Или пък да научим стотици design patterns/antipatterns и после да ги търсим в код, за да обясняваме че кода смуче. Това че смуче е ясно, а това как да го оправим в повечето случаи е ясно, обаче няма време/ресурси за да се оправи, затова стои и си смуче.

Стига baby talk, хайде да си вземем изпита :)

FD (functional dependencies) - същност

Ако от дадено множество атрибути $A = \{ A_1, A_2, \dots, A_k \}$ може да "открием" еднозначно стойността на друго множество атрибути $B = \{ B_1, B_2, \dots, B_n \}$, ще казваме че $B$ функционално зависи от $A$, записваме $A \to B$.
Примери: Ако разглеждаме хора, имащи егн, име, адрес, телефон (за простота приемаме че имат по един адрес и телефон), то като "знаем" ЕГН-то може да открием останалите - защо? ами просто на едно ЕГН съответства точно едно име, един адрес и един телефон (или, другояче казано - един човек). Т.е името е функционално зависимо от ЕГН-то (както и адреса и телефона).

Тривиални, нетривиални, напълно нетривиални

• Тривиални FD: $A \to B$, ако $B \subseteq A$;
• Нетривиални FD: $A \to B$, ако $B \nsubseteq A$;
• Напълно нетривиални FD: $A \to B$, ако $A \cap B = \varnothing$.

Аксиоми на Армстронг - или просто правила за извод

Важно: Това не са аксиоми, а правила за извод². Те нямат доказателства!! (това което тя нарича доказателство е baby talk - не го казвай на изпита :)).
Тези твърдениица ни позволяват да образуваме нови функционални зависимости на базата на вече съществуващи. Те са коректни и пълни, демек новите функционални зависимости, получени чрез тях са верни (omfg, оставаше и да не са - нали ще ги докажеме), и са всички възможни, които могат да се получат (от даденото начално множество FD). Ето такава една теорема е по-интересна (че са пълни) но разбира се не се доказва (на нас).

Ax1 - рефлексивност

(17)

\begin{align} A \to B \quad \forall\ B \subseteq A \end{align}

С други думи може да си правим тривиални функционални зависимости.

Ax2 - разширение, попълнение

(18)

\begin{align} A \to B \Longrightarrow AW \to BW \quad \forall W \end{align}

Ax3 - транзитивност

(19)

\begin{align} A \to B \And B \to C \Longrightarrow A \to C \end{align}

Понеже може да ви се наложи да ги доказвате, един rule of thumb: Ако нещо е супер тривиално и просто не може да кажете нищо като обяснение, пробвайте с допускане на противното. Някак очевидно грешните неща минават за доказателство, а очевидно верните не :)) Пък и сте направили "допускане на противното" - т.е извършили сте някаква работа - мениджърите се радват.

Следствия

Обединение

(20)

\begin{align} A \to B \And A \to C \Longrightarrow A \to BC \end{align}

Псевдотранзитивност

(21)

\begin{align} A \to B \And BZ \to CZ \Longrightarrow AZ \to CZ \end{align}

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

(22)

\begin{align} A \to B \Longrightarrow A \to B' \quad \forall B' \subseteq B \end{align}

FD и ключове

Ето една нова дефиниция на ключ на релация с използването на FD:
Множество атрибути $A = \{ A_1, \dots, A_k \}$ наричаме ключ на релацията $R$, ако

• $A$ определя функционално всичките останали атрибути на $R$ (тогава $A$ се нарича суперключ);
• Не съществува $A' \subsetneq A$, което функционално определя всички останали атрибути на $R$ (всички останали без $A'$, a не без $A$).

Footnotes

1. http://blogs.microsoft.co.il/blogs/bursteg/archive/2007/09/30/how-to-model-inheritance-in-databases.aspx

2. http://en.wikipedia.org/wiki/Armstrong's_axioms