A B C D
A B
C
D
1 2 3 4
1 2 3 4
R
⊃< ⎢S = 1 2 3 5 R⎪>⊂ S =
1 2
3
5
4 2 3 4
4 2 3 4
4 2 3 5
4 2 3 5
3 1 4 2
3 1 4 2
2 2 6 NULL
NULL 3 5 4
A B
C D
1
2
3
4
1
2
3
5
R
⊃⊂ S =
4 2
3 4
22
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 исчисления кортежей.
В заключение заметим, что если реляционное исчисление ограничи-
вается только безопасными (т. е. имеющими смысл) выражениями, то
реляционное исчисление доменов эквивалентно реляционному исчисле-
нию кортежей, а оно в свою очередь – реляционной алгебре.
Достарыңызбен бөлісу: |