Реляционная модель данных

Создание запросов реляционной алгебры

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

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

Пример 1.

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

Сначала выводится информация о машинах, чтобы понимать значения всех атрибутов отношения. Информация об инспекциях хранится в таблице «Проверка», и, если обнаружены неисправности, они регистрируются в таблице «Проблема». Таким образом, нужны эти три таблицы, чтобы получить нужную информацию.

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

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

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

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

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

$$\pi_{Id}Employee \cup \pi_{Id}Parking$$

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

$$
\rho_{name/cName}
(\pi_{cName} College)
\cup
\rho_{name/sName}
(\pi_{sName} Student)
$$

Замкнутость реляционной алгебры

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

Операции над одним отношением называются унарными, над двумя отношениями — бинарными, над тремя — тернарными (таковые практически неизвестны).

Пример унарной операции — проекция, пример бинарной операции — объединение.

N-арную реляционную операцию f можно представить функцией, возвращающей отношение и имеющей n отношений в качестве аргументов:

R=f(R1,R2,…,Rn){\displaystyle R=f(R_{1},R_{2},\dots ,R_{n})}

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

R=f(f1(R11,R12,…),f2(R21,R22,…),…){\displaystyle R=f(f_{1}(R_{11},R_{12},\dots ),f_{2}(R_{21},R_{22},\dots ),\dots )}

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

Алгоритм Бернштейна построения схемы БД в НФЭК по множеству ФЗ

Филип Бернштейн предложил алгоритм построения схемы в 3НФ по ФЗ в 1976 г. Позже, Заниоло показал, что схема, построенная по этому алгоритму так же находится в НФЭК.

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

Алгоритм может быть описан следующим образом:

Пусть дано множество \(F\) нетривиальных ФЗ. Тогда:

  1. Удалить избыточные атрибуты в детерминантах (левых частях) каждой ФЗ. Получить множество ФЗ \(G\).
  2. Построить неизбыточное покрытие \(H\) для \(G\) (минимизировать \(G\))
  3. Разбить \(H\) на группы таким образом, чтобы левые части ФЗ в каждой группе имели одинаковые левые части.
  4. Объединить эквивалентные ключи. Для каждых двух групп \(H_i\) и \(H_j\), имеющих левыми частями соответственно \(X_i\) и \(X_j\), объединить их, если в \(H^+\) существуют ФЗ \(X_i \to X_j\) и \(X_j \to X_i\).
  5. Составить отношения. Для каждой группы, составить отношение, содержащее атрибуты этой группы. Ключом каждого отношения будут атрибуты детерминанта группы.

Избыточным атрибутом в детерминанте ФЗ \(g \in G\), \(g = X_1, \ldots, X_p \to Y\), является атрибут \(X_i\), если \(G^+\) содержит ФЗ \(X_1, \ldots,X_{i-1}, X_{i+1}, \ldots, X_p \to Y\).

Иначе, для ФЗ \((A \to B) \in G\), атрибут \(a\in A\) является избыточным, если \(a\in (A-\{a\})^+_ G\).

Виды связей между отношениями

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

Внешний ключ
Набор атрибутов \(A\) отношения \(R\) называется внешним ключом, если тот же набор атрибутов \(A\), либо некое переименование \(\rho_B A\), является суперключом некого другого отношения \(S\), причем множество значений \(A\) по всем записям \(R\) в любой момент времени является подмножеством значений \(\rho_B A\) по всем записям \(S\).

Выделяется четыре типа связей:

Один к одному (1:1)

Каждой записи отношения \(R\) соответствует одна и только одна запись отношения \(S\), и наоборот.

Нередко оказывается, что отношения \(R\) и \(S\) можно объединить без каких-либо потерь. В таких случаях, единственной причиной сохранять два отношения может быть связь этих отношений с различными сущностями.

