Реляционная алгебра — студенческий портал

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

Реляционная алгебра — формальная система манипулирования отношениями в реляционной модели данных. [1]

Выборка

Операция выборки — унарный оператор, записываемый как σaθb(R) или σaθv(R), где:

  • a, b — имена атрибутов
  • θ — оператор сравнения из множества {}
  • v — константа
  • R — отношение (в оригинале — relation, однако как видно из примера, подразумевается не столько взаимосвязь таблиц, сколько взаимосвязь/соотношение различных фактов в рядах этих таблиц).

Выборка σaθb(R) (или σaθv(R)) выбирает все наборы значений R, для которых функция a θ b (или a θ v) будет истинна.

Пример

Пусть даны следующие соотношения:

Персоны

Имя
Возраст
Вес
Harry 34 80
Sally 28 64
George 29 70
Helena 54 54
Peter 34 80

Тогда результаты выборок будут следующими:

σВозраст ≥ 34(Персоны)

Имя
Возраст
Вес
Harry 34 80
Helena 54 54
Peter 34 80

Эквивалентный SQL-запрос:

SELECT * FROM Персоны WHERE Возраст >= 34

σВозраст = Вес(Персоны)

Имя
Возраст
Вес
Helena 54 54

Эквивалентный SQL-запрос:

SELECT * FROM Персоны WHERE Возраст = Вес

Проекция

Операция выборки — унарный оператор, записываемый как πa1,…,an(R) где a1,…,an — спиоск полей, подлежащих выборке. Результатом такой выборки будет набор последовательностей значений отношения R, в котором будут присутствовать только поля, перечисленные в списке a1,…,an с естественным уничтожением потенциально возникающих кортежей-дубликатов[4].

Пример

Пусть даны следующие соотношения:

Персоны

Имя
Возраст
Вес
Harry 34 80
Sally 28 64
George 29 70
Helena 54 54
Peter 34 80

Результат проекции:

πВозраст,Вес(Персоны)

Возраст
Вес
28 64
29 70
54 54
34 80

Эквивалентный SQL-запрос:

SELECT DISTINCT Возраст, Вес FROM Персоны

Примечательно, что в SQL для полного соответствия операции проекции необходимо указывать ключевое слово DISTINCT, поскольку без него строка с возрастом 34 и весом 80 отобразится дважды, что отличается от результата реляционной операции проекции.

Объединение

Реляционная алгебра - Студенческий портал

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

Пример

Пусть даны следующие соотношения:

Персоны

Имя
Возраст
Вес
Harry 34 80
Sally 28 64
George 29 70
Helena 54 54
Peter 34 80

Персонажи

Имя
Возраст
Вес
Daffy 24 19
Donald 25 23
Scrooge 81 27

Результат объединения:

Имя
Возраст
Вес
Harry 34 80
Sally 28 64
George 29 70
Helena 54 54
Peter 34 80
Daffy 24 19
Donald 25 23
Scrooge 81 27

Эквивалентный SQL-запрос:

SELECT Имя, Возраст, Вес FROM Персоны
UNION
SELECT Имя, Возраст, Вес FROM Персонажи

Пересечение

Реляционная алгебра - Студенческий портал

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

Пример

Пусть даны следующие соотношения:

Персоны

Имя
Возраст
Вес
Harry 34 80
Sally 28 64
George 29 70
Helena 54 54
Peter 34 80

Персонажи

Имя
Возраст
Вес
Daffy 24 19
George 29 70
Donald 25 23
Scrooge 81 27
Sally 28 64

Результат пересечения:

Имя
Возраст
Вес
George 29 70
Sally 28 64

Эквивалентный SQL-запрос:

SELECT Имя, Возраст, Вес FROM Персоны
INTERSECT
SELECT Имя, Возраст, Вес FROM Персонажи

Ключевое слово INTERSECT может отсутствовать в некоторых СУБД, однако оно включено в стандарт [5].

Разность

Реляционная алгебра - Студенческий портал

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

Пример

Пусть даны следующие соотношения:

Персоны

