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

1. Выборка (сокращенное название операции -  Θ (тета) - выборка):

S WHERE XΘY, где Θ ={<, ≤, =, ≠, ≥,>}.

Θ - выборкой из отношения S по атрибутам X и Y называется отношение, имеющее тот же заголовок, что и отношение S, и тело, содержащее множество всех кортежей отношения S таких, для которых проверка условия "XΘY" дает значение "истина". Ясно,что атрибуты X и Y должны быть определены на одном и том же домене, а операция на этом домене должна иметь смысл.

На практике эта операция используется, как правило, в модификации, когда вместо X или Y указано скалярное значение, чаще всего в форме

S WHERE XΘC, где C - литеральная константа.

В результате выполнения этого оператора получается "горизонтальное" подмножество исходного отношения.

Пример 3. Пусть задано отношение S (поставщики)

S

Номер	Фио	Город
S01	Иванов	Томск
S02	Петров	Томск
S03	Сидоров	Кемерово
S04	Кузнецов	Барнаул
S05	Быков	Омск

 

Результатом выполнения операции S WHERE Город = "Томск", будет отношение

 

Номер	Фио	Город
S01	Иванов	Томск
S02	Петров	Томск

 

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

1. S WHERE Q1 AND Q2 ≡ (S WHERE Q1) INTERSECT (S WHERE Q2)

2. S WHERE Q1 OR Q2 ≡ (S WHERE Q1) UNION (S WHERE Q2)

3. S WHERE NOT Q ≡ S MINUS (S WHERE Q)

оператор выборки можно расширить до формы, в которой условие в выражении WHERE будет содержать произвольное число логических сочетаний простых сравнений.

2. Проекция. Проекцией отношения S по атрибутам X₁, X₂, …, X_n и обозначаемой как

S[X₁, X₂, …, X_n],

называется отношение с заголовком {X₁, X₂, …, X_n}и телом, содержащим множество всех кортежей {X₁:x₁, X₂:x₂, …, X_n:x_n} таких, для которых в отношении S значение атрибута X₁ равно x₁, атрибута X₂ равно x₂, …, атрибута X_n равно x_n.

Пример 4. Результатом выполнения операции S[Фио] для отношения S предыдущего примера будет отношение

Фио

Иванов

Петров

Сидоров

Кузнецов

Быков

 

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

Замечание. Некорректное применение операции проекции может привести к потере информации; для нашего примера такая ситуация могла бы возникнуть, если в отношении S хранились бы сведения о двух разных поставщиках с одинаковой фамилией.

3. Естественное (экви) соединение. Пусть отношения S и P имеют заголовки{X₁, X₂, …, Xm, Y₁, Y₂, …, Yn} и {Y₁, Y_2,…, Y_n, Z₁, Z_2, …, Zp, соответственно, причем атрибуты {Y₁, Y₂, …, Yn}по именам и доменам в обоих отношениях совпадают.

Рассмотрим три совокупности {X₁, X₂, …, Xm}, {Y₁, Y₂, …, Yn} и { Z₁, Z₂, …, Zp} как три составных атрибута {X}, {Y} и {Z}. Тогда естественным соединением отношений S и P

S JOIN P

называется отношение с заголовком {X, Y, Z} и телом, содержащим множество всех кортежей {X:x, Y:y, Z:z} таких, для которых в отношении S значение атрибута X равно x, атрибута Y равно y, а в отношении P значение атрибута Y равно y, а атрибута Z равно z.

Замечание. При отсутствии общих атрибутов у исходных отношений S и P естественное соединение эквивалентно декартовому произведению.

Пример 5. Пусть заданы два отношения S (поставщики) и P (детали)

S

Ном_пост	Фио	Город
S01	Иванов	Томск
S02	Петров	Томск
S03	Сидоров	Кемерово
S04	Кузнецов	Барнаул
S05	Быков	Омск

 

P

Ном_дет	Назв_дет	Цвет	Вес	Город
P01	Вентиль	Белый		Томск
P02	Колено	Черный		Томск
P03	Втулка	Желтый		Кемерово
P04	Кран	Белый		Барнаул
P05	Смеситель	Белый		Барнаул
P06	Труба	Черный		Омск

 

Результатом (S JOIN P) соединения этих двух отношений будет отношение

Ном_пост	Фио	Город	Ном_дет	Назв_дет	Цвет	Вес
S01	Иванов	Томск	P01	Вентиль	Белый
S01	Иванов	Томск	P02	Колено	Черный
S02	Петров	Томск	P01	Вентиль	Белый
S02	Петров	Томск	P02	Колено	Черный
S03	Сидоров	Кемерово	P03	Втулка	Желтый
S04	Кузнецов	Барнаул	P04	Кран	Белый
S04	Кузнецов	Барнаул	P05	Смеситель	Желтый
S05	Быков	Омск	P06	Труба	Черный

Очевидно, что соединение может производиться не по одному, а по нескольким атрибутам.

Пример 6. Пусть заданы два отношения

R1

A	B	C
a1	b1	c1
a1	b2	c2
a2	b1	c1
a3	b2	c2

 

R2

B	C	D
b1	c1	d1
b1	c1	d2
b2	c2	d2

 

Результатом выполнения операции (R1 JOIN R2) будет являться отношение

 

A	B	C	D
a1	b1	c1	d1
	a1	b1	c1	d2
	a1	b2	c2	d2
	a2	b1	c1	d1
	a2	b1	c1	d2
	a3	b2	c2	d2

 

Операция естественного соединения применяется к паре отношений R1 и R2, обладающих (возможно составным) общим атрибутом S (т.е. атрибутом с одним и тем же именем и определенным на одном и том же домене). Пусть AB обозначает объединение заголовков отношений R1 и R2. Тогда естественное соединение R1 и R2 - это спроецированный на AB результат эквисоедиения R1 и R2 по A.S и B.S. Если вспомнить определение внешнего ключа отношения, то должно стать понятно, что основной смысл операции естественного соединения - возможность восстановления сложной сущности, декомопозированной (расчлененной) по причине требования первой нормальной формы. Операция естественного соединения не включается прямо в состав набора операций реляционной алгебры, но имеет очень важное практическое значение.

4. Θ-соединение (условное соединение). Это операция соединения двух отношений на основе некоторых условий, отличных от эквивалентности.

Пусть отношения S и P не имеют общих имен атрибутов и условие Θ определяется аналогично операции выборки. Тогда Θ-соединением отношения S по атрибуту X с отношением P по атрибуту Y называется результат вычисления выражения

(S TIMES P) WHERE XΘY,

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

Очевидно, что атрибуты X и Y должны быть определены на одном и том же домене и операция Θ должна иметь на этом домене смысл.

Пример 7. Пусть имеются два отношения S (потоки студенческих групп) и P (аудитории).

S

Ном_потока	Кол_студ

 

P

Ном_ауд	Вмест_ауд

Результатом выполнения операции Θ-соединения отношений S и P по условию

ВМЕСТ_АУД > КОЛ_СТУД

(вместимость аудитории должна быть больше количества студентов в потоке) будет отношение

 

Ном_потока	Кол_студ	Ном_ауд	Вмест_ауд

5. Деление. Пусть заголовки отношений S (делимое) и P (делитель) имеют вид{X₁, X₂, …, Xm, Y₁, Y₂, …, Yn}и {Y₁, Y₂, …, Yn},соответственно, причем атрибуты {Y₁, Y₂, …, Yn}в обоих отношениях представлены одинаковыми именами и определены на одних и тех же доменах. Будем рассматривать выражения{X₁, X₂, …, Xm} и {Y₁, Y₂, …, Yn}как два составных атрибута {X} и {Y}. Тогда результатом деления отношения S на отношение P, обозначаемое как

S DEVIDEBY P,

называется отношение с заголовком {X} и телом, содержащим множество всех кортежей{X:x} таких, что для каждого xЄX существует множество кортежей {X:x, Y:y} отношения S таких, у которых множество составляющих {Y:y} включает все кортежи {Y:y} отношения P. Или нестрого: результат содержит такие X-значения из отношения S, для которых соответствующие Y-значения включают все Y-значения из отношения P.

Пример 8. Пусть заданы следующие отношения

SP

Ном_пост	Ном_дет
S1	P1
S1	P2
S1	P3
S1	P4
S1	P5
S1	P6
S2	P1
S2	P2
S2	P4
S3	P2
S4	P2
S4	P4
S4	P5

 

P1

Ном_дет

P1

 

P2

Ном_дет

P2

P4

 

P3

Ном_дет

P1

P2

P3

P4

P5

 

Результатами выполнения операций деления будут следующие отношения:

 

SP DIVIDEBY P1:

Ном_пост

S1

S2

SP DEVIDEBY P2:

Ном_пост

S1

S2

S4

SP DEVIDEBY P3:

Ном_пост

S1

 

 

Пример использования операций реляционной алгебры

Пусть заданы отношения S (поставщики), P (детали) и SP (поставки):

 

S

Ном_пост	Фио	Город
S01	Иванов	Томск
S02	Петров	Томск
S03	Сидоров	Кемерово
S04	Кузнецов	Барнаул
S05	Быков	Омск

P

Ном_дет	Назв_дет	Цвет	Вес	Город
P01	Вентиль	Белый		Томск
P02	Колено	Черный		Томск
P03	Втулка	Желтый		Кемерово
P04	Кран	Белый		Барнаул
P05	Смеситель	Желтый		Барнаул
P06	Труба	Черный		Омск

 

SP

Ном_пост	Ном_дет	Количество
S01	P01
S01	P02
S01	P03
S01	P04
S01	P05
S01	P06
S02	P01
S02	P02
S03	P02
S04	P02
S04	P04
S04	P05

 

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

Запрос 1. Получить имена поставщиков, поставляющих деталь "Колено"

(((SP JOIN P) WHERE Назв_дет = "Колено") JOIN S) [Фио]

Запрос 2. Получить имена поставщиков, поставляющих все детали.

(((SP[Ном_пост, Ном_дет]) DEVIDEBY (P[Ном_дет])) JOIN S) [Фио]

Запрос 3. Получить имена поставщиков, которые не поставляют деталь "Кран".

(S[Ном_пост,Фио]MINUS(((SP JOIN P) WHERE Назв_дет="Кран")JOIN S) [Ном_пост,ФИО]) [Фио]

Учитывая, что каждый экземпляр схемы отношения можно представить как значение некоторой переменной, выполнение этого запроса может быть реализовано следующей иллюстративной программой:

 

T1 = S[Ном_пост, Фио];

T2 = SP JOIN P;

T3 = T2 WHERE Назв_дет = "Кран";

T4 = T3 JOIN S;

T5 = T4[Ном_пост, Фио];

T6 = T1 MINUS T5;

T7 = T6[Фио].

Замечание. Если посмотреть на общий обзор реляционных операций, то видно, что домены атрибутов результирующего отношения однозначно определяются доменами отношений-результатов. Однако с именами атрибутов результата не всегда бывает все так просто. Например, представим себе, что у отношений-операндов операции прямого произведения имеются одноименные атрибуты с одинаковыми доменами. Каким должен был бы быть заголовок результирующего отношения? Поскольку заголовок - это множество, в нем не должны содержаться одинаковые элементы. Но и потерять атрибут в результате недопустимо. А это значит, что в этом случае вообще невозможно корректно выполнить операцию прямого произведения. Аналогичные проблемы могут возникать и в случаях других двуместных операций. Для их разрешения в состав операций реляционной алгебры вводится операция переименования. Ее следует применять в любом случае, когда возникает конфликт именования атрибутов в отношениях-операндах одной реляционной операции. Тогда к одному из операндов сначала применяется операция переименования, а затем основная операция выполняется уже безо всяких проблем.

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

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

Пример. Пусть к базе данных, содержащей отношения S, P и SP (точнее, к СУБД, в рамках которой реализована данная база данных) поступил запрос:

"Получить номера и города поставщиков, поставляющих деталь "Смеситель".

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

П1. Образовать естественное соединение отношений SP и P по атрибуту Ном_дет.

П2. Выбрать из результата этого соединения кортежи, у которых Назв_дет= "Смеситель".

П3. Образовать естественное соединение результирующего отношения П2 и отношения S по атрибуту Ном_пост.

П4. Спроецировать результирующее отношение по атрибутам Ном_пост и Город.

В терминах реляционного исчисления формулировка искомого выражения могла бы выглядеть следующим образом:

“Получить атрибуты Ном_пост и Город для таких поставщиков отношения S, для которых существует поставка в отношении SP детали со значением атрибута Ном_дет таким, что значение атрибута Назв_дет в соответствующих кортежах отношения P равно " Смеситель ".

Реляционное исчисление основано на разделе математической логики, который называется исчислением (или логикой) предикатов. Существуют две версии реляционного исчисления – исчисление кортежей и исчисление доменов.

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

Рассмотрим основные понятия данного инструментария:

· переменная кортежа,

· правильно построенная формула,

· выражение исчисления кортежей.

Пусть переменная кортежа определяется (описывается) выражением [3]

RANGE OF T IS V₁, V₂, …, V_n,

где

T – переменная кортежа,

V _i (i =1, …, n) – имя отношения либо выражение исчисления кортежей.

Пусть каждое из V_i (i =1, …, n) является отношением, причем все отношения должны быть совместимыми по типу. Тогда областью значений переменной кортежа T является множество кортежей объединения отношений V_i (i =1, …, n).

Примеры определения переменной кортежа:

RANGE OF TS IS S;

RANGE OF TP IS P;

RANGE OF T1 IS TS WHERE S.Город = "Томск".

Замечание. В третьем примере значениями переменной Т1 являются все кортежи отношения S, для которых выполняется указанное в определении условие.

 

Правильно построенная формула (ППФ). Понятие ППФ является одним из центральных в логике предикатов, следовательно, и в реляционном исчислении. ППФ служат для выражения условий, накладываемых на кортежные переменные.

Базовым при построении ППФ является определение атома. Применительно к исчислению кортежей выделяют два типа атомов:

Тип 1. T.X Θ U.Y, где T,U – переменные-кортежи, X,Y – атрибуты, Θ = {<, ≤, =, ≠, ≥,>}.

Тип 2. С Θ T.X, T.X Θ С, где C – литеральная константа.

Таким образом, основой ППФ являются простые сравнения, представляющие собой операции сравнения скалярных значений (значений атрибутов переменных или литерально заданных констант). Например, конструкция S.Город ="Томск" является простым сравнением. По определению, простое сравнение является ППФ. Итак,

Правило 1. Каждый атом есть ППФ.

Более сложные варианты ППФ строятся с помощью логических связок NOT, AND, OR и IF... THEN.

Правило 2 (введение логических формул).

Если φ и ψ – суть ППФ, то

- NOT φ,

- φ AND ψ,

- φ OR ψ,

- IF Q THEN φ, (где Q – логическая формула),

- (φ),

тоже суть ППФ.

Наконец, допускается построение ППФ с помощью кванторов.

Правило 3 (введение кванторов).

Обозначим через EXISTS квантор с уществования и через FORALL – квантор всеобщности. Пусть φ есть ППФ и T – переменная. Тогда

- EXISTS T(φ),

- FORALL T(φ) - суть ППФ.

Здесь первая формула означает:

"Существует по крайней мере одно такое значение переменной T (по крайней мере один кортеж соответствующего отношения), на котором результат вычисления ППФ φ равен булевому значению True ".

Трактовка второй формулы очевидна:

"Для всех значений переменной T (на всех кортежах соответствующего отношения) вычисление значения ППФ φ дает значение True. "

Переменные, входящие в ППФ, могут быть свободными или связанными. Все переменные, входящие в ППФ, при построении которой не использовались кванторы, являются свободными. Фактически, это означает, что если для какого-то набора значений свободных кортежных переменных при вычислении ППФ получено значение истина, то эти значения кортежных переменных могут входить в результирующее отношение. Если же имя переменной Т использовано сразу после квантора при построении ППФ вида EXISTS или FORALL, то в этой ППФ и во всех ППФ, построенных с ее участием, Т - это связанная переменная. Это означает, что такая переменная не видна за пределами минимальной ППФ, связавшей эту переменную. При вычислении значения такой ППФ используется не одно значение связанной переменной, а вся ее область определения.

Пусть СОТР1 и СОТР2 - две кортежные переменные, определенные на отношении СОТРУДНИКИ. Тогда, ППФ

EXISTS СОТР2 (СОТР1.Сотр_зарп > СОТР2.Сотр_зарп)

для текущего кортежа переменной СОТР1 принимает значение истина в том и только в том случае, если во всем отношении СОТРУДНИКИ найдется хотя бы один кортеж (связанный с переменной СОТР2) такой, что значение его атрибута СОТР_ЗАРП удовлетворяет внутреннему условию сравнения. В свою очередь, ППФ

FORALL СОТР2 (СОТР1.Сотр_зарп > СОТР2.Сотр_зарп)

для текущего кортежа переменной СОТР1 принимает значение истина в том и только в том случае, если для всех кортежей отношения СОТРУДНИКИ (связанных с переменной СОТР2) значения атрибута Сотр_зарп удовлетворяет условию сравнения.

На самом деле, правильнее говорить не о свободных и связанных переменных, а о свободных и связанных вхождениях переменных. Легко видеть, что если переменная T является связанной в ППФ φ, то во всех ППФ, включающих φ, может использоваться имя переменной T, которая может быть свободной или связанной, но в любом случае не имеет никакого отношения к вхождению переменной T в ППФ φ.

Пример. Пусть ППФ F1 и F2 имеют следующий вид:

F1 - EXISTS СОТР2 (СОТР1.Сотр_отд_ном = СОТР2.Сотр_отд_ном)

F2 - FORALL СОТР2 (СОТР1.Сотр_зарп > СОТР2.Сотр_зарп)

Очевидно, что в ППФ (F1 AND F2) два связанных вхождения переменной СОТР2 имеют совершенно разный смысл.

Сформулируем данные понятия более точно. Под экземпляром переменной кортежа в ППФ будем понимать наличие имени переменной:

a) в строке T.X,

b) в строках EXISTS T и FORALL T.

Заметим, что здесь понятие экземпляра переменной рассматривается в чисто синтаксическом аспекте.

Каждый экземпляр переменной кортежа T в ППФ является или свободным, или связанным в зависимости от выполнения следующих условий:

· в атомах все экземпляры свободны;

· экземпляры переменной T, которые в формуле φ, связаны в формулах EXISTS T(φ) и FORALL T(φ);

· в логических ППФ экземпляры свободны или связанны в зависимости от того, свободны или связаны они в формулах φ и ψ.

Примеры:

Атомы:

1) TS.Ном_пост=”S1”

2) TS.Ном_пост ≠ TSP.Ном_пост

Экземпляры TS и TSP в обоих примерах свободны.

Логические формулы:

1) NOT (TS.Город = “Томск”)

2) (TS.Ном_пост = TSP.Ном_пост) AND (TSP.Ном_дет ≠ T.Ном_дет)

Экземпляры TS и TSP в обоих примерах свободны.

Кванторные формулы:

1) EXISTS TSP ((TSP.Ном_пост = TS.Ном_пост) AND (TSP.Ном_дет = TP.Ном_дет) AND (TP.Назв_дет ≠ “Смеситель”))

2) FORALL TP (TP.цвет = “Белый”)

В первом примере все три экземпляра TSP связаны, а экземпляры TS и TP – свободны; во втором примере оба экземпляра TP связаны.

Еще раз отметим, что понятие связности необходимо для определения истинности или ложности формулы (соответствующего утверждения): связность принципиальным образом уточняет сформулированное утверждение.

Выражения исчисления кортежей. В общем виде выражение исчисления кортежей имеет вид:

<список_целевых_элементов> [WHERE ППФ],

где:

- целевой элемент - имя простой переменной (T) или выражение вида (T.A),

- WHERE – условие.

Результатом выполнения выражения является удовлетворение запроса к базе данных.

Примеры. Реализовать в виде выражений следующие запросы:

1) "Определить имена поставщиков, поставляющих деталь "Кран":

TS.ФИО WHERE EXISTS TSP ((EXISTS TS(TSP.Ном_пост = TS.Ном_пост)) AND (EXISTS TP ((TS.Ном_дет = TP.Ном_дет) AND (TP.Ном_дет = “Кран”)))

2) "Определить имена поставщиков, поставляющих все детали":

TS.ФИО WHERE FORALL TP (EXISTS TSP)(EXITS TS (TSP.Ном_пост = TS.Ном_пост)) AND (TSP.Ном_дет = TS.Ном_дет)))

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

Таким образом, можно сказать, что, по крайней мере внешне, формулировка удовлетворения запроса в терминах реляционной алгебры носит предписывающий (процедурный) характер, а реляционного исчисления – описательный (декларативный). В алгебре описывается решение проблемы, запрос, представленный на языке реляционной алгебры, может быть вычислен на основе вычисления элементарных алгебраических операций с учетом их старшинства и возможного наличия скобок. В исчислении предикатов описывается, в чем проблема заключается; формула только устанавливает условия, которым должны удовлетворять кортежи результирующего отношения.

Эти отличия, однако, существуют только внешне. Доказано, что механизмы реляционной алгебры и реляционного исчисления эквивалентны, то есть для любого допустимого выражения реляционной алгебры можно построить эквивалентную (т.е. производящую такой же результат) формулу Различия связаны с разными стилями выражения: алгебра ближе к языкам программирования, а исчисление – естественному языку.

Обычно (как, например, в случае языка SQL) язык основывается на некоторой смеси алгебраических и логических конструкций. Тем не менее, знание алгебраических и логических основ языков баз данных часто бывает полезно на практике.

Подробно реляционная модель данных рассмотрена в [2].