Специальные операции реляционной алгебры

Горизонтальный выбор, или операция фильтрации. Для определения этой операции нам необходимо ввести дополнительные обозначения.

Пусть а — булевское выражение, составленное из термов сравнения с помощью связок И (∧), ИЛИ (∨), НЕ (¬) и, возможно, скобок. В качестве термов сравнения допускаются:

• А ос а, где А — имя некоторого атрибута, принимающего значения из домена D; a — константа, взятая из того же домена D, a ∈ D; oc — одна из допустимых для данного домена D операций сравнения;

• А ос В, где А, В — имена некоторых θ-сравнимых атрибутов, то есть атрибутов, принимающих значения из одного и то же домена D.

Результатом операции выбора, или фильтрации, заданной на отношении R в виде булевского выражения, определенного на атрибутах отношения R, называется отношение R[α], включающее те кортежи из исходного отношения, для которых истинно условие выбора или фильтрации: R[α(r)] = {r | r ∈ R ∧ α(r) = true}.

Операция фильтрации является одной из основных при работе с реляционной моделью данных. Условие а может быть сколь угодно сложным.

Вертикальный выбор или операция проецирования. Пусть R — отношение, S_R = (A₁, ... , A_n) — схема отношения R. Обозначим через B подмножество атрибутов [ A_i ]; B ⊆ { A_i }.

Проекцией отношения R на набор атрибутов B, обозначаемой R[B], называется отношение со схемой, соответствующей набору атрибутов B S_R[B] = B, содержащему кортежи, получаемые из кортежей исходного отношения R путем удаления из них значений, не принадлежащих атрибутам из набора В. R[B] = { r[B] }. По определению отношений все дублирующие кортежи удаляются из результирующего отношения.

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

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

Пусть R = { r }, Q = { q } - исходные отношения, S_R, S_Q - схемы отношений R и Q соответственно. S_R = (A₁, A₂, ... , A_k); S_Q = (B₁, B₂, ... , B_m), где A_i, B_j — имена атрибутов в схемах отношений R и Q соответственно. Полагаем, что заданы наборы атрибутов А и В: А ⊆ {A_i}, i=1,k;B ⊆ {B_j}, j=1,m, и эти наборы состоят из θ-сравнимых атрибутов.

Тогда соединением отношений R и Q при условии β будет подмножество декартова произведения отношений R и Q, кортежи которого удовлетворяют условию β, рассматриваемому как выполнение условия: r.A_i θ_i q.B_i, i=1-k, где k — число атрибутов, входящих в наборы А и В, а θ_i — конкретная операция сравнения. Условие должно принимать значение «истина» для всех сравнений.

R [β] Q = { (r, q) ∧ r.A_i θ_i q.B_i = true, i=1,k}

Операция деления. Для определения операции деления рассмотрим сначала понятие множества образов. Пусть R — отношение со схемой S_R = (A₁, A₂ ,…, A_k). Пусть A — некоторый набор атрибутов А ⊆ { A_i} i=1,k , A¹ — набор атрибутов, не входящих в множество A.

Пересечение множеств A и A¹ пусто: A ∩ A¹ = ∅; объединение множеств равно множеству всех атрибутов исходного отношения: A ∪ A¹ = S_R.

Тогда множеством образов элемента у проекции R[A] называется множество таких элементов y проекции R[A] , для которых сцепление (x, y) является кортежами отношения R, то есть QA(x) = {y | y ∈ R[A ] ∧ (x, y) ∈ R} - множество образов.

Дадим теперь определение операции деления. Пусть даны два отношения R и T соответственно со схемами: S_R = (A₁, A₂, ... , A_k); S_T = (B₁, B₂, ... , B_m); A и B - наборы атрибутов этих отношений, одинаковой длины (без повторений); A ⊆ S_R ; B ⊆ S_T. Атрибуты A¹ — это атрибуты из R, не вошедшие в множество A.

