Основы реляционной алгебры реферат

Обновлено: 05.07.2024

Пример того, как можно комбинировать оператор выборки и проекции. Выберем id студентов с gpa > 3.7:

2.3 Оператор переименования

Как следует из названия оператор переименования позволяет переименовывать атрибуты отношений. Оператор переименования является унарным оператором и имеет следующую форму:

где new - новое название атрибута, original - старое название атрибута. Например для отношения:

Получим новое отношение с переименованными атрибутами:

Далее на примерах мы поймем почему данный оператор так важен.

3.1 Декартово произведение

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

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

в результате получим отношение:

Декартово произведение в нашем случае является бинарным оператором, поэтому для соединения более двух отношении необходимо использовать скобки.

$$ Person \times (Employee \times Parking) $$

Само по себе декартово произведение не так полезно, если его не использовать с другими операторами.

Например, мы хотим получить место парковки Боба. Для этого используя декартово произведение можно применить оператор выборки на сравнение EmployeeId и ParkingId к результату полученного отношения:

В результате получим отношение

3.2 Естественное соединение

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

$$ Employee \bowtie Parking $$

Пример решения задачи отображения места парковки Боба используя оператор естественного соединения:

3.3 Тета соединение

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

В большинстве реляционных базах данных в качестве оператора JOIN используется именно тета соединение.

Для наглядности мы можем переписать наш предыдущий запрос получения места парковки Боба используя тета соединение:

4.1 Оператор объединения

Все операторы, которые были описаны выше используются для объединения кортежей таблиц по горизонтали. А что если необходимо объединить в один список значения из разных таблиц? Для этого удобнее всего будет воспользоваться оператором объединения. Например, можно объединить столбцы Id отношений Parking и Employee:

$$\pi_Employee \cup \pi_Parking$$

Оператор объединения ожидает, что типы объединяемых столбцов, их название и их количество должно быть одинаковым. Для объединения столбцов с разными названиями можно воспользоваться оператором переименования:

4.2 Оператор разности

Оператор разности для отношений работает так же как и для множеств, так как отношения являются сами по себе множествами, как мы рассмотрели ранее.

Например, нам нужно получить список свободных парковочных мест. Для этого мы можем применить оператор разности между отношениями Employee и Parking:

$$\pi_ Parking - \pi_ Employee$$

Но данный запрос в качестве результата покажет только Id парковочных мест. Что если мы хотели бы показать еще и номера свободных парковочных мест? Мы не можем добавить в контекст проекции атрибут Space, так как это исказит наше множество. Для этого мы можем применить естественное соединение к полученному результату из множества Id свободных парковочных мест:

$$ \pi_ ((\pi_Parking - \pi_Employee) \bowtie Parking) $$

4.3 Пересечение

Оператор пересечения возвращает общие элементы двух множеств. Пересечение множеств можно представить в виде равенства:

ГОСТ

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

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

Коддом был предложен вариант реляционной алгебры, который содержит основные операции объединения, разности (вычитания), пересечения, декартова (прямого) произведения (или просто произведения), выборки (селекции, ограничения), проекции, деления и соединения.

На рисунке 1 представлено графическое представление названных операций.

Недостатки реляционной алгебры Кодда

Реляционная алгебра, предложенная Коддом, имеет несколько недостатков:

Перечисленные операции являются избыточными, т.к. минимально необходимым набором являются 5 операций: операция объединения, вычитания, произведения, проекции и выборки. Остальные 3 операции (пересечения, соединения и деления) можно представить в виде комбинации пяти минимально необходимых. К примеру, соединение является проекцией выборки произведения.
Названных операций недостаточно для возможности построения реальной системы построения БД, основанной на принципах реляционной алгебры. Необходимы расширения, которые включают операции переименования атрибутов, создания новых вычисляемых атрибутов, нахождения итоговых функций, составления сложных алгебраических выражений, сравнения, присвоения и т.д.

Готовые работы на аналогичную тему

Операции реляционной алгебры Кодда

