Реляционная алгебра. Операции реляционной алгебры: выборка, проекция, объединение, пересечение, разность, произведение, деление,
Реляционная алгебра — формальная система манипулирования отношениями в реляционной модели данных. [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» Вы найдёт немало примеров комбинаций различных логических условий для выборок из базы данных.
Операция проекции
- Операция проекции (
) работает, как и операция выборки, только с одним отношением и определяет новое отношение R, в котором есть лишь те атрибуты (столбцы), которые заданы в операции, и их значения.
- Запрос SQL
- SELECT DISTINCT A4, A3 from R3
- Пусть вновь дано то же отношение R3:
R3 | |||
A1 | A2 | A3 | A4 |
3 | hh | yl | ms |
4 | pp | a1 | sr |
1 | rr | yl | ms |
Из исходного отношения выбираем только столбцы А4 и А3 и видим, что строки со значениями — первая и третья — идентичны. Исключаем дубликат (за это отвечает ключевое слово DISTINCT в SQL-запросе, которое говорит, что нужно выбрать только уникальные записи) и получаем следующее новое отношение, в котором два атрибута и две строки (записи):
Операция объединения
Результатом объединения двух множеств (отношений) А и В () будет такое множество (отношение) С, которое включает в себя те и только те элементы, которые есть или во множестве А или во множестве В.
Говоря упрощённо, все элементы множества А и множества В, за исключением дубликатов, образующихся за счёт того, что некоторые элементы есть и в первом, и во втором множестве.
Операция объединения реляционной алгебры идентична операции объединения множеств, которая также описана в материале «Множества и операции над множествами».
- Запрос 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 должны быть совместимы по объединению. Операция разности реляционной алгебры идентична операции разности множеств, которая также описана в материале «Множества и операции над множествами».
- Запрос SQL
- SELECT A1, A2, A3 from R2 EXCEPT SELECT A1, A2, A3 from R1
- Установим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Вновь даны два отношения R1 и R2:
R1 | R2 | ||||
A1 | A2 | A3 | A1 | A2 | A3 |
Z7 | aa | w11 | X8 | pp | k21 |
B7 | hh | h15 | Q2 | ee | h15 |
X8 | pp | w11 | X8 | pp | w11 |
Из отношения R2 исключаем строку, которая есть также в отношении R2 — третью — и получаем новое отношение:
В некоторых диалектах 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 удовлетворяющие предикату Р. Значением предиката Р может быть один из операторов сравнения (, >=, = или !=).
- Запрос SQL
- SELECT * from R3, R4 WHERE A1>=A5
- Посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса 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) и зависят от одной или нескольких бинарных переменных. Это так называемые булевы функции.
Из одного или нескольких высказываний, принимаемых за простые, можно составлять сложные высказывания, которые будут бинарными функциями простых высказываний.
Объединение простых высказываний в сложные в алгебре логики производится без учета внутреннего содержания (смысла) этих высказываний.
Используются определенные логические операции (или логические связи), позволяющие объединять некоторые данные высказывания (постоянные или переменные) в более сложные (постоянные или переменные).
К числу основных логических операций относятся следующие: отрицание, конъюнкция, дизъюнкция, эквивалентность, импликация. Логические операции задаются таблично, как функции простых высказываний.
Отрицание высказывания. Отрицание высказывания А — это высказывание, которое истинно, когда А ложно, и ложно, когда А истинно; обозначается: А; читается: «не А».
Конъюнкция двух высказываний.
Конъюнкция двух высказываний — это сложное высказывание, которое истинно в случае истинности обоих высказываний, его образующих, и ложно в остальных случаях.
Конъюнкция двух высказываний обозначается: А В; читается «А и В». Знак конъюнкции «» имеет смысл союза «и». Операция конъюнкции имеет также смысл логического умножения и может обозначается знаком «&».
|
Дизъюнкция двух высказываний. Дизъюнкция двух высказываний — это сложное высказывание, которое ложно в случае ложности обоих составляющих его высказываний и истинно в остальных случаях.
Операция дизъюнкции обозначается: AB; читается: «А или В» (другое обозначение: А + В; другое название — «логическое сложение»).
Знак логической связи «» имеет смысл союза «или» и называется знаком дизъюнкции. Союз «или» может употребляться в нескольких различных смыслах.
Знак «» может иметь смысл «или», употребленный, например, в фразе: «При звоне будильника Петя или Ваня проснется» (здесь «или» не исключает возможности того, что проснутся оба). В данном случае дизъюнкция имеет смысл неразделительного «или».
Существует еще исключающее значение союза «или» (например: «Выбирай: он или я»), которое тоже может быть принято за один из видов логических операций, но его не следует смешивать с дизъюнкцией.
|
Эквивалентность двух высказываний.
Эквивалентность двух высказываний — это сложное высказывание, истинное тогда, когда значения истинности составляющих высказываний одинаковы, и ложное — в противном случае; обозначается: А В; читается: «А эквивалентно В». Для эквивалентности справедливы высказывания, которые можно записать следующим образом: 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
Базы данных
- МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
- Государственное образовательное учреждение
- высшего профессионального образования
- Московский физико-технический институт
- (государственный университет)
- УТВЕРЖДАЮ
- Проректор по учебной работе
Ю.А. Самарский
- 22 января 2004 г.
- П Р О Г Р А М М А
- по курсу: БАЗЫ ДАННЫХ
- по направлению 511600
- факультет ФУПМ
- кафедра математических основ управления
-
курс
II - семестр 4
- лекции 32 часа Экзамен – нет
- семинары – нет Зачёт с оценкой – 4 семестр
- лабораторные занятия – 32 часа
- самостоятельная работа – 2 часа в неделю
- ВСЕГО ЧАСОВ 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
Примечания
- ↑ Introduction to Joins
- ↑ Дейт, Кристофер. SQL и реляционная теория. Как грамотно писать код на SQL. — Символ-Плюс, 2010
- ↑ К. Дейт, Хью Дарвен. Основы будущих систем баз данных. Третий манифест. М: Янус-К, 2004.
- ↑ Грей, 1989, с. 188
- Грей П. Логика, алгебра и базы данных. — М.: Машиностроение, 1989. — С. 188-213. — 368 с.
- http://www.citforum.ru/database/dblearn/
Источник: https://dic.academic.ru/dic.nsf/ruwiki/41618