ТОРА (9) - Лекция №1 - Операции реляционной алгебры

Определения

Схема отношения

Это поименованная совокупность атрибутов.

<math>R = (A_1, ..., A_n)</math>, где <math>A_i</math> - некоторый атрибут из домена отношения.

<math>R = (</math>идентификатор поставщика, адрес, товар, цена<math>)=(A_1, A_2, A_3, A_4)</math>.

Здесь <math>(A_1, A_3)</math> - ключ, определяющий запись.

Степень схемы отношения

Это количество атрибутов в схеме.

Для <math>R = (A_1, A_2, A_3, A_4)</math> степень равна 4.

Экземпляр отношения

Это конкретная таблица с данной схемой отношения.

<math>R = (</math>идентификатор поставщика, адрес, товар, цена<math>)</math>.

Идентификатор	Адрес	Товар	Цена
ОАО "Х"	Ленина, 2	сахар	40
ОАО "У"	Комсомола, 25	соль	5

Кортеж

Любая одна строка в таблице экземпляра отношения.

Схема БД.

<math>A</math> - множество всех атрибутов некоторой предметной области (универсальная схема отношения).

<math>R_1, ..., R_n</math> - совокупность атрибутов.

Тогда <math>\rho=(R_1, ..., R_n)</math> называется схемой БД.

Пример:

<math>A = (A_1, A_2, A_3, A_4)</math>

и две схемы: <math>R_1 = (A_1, A_2)</math> и <math>R_2 = (A_1, A_3, A_4)</math>

Так как <math>R_1\bigcup R_2 = A</math>, то <math>\rho = (R_1, R_2)</math>.

Примеры схем БД

Пример "плохой" схемы БД

Пусть <math>A = (</math>идентификатор поставщика, адрес, товар, цена<math>)</math>

и есть одна схема <math>\rho = R_1 = A</math>

Данная схема БД обладает следующими недостатками (аномалиями):

• избыточность. Адрес поставщика повторяется для каждого поставляемого им товара;
• потенциальная противоречивость. Если у поставщика меняется адрес, то его необходимо изменить во всех кортежах, в которые он входит;
• аномалия включения кортежа. В выбранном отношении <math>R</math> пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар;
• аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике.

Первопричиной этих недостатков является то, что <math>R_1</math> не находится в 3НФ

Пример "хорошей" схемы БД

Пусть <math>A = (</math>идентификатор поставщика, адрес, товар, цена<math>)</math>

<math>R_1 = (</math>идентификатор, адрес<math>)</math>

<math>R_2 = (</math>товар, цена<math>)</math>

Схема <math>\rho = (R_1, R_2)</math> находится в 3НФ и не обладает перечисленными выше недостатками.

Основные операции реляционной алгебры

Объединение отношений

<math>R=R_1\bigcup R_2</math>

Объединение отношений - это отношение, каждый кортеж которого принадлежит либо <math>R_1</math>, либо <math>R_2</math>. Дублирование кортежей не допускается.

<math>A_1</math> <math>A_2</math> <math>R_1</math> 1 2 3 4

<math>A_1</math> <math>A_2</math> <math>R_2</math> 5 6 1 2

	<math>A_1</math>	<math>A_2</math>
<math>R</math>	1	2
	3	4
5	6

Пересечение отношений

r=r_1\пересечение r_2

Пересечение отношений - это отношение, каждый кортеж которого принадлежит и r_1, и r_2

    A_1 A_2

r_1= 1 2

     3   4

    A_1 A_2

r_2= 5 6

     1   2

    A_1 A_2

r= 1 2

Разность отношений

r=r_1-r_2

Разность отношений - это отношение, кортежи которого принадлежат r_1 и не принадлежат r_2

    A_1 A_2

r_1= 1 2

     3   4

    A_1 A_2

r_2= 5 6

     1   2

    A_1 A_2

r= 3 4

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

R, S - две схемы отношения со степенями k_1 и k_2 t = R \x S

Декартово произведение - это отношение t со степенью k_1+k_2, кортежи которого получаются конкатенацией кортежей из отношений R и S.

   A_1 A_2

R = 1 2

    3   4

   A_1 A_3

S = 5 6

    7   8
   
   R.A_2 A_2 S.A_1 A_3

t = 1 2 5 6

     1    2    7    8
     3    4    5    6
     3    4    7    8

Проекция

t=\заглавнаяпи_{A_i1 ... A_ik}(R)

Проекция - это отношение, каждый кортеж которого состоит из значений атрибутов A_i1 ... A_ik исходного отношения R.

   A_1 A_2 A_3 A_4

R = 1 2 3 4

    7   8   9   10
    3   4   5   6
    3   4   7   6
                             A_1 A_4

t=\заглавнаяпи_{A_1, A_4}(R)= 1 4

                              7   10
                              3   6

Селекция

t=\sigma_F (R)

Селекция - это отношение, каждый кортеж которого принадлежит исходному отношению R и удовлетворяет логическому условию F.

   A_1 A_2 

R = 1 2

    9   8
    3   3

                           A_1 A_2 

t=\sigma_{A_1 <= A_2} (R) = 1 2

                            3   3

Естественное соединение

t = R \|><| S

Определение этой операции следует из способа построения естественного соединения.

   A_1 A_2 A_3

R = 1 2 3

    4   6   7

   A_1 A_2 A_4 A_5

S = 1 2 7 8

    8   9   10  11
    4   6   9   16

Правило построения естественного соединения:

• построить декартово произведение R \x S

     R.A_1 R.A_2 A_3 S.A_1 S.A_2 A_4 A_5

t_1 = 1 2 3 1 2 7 8

      1     2     3    8     9    10  11
      1     2     3    4     6    9   16
      4     6     7    1     2    7   8
      4     6     7    8     9    10  11
      4     6     7    4     6    9   16

• выбрать из этого произведения кортежи по условию R.A_1=S.A_i1 ... R.A_k=S.A_ik, где A_1=A_k - общие атрибуты в схема отношений R и S (предполагается, что эти атрибуты занимают одинаковое положение в отношениях. Хотя не обязательно)

     R.A_1 R.A_2 A_3 S.A_1 S.A_2 A_4 A_5

t_2 = 1 2 3 1 2 7 8

      4     6     7    4     6    9   16

• удалить из полученного отношения S.A_i1 ... S.A_ik, потому что они будут дублирующими

     A_1 A_2 A_3 A_4 A_5

t_3 = 1 2 3 7 8

      4   6   7   9   16