<- Основы реляционной алгебры
Содержание
- 1.0 Введение и основные понятия
- 2.0 Операторы реляционной алгебры
- 3.0 Объединение отношений
- 4.0 Множества
- 5.0 Дополнительные материалы
1.0 Введение и основные понятия
1.1 Как устроена реляционная модель?
База данных это множество именованных отношений - таблиц. Отношение или "relatio" - фундаментальное понятие в реляционной модели именно поэтому модель называется реляционной.
Само по себе отношение является множеством, которое содержит список кортежей представляющих строки таблицы. Например, если представить таблицу с тремя столбцами (Name, City, Job), то саму таблицу можно показать в виде множества кортежей:
{
(Kris, Berlin, Database Designer),
(Mike, Zurich, SRE),
(Harald, Berlin, Security Engineer)
}
Кортежи отношения всегда не упорядочены, так как являются частью множества. Значения же кортежей всегда упорядочены, так как значения являются частью кортежей, а не множества. Тут важно заметить, что выражение ORDER BY в языке SQL не является частью его реляционной алгебры.
Каждый элемент кортежа представляет именованный атрибут или столбец. Обычно столбцы задаются во время создания таблицы и модифицируются редко (или даже никогда). Атрибуты имеют тип, который иногда называется доменом. Например Id может быть целым типом, имя может быть строкой, фото может быть файлом jpeg. Так же реляционные базы данных могут поддерживать концепцию перечисляемого домена. Например, штат может быть перечисляемым доменом из 50 сокращений.
Также есть специальное значение, которым может быть установлен столбец любого типа. Это специальное значение именуется NULL, оно играет очень важную роль в реляционных базах данных. NULL используются для обозначения того, что значение может быть неизвестным или неопределенным.
Еще одним важным атрибутом отношения является первичный ключ (primary key). Каждое значение такого атрибута должно быть уникальным. У подобных атрибутов есть несколько важных применений. Одно из них - извлечение определенных кортежей. Например, вы можете запросить кортеж по его уникальном ключу. В то же время система баз данных для эффективности строит специальную структуру индексов для более быстрого нахождения кортежей.
Более важное применение ключей это создание связей между кортежами отношений по их уникальному ключу, так как в реляционных базах данных нет концепции указателей. Такие ключи называются внешними ключами (foreign key).
1.2 Важная терминология
Схема - структурированное описание отношения в базе данных. Схема содержит в себе название отношения, атрибуты этого отношения и типы этих атрибутов.
Экземпляр - фактическое содержание в данный момент времени. Схема устанавливается заранее, а затем экземпляры данных будут меняться со временем.
1.3 Выполнение запросов в реляционных базах данных
Основные шаги в создании и использовании реляционных баз данных.
Проектирования схемы; создание используя язык DDL (Data Definition Language). Схема содержит структуру отношений и атрибуты этих отношений.
Начальная загрузка исходных данных
Реляционная алгебра это формальный язык, который формирует основы таких языков, как SQL.
Запросы в реляционных базах данных действуют на отношения, которые так же в свою очередь порождают новые отношения.
Самый простой запрос в реляционной алгебре это запрос самого отношения: $$Relation$$ который вернет его копию.
1.4 Дубликаты
Семантика реляционной алгебры устраняет дубликаты, так как она основана на множествах. Это немного отличает реляционную алгебру от языка SQL. Устранение дубликатов является ресурсоемкой задачей, поэтому нецелесообразно использовать обычные множества в языке SQL. Вместо этого используются мультимножества, где данные могут дублироваться, а устранение дубликатов можно добиться добавлением оператора DISTINCT.
2.0 Операторы реляционной алгебры
2.1 Оператор выборки (ограничение)
Оператор выборки служит для фильтрации определенных строк отношений. Оператор обозначается греческой буквой сигма
$$\sigma$$
с контекстом обозначающим условие, которое используется для фильтрации строк извлеченных из отношения:$$ \sigma_{condition} Relation $$
Например, следующим запросом можно выбрать студентов университета "Stanford" с оценкой больше 3.7 учащихся на факультете "Computer Science":
$$ \sigma_{ cName="Stanford" \wedge gpa > 3.7 \wedge major = "Computer Science"} Student $$
2.2 Оператор проекции
Оператор проекции служит для выборки определенных столбцов отношения. Оператор обозначается греческой буквой пи
$$\pi$$
и в качестве контекста указывается список колонок:$$ \pi_{a_{1}...a_{n}} Relation $$
Пример того, как можно комбинировать оператор выборки и проекции. Выберем id студентов с gpa > 3.7:
$$ \pi_{id} (\sigma_{gpa>3.7}Student) $$
2.3 Оператор переименования
Как следует из названия оператор переименования позволяет переименовывать атрибуты отношений. Оператор переименования является унарным оператором и имеет следующую форму:
$$ \rho_{new/original} (Relation) $$
где new - новое название атрибута, original - старое название атрибута. Например для отношения:
+------------------+
| Employee |
+----------+-------+
| Id | Name |
+----------+-------+
| 1001 | Bob |
| 1002 | Alice |
| 1003 | Rob |
+----------+-------+
$$ \rho_{EmployeeName/Name} (\rho_{EmployeeId/Id}(Employee)) $$
Получим новое отношение с переименованными атрибутами:
+---------------------------+
| Employee |
+------------+--------------+
| EmployeeId | EmployeeName |
+------------+--------------+
| 1001 | Bob |
| 1002 | Alice |
| 1003 | Rob |
+------------+--------------+
Далее на примерах мы поймем почему данный оператор так важен.
3.0 Объединение отношений
3.1 Декартово произведение
Декартово произведение служит для комбинации двух отношений. Данный оператор берет два отношения создавая пары всех возможных комбинаций кортежей. Декартово произведение требует, чтобы у кортежей комбинируемых отношений было уникальное название атрибутов, в противном случае необходимо переименовывать атрибуты оператором переименования, который мы рассмотрели ранее. Например, два отношения:
+----------+-------+
| Employee |
+----------+-------+
| Id | Name |
+----------+-------+
| 1001 | Bob |
| 1002 | Alice |
| 1003 | Rob |
+----------+-------+
+---------+-------+
| Parking |
+---------+-------+
| Id | Space |
+---------+-------+
| 1001 | 6 |
| 1002 | 8 |
| 1004 | 1 |
+---------+-------+
имеют общие атрибуты Id. Запрос можно выразить следующим образом, что бы избавиться от дубликатов атрибутов:
$$ \rho_{EmployeeId/Id} (Employee) \times \rho_{ParkingId/Id} (Parking) $$
в результате получим отношение:
+-------------+---------------+------------+---------------+
| EmployeeId | Name | ParkingId | Space |
+-------------+---------------+------------+---------------+
| 1001 | Bob | 1001 | 6 |
| 1001 | Bob | 1002 | 8 |
| 1001 | Bob | 1004 | 1 |
| 1002 | Alice | 1001 | 6 |
| 1002 | Alice | 1002 | 8 |
| 1002 | Alice | 1004 | 1 |
| 1003 | Rob | 1001 | 6 |
| 1003 | Rob | 1002 | 8 |
| 1003 | Rob | 1004 | 1 |
+-------------+---------------+------------+---------------+
Декартово произведение в нашем случае является бинарным оператором, поэтому для соединения более двух отношении необходимо использовать скобки.
$$ Person \times (Employee \times Parking) $$
Само по себе декартово произведение не так полезно, если его не использовать с другими операторами.
Например, мы хотим получить место парковки Боба. Для этого используя декартово произведение можно применить оператор выборки на сравнение EmployeeId и ParkingId к результату полученного отношения:
$$ \pi_{Name, Space} (\sigma_{EmployeeId = ParkingId \wedge Name = 'Bob'} (\rho_{EmployeeId/Id}(Employee) \times \rho_{ParkingId/Id}(Parking))) $$
В результате получим отношение
+------+-------+
| Name | Space |
+------+-------+
| Bob | 6 |
+------+-------+
3.2 Естественное соединение
Естественное соединение использует декартово произведение, но позволяет обеспечить сравнение значений всех атрибутов с одинаковым названием по умолчанию, а также устранить дубликаты атрибутов:
$$ Employee \bowtie Parking $$
+------+-------+-------+
| Id | Name | Space |
+------+-------+-------+
| 1001 | Bob | 6 |
| 1002 | Alice | 8 |
+------+-------+-------+
Пример решения задачи отображения места парковки Боба используя оператор естественного соединения:
$$\pi_{Name, Space}(\sigma_{Name = 'Bob'}(Employee \bowtie Parking))$$
+------+-------+
| Name | Space |
+------+-------+
| Bob | 6 |
+------+-------+
3.3 Тета соединение
Тета соединение, так же как и естественное соединение является всего лишь сокращенной записью оператора выборки и декартова произведения. Тета - это контекст, в который передается условное выражения вместо оператора выборки:
$$Exp_{1} \bowtie_{\theta}(Exp_{1} \times Exp_{2})$$
В большинстве реляционных базах данных в качестве оператора JOIN используется именно тета соединение.
Для наглядности мы можем переписать наш предыдущий запрос получения места парковки Боба используя тета соединение:
$$\pi_{Name, Space}(Employee \bowtie_{Name='Bob'} Parking)$$
4.0 Множества
4.1 Оператор объединения
Все операторы, которые были описаны выше используются для объединения кортежей таблиц по горизонтали. А что если необходимо объединить в один список значения из разных таблиц? Для этого удобнее всего будет воспользоваться оператором объединения. Например, можно объединить столбцы Id отношений Parking и Employee:
$$\pi_{Id}Employee \cup \pi_{Id}Parking$$
+------+
| Id |
+------+
| 1001 |
| 1002 |
| 1003 |
| 1004 |
+------+
Оператор объединения ожидает, что типы объединяемых столбцов, их название и их количество должно быть одинаковым. Для объединения столбцов с разными названиями можно воспользоваться оператором переименования:
$$ \rho_{name/cName} (\pi_{cName} College) \cup \rho_{name/sName} (\pi_{sName} Student) $$
4.2 Оператор разности
Оператор разности для отношений работает так же как и для множеств, так как отношения являются сами по себе множествами, как мы рассмотрели ранее.
Например, нам нужно получить список свободных парковочных мест. Для этого мы можем применить оператор разности между отношениями Employee и Parking:
$$\pi_{Id} Parking - \pi_{Id} Employee$$
+------+
| Id |
+------+
| 1004 |
+------+
Но данный запрос в качестве результата покажет только Id парковочных мест. Что если мы хотели бы показать еще и номера свободных парковочных мест? Мы не можем добавить в контекст проекции атрибут Space, так как это исказит наше множество. Для этого мы можем применить естественное соединение к полученному результату из множества Id свободных парковочных мест:
$$ \pi_{Id, Space} ((\pi_{Id}Parking - \pi_{Id}Employee) \bowtie Parking) $$
+------+-------+
| Id | Space |
+------+-------+
| 1004 | 1 |
+------+-------+
4.3 Пересечение
Оператор пересечения возвращает общие элементы двух множеств. Пересечение множеств можно представить в виде равенства:
$$E_{1} \cap E_{2} \equiv E_{1} - (E_{1} - E_{2})$$
Пересечение множеств можно заменить естественным соединением:
$$E_{1} \cap E_{2} \equiv E_{1} \bowtie E_{2}$$