Реляционные базы данных. Функции

Реляционные базы данных Rn  D1  D2  ... Dn Di - атрибут {D1, D2 ,...,Dn} - тип записи R4  D1  D2  D3  D4 - расписание экзаменов R4 1 2 3 4 5 6 D1 A-1 A-2 A-2 A-1 A-1 A-2 D2 Информатика Дискретная математика Математический анализ Дискретная математика Математический анализ Информатика D3 03.09. 03.09. 06.09. 07.09. 10.09. 10.09. D4 ауд.716 ауд.718 ауд.718 ауд.716 ауд.718 ауд.716 D1  {A-1, A-2} D2 {Информатика, Дискретная математика, Математический анализ} D3  {03.09.,06.09.,07.09., 10.09.} D4 {ауд.716, ауд.718} Первая нормальная форма Операции: объединение, пересечение, разность, прямое произведение. Операция селекции - построение подмножества кортежей по заданному свойству (множеству свойств) (сечение) Rn  ( x1, x2 ,..., xn ) | ( x1, x2 ,..., xn )  Rn & xi  ai  R4  R4 - расписание экзаменов по Дискретной математике R4 D1 D2 D3 D4 2 4 A-2 Дискретная математика A-1 Дискретная математика 03.09. 07.09. ауд.718 ауд.716 Операция проекции Rn  D1  D2  ... Dn    iR,ni ,...,i  ai1 , ai2 ,...,aim | a1, a2 ,...,an   Rn 1 2 m R4 1 2 3 4 5 6  2R,43 1 2 3 4 5 6 D1 A-1 A-2 A-2 A-1 A-1 A-2 D2 Информатика Дискретная математика Математический анализ Дискретная математика Математический анализ Информатика D2 Информатика Дискретная математика Математический анализ Дискретная математика Математический анализ Информатика D3 03.09. 03.09. 06.09. 07.09. 10.09. 10.09.  D3 03.09. 03.09. 06.09. 07.09. 10.09. 10.09. на Di1 , Di2 ,...,Dim D4 ауд.716 ауд.718 ауд.718 ауд.716 ауд.718 ауд.716 Операция соединения по атрибуту Di D2 R4 D1 1 A-1 Информатика 2 A-2 Дискретная математика D3 03.09. 03.09. D4 ауд.716 ауд.718 Q4 D1 1 A-2 2 A-1 D3 06.09. 07.09. D4 ауд.718 ауд.716 D2 Математический анализ Дискретная математика Соединение по атрибуту D1 D2 D4 D3 D2 D4 D3 R7 D1 03.09. ауд.716 Дискретная математика 07.09. ауд.716 1 A-1 Информатика 2 A-2 Дискретная математика 03.09. ауд.718 Математический анализ 06.09. ауд.718 f  A B Функции a  A a, b   f , a, c   f  b  c f : A B A  B f a, b f , b  f (a) P={(1,2),(2,3),(3,2)} – функция, f A  a  A | b  B : b  f (a) f B  b  B | a  A : b  f (a) A  A1  A2  ... An A - домен функциональность b - образ элемента a  A a - прообраз элемента b B Q={(1,2),(2,3),(1,3)} – не функция тотальная функция f A  A - n местная функция f : An  A - операция B - кодомен Типы функций. 1. Инъективная b  f (a1), b  f (a2 )  a1  a2 2. Сюръективная b B a  A : b  f (a) 3. Биективная y f : 0,1  0,1 fi : R  R 1 f2 f1( x)  e x f3 f1 f4 O 1 x f 2 ( x)  x  sin x f3 ( x )  2 x  1 f : A B g  f  id A f  h  id B g:B A h: B  A g - левая обратная для f h - правая обратная для f Теорема. Функция f инъективна, если и только если она имеет левую обратную функцию. Функция f сюръективна, если и только если она имеет правую обратную функцию. Теорема. Если f инъективна, то |A|≤|B|. Если f сюръективна, то |A|≥|B|. a1 a2 a3 a4 A b1 a1 b2 a2 b3 a3 b4 a4 b5 a5 B A Если f биективна, то |A|=|B|. b1 b2 b3 b4 B Базы данных Операция проекции Rn  D1  D2  ... Dn на Di1 , Di2 ,...,Dim    iR,ni ,...,i  ai1 , ai2 ,...,aim | a1, a2 ,...,an   Rn 1 2 m  pI : D1  D2  ... Dn  Di1  Di2  ... Dik Функция естественной проекции: pI ( x1, x2 ,..., xn )  ( xi1 , xi2 ,...xik ) 1  i1  i2  ...  ik  n I  {i1, i2 ,...,ik } Функциональная зависимость между атрибутами R D2 S   2,43 1 Информатика 2 Дискретная математика 3 Математический анализ 4 Дискретная математика 5 Математический анализ 6 Информатика D3 03.09. 03.09. 06.09. 07.09. 10.09. 10.09. S  D2  D3 S  {(И ,03.09), ( ДМ ,03.09), (МА,06.09), ( ДМ ,07.09), (МА,10.09), ( И ,10.09)} - не функция D3 не является функционально зависимым от D2 {Di1  Di2  ... Dim } функционально зависимо от {D j  D j  ... D j } 1 2 k R4 1 2 3 4 5 6 D1 A-1 A-2 A-2 A-1 A-1 A-2 (A-1,И) (A-2,ДМ) D2 Информатика Дискретная математика Математический анализ Дискретная математика Математический анализ Информатика … D3 03.09. 03.09. 06.09. 07.09. 10.09. 10.09. D4 ауд.716 ауд.718 ауд.718 ауд.716 ауд.718 ауд.716 {D1, D2} функционально определяет {D3 , D4} R P12  1,24 P12  P34 R4 P34   3,4 - функция (биекция) (03.09.,ауд.716) (03.09.,ауд.718) Ключ - множество атрибутов, значения которых единственным {D1, D2} {D2 , D3} образом определяют запись