Учебное пособие Для студентов университетов Специальностей «Информатика», «Прикладная математика»

 
 4 
2 
3 
5 
 3 
1 
4 
2 
 2 
2 
6 
NULL 
 NULL 
3 
5 
4 
2.  Пример,  демонстрирующий  выполнение 
θ-полусоединения  отно-
шений R и S. 
 
A B 
C 
 
D E 
 
1 
2 
3                       S = 
4 
5 
R = 
4 
3 
2   
3 
2 
 2 
7 
1 
 
 
 
 1 
2 
6 
 
 
 
 
 
A B C 
 1 
2 
3 
R 
⎜>
C<D
S = 
4 3 2 
 2 
7 
1 
3.  Пример,  демонстрирующий  выполнение  естественного  полусоеди-
нения отношений R и S. 
 
A B C  
B C D 
R = 
7 
3 
1                           S = 
4 
3 
1 
 
2 4 1  
4 1 2 
 
 
A B C 
R 
⎢> S = 
2 4 1 
 
 
3.2. РЕЛЯЦИОННОЕ ИСЧИСЛЕНИЕ. 
В отличие от реляционной алгебры, которая указывает, как получить 
требуемое отношение из имеющихся отношений, реляционное исчисле-
ние  указывает  свойства  искомого  отношения  без  конкретизации  проце-
дуры его получения. Математической основой реляционного исчисления 
является исчисление предикатов – один из разделов математической ло-
гики.  В  теории  исчисления  предикатов  под  предикатом  понимается 
функция,  значения  которой  являются  высказываниями.  Высказывание 
может  быть  истинным  или  ложным.  Чтобы  задать  n-местный  предикат 
P(x
1
, …, x
n
),  следует  указать  множества  D
1
, …, D
n
 – области  изменения 
предикатных  переменных    x
1
, …, x
n
.  Синтаксически  задание  n-местного 
 
23

 
предиката  осуществляется  указанием  формулы  логико-математического 
языка, содержащей n переменных. В наиболее распространенном случае 
такой  язык  содержит  предикатные  переменные  x,  y,  z, … функциональ-
ные  символы  f,  g,  h, … с  различным  количеством  аргументных  мест  и 
предикатные символы P, Q, R, … также с различным количеством аргу-
ментных  мест.  Из  переменных  и  функциональных  символов  конструи-
руются  термы  языка,  содержательно  интерпретируемые  как  имена  объ-
ектов исследования. Если P есть n-местный предикатный символ, n 
≥ 0, а 
t
1
, …, t
n
 – термы, то P(t
1
, …, t
n
) есть, по определению, атомарная форму-
ла. Содержательно P(t
1
, …, t
n
) означает, что истинно высказывание, гла-
сящее, что t
1
, …, t
n
 связаны отношением P. Из атомарных формул с по-
мощью пропозициональных связок и кванторов конструируются форму-
лы языка. Обычный набор связок состоит из операторов сравнения, а на-
бор кванторов включает конъюнкцию, дизъюнкцию, импликацию, отри-
цание,  квантор  «для  всех»,  квантор  «существует».  Вхождения  перемен-
ной x в формулу 
ϕ называется связанным, если x входит в часть ϕ вида 
∃xϕ или ∀xϕ. Остальные вхождения называются свободными. 
Для  баз  данных  исчисление  предикатов  существует  в  двух  формах: 
реляционного  исчисления  кортежей  и  реляционного  исчисления  доме-
нов. В реляционном исчислении кортежей задача состоит в нахождении 
таких кортежей, для которых предикат является истинным. Это исчисле-
ние основано на переменных кортежа, т. е. таких, для которых допусти-
мыми значениями могут быть только кортежи данного отношения.  Опи-
сательную часть исчисления можно представить в виде  
RANGE OF <переменная> IS <список>. 
Здесь <переменная> – это идентификатор переменной кортежа, <список> 
– конструкция вида X
1
[, X
2
[, …, X
n
]…]. Список содержит элементы, каж-
дый из которых является либо отношением, либо выражением над отно-
шениями.  Область  допустимых  значений  <переменной>  образуется  пу-
тем объединения значений всех элементов списка. Выражение реляцион-
ного исчисления, формирующего запрос на языке исчисления кортежей, 
упрощенно можно записать в виде 
(Y
1
[, Y
2
[…,Y
m
]…]) [WHERE wff]. 
Здесь  Y
i
 – это запись вида  
{<переменная> 
⏐<переменная>.<атрибут>} [AS <атрибут>]  
Соответственно wff  – well-formed formula (правильно построенная фор-
мула) – это предикат, который записывается одним из следующих типов: 
 <условие> 
 