Имя
Возраст
Вес
Harry 34 80
Sally 28 64
George 29 70
Helena 54 54
Peter 34 80

Персонажи

Имя
Возраст
Вес
Daffy 24 19
George 29 70
Donald 25 23
Scrooge 81 27
Sally 28 64

Результат разности:

Имя
Возраст
Вес
Harry 34 80
Helena 54 54
Peter 34 80

Эквивалентный SQL-запрос:

SELECT Имя, Возраст, Вес FROM Персоны
EXCEPT
SELECT Имя, Возраст, Вес FROM Персонажи

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

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

Пример

Пусть даны следующие соотношения:

Мульфильмы

Код_мульта
Название_мульта
The Simpsons
1 Family Guy
2 Duck Tales

Каналы

Код_канала
Название_канала
СТС
1 2х2

Результат произведения:

Код_мульта
Название_мульта
Код_канала
Название_канала
The Simpsons СТС
The Simpsons 1 2х2
1 Family Guy СТС
1 Family Guy 1 2х2
2 Duck Tales СТС
2 Duck Tales 1 2х2

Эквивалентный SQL-запрос:

SELECT * FROM Мультфильмы, Каналы

Деление

Реляционное деление достаточно нетривиально описать, но на примере его смысл нагляден. В целом, из таблицы A берутся значения строк, для которых присутствуют все комбинации значений из таблицы B. Понятно? Ну, примерно об этом я и пытался сказать, смотрим пример:

Пример

Пусть даны следующие соотношения:

Мульфильмы

Код_мульта
Название_мульта
Название_канала
The Simpsons RenTV
The Simpsons 2х2
The Simpsons CTC
1 Family Guy RenTV
1 Family Guy 2х2
2 Duck Tales СТС
2 Duck Tales 2×2

Тогда при делении на таблицу каналов:

Каналы

Название_канала
RenTV
2х2

Результатом будет:

Код_мульта
Название_мульта
The Simpsons
1 Family Guy

Family Guy и The Simpsons — мультфильмы, которые показывались и на RenTV и на 2×2 (условие во второй таблице). При этом Duck Tales не показывалось по RenTV, потому был исключён из результирующей таблицы.

Эквивалентный SQL-запрос привести затрудняюсь

Соединение

Операция соединения есть результат последовательного применения операций декартового произведения и выборки. Если в отношениях и имеются атрибуты с одинаковыми наименованиями, то перед выполнением соединения такие атрибуты необходимо переименовать.[4]

Пример

Мульфильмы

Код_мульта
Название_мульта
Название_канала
The Simpsons 2х2
1 Family Guy 2х2
2 Duck Tales RenTV

Каналы

Код_канала
Частота
RenTV 3,1415
2х2 783,25

Соединим их с выборкой σНазвание_канала = Код_канала(Произведение)
Первый этап, произведение:

Код_мульта
Название_мульта
Название_канала
Код_канала
Частота
The Simpsons 2х2 RenTV 3,1415
The Simpsons 2х2 2х2 783,25
1 Family Guy 2х2 RenTV 3,1415
1 Family Guy 2х2 2х2 783,25
2 Duck Tales RenTV RenTV 3,1415
2 Duck Tales RenTV 2х2 783,25

Второй этап, выборка σНазвание_канала = Код_канала(Произведение):

Код_мульта
Название_мульта
Название_канала
Код_канала
Частота
The Simpsons 2х2 2х2 783,25
1 Family Guy 2х2 2х2 783,25
2 Duck Tales RenTV RenTV 3,1415

Эквивалентный SQL-запрос:

SELECT * FROM Мультфильмы, Каналы WHERE Название_канала = Код_канала

Источник: http://migku.wikidot.com/gos-db-16

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

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

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

Для каждой операции реляционной алгебры будет дана её реализация в виде запросов на языке SQL.

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

будем выполнять операции над отношениями (таблицами) с абстрактными данными, такими как R1, R2 (названия таблиц — отношений) и т.д. и А1, А2, А3 (названия атрибутов — столбцов) и h15, w11 и т.п.

(содержание записей таблиц базы данных).

