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

Теорема. [ Дж. Ульман Основы систем баз данных. «Финансы и статистика», 1983. ] Если E – выражение реляционной алгебры, то существует эквивалентное ему безопасное выражение в реляционном исчислении с переменными – кортежами.

В данном случае E эквивалентно выражению {t ï R (t)}.

Выражение {t ï y (t)} называют безопасным, если выполняются следующие условия:

1. Всякий раз, когда t удовлетворяет y, каждый компонент t является элементом dom(y).

2. Для любого подвыражения y вида ( $ u) ( w (u)) каждый компонент u принадлежит dom( w ), если u удовлетворяет w.

3. Если для любого подвыражения y вида ( " u) ( w (u)) каждый компонент u не принадлежит dom( w ), то u удовлетворяет w.

Условия 2 и 3 позволяют установить истинность квантифицированной формулы ( $ u) ( w (u)) и ( " u) ( w (u)), рассматривая только u, составленные из принадлежащих dom( w ) значениям. Например, любая формула ( $ u) (R(u) Ú …) удовлетворяет условию 2, а любая формула ( " u) (ØR(u) Ú …) удовлетворяет условию 3. Фактически это подтверждает тождества 1-4.

Безопасность выражений

Выражение реляционного исчисления может генерировать бесконечную последовательность кортежей. Например, таким является выражение, которое обозначает все кортежи, не принадлежащие к отношению R:

{t ½Ø R(t)}

Выражения такого рода называют опасными. Для того чтобы избежать возникновения этой проблемы, необходимо ввести ограничение, согласно которому все значения, присутствующие в полученных результатах, должны принадлежать к области определения исходного выражения A_i; для этого используется обозначение dom(A_i). Областью определения выражения A_i являются все значения, явно присутствующие в A_i.

Выражение является безопасным, если все значения, присутствующие в полученных результатах, принадлежат к области определения самого выражения. Приведенное выше выражение является опасным, поскольку в нем предусмотрено получение кортежей, не принадлежащих к отношению R (т.е. кортежей, находящихся за пределами области определения отношения). Все другие примеры выражений реляционного исчисления кортежей, приведенные в лекции, являются безопасными.

Выразим некоторые операции реляционной алгебры через формулы реляционного исчисления кортежей.

1). Объединение отношений R и S выражается следующим образом:

{t ï R(t) Ú S(t)}

или

{t ï ( $ u) ( R (u)) Ú ($ v) (S(v)) Ù (t [1] = u [1] Ú t [1] = v [1]) }

Например:

R(u)		S(v)		R È S(t)
a		d		a
b		c		b
c				c
				d

Это означает: «множество кортежей t, таких, что t принадлежит R или t принадлежит S». Отметим, что объединение имеет смысл, только если R и S обладают одной и той же арностью.

2). Разность R – S может быть представлена следующим выражением:

{t ï R(t) Ù Ø S(t)}

или

{t ï ( $ u) (R(u) Ù ( " v) (S(v) Ù (t [1] =u [1] Ù u [1] ≠ v [1] )))}

3). Если R и S — отношения арности соответственно r и p, то декартовое произведение R ´ S в исчислении можно записать в виде:

{t^(r+p) ï ( $ u^(r)) ( $ v^(p)) (R(u) Ù S(v) Ù t [1]= u [1] Ù t [ 2 ]= u [ 2 ] Ù … Ù t [ r ]=

= u [ r ] Ù t [ r+ 1]= v [1] Ù t [ r+2 ]= v [ 2 ] Ù... Ù t [ r+p ]= v [ p ] )}

Здесь, tⁱ указывает, что t имеет арность i. Приведенное выражение означает, что R ´ S есть множество кортежей t (рассматриваемых как кортежи длины r+p), таких, что существует кортеж и, принадлежащий отношению R, и кортеж v, принадлежащий отношению S, причем r первых компонентов t образуют и, а следующие p компонентов – v.

4). Проекция p _{i1, i2, …, ik}(R) выражается следующим образом:

{t^(k) ï ( $ u) (R(u) Ù t [1]= u [ i₁ ] Ù … Ù t [ k ]= u [ i_k ] )}

5). Селекция s_F (R) может быть выражена в виде:

