80.2.1. БАЗЫ ДАННЫХ

 
  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.