Мегаобучалка Главная | О нас | Обратная связь

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





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

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

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

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

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

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

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

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

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



Пусть R = { r }, Q = { q } - исходные отношения, SR, SQ - схемы отношений R и Q соответственно.
SR = (A1, A2, ... , Ak); SQ = (B1, B2, ... , Bm), где Ai, Bj — имена атрибутов в схемах отношений R и Q соответственно. Полагаем, что заданы наборы атрибутов А и В: А ⊆ {Ai}, i=1,k;B ⊆ {Bj}, j=1,m, и эти наборы состоят из θ-сравнимых атрибутов.

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

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

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

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

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

Дадим теперь определение операции деления. Пусть даны два отношения Rи T соответственно со схемами: SR = (A1, A2, ... , Ak); ST = (B1, B2, ... , Bm); A и B - наборы атрибутов этих отношений, одинаковой длины (без повторений); A ⊆ SR ; B ⊆ ST. Атрибуты A1 — это атрибуты из R, не вошедшие в множество A.

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

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

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

R1 = <ФИО, Дисциплина, Оценка>; R2 = <ФИО, Группа>; R3 = < Группы, Дисциплина>,

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

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

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

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

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

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

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

R5 = (R1 [Дисциплина = "БД"])[ФИО];

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

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

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

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

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

R4 = (R2[R2 Группа = R3.Группа] R3)[ФИО, Дисциплина];

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

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

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

R6 = (R4 \ R5)[ФИО].

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

S = R2[ФИО] \ R6

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





Читайте также:


Рекомендуемые страницы:


Читайте также:

©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (875)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.006 сек.)