Реляционное исчисление базы данных кратко

Обновлено: 05.07.2024

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

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

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

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

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

ПРОИЗВЕДЕНИЕ(PRODUCT) (×): построить декартово произведение двух отношений. Пусть R - таблица, со степенью k 1 и пусть S таблица со степенью k 2 . R × S - это множество всех k 1 + k 2 - кортежей, где первыми являются k 1 элементы кортежа R и где последними являются k 2 элементы кортежа 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 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 год ].

Пример 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) .

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

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

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

Поскольку язык SQL в итоге оказался более популярным и сегодня является стандартом для работы с реляционными данными, мы не будем сильно углубляться в эту тему, а дадим лишь краткий обзор.

Начнем с небольшого сравнения реляционной алгебры и реляционного исчисления.

Предположим, что мы работаем с базой данных, содержащей отношения Студенты (Студент_Номер, Студент_Имя, Студент_Стипендия, Группа_Номер) и Группы (Группа_Номер, Группа_Наименование, Группа_Количество, Группа_Староста), и хотим узнать имена и номера студентов, являющихся старостами групп с количеством студентов в них больше 20.

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

· Выполнить соединение отношений Студенты и Группы по условию Студент_Номер = Группа_Староста;

· Ограничить полученное отношение по условию Группа_Количество > 20;

· Спроецировать результат предыдущей операции на атрибут Студент_Имя, Студент_Номер.

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

Выдать Студент_Имя и Студент_Номер для студентов таких, что существует группа с таким же значением Группа_Староста и значением Группа_Количество большим 20.

Базисными понятиями исчисления являются понятие переменной с определенной для нее областью допустимых значений и понятие правильно построенной формулы (Well-Formed Formula, WFF), опирающейся на переменные, предикаты и кванторы.

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

В отличие от раздела, посвященного реляционной алгебре, в этом разделе нам не удастся избежать использования некоторого конкретного синтаксиса, который мы, тем не менее, формально определять не будем. Необходимые синтаксические конструкции будут вводиться по мере необходимости. В совокупности, используемый синтаксис близок, но не полностью совпадает с синтаксисом языка баз данных QUEL, который долгое время являлся основным языком СУБД Ingres.

Для определения кортежной переменной используется оператор RANGE. Например, для того, чтобы определить переменную Студент, областью определения которой является отношение Студенты, нужно употребить конструкцию:

RANGE СОТРУДНИК IS СОТРУДНИКИ

Как мы уже говорили, из этого определения следует, что в любой момент времени переменная Студент представляет некоторый кортеж отношения Студенты. При использовании кортежных переменных в формулах можно ссылаться на значение атрибута переменной (так же, как в объектно-ориентированных языках мы ссылаемся на свойства объекта). Например, для того, чтобы сослаться на значение атрибута Студент_Имя переменной Студент, нужно употребить конструкцию Студент.Студент_Имя.

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

Наконец, допускается построение WFF с помощью кванторов. Если form - это WFF, в которой участвует переменная var, то конструкции EXISTS var (form) и FORALL var (form) представляют wff.

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

Пусть Студент1 и Студент2 - две кортежные переменные, определенные на отношении Студенты. Тогда, WFF EXISTS Студент2 (Студент1.Студент_Стипендия > Студент2.Студент_Стипе-ндия) для текущего кортежа переменной Студент1 принимает значение true в том и только в том случае, если во всем отношении Студенты найдется кортеж (связанный с переменной Студент2) такой, что значение его атрибута Студент_Стипендия удовлетворяет внутреннему условию сравнения.

WFF FORALL Студент2 (Студент1.Студент_Стипендия > Студент2.Студент_Стипендия) для текущего кортежа переменной Студент1 принимает значение true в том и только в том случае, если для всех кортежей отношения Студенты (связанных с переменной Студент2) значения атрибута Студент_Стипендия удовлетворяют условию сравнения.

Итак, WFF обеспечивают средства формулировки условия выборки из отношений БД. Чтобы можно было использовать исчисление для реальной работы с БД, требуется еще один компонент, который определяет набор и имена столбцов результирующего отношения. Этот компонент называется целевым списком (target_list).

Целевой список строится из целевых элементов, каждый из которых может иметь следующий вид:

var.attr, где var - имя свободной переменной соответствующей WFF, а attr - имя атрибута отношения, на котором определена переменная var;

var, что эквивалентно наличию подсписка var.attr1, var.attr2, . var.attrn, где attr1, attr2, . attrn включает имена всех атрибутов определяющего отношения;

new_name = var.attr; new_name - новое имя соответствующего атрибута результирующего отношения.

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

Выражением реляционного исчисления кортежей называется конструкция вида target_list WHERE wff. Значением выражения является отношение, тело которого определяется WFF, а набор атрибутов и их имена - целевым списком.

В исчислении доменов областью определения переменных являются не отношения, а домены. Применительно к базе данных Студенты-Группы можно говорить, например, о доменных переменных Имя (значения - допустимые имена) или Номер_Группы (значения - допустимые номера групп).

Основным формальным отличием исчисления доменов от исчисления кортежей является наличие дополнительного набора предикатов, позволяющих выражать так называемые условия членства. Если R - это n-арное отношение с атрибутами a1, a2, . an, то условие членства имеет вид

R (ai1:vi1, ai2:vi2, . aim:vim) (m 20;

· Спроецировать результат предыдущей операции на атрибут Студент_Имя, Студент_Номер.

RANGE СОТРУДНИК IS СОТРУДНИКИ

Целевой список строится из целевых элементов, каждый из которых может иметь следующий вид:

new_name = var.attr; new_name - новое имя соответствующего атрибута результирующего отношения.

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

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

Базисными понятиями реляционного исчисления являются:

- понятие переменной с определенной для нее областью допустимых значений.

- понятие правильно построенной формулы, опирающейся на переменные, предикаты и кванторы.

Аналитические выражения записывают в одной из следующих форм:

а) - читается так: “множество переменных t таких, что истинна формула Y “

гдеt- переменная - кортеж,

t1. tk - переменные на доменах,

k - ранг отношения,

Y- формула, построенная из атомов.

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

8.2. Реляционное исчисление кортежей

Атомы формулY могут быть трех типов:

1. R(S) - означает, что S - это кортеж в отношенииR

2. s[i] @ u[j] - означает, чтоi-ая компонента S и j-ая компонентаU связаны оператором сравнения ( =).Например: s[1]

4. Если Y- формула, то(" s) (Y ) - тоже формула, которая утверждает, что при подстановке любого значения переменной S в формулу Y она остается истинной.

5. Порядок старшинства операций в формулах: операторы сравнения ( = и т.п.), $ , " , Ш ,Щ ,Ъ

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

При использовании кортежных переменных можно ссылаться на отдельный атрибут этой переменной, например: если S = (5, Иванов, 500, 3) - это кортеж отношения СОТРУДНИКИ (номер, имя, оклад, отдел), то S[3] = 500 - это значение третьего атрибута данного кортежа (оклад). На практике в языках, основанных на реляционном исчислении, часто вместо номера атрибута используют его имя, например, вместоS[3] пишут S.Оклад, что более наглядно.

Переменные, входящие в формулы, могут быть свободными или связанными. Ксвободным относят все переменные, входящие в формулу, при построении которой не использовались кванторы. Множество кортежей - значений этих переменных, при которых формула истинна, образуют результирующее отношение.

Если же имя переменной Х использовано сразу после квантора $ Х или " Х, то она считается связаннойпеременной, которая не видна за пределами формулы, описанной в кванторе. При вычислении значения такой формулы используется не одно значение связанной переменной, а вся ее область определения.Например, пусть Х и Y - две кортежные переменные, определенные на отношении СОТРУДНИКИ. Тогда, формула

$ Y (Х.Оклад > Y.Оклад)

для текущего значения Х истинна в том и только в том случае, если во всем отношении СОТРУДНИКИ найдется кортеж Y такой, что значение его атрибута Оклад удовлетворяет заданному условию сравнения.

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

1. Х.А где Х- имя свободной переменной, а А - имя атрибута отношения

2. Х, то есть имена всех атрибутов отношения

3. N = X.A, где N - новое имя атрибута результирующего отношения (когда используются несколько переменных с одинаковой областью определения)

В реальных языках БД вместо математических обозначений кванторов и логических связок используют, как правило, словесные обозначения:

$	EXISTS	Ш	NOT
"	FORALL	Щ	AND
\|	WHERE	Ъ	OR

Таким образом, аналитическое выражениереляционного исчисления кортежей можно записать в виде:

ЦелевойСписок WHERE Формула.

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

8.3. Реляционное исчисление доменов

В этом исчислении переменные являются доменами. Например, в базе данных СОТРУДНИКИ-ОТДЕЛЫ можно говорить о доменных переменных ИМЯ (значения - допустимые имена) или НОМЕР (значения - допустимые номера сотрудников). Основным отличием исчисления доменов от исчисления кортежей является наличие дополнительного набора предикатов, позволяющих выражать так называемые условия членства.

Если R - это отношение с атрибутами a₁, a₂, . a_n, то условие членства имеет вид

Аннотация: Эта лекция завершает цикл лекций, посвященных манипуляционному аспекту реляционной модели данных. Материал лекции интересен и сам по себе, поскольку демонстрирует, насколько аппарат математической логики упрощает формулировку запросов к базам данных.

Введение

Предположим, что мы работаем с базой данных, которая состоит из отношений СЛУЖАЩИЕ и ПРОЕКТЫ (в отношении ПРОЕКТЫ атрибут ПРОЕКТ_РУК содержит имена служащих, являющихся руководителями проектов, а атрибут ПРО_ЗАРП – среднее значение зарплаты, получаемой участниками проекта), и хотим узнать имена и номера служащих, которые являются руководителями проектов со средней заработной платой, превышающей 18000 руб.

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

Это выражение можно было бы прочитать, например, следующим образом:

выполнить эквисоединение отношений СЛУЖАЩИЕ и ПРОЕКТЫ по условию СЛУ_ИМЯ = ПРОЕКТ_РУК ;
ограничить полученное отношение по условию ПРО_ЗАРП > 18000.00 ;
спроецировать результат предыдущей операции на атрибут СЛУ_ИМЯ, СЛУ_НОМ .

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

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

RANGE СЛУЖАЩИЙ IS СЛУЖАЩИЕ и

RANGE ПРОЕКТ IS ПРОЕКТЫ

СЛУЖАЩИЙ.СЛУ_ИМЯ, СЛУЖАЩИЙ.СЛУ_НОМ WHERE EXISTS (СЛУЖАЩИЙ.СЛУ_ИМЯ = ПРОЕКТ.ПРОЕКТ_РУК AND ПРОЕКТ.ПРО_ЗАРП > 18000.00) .

Это выражение можно было бы прочитать, например, следующим образом: выдать значения СЛУ_ИМЯ и СЛУ_НОМ для каждого кортежа служащих такого, что существует кортеж проектов со значением ПРОЕКТ_РУК , совпадающим со значением СЛУ_ИМЯ этого кортежа служащих, и значением ПРО_ЗАРП , большим 18000.00 .

Во второй формулировке мы указали лишь характеристики результирующего отношения, но ничего не сказали о способе его формирования. В этом случае система сама должна решить, какие операции и в каком порядке нужно выполнить над отношениями СЛУЖАЩИЕ и ПРОЕКТЫ . Обычно говорят, что алгебраическая формулировка является процедурной, т. е. задающей последовательность действий для выполнения запроса, а логическая – описательной (или декларативной), поскольку она всего лишь описывает свойства желаемого результата. Как мы указывали в начале лекции 3, на самом деле эти два механизма эквивалентны, и существуют не слишком сложные правила преобразования одного формализма в другой.

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

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

Как и в лекциях, посвященных реляционной алгебре, в этой лекции нам не удастся избежать использования некоторого конкретного синтаксиса, который мы тем не менее формально определять не будем. Те или иные синтаксические конструкции будут вводиться по мере необходимости. В совокупности используемый синтаксис близок, но не полностью совпадает с синтаксисом языка баз данных QUEL, который долгое время являлся основным языком известной реляционной СУБД Ingres .

Читайте также: