Реляционная алгебра базируется на теории множеств и является основой логики работы баз данных.
Когда я только изучал устройство баз данных и SQL, предварительное ознакомление с реляционной алгеброй очень помогло дальнейшим знаниям правильно уложиться в голове, и я постараюсь что бы эта статья произвела подобный эффект.
Так что если вы собираетесь начать свое обучение в этой области или вам просто стало интересно, прошу под кат.
Реляционная база данных
Для начала введем понятие реляцинной базы данных, в которой будем выполнять все действия.
Реляционной базой данных называется совокупность отношений, содержащих всю информацию, которая должна хранится в базе. В данном определении нам интересен термин отношение, но пока оставим его без строго определения.
Лучше представим себе таблицу продуктов.
Таблица PRODUCTS
| ID | NAME | COMPANY | PRICE |
| 123 | Печеньки | ООО ”Темная сторона” | 190 |
| 156 | Чай | ООО ”Темная сторона” | 60 |
| 235 | Ананасы | ОАО ”Фрукты” | 100 |
| 623 | Томаты | ООО ”Овощи” | 130 |
Таблица состоит из 4х строк, строка в таблице является кортежем в реляционной теории. Множество упорядоченных кортежей называется отношением.
Перед тем как дать определение отношения, введем еще один термин - домен. Домены применительно к таблице это столбцы.
Для ясности, теперь введем строгое определение отношения.
Пусть даны N множеств D1,D2, …. Dn (домены), отношением R над этими множествами называется множество упорядоченных N-кортежей вида
Каждый элемент кортежа представляет собой значение одного из атрибутов, соответствующего одному из доменов.
Ключи в отношениях
В отношении требованием является то, что все кортежи должны различаться. Для однозначной идентификации кортежа существует первичный ключ. Первичный ключ это атрибут или набор из минимального числа атрибутов, который однозначно идентифицирует конкретный кортеж и не содержит дополнительных атрибутов.Подразумевается, что все атрибуты в первичном ключе должны быть необходимыми и достаточными для идентификации конкретного кортежа, и исключение любого из атрибутов в ключе сделает его недостаточным для идентификации.
Например, в такой таблице ключом будет сочетание атрибутов из первого и второго столбца.
Таблица DRIVERS
Видно, что в организации может быть несколько водителей, и чтобы однозначно идентифицировать водителя необходимо и значение из столбца “Название организации” и из “Имя водителя”. Такой ключ называется составным.
В реляционной БД таблицы взаимосвязаны и соотносятся друг с другом как главные и подчиненные. Связь главной и подчиненнной таблицы осуществляется через первичный ключ (primary key) главной таблицы и внешний ключ (foreign key) подчиненной таблицы.
Внешний ключ это атрибут или набор атрибутов, который в главной таблице является первичным ключем.
Этой подготовительной теории будет достаточно для знакомства с основными операциями реляционной алгебры.
Операции реляционной алгебры
Основные восемь операций реляционной алгебры были предложены Э.Коддом .- Объединение
- Пересечение
- Вычитание
- Декартово произведение
- Выборка
- Проекция
- Соединение
- Деление
Для понимания важно запомнить, что результатом любой операции алгебры над отношениями является еще одно отношение, которое можно потом так же использовать в других операциях.
Создадим еще одну таблицу, которая нам пригодится в примерах.
Таблица SELLERS
| ID | SELLER |
| 123 | OOO “Дарт” |
| 156 | ОАО ”Ведро” |
| 235 | ЗАО “Овоще База” |
| 623 | ОАО ”Фирма” |
Условимся, что в этой таблице ID это внешний ключ, связанный с первичным ключом таблицы PRODUCTS.
Для начала рассмотрим самую простую операцию - имя отношения. Её результатом будет такое же отношение, то есть выполнив операцию PRODUCTS, мы получим копию отношения PRODUCTS.
Проекция
Проекция является операцией, при которой из отношения выделяются атрибуты только из указанных доменов, то есть из таблицы выбираются только нужные столбцы, при этом, если получится несколько одинаковых кортежей, то в результирующем отношении остается только по одному экземпляру подобного кортежа.Для примера сделаем проекцию на таблице PRODUCTS выбрав из нее ID и PRICE.
Синтаксис операции:
π
(ID, PRICE) PRODUCTS
В условии выборки мы можем использовать любое логическое выражение. Сделаем еще одну выборку с ценой больше 90 и ID товара меньше 300:
σ (PRICE>90 ^ ID<300) PRODUCTS
Умножение
Умножение или декартово произведение является операцией, производимой над двумя отношениями, в результате которой мы получаем отношение со всеми доменами из двух начальных отношений. Кортежи в этих доменах будут представлять из себя все возможные сочетания кортежей из начальных отношений. На примере будет понятнее.Получим декартово произведения таблиц PRODUCTS и SELLERS.
Синтаксис операции:
PRODUCTS × SELLERS
Можно заметить, что у двух этих таблиц есть одинаковый домен ID. В подобной ситуации домены с одинаковыми названиями получают префикс в виде названия соответствующего отношения, как показано ниже.
Для краткости перемножим не полные отношения, а выборки с условием ID<235
(цветом выделены одни и те же кортежи)
| PRODUCTS.ID | NAME | COMPANY | PRICE | SELLERS.ID | SELLER |
| 123 | Печеньки | ООО ”Темная сторона” | 190 | 123 | OOO “Дарт” |
| 156 | Чай | ООО ”Темная сторона” | 60 | 156 | ОАО ”Ведро” |
| 123 | Печеньки | ООО ”Темная сторона” | 190 | 156 | ОАО ”Ведро” |
| 156 | Чай | ООО ”Темная сторона” | 60 | 123 | OOO “Дарт” |
Для примера использования этой операции представим себе необходимость выбрать продавцов с ценами меньше 90. Без произведения необходимо было бы сначала получить ID продуктов из первой таблицы, потом по этим ID из второй таблицы получить нужные имена SELLER, а с использованием произведения будет такой запрос:
π (SELLER) σ (RODUCTS.ID=SELLERS.ID ^ PRICE<90) PRODUCTS × SELLERS
В результате этой операции получим отношение:
| SELLER |
| ОАО ”Ведро” |
Соединение и естественное соединение
Операция соединения обратна операции проекции и создает новое отношение из двух уже существующих. Новое отношение получается конкатенацией кортежей первого и второго отношений, при этом конкатенации подвергаются отношения, в которых совпадают значения заданных атрибутов. В частности, если соединить отношения PRODUCTS и SELLERS, этими атрибутами будут атрибуты доменов ID.Также для понятности можно представить соеднинение как результат двух операций. Сначала берется произведение исходных таблиц, а потом из полученного отношения мы делаем выборку с условием равенства атрибутов из одинаковых доменов. В данном случае условием явлется равенство PRODUCTS.ID и SELLERS.ID.
Попробуем соединить отношения PRODUCTS и SELLERS и получим отношение.
| PRODUCTS.ID | NAME | COMPANY | PRICE | SELLERS.ID | SELLER |
| 123 | Печеньки | ООО ”Темная сторона” | 190 | 123 | OOO “Дарт” |
| 156 | Чай | ООО ”Темная сторона” | 60 | 156 | ОАО ”Ведро” |
| 235 | Ананасы | ОАО ”Фрукты” | 100 | 235 | ЗАО “Овоще База” |
| 623 | Томаты | ООО ”Овощи” | 130 | 623 | ОАО ”Фирма” |
Натуральное соединение получает схожее отношение, но в случае, если у нас корректно настроена схема в базе (в данном случае первичный ключ таблицы PRODUCTS ID связан с внешним ключем таблицы SELLERS ID), то в результирующем отношении остается один домен ID.
Синтаксис операции:
PRODUCTS ⋈ SELLERS;
Получится такое отношение:
| PRODUCTS.ID | NAME | COMPANY | PRICE | SELLER |
| 123 | Печеньки | ООО ”Темная сторона” | 190 | OOO “Дарт” |
| 156 | Чай | ООО ”Темная сторона” | 60 | ОАО ”Ведро” |
| 235 | Ананасы | ОАО ”Фрукты” | 100 | ЗАО “Овоще База” |
| 623 | Томаты | ООО ”Овощи” | 130 | ОАО ”Фирма” |
Пересечение и вычитание.
Результатом операции пересечения будет отношение, состоящее из кортежей, полностью входящих в состав обоих отношений.Результатом вычитания будет отношение, состоящее из кортежей, которые являются кортежами первого отношения и не являются кортежами второго отношения.
Данные операции аналогичны таким же операциям над множествам, так что, я думаю, нет необходимости подробно их расписывать.
Источники информации
- Основы использования и проектирования баз данных - В. М. Илюшечкин
- курс лекций Introduction to Databases - Jennifer Widom, Stanford University
Буду благодарен за аргументированные замечания
Реляционная алгебра, как нетрудно догадаться, – это особая разновидность алгебры, в которой все операции производятся над реляционными моделями данных, т. е. над отношениями.
В табличных терминах отношение включает в себя строки, столбцы и строку – заголовок столбцов. Поэтому естественными унарными операциями являются операции выбора определенных строк или столбцов, а также смены заголовков столбцов – переименования атрибутов.
1. Унарная операция выборки
Первой унарной операцией, которую мы рассмотрим, является операция выборки – операция выбора строк из таблицы, представляющей отношение, по какому-либо принципу, т. е. выбор строк-кортежей, удовлетворяющих определенному условию или условиям.
Оператор выборки обозначается ? <P >, условие выборки – P <S >, т. е., оператор ? берется всегда с определенным условием на кортежи P , а само условие P записывается зависящим от схемы отношения S . С учетом всего этого сама операция выборки над схемой отношения S применительно к отношению r
? <P >r (S ) ? ? <P >r = {t (S ) |t ? r & P <S >t } = {t (S ) |t ? r & IfNull (P <S >t , False };
Результатом этой операции будет новое отношение с той же схемой отношения S
, состоящее из тех кортежей t
(S
) исходного отношения-операнда, которые удовлетворяют условию выборки Pt
. Понятно, что для того, чтобы применить какое-то условие к кортежу, необходимо подставить значения атрибутов кортежа вместо имен атрибутов.
Чтобы лучше понять принцип работы этой операции, приведем пример. Пусть дана следующая схема отношения:
S : Сессия (№ зачетной книжки, Фамилия, Предмет, Оценка).
Условие выборки возьмем такое:
P <S > = (Предмет = ‘Информатика’ and Оценка > 3).
Нам необходимо из исходного отношения-операнда выделить те кортежи, в которых содержится информация о студентах, сдавших предмет «Информатика» не ниже, чем на три балла.
Пусть также дан следующий кортеж из этого отношения:
t 0 (S ) ? r (S
Применяем наше условие выборки к кортежу t 0 , получаем:
P
t0 = (‘Базы данных’ = ‘Информатика’ and 5 > 3);
На данном конкретном кортеже условие выборки не выполняется.
А вообще результатом этой конкретной выборки
? <Предмет = "Информатика" and Оценка > 3 > Сессия
будет таблица «Сессия», в которой оставлены строки, удовлетворяющие условию выборки.
2. Унарная операция проекции
Еще одна стандартная унарная операция, которую мы изучим, – это операция проекции. Операция проекции – это операция выбора столбцов из таблицы, представляющей отношение, по какому-либо признаку. А именно машина выбирает те атрибуты (т. е. буквально те столбцы) исходного отношения-операнда, которые были указаны в проекции.
Оператор проекции
обозначается [S"
] или ?
t (S ) [S’ ] = {t (a )|a ? def (t ) ? S ’}, S " ?S .
Важно заметить, что дубликаты кортежей из результата исключаются, т. е. в таблице, представляющей новое, результирующее отношение повторяющихся строк не будет.
С учетом всего вышесказанного, операция проекции в терминах систем управления базами данных будет выглядеть следующим образом:
? <S" >r (S ) ? ? <S’ >r ? r (S ) [S ’] ? r [S" ] = {t (S ) [S’ ] | t ? r };
Рассмотрим пример, иллюстрирующий принцип работы операции выборки.
Пусть дано отношение «Сессия» и схема этого отношения:
S : Сессия (№ зачетной книжки, Фамилия, Предмет, Оценка);
Нас будут интересовать только два атрибута из этой схемы, а именно «№ зачетной книжки» и «Фамилия» студента, поэтому подсхема S" будет выглядеть следующим образом:
S" : (№ зачетной книжки, Фамилия).
Нужно исходное отношение r (S ) спроецировать на подсхему S" .
t 0 (S ) ? r (S ): {(№ зачетной книжки: 100), (Фамилия: ‘Иванов’), (Предмет: ‘Базы данных’), (Оценка: 5)};
Значит, проекция этого кортежа на данную подсхему S" будет выглядеть следующим образом:
t 0 (S ) S" : {(№ зачетной книжки: 100), (Фамилия: ‘Иванов’)};
Если говорить об операции проекции в терминах таблиц, то проекция Сессия [№ зачетной книжки, Фамилия] исходного отношения – это таблица Сессия, из которой вычеркнуты все столбцы, кроме двух: № зачетной книжки и Фамилия. Кроме того, все дублирующиеся строки также удалены.
3. Унарная операция переименования
И последняя унарная операция, которую мы рассмотрим, – это операция переименования атрибутов . Если говорить об отношении как о таблице, то операция переименования нужна для того, чтобы поменять названия всех или некоторых столбцов.
Оператор переименования выглядит следующим образом: ?>, здесь ? - функция переименования .
Эта функция устанавливает взаимно-однозначное соответствие между именами атрибутов схем S и S, где соответственно S - схема исходного отношения, а S - схема отношения с переименованными атрибутами. Таким образом, оператор ? <?> в применении к отношению r (S ) дает новое отношение со схемой S , состоящее из кортежей исходного отношения только с переименованными атрибутами.
Запишем операцию переименования атрибутов в терминах систем управления базами данных:
? <? > r (S ) ? ? <? >r = {? <? > t (S )| t ? r };
Приведем пример использования этой операции:
Рассмотрим уже знакомое нам отношение Сессия, со схемой:
S: Сессия (№ зачетной книжки, Фамилия, Предмет, Оценка);
Введем новую схему отношения S, с другими именами атрибутов, которые мы бы хотели видеть вместо имеющихся:
S:
Например, заказчик базы данных захотел в вашем готовом отношении видеть другие названия. Чтобы воплотить в жизнь этот заказ, необходимо спроектировать следующую функцию переименования:
? : (№ зачетной книжки, Фамилия, Предмет, Оценка) > (№ ЗК, Фамилия, Предмет, Балл);
Фактически, требуется поменять имя только у двух атрибутов, поэтому законно будет записать следующую функцию переименования вместо имеющейся:
? : (№ зачетной книжки, Оценка) > (№ ЗК, Балл);
t 0 (S ) ? r (S ): {(№ зачетной книжки: 100), (Фамилия: ‘Иванов’), (Предмет: ‘Базы данных’), (Оценка: 5)};
Применим оператор переименования к этому кортежу:
? t 0 (S ): {(№ ЗК: 100), (Фамилия: ‘Иванов’), (Предмет: ‘Базы данных’), (Балл: 5)};
Итак, это один из кортежей нашего отношения, у которого переименовали атрибуты.
В табличных терминах отношение
? < № зачетной книжки, Оценка > «№ ЗК, Балл > Сессия -
это новая таблица, полученная из таблицы отношения «Сессия», переименованием указанных атрибутов.
4. Свойства унарных операций
У унарных операций, как и у любых других, есть определенные свойства. Рассмотрим наиболее важные из них.
Первым свойством унарных операций выборки, проекции и переименования является свойство, характеризующее соотношение мощностей отношений. (Напомним, что мощность – это количество кортежей в том или ином отношении.) Понятно, что здесь рассматривается соответственно отношение исходное и отношение, полученное в результате применения той или иной операции.
Заметим, что все свойства унарных операций следуют непосредственно из их определений, поэтому их можно легко объяснить и даже при желании вывести самостоятельно.
1) соотношение мощностей:
а) для операции выборки: | ? <P >r |? |r |;
б) для операции проекции: | r [S" ] | ? |r |;
в) для операции переименования: | ? <? >r | = |r |;
Итого, мы видим, что для двух операторов, а именно для оператора выборки и оператора проекции, мощность исходных отношений – операндов больше, чем мощность отношений, получаемых из исходных применением соответствующих операций. Это происходит потому, что при выборе, сопутствующему действию этих двух операций выборки и проекции, происходит исключение некоторых строк или столбцов, не удовлетворивших условиям выбора. В том случае, когда условиям удовлетворяют все строки или столбцы, уменьшения мощности (т. е. количества кортежей) не происходит, поэтому в формулах неравенство нестрогое.
В случае же операции переименования, мощность отношения не изменяется, за счет того, что при смене имен никакие кортежи из отношения не исключаются;
2) свойство идемпотентности:
а) для операции выборки: ? <P > ? <P >r = ? <P >;
б) для операции проекции: r [S’ ] [S’ ] = r [S" ];
в) для операции переименования в общем случае свойство идемпотентности неприменимо.
Это свойство означает, что двойное последовательное применение одного и того же оператора к какому-либо отношению равносильно его однократному применению.
Для операции переименования атрибутов отношения, вообще говоря, это свойство может быть применено, но обязательно со специальными оговорками и условиями.
Свойство идемпотентности очень часто используется для упрощения вида выражения и приведения его к более экономичному, актуальному виду.
И последнее свойство, которое мы рассмотрим, – это свойство монотонности. Интересно заметить, что при любых условиях все три оператора монотонны;
3) свойство монотонности:
а) для операции выборки: r 1 ? r 2 ? ? <P > r 1 ? ? <P >r 2 ;
б) для операции проекции: r 1 ? r 2 ? r 1 [S" ] ? r 2 [S" ];
в) для операции переименования: r 1 ? r 2 ? ? <? >r 1 ? ? <? >r 2 ;
Понятие монотонности в реляционной алгебре аналогично этому же понятию из алгебры обычной, общей. Поясним: если изначально отношения r 1 и r 2 были связаны между собой таким образом, что r ? r 2 , то и после применения любого их трех операторов выборки, проекции или переименования это соотношение сохранится.
Реляционная алгебра - это язык операций, выполняемых над отношениями - таблицами реляционной базы данных. Операции реляционной алгебры позволяют на основе одного или нескольких отношений создавать другое отношение без изменения самих исходных отношений. Полученное другое отношение обычно не записывается в базу данных, а существует в результате выполнения SQL-запроса - массиве, создаваемом функциями для работы с базами данных в языках программирования. Для каждой операции реляционной алгебры будет дана её реализация в виде запросов на языке SQL.
Рассмотрим операции реляционной алгебры. Чтобы Вам не отвлекаться на содержание таблиц не Ваших баз данных, таких как "Продукты", "Водители", "сливы", "груши", "чай", "кофе", Владимиры, Сергеи и т.п. будем выполнять операции над отношениями (таблицами) с абстрактными данными, такими как R1, R2 (названия таблиц - отношений) и т.д. и А1, А2, А3 (названия атрибутов - столбцов) и h15, w11 и т.п. (содержание записей таблиц базы данных).
Приоритеты выполнения операций реляционной алгебры (в порядке убывания пунктов списка, а в одном пункте - операции с равными приоритетами):
- селекция, проекция
- декартово произведение, соединение, пересечение, деление
- объединение, разность.
Операция выборки
Операция выборки работает с одним отношением и определяет результирующее отношение R , которое содержит только те кортежи (или строки, или записи), отношения , которые удовлетворяют заданному условию (предикату P ).
Таким образом, операция выборки - унарная операция - и записывается следующим образом:
где P - предикат (логическое условие).
Запрос SQL
Теперь посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. В таблице ниже дано одно отношение, с которым работает эта операция.
| R3 | |||
| A1 | A2 | A3 | A4 |
| 3 | hh | yl | ms |
| 4 | pp | a1 | sr |
| 1 | rr | yl | ms |
Просматриваем столбец А3 и устанавливаем, что предикату A3>"d0" удовлетворяют записи в первой и третьей строках исходного отношения (так как номер буквы y в алфавите больше номера буквы d). В результате получаем следующее новое отношение, в котором две строки:
| R | |||
| A1 | A2 | A3 | A4 |
| 3 | hh | yl | ms |
| 1 | rr | yl | ms |
Комбинировать всевозможные логические условия для выборок Вам поможет материал "Булева алгебра (алгебра логики)" .
Запрос SQL
SELECT A1, A2, A3 from R1 UNION SELECT A1, A2, A3 from R2
Теперь посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Теперь даны два отношения, так как операция объединения - бинарная операция:
| R1 | R2 | |||||
| A1 | A2 | A3 | A1 | A2 | A3 | |
| Z7 | aa | w11 | X8 | pp | k21 | |
| B7 | hh | h15 | Q2 | ee | h15 | |
| X8 | pp | w11 | X8 | pp | w11 | |
Объединяем строки первого и второго отношения и видим, что третья строка, которая является третьей и в первом, и во втором отношении - идентичны, поэтому её включаем в новое отношение только один раз. Получаем следующее отношение:
| R | ||
| A1 | A2 | A3 |
| Z7 | aa | w11 |
| B7 | hh | h15 |
| X8 | pp | w11 |
| X8 | pp | k21 |
| Q2 | ee | h15 |
Важно следующее: операция объединения может быть выполнена только тогда, когда два отношения обладают одинаковым числом и названиями атрибутов (столбцов), или, говоря формально, совместимы по объединению.
Операция пересечения
Результатом пересечения двух множеств (отношений) А и В () будет такое множество (отношение) С, которое включает в себя те и только те элементы, которые есть и во множестве А, и во множестве В. Операция пересечения реляционной алгебры идентична операции .
Запрос SQL
SELECT A1, A2, A3 from R1 INTERSECT SELECT A1, A2, A3 from R2
В некоторых диалектах SQL отсутствует ключевое слово INTERSECT. Его заменой, например, в MySQL и других, является INNER JOIN. О том, как работает оператор SQL JOIN вообще и его разновидности INNER JOIN, LEFT OUTER JOIN, RIGHT OUTER JOIN и FULL OUTER JOIN - на уроке SQL JOIN - соединение таблиц базы данных .
Запрос MySQL
Теперь посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Вновь даны два отношения R1 и R2:
| R1 | R2 | |||||
| A1 | A2 | A3 | A1 | A2 | A3 | |
| Z7 | aa | w11 | X8 | pp | k21 | |
| B7 | hh | h15 | Q2 | ee | h15 | |
| X8 | pp | w11 | X8 | pp | w11 | |
Просматриваем все записи в двух отношениях, и обнаруживаем, что и в первом, и во втором отношении есть одна строка - та, которая является третьей и в первом, и во втором отношении. Получаем новое отношение:
| R | ||
| A1 | A2 | A3 |
| X8 | pp | w11 |
Операция разности
Разность двух отношений R1 и R2 () состоит из кортежей (или записей, или строк), которые имеются в отношении R1, но отсутствуют в отношении R2. Отношения R1 и R2 должны быть совместимы по объединению. Операция разности реляционной алгебры идентична операции .
Запрос SQL
SELECT
A1, A2, A3 from R2 EXCEPT
SELECT
A1, A2, A3 from R1
Установим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Вновь даны два отношения R1 и R2:
| R1 | R2 | |||||
| A1 | A2 | A3 | A1 | A2 | A3 | |
| Z7 | aa | w11 | X8 | pp | k21 | |
| B7 | hh | h15 | Q2 | ee | h15 | |
| X8 | pp | w11 | X8 | pp | w11 | |
Из отношения R2 исключаем строку, которая есть также в отношении R2 - третью - и получаем новое отношение:
| R | ||
| A1 | A2 | A3 |
| X8 | pp | w11 |
| Q2 | ee | h15 |
Операция декартова произведения
Операция декартова произведения () определяет новое отношение R, которое является результатом конкатенации каждого кортежа отношения R1 с каждым кортежем отношения R2.
Запрос SQL
SELECT * from R3, R4
Установим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Даны два отношения R3 и R4:
| R3 | R4 | |||||
| A1 | A2 | A3 | A4 | A5 | A6 | |
| 3 | hh | yl | ms | 3 | hh | |
| 4 | pp | a1 | sr | 4 | pp | |
| 1 | rr | yl | ms | |||
В новом отношении должны присутствовать все атрибуты (столбцы) двух отношений. Сначала первая строка отношения R3 сцепляется с каждой из двух строк отношения R4, затем вторая строка отношения R3, затем третья. В результате должно получиться 3 Х 2 = 6 кортежей (строк). Получаем такое новое отношение:
| R | |||||
| A1 | A2 | A3 | A4 | A5 | A6 |
| 3 | hh | yl | ms | 3 | hh |
| 3 | hh | yl | ms | 4 | pp |
| 4 | pp | a1 | sr | 3 | hh |
| 4 | pp | a1 | sr | 4 | pp |
| 1 | rr | yl | ms | 3 | hh |
| 1 | rr | yl | ms | 4 | pp |
Как правило, системы баз данных оснащены языком запросов, которые могут помочь его пользователям запрашивать экземпляры. Существует два таких типа - реляционная алгебра и реляционное исчисление. Первый является процедурным который принимает экземпляры отношений как входные данные и выводит примеры отношений как выходные. Использует для этого унарные или двоичные исчисления. Реляционная алгебра выполняется рекурсивно, а рассматриваются как отношения.
Декартово произведение (Χ)
Объединяет информацию двух разных отношений в одну.
Обозначения - r Χ s,
где r и s - отношения, а их выход будет определяться как
r Χ s = {qt | q ∈ r и t ∈ s}.
Вывод. Устанавливает отношение, которое показывает все книги и статьи, написанные с помощью учебника.
Переименовать операцию (ρ).
Отношением реляционной алгебры являются результаты, но без какого-либо имени. Операция переименования позволяет изменить выходное значение, обозначается маленькой греческой буквой ρ .
Обозначение - ρ x (E),
где результат выражения E сохраняется с именем x.
Дополнительные операции:
- установить пересечение;
- присваивание;
- естественное соединение.
Реляционное исчисление
Является непроцедурным язык запросов, то есть он говорит, что делать, но не объясняет, как это реализовать. Реляционное исчисление существует в двух формах:
- корреляционное исчисление кортежа;
- фильтрация переменных диапазонов.
Обозначения - T/Состояние: возвращает все кортежи T, удовлетворяющие условию. Результат. Возвращает кортежи с именем. TRC можно количественно определить. Можно использовать экзистенциальные (∃) и универсальные кванторы (∀). Вывод. Вышеприведенный запрос даст тот же результат, что и предыдущий.
Доменное реляционное исчисление DRC
Переменная фильтрации использует домен атрибутов вместо целых значений кортежа (как это сделано в TRC, упомянутом выше).
Обозначения - {a 1 , a 2 , a 3 , ..., a n | P (a 1 , a 2 , a 3 , ..., a n)},
где a1, a2 - атрибуты, а P обозначает формулы, построенные внутренними значениями.
Вывод. Устанавливает статью, страницу и тему из отношения TutorialsPoint, где subject является базой данных.
Подобно TRC, DRC также может быть записана с использованием экзистенциальных и универсальных кванторов. ДРК также включает операторов реляционной алгебры. Сила выражения вычисления, исчисления и корреляции отношений между точками эквивалентна.
Вариации и схемы реляционного исчисления и алгебры
Модель ER, когда она концептуализирована на диаграммах, дает хороший обзор сущностных отношений, которые легче понять. Схематические изображения могут быть сопоставлены с реляционной схемой, т. е. их можно создать совместно друг с другом. Невозможно импортировать все ограничения ER в реляционную модель, но может быть сгенерирована приблизительная структура. Существует несколько процессов и алгоритмов, доступных для преобразования диаграмм в эту систему. Некоторые из них автоматизированы, а другие создаются вручную. Диаграммы ER в основном состоят из следующих критериев:
- сущности и ее атрибутов;
- связи, которая является ассоциацией между вышеупомянутыми значениями.
Сопоставление объектов и отношений происходят разными путями и схемами. К примеру, сущность - это объект реального мира с некоторыми атрибутами. Процесс сопоставления, алгоритм следующий:
- создать таблицу для каждого объекта;
- атрибуты должны стать полями таблиц с соответствующими типами данных;
- объявить первичный ключ.
Отношение - это ассоциация между сущностями. Процесс составления следующий:
- создать таблицу для отношений;
- добавить первичные ключи всех участвующих сущностей в качестве полей таблицы с соответствующими типами данных;
- если отношение имеет какой-либо атрибут, установить каждый атрибут в качестве поля таблицы;
- объединить первичный ключ, составляющий все остальные для участвующих объектов;
- указать все ограничения внешнего ключа.
Отображение слабых наборов и иерархических объектов происходит по определенной системе. Прежде всего, необходимо понимать сущностные основы и значений. Слабый набор объектов - это тот, который не имеет никакого первичного ключа, связанного с ним. Процесс отображения следующий:
- создать таблицу для слабого набора объектов;
- добавить все атрибуты в схему как поле;
- указать первичный ключ для идентификации;
- установить все ограничения внешнего ключа.
Отображение иерархических объектов основано на специализации или обобщении языка реляционной алгебры происходит в виде последовательных сущностей. Алгоритм следующий:
- создать таблицы для всех объектов более высокого нижнего уровня;
- добавить первичные ключи;
- на низком уровне реализовать все другие атрибуты объектов нижнего уровня;
- объявить первичные ключи таблицы;
- установить ограничения внешнего ключа.
Существующие варианты для описания, хранения, изменения информации
SQL - это язык программирования для реляционных баз данных. Он разработан над алгеброй и корреляционным исчислением кортежей. SQL поставляется в виде пакета со всеми основными дистрибутивами СУБД. Содержит как данные, так и языки манипулирования ими. Используя свойства определения данных SQL реляционной алгебры, можно спроектировать и изменить схему базы, тогда как свойства управления и корректировки, а также изменения данных позволяют хранить и извлекать установленную в систему информацию. Использует следующий набор команд для определения структуры и системы:
- создает новые таблицы и представления из СУБД.
- выбрасывает команды.
- изменяет схему базы данных.
- эта команда добавляет атрибут в объект типа string.
SQL оснащен языком манипулирования данными (DML). Он изменяет экземпляр базы, вставляя, обновляя и удаляя информацию. DML отвечает за изменение всех данных. SQL содержит следующий набор команд в разделе DML:
- SELECT - это одна из основных команд запроса. Он аналогичен проекционной операции реляционной алгебры. Он выбирает атрибуты на основе условия, описанного в приложении WHERE.
- FROM - этот раздел принимает имя в качестве аргумента, из которого атрибуты должны быть выбраны/спроецированы. В случае если дано более одного названия, этот пункт соответствует декартовому произведению.
- WHERE - этот раздел определяет предикат или условия, которые должны соответствовать, чтобы квалифицировать проецирующийся атрибут.
Существуют также команды:
- вставка;
- изменение значений;
- удаление.
Создание запросов реляционной алгебры
При построении поиска задача состоит в том, чтобы найти структуру операций, которая приведет к правильному выводу. Основными операциями реляционной алгебры являются простые операции с одним или двумя отношениями в качестве операндов. Комбинированные эффекты последовательности определяют конечный результат. Поскольку система реляционной алгебры в базах данных довольно проста, многие промежуточные результаты могут быть получены до достижения конечного вывода, они также используются в качестве операндов, которые производят новые получаемые данные.
Для большинства операторов порядок запросов и их выполнения не имеет значения, а это означает, что один и тот же вывод может быть достигнут путем формирования и комбинирования промежуточных данных по-разному. На практике поиски в базе довольно легки. Система выполнения операций и промежуточных результатов определяется оптимизатором запросов. При формировании вопросов, требований нужно
сначала выбрать, какие отношения необходимы для достижения ответа, а затем указать операции и промежуточные результаты. Структура запроса реляционной алгебры в базе данных с результатами может быть представлена в виде диаграммы. Оптимизаторы требований пытаются организовать максимально эффективное выполнение. На практике это обычно означает, что они стараются как можно быстрее минимизировать промежуточные результаты. В этом помогут распространенные примеры реляционной алгебры.
Информация об автомобилях модели 1996 года, где в ходе инспекции на 1999 год обнаружены недостатки.
Сначала выводится информация о машинах, чтобы понимать значения всех атрибутов отношения. Информация об инспекциях хранится в таблице «Проверка», и, если обнаружены неисправности, они регистрируются в таблице «Проблема». Таким образом, нужны эти три таблицы, чтобы получить нужную информацию.
Интересны только автомобили 1996 года. Модельный ряд автомобиля представлен как значение установленного атрибута в строке таблицы информации о машине. Первый промежуточный результат состоит из кортежей, представляющих варианты 1996 года.
Таким образом, нужны только строки, которые охватывают этот период. Необходимо использовать выделение для их извлечения. Теперь есть автомобили и инспекции, которые требовались. Затем строки соединяются с помощью операции объединения. К ним должен быть подключен общий номер регистра, поскольку он является единственным общим столбцом, используется естественное соединение.
Чтобы выяснить, были ли обнаружены неисправности в ходе проверок, необходимо связать строки проблем с проверкой. После подключения контрольных рядов к автомобилям, можно подключить этот результат к таблице неисправностей. Присоединение должно основываться на общем регистрационном номере и проверенной дате. Это единственные общие столбцы в таблицах, поэтому используется естественное соединение.
Варианты исчислений без промежуточных результатов
Необходимая информация: Имя водителя для модельного года 1995 года или более старые автомобили, которые не были проверены на 2000 год. Имя находится в таблице "Водитель". Правоохранительные органы описаны в таблице «Инспекция и автомобили в столовой машине». Таким образом, нужны эти три таблицы. Во-первых, необходимо узнать автомобили, которые не были осмотрены на 2000 год. Невозможно решить эту проблему, используя только инспекцию, указанную в таблице, поскольку она содержит данные об этих проверках, которые были сделаны, а не о тех, что не были реализованы. Эта проблема решается путем поиска дополняющих автомобилей, которые проверяются до 2000 года. На самом деле нужны только их регистрационные номера.
Существуют и другие примеры помимо указанных выше, которые показывают, каким образом можно изменить или найти какую-либо информацию. Варианты запросов могут быть оптимизированными при помощи специальных операций. По сути, чтобы поиск и нахождение данных были наиболее легкими и простыми, существует реляционная модель исчисления.
Где закреплена и защищена информация
Алгебры хранится в форматах файлов, содержащих записи. На физическом уровне фактическая информация закреплена в электромагнитном формате на каком-либо устройстве. Эти устройства хранения могут быть разделены на три категории:
- Первичное. К этой категории относится память, которая напрямую доступна для ЦП. Регистры, быстрая память (кэш) и основная (ОЗУ) напрямую доступны для центральной, так как все они размещены на материнской плате или чипсете. Это хранилище, как правило, очень маленькое, сверхбыстрое и неустойчивое. Для поддержания состояния требуется постоянный источник питания. В случае сбоя все его данные теряются.
- Вторичное. Используется для хранения информации для будущего использования или резервного копирования. Включает в себя устройства памяти, которые не являются частью чипсета или материнской платы процессора, например магнитные диски, оптические диски (DVD, CD и т. д.), жесткие диски, флэш-накопители и магнитные ленты.
- Третичное. Используется для хранения огромных объемов данных. Поскольку такие запоминающие устройства являются внешними по отношению к компьютерной системе, они являются самыми медленными по скорости. Эти гаджеты хранения в основном используются для резервного копирования всей системы. Оптические диски и магнитные ленты широко используются в качестве третичного хранилища.
Для эффективности запроса важны специальные операции реляционной алгебры.
Структура хранения
Компьютерная система имеет четко определенную иерархию памяти. ЦП имеет прямой доступ к основной системе, а также к встроенным регистрам. Время доступа к основной памяти, очевидно, меньше, чем скорость процессора. Чтобы минимизировать это несоответствие, вводится кэш. Кэш-память обеспечивает самое быстрое время доступа и содержит данные, которые наиболее часто обращаются к ЦП.
Память с самым быстрым доступом является самой дорогостоящей. Большие устройства хранения данных обеспечивают небольшую скорость, и они дешевле, однако они могут хранить огромные объемы данных по сравнению с регистром процессора или кэш-памятью.
Магнитные и жесткие диски являются наиболее распространенными вторичными устройствами хранения в современных компьютерных системах. Они называются магнитными, состоят из металлической основы. Эти диски размещаются вертикально на шпинделе. Головка чтения/записи перемещается между ними и используется для намагничивания или снятия такого пятна под ним. Его можно распознать как 0 (ноль) или 1 (один).
Жесткие диски отформатированы в четко определенном порядке для эффективного хранения данных. На нем много концентрических кругов, называемых дорожками. Каждый трек далее разделяется на сектора, где обычно хранится 512 байт данных.
Файловые операции
Операции над системой языка реляционной алгебры и ее базы данных можно в целом классифицировать по двум категориям:
- обновление;
- поиск.
Первая категория изменяет значения данных путем вставки, удаления или обновления. С другой стороны, операции поиска не редактируют информацию, а извлекают ее после необязательной условной фильтрации. В обоих типах операций отбор играет значительную роль. Помимо создания и удаления файла может быть несколько операций, которые могут в них выполняться:
- Открыть - существует в одном из двух режимов чтения или записи. В первом случае операционная система не позволяет никому изменять данные. Другими словами, данные только считываются. Файлы, открытые в режиме чтения, могут совместно использоваться несколькими объектами. Режим записи позволяет изменять данные. Файлы могут быть прочитаны, но не могут использоваться совместно.
- Закрыть - это самая важная операция с точки зрения операционной системы, так как она удаляет все блокировки (если в режиме общего доступа), сохраняет данные (если они изменены) на вторичный носитель и освобождает все буферы и обработчики, связанные с файлом.
- Индексирование - это метод структуры информации для эффективного извлечения записей из файлов системы на основе некоторых атрибутов, где была выполнена эта система. Определяется на основе атрибутов.
Индексирование может быть следующего типа:
- Первичный определяется в файле упорядоченных данных. Файл информации упорядочен в ключевом поле.
- Вторичный индекс сгенерирован из поля, которое является ключом-кандидатом, и имеет уникальное значение в каждой записи или не ключ с повторяющимися значениями.
- Кластеризация определяется в упорядоченном файле данных, в не ключевом поле.
Система управления базами данных или СУБД относится к технологии хранения и извлечения информации пользователей с максимальной эффективностью наряду с соответствующими мерами безопасности. Детальное рассмотрение этого вопроса приводит к выводу, что реляционная алгебра является языком операторов, которые применяют отношения в качестве аргументов и возвращают их в результате.
Начинать изучать SQL лучше всего с азов реляционных баз данных. Я дам пояснение что такое реляционная база данных, что такое отношение и какие операции над ними можно производить.
Поехали …
Что такое SQL?
SQL (Structured Query Language)
– структурированный язык запросов, универсальный компьютерный язык, применяемый для создания, модификации и управление данными в реляционных базах данных
Что такое реляционная база данных?
Это совокупность взаимосвязанных данных хранящихся в виде отношений
Что такое отношения?
Отношение это некое множество картежей
Что такое кортеж?
Картеж это определенный набор элементов, причем каждый элемент набора принадлежит некоторому множеству (можно сказать типу элемента). Если говорить проще, то кортеж это список элементов, между которыми есть связь или как говорят, есть отношение . Представить кортеж можно с помощью графа или таблицы состоящий из одной строки.
Продемонстрирую кортеж из двух элементов с помощью графа:
Вершины графа это элементы их некоторого множества, в данном случае, это элемент а1 из множества А и элемент b1 из множества B . Ребро между вершинами обозначает связь между элементами или как говорят элемент а1 находится в отношение с b1 .
Продемонстрирую этот же кортеж с помощью таблицы:
Номер 1 у а1 и b1 , был выбран произвольно.
Итак, мы добрались до элементарного кирпичика, т.е. до кортежа , начнем разматывать нашу логику обратно, что бы понять, что такое реляционная база данных и SQL .
Как я сказал, отношение это множество кортежей , причем ограниченное (если отойти от теории). Представить отношения можно в виде матрицы, графа, таблицы.
Продемонстрирую, как представить отношение в виде графа:
На графике видно, что есть несколько кортежей, причем какой кортеж первый, а какой второй и третий не важно , это просто множество кортежей. В множестве нет такого понятия «первый», «второй» и «третий», это всё сразу и очередность не важна.
Продемонстрирую, как представить отношение в виде таблицы:
Последовательность строк или кортежей в таблице не важна , из графа я их взял в произвольном порядке.
Также важно заметить, что последовательность столбцов тоже не важна , если мы поменяем их местами, то с точки зрения теории множеств, отношение останется не низменным . В этом как раз и заключается отрицательная сторона таблицы, как способа визуализации отношения, ведь нам психологически трудно будет назвать таблицы равными, если у них в разной последовательности следуют столбы и строки.
Как было сказано в самом начале, что реляционная база данных это совокупность взаимосвязанных данных хранящихся в виде отношений . Если представлять отношения в виде таблиц, то реляционная БД это некий набор взаимосвязанных таблиц . Выходит SQL это язык создания, модификации и управление таблицами в реляционной БД .
Итак, с логической цепочкой мы разобрались: SQL, реляционная БД, отношения, кортеж..Теперь мы затронем язык SQL, т.е. тему манипулирования с отношениями, важно разобраться какие операции мы можем проводить над отношениями .
Все операции продемонстрировать не возможно, в связи с их большим количеством, приведу только базовые:
1. Селекция (другие имена операции — выборка, ограничение)
Операция «селекция» или «выборка» выполняется над одним отношением , смысл его заключается в том, что по заданному условию осуществляется выборка подмножества кортежей . Результат операции – отношение отличающиеся от исходного меньшим числом кортежей . Пример:
Пусть есть отношение, назовем его «исходная таблица №1»:
Результат «выборки» из исходной таблицу №1, при условии что А=а3
На языке SQL:
синтаксис — SELECT * FROM имя_таблицы WHERE имя_столбца=значение
SELECT * FROM исходная_таблица WHERE А=a3
2. Проекция
Операция «проекция» выполняется над одним отношением , в результате неё формируется новое отношение с указанными столбцами таблицы .
Например, есть отношение, назовем ее «исходная таблица №2»:
Произведем над данным отношением операцию «проекция» по атрибутам А и С , результат:
В результате мы получили два одинаковых картежа, в отношение такого быть не может, поэтому сократим их (в СУБД сокращения происходят автоматически):
Выходит, при проекции у нас может сокращаться число кортежей , это бывает, за ошибку это считать не надо .
На языке SQL:
синтаксис — SELECT список_столбцов FROM имя_таблицы
реализация для данного случая — SELECT А,С FROM исходная_таблица_№2
3. Естественное соединение
Операция «естественное соединение » выполняется над двумя логическими связанными отношениями , в результате неё формируется новое отношение со столбцами первого и второго отношения и с кортежами, которые получаются в результате соединения каждого кортежа первого и второго отношения . На примере должно быть более понятно, пусть есть два отношения, назовем их исходная таблица №3.1 и исходная таблица №3.2:
Исходная таблица №3_1
Исходная таблица №3_2
Проведем операцию «соединения» первого и второго отношения, результат:
Интересно заметить, что мы получили исходное отношение из раздела «2. Проекция», последовательность столбцов в отношение значения не имеет.
На языке SQL:
реализация для данного случая — SELECT исходная_таблица_№3_1.*, исходная таблица №3_2.В FROM исходная_таблица_№3_1, исходная таблица №3_2 WHERE исходная таблица №3_1.A= исходная таблица №3_2.A
4. Объединение
Операция «объединение» выполняется над двумя отношениями имеющих одинаковый набор столбцов и тип данных в этих столбцах , результат операции новое отношение, которое включает в себя все кортежи «первого» и «второго» отношения (повторяющиеся сокращаются).
Исходная таблица №4_1
Исходная таблица №4_2
Произведем операцию «объединения» отношения №4.1 и отношения №4.2 , результат:
На языке SQL:
синтаксис — SELECT список_столбцов_таблицы1 FROM таблица1 UNION SELECT список_столбцов_таблицы2 FROM таблица2
реализация для данного случая — SELECT А,В FROM исходная_таблица_№4_1 UNION SELECT А,В FROM исходная_таблица_№4_2
5. Пересечение
Операция «пересечение» выполняется , результат операции новое отношение, которое включает в себя одинаковые кортежи «первого» и «второго» отношения .
Пример, пусть есть два отношения:
Исходная таблица №5_1
Исходная таблица №5_2
Произведем операцию «пересечения» с данными отношениями, результат:
Т.е. в результирующее отношение, попали повторяющиеся кортежи из «первого» и «второго» отношения.
На языке SQL:
синтаксис — SELECT одна_из_таблиц.столбец1, одна_из_таблиц.столбец2, … FROM таблица1,таблица2 WHERE таблица1.столбец1=таблица2.столбец1 AND таблица1.столбец2= таблица2.столбец2 AND …
реализация для данного случая –
SELECT исходная_таблица_№5_1.А, исходная_таблица_№5_1.В FROM исходная_таблица_№5_1, исходная_таблица_№5_2 WHERE исходная_таблица_№5_1.А = исходная_таблица_№5_2.А AND исходная_таблица_№5_1.В = исходная_таблица_№5_2.В
6. Вычитание (разность)
Операция «вычитание» выполняется над двумя отношениями имеющими одинаковый набор столбцов и тип данных в этих столбцах , результат операции новое отношение, которое включает в себя кортежи «первого» отношения отличные от кортежей «второго» отношения , на примере думаю должно быть более понятно.
Пример, пусть есть два отношения:
Исходная таблица №6_1
Исходная таблица №6_2
Произведем операцию «разность» , т.е. от исходной таблицы №6_1 отнимем исходную таблицу №6_2, результат:
Т.е. результирующее отношение, это «первое» отношение без повторяющихся кортежей «второго» отношения.
На языке SQL:
реализация для данного случая – SELECT исходная_таблица_№6_1.А, исходная_таблица_№6_1.В FROM исходная_таблица_№6_1 WHERE NOT EXISTS (SELECT исходная_таблица_№6_2.А, исходная_таблица_№6_2.В FROM исходная_таблица_№6_2
WHERE исходная_таблица_№6_2.А= исходная_таблица_№6_1.А AND исходная_таблица_№6_2.В= исходная_таблица_№6_1.В)
7. Декартово произведение
Декартово произведение выполняется над двумя произвольными отношениями, результат операции новое отношение с количество столбцов равному сумме количества столбцов «первого» и «второго» отношения, а количество строк равному произведение количеству строк «первого» и «второго» отношения . Кортежи результирующего отношение, если говорить по-простому, получаются путем комбинации каждого кортежа «первого» отношения с кортежами «второго» отношения.
Пример, пусть есть два произвольных отношения:
Исходная таблица №7_1
Исходная таблица №7_2
Произведем «декартово произведение» данных двух отношений, результат:
На языке SQL:
реализация для данного случая – SELECT исходная_таблица_№7_1.А, исходная_таблица_№7_1.В, исходная_таблица_№7_2.А, исходная_таблица_№7_2.В FROM исходная_таблица_№7_1, исходная_таблица_№7_2
Мы разобрались с основными операции над отношениями и напоследок теоретической части поста разберемся что такое ключ.
Что такое ключ?
Ключ – это один или не сколько столбцов таблицы , которые однозначно определяют запись (строку) . Пример, пусть есть отношение представленное в виде таблицы:
Ключом данного отношения может быть столбец А . Т.к. значения только данного столбца в отношение , например: а3 определяет запись «а3 b1 d3» , a2 определят запись «a2 b2 d3» , a1 определяет запись «a1 b2 d1» . Другие столбцы данную функцию нести не могут.
Если ключ состоит из одного столбца , то его называют простым , если из нескольких его называют составным . В данной таблице, помимо простого ключа, есть еще один – составной, состоящий из столбцов B и D . Значения этих столбцов однозначной определят запись (строки), пример: b1 и d3 однозначно определяет запись «a3 b1 d3» , b2 и d3 однозначной определяет запись «a2 b2 d3» , b2 и d1 однозначно определяет запись «a1 b2 d1» .
На практике обычно выбирают один ключ , причем самый простой , в данном случае это столбец А . Такой ключ также называют «первичный ключ ».
