Реляционная алгебра как манипуляционная часть реляционной модели данных: общая характеристика, основные элементы, теоретико-множественные и специальные операции.

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

· алгебраические языки (реляционная алгебра), позволяющие выражать запросы с помощью специальных операторов, применяемых к отношениям;

· языки исчисления предикатов (реляционное исчисление), в которых запросы описывают требуемое множество кортежей путем спецификации предиката, которому должны удовлетворять эти кортежи.

Из приведенного определения следует:

· языки реляционной алгебры показывают, как получить результат;

· языки реляционного исчисления показывают, что должно быть получено.

 

Языки реляционного исчисления делятся на два класса: с переменными–кортежами и с переменными на доменах – в зависимости от того, что является примитивными объектами исчисления: кортежи или элементы доменов, являющиеся значениями некоторых атрибутов.

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

 

Все операции над отношениями можно разбить на две группы:

– Теоретико-множественные операции – традиционные операции над множествами, определяемые теорией множеств; к ним относятся: 1)объединение, 2)вычитание, 3)пересечение, 4)прямое (декартово) произведение

– Специальные реляционные операции; к ним относятся: 1)выбор (селекция), 2)проекция, 3)соединение, 4)деление, 5)переименование.

 

Результирующее отношение будет иметь, наряду с реализацией, и схему отношения.Схема отношения – это поименованная совокупность имен атрибутов.Обязательным условием для определения схемы отношения является уникальность имен атрибутов в схеме. Для того чтобы результирующее отношение имело правильную схему, содержащую правильные (уникальные в данной схеме) имена атрибутов, может быть востребована специальная операция переименования, позволяющая переименовать атрибут в некоторой схеме отношения.

 

Простые домены считаются совместимыми по объединению, если они состоят из элементов одного типа. Два отношения считаются совместимыми по объединению, если

· оба отношения имеют одно и то же множество атрибутов,

· одноименные атрибуты двух отношений определены на совместимых по объединению доменах.

 

Объединением двух отношений r1(R1) и r2(R2), совместимых по объединению, называется отношение s = r1 È r2, для которого

1) схема отношения совпадает с R1 или R2,

2) реализация отношения представляет множество кортежей, принадлежащих реализации r1 и/или r2.

Формальная запись: Даны r1(R1), r2(R2), r1 = {t1_i}, r2 = {t2_i}, R1 º R, R2 º R.

s = r1 È r2 = s(R), s = {t_i | t_i Î r1 и/или t_i Î r2}

Свойства операции:

· коммутативна – r1 È r2 º r2 È r1

· ассоциативна – r1 È (r2 È r3) = (r1 È r2) È r3 = r1 È r2 È r3

 

Вычитанием двух отношений r1(R1) и r2(R2), совместимых по объединению, называется отношение s = r1 – r2, для которого

1) схема отношения совпадает с R1 или R2,

2) реализация отношения представляет множество кортежей, принадлежащих реализации r1, за исключением тех, которые имеются в r2.

Формальная запись: Даны r1(R1), r2(R2), r1 = {t1_i}, r2 = {t2_i}, R1 º R, R2 º R.

s = r1 – r2 = s(R), s = {t_i | t_i Î r1 и t_i Ï r2}

Свойства операции: не коммутативна и не ассоциативна.

 

Пересечением двух отношений r1(R1) и r2(R2), совместимых по объединению, называется отношение s = r1 Ç r2, для которого

1) схема отношения совпадает с R1 или R2,

2) реализация отношения представляет множество кортежей, содержащихся и в r1, и в r2.

Формальная запись: Даны r1(R1), r2(R2), r1 = {t1_i}, r2 = {t2_i}, R1 º R, R2 º R.

s = r1 Ç r2 = s(R), s = { t_i | t_i Î r1 и t_i Î r2}

Свойства операции:

· коммутативна – r1 Ç r2 º r2 Ç r1

· ассоциативна – r1 Ç (r2 Ç r3) = (r1 Ç r2) Ç r3 = r1 Ç r2 Ç r3

Операцию пересечения можно выразить через операцию вычитания: r1 Ç r2 = r1 – (r1 – r2)

 

Декартовым произведением двух отношений r1(R1) и r2(R2), у которых R1 Ç R2 = 0, называется отношение s = r1 ´ r2, для которого

1) схема отношения определяется сцеплением (объединением) схем R1 и R2,

2) реализация отношения представляет множество кортежей, которое получается путем сцепления каждого кортежа из r1 с каждым кортежем из r2.

