| Обучающее руководство по PostgreSQL | ||
|---|---|---|
| Предыдущий | Глава 2. SQL | Следующий |
В предыдущем разделе (Формальное описание реляционной модели данных), мы обозначили математическое представление о реляционной модели. Теперь мы знаем, как можно хранить данные с помощью реляционной модели данных, но мы не знаем что делать с всеми этими таблицами, чтобы получить от базы данных что-нибудь ещё. Например, кто-то хочет узнать имена всех поставщиков, которые продают деталь '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 - таблица, со степенью k1 и пусть S таблица со степенью k2. R × S - это множество всех k1 + k2 - кортежей, где первыми являются k1 элементы кортежа R и где последними являются k2 элементы кортежа 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 ∣ ∀ ts ∈ S ∃ tr ∈ R так, что tr(A,B)=t∧tr(C,D)=ts} где tr(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 год].
Пример 2-3. Запрос с использованием реляционной алгебры
Вспомним, что мы формулируем все эти реляционные операторы для того чтобы получить данные из базы данных. Давайте вернёмся к нашему примеру из предыдущего раздела (Операции в реляционной модели данных), где кто-то захотел узнать имена всех поставщиков, продающих деталь Screw. На этот вопрос можно ответить, используя следующие операции реляционной алгебры:
π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 год].
Иногда говорят, что языки, основанные на реляционном исчислении "высокоуровневые" или "более описательные", чем языки, основанные на реляционной алгебре, потому что алгебра (частично) задаёт порядок операций, тогда как исчисление оставляет компилятору или интерпретатору определять наиболее эффективный порядок вычисления.
| Предыдущий | Начало | Следующий |
| Формальное описание реляционной модели данных | В начало главы | Язык SQL |