Приоритеты выполнения операций реляционной алгебры (в порядке убывания пунктов списка, а в одном пункте — операции с равными приоритетами):

  • селекция, проекция
  • декартово произведение, соединение, пересечение, деление
  • объединение, разность.
  • Операция выборки работает с одним отношением и определяет результирующее отношение R, которое содержит только те кортежи (или строки, или записи), отношения , которые удовлетворяют заданному условию (предикату P).
  • Таким образом, операция выборки — унарная операция — и записывается следующим образом:
  • ,
  • где P — предикат (логическое условие).
  • Запрос SQL
  • SELECT * from R3 WHERE A3>'d0'

Теперь посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса 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» Вы найдёт немало примеров комбинаций различных логических условий для выборок из базы данных.

Операция проекции

  1. Операция проекции (Реляционная алгебра - Студенческий портал) работает, как и операция выборки, только с одним отношением и определяет новое отношение R, в котором есть лишь те атрибуты (столбцы), которые заданы в операции, и их значения.
  2. Запрос SQL
  3. SELECT DISTINCT A4, A3 from R3
  4. Пусть вновь дано то же отношение R3:
R3
A1 A2 A3 A4
3 hh yl ms
4 pp a1 sr
1 rr yl ms

Из исходного отношения выбираем только столбцы А4 и А3 и видим, что строки со значениями — первая и третья — идентичны. Исключаем дубликат (за это отвечает ключевое слово DISTINCT в SQL-запросе, которое говорит, что нужно выбрать только уникальные записи) и получаем следующее новое отношение, в котором два атрибута и две строки (записи):

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

Результатом объединения двух множеств (отношений) А и В () будет такое множество (отношение) С, которое включает в себя те и только те элементы, которые есть или во множестве А или во множестве В.

Читайте также:  Тирания писистрата и писистратидов в афинах (560—510 гг. до н. э.). - студенческий портал

Говоря упрощённо, все элементы множества А и множества В, за исключением дубликатов, образующихся за счёт того, что некоторые элементы есть и в первом, и во втором множестве.

Операция объединения реляционной алгебры идентична операции объединения множеств, которая также описана в материале «Множества и операции над множествами».

  • Запрос 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 и других, операция пересечения множеств может реализована с применением предиката 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

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

Операция разности

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

  1. Запрос SQL
  2. SELECT A1, A2, A3 from R2 EXCEPT SELECT A1, A2, A3 from R1
  3. Установим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса 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 — третью — и получаем новое отношение:

В некоторых диалектах SQL отсутствует ключевое слово EXCEPT. Поэтому, например, в MySQL и других, операция пересечения множеств может реализована с применением предиката NOT EXISTS.

Операция декартова произведения

  • Операция декартова произведения () определяет новое отношение 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

Операция деления

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

Запрос SQL

SELECT DISTINCT A1, A4 from R5 WHERE NOT EXIST (SELECT * from R6 WHERE NOT EXIST R6.A2 = R5.A2 AND

R6.A3 = R5.A3)

Давайте посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса 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 эти строки становятся идентичными. Поэтому в новом отношении присутствует эта строка один раз. Новое отношение:

Операция тета-соединения

В результате этой операции получается отношение, которое содержит кортежи из декартова произведения отношений R1 и R2 удовлетворяющие предикату Р. Значением предиката Р может быть один из операторов сравнения (, >=, = или !=).

  1. Запрос SQL
  2. SELECT * from R3, R4 WHERE A1>=A5
  3. Посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса 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

Это таблицы (отношения) из главы о декартовом произведении. Выполняем операцию декартового произведения. Видим, что условию предиката Р удовлетворяет один кортеж декартового произведения — первый (так как 3>=3). Получаем следующее новое отношение:

R
A1 A2 A3 A4 A5 A6
3 hh yl ms 3 hh

Реляционные базы данных и язык SQL

Поделиться с друзьями

Источник: https://function-x.ru/relation_algebra.html

GOUSPO студенческий портал! » Взаимосвязи в моделях и реляционный подход к построению модели

admin

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