Здесь отношения r1(R1) и r2(R2) могут иметь разные схемы, не обязательно совместимые по объединению. Перед выполнением операции декартова произведения необходимо переименовать схемы отношений R1 или R2 так, чтобы они не имели одноименных атрибутов.

Формальная запись:

Даны r₁(R₁), R₁(A₁, A₂, …, A_m), r₂(R₂), R₂(B₁, B₂, …, B_n), r₁ = {t_1i}, r₂ = {t_2i}, R₁ Ç R₂ = 0

s = r₁ ´ r₂ = s(R), R(A₁, A₂, …, A_m, B₁, B₂, …, B_n), s = {u_i v_j | u_i Î r₁, v_j Î r₂}

Свойства операции:

· коммутативна – r1 ´ r2 º r2 ´ r1

· ассоциативна – r1 ´ (r2 ´ r3) = (r1 ´ r2) ´ r3 = r1 ´ r2 ´ r3

 

Специальные операции определены только для нормализованных отношений. В этих операциях наряду с самими отношениями участвуют и их атрибуты. В отношениях РМД к атрибутам можно обращаться или по имени, или по их позиции в схеме отношения. Мы будем использовать обращение к атрибутам по имени.

Операция проекции является унарной операцией на отношениях, т.е. в этой операции участвует только одно отношение.

Проекцией отношения r(R), R = {Ai}, на некоторый список имен атрибутов (подмножество атрибутов) L из R, L Í R, называется отношение s = pL(r), для которого:

1) схема отношения определяется списком L,

2) реализация отношения есть множество кортежей, полученных из кортежей отношения r вычеркиванием элементов, соответствующих атрибутам R – L и исключением дубликатов.

Формальная запись: Дано r(R), R(A1, A2, …, Am), r = {<t1: A1, t2: A2…, tm: Am >}

s(L) = pL(r), L Í R, L(B1, B2, …, Bk), Bi Í R, s = {<u1: B1, u2: B2, …, uk: Bk> | таких, что ui = tj, если Bi º Aj}

Проекция дает вертикальное подмножество отношения. Свойство проекции:

Если Y Í X Í R, то pY(pX(r)) º pY(r)

 

Операцию выбора называют еще ограничением и селекцией. Также унарная операция.

Выбором из отношения r(R) по условию F называется отношение s = sF(r), для которого:

1) схема отношения совпадает со схемой R,

2) реализация отношения есть множество кортежей из r, удовлетворяющих условию F.

Формальная запись: Дано r(R), r = {ti}

s(R) = sF(r), s = {u_i | u_i Î R и F(u_i) – истинно}

Условие (предикат) F записывается в соответствии со следующими правилами:

· в качестве операндов могут быть указаны атрибуты отношения и/или константы;

· в качестве операций могут быть использованы операции отношения (=, ¹ и т.д.) и логические операции (Ù, Ú, Ø).

Для указания порядка вычисления предиката F в нем могут быть использованы круглые скобки. Выбор дает горизонтальное подмножество отношения. Свойства операции:

· коммутативна – sF1(sF2(r)) = sF2(sF1(r)) = sF1Ù F2 (r)

· дистрибутивна относительно операций g = (Ù, Ú, –): sF (r g s) = sF (r) g sF (s)

Операция выбора осуществляет ограничение кортежей исходного отношения до значений, удовлетворяющих условию.

 

В реляционной алгебре рассматриваются две модификации операции соединения: естественное соединение и соединение по условию (или q – соединение). Рассмотрим естественное.

Естественным соединением отношений r1(R1), R1 = XY, и r2(R2), R2 = YZ, где Y – общее подмножество атрибутов из R1 и R2, определенных на одних и тех же доменах, называется отношение s(R) = r1 r2, для которого:

1) схема отношения R = R1 È R2 = XYZ,

2) реализация отношения есть множество кортежей {t}, для которых pXY(t)Î r1 и pYZ(t)Î r2.

Формальная запись: Даны r1(R1), R1 = XY, и r2(R2), R2 = YZ.

s(R) = r1 r2, R = R1 È R2 = XYZ, s = {t | таких, что pXY(t) Î r1 и pYZ(t) Î r2}

 

Частным от деления отношения r1(R1) на отношение r2(R2), для которых R2 Í R1 и R2 не пусто, называется отношение s(R) = r1 ¸ r2, для которого:

1) схема отношения R = R1 – R2,

2) реализация отношения есть множество кортежей t таких, что для всех ti Î r2 существует tj Î r1 такой, что tj(R1 – R2) = t и tj(R2) = ti.

Формальная запись: Даны r1(R1), r2(R2), R2 Í R1, R2 ¹ 0.

