Файл: Тема 6. Математические основы реляционных баз данных.pdf

1.  Атом – формула; 

2.  Если  ,   - формулы, то   &  ,      , 

 - формулы; 

3.  Если   – формула, то  s ,  s  - формулы. 

Здесь    –  квантор  существования,    -  квантор  общности.  Вхождение 

переменной s в формулу   в последнем случае считается связанным квантором. 

Вхождение переменной, не попадающее в область действия никакого квантора, 

- свободное. Подстановка значений возможна только для свободных вхождений 

переменных. 

4.  Порядок старшинства операций: сравнение,  ,  ,  ,   ,  . 

В  выражении  реляционного  исчисления  с  переменными-кортежами 

{t| (t)} переменная-кортеж t - единственная свободная в   переменная. 

Примеры. 

1.  R S = {t|R(t) S(t)}, отношения R и S имеют одинаковую арность; 

2.  R-S = {t|R(t)& S(t)}; 

3.  Если R и S - отношения арности r и s, то  

R S = {t

(r+s)

| u

(r)

v

(s)

(R(u)&S(v)&t[1]=u[1]&…&t[r+1]=v[1]&…&t[r+s]=v[s])} 

4. 

)

(

...

2

1

R

k

i

i

i

{t

(k)

| u(R(u)&t[1]=u[i

1

]&…&t[k]=u[i

k

])}; 

4. 

F

(R)={t|R(t)&F },  где  F   образуется  из  F  заменой  номера  i  на 

выражение t[i]. 

Безопасные выражения 

Определенное  выше  исчисление  с  переменными-кортежами  позволяет 

представлять бесконечные отношения, например {t| R(t)}, которое невозможно 

реализовать  физически.  Для  устранения  бесконечных  отношений  множество 

допустимых выражений реляционного исчисления ограничивают безопасными 

выражениями  { t |  (t)}, для которых можно показать, что каждый компонент 

любого  t,  удовлетворяющего 

(t),  должен  быть  элементом  специального 

множества  DOM( ).  Множество  DOM( )  определяется  как  множество 

символов,  которые  либо  явно  появляются  в  ,  либо  служат  компонентами 

какого-либо  кортежа  в  некотором  отношении,  упоминаемом  в  .  Множество 

DOM( ) конечно. 

Редукция  реляционной  алгебры  к  реляционному  исчислению  с 

переменными-кортежами. 

Справедливо утверждение: для каждого выражения реляционной алгебры 

существует  эквивалентное  ему  безопасное  выражение  реляционного 

исчисления с переменными-кортежами. 

Реляционное исчисление с переменными на доменах. 

Исчисление с переменными на доменах строится аналогично исчислению 

с переменными-кортежами: 

1. 

В  исчислении  с  переменными  на  доменах  вместо  переменных-

кортежей 

используются 

переменные 

на 

доменах, 

представляющие компоненты кортежей. 

2. 

Атомы: 

a.   R(x

1

,x

2

,…x

k

), где R – отношение, x

i

 - константа или переменная 

на домене. Атом утверждает, что (x

1

,x

2

,…x

k

) – кортеж R. 

b.   x y,  где  x,y  –  константы  или  переменные  на  доменах,    -

сравнение. Выражение утверждает, что x находится в отношении 

 к y. 

3. 

Формулы используют связки &,  ,   и кванторы ( x)( x), где x – 

переменная на домене. 

Понятия  свободного  и  связанного  вхождения  переменных,  безопасного 

выражения  определяются  так  же,  как  и  в  исчислении  с  переменными-

кортежами.  Выражения  исчисления  с  переменными  на  доменах  имеют  вид 

{x

1

,x

2

,…x

k

| (x

1

,x

2

,…x

k

)},  где 

  -  формула  со  свободными  переменными 

x

1

,x

2

,…x

k

. 

Сведение  исчисления  с  переменными–кортежами  к  исчислению  с 

переменными на доменах. 

Пусть  задано  выражение  с  переменными-кортежами  {t| (t)}.  Переход  к 

эквивалентному  выражению  с  переменными  на  доменах  производится  по 

следующим правилам. 

Если t имеет арность k, введем k новых переменных на доменах t

1

,t

2

,…t

k

 и 

заменим  исходное  выражение  следующим:  {t

1

,t

2

,…t

k

|

(t

1

,t

2

,…t

k

)}.  Формула   

получается  из  формулы  ,  в  которой  любой  атом  R(t)  заменяется  атомом 

R(t

1

,t

2

,…t

k

), а каждое свободное вхождение t[i] – переменной t

i

. 

Далее  для  каждого  квантора  ( u)( u)  вводим  m  новых  переменных  на 

доменах u

1

,u

2

,…u

m

 (m - арность u). В области действия квантора заменяем u[i]на 

u

i

  и  R(u)  на  R(u

1

,u

2

,…u

m

).  Заменяем  знаки  ( u)( u)  на  ( u

1

)…  ( u

m

)  (( u

1

) 

…( u

m

)).  В  результате  получаем  выражение  исчисления  с  переменными  на 

доменах, эквивалентное исходному выражению. 

Справедливо  утверждение:  для  каждого  безопасного  выражения 

реляционного 

исчисления 

с 

переменными 

кортежами 

существует 

эквивалентное  ему  безопасное  выражение  исчисления  с  переменными  на 

доменах. 

Можно  также  показать,  что  для  каждого  безопасного  выражения 

реляционного  исчисления  с  переменными  на  доменах  существует 

эквивалентное ему выражение реляционной алгебры. 

Практические задания для самостоятельного выполнения 

Выполнить 

следующие 

операции 

над 

двумя 

совместными 

отношениями R1, R2 с идентичной структурой.  

 R1 

ФИО  

Год рождения  

Должность  

Кафедра  

Иванов И.И.  

1968  

Зав. кафедрой  

22  

Сидоров С.С.  

1973  

Доцент  

22  

Козлов К.К.  

1980  

Ассистент  

23  

R2 

ФИО  

Год рождения  

Должность  

Кафедра  

Цветкова Н.Н.  

1965  

Доцент  

23  

Петрова П.П.  

1973  

Ст. преподаватель  

22  

Козлов К.К.  

1980  

Ассистент  

23  

1.  Объединение. 

В 

результате 

операции 

построить 

новое 

отношение R = R1 U R2  

2.  Пересечение. Результирующее отношение RP = R1   R2  

3.  Вычитание. В результате строится новое отношение RV = R1 - R2