Методы и алгоритмы обработки информации в реляционных базах данных основываются на теории реляционной алгебры, кото­рую ранее называли алгеброй логики, или булевой алгеброй.

Алгебра логики представляет собой прежде всего алгебру выс­казываний.

Под высказыванием в алгебре логики понимают всякое предложение, которое либо истинно, либо ложно; при этом может иметь место только одно из двух указанных значений (на­пример: «Москва — столица России» — истинное высказывание; «снег черен» — ложное высказывание).

Отдельные высказывания в алгебре логики обозначаются буквами какого-либо алфавита, например: А, В, С. Истинность или ложность высказываний на­зывается их значениями истинности. В алгебре логики принято отождествлять истинность высказывания с числом 1, а ложность высказывания — с числом 0.

Запись А = 1 и С = 0 означает, что А истинно и что С ложно. Каждое конкретное высказывание имеет вполне определенное значение истинности — это постоянная, рав­ная 0 или 1. От конкретных (постоянных) высказываний следует отличать так называемые переменные высказывания.

Переменное высказывание — это не высказывание в подлинном смысле, а переменная для высказываний (пропозициональная пе­ременная), т.е.

символ, вместо которого можно подставить посто­янные высказывания (или их наименования) и который может принимать лишь два значения: «истинно» или «ложно», или соот­ветственно 1 и 0 (двоичная переменная). Переменные высказыва­ния (т.е.

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

Предметом изучения в алгебре логики являются бинарные (или двузначные) функции, т. е. функции, которые принимают лишь два значения («истинно» или «ложно»; 0 или 1) и зависят от од­ной или нескольких бинарных переменных. Это так называемые булевы функции.

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

Объединение про­стых высказываний в сложные в алгебре логики производится без учета внутреннего содержания (смысла) этих высказываний.

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

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

Отрицание высказывания. Отрицание высказывания А — это высказывание, которое истинно, когда А ложно, и ложно, когда А истинно; обозначается: А; читается: «не А».

Конъюнкция двух высказываний.

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

Конъюнкция двух высказываний обозначается: А В; чи­тается «А и В». Знак конъюнкции «» имеет смысл союза «и». Опе­рация конъюнкции имеет также смысл логического умножения и может обозначается знаком «&».

Значения истинности операции конъюнкции

А В АВ
1 1 1
1
1

Дизъюнкция двух высказываний. Дизъюнкция двух высказыва­ний — это сложное высказывание, которое ложно в случае лож­ности обоих составляющих его высказываний и истинно в осталь­ных случаях.

Читайте также:  Строение и процессы жизнедеятельности хрящевых рыб - студенческий портал

Операция дизъюнкции обозначается: AB; читается: «А или В» (другое обозначение: А + В; другое название — «логическое сложение»).

Знак логической связи «» имеет смысл союза «или» и назы­вается знаком дизъюнкции. Союз «или» может употребляться в нескольких различных смыслах.

Знак «» может иметь смысл «или», употребленный, например, в фразе: «При звоне будиль­ника Петя или Ваня проснется» (здесь «или» не исключает воз­можности того, что проснутся оба). В данном случае дизъюнкция имеет смысл неразделительного «или».

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

Значения истинности операции дизъюнкции

А В AB
1 1 1
1 1
1 1

Эквивалентность двух высказываний.

Эквивалентность двух выс­казываний — это сложное высказывание, истинное тогда, когда значения истинности составляющих высказываний одинаковы, и ложное — в противном случае; обозначается: А  В; читается: «А эк­вивалентно В». Для эквивалентности справедливы высказывания, которые можно записать следующим образом: A 1 = А, что озна­чает: А эквивалентно единице, когда А истинно.

Запись А  0 = А означает, что А эквивалентно нулю, когда А ложно.

Отрицание эквивалентности.

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

Отрицание эквивалентно­сти означает, что А не эквивалентно В. Эта операция имеет важное значение в теории проектирова­ния ЭВМ, так как она представляет собой так называемое сложе­ние двоичных чисел по модулю два.

Импликация двух высказываний. Импликация двух высказыва­ний обозначается: A В; читается: «если А, то В». Это такое слож­ное высказывание, которое ложно только в том случае, когда А истинно, а В ложно.

Импликация не предполагает обязательную связь по смыслу между условием А и следствием В, хотя и не исключает такую связь. Смысл импликации можно выра­зить следующим образом: «А ложно или В истинно».

В этом выражении союз «или» имеет не исключающее значение.

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

2. Реляционный подход к построению модели данных.

Развитие реляционных баз данных началось в конце 1960-х гг., когда появились первые работы, в которых обсуждались возмож­ности использования привычных для специалиста способов фор­мализованного представления данных в виде таблиц.

Некоторые специалисты такой способ представления информации называли таблицами решений, другие — табличными алгоритмами. Теоре­тики реляционных баз данных табличный способ представления информации называли даталогическими моделями.

Основоположником теории реляционных баз данных считается сотрудник фирмы IBM доктор Э. Ф. Кодд, опубликовавший 6 июня 1970 г. статью «Реляционная модель данных для больших коллек­тивных банков данных. В этой статье впервые и был использован термин «ре­ляционная модель данных», что и положило начало реляцион­ным базам данных.

Теория реляционных баз данных, разработанная в 1970-х гг. в США доктором Э. Ф. Коддом, опиралась на математический аппарат те­ории множеств.

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

В настоящее время теоретическую основу проектирования баз данных (БД) состав­ляет математический аппарат реляционной алгебры.

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

Таблица базы данных — двумерный массив, содержащий информацию об одном классе объектов. В теории реляционной алгебры двумерный массив (таблицу) называют отношением.

Таблица состоит из следующих элементов: поле, ячейка, запись.

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

Поля (столбцы)

Ячейка содержит конкретное значение соответствующего поля (признака одного объекта).

Запись — строка таблицы. Она содержит значения всех призна­ков, характеризующих один объект. Число записей (строк) соот­ветствует числу объектов, данные о которых содержатся в таб­лице.

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

В табл. 2.1 приведены термины, применяемые в теории и прак­тике разработки реляционных баз данных.

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

Ключом считается поле, значения которого однозначно опреде­ляют значения всех остальных полей в таблице. Например, поле «Номер паспорта», или «Идентификационный номер налогопла­тельщика (ИНН)», однозначно определяет характеристики любого физического лица (при составлении соответствующих таблиц баз данных для отделов кадров или бухгалтерии предприятия).

Термины реляционных баз данных

Теория БД Реляционные СУБД(FoxPro, Microsoft Access) SQL Server 7.0
Отношение (Relation) Таблица (Table) Таблица (Table)
Атрибут (Attribute) Поле (Field) Колонка (Column)
Кортеж (Tuple) Запись (Record) Строка (Row)

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

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

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

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

•  не следует включать в состав ключа поля таблицы, значения; которых сами по себе однозначно идентифицируют записи в таб­лице. Например, не стоит создавать ключ, содержащий одновременно поля «номер паспорта» и «идентификационный номер налогоплателыцика», поскольку каждый из этих атрибутов может однозначно идентифицировать записи в таблице;

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

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

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

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

3. Типы взаимосвязей в модели: «один-к-одному», «один-ко-многим» и «многие-ко-многим».

  • Между таблицами устанавливаются следующие типы связей: «один к одному»; «один ко многим»; «многие ко многим»:
  • •  связь «один к одному» устанавливается в случаях, когда конкретная строка главной таблицы в любой момент времени связана только с одной строкой подчиненной таблицы;
  • •  связь «один ко многим» устанавливается в случаях, когда конкретная строка главной таблицы в любой момент времени связана с несколькими строками подчиненной таблицы; при этом любая строка подчиненной таблицы связана только с од­ной строкой главной таблицы;
  • • связь «многие ко многим» устанавливается в случаях, ког­да конкретная строка главной таблицы в любой момент време­ни связана с несколькими строками подчиненной таблицы и в то же время одна строка подчиненной таблицы связана с не­сколькими строками

Источник: http://gouspo.ru/?p=207

Базы данных

  • МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
  • Государственное образовательное учреждение
  • высшего  профессионального образования
  • Московский физико-технический институт
  • (государственный университет)
  •                                                                               УТВЕРЖДАЮ
  •                                                                Проректор по учебной работе

                                                                                     Ю.А. Самарский

  1.                                                                                      22 января 2004 г.
  2. П Р О Г Р А М М А
  3. по курсу:  БАЗЫ ДАННЫХ
  4. по направлению    511600
  5. факультет               ФУПМ
  6. кафедра математических основ управления
  7. курс       
    II

  8. семестр   4
  9. лекции    32 часа         Экзамен  –  нет
  10. семинары  –  нет         Зачёт с оценкой  –  4 семестр
  11. лабораторные занятия   –   32 часа
  12. самостоятельная работа  –  2 часа в неделю
  13. ВСЕГО ЧАСОВ    64

Программу и задание составил доц., к.ф.- м.н. Бездушный А.Н.

Программа утверждена на заседании кафедры математических основ управления 26 декабря 2003 г.

Заведующий кафедрой  С.А. Гуз

1. Основные концепции баз данных

Системы управления базами данных. Понятия базы данных, системы баз данных и систем управления базами данных (СУБД). Требования к СУБД. Характеристики, функции СУБД.

2. Архитектура систем баз данных

ANSI/SPARC архитектура систем баз данных. Три уровня абстракции данных. Администратор базы данных. Структура СУБД. Объекты логической структуры хранения базы данных. Физическая структура базы данных.

Распределение оперативной памяти. Процессы, обеспечивающие работу сервера баз данных. Экземпляр СУБД. Централизованная архитектура и архитектура «клиент-сервер». Разновидности архитектуры «клиент-сервер».

3. Модели данных (обзор и сравнение)

Реляционная модель. Иерархическая модель. Сетевая модель. Понятие нормализации. Приведение к иерархии.

4. Объекты реляционных баз данных

Таблицы. Представления. Последовательности. Триггеры. Хранимые процедуры. Пакеты. Синонимы. Связи. Использование словаря базы данных.

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

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

6. Язык

запросов
Structured Query Language (SQL)

Историческая справка. Терминология SQL. Определение схем данных: создание и уничтожение таблиц и индексов. Использование индексов. Операции манипулирования данными: классификация. Операция выборки: определение, простая выборка, исключение дубликатов, выборка вычисляемых значений, ограниченная выборка, выборка с упорядочиванием.

Операции соединения: простое соединение, соединение трёх таблиц, соединение таблицы с ней самой. Вложенные запросы. Подзапросы. Простой подзапрос. Подзапрос с несколькими уровнями. Использование одной и той же таблицы в подзапросе. Стандартные функции. Группы. Операция объединения UNION. Представления. Встроенный SQL. Операции с курсорами.

7. Введение в проектирование реляционных баз данных

Нормализация, функциональные и многозначные зависимости. Нормальные формы. Первая, вторая и третья нормальные формы. Нормальная форма Бойса-Кодда. Четвёртая и пятая нормальные формы. Процедура нормализации. Процедура проектирования. Модель «сущность-связь» (ER-модель).

Читайте также:  Президент рф - студенческий портал

Основные понятия модели  «сущность-связь». Характеристика связей и язык моделирования. Классификация сущностей. Первичные и внешние ключи. Ограничения целостности. Построение инфологической модели. Пример разработки простой ER-модели. Концептуальные и физические ER-модели.

8. Восстановление данных

Типы сбоев. Восстановление системы. Средства восстановления базы данных. Порядок восстановления базы данных. Понятие транзакции. ACID-транзакции. Управление транзакциями. Транзакции READ JNLY. Фиксация и откат транзакций. Точки сохранения. Дискретные транзакции. Двухфазная фиксация. Поддержка транзакций в языке SQL. Команды COMMIT и ROLLBACK.

9. Совместное использование базы данных

Проблемы совместного доступа к базе данных. Соперничество, целостность и согласованность данных. Понятие блокировки. Виды блокировок. Механизмы автоматических блокировок. Явная блокировка. Тупики. Понятие сериализуемости. Поддержка блокировок в языке SQL. Служба управления блокировками.

10. Безопасность данных

Обязательное и избирательное управления доступом к базе данных. Поддержка безопасности данных в языке SQL; представления, директивы GRANT и REVOKE.

11. Целостность данных

Целостность атрибутов, отношений, базы данных. Ограничения целостности. Триггеры. Примеры реализации ограничений целостности и триггеров.

12. Обработка запросов

Этапы обработки запроса. Декомпозиция запроса. План выполнения запроса. Генерация эквивалентных планов. Оптимизация запросов. Стоимостная функция выполнения плана запроса.

13. Реляционная алгебра

Реляционная алгебра как формализм для внутреннего представления запроса. Синтаксис реляционной алгебры. Операции над множествами. Специальные реляционные операции. Операции расширения и подведения итогов.

14. Реляционное исчисление

Переменные кортежей. Кванторы. Выражения. Кортежные переменные и правильно построенные формулы. Целевые списки и выражения реляционного исчисления. Реляционное исчисление доменов.

СПИСОК ЛИТЕРАТУРЫ

1. Дейт К. Введение в системы баз данных Киев.: Диалектика, 1998. 784 с.

2. Гарсиа-Молина Г., Ульман Д., Уидом Д. Системы баз данных. Полный курс. М.: Вильямс, 2002. – 1088 с.

3. Коннолли Т., Бегг К., Страчан А. Базы данных: проектирование, реализация и сопровождение. Теория и практика. 2-е изд. Уч. пособ. М.: Вильямс, 2000. –1120 с.

4. Грабер М. Введение в SQL. М.: Лори, 1996.

5. Грабер М. Справочное руководство по SQL. – М.: Лори, 1997. – 291 с.

6. Боуман Д., Эмерсон С., Дарновски М. Практическое руководство по SQL. Киев: Диалектика, 1997.

7. Мейер Д. Теория реляционных баз данных. М.: Мир, 1987. – 608 с.

8. Ульман Дж. Основы систем баз данных. М.: Финансы и статистика, 1983. – 320 с.

9. Ульман Дж., Уидом Д. Основы систем баз данных. М.: Лори, 2000. – 374 с.

10. Цикритзис Д., Лоховски Ф. Модели данных. М.: Финансы и статистика, 1987. – 344 с.

11. Пушников А.Ю. Введение в системы управления базами данных. www.citforum.ru.

12. Кузнецов С.Д. Введение в системы управления базами данных //СУБД. – 1995.– № 1, 2, 3, 4, – 1996. – № 1, 2, 3, 4, 5.

13. Ладыженский Г.М. Системы управления базами данных – коротко о главном //СУБД. – 1995. – № 1, 2, 3, 4.

14. Кузнецов С.Д. SQL. Язык реляционных баз данных. М.: Майор, 2001. – 192 с.

15. Кузнецов С.Д. Введение в стандарты языка  баз данных SQL. Центр Информационных технологий. – 1998,

 http://www.citforum.ru/database/sqlbook/index.shtml.

16. Кузнецов С.Д. Методы оптимизации выполнения запросов в реляционных СУБД.

http://www.citforum.ru/database/articles/art_26.shtml.

17. Кузнецов С.Д. Дубликаты, неопределенные значения, первичные и возможные ключи и другие экзотические прелести языка SQL // СУБД. –1997. –№ 3. –С. 77 – 80.

18. Кузнецов С.Д. Неопределенная информация и трехзначная логика // СУБД. –1997. – № 5. – С. 65 – 67.

19. Кириллов В.В., Громов Г.Ю. Структуризированный язык запросов (SQL) //Центр Информационных технологий. –1998,

http://www.citforum.ru/database/sql_kg/index.shtml.

20. Чамберлин Д.Д. и др. SEQUEL 2: унифицированный подход к определению, манипулированию и контролю данных

// СУБД. –1996. № 1. С. 144 – 159.

21. Злуф М.М. Query-by-Example: язык баз данных // СУБД. 1996. – № 3. – С. 149 – 160.

22. Зиндер Е.З. Критерии выбора современной СУБД как объекта инвестиций для развития предприятия // СУБД. –1995. – № 1. С. 35 – 48.

23. Чен П. Модель «сущность-связь» – шаг к единому представлению о данных // СУБД. – 1995. – № 3. – С. 137 – 158.

24. Кодд Э.Ф. Расширение реляционной модели для лучшего отражения семантики // СУБД. –1996. –№ 5-6. –С. 163 – 192.

25. Когаловский М.Р. Энциклопедия технологий баз данных. М.: Финансы и статистика, 2002. – 800 с.

Источник: https://MIPT.ru/dcam/students/curriculum/prog/inform/database.php

Реляционная алгебра — это… Что такое Реляционная алгебра?

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

Первоначальный набор из 8 операций был предложен Э. Коддом в 1970-е годы и включал как операции, которые до сих пор используются (проекция, соединение и т.д.), так и операции, которые не вошли в употребление (например, деление отношений).

В процессе развития реляционной теории и практики было предложено несколько новых реляционных операций, например полусоединение (SEMI-JOIN) и полуразность, или анти-полусоединение (ANTI-SEMI-JOIN)[1][2], CROSS APPLY и OUTER APPLY, транзитивное замыкание (TCLOSE) и др.

Поскольку многие операции выразимы друг через друга, в составе реляционной алгебры можно выделить несколько вариантов базиса (набора операций, через который выразимы все остальные). Наиболее известный и строго определённый базис (алгебра А) предложен Кристофером Дейтом и Хью Дарвеном[3].

Реляционная алгебра и реляционное исчисление эквиваленты по своей выразительной силе[4]. Существуют правила преобразования запросов между ними.

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

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

  • Операции над одним отношением называются унарными, над двумя отношениями — бинарными, над тремя — тернарными (таковые практически неизвестны).
  • Пример унарной операции — проекция, пример бинарной операции — объединение.
  • N-арную реляционную операцию f можно представить функцией, возвращающей отношение и имеющей n отношений в качестве аргументов:

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

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

Ограничения на операции

Некоторые реляционные операции, в частности, операции объединения, пересечения и вычитания, требуют, чтобы отношения имели совпадающие (одинаковые) заголовки (схемы). Это означает, что совпадают количество атрибутов, названия атрибутов и тип (домен) одноимённых атрибутов.

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

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

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

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

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

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, …, Am, B1, B2, …, Bm), заголовок которого является сцеплением заголовков отношений A(A1, A2, …, Am) и B(B1, B2, …, Bm), а тело состоит из кортежей, являющихся сцеплением кортежей отношений A и B:

(a1, a2, …, am, b1, b2, …, bm)

таких, что

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

Синтаксис:

A TIMES B

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

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

A WHERE c

Проекция

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

Отношение с заголовком (X, Y, …, Z) и телом, содержащим множество кортежей вида (x, y, …, z), таких, для которых в отношении A найдутся кортежи со значением атрибута X равным x, значением атрибута Y равным y, …, значением атрибута Z равным z. При выполнении проекции выделяется «вертикальная» вырезка отношения-операнда с естественным уничтожением потенциально возникающих кортежей-дубликатов.
Синтаксис:

A[X, Y, …, Z]

или

PROJECT A {x, y, …, z}

Соединение

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

(A TIMES B) WHERE c

Деление

Отношение с заголовком (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

Примечания

  1. Introduction to Joins
  2. Дейт, Кристофер. SQL и реляционная теория. Как грамотно писать код на SQL. — Символ-Плюс, 2010
  3. К. Дейт, Хью Дарвен. Основы будущих систем баз данных. Третий манифест. М: Янус-К, 2004.
  4. Грей, 1989, с. 188
  • Грей П. Логика, алгебра и базы данных. — М.: Машиностроение, 1989. — С. 188-213. — 368 с.
  • http://www.citforum.ru/database/dblearn/

Источник: https://dic.academic.ru/dic.nsf/ruwiki/41618

Ссылка на основную публикацию
Adblock
detector