{t ï R(t) Ù F ¢ }

или

{t ï ( $ u) ( R (u) Ù F ¢ )}

где формула F ¢ есть F, в которой каждый операнд i, обозначающий i -й компонент, заменяется на t [ i ].

То есть если s_{A1=a1 AND A2=a2 AND Ak=ak}(R), то

{t ï R(t) Ù (t [ A₁ ]= a₁ Ù … Ù t [ A_k ]= a_k)}

В качестве самостоятельного примера можно представить отношение R арности 2, которое отображает экземпляр R, когда оно имеет два или более кортежа, и пустое отношение, когда R пусто или имеет только один кортеж, формулой исчисления следующим образом:

{t⁽²⁾ ï ( $ u) (R(t) Ù R(u) Ù (t [ 1 ] ¹ u [ 1 ] Ú t [ 2 ] ¹ u [ 2 ] ))}

Второй пример: пусть в терминах реляционной алгебры запрос выглядит как

p_1,4 (s₂₌₃ (R´S)),

тогда это выражение можно записать в виде безопасного выражения в реляционном исчислении:

1. первый шаг: выразим декартово произведение R´S:

{t ï ( $ u) ( $ v) (R(u) Ù S(v) Ù t [1] = u [1] Ù t [2] = u [2] Ù t [3] = v [1] Ù t [4] = v [2] )}

2. второй шаг: для s₂₌₃ (R´S) добавим к этой формуле терм

Ù t [2] = t [3]

3. третий шаг: определим для проекции новые компоненты w и получим общий вид запроса:

{w ï ( $ t) ( $ u) ( $ v) (R(u) Ù S(v) Ù t [1] = u [1] Ù t [2] = u [2] Ù t [3] = v [1] Ù t [4] = v [2] ) Ù t [2] = t [3] Ù w [1] = t [1] Ù w [2] = t [4] }

это выражение можно записать короче, если не использовать t, а выразить все через u и w:

{w ï ( $ u) ( $ v) (R(u) Ù S(v) Ù u [2] = v [1] Ù w [1] = v [1] Ù w [2] = v [2] }

Примеры.

Список		Экзамен
Группа	ФИО	№зк		№зк	Предмет	Оценка

1. Создать список предметов, которые сдавали студенты.

{(t[Предмет] ï ($t) (Экзамен (t))}

SELECT Предмет

FROM Экзамен

2. Создать список оценок по предмету БД и Математика.

{t[Предмет, Оценка] ï ($t) (Экзамен (t)) Ù (t[Предмет] = ‘БД’ Ú t[Предмет] = ‘Математика’)}

SELECT Предмет, Оценка

FROM Экзамен

WHERE Предмет = ‘БД’ OR Предмет = ‘Математика’

3. Создать список студентов, которые сдали экзамен по БД.

Этот запрос можно сформулировать по-другому: Для всех студентов, данные о которых нужно привести в списке, в отношении ‘Экзамен’ существуют кортежи, соответствующие этим студентам кортежи, причем значение атрибута ‘Предмет’ в каждом таком кортежи равно ‘БД’.

Эквивалентная формулировка данного запроса в реляционной алгебре будет выглядеть так: Выбрать такие кортежи отношения ‘Список’, в которых значение атрибута ‘Предмет’ равно ‘БД’, и выполнить их соединение с отношением ‘Экзамен’.

{t[Предмет] ï ($t) (Список(t)) Ù ($s) (Экзамен(s)) Ù (t[№зк] = s[№зк]) Ù (s[Предмет] = ‘БД’)}

В соответствии с исчислением

a) SELECT Предмет

FROM Список AS a

Дата добавления: 2014-01-11