THIS SECTION IS UNDER CONSTRUCTION
Базы данных / | \ Простые Реляционные Объектные
Основная идея реляционной алгебры: т.к. отношения являются множествами то средства манипулирования ими тоже являются множествами. Def === Множество - любая определенная совокупность объектов. Объекты из которых составлено множество называются его элементами. Элементы множества по определению различны и отличимы друг от друга. Def === Мультимножество - одинаковые элементы могут входить несколько раз. Def === Прямое (Декартово) произведение двух множеств A x B- множество содержащие все возможные пары (a,b), где a - принадлежит множеству A, а B - принадлежит множеству B. Реляционная алгебра
Def === Пусть A и B - два множества. Бинарным отношением из множества A в множество B называется тройка [A,B,R], где R - подмножество декартово произведения A x B. (Среди элементов множеств A и B могут быть такие, какие не входят ни в одну из пар определяющих отношение R).
(Собственно отношение R из множества А во множество B - это в общем виде не тоже самое что отношение R из множества B во множества A.
Def === Пусть R - отношение из множества A во множество A. Тогда R: рефлексивно, если для любого элемента а множества A в отношение входит aRa антирефлексивно, если для любого элементв множества A в отношение не входит aRa симметрично, если для любых элементов a и b множества A если в отношение входит aRb, то входти и bRa антисимметрично, если для любых элементов a и b множества A если в отношение входят aRb и bRA, то a = b транзитивно, если для любых элементов a,b и с множества A если в отношение входят aRb и bRc, то aRc тоже входит в отношение линейным, если для любых элементов a и b множества A либо a = b, либо aRb входит в отношение, либо bRa входит в отношение Примеры: Рефлексивное отношение: >= a >= a всегда входит в отношение >=
Нерефлексивное отношение: > a > a всегда невходит в отношение > Симметричное отношение: = из a = b, следует b = a Антисимметричное: >= если a >= b, и b >= a, то a = b Транзитивное: > если a > b, и b > c, то a > c Def === Ассимметричное транзитивное отношение - называется отношением порядка. Если отношение порядка рефлексивно, то оно называется отношением нестрогово порядка Если отношение порядка антирейлексивно, то оно называется отношением строгово порядка Если отношения порядка линейно, то оно называется отношением линейного порядка Если отношение порядка не линейно, то оно называется отношением частичного порядка Def ==== Если для любого a, (a,b) принадлежит оношению и (a,c) принадлежит отношению, следует что b = c, то такое отношение называется функциональным или функцией. Def === Если из b = f(a1) и b = f(a2) следует что a1 = a2, то такая функция называется иньекцией.
Def === Если для любого b принадлежащему B cуществует a принадлежащий A, такой что b = f(a), то такая функция называется сюрьекцией
Def === Если функция одновременно является и иньекцией и сюрьекцией то такая функция называется биекцией.
Домен - множество фтомарных значений одного и того же типа Отношение - множество, по определению не имеет совпадающих элементов Заголовок отношения содержит множество аттрибутов Тело отношения содержит множество меняющихся во времени кортежей Кортеж - множество пар (аттрибут-значение) Степень отношения - число его аттрибутов Мощность отношения - число кортежей Ключ - минимальный набор аттрибутов по значению которых можно однозначно найти элементы сущности.
Операции: Теоретико-множественные Объединение Пересечение Разность Прямое произведение отношений Специальные реляционные Ограничение отношения Проекция отношения Соотношение отношений Деление отношений Примитивы Добавление Удаление Изменение Отношение (binary relation) R между элементами множеств A и B - подмножество декартово произведения AxB Пишут что если (a,b) принадлежит R, то aRb например a>b или a<=b итд.
все X, которые принадлежат хотя бы одному A или B UNION Объединение
все X, которые принадлежат одновременно A и B INTERSEC A INTERSEC B = A MINUS (A MINUS B) Пересечение
все Х входящие в А, но не входящие в B MINUS Разность
Декартого произведение в результате имеем {x,y} для каждого х в А и y в B. TIMES Пример A {a,b} B {a,b,c} AxB {(a,a),(a,b),(a,c),(b,a),(b,b),(b,c)} Прямое произведение
Выборка все Х из А для которых выполняется условие ограничения A WHERE c WHERE c1 AND c2 (A WHERE c1) INTERSECT (A WHERE c2) WHERE c1 OR c2 (A WHERE c1) UNION (A WHERE c2) WHERE NOT c1 A MINUS (A WHERE c1) Ограничение отношения
Отношение с заголовком (X,Y..Z) и телом вида (x,y, ...z) таких для которые в отношении А найдуться кортежи со значением X = x, Y =y, Z = z A[X,Y,...Z] Проекция
Последовательное применение декартового произведения и выборки (A TIMES B) WHERE c Соединение R c T по столбцам i и j - R[i (-) j] T, то есть строки в декартовом произведении R X T, в котором значение из i столбца R, находиться в отношении (-) со значением j-го столбца T. Соединение
Эквисоединение - когда (-) - это отношение равенства
Естественное соединение - эквисоединение в котором исключен столбец j.
Композиция - эквисоединение, где исключены столбцы по которым производилось соединение. Тетасоединение - соединение где отношение (-) - отлично от отношения равенства. Sort-Merge Join предварительная сортировка таблиц по атрибутам на которых будет делаться join. Join Selection Factor определяет насколько разряжены атрибуты по которым будет делаться join Nested loop join Hash Join
A DIVIDEBY B A DIVIDEBY B = A[X] MINUS ((A[X] TIMES B) MINUS A)[X] Реляционное деление - имеет два операнда - бинарный {X,Y} и унарный {Y}. Результатирующее отношение состоит из одноатрибутных кортежей включающих значение первого атрибута 1го операнда таких что множество значений 2го аттрибута (при фиксированном значение 1го аттрибута) совпадает с множеством значений второго операнда. Деление
M1 M2 M3 = M1 divideby M2 A B C A B C -------- --- ------- a b d a b d a c d e c d e b d e c d
M1 M2 M3 = M1 divideby M2 A B C D A B C D ------------ ------ ------- a b c d a b c d a b b d e d b d a b e f e f e d c d e d b d e d e f
M1 M2 M3 = M1 divideby M2 A B C D A B C D ------------ ------ ------- a b c d c d a b a b e f e f e d b c c d e d c d e d e f c b e f
Мощность множества - число элементов в нем |0| = 0 | A or B | = |A| + |B| - |A and B| | A X B | = |A| * |B| Реляционные базы данных - данные хранятся в таблицах primary key foreign key
Типы бинарных связей 1:1 1:N N:M
Назначение нормальных форм - приведение структуры базы данных к виду обеспечивающиму минимальную избыточность Классы отношений DKNF 5NF 4NF BCNF 3NF 2NF 1NF Нормальные формы
1NF Таблица находится в первой нормальной форме если каждый ее атрибут атомарен и все строки различны.
2NF Таблица находится во второй нормальной форме, если она находиться в первой нормальной форме и при этом любой из ее атрибутов не входящих в состав первичного ключа функционально полно зависит от первичного ключа
3NF Таблица находится в третьей нормальной форме если она находиться во второй и при этом любой ее неключевой атрибут функционально зависит только от первичного ключа.
NFBC Нормальная форма Бойса-Кодда 3NF + Все зависимые от первичного ключа атрибуты должны быть потенциальными ключами отношения
4NF NFBC + не содержит нетривиальных многозначных зависимостей Def === Пусть существует отношение R, а так же три его подмножества A,B и С В многозначно зависит от A, тогда и только тогда когда множество значений атрибута B соответсвующее паре значений [a,c], где a принадлежит A, а c - принадлежит C, зависит только от a, и не зависит от с.
5NF 4NF + любая многозначная зависимость является тривиальной
DKNF (Domain-Key Normal Form) 6NF
Свойства транзакции: Атомарность - либо выполняется, либо нет Непротиворечивость - оставляет данные в непротиворечивом состоянии (например для таблиц - не должно получаться строк дубликатов) Изоляция - во время выполнения транзакции другие процессы не должны видеть данные в промежуточном состоянии. Долговечность - изменения сделаннные успешной транзакцией остаются даже если сбой питания. Транзакции
Состояния транзакции
Типы транзакций
RC - Recoverable - каждая транзакция коммититься только после того, как все транзакции из которых она читает закоммичены. ACR - Avoid Cascading Rollback - Каждая транзакция может читать только закоммиченные данные. ST - Strict - каждая транзакция может читать и писать закоммиченные данные.
Проблемы доступа Неповторяющиеся чтение (non-repeatable read)
Грязное чтение (dirty read) Temporary update --------------------------------------- T1 T2 --------------------------------------- READ(X) ... WRITE(X) ... ... READ(X) ... ... ... WRITE(X) ... READ(Y) --------------------------------------- T1 fails and abort.
Потерянное обновление (lost update) --------------------------------------- T1 T2 --------------------------------------- READ(X) ... READ(X) ... ... ... ... WRITE(X) ... READ(Y) ... ... ... ... WRITE(X) WRITE(Y) ---------------------------------------
Фантомная вставка (phantom insert)
THIS SECTION IS UNDER CONSTRUCTION
Уровни изоляции транзакций 0 - Неподтверждённое чтение (Read Uncommited, Dirty Read, грязное чтение) чтение незафиксированных изменений своей транзакции и конкурирующих транзакций, возможны нечистые, неповторяемые чтения и фантомы 1 - Подтверждённое чтение (Read Commited) - чтение всех изменений своей транзакции и зафиксированных изменений конкурирующих транзакций, нечистые чтения невозможны, возможны неповторяемые чтения и фантомы 2 - Повторяемое чтение (Repeatable Read ,Snapshot) - чтение всех изменений своей транзакции, любые изменения, внесённые конкурирующими транзакциями после начала своей недоступны, нечистые и неповторяемые чтения невозможны, возможны фантомы 3 - Упорядоченный - (Serializable, сериализуемый) - упорядоченные (cериализуемые) транзакции. Идентичен ситуации при которой транзакции выполняются строго последовательно одна после другой. То есть транзакции, результат действия которых не зависит от порядка выполнения шагов транзакции (запрещено чтение всех данных изменённых с начала транзакции, в том числе и своей транзакцией). Фантомы невозможны.
Реализация транзакций Блокировка доступа Журнализация изменений (Write ahead Logging) (in-place update) Shadow Paging (copy-on-write) измененная версия страницы записывается в другое место
Two Phase Locking Транзакция следует двухфазному протоколу если все locks производяться до первого unlock. И в shrinking phase не происходит новых locks.
Борьба с DeadLocks Wait-Die схема Ресурс захвачен Tj, нужен Ti Если timestamp(Ti) < timestamp(Tj) Ti ждет иначе Abort Ti, restart later с тем же timestamp Wound-Wait схема Ресурс захвачен Tj, нужен Ti Если timestamp(Ti) < timestamp(Tj) Abort Tj, restart later с тем же timestamp иначе Ti ждет
Distributed Transaction Coordinator Phase 0: Координатор инициирует протокол Присылает действия для участников Phase 1: Координатор спрашивает всех участников - могут ли они commit Участники отвечают - да или нет Phase 2: Если все ответили да - координатор посылает Commit участникам иначе присылает Abort Участники присылают - Has Commited/Have Aborted
Блокировки Блокировка базы:
Блокировка таблицы:
Блокировка страницы:
Блокировка строки:
Shadow-paging
WAL (Write-Ahead Logging) Журналирование изменений (ARIES) LSN (Log Sequence Number) Type - compensation [откат части транзакции], update, commit TransID - transaction identifier PrevLSN PageID - идентификатор страницы затронутой операцией UndoNxtLSN - номер следущей записи журнала, которую надо будет обработать при откате
Фазы обработки: Analysis Redo Undo
Представление (View) - виртуальная таблица, результат запроса из базы данных. Изменение базы приводит к изменению представлений. Представление
Индекс - объект базы данных, создаваемый с целью повышения производительности запросов. кластерный индекс - таблица храниться в оптимизированном порядке Некластерный индекс - внешний Индекс
Тригер - хранимая процедура особого типа, которая вызывается не непосредственно, а при наступлении определенного события - INSERT или DELETE строки, UPDATE в столбце. итд Триггеры бывают - BEFORE и AFTER. Триггеры