Lektsii_po_Diskretnoy_Matematike / Глава 2
.pdfКононов Василий, Сагитова Адиля и Главатских Павел |
Глава 2 |
|
|
Глава 2. Реляционная алгебра. |
|
|
Неделимый объект или скаляр |
– это объект, |
Определение. |
Основные понятия. |
|
представляющий собой неделимое целое, т.е. не являющийся множеством.
Определение. Домен – это именованное{ } множество скаляров{ одного типа.} Пример. Натуральные числа = 1,2,3, … . Русские имена = Иван, Пётр, … .
Замечание. Между понятиями домена и типа данных в программировании существует прямое соответствие. Обычно домен задаёт допустимое множество значений, которые может принимать предметная переменная. Однако в понятие типа данных входят также и операции над типом. Домен, в свою очередь, явно операции не определяет.
||В дальнейшем будет дано определение типа.
Определение. n-местное (n-арное) отношение – это множество (класс) упорядоченных систем из элементов (упорядоченных n-ок, как частный случай для бинарных отношений – упорядоченных пар) членов некоторого множества. Это множество называется полем данного отношения.
||В дальнейшем для сокращения будем называть «n-местные отношения» просто ||«отношениями».
|
Определение. |
|
Отношение |
|
|
– |
это |
n-арное отношение |
на доменах |
||||||||||||
1 × 2 × … × |
|
– атрибут, назовём |
|
|
|
отношения. |
|
|
|
|
|
||||||||||
|
|
|
. Имя каждого домена назовём атрибутом, а выражение |
||||||||||||||||||
вида |
|
, где |
|
|
1 |
|
2 |
|
|
схемой |
|
|
|
|
|
|
|
||||
//“ ” –(является1, 2, … ,подмножеством) |
, |
|
|
|
|
– декартово произведение. |
|
||||||||||||||
|
|
Реляционная |
алгебра |
|
|
|
|
|
|
|
|
|
|
|
|||||||
Определение. |
|
× |
× …–× это |
|
совокупность |
носителя |
|
и |
|||||||||||||
сигнатуры , определяемых следующим образом: |
|
|
, где |
|
– |
множество |
|||||||||||||||
|
|
|
|
|
|
||||||||||||||||
отношений разной степени арности, |
|
– |
множество операций |
реляционной |
|||||||||||||||||
|
|
|
|
= |
|
|
|
|
|
|
|||||||||||
алгебры: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1)теоретико-множественные операции;
2)специальные операции.
Каждый элемент отношения называется кортежом.
Кононов Василий, Сагитова Адиля и Главатских Павел Глава 2
Элементы отношения (его атрибуты, схема, кортежи) определяют плоскую
таблицу аналогично тому, как бинарное отношение задаёт матрицу |
× |
. Т.е. |
|||||||||||||
отношение ( 1 |
, 2 |
, … , ) будет задавать плоскую таблицу |
: |
|
|||||||||||
|
|
1 |
|
2 |
|
|
3 |
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
|
|
1 |
|
… |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
2 |
|
|
2 |
|
… |
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
3 |
|
|
3 |
|
… |
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
… |
|
… |
|
|
… |
|
… |
|
|
… |
|
|
|
Пример. |
|
|
|
|
|
|
|
|
|
|
|
|
|||
Таблица1 |
«Студент2 » |
(№3 |
зачётной |
книжки |
, |
ФИО, Группа). Здесь |
|||||||||
Соответственно, |
|
, |
, |
|
, …, |
, где – домены. |
|
|
№ зачётной книжки, ФИО и группа – это атрибуты (имена соответствующих доменов). Наборы кортежей, которые составляют конкретную таблицу,
соответствующей схеме э ого отношения, могут выглядеть следующим образом: |
|||
Студент = { 123, |
ИвановИ. И. , |
К4−221 |
|
131, |
ПетровП. П. , |
К4− |
281 |
211, |
КузнецовВ. И. , К4 |
−361 }. |
Степень отношения определяет количество атрибутов в схеме. Кардинальное число (или мощность) отношения определяет количество кортежей в отношении.
Соотношения между формальными и неформальными определениями:
Неформальные |
Формальные |
|
|
Таблица |
Отношение |
|
|
Строка, запись |
Кортеж |
|
|
Количество строк |
Кардинальное число |
|
|
Столбец, поле |
Атрибут |
|
|
Тип данных |
Домен |
|
|
Количество столбцов |
Степень отношения |
|
|
Кононов Василий, Сагитова Адиля и Главатских Павел |
Глава 2 |
Задачи, которые решаются при помощи реляционных баз данных:
1)Поиск информации – решается при помощи реляционной алгебры. Результатом любой операции реляционной алгебры является отношение, содержащее только необходимую часть от всех данных, содержащихся в базе.
2)Определение структуры базы данных – решается при помощи определения схемы отношений. Схема базы данных – схема (модель) некоторой предметной области (в которой мы работаем).
3)Определение ограничений целостности данных – решается с помощью формул исчисления предикатов (с формально-теоретической точки зрения). Пример ограничения целостности данных: в рассмотренной выше таблице «Студент» есть графа «№ зачётной книжки». Если в базе будет храниться
информация о студентах с одинаковыми номерами зачётных книжек – это не есть хорошоОперации, т.к. в этом случаереляционнойтеряется однозначностьалгебры. .
Пусть заданы 2 отношения: Доср_сдача (№ зачётки, ФИО, предмет) и Сдача_в_срок (№ зачётки, ФИО, предмет).
Определим, с какими данными (наборами кортежей) мы будем работать:
Сдача_в_срок = С = { < 121, Иванов, ДМ >,
<123, Петров, Теория БД >,
<124, Сидоров, Физика > }
Доср_сдача = Д = { < 121, Иванов, ДМ > }.
//Т.е. Иванов попытался сдать досрочно, но не сдал, а сдал потом, как и все, в срок.
Теоретико-множественные операции (здесь у множеств должны совпадать
|
|
|
|
( 1, 2 |
, … , ) = 1( 1, 2, … , ) 2( 1, 2, …, |
, , ) |
|
||||
количество столбцов, а также домены): |
( 1, 2, … , ) |
|
1 |
2 |
|
|
|||||
|
: |
|
– |
|
|
|
|
; |
|||
1) Объединение |
|
|
|
|
|
|
|
||||
результат операции – это отношение |
|
на столбцах |
|
|
…, |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
{< 121, Иванов, ДМ >, < 123, Петров, Теория БД >, < 124, Сидоров, Физика >}. |
|||||||||||
Д∩ С |
= { < 121, |
– |
( 1, 2 |
, … , ) = 1( 1, 2, … , ) ∩ 2( 1, 2, … , ) |
: |
||||||
Д 2)С =Пересечение |
|
|
|
|
|
|
|
Иванов, ДМ > }.
|
|
= { < 123, Петров, ( 1, 2 |
, … , ) |
= 1( 1, 2, … , ) |
( 1, 2, … , ) |
|
||||||||||||||||
Кононов Василий, Сагитова Адиля и Главатских Павел |
|
|
|
|
|
|
|
|
|
|
Глава 2 |
|||||||||||
3) |
Разность |
– |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
: |
|
|
ДекартовоС Д |
|
|
|
Теория БД >, < 124, Сидоров, Физика > }. |
|
|
|||||||||||||||
4) |
произведение – |
= |
|
|
, … , |
|
× |
|
, … , |
: |
|
|||||||||||
|
|
= { < , … , |
, |
, … , |
|
|
|
|||||||||||||||
|
Д× С |
|
121,( 1 |
Иванов |
,1 |
ДМ, 121,) |
Иванов1( 1 , ДМ )>, < 2121,( 1 |
Иванов) , ДМ, 123, |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Петров, Теория БД >, < 121, …, 124, … >, < 123, …, 121, … >, …}. |
|
|
|
||||||||||||||||||
|
Специальные операции: |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|||||
|
атрибутов |
|
1 |
( 1, … , )[ ] = ( ) |
|
|
|
|
|
|
|
|
||||||||||
1) |
|
С (№1, …зачётки, |
, ФИО, предмет) [№ |
зачётки] ={ {121,, … ,123,} 124}. |
|
|||||||||||||||||
Проекция – это |
|
|
|
|
|
|
|
|
|
|
; т.е. отношение |
|
с набором |
|||||||||
|
|
|
|
|
спроецировано на |
|
, где |
|
|
|
|
|
: |
|
|
|||||||
2) |
Ограничение – 1( 1, … , )[БулевовыражениеподА] = |
( 1 |
, … , ): |
|
Д (№ зачётки, ФИО, предмет) [Предмет = 'ДМ'] = { 121, Иванов, ДМ }.
( ) ( )[ ] ( )
3) Соединение –
1, … , , 1, … , = 1 1, … , Булевовыражение 2 1, … , :
Д (№ зачётки, ФИО, предмет) [№зач. = №зач.] Группа (№ зач., № группы) = …
Если таблица выглядит следующим образом:
|
|
|
|
№ зачётки |
|
|
|
|
|
|
|
№ группы |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
121 |
|
|
|
|
|
|
|
|
К4-221 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
123 |
|
|
|
|
|
|
|
|
К6-222 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
124 |
|
|
|
|
|
|
|
|
К4-361 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
220 |
|
|
|
|
|
|
|
|
К8-331 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
то … = { 121, Иванов |
ДМ, 121, К4-221}. |
|
|
( 1 |
, … , ) ÷ 2 |
( 1, … , .) |
|
||||||||||||
она |
|
|
|
( 1, … , |
, 1, … , ) = 1 |
|
|||||||||||||
Пример. Пусть даны |
|
1 |
÷ 2 |
= 1 |
[ |
] ∕ ( 1[ ] × ) ∕ 1 [и] |
. Задаётся |
||||||||||||
4) Деление – |
|
|
|
|
|
|
1 |
= { , , , , , } |
|
||||||||||
Тогда 1 |
÷ 2 = . |
|
|
|
|
|
2 |
{ , } |
|||||||||||
|
следующим образом: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
наборы кортежей |
|
|
|
|
|
|
|
|
|
. |
Реляционная алгебра. Неформальное определение. |
Глава 2 |
Кононов Василий, Саг това Адиля и Главатских Павел |
Основной объект в реляционных базах данных (БД) – плоская таблица с данными, ячейки которой не могут содержать других таблиц.
Определение. База данных – это совокупность именованных таблиц. Каждая строка представляет собой запись о некотором объекте реального мира или его свойствах.
Для удобства идентификации записей вводят понятие первичного ключа.
Определение. Первичный ключ таблицы – это один или несколько столбцов, значение которого в каждой строке уникально, т.е. нет 2-х или более строк, в которых значения в этих столбцах совпадают. Таким образом, можно говорить о том, что значения в остальных столбцах однозначно идентифицируются ключом.
В рассмотренной выше таблице «Студент» в качестве первичного ключа можно использовать № зачётной книжки# . Часто, для удобства чтения, первичный
ключ обозначают символом «диез» – “ ”: «Студент (# № зачётной книжки, ФИО, группа)». Если первичный ключСвязь– основноймежду таблицами, то д езов стоит. несколько.
Первичный ключ может быть использован в качестве ссылки в другой таблице. Таким образом, мы избегаем копирования данных и расхождения в данных при неаккуратном их изменении.
Пример. Пусть есть 2 таблицы, в которых есть одинаковый атрибут (группа):
«Студент (# № зачётной книжки, ФИО, группа)» и
«Предмет (преподаватель, курс, группа)».
Допустим, что нам необходимо переименовать группы во всём институте. Предположим, что мы переименовали группы только в таблице «Студент», забыв это сделать во 2-й. В этом случае возникнет нарушение целостности данных. Если сделать иначе и ввести отдельную таблицу «Группа (#10, группа)», то в первых 2-х
||#10 – произвольный абстрактный номер, являющийся первичным ключом.
таблицах вместо атрибута «группа» можно писать этот уникальный идентификатор (10) в качестве ссылки. Таким образом, достаточно переименовать строковое представление имени группы только в одной таблице.
Определение. Внешний ключ – ссылка на первичный ключ другой таблицы.
Кононов Василий, Сагитова Адиля и Главатских Павел Глава 2
Введём обозначения: PK (primary key) – первичный ключ, FK (foreign key) – внешний ключ.
1)PK и FK должны быть определены на одном и том же домене.
2)В таблице с FK он не должен принимать значения, которые не принимает PK
в дрПонятиеугой таблиценормализации(т.е. нет ссылоки«вограниченияникуда»). на таблицах.
Определение. Нормализация – это приведение данных в таблице к определённому виду, заданному набором ограничений.
Про нормализованную таблицу говорят, что она находится в нормальной форме. Существуют различные нормальные формы (1NF, 2NF, 3NF, 3NF усиленная).
Набор ограничений для 1NF (1-й нормальной формы):
1)В таблице нет одинаковых строк.
Это страховка от избыточности данных; а также неявное указание на то, что в таблице используются первичные ключи, которые по определению уникальны. Существует возможность организовывать ссылки между таблицами. Другими словами, пусть в таблице есть первичный ключ. Тогда, если таблица не находится в 1-й нормальной форме, то первичные ключи дублируются. А это противоречит определению первичного ключа.
2)Строки не упорядочены сверху вниз.
3)Столбцы не упорядочены слева направо.
4)Все значения атрибутов атомарны.
В качестве атрибутов не могут выступать другие таблицы, линейные списки и т.д. Например, существует тип в базах данных: BLOB – Binary large object.
Для формального задания ограничений на таблицах можно использовать формулы исчисления предикатов. Так, например, для задания первичного ключа
ь формулы следующего вида:
можно, ,использова, , Студент( , , )&Студент( , , ) → ( = )&( = ) .
′ ′ ′ ′′ ′′ ′ ′ ′ ′ ′′ ′′ ′ ′′ ′ ′′
Что определяет эта формула? У нас есть отношение «Студент». Мы задаём предикат, структура которого соответствует схеме отношения. Т.е. у предиката такое же имя как у таблицы, количество′ его аргументов совпадает с количеством доменов в таблице. 1-й аргумент – это PK (первичный ключ).