# Реляционная алгебра

В ней определяются основные операции над данными реляционного типа. Все операции можно разделить на традиционные над множествами и специализированные, вводимые для удобства поиска в БД. К операциям 1-й группы относятся: объединения, пересечения, разность, декартово произведение. К операциям 2 -й группы относятся: проекция, ограничение, соединение, деление.

Объединение. В результате применения этой операции получается отношение. объединяющее кортежи, содержащиеся в исходных отношениях. Пусть имеем два исходных отношения R1 и R2 . Операция объединения этих отношений обозначается R1 ∪ R2: R1 ∪ R2 = { r / r ∈ R1 или r ∈ R2 }. Объединяемые отношения должны иметь одинаковые атрибуты ( должны быть объединимы ):

Пересечение. В данной операции ( обозначенной ∩ ) получают отношение, включающее кортежи, общие для R1 и R2: R1 ∩ R2 = { r / r ∈ R1 и r ∈ R2 }.

Разность: В результате применения этой операции (R1 \ R2 ) получается отношение, содержащее кортежи, являющиеся кортежами отношения R1 и не являющиеся кортежами отно-шения R2: R1 \ R2 = { r / r ∈ R1 и r R2 }.

Декартово ( прямое ) произведение. В этой операции ( R1 × R2 ) из m - местного отношения R1 и n - местного отношения R2 получают ( m + n ) - местное отношение. Причём первые m элементов представляют кортежи из отношения R1 , последние n элементов - кортежи из отношения R2: R1 × R2 = {< r1, r2 > / r R1 и r R2 }.

Проекция: Операция проекции предназначена для изменения числа столбцов в отношении, то есть в том случае, когда из строк - кортежей требуется исключить какие-либо атрибуты. Обозначим через j1, j2,..., jn - номера столбцов n - местного отношения R. Операцию определе-ния проекции отношения R обозначим через Πj1, j2,..., jn ( R ), а сама операция заключается в том, что из отношения R выбираются столбцы и компонуются в указанном порядке j1, j2,..., jn.

Ограничение. Ограничением называют такую операцию, в которой отношение исследуют по строкам и выделяют множество строк, удовлетворяющим заданным условиям. Обозначим через r строку (кортеж) отношения R, а через θ определим одно из отношений: =, ≠, <, ≤, >, ≥. Тогда θ - ограничение между выбранным атрибутом А в отношении R и некоторой величиной C определяют следующим образом: R[A θ C] = { r / r R и r [A] θ C }, где r [A] соответствует значению атрибута А в строке r. То есть θ - ограничение обеспечивает получение среди строк отношения R только тех строк, в которых значение атрибута А и значение величины С удовлетворяет условиям сравне-ния θ.

Пример: |

Так- как операция θ - ограничения предусматривает выбор среди строк отно-шения R только тех, в которых значение атрибутов А и В удовлетворяло условию сравнения θ, то для условий (В < С) и (A = D) получим следующие отношения:

Соединение. Операция соединения обратна операции проекции. Рассмотрим два отношения R1 (А, В) и R2 (В, С). Соединением отношений R1 и R2 (R1 ∞ R2 ) называют операцию, при которой соединяют два отношения, используя в качестве признака общий атрибут В: R1 ∞ R2 = { <A,B,C> / <A,B> ∈ R1 и <B,C> ∈ R2 }. Отношение R1 ∞ R2 является отношением с атрибутами <A,B,C>.

Деление. Рассмотрим деление m - местного отношения R1 на n - местное отношение R2. Пусть из общего количества m атрибутов отношения R1 выделим несколько атрибутов: A,B,...,F и из них составляем список, обозначив его через M. Набор значений атрибутов из М столбцов можно рассмотреть как проекцию отношения R на список атрибутов М, то есть (R1). Тогда через будут обозначаться атрибуты дополнительные к М, то есть атрибуты отношения R1, не вошедшие в список М, и соответственно значения атрибутов из списка М опреде-ляются (R1). Операцию деления можно определить так: R1 [M ÷ N] R2 = (R1) \ (((R1) × (R2)) \ R1 }, где - это проекция отношения на атрибуты списка М. Включим в список матрицы М атрибуты C и D (из отношения R1), тогда в список М войдут атрибуты A и B, а в список N - атрибуты C и D из отношения R2: R1[ (С,D) ÷ (С,D)] R2 При построении языка манипулирования данными на основе реляционной алгебры каждый оператор языка реализует некоторый набор алгебраических операций, в результате выполнения которых получается желаемое выходное отношение. Другой подход к построению языка манипулирования данными основан на использо-вании моделей реляционного исчисления. Суть этого подхода заключается в том, что желаемый результат определяется не зада-нием набора операций над отношениями, а путём описания требований, которым должно удовлетворять результирующее отношение. СУБД представляется самой подобрать последова-тельность операций, ведущих к поставленной цели. Языки, основанные на использовании моделей реляционного исчисления, представляют собой языки очень высокого уровня. В реляционном исчислении, так же как и в реляционной алгебре, имеется набор по-нятий и операций, которые позволяют записывать любое отношение в виде некоторой фор-мулы или формального выражения. Формулы в РИ помимо арифметических операций (=, ≠, <, ≤, >, ≥) включают дополнительные логические операции. К ним относят операции квантификации: ∀ - квантор общности, ∃ - квантор существования. Например, ∀x читается "для всех x". ∃y читается "существует y такой, что". Используются также логические операции ∨,∧, ; ∨- логическое сложение (дизьюнкция) - "или", ∧ - логическое умножение (коньюнкция) - "и", - операция отрицания - "не". R1 ∧ R2 - отношение R1 и отноение R2, R1 ∨ R2 - отношение R1 ИЛИ отношение R2. При записи выражений в РИ исользуется понятие свободных или связных пере-менных.Вхождение переменных x в формулу РИ ψ(x) связано, если в ψ она находится в части формулы, начинающейся квантором ∀ или ∃, за которым непосредственно следует переменная x. В таких случаях говорят, что квантор связывает переменную x. В остальных случаях вхождение переменной x в формулу ψ свободно. Например, в формуле ∀x ( R1 (x, y) ∨ ( ∃y) R2 (x, y, z)) переменная x связана, переменная y в отношении R1 свободна, а в R2 - связана, переменная z - свободна. Формулы в РИ строятся из атомов и совокупности арифметических и логических опе-раторов. Атомы в РИ представляются по-разному, в зависимости от того, что используется в качестве переменной кортеж (строка) или атрибут (столбец). Выражение РИ с переменными-кортежами может иметь следующий вид:{r / ψ (r)}, где r - кортеж; ψ- некоторая формула исчисления. Например, выражение {r / R1 (r) ∧ R2 (r)}, где в качестве формулы ψ (r) используется выражение {R1 (r) ∧ R2 (r)}, означает, что необходимо получить множество всех кортежей r таких, что они принадлежат одновременно как отношению R1, так и отношению R2. Выражение РИ с переменными на доменах (т. е. в качестве переменной используется атрибут) имеет вид {x1, x2, ... , xn / ψ (x1, x2, ... , xn)} где ψ - формула, обладающая тем свойством, что только её свободные переменные на доменах являются различными переменными x1, x2, ... , xn.