какие операции реляционной алгебры могут уменьшить количество атрибутов в итоговом отношении
Операции реляционной алгебры. Нормальные формы. Связи между отношениями. Проектирование баз данных.
Реляционная теория так же определяет некоторые операции над отношениями. Перечислим основные операции реляционной алгебры:
Возвращает отношение, содержащее все записи (кортежи) из заданного отношения, которые удовлетворяют указанным условиям.
Возвращает отношение, содержащее все записи (кортежи) заданного отношения, которые остались в этом отношении после исключения из него некоторых атрибутов.
Возвращает отношение, содержащее все записи (кортежи) заданного отношения, при этом название одного атрибута заменяется на другое.
Возвращает отношение, содержащее все возможные записи, которые являются сочетанием двух записей, принадлежащих соответственно двум заданным соотношениям.
\(R \times S\) возвращает отношение, в котором присутствуют все атрибуты отношений \(R\) и \(S\) во всех возможных комбинациях.
Возвращает отношение, содержащее все кортежи, которые принадлежат либо одному из двух заданных отношений, либо им обоим.
Возвращает отношение, содержащее все кортежи, которые принадлежат одновременно двум заданным отношениям.
Возвращает отношение, содержащее все кортежи, которые принадлежат первому из двух заданных отношений и не принадлежат второму.
Возвращает отношение, содержащее все возможные кортежи, которые представляют собой комбинацию атрибутов двух кортежей, принадлежащих двум заданным отношениям, при условии, что в этих двух комбинируемых кортежах присутствуют одинаковые значения в одном или нескольких общих для исходных отношений атрибутах (причем эти общие значения в результирующем кортеже появляются один раз, а не дважды)
Возвращает отношение, содержащее все возможные кортежи, которые представляют собой комбинацию атрибутов двух кортежей, принадлежащих двум заданным отношениям, при условии θ.
\(R \bowtie_\theta S = \sigma_\theta (R \times S)\)
Для заданных двух отношений, возвращает отношение, содержащие атрибуты, уникальные для первого отношения и такие записи, для которых декартово произведение проекции первого отношения на уникальные для него атрибуты и второго отношения существуют в первом отношении.
\(a_i \in R, a_i \notin S\)
Реляционная алгебра обладает свойством замкнутости, т.е. результатом любой операции над отношением является отношение. Это позволяет производить операции над результатами операций. Так, в частности, частым вариантом является выборка по соединению, или объединение проекций.
В дальнейшем, когда мы будем разбирать операторы языка SQL, мы попытаемся найти аналоги этих операций.
Нормальные формы
Для упрощения задач обработки данных, существуют так называемые нормальные формы реляционной модели. Они описывают, каким образом должна быть устроена структура БД, чтобы задачи поиска легко формализовывались. Обычно выделяют 6 основных нормальных форм, и две более строгих версии третьей и пятой нормальных форм. В практике проектирования СУБД обычно ограничиваются нормализацией до третьей или “строгой третьей”, поскольку, во-первых, дальнейшая нормализация не всегда осмыслена, во-вторых, усилия, необходимые для дальнейшей нормализации, как правило, значительно превышают результат.
Одним из важных эффектов нормализации является уменьшение количества возможных аномалий – случаев, когда в БД возникают противоречивые данные.
Для нормализации используется операция, называемая декомпозицией.
Отношение, соответствующая реляционной модели, автоматически находится в 1НФ.
Напомним требования реляционной модели:
Для определения 2НФ, необходимо знание определение функциональной зависимости введенное в Лекции1
Введем понятие суперключа:
Минимальный набор атрибутов, от которого функционально зависят все атрибуты отношения, будем называть потенциальным ключом.
Более строгое определение потенциального ключа:
Так же введем определения ключевых и неключевых атрибутов:
Ключевые атрибуты это атрибуты, которые входят в какой-либо потенциальный ключ Неключевые атрибуты это атрибуты, которые не входят ни в один потенциальный ключ
Отношение находится во 2НФ, если
Отношение находится в 3НФ, если
Определение Кента: каждый неключевой атрибут “должен предоставлять информацию о ключе, полном ключе и ни о чём, кроме ключа”.
Отношение находится в 3НФ тогда и только тогда, когда для каждой его функциональной зависимости \(X\rightarrow A\) выполняется хотя бы одно из условий:
Нормальная форма Бойса-Кодда (НФБК)
Отношение находится в НФБК (усиленной 3НФ), если
Формально: Отношение находится в НФБК тогда и только тогда, когда детерминантом (левой частю) любой его функциональной зависимости, входящей в (какое-либо) минимальное покрытие ФЗ этого отношения, является потенциальный ключ.
Определение Дэйта: “Каждый атрибут должен предоставлять информацию о ключе, полном ключе и ни о чём, кроме ключа”.
Отношение находится в 3НФ тогда и только тогда, когда для каждой его функциональной зависимости \(X\rightarrow A\) выполняется хотя бы одно из условий:
Нормальная форма элементарного ключа (НФЭК)
НФЭК предложена Карло Занионо в 1982 году в качестве “компромисса” между 3НФ и НФБК.
Отношение находится в НФЭК, если
Иначе, отношение находится в НФЭК, если для любой его ФЗ \(X\to A\) выполняется хотя бы одно из условий:
Декомпозиция без потерь
Как было сказано ранее, получить более высокую нормальную форму можно при помощи декомпозиции отношений.
Однако, не всякая декомпозиция допустима.
Выделяют два типа декомпозиции, используемой для нормализации.
Декомпозиция без потерь (lossless-join) позволяет восстановить исходное отношение при помощи операции соединения.
Как выбрать декомпозиции без потерь из всех возможных? Ответ на этот вопрос дает теорема Хита.
Декомпозиция без потерь, однако, может не сохранять функциональные зависимости.
Всегда существует декомпозиция без потерь до НФБК.
Декомпозиция, сохраняющая зависимости (dependency-preserving) сохраняет неизменным замыкание ФЗ всех отношений БД.
Всегда существует декомпозиция до НФЭК, сохраняющая зависимости. Однако, не всегда возможна декомпозиция, сохраняющая зависимости, до НФБК.
Проецирование функциональных зависимостей
Декомпозиция отношений по сути осуществляется при помощи операции проекции. При этом, мы утверждаем, что функциональные зависимости при декомпозиции сохраняются. Возникает вопрос: каким образом функциональные зависимости ведут себя при проецировании отношений?
Пусть отношение \(R(A,B,C,D)\) имеет следующие ФЗ:
Теперь найдем минимальное множество ФЗ. По правилу транзитивности, ФЗ \(A \to D\) следует из двух других, поэтому его можно исключить. В итоге, получаем минимальное множество ФЗ \(S\) : \[A \to C\] \[C \to D\]
Алгоритм Бернштейна построения схемы БД в НФЭК по множеству ФЗ
Филип Бернштейн предложил алгоритм построения схемы в 3НФ по ФЗ в 1976 г. Позже, Заниоло показал, что схема, построенная по этому алгоритму так же находится в НФЭК.
Данный алгоритм строит, по сути, декомпозицию отношения в 1НФ без потерь и сохраняет зависимости.
Алгоритм может быть описан следующим образом:
Пусть дано множество \(F\) нетривиальных ФЗ. Тогда:
Виды связей между отношениями
Очевидно, что новые отношения, полученные в результате декомпозиции, каким-то образом связаны между собой. Эта связь обеспечивается внешними ключами.
Выделяется четыре типа связей:
Нередко оказывается, что отношения \(R\) и \(S\) можно объединить без каких-либо потерь. В таких случаях, единственной причиной сохранять два отношения может быть связь этих отношений с различными сущностями.
Связи так же делятся на идентифицирующие и не идентифицирующие.
это такая связь, которая требует существования значения первичного ключа связанного отношения. Иными словами, запись в связанном отношении необходима для идентификации записи в данном.
Например, даны отношения Directory = (Id, Name) и File = (Id, Name, DirectoryId), связанные 1:М через внешний ключ File.DirectoryId ⇆ Directory.Id. В данной модели, файл не может существовать без директории, и эта связь является идентифицирующей, поскольку требует существования значения Directory.Id, равного File.DirectoryId.
Не идентифицирующая связь
связь, не являющаяся идентифицирующей.
Например, даны два отношения Account = (Id, Type) и AccountType = (Type, Description), связанные M:1 через внешний ключ Account.Type ⇆ AccountType.Type. В данной модели Type может быть не задан. Такое отношение не будет идентифицирующим, поскольку записи в Account и AccountType могут существовать независимо друг от друга.
Проектирование баз данных
Проектирование баз данных – это процесс концептуализации и реализации базы данных, описывающих некую предметную область, для встраивания в конкретную СУБД.
Обычно выделяют следующие этапы проектирования БД:
Рассмотрим эти этапы более подробно.
Инфологическое проектирование
Такие модели, как правило, строятся без ориентации на конкретную СУБД или даже модель данных. Смысл построения инфологической модели заключается в выделении основных сущностей предметной области и их свойств (атрибутов).
Один из популярных способов построения инфологической модели – построение ER-диаграмм.
ER-диаграммы
В отличие от диаграмм атрибутов, ER-диаграммы, кроме непосредственно атрибутов, включают так же в явном виде “сущности” и “связи” между ними, откуда, собственно, и происходит название: entity-relationship diagram, или диаграмма сущности-связи.
И сущности, и связи могут обладать набором атрибутов. Сущности без атрибутов – явление достаточно бессмысленное, как Кантовская “вещь в себе”. Связи без атрибутов – явление, напротив, весьмя распространенное.
Строго говоря, на диаграмме обозначаются классы сущностей. Во избежание путаницы, под словом “сущность” будем понимать набор атрибутов, а набор значений этих атрибутов будем называть экземпляром сущности.
В наиболее распространенной нотации, атрибуты обозначаются овалами, сущности – прямоугольниками, а связи – ромбами.
Сущности и связи соединяются между собой линиями. Существуют различные нотации, подразумевающие различную степень подробности описания. Мы будем использовать упрощенную схему, в которой для каждой линии надписывается, как раз сущность участвует в связи: 1 или много раз (М). В связи могут участвовать две или более сущностей. Хотя многозначные связи (связи, в которых участвуют более двух сущностей) – не слишком распространенное явление, иногда они бывают необходимы.
Для каждой сущности могут быть выделены один или несколько идентифицирующих атрибутов, так же, по аналогии с реляционной моделью, называемых ключом. Значения ключа сущности однозначно идентифицируют экземпляр сущности, так же как значение потенциального ключа отношения однозначно идентифицирует запись. Понятно, что ключей может быть несколько – по крайней мере один ключ, включающий все атрибуты сущности, должен существовать – назовем его тривиальным. Кроме того, возможно существуют ключи-подмножества тривиального. Условимся, что из всех ключей мы выбираем один минимальный, и используем его (назовем его первичным).
Атрибуты, входящие в первичный ключ на ER-диаграмме подчеркиваются.
Логическое (даталогическое) проектирование
На этапе логического проектирования учитывается специфика конкретной модели данных, но может не учитываться специфика конкретной СУБД.
Переход от ER-диаграмм к ФЗ
ER-диаграммы вполне естественным образом могут быть преобразованы к ФЗ.
Каждая сущность подразумевает ФЗ неключевых атрибутов от ключевых, поскольку значения ключевых атрибутов однозначно определяют значения остальных – иначе, значения неключевых атрибутов есть (вообще говоря, дискретная) функция от значений ключевых атрибутов.
Связи двух сущностей типа один-к-одному устанавливают взаимно-однозначное соответствие между сущностями, то есть взаимные ФЗ между ключами сущностей. Атрибуты самой связи функционально зависят от всех ключей входящих в связь сущностей.
Связи двух сущностей типа один-ко-многим и многие-к-одному естественным образом моделируют функциональную зависимость между ключевыми атрибутами соответствующих сущностей: в левой части ФЗ находятся ключевые атрибуты сущности, входящей в связь многократно, а в правой – ключевые атрибуты сущности, входящей в связь однократно, а так же атрибуты самой связи (если есть). Можно сказать, что ФЗ моделирует связь типа многие-к-одному.
Это же рассуждение естественным образом обобщается на многозначные связи: каждая из однократно входящих в связь сущностей (точнее, ее ключи) функционально зависят от всех многократно входящих в связь сущностей. То же самое можно сказать об атрибутах самой связи.
Наконец, связь типа многие-ко-многим можно рассматривать как частный случай многозначной связи: все атрибуты связи функционально зависят от всех ключевых атрибутов связанных сущностей.
Диаграммы атрибутов
Кроме непосредственной записи ФЗ в столбик, существует более наглядный способ представления ФЗ отношений. Он так же может использоваться для нормализации отношения по крайней мере до 3НФ.
Диаграммы атрибутов строятся следующим образом. В овалах записываются все атрибуты данной предметной области, и между ними рисуются стрелки, соответствующие ФЗ, присутствующим в системе. В случае наличия составных левых частей ФЗ, вводятся промежуточные узлы, обозначаемые точкой.
Например, построим диаграмму атрибутов для нашего примера с теннисными кортами.
Использование диаграмм атрибутов позволяет достаточно просто обнаруживать транзитивные зависимости и выделять отдельные отношения методом простой группировки связанных узлов (атрибутов).
В качестве примера, выделим на этой диаграмме отношения. Сначала выделим все возможные ключевые атрибуты по следующему признаку: если какой-либо атрибут функционально зависит от данного, то данный атрибут является ключевым.
Теперь для каждого ключевого атрибута выделим его и все атрибуты, непосредственно зависящие от него, в отдельную группу.
Это позволит нам выделить группы атрибутов, не имеющие транзитивных зависимостей, в которых все неключевые атрибуты зависят от потенциального ключа.
Двойной линией обозначены внешние ключи.
Несложно заметить, что каждая из выделенных групп является отношением в 3НФ.
Какие операции реляционной алгебры могут уменьшить количество атрибутов в итоговом отношении
Во вторую группу входят операции, применимые только к отношениям:
| Рис. 1. Операции реляционной алгебры |
Нужно объединить два отношения Физ_лица и Юр_лица.
| ФИО | Адр_регистрации | Факт_адр |
|---|---|---|
| Иванов Ю.М. | Москва, Тверская 2 | С.-Петербург,Садовая ул. 12 |
| Сергеев И.А. | С.-Петербург, Седова 23 | С.-Петербург, Гороховая ул. 34 |
| . | . | . |
| Наим | Адр_регистрации | Адр_офиса |
|---|---|---|
| Альфа | Новгород, Садовая ул. 2 | С.-Петербург,Садовая ул. 42 |
| Бета. | С.-Петербург, Московский пр. 23 | Гатчина, Лесная ул. 34 |
| . | . | . |
Результат запроса:
| ИМЯ | Адр_официальный | Фактический_адр |
|---|---|---|
| Иванов Ю.М. | Москва, Тверская 2 | С.-Петербург,Садовая ул. 12 |
| Сергеев И.А. | С.-Петербург, Седова 23 | С.-Петербург, Гороховая ул. 34 |
| Альфа | Новгород, Садовая ул. 2 | С.-Петербург,Садовая ул. 42 |
| Бета. | С.-Петербург, Московский пр. 23 | Гатчина, Лесная ул. 34 |
| . | . | . |
Операции объединения, пересечения и разности имеют следующие особенности:
Из отношения Жители нужно выбрать жителей, младше 30 лет
| ФИО | Возраст |
|---|---|
| Андреев | 31 |
| Иванов | 21 |
| Перов | 40 |
| Яковлев | 27 |
На языке SQL запрос запрос выглядит так:
Результат выборки
| ФИО | Возраст |
|---|---|
| Андреев | 31 |
| Перов | 40 |
Из отношения Жители нужно выбрать только фамилии жителей
| Имя | ФИО | Возраст |
|---|---|---|
| Юрий | Иванов | 31 |
| Сергей | Иванов | 21 |
| Владимир | Перов | 40 |
| Игорь | Перов | 27 |
На языке SQL запрос запрос выглядит так:
Результат выборки
| ФИО |
|---|
| Иванов |
| Перов |
Язык SQL предназначен для работы с реальными таблицами и допускает несколько одинаковых строк в таблице с результатами запроса. Для исключения одинаковых строк служит служебное слово DISTINCT
Семантически общие атрибуты описывают общие свойства соединяемых отношений. Общие атрибуты должны иметь один тип
Даны два отношения Рабочие и Инструменты
|
|
| ТабНомер | ФИО | Должность | Инструмент |
|---|---|---|---|
| 1 | Андреев | Слесарь | Штангельциркул |
| 1 | Андреев | Слесарь | Микрометр |
| 1 | Андреев | Слесарь | Линейка |
| 2 | Иванов | Слесарь | Штангельциркул |
| 2 | Иванов | Слесарь | Скоба |
Если в запросе не указать общий атрибут, то получится декартово произведение, состоящее из 4*5=20 кортежей.
При выполнении запроса SELECT, как правило, делаются несколько реляционных операций. Например, для выборки из отношения Рабочие всех кортежей со слесарями и атрибутов ФИО и Должность служит оператор
Выполнение этого запроса состоит из двух реляционных операций: выборки и проекции.
Реляционная алгебра, операции реляционной алгебры
Что такое реляционная алгебра
Операция выборки
,
Запрос 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 |
Комбинировать всевозможные логические условия для выборок Вам поможет материал «Булева алгебра (алгебра логики)».
А в материалах раздела «Программирование PHP/MySQL» Вы найдёт немало примеров комбинаций различных логических условий для выборок из базы данных.
Операция проекции
Запрос SQL
Пусть вновь дано то же отношение R3 :
| R3 | |||
| A1 | A2 | A3 | A4 |
| 3 | hh | yl | ms |
| 4 | pp | a1 | sr |
| 1 | rr | yl | ms |
| R | |
| A4 | A3 |
| ms | yl |
| sr | a1 |
Операция объединения
Результатом объединения двух множеств (отношений) А и В (
) будет такое множество (отношение) С, которое включает в себя те и только те элементы, которые есть или во множестве А или во множестве В. Говоря упрощённо, все элементы множества А и множества В, за исключением дубликатов, образующихся за счёт того, что некоторые элементы есть и в первом, и во втором множестве. Операция объединения реляционной алгебры идентична операции объединения множеств, которая также описана в материале «Множества и операции над множествами».
Запрос 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
В некоторых диалектах SQL отсутствует ключевое слово INTERSECT. Поэтому, например, в MySQL и других, операция пересечения множеств может реализована с применением предиката EXISTS.
Теперь посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса 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
Установим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса 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 |
| Q2 | ee | h15 |
В некоторых диалектах SQL отсутствует ключевое слово EXCEPT. Поэтому, например, в MySQL и других, операция пересечения множеств может реализована с применением предиката NOT EXISTS.
Операция декартова произведения
Операция декартова произведения (
) определяет новое отношение R, которое является результатом конкатенации каждого кортежа отношения R1 с каждым кортежем отношения R2.
Запрос SQL
Установим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса 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 |
Операция деления
Результатом операции деления (
) является набор кортежей (строк) отношения R1, которые соответствуют комбинации всех кортежей отношения R2. Для этого нужно, чтобы в отношении R2 была часть атрибутов (можно и один), которые есть в отношении R1. В результирующем отношении присутствуют только те атрибуты отношения R1, которых нет в отношении R2.
Запрос SQL
Давайте посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Даны два отношения R5 и R6:
| R5 | R6 | ||||
| A1 | A2 | A3 | A4 | A2 | A3 |
| 2 | S3 | 4 | sun | R4 | 8 |
| 3 | X8 | 7 | kab | X8 | 7 |
| 3 | R4 | 8 | kab | ||
Комбинации всех кортежей отношения R6 соответствуют вторая и третья строки отношения R5. Но после исключения атрибутов (столбцов) А2 и А3 эти строки становятся идентичными. Поэтому в новом отношении присутствует эта строка один раз. Новое отношение:
Операция тета-соединения
Запрос SQL
Посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса 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 | ||