s(R) = r1 ¸ r2, R = R1 – R2, s = {t_j | " u Î r₂ (t_ju Î r₁)}

Другими словами, s ´ r2 Î r1.

8. Реляционное исчисление с переменными-кортежами: основные определения, понятие атомов, правильно построенная формула.

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

· алгебраические языки (реляционная алгебра), позволяющие выражать запросы с помощью специальных операторов, применяемых к отношениям;

· языки исчисления предикатов (реляционное исчисление), в которых запросы описывают требуемое множество кортежей путем спецификации предиката, которому должны удовлетворять эти кортежи.

Из приведенного определения следует:

· языки реляционной алгебры показывают, как получить результат;

· языки реляционного исчисления показывают, что должно быть получено.

 

Языки реляционного исчисления делятся на два класса: с переменными–кортежами и с переменными на доменах – в зависимости от того, что является примитивными объектами исчисления: кортежи или элементы доменов, являющиеся значениями некоторых атрибутов.

 

Реляционное исчисление лежит в основе декларативного подхода к формулировке запроса к БД, суть которого заключается в следующем: запросу к БД соответствует формула некоторой формально-логической теории, которая описывает свойства желаемого результата.

Ответом на запрос служит множество объектов из области интерпретации (которой является БД), на котором истинна формула, соответствующая запросу.

В качестве такой формально-логической теории используется теория исчисления предикатов первого порядка, в которой формула задается в виде предиката.

 

Даны некоторые попарно не пересекающиеся произвольные множества D1, D2, …, Dn, Di Ç Dj = 0 для любых i ¹ j, и переменные x1, x2, …, xn, принимающие значения из соответствующих множеств: xi Î Di для любых i. Тогда предикатом (или предикатной функцией) называется функция P(x1, x2, …, xn), принимающая одно из двух значений – 1 или 0 (истина или ложь). Переменные x1, x2, …, xn называются предикатными переменными. Множества D1, D2, …, Dn образуют область интерпретации предиката.

 

В записи предиката, наряду с логическими операциями Ù, Ú, Ø, смысл и использование которых традиционны, используются специальные операции – кванторы: всеобщности " и существования $. Смысл использования кванторов следующий: "x (f(x)) означает, что для всех значений x из области интерпретации формула f(x) имеет значение "истина"; $x (f(x)) означает, что существует по крайней мере одно значение x из области интерпретации, для которого формула f(x) имеет значение "истина".

 

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

Переменные-кортежи должны удовлетворять определенной схеме отношения R. Правильно построенная формула (wff – well formulated formula) определяет результаты отбора: выбираются те кортежи, для которых wff дает значение 1.

Обозначим правильно построенную формулу (предикат, значения которого 0 или 1) через y(t). Рассмотрим правила построения y(t).

 

I. Основой формулы являются атомы, которые могут иметь значения 0 или 1.

Существует три типа атомов формулы y(t).

1. Пусть r(R) – некоторая реализация отношения, удовлетворяющая схеме R; t – некоторая переменная-кортеж, удовлетворяющая схеме R. Тогда r(t) – атом; означает, что t есть кортеж в реализации отношении r (т.е. формула истинна, если t Î r).

2. Пусть r(R) – некоторая реализация отношения, удовлетворяющая схеме R; u и v – переменные-кортежи из отношения r(R) (т.е. u Î r, v Î r); q – арифметическая операция сравнения (<, =, >, ³, ¹, £); A, B – атрибуты схемы отношения R, сравнимые по операции q; тогда u[A] q v[B] – атом.

3. Пусть u – переменная-кортеж из отношения r(R) (т.е. u Î r); q – арифметическая операция сравнения (<, =, >, ³, ¹, £); A, B – атрибуты схемы отношения R, сравнимые по операции q; c – константа из домена, на котором определен атрибут B; ®u[A]qc (или cqu[A]) – атом.

Запись u[A] означает «значение переменной-кортежа u по атрибуту A».

 

II. Формула реляционного исчисления y(t), а также свободные и связанные вхождения переменных определяются по следующим рекурсивным правилам:

1. Каждый атом есть формула. Все вхождения переменных-кортежей, упомянутых в атоме, являются свободными. Например, формула r(t) утверждает, что переменная-кортеж t является кортежем отношения r(R).

2. Если x(R) – переменная-кортеж из отношения r со схемой R; y(x) – формула, в которой переменная x имеет свободное вхождение; тогда $x(R) (y(x)). Данная формула утверждает, что существует хотя бы один кортеж x в отношении r(R), такой, что при подстановке его в формулу y(x) вместо всех свободных вхождений x получим значение "истина". Например, формула $x(R) (r(x)) утверждает, что отношение r не пусто (то есть, существует хотя бы один кортеж x, принадлежащий r).

3. Если x(R) – переменная-кортеж из отношения r со схемой R; y(x) – формула, в которой переменная x имеет свободное вхождение; тогда "x(R) (y(x)). Данная формула утверждает, что для всех кортежей x из отношения r(R) при подстановке их в формулу y(x) вместо всех свободных вхождений x получим значение "истина". Например, формула "x(R) (x[A] ¹ Æ) утверждает, что для всех кортежей значение атрибута A является обязательным.

4. Если y(x) и j(x) – формулы, тогда Øy(x), y(x) Ù j(x), y(x) Ú j(x) – тоже формулы. Вхождения переменной x в эти формулы остаются свободными или связанными – такими, какими были в y(x) или j(x) соответственно.

5. Если y(x) – формула, то (y(x)) – тоже формула; вхождение переменной x остается свободным или связанным – таким, каким оно было в y(x).

6. Ничто иное не является формулой.

 

При вычислении формул используется порядок старшинства операций, определяемый правилами построения формулы:

a) атомы, в которых могут быть использованы арифметические операции сравнения;