Один ко многим (1:M)
Каждой записи отношения \(R\) соответствует \(M \geq 0\) записей отношения \(S\), но каждой записи отношения \(S\) соответствует только одна запись отношения \(R\).
Многие к одному (M:1)
Каждой записи отношения \(R\) соответствует только одна запись отношения \(S\), но каждой записи отношения \(S\) соответствует \(M \geq 0\) записей отношения \(R\)
Многие ко многим (M:N)
Каждой записи отношения \(R\) соответствует \(M \geq 0\) записей отношения \(S\), и каждой записи отношения \(S\) соответствует \(N \geq 0\) записей отношения \(R\)

Связи так же делятся на идентифицирующие и не идентифицирующие.

Идентифицирующая связь

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

Например, даны отношения 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 могут существовать независимо друг от друга.

Проектирование баз данных

Проектирование баз данных – это процесс концептуализации и реализации базы данных, описывающих некую предметную область, для встраивания в конкретную СУБД.

Обычно выделяют следующие этапы проектирования БД:

  1. Концептуальное (инфологическое) проектирование.
  2. Логическое (даталогическое) проектирование
  3. Физическое проектирование

Рассмотрим эти этапы более подробно.

Структура хранения

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

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

Магнитные и жесткие диски являются наиболее распространенными вторичными устройствами хранения в современных компьютерных системах. Они называются магнитными, состоят из металлической основы. Эти диски размещаются вертикально на шпинделе. Головка чтения/записи перемещается между ними и используется для намагничивания или снятия такого пятна под ним. Его можно распознать как 0 (ноль) или 1 (один).

Жесткие диски отформатированы в четко определенном порядке для эффективного хранения данных. На нем много концентрических кругов, называемых дорожками. Каждый трек далее разделяется на сектора, где обычно хранится 512 байт данных.

Инфологическое проектирование

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

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

Один из популярных способов построения инфологической модели – построение ER-диаграмм.

ER-диаграммы

В отличие от диаграмм атрибутов, ER-диаграммы, кроме непосредственно атрибутов, включают так же в явном виде “сущности” и “связи” между ними, откуда, собственно, и происходит название: entity-relationship diagram, или диаграмма сущности-связи.

И сущности, и связи могут обладать набором атрибутов. Сущности без атрибутов – явление достаточно бессмысленное, как Кантовская “вещь в себе”. Связи без атрибутов – явление, напротив, весьмя распространенное.

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

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

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

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

Атрибуты, входящие в первичный ключ на ER-диаграмме подчеркиваются.

Рассмотрим ER-диаграмму для примера с теннисными кортами.

Заметки о SQL и реляционной алгебре +32

  • 18.01.16 09:32


varagian

#275251

Хабрахабр

19000

Алгоритмы, Математика, SQL

На Хабре и за его пределами часто обсуждают реляционную алгебру и SQL, но далеко не так часто акцентируют внимание на связи между этими формализмами. В данной статье мы отправимся к самым корням теории запросов: реляционному исчислению, реляционной алгебре и языку SQL

Мы разберем их на простых примерах, а также увидим, что бывает полезно переключаться между формализмами для анализа и написания запросов.
Зачем это может быть нужно сегодня? Не только специалистам по анализу данных и администраторам баз данных приходится работать с данными, фактически мало кому не приходится что-то извлекать из (полу-)структурированных данных или трансформировать уже имеющиеся. Для того, чтобы иметь хорошее представление почему языки запросов устроены определенным образом и осознанно их использовать нужно разобраться с ядром, лежащим в основе. Об этом мы сегодня и поговорим.
Большую часть статьи составляют примеры с вкраплениями теории. В конце разделов приведены ссылки на дополнительные материалы, а для заинтересовавшихся и небольшая подборка литературы и курсов в конце.
Содержание

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

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

Переименование

Результатом применения операции переименования атрибутов является отношение с изменёнными именами атрибутов.

Синтаксис:

R RENAME Atr1, Atr2, … AS NewAtr1, NewAtr2,

где

R — отношение
Atr1, Atr2, … — исходные имена атрибутов
NewAtr1, NewAtr2, … — новые имена атрибутов.

Объединение

Отношение с тем же заголовком, что и у совместимых по типу отношений A и B, и телом, состоящим из кортежей, принадлежащих или A, или B, или обоим отношениям.
Синтаксис:

A UNION B

Пересечение