Пересечение множеств A ∩∩ A¹ = ∅ — пусто и A ∪ A¹ = S_R. Проекции R[A] и T[B] совместимы по объединению, то есть имеют эквивалентные схемы: S_R[A] ~ S_T[B] .

Тогда операция деления ставит в соответствие отношениям R и T отношение Q = R[A:B]T, кортежи которого являются теми элементами проекции R[A¹], для которых T[B] входит в построенные для них множество образов: R[A:B]T = {r | r ∈ R[A¹] ∧ T[B] ⊆ {y | y ∈ R [A] ∧ (r, y) ∈ R } }.

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

R₁ = <ФИО, Дисциплина, Оценка>; R₂ = <ФИО, Группа>; R₃ = < Группы, Дисциплина>,

где R₁ — информация о попытках (как успешных, так и неуспешных) сдачи экзаменов студентами; R₂ — состав групп; R₃ — список дисциплин, которые надо сдавать каждой группе. Будем считать, что доменом для атрибута Дисциплина будет множество всех дисциплин, преподающихся в ВУЗе, доменом для атрибута Группа будет множество всех групп ВУЗа и т. д.

В каждом из приведенных примеров путем операций над исходными отношениями R₁, R₂, R₃ формируются промежуточные отношения и результирующее отношение S:

• Список студентов, которые сдали экзамен по БД на "отлично". Результат может быть получен применением операции фильтрации по сложному условию к отношению R₁ и последующим проектированием на атрибут «ФИО».

S = (R₁[Оценка = 5 ∧ Дисциплина = "БД"])[ФИО];

• Список тех, кто должен был сдавать экзамен по БД, но пока еще не сдавал. Сначала найдем всех, кто должен был сдавать экзамен по БД. В отношении R₃ находится список всех дисциплин, по которым каждая группа должна была сдавать экзамены, ограничим перечень дисциплин только "БД". Для того чтобы получить список студентов, нам надо соединить отношение R₃ и R₂, в котором определен список студентов каждой группы.

R₄ = (R₂[R₃.НомерГруппы = R₂.НомерГруппы ∧ R₃.Дисциплина = "БД"] R₃)[ФИО];

• Теперь получим список всех, кто сдавал экзамен по "БД" (нас пока не интересует результат сдачи, а интересует сам факт попытки сдачи, то есть присутствие в отношении R₁):

R₅ = (R₁ [Дисциплина = "БД"])[ФИО];

и, наконец, результат — все, кто есть в первом множестве, но не во втором: S=R₄ \ R₅;

• Список имеющих несколько двоек:

S = (R₁[R₁.ФИО = R'₁.ФИО ∧ R₁.Дисциплина ≠ R'₁.Дисциплина ∧ R₁.Оценка <= 2 ∧ R'₁.Оценка <= 2] R'₁)[ФИО]

Этот пример весьма интересен: для поиска строк, удовлетворяющих в совокупности условию больше одного, применяется операция соединения отношения с самим собой. Поэтому мы как бы взяли копию отношения R₁ и назвали ее R'₁.

• Список круглых отличников. Строим список всех пар <студент—дисциплина>, которые в принципе должны быть сданы:

R₄ = (R₂[R₂ Группа = R₃.Группа] R₃)[ФИО, Дисциплина];

Строим список пар <студент—дисциплина>, где получена оценка "отлично":

R₅ = (R₁[Оценка = 5])[ФИО, Дисциплина];

Строим список студентов, что-либо не сдавших на "отлично":

R₆ = (R₄ \ R5)[ФИО].

Исключив последнее отношение из общего списка студентов, получаем результат:

S = R₂[ФИО] \ R₆

Обратите внимание, что для получения множества студентов, что-либо не сдавших на "отлично" (R₆), мы осуществили "инверсию" множества всех отлично сданных пар <студент—дисциплина> (R₅) путем вычитания его из предварительного построенного универсального множества (R₄).