b) кванторы;

c) отрицание (Ø)

d) операция "И" (Ù)

e) операция "ИЛИ" (Ú)

Скобки используются для изменения порядка вычисления формулы.

Выражение реляционного исчисления с переменными-кортежами имеет вид: {t(R) | y(t)}, где t – переменная-кортеж, удовлетворяющая схеме отношения R; единственная переменная, имеющая свободное вхождение в формулу y(t); y(t) – правильно построенная формула. Интерпретация выражения реляционного исчисления: множество кортежей t, удовлетворяющих схеме отношения R, таких, для которых правильно построенная формула y(t) истинна.

Пример:

Пусть есть отношение R(ИМЯ, СТИПЕНДИЯ); атрибут СТИПЕНДИЯ определен на домене D = {«да», «нет»}. Тогда выражение

{ t(ИМЯ) | $x(R) (r(x) Ù x[СТИПЕНДИЯ] = «да» Ù x[ИМЯ] = t[ИМЯ]}

позволит получить из отношения имена всех студентов, получающих стипендию.

 

Выражение вида {t | Ø r(t) } в общем случае определяет бесконечное отношение, что недопустимо. Поэтому в реляционном исчислении ограничиваются рассмотрением так называемых безопасных выражений вида {t | y(t) }, которые гарантированно дают ограниченное множество кортежей. В таких выражениях значения атрибутов кортежей t являются элементами некоторого ограниченного универсального множества – DOM(y).DOM(y) – унарное отношение, элементами которого являются символы, которые либо явно появляются в y, либо служат компонентами какого-либо кортежа в некотором отношении R, упоминаемом в y.

 

«Выражение {t | y(t)} реляционного исчисления с переменными-кортежами назовем безопасным, если выполняются следующие условия:

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

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

Если для любого подвыражения 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.»

 

Эквивалентность выражений реляционной алгебры и реляционного исчисления с переменными-кортежами (теорема):Если E – выражение реляционной алгебры, то эквивалентное ему безопасное выражение реляционного исчисления с переменными-кортежами.

Выражение реляционной алгебры	Выражение реляционного исчисления с переменными-кортежами
Объединение: r1 È r2, r1(R), r2(R)	{x(R) | r1(x) Ú r2(x) }
Разность: r1 – r2 , r1(R), r2(R)	{x(R) | r1(x) Ù Ør2(x) }
Пересечение: r1 Ç r2, r1(R), r2(R)	{x(R) | r1(x) Ù r2(x) }
Декартово произведение: r1 ´ r2, r1(R1), r2(R2)	{x(R1R2) | $u(R1) $v(R2) (r1(u) Ù r2(v) Ù x[R1] = u{r1] Ù x[R2] = v[R2]) }
Проекция: pL(r), r(R), L Í R	{t(L) | $u(R) (r(u) Ù u[L] = t[L] }
Выбор: sF(r), r(R)	{ t(R) | r(t) Ù F’) }
Естественное соединение: r1 r2, r1(AB), r2(BC)	{ t(ABC) | $u(AB) $v(BC) (r1(u) Ù r2(v) Ù u[B] = v[B] Ù t[AB] = u[AB] Ù t[C] = v[C]) }
Деление: r1 ¸ r2, r1(AB), r2(B)	{ t(A) | "x(B) (r2(x) Ù $y(AB) (r1(y) Ù y[B] = x[B] Ù y[A] = t[A] }