24

 
 NOT  wff  
 <условие> AND wff  
 <условие> OR  wff  
IF <условие> THEN wff  
EXISTS <переменная> (wff)  
FORALL <переменная> (wff)  
(wff)  
Например, предположим, что имеется три отношения О1, О2, О3, 
 
ПР 
КАФ  ФАК    СТУД КУРС  ГР 
  ПР 
СТУД  ЧАС 
П1 
К1 
Ф1  
С1 3  2   
П1 
С1 10 
П2 
К1 
Ф1  
С2 3  1   
П2 
С2 10 
П3 
К2 
Ф1  
С3 4  2   
П2 
С3 10 
 
 
 
  С4 4  1   
П3 
С1 10 
отношение О1 
 
    
П3 
С4 20 
 
 
 
 
отношение О2  
   
 
 
 
 
   
 
 
 
отношение О3 
 
в первом из которых указываются сведения о преподавателях (препода-
ватель, кафедра, факультет), во втором – сведения о студентах (студент, 
курс,  группа),  в  третьем – сведения  о  количестве  часов  консультаций 
(преподаватель, студент, часы). Создадим список преподавателей,  рабо-
тающих на кафедре К1: 
RANGE OF S IS O1 
(S.ПР) WHERE  S.КАФ=’К1’ 
Создадим список преподавателей, студентов четвертого курса и часов: 
RANGE OF P IS O2 
RANGE OF V IS O3 
(V) WHERE EXISTS P (V.СТУД=P.СТУД  AND  P.КУРС=4) 
Этот же список можно сформировать следующим образом: 
RANGE OF P IS O2 
RANGE OF V IS O3 
RANGE OF VP IS (V) WHERE EXISTS P (V.СТУД=P.СТУД  AND  
P.КУРС=4) 
(VP)  
В реляционном исчислении доменов используются переменные, значе-
ния которых берутся из доменов, а не из кортежей отношений. Исчисле-
ние  доменов  поддерживает  дополнительную  форму  условий,  называе-
 
25

 
мую условием принадлежности. В общем виде условие принадлежности 
записывается в виде R(A
1 
: p
1
, A
2 
: p
2
,…), где A
i
 – атрибут отношения R, а 
p
i
 – переменная домена или литерал. Условие считается истинным тогда 
и  только  тогда,  когда  в  отношении  R  имеется  кортеж  со  значениями  p
i
 
для  атрибутов A
i
. 
Для приведенных выше в примере первого списка выражения исчис-
ления доменов будут иметь вид 
(S) WHERE О1 (КАФ : ‘К1’) 
Здесь  S – переменная  домена  атрибута  ПР,  объявленная  каким-либо 
образом, подобно оператору RANGE исчисления кортежей. 
В заключение заметим, что если реляционное исчисление  ограничи-
вается  только  безопасными  (т.  е.  имеющими  смысл)  выражениями,  то 
реляционное  исчисление  доменов  эквивалентно  реляционному  исчисле-
нию кортежей, а оно в свою очередь – реляционной алгебре.  

жүктеу/скачать 2,58 Mb.

Достарыңызбен бөлісу: