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

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

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

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

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

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

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

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

S

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

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

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

P

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

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

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

R1

R2

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

Операция естественного соединения применяется к паре отношений 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

P1

P2

P3

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

SP DIVIDEBY P1:

SP DEVIDEBY P2:

SP DEVIDEBY P3:

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

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

S

P

SP

Запросы к базе данных, включающей отношения 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].