Операции реляционной алгебры Кодда делятся на 2 группы:

Базовые теоретико-множественные – включают классические операции теории множеств: объединения, разности, пересечения и произведения.
Специальные реляционные – включают операции проекции, селекции, деления и соединения.

Операции реляционной алгебры могут быть унарными – выполненными над одним отношением (к примеру, проекция), и бинарными – выполненными над двумя отношениями (к примеру, разность).

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

Под совместимостью структур отношений понимается совместимость типов соответствующих доменов и имен атрибутов.

Частный случай совместимости – совпадение (идентичность).

Объединение

Отношение $R$ является объединением ($R1 UNION R2$) двух совместимых отношений одинаковой размерности $R1$ и $R2$, если оно содержит все элементы исходных отношений, исключая повторения.

Пусть отношение $R1$ является множеством поставщиков из Парижа, а отношение $R2$ – множеством поставщиков, выпускающих деталь $D1$. Тогда отношением $R$ будут поставщики, которые находятся в Париже, поставщики, которые выпускают деталь $D1$, или те и другие.

Вычитание

Отношение $R$ является вычитанием ($R1 MINUS R2$) совместимых отношений одинаковой размерности $R1$ и $R2$, если оно содержит множество кортежей, которые принадлежат $R1$, но не принадлежат отношению $R2$.

Для отношений $R1$ и $R2$ из рассмотренного примера отношение $R$ будет являться множеством поставщиков, которые находятся в Париже, но не выпускают деталь $D1$, то есть $R=<(D4, Николай, 20, Париж)>$.

Обратим внимание, что выполнение вычитания зависит от порядка следования операндов, то есть результаты выполнения операций $R2 MINUS R1$ и $R1 MINUS R2$ будут разными.

Пересечение

Отношение $R$ является пересечением ($R1 INTERSECT R2$) двух совместимых отношений одинаковой размерности $R1$ и $R2$, если оно содержит кортежи, которые одновременно принадлежат обоим исходным отношениям.

Отношение $R$ для отношений $R1$ и $R2$ будет состоять из всех производителей из Парижа, которые выпускают деталь $D1$. Таким образом, отношение $R$ содержит единственный элемент $(D1, Сергей, 20, Париж)$.

Произведение

Произведением ($R1 TIMES R2$) отношения $R1$ степени $s1$ и отношения $R2$ степени $s2$, которые не содержат одинаковые имена атрибутов, является такое отношение $R$ степени $(s1+s2)$, которое имеет заголовок в виде сцепления заголовков отношений $R1$ и $R2$ и содержит кортежи, первые $s1$ элементов кортежей из которых принадлежат множеству $R1$, а следующие $s2$ элементов принадлежат множеству $R2$.

Выборка

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

При записи формулы используют операнды – имена атрибутов (можно номера столбцов), логические операции (NOT – НЕ, OR – ИЛИ, AND – И), константы, скобки и операции сравнения.

Проекция

Проекцией отношения $R$ на атрибуты $А, В, С, \cdots (R [А, В, С, \cdots])$, где множество $$ – подмножество полного списка атрибутов заголовка отношения $R$, является отношение с заголовком $А, В, С, \cdots$ и телом, которое содержит кортежи отношения $R$ без повторяющихся кортежей.

Наличие одинаковых атрибутов в списке $А, В, С, \cdots$ недопустимо.

Деление

Отношение $R$ является делением ($R1 DIVIDEBY R2$) отношения $R1$ с атрибутами $А$ и $В$ на отношение $R2$ с атрибутом $В$ ($А$ и $В$ могут быть простыми или составными атрибутами, $В$ – общий атрибут, который определен на одном и том же домене), если оно имеет заголовок $А$ и тело, состоящее из кортежей $r$ таких, что отношение $R1$ содержит кортежи $(r, s)$, к тому же множество значений $s$ содержит множество значений атрибута $В$ отношения $R2$.

Соединение

Отношение $R$ является соединением $Cf(R1, R2)$ отношений $R1$ и $R2$ по заданному формулой $f$ условию, если его можно получить с помощью декартова произведения отношений $R1$ и $R2$ с применением к полученному результату операции выборки по формуле $f$.

Иначе говоря, соединение отношения $R1$ по атрибуту $Х$ с отношением $R2$ по атрибуту $Y$ (отношения не могут иметь общие имена атрибутов) является результатом выполнения операции вида:

$(R1 TIMES R2) WHERE X Q Y$,

где $Q$ является логическим выражением над атрибутами, которые определены на одном (в случае составного атрибута – на нескольких) домене. Дейтом были предложены дополнительные операции реляционной алгебры, к которым относятся: переименование, расширение, подведение итогов, присвоение, вставка, обновление, удаление, сравнение.

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Описание презентации по отдельным слайдам:

Основы реляционной алгебры

Появление теоретико-множественных моделей в системах баз данных было предопределено настоятельной потребностью пользователей в переходе от работы с элементами данных, как это делается в графовых моделях, к работе с некоторыми макрообъектами. Основной моделью в этом классе является реляционная модель данных.
Теоретической основой этой модели стала теория отношений, основу которой заложили два логика — американец Чарльз Содерс Пирс (1839-1914) и немец Эрнст Шредер (1841-1902).
Американский математик Эдгар Франк Кодд в 1970 году впервые сформулировал основные понятия и ограничения реляционной модели, ограничив набор операций в ней семью основными и одной дополнительной операцией. Предложения Кодда были настолько эффективны для систем баз данных, что за эту модель он был удостоен престижной премии Тьюринга в области теоретических основ вычислительной техники.

Основной структурой данных в модели является отношение, именно поэтому модель получила название реляционной (от английского relation — отношение).

Домен – это общее множество значений, из которых берутся конкретные значения определенного атрибута некоторого отношения (D)

Кортеж соответствует экземпляру записи

Степень (n – арность отношения)– количество атрибутов

Кардинальное число (кардинальность отношения) – количество кортежей содержащихся в отношении
Набор атрибутов, однозначно определяющий каждый объект, называют ключом.

Для таблицы должны выполняться следующие правила:

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

Если атрибуты принимают значения из одного и того же домена, то они называются Q-сравпимыми, где Q множество допустимых операций сравнения, заданных для данного домена.
Например, если домен содержит числовые данные , то для него допустимы все операции сравнения, тогда Q = ,>=, >. Однако и для доменов, содержащих символьные данные, могут быть заданы не только операции сравнения по равенству и неравенству значений. Если для данного домена задано лексикографическое упорядочение, то он имеет также полный спектр операций сравнения.
Схемы двух отношений называются эквивалентными, если они имеют одинаковую степень и возможно такое упорядочение имен атрибутов в схемах, что на одинаковых местах будут находиться сравнимые атрибуты, то есть атрибуты, принимающие значения из одного домена.

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

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

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

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

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

Основным множеством в реляционном алгебре является множество отношений.

Всего Коддом было предложено 8 операций.

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

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

Операции над отношениями
Объединение
Пересечение
Разность
Произведение
Выборка (ограничение)
Проекция
Соединение
Деление

Разностью отношений R1 и R2 называется отношение, содержащее множество кортежей, принадлежащих R1 и не принадлежащих R2

Пример
Исходными являются три отношения R1 R2 и R3.

Все они имеют эквивалентные схемы.
R1= (ФИО, Паспорт, Школа);
R2= (ФИО, Паспорт, Школа);
R3= (ФИО, Паспорт, Школа).

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

Ответим на следующие вопросы:

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

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

Эта операция не накладывает никаких дополнительных условий на схемы исходных отношений, поэтому операция расширенного декартова произведения, обозначаемая R1 ® R2, допустима для любых двух отношений.

Сцеплением, или конкатенацией, кортежей с = и q = называется кортеж, полученный добавлением значений второго в конец первого.

Сцепление кортежей с и q обозначается как (с , q).
(с, q) =
Здесь n — число элементов в первом кортеже с, m — число элементов во втором кортеже q.

Расширенным декартовым произведением отношения R, степени n со схемой
SR1=(А1,А2. Аn)
и отношения R2 степени m со схемой
SR2=(В1,В2, . , Вm)
называется отношение R3 степени n+m со схемой
SR3 = (А1, А2, . , Аn, В1, В2, . Вm),
содержащее кортежи, полученные сцеплением каждого кортежа r отношения R1 с каждым кортежем q отношения R2.
То есть если R1 = < r >, R2 = < q >
R1 ® R2 =

Например, на производстве в отношении R7 задана обязательная номенклатура деталей для всех цехов, а в отношении R8 дан перечень всех цехов.

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

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

Пусть а — булевское выражение, составленное из термов сравнения с помощью связок И , ИЛИ , НЕ и, возможно, скобок. В качестве термов сравнения допускаются:
а) терм А ос а, где А — имя некоторого атрибута, принимающего значения из домена D; а — константа, взятая из того же домена D; ос — одна из допустимых для данного домена D операций сравнения;
б) терм А ос В, где А, В — имена некоторых Q-сравнимых атрибутов, то есть атрибутов, принимающих значения из одного и то же домена D.

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

Проекцией отношения R на набор атрибутов В, обозначаемой R[B], называется отношение со схемой, соответствующей набору атрибутов В, содержащему кортежи, получаемые из кортежей исходного отношения R путем удаления из них значений, не принадлежащих атрибутам из набора В.

По определению отношений все дублирующие кортежи удаляются из результирующего отношения.

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

Операция условного соединения.
Результат соединения – это отношение, кортежи которого являются сочетанием двух кортежей, принадлежащих двум начальным отношениям и имеющих общие значения для одного или нескольких атрибутов (общее значение в результирующем отношении появляется только один раз).
Пусть R = , Q = < q >— исходные отношения,
SR, SQ — схемы отношений R и Q соответственно.
SR = (А1, А2, . , Ak): SQ = (В1 В2, . , Bm),
где А, В, — имена атрибутов в схемах отношений R и Q соответственно. При этом полагаем, что заданы наборы атрибутов А и В и эти наборы состоят из Q-сравнимых атрибутов.
Тогда соединением отношений R и Q при условии р будет подмножество декартова произведения отношений R и Q, кортежи которого удовлетворяют условию р

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

Пусть заданы два отношения:
A с заголовком
B с заголовком .

Будем считать, что атрибут bi отношения A и атрибут bi отношения B не только обладают одним и тем же именем, но и определены на одном и том же домене.
Назовем множество атрибутов составным атрибутом a, а множество атрибутов - составным атрибутом b.

После этого будем говорить о реляционном делении бинарного отношения A(a,b) на унарное отношение B(b).

Результатом деления A на B является унарное отношение C(a), состоящее из кортежей v таких, что в отношении A имеются кортежи такие, что множество значений включает все множество значений атрибута b в отношении B.

Операция деления удобна тогда, когда требуется сравнить некоторое множество характеристик отдельных атрибутов.

Например, пусть у нас есть отношение A, которое содержит номенклатуру всех выпускаемых деталей на нашем предприятии, а в отношении B хранятся сведения о том, что и в каких цехах действительно выпускается.

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

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

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

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

P(D1,D2,D3) Q(D4,D5) R(M,P,Q,T) S(A,B)

1 11 x x 1 x 101 5 a 5 a

2 11 y x 2 y 105 3 a 10 b

3 11 z y 1 z 500 9 a 15 c

4 12 x w 50 1 b 2 d

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

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

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

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

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

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

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

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

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

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

Помимо этого есть ряд особых операций, характерных для работы с БД:

ü переименование, результатом которого получается отношение, набор кортежей которого совпадает с телом первоначального отношения, но имена атрибутов изменены;

ü присваивание – позволяет сохранить результат вычисления реляционного выражения в существующем отношении БД.

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