Основы реляционной алгебры

 

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

1. C = A U B- объединение (UNION). Результат образуют кортежи, входящие в A или B без дублирования. Отношения A и B должны иметь одинаковое количество атрибутов и соответствие их типов, то есть атрибуты с одинаковыми порядковыми номерами в отношениях A и B должны быть совместимы по типам данных. Например, таблицы A и B могут представлять собой данные о студентах, получивших зачет по двум разным предметам. Тогда в объединении таблиц будут представлены студенты, получившие хотя бы один зачет.

2. C = A - B- разность (MINUS). Результат образуют кортежи, входящие как в A, но не входящие в B. Операция корректна при тех же требованиях к отношениям A и B, что и предыдущая операция. Для предыдущего примера в C окажутся только те студенты, которые получили зачет по первому, но не по второму предмету.

3. C = A ∩ B- пересечение (INTERSECT). Результат образуют кортежи, входящие как в A, так и в B. Требования к операндам такие же, как и ранее. Пересечение выражается через разность: A ∩ B = A - (A –B). Для того же примера в C попадут обладатели зачетов по обоим предметам.

4. C = A ´ B– декартово произведение (TIMES). Результат образуют все упорядоченные кортежи, образованные сцеплением (конкатенацией) кортежей из отношений A и B. Число атрибутов декартова произведения равно сумме числа атрибутов A и B, а число кортежей определяется как произведение числа кортежей A и B. Эта операция трудоемка и требует больших затрат памяти, поэтому служит в большей степени для теоретических, а не практических целей. Например, если в таблице A (Stud, Gr) представлены студенты разных групп потока, а в B (Prep, Kaf) преподаватели разных кафедр, которые могут принимать экзамены сессии, то в C (Stud, Gr, Prep, Kaf) окажутся все возможные пары студент-преподаватель.

5. C = σF (A) - селекция или выборка (SELECT). Результатом является множество кортежей, для которых логическое выражение или условие F устанавливается в истину. Это первая рассматриваемая операция, присущая именно реляционной алгебре, а не теории множеств. Логическое выражение строится на основе атрибутов отношения A. Например, операция селекции для таблицы A из предыдущего примера по условию Gr=’ПС-12’ определит таблицу C (Stud, Gr), в которой останутся только студенты группы ПС-12.

6. C = πS (A) - проекция (PROJECT). Здесь список S является подмножеством атрибутов A и задает атрибуты результата операции. Кортежами результата являются “урезанные” кортежи отношения A с исключением дублирования одинаковых кортежей. Пусть, например, в таблице А (Stud, Gr, St) поле St определяет старосту группы. Проекция A по атрибутам Gr, St даст перечень групп с их старостами. Число записей в результате окажется меньше, чем в A, поскольку в каждой группе может быть много студентов, а информация о группе появится в единственной записи.

7. C = AB - соединение (JOIN). Операция соединения имеет несколько видов. Наиболее общий из них представляет θ-соединение. Результат образуют все упорядоченные кортежи, образованные сцеплением (конкатенацией) тех кортежей из отношений A и B, для которых выполняется условие Ai θ Bj, где Ai и Bj – значения i-го и j-го атрибутов A и B, а θ – одна из операций сравнения (‘=’, ‘<’, ‘>’, ‘≠’, ‘≤’, ‘≥’). Таким образом, θ-соединение представляет собой декартово произведение с условием. В подавляющем большинстве случаев θ задает операцию равенства, и такое соединение называется эквисоединением. Если атрибуты Ai и Bj имеют одинаковое наименование, то оно появится в результате дважды, и во всех кортежах будут повторяться одинаковые значения. Это, конечно, неудобно, поэтому чаще используют естественное соединение, в котором все одноименные атрибуты отношений A и B встречаются один раз. Легко заметить, что естественное соединение теоретически сводится к последовательности таких операций, как декартово произведение, селекция и проекция. Однако практически оно реализуется гораздо эффективнее.

Пусть, например, таблица A (Stud, Gr) содержит данные о студентах факультета X, а B (Stud, Room) – данные о студентах разных факультетов, проживающих в общежитии Y. Операция естественного соединения C = AB определит таблицу C (Stud, Gr, Room), в которой окажутся данные о студентах факультета X, проживающих в общежитии Y.

В переводной литературе соединение часто неправильно называют объединением. Нужно четко понимать разницу между этими операциями.

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

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

Представленный набор операций фигурировал в ранних статьях Э.Кодда. Многие авторы предлагали и другие операции, ориентированные для удобства использования и связи исходных операций. Обоснование и подробное обсуждение различных вариантов дополнительных операций имеет в большей степени теоретический интерес. Приведем в качестве примера несколько таких операций [2].

1. Переименование (RENAME). Операция позволяет присвоить другое имя атрибуту отношения.

2. Полусоединение(SEMIJOIN). Операция определяется выражением

C=π<A> (AB), где <A> - список атрибутов отношения A. Иными словами, выделяются кортежи A, нашедшие соответствие в отношении B.

3. Полувычитание(SEMIMINUS). Операция определяется выражением

C=A -π<A> (AB), где <A> - список атрибутов отношения A. В противоположность полусоединению находятся те кортежи отношения A, которые не нашли соответствия в отношении B.

4. Расширение(EXTEND). Операция позволяет добавить новое поле в отношение, определяя его значение выражением над другими полями.

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

Операции реляционной алгебры могут использоваться последовательно. Рассмотрим снова отношения по поставщикам S (S# , Sn, Scity), изделиям P (P#, Pn, Pcity, W) и поставкам SP (S#, P#, Q). Здесь S# - номер поставщика, Sn – его имя, Scity – место проживания, P# - номер изделия, Pn – его наименование, Pcity – место хранения, W – вес, Q – объем поставки. Требуется найти имена и места проживания поставщиков, поставляющих детали веса более 10.

Можно получить результат следующими операциями:

A = σ W>10 (P)

B = ASP

C = BS

R = π Sn, Scity (C)

Здесь оба соединения – естественные, то есть первое производится по атрибуту P#, а второе по атрибуту S#. Мы получили пример “программы” в виде последовательности операций реляционной алгебры.

На основе операций реляционной алгебры были предложены и реализованы такие экспериментальные языки запросов, как IS/1 и PRTV. Языки реляционной алгебры являются процедурными языками, так как реализуют заданную последовательность операций, приводящих к результату. Вместе с тем эти языки более высокоуровневые по сравнению с языками, ориентированными на обработку отдельных записей.

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