Отношение с тем же заголовком, что и у отношений A и B, и телом, состоящим из кортежей, принадлежащих одновременно обоим отношениям A и B.
Синтаксис:

A INTERSECT B

Вычитание

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

A MINUS B

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

Отношение, заголовок (A1, A2, …, An, B1, B2, …, Bm) которого является сцеплением заголовков отношений A(A1, A2, …, An) и B(B1, B2, …, Bm), а тело состоит из кортежей, являющихся всеми вариантами сцеплений кортежей отношений A и B: (a1, a2, …, an, b1, b2, …,bm),

таких, что

(a1, a2, …, an) ∈ A,
(b1, b2, …, bm) ∈ B.

Синтаксис:

A TIMES B

Выборка (ограничение)

Отношение с тем же заголовком, что и у отношения A, и телом, состоящим из кортежей, значения атрибутов которых при подстановке в условие c дают значение ИСТИНА. c представляет собой логическое выражение, в которое могут входить атрибуты отношения A и/или скалярные выражения.
Синтаксис:

A WHERE c

Проекция

Основная статья: Проекция (реляционная алгебра)

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

A

или

PROJECT A {x, y, …, z}

Соединение

Операция соединения отношений A и B по предикату P логически эквивалентна последовательному применению операций декартового произведения A и B и выборки по предикату P. Если в отношениях имеются атрибуты с одинаковыми наименованиями, то перед выполнением соединения такие атрибуты необходимо переименовать.

Синтаксис:

(A TIMES B) WHERE P

Деление

Отношение с заголовком (X1, X2, …, Xn) и телом, содержащим множество кортежей (x1, x2, …, xn), таких, что для всех кортежей (y1, y2, …, ym) ∈ B в отношении A(X1, X2, …, Xn, Y1, Y2, …, Ym) найдется кортеж (x1, x2, …, xn, y1, y2, …, ym).

Синтаксис:

A DIVIDEBY B

Логическое (даталогическое) проектирование

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

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

Переход от ER-диаграмм к ФЗ

ER-диаграммы вполне естественным образом могут быть преобразованы к ФЗ.

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

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

Связи двух сущностей типа один-ко-многим и многие-к-одному естественным образом моделируют функциональную зависимость между ключевыми атрибутами соответствующих сущностей: в левой части ФЗ находятся ключевые атрибуты сущности, входящей в связь многократно, а в правой – ключевые атрибуты сущности, входящей в связь однократно, а так же атрибуты самой связи (если есть). Можно сказать, что ФЗ моделирует связь типа многие-к-одному.

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

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

Таким образом:

  1. Каждая сущность \(E\) преобразуется к ФЗ вида \ где \(K_E\) – множество ключевых (идентифицирующих) атрибутов сущности \(E\), а \(A_E\) – множество всех атрибутов сущности \(E\).
  2. Каждая связь \(R\) между сущностями \(E_1,\ldots,E_n\), входящими в связь многократно и \(S_1,\ldots,S_m\), входящими в связь однократно, преобразуется к ФЗ вида \ где \(K_i\) – ключи соответствующих сущностей, \(A_R\) – атрибуты связи, и ФЗ вида \.

Следует сделать одно важное замечание: если связь многие-ко-многим (возможно многозначная) не имеет атрибутов, то она даст исключительно тривиальные функциональные зависимости. Это, как правило, нежелательно, поскольку при формальном анализе в итоге приведет к потере этой связи

Это связано с тем, что связь многие-ко-многим является нефункциональной зависимостью. Решением этой проблемы может быть ввод фиктивного атрибута с пустым доменом, скажем, \(\theta\), уникального для данной связи. Это позволит формально анализировать функциональные зависимости для – фактически – неопределенной функции.

Диаграммы атрибутов

Кроме непосредственной записи ФЗ в столбик, существует более наглядный способ представления ФЗ отношений. Он так же может использоваться для нормализации отношения по крайней мере до 3НФ.

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

Например, построим диаграмму атрибутов для нашего примера с теннисными кортами.

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

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

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

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

Двойной линией обозначены внешние ключи.

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

Добавить комментарий

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

Adblock
detector