Операции в реляционной модели данных

В предыдущем разделе (Формальное описание реляционной модели данных), мы обозначили математическое представление о реляционной модели. Теперь мы знаем, как можно хранить данные с помощью реляционной модели данных, но мы не знаем что делать с всеми этими таблицами, чтобы получить от базы данных что-нибудь ещё. Например, кто-то хочет узнать имена всех поставщиков, которые продают деталь 'Screw'. Можно определить два различных типа записи отражающих операции над отношениями:

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

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

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

Реляционная алгебра была представлена E. F. Codd в 1972 году. Она состоит из множества операций над отношениями:

• ВЫБОРКА(SELECT) (σ): извлечь кортежи из отношения, которые удовлетворяют заданным условиям. Пусть R - таблица, содержащая атрибут A. σ_A=a(R) = {t ∈ R ∣ t(A) = a} где t обозначает кортеж R и t(A) обозначает значение атрибута A кортежа t.

• ПРОЕКЦИЯ(PROJECT) (π): извлечь заданные атрибуты (колонки) из отношения. Пусть R отношение, содержащее атрибут X. π_X(R) = {t(X) ∣ t ∈ R}, где t(X) обозначает значение атрибута X кортежа t.

• ПРОИЗВЕДЕНИЕ(PRODUCT) (×): построить декартово произведение двух отношений. Пусть R - таблица, со степенью k₁ и пусть S таблица со степенью k₂. R × S - это множество всех k₁ + k₂ - кортежей, где первыми являются k₁ элементы кортежа R и где последними являются k₂ элементы кортежа S.

• ОБЪЕДИНЕНИЕ(UNION) (∪): построить теоретико-множественное объединение двух таблиц. Даны таблицы R и S (обе должны иметь одинаковую степень), объединение R ∪ S - это множество кортежей, принадлежащих R или S или обоим.

• ПЕРЕСЕЧЕНИЕ(INTERSECT) (∩): построить теоретико-множественное пересечение двух таблиц. Даны таблицы R и S, R ∪ S - это множество кортежей, принадлежащих R и S. Опять необходимо, чтобы R и S имели одинаковую степень.

• ВЫЧИТАНИЕ(DIFFERENCE) (− или ∖): построить множество различий двух таблиц. Пусть R и S опять две таблицы с одинаковой степенью. R - S - это множество кортежей R,не принадлежащих S.

• СОЕДИНЕНИЕ(JOIN) (∏): соединить две таблицы по их общим атрибутам. Пусть R будет таблицей с атрибутами A,B и C и пусть S будет таблицей с атрибутами C,D и E. Есть один атрибут, общий для обоих отношений, атрибут C. R ∏ S = π_{R.A,R.B,R.C,S.D,S.E}(σ_R.C=S.C(R × S)). Что же здесь происходит? Во-первых, вычисляется декартово произведение R × S. Затем, выбираются те кортежи, чьи значения общего атрибута C эквивалентны (σ_{R.C = S.C}). Теперь мы имеем таблицу, которая содержит атрибут C дважды и мы исправим это, выбросив повторяющуюся колонку.

  Пример 2-2. Внутреннее соединение

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

           R   A | B | C      S   C | D | E
              ---+---+---        ---+---+---
               1 | 2 | 3          3 | a | b
               4 | 5 | 6          6 | c | d
               7 | 8 | 9
  	 

  Во-первых, мы вычислим декартово произведение R × S и получим:

         R x S   A | B | R.C | S.C | D | E
                ---+---+-----+-----+---+---
                 1 | 2 |  3  |  3  | a | b
                 1 | 2 |  3  |  6  | c | d
                 4 | 5 |  6  |  3  | a | b
                 4 | 5 |  6  |  6  | c | d
                 7 | 8 |  9  |  3  | a | b
                 7 | 8 |  9  |  6  | c | d
  	

  После выборки σ_R.C=S.C(R × S) получим:

                 A | B | R.C | S.C | D | E
                ---+---+-----+-----+---+---
                 1 | 2 |  3  |  3  | a | b
                 4 | 5 |  6  |  6  | c | d
  	

  Удалить повторяющуюся колонку S.C можно с помощью проекции следующей операцией: π_{R.A,R.B,R.C,S.D,S.E}(σ_R.C=S.C(R × S)) и получим:

                     A | B | C | D | E
                    ---+---+---+---+---
                     1 | 2 | 3 | a | b
                     4 | 5 | 6 | c | d
  	

• ДЕЛЕНИЕ(DIVIDE) (÷): Пусть R будет таблицей с атрибутами A, B, C, и D и пусть S будет таблицей с атрибутами C и D. Мы можем определить деление как: R ÷ S = {t ∣ ∀ t_s ∈ S ∃ t_r ∈ R так, что t_r(A,B)=t∧t_r(C,D)=t_s} где t_r(x,y) означает кортеж таблицы R, который состоит только из элементов x и y. Заметим, что кортеж t состоит только из элементов A и B отношения R.

  Зададим следующие таблицы

            R   A | B | C | D        S   C | D
               ---+---+---+---          ---+---
                a | b | c | d            c | d
                a | b | e | f            e | f
                b | c | e | f
                e | d | c | d
                e | d | e | f
                a | b | d | e
  	

  R ÷ S получается

                           A | B
                          ---+---
                           a | b
                           e | d
  	

Более подробное описание и определение реляционной алгебры смотри у [Ullman, 1988 год] или [Дейта, 1994 год].

πSUPPLIER.SNAME(σPART.PNAME='Screw'(SUPPLIER ∏ SELLS ∏ PART))
      

                             SNAME
                            -------
                             Smith
                             Adams
      

Реляционное исчисление

Реляционное исчисление основано на логике первого порядка. Если два варианта реляционного исчисления:

• The Исчисление доменов (DRC), где переменными являются элементы (атрибуты) кортежа.

• The исчисление кортежей (TRC), где переменными являются кортежи.

Мы хотим обсудить исчисление кортежей потомучто оно лежит в основе большинства реляционных языков. Подробное обсуждение DRC (и также TRC) смотри у [Дейта, 1994 год] или [Ullman, 1988 год].

Исчисление кортежей

Запросы, использующие TRC, представлены в следующем виде: x(A) ∣ F(x) где x - это переменная кортежа, A - это множество атрибутов и F - формула. Результирующие отношение состоит из всех кортежей t(A), которые удовлетворяют F(t).

Если мы хотим ответить на вопрос из примера Запрос с использованием реляционной алгебры, с помощью TRC, то мы сформулируем следующий запрос:

     {x(SNAME) ∣ x ∈ SUPPLIER ∧ \nonumber
                       ∃ y ∈ SELLS ∃ z ∈ PART (y(SNO)=x(SNO) ∧ \nonumber
                        z(PNO)=y(PNO) ∧ \nonumber
                        z(PNAME)='Screw')} \nonumber
     

Вычисление запроса над таблицами из Базы данных поставщиков и товаров опять приведёт к тому же результату что и в Запрос с использованием реляционной алгебры.

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

Реляционная алгебра и реляционное исчисление имеют одинаковую выражающую мощность; т.е. все запросы, которые можно сформулировать с помощью реляционной алгебры, могут быть также сформулированы с помощью реляционного исчисления и наоборот. Первым это доказал E. F. Codd в 1972 году. Это доказательство основано на алгоритме (“алгоритм редукции Кодда”) по которому произвольное выражение реляционного исчисления может быть сокращено до семантически эквивалентного выражения реляционной алгебры. Более подробное обсуждение смотри у [Дейта, 1994 год] и [Ullman, 1988 год].

Иногда говорят, что языки, основанные на реляционном исчислении "высокоуровневые" или "более описательные", чем языки, основанные на реляционной алгебре, потому что алгебра (частично) задаёт порядок операций, тогда как исчисление оставляет компилятору или интерпретатору определять наиболее эффективный